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

Measure of the structural complexity of a software program

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

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

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

Описание

Определение

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

Цикломатическая сложность раздела исходного кода — это количество линейно независимых путей внутри него; набор путей является линейно зависимым, если существует подмножество одного (или более) путей, в котором симметричная разность их наборов ребер пуста. Если бы исходный код не содержал операторов потока управления (условий или точек принятия решения), сложность была бы равна 1, поскольку в коде был бы только один путь. Если бы в коде был один оператор IF с одним условием, в коде было бы два пути: один, где оператор IF имеет значение TRUE, и другой, где он имеет значение FALSE, поэтому сложность была бы равна 2. Два вложенных IF с одним условием, или одно ЕСЛИ с двумя условиями даст сложность 3.

Цикломатическая сложность структурированной программы ^[а] определяется относительно графа потока управления программы, ориентированного графа, содержащего базовые блоки программы, с ребром между двумя базовыми блоками, если управление может передаваться от первого к второй. Тогда сложность 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 будет равно количеству рассматриваемых программ; каждая подпрограмма будет отображаться как несвязное подмножество графа.

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

Цикломатическая сложность может быть расширена до программы с несколькими точками выхода; в данном случае оно равно

$${\displaystyle \pi -s+2,}$$

s^{[5] [6]} ${\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()должен также вызывать другую. ^[b] Если предположить, что результаты 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]

Искусственный интеллект

Цикломатическая сложность также может использоваться для оценки семантической сложности программ искусственного интеллекта. ^[17]

Ультраметрическая топология

Цикломатическая сложность оказалась полезной в географическом и ландшафтно-экологическом анализе после того, как было показано, что ее можно реализовать на графиках ультраметрических расстояний. ^[18]

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

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

Примечания

1. Здесь «структурированный» означает «с одним выходом ( оператором возврата ) для каждой функции».
2. Это довольно распространенный тип состояния; рассмотрите возможность f1выделения некоторого ресурса, который f3освобождается.

Рекомендации

1. Эй Джей Соби. «Тестирование базового пути».
2. McCabe (декабрь 1976 г.). «Мера сложности». Транзакции IEEE по разработке программного обеспечения . СЭ-2 (4): 308–320. дои : 10.1109/tse.1976.233837. S2CID  9116234.
3. Филип А. Лапланте (25 апреля 2007 г.). Что должен знать каждый инженер о программной инженерии . ЦРК Пресс. п. 176. ИСБН 978-1-4200-0674-2.
4. Фрикер, Себастьян (апрель 2018 г.). «Что такое цикломатическая сложность?». Фроглогик ГмбХ . Проверено 27 октября 2018 г. Чтобы вычислить графовое представление кода, мы можем просто дизассемблировать его ассемблерный код и создать граф, следуя правилам: ...
5. Дж. Белзер; А. Кент; А.Г. Хольцман; Дж. Г. Уильямс (1992). Энциклопедия компьютерных наук и технологий . ЦРК Пресс. стр. 367–368.
6. Харрисон (октябрь 1984 г.). «Применение меры сложности Маккейба к программам с множественным выходом». Программное обеспечение: практика и опыт . 14 (10): 1004–1007. дои : 10.1002/сп.4380141009. S2CID  62422337.
7. Дистель, Рейнхард (2000). Теория графов . Аспирантура по математике 173 (2-е изд.). Нью-Йорк: Спрингер. ISBN 978-0-387-98976-1.
8. Томас Маккейб младший (2008). «Метрики качества программного обеспечения для выявления рисков». Архивировано из оригинала 29 марта 2022 г.
9. Артур Х. Уотсон; Томас Дж. Маккейб (1996). «Структурированное тестирование: методология тестирования с использованием метрики цикломатической сложности» (PDF) . Специальная публикация NIST 500-235.
10. Пол К. Йоргенсен (2002). Тестирование программного обеспечения: подход мастера, второе издание (2-е изд.). ЦРК Пресс. стр. 150–153. ISBN 978-0-8493-0809-3.
11. Норман Э. Фентон; Мартин Нил (1999). «Критика моделей прогнозирования дефектов программного обеспечения» (PDF) . Транзакции IEEE по разработке программного обеспечения . 25 (3): 675–689. CiteSeerX 10.1.1.548.2998 . дои : 10.1109/32.815326. 
12. Шредер, Марк (1999). «Практическое руководство по объектно-ориентированным метрикам». ИТ-специалист . 1 (6): 30–36. дои : 10.1109/6294.806902. S2CID  14945518.
13. Лес Хаттон (2008). «Роль эмпиризма в повышении надежности будущего программного обеспечения». версия 1.1.
14. Кан (2003). Метрики и модели в инженерии качества программного обеспечения . Аддисон-Уэсли. стр. 316–317. ISBN 978-0-201-72915-3.
15. Г. С. Черф (1992). «Исследование характеристик сопровождения и поддержки коммерческого программного обеспечения». Журнал качества программного обеспечения . 1 (3): 147–158. дои : 10.1007/bf01720922. ISSN  1573-1367. S2CID  37274091.
16. ISO 26262-3:2011(ru) Транспорт дорожный. Функциональная безопасность. Часть 3. Фаза концепции. Международная организация по стандартизации.
17. Пападимитриу, Фивос (2012). «Искусственный интеллект в моделировании сложности трансформаций средиземноморских ландшафтов». Компьютеры и электроника в сельском хозяйстве . 81 : 87–96. doi : 10.1016/j.compag.2011.11.009.
18. Пападимитриу, Фивос (2013). «Математическое моделирование землепользования и сложности ландшафта с ультраметрической топологией». Журнал науки о землепользовании . 8 (2): 234–254. дои : 10.1080/1747423X.2011.637136 . S2CID  121927387.

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

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