Цикломатическая сложность

Мера структурной сложности программного обеспечения

Цикломатическая сложность — это программная метрика, используемая для обозначения сложности программы . Это количественная мера количества линейно независимых путей в исходном коде программы . Она была разработана Томасом Дж. МакКейбом-старшим в 1976 году.

Цикломатическая сложность вычисляется с использованием графа потока управления программы. Узлы графа соответствуют неделимым группам команд программы, а направленное ребро соединяет два узла, если вторая команда может быть выполнена сразу после первой команды. Цикломатическая сложность может также применяться к отдельным функциям , модулям , методам или классам внутри программы.

Одна из стратегий тестирования , названная МакКейбом, который первым ее предложил, тестированием базисного пути , заключается в тестировании каждого линейно независимого пути через программу. В этом случае количество тестовых случаев будет равно цикломатической сложности программы. ^[1]

Описание

Определение

Граф потока управления простой программы. Программа начинает выполняться в красном узле, затем входит в цикл (группа из трех узлов сразу под красным узлом). При выходе из цикла есть условный оператор (группа под циклом), и программа выходит в синем узле. Этот граф имеет девять ребер, восемь узлов и один связный компонент , поэтому цикломатическая сложность программы составляет 9 − 8 + 2×1 = 3 .

Существует несколько способов определения цикломатической сложности раздела исходного кода . Один из распространенных способов — это количество линейно независимых путей внутри него. Набор путей линейно независим, если набор ребер любого пути в не является объединением наборов ребер путей в некотором подмножестве . Если исходный код не содержал операторов потока управления (условных операторов или точек принятия решений), сложность была бы равна 1, поскольку в коде был бы только один путь. Если бы в коде был один оператор IF с одним условием , в коде было бы два пути: один, где оператор IF равен TRUE, и другой, где он равен FALSE. Здесь сложность была бы равна 2. Два вложенных оператора IF с одним условием или один IF с двумя условиями дали бы сложность 3. ${\displaystyle S}$ ${\displaystyle P}$ ${\displaystyle S}$ ${\displaystyle S/P}$

Другой способ определения цикломатической сложности программы — это рассмотрение ее графа потока управления , направленного графа, содержащего основные блоки программы, с ребром между двумя основными блоками, если управление может перейти от первого ко второму. Сложность M тогда определяется как ^[2]

$${\displaystyle M=E-N+2P,}$$

где

• E = количество ребер графа.
• N = количество узлов графа.
• P = количество подключенных компонентов .

Та же функция, представленная с использованием альтернативной формулировки, где каждая точка выхода соединена обратно с точкой входа. Этот граф имеет 10 ребер, восемь узлов и один связанный компонент , что также приводит к цикломатической сложности 3 с использованием альтернативной формулировки ( 10 − 8 + 1 = 3 ).

Альтернативная формулировка этого, как первоначально предлагалось, заключается в использовании графа, в котором каждая точка выхода связана обратно с точкой входа. В этом случае граф сильно связан . Здесь цикломатическая сложность программы равна цикломатическому числу ее графа (также известному как первое число Бетти ), которое определяется как ^[2] $${\displaystyle M=E-N+P.}$$

Это можно рассматривать как вычисление числа линейно независимых циклов , которые существуют в графе: тех циклов, которые не содержат других циклов внутри себя. Поскольку каждая точка выхода возвращается к точке входа, существует по крайней мере один такой цикл для каждой точки выхода.

Для одной программы (или подпрограммы, или метода) P всегда равно 1; более простая формула для одной подпрограммы выглядит так ^[3] $${\displaystyle M=E-N+2.}$$

Цикломатическая сложность может быть применена к нескольким таким программам или подпрограммам одновременно (например, ко всем методам в классе). В этих случаях P будет равно количеству рассматриваемых программ, и каждая подпрограмма будет отображаться как несвязное подмножество графа.

Маккейб показал, что цикломатическая сложность структурированной программы с одной точкой входа и одной точкой выхода равна числу точек принятия решений (выражений «if» или условных циклов), содержащихся в этой программе, плюс один. Это справедливо только для точек принятия решений, подсчитанных на самом низком уровне инструкций машинного уровня. ^[4] Решения, включающие составные предикаты, подобные тем, что встречаются в языках высокого уровня, следует IF cond1 AND cond2 THEN ...подсчитывать с точки зрения вовлеченных предикатных переменных. В этом примере следует подсчитать две точки принятия решений, поскольку на уровне машины это эквивалентно IF cond1 THEN IF cond2 THEN .... ^{[2] [5]}

Цикломатическая сложность может быть расширена до программы с несколькими точками выхода. В этом случае она равна где — число точек принятия решения в программе, а s — число точек выхода. ^{[5] [6]} $${\displaystyle \pi -s+2,}$$ ${\displaystyle \pi }$

Алгебраическая топология

Четный подграф графа (также известный как эйлеров подграф ) — это тот , в котором каждая вершина инцидентна четному числу ребер. Такие подграфы являются объединениями циклов и изолированных вершин. Подграфы будут идентифицироваться по их наборам ребер, что эквивалентно рассмотрению только тех четных подграфов, которые содержат все вершины полного графа.

Множество всех четных подграфов графа замкнуто относительно симметрической разности и, таким образом, может рассматриваться как векторное пространство над GF(2) . Это векторное пространство называется пространством циклов графа. Цикломатическое число графа определяется как размерность этого пространства. Поскольку GF(2) имеет два элемента, а пространство циклов обязательно конечно, цикломатическое число также равно 2-логарифму числа элементов в пространстве циклов.

Базис для пространства циклов легко построить, сначала зафиксировав остовной лес графа, а затем рассмотрев циклы, образованные одним ребром, не входящим в лес, и путем в лесу, соединяющим конечные точки этого ребра. Эти циклы образуют базис для пространства циклов. Цикломатическое число также равно числу ребер, не входящих в максимальный остовной лес графа. Поскольку число ребер в максимальном остовном лесу графа равно числу вершин за вычетом числа компонентов, формула определяет цикломатическое число. ^[7] ${\displaystyle E-N+P}$

Цикломатическая сложность может быть также определена как относительное число Бетти , размер относительной группы гомологий :

$${\displaystyle M:=b_{1}(G,t):=\operatorname {rank} H_{1}(G,t),}$$

что читается как «ранг первой группы гомологии графа G относительно конечных узлов t ». Это технический способ сказать «количество линейно независимых путей через потоковый граф от входа до выхода», где:

• «линейно независимый» соответствует гомологии, и возврат не учитывается дважды;
• «пути» соответствуют первой гомологии (путь — это одномерный объект); и
• «относительный» означает, что путь должен начинаться и заканчиваться в точке входа (или выхода).

Эту цикломатическую сложность можно вычислить. Ее также можно вычислить с помощью абсолютного числа Бетти , определив конечные узлы на данном компоненте или нарисовав пути, соединяющие выходы со входом. Новый, дополненный граф получает ${\displaystyle {\tilde {G}}}$ $${\displaystyle M=b_{1}({\tilde {G}})=\operatorname {rank} H_{1}({\tilde {G}}).}$$

Его также можно вычислить с помощью гомотопии . Если (связанный) граф потока управления рассматривается как одномерный комплекс CW, называемый , фундаментальная группа будет . Значение представляет собой цикломатическую сложность. Фундаментальная группа подсчитывает, сколько циклов проходит через граф до гомотопии, выравниваясь, как и ожидалось. ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \pi _{1}(X)\cong \mathbb {Z} ^{*n}}$ ${\displaystyle n+1}$

Интерпретация

В своей презентации «Метрики качества программного обеспечения для выявления рисков» ^[8] для Министерства внутренней безопасности Том МакКейб представил следующую классификацию цикломатической сложности:

• 1 - 10: Простая процедура, небольшой риск
• 11 - 20: Более сложный, умеренный риск
• 21 - 50: Сложный, высокий риск
• > 50: Непроверяемый код, очень высокий риск

Приложения

Ограничение сложности во время разработки

Одним из первоначальных применений МакКейба было ограничение сложности процедур во время разработки программ. Он рекомендовал программистам подсчитывать сложность модулей, которые они разрабатывают, и разбивать их на более мелкие модули всякий раз, когда цикломатическая сложность модуля превышает 10. ^[2] Эта практика была принята методологией структурированного тестирования NIST , которая отметила, что с момента первоначальной публикации МакКейба цифра 10 получила существенные подтверждающие доказательства. Однако она также отметила, что в некоторых обстоятельствах может быть целесообразно ослабить ограничение и разрешить модули со сложностью до 15. Поскольку методология признавала, что иногда возникали причины для выхода за пределы согласованного предела, она сформулировала свою рекомендацию следующим образом: «Для каждого модуля либо ограничьте цикломатическую сложность [согласованным пределом], либо предоставьте письменное объяснение того, почему предел был превышен». ^[9]

Измерение «структурированности» программы

Раздел VI статьи Маккейба 1976 года посвящен определению того, как выглядят графы потока управления (CFG) неструктурированных программ с точки зрения их подграфов, которые идентифицировал Маккейб. (Подробнее см. теорему о структурированной программе .) Маккейб завершил этот раздел, предложив численную меру того, насколько близка данная программа к идеалу структурированного программирования, т. е. ее «структурированности». Маккейб назвал меру, которую он разработал для этой цели, существенной сложностью . ^[2]

Для вычисления этой меры исходный CFG итеративно сокращается путем определения подграфов, имеющих один вход и одну точку выхода, которые затем заменяются одним узлом. Это сокращение соответствует тому, что сделал бы человек, если бы он извлек подпрограмму из большего фрагмента кода. (В настоящее время такой процесс подпадает под общий термин рефакторинга . ) Метод сокращения Маккейба позже был назван конденсацией в некоторых учебниках, поскольку он рассматривался как обобщение конденсации на компоненты, используемые в теории графов . ^[10] Если программа структурирована, то процесс сокращения/конденсации Маккейба сводит ее к одному узлу CFG. Напротив, если программа не структурирована, итеративный процесс определит неприводимую часть. Существенная мера сложности, определенная Маккейбом, — это просто цикломатическая сложность этого неприводимого графа, поэтому она будет равна точно 1 для всех структурированных программ, но больше единицы для неструктурированных программ. ^{[9] : 80}

Последствия для тестирования программного обеспечения

Другим применением цикломатической сложности является определение количества тестовых случаев, необходимых для достижения полного тестового покрытия конкретного модуля.

Это полезно из-за двух свойств цикломатической сложности M для конкретного модуля:

• M — верхняя граница количества тестовых случаев, необходимых для достижения полного покрытия ветвей .
• M — нижняя граница для числа путей через граф потока управления (CFG). Если предположить, что каждый тестовый случай занимает один путь, то число случаев, необходимых для достижения покрытия пути, равно числу путей, которые фактически могут быть выбраны. Но некоторые пути могут быть невозможны, поэтому , хотя число путей через CFG, очевидно, является верхней границей для числа тестовых случаев, необходимых для покрытия пути, это последнее число ( возможных путей) иногда меньше M.

Все три приведенных выше числа могут быть равны: покрытие ветвей цикломатическая сложность число путей. ${\displaystyle \leq }$ ${\displaystyle \leq }$

Например, рассмотрим программу, состоящую из двух последовательных операторов if-then-else.

если ( c1 ()) f1 (); иначе f2 ();   если ( c2 ()) f3 (); иначе f4 ();   

Граф потока управления исходного кода выше; красный круг — точка входа функции, а синий круг — точка выхода. Выход был соединен с входом, чтобы сделать граф сильно связанным.

В этом примере двух тестовых случаев достаточно для достижения полного покрытия ветвей, в то время как для полного покрытия путей необходимо четыре. Цикломатическая сложность программы равна 3 (поскольку сильно связанный граф для программы содержит 9 ребер, 7 узлов и 1 связный компонент) ( 9 − 7 + 1 ).

В общем, для полного тестирования модуля следует проверить все пути выполнения через модуль. Это означает, что модуль с высоким номером сложности требует больше усилий по тестированию, чем модуль с более низким значением, поскольку более высокий номер сложности указывает на большее количество путей через код. Это также означает, что модуль с более высокой сложностью сложнее понять, поскольку программист должен понимать различные пути и результаты этих путей.

К сожалению, не всегда практично проверять все возможные пути через программу. Учитывая пример выше, каждый раз, когда добавляется дополнительный оператор if-then-else, количество возможных путей увеличивается в 2 раза. По мере того, как программа растет таким образом, она быстро достигает точки, где проверка всех путей становится непрактичной.

Одна из распространенных стратегий тестирования, поддерживаемая, например, методологией структурированного тестирования NIST, заключается в использовании цикломатической сложности модуля для определения количества тестов «белого ящика» , необходимых для получения достаточного покрытия модуля. Почти во всех случаях, согласно такой методологии, модуль должен иметь по крайней мере столько же тестов, сколько его цикломатическая сложность. В большинстве случаев этого количества тестов достаточно для проверки всех соответствующих путей функции. ^[9]

В качестве примера функции, требующей большего, чем просто покрытие ветвей для точного тестирования, пересмотрите приведенную выше функцию. Однако предположим, что для избежания возникновения ошибки любой код, который вызывает либо f1(), f3()должен также вызывать другой. ^[a] Предполагая, что результаты c1()и c2()независимы, функция, представленная выше, содержит ошибку. Покрытие ветвей позволяет протестировать метод всего двумя тестами, например, следующими тестовыми случаями:

• c1()возвращает истину и c2()возвращает истину
• c1()возвращает false и c2()возвращает false

Ни один из этих случаев не выявляет ошибку. Однако, если мы используем цикломатическую сложность для указания количества требуемых тестов, число увеличивается до 3. Поэтому мы должны протестировать один из следующих путей:

• c1()возвращает true и c2()возвращает false
• c1()возвращает false и c2()возвращает true

Любой из этих тестов выявит ошибку.

Соотношение с количеством дефектов

Несколько исследований изучали корреляцию между числом цикломатической сложности МакКейба и частотой дефектов, возникающих в функции или методе. ^[11] Некоторые исследования ^[12] обнаружили положительную корреляцию между цикломатической сложностью и дефектами; функции и методы, которые имеют самую высокую сложность, как правило, также содержат больше всего дефектов. Однако корреляция между цикломатической сложностью и размером программы (обычно измеряемым в строках кода ) была продемонстрирована много раз. Лес Хаттон утверждал ^[13] , что сложность имеет ту же предсказательную способность, что и строки кода. Исследования, которые контролировали размер программы (т. е. сравнивали модули, которые имеют разную сложность, но схожий размер), как правило, менее убедительны, при этом многие не обнаружили значительной корреляции, в то время как другие нашли корреляцию. Некоторые исследователи подвергают сомнению обоснованность методов, используемых в исследованиях, не обнаружив никакой корреляции. ^[14] Хотя эта связь, вероятно, существует, ее нелегко использовать на практике. ^[15] Поскольку размер программы не является контролируемой характеристикой коммерческого программного обеспечения, полезность числа МакКейба была поставлена ​​под сомнение. ^[11] Суть этого наблюдения в том, что более крупные программы, как правило, более сложны и имеют больше дефектов. Уменьшение цикломатической сложности кода не доказано, что уменьшает количество ошибок или багов в этом коде. Однако международные стандарты безопасности, такие как ISO 26262 , предписывают руководящие принципы кодирования, которые обеспечивают низкую сложность кода. ^[16]

Смотрите также

• Сложность программирования
• Ловушка сложности
• Компьютерная программа
• Компьютерное программирование
• Поток управления
• Путь от решения к решению
• Проектирование предикатов
• Основная сложность (числовая мера «структурированности»)
• Меры сложности Холстеда
• Разработка программного обеспечения
• Тестирование программного обеспечения
• Статический анализ программы
• Ремонтопригодность

Примечания

1. Это довольно распространенный тип состояния; рассмотрим возможность f1выделения некоторого ресурса, который затем f3высвобождается.

Ссылки

1. Эй Джей Соби. «Тестирование базового пути».
2. McCabe (декабрь 1976 г.). «Мера сложности». Труды IEEE по программной инженерии . SE-2 (4): 308–320. doi :10.1109/tse.1976.233837. S2CID  9116234.
3. Филип А. Лапланте (25 апреля 2007 г.). Что каждый инженер должен знать о программной инженерии . CRC Press. стр. 176. ISBN 978-1-4200-0674-2.
4. Фрикер, Себастьен (апрель 2018 г.). «Что именно представляет собой цикломатическая сложность?». froglogic GmbH . Получено 27 октября 2018 г. Чтобы вычислить графовое представление кода, мы можем просто разобрать его ассемблерный код и создать граф, следуя правилам: ...
5. J. Belzer; A. Kent; AG Holzman; JG Williams (1992). Энциклопедия компьютерных наук и технологий . CRC Press. С. 367–368.
6. Харрисон (октябрь 1984 г.). «Применение меры сложности Маккейба к программам с множественным выходом». Программное обеспечение: практика и опыт . 14 (10): 1004–1007. doi :10.1002/spe.4380141009. S2CID  62422337.
7. Дистель, Рейнхард (2000). Теория графов . Выпускные тексты по математике 173 (2-е изд.). Нью-Йорк: Springer. ISBN 978-0-387-98976-1.
8. Томас МакКейб-младший (2008). «Метрики качества программного обеспечения для выявления рисков». Архивировано из оригинала 29.03.2022.
9. Артур Х. Уотсон; Томас Дж. МакКейб (1996). "Структурированное тестирование: Методология тестирования с использованием метрики цикломатической сложности" (PDF) . Специальная публикация NIST 500-235.
10. Пол С. Йоргенсен (2002). Тестирование программного обеспечения: подход мастера, второе издание (2-е изд.). CRC Press. стр. 150–153. ISBN 978-0-8493-0809-3.
11. Norman E Fenton; Martin Neil (1999). "Критика моделей прогнозирования дефектов программного обеспечения" (PDF) . IEEE Transactions on Software Engineering . 25 (3): 675–689. CiteSeerX 10.1.1.548.2998 . doi :10.1109/32.815326. 
12. Шредер, Марк (1999). «Практическое руководство по объектно-ориентированным метрикам». IT Professional . 1 (6): 30–36. doi :10.1109/6294.806902. S2CID  14945518.
13. Лес Хаттон (2008). «Роль эмпиризма в повышении надежности будущего программного обеспечения». версия 1.1.
14. Кан (2003). Метрики и модели в проектировании качества программного обеспечения . Addison-Wesley. стр. 316–317. ISBN 978-0-201-72915-3.
15. GS Cherf (1992). «Исследование характеристик обслуживания и поддержки коммерческого программного обеспечения». Журнал качества программного обеспечения . 1 (3): 147–158. doi :10.1007/bf01720922. ISSN  1573-1367. S2CID  37274091.
16. ISO 26262-3:2011(ru) Транспорт дорожный — Функциональная безопасность — Часть 3: Фаза концепции. Международная организация по стандартизации.

Внешние ссылки

• Генерация метрик цикломатической сложности с помощью Polyspace
• Роль эмпиризма в повышении надежности будущего программного обеспечения
• Цикломатическая сложность Маккейба и почему мы ее не используем