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

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

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

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

Описание [ править ]

Определение [ править ]

Существует несколько способов определения цикломатической сложности раздела исходного кода . Одним из распространенных способов является количество линейно независимых путей внутри него. Набор $S$ путей линейно независимо, если множество ребер любого пути $P$ в $S$ не является объединением множеств ребер путей в некотором подмножестве $S/P$ . Если бы исходный код не содержал операторов потока управления (условий или точек принятия решения), сложность была бы равна 1, поскольку в коде был бы только один путь. Если бы в коде был один оператор IF с одним условием, в коде было бы два пути: один, где оператор IF имеет значение ИСТИНА, и другой, где он имеет значение ЛОЖЬ. Здесь сложность будет равна 2. Два вложенных IF с одним условием или один IF с двумя условиями дадут сложность 3.

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

M=E-N+2P,

где

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

Альтернативная формулировка этого, как первоначально предлагалось, заключается в использовании графа, в котором каждая точка выхода соединена обратно с точкой входа. В этом случае граф сильно связен . Здесь цикломатическая сложность программы равна циклому числу ее графа (также известному как первое число Бетти ), которое определяется как ^[2]

M=E-N+P.

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

Для отдельной программы (или подпрограммы, или метода) $P$ всегда равно 1; более простая формула для одной подпрограммы: ^[3]

M=E-N+2.

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

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

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

\pi -s+2,

где

\pi

— количество точек принятия решения в программе, а

s

— количество точек выхода. ^[5]^[6]

Алгебраическая топология [ править ]

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

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

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

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

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

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

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

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

M=b_{1}({\tilde {G}})=\operatorname {rank} H_{1}({\tilde {G}}).

Его также можно вычислить с помощью гомотопии . Если (связный) граф потока управления рассматривается как одномерный комплекс CW, называемый $X$ , фундаментальная группа $X$ будет $\pi _{1}(X)\cong \mathbb {Z} ^{*n}$ . Стоимость $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$ .

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

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

if (c1())
    f1();
else
    f2();

if (c2())
    f3();
else
    f4();

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

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

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

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

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

c1() возвращает истину и c2() возвращает истину
c1() возвращает ложь и c2() возвращает ложь

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

c1() возвращает истину и c2() возвращает ложь
c1() возвращает ложь и c2() возвращает истину

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

Соотношение с количеством дефектов [ править ]

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

См. также [ править ]

Примечания [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

[1] Эй Джей Соби. «Тестирование базового пути» .

[mccabe76-2] Перейти обратно: ^а ^б ^с ^д ^и Маккейб (декабрь 1976 г.). «Мера сложности». Транзакции IEEE по разработке программного обеспечения . СЭ-2 (4): 308–320. дои : 10.1109/tse.1976.233837 . S2CID 9116234 .

[Laplante2007-3] Филип А. Лаплант (25 апреля 2007 г.). Что должен знать каждый инженер о программной инженерии . ЦРК Пресс. п. 176. ИСБН 978-1-4200-0674-2 .

[4] Фрикер, Себастьян (апрель 2018 г.). «Что такое цикломатическая сложность?» . Фроглогик ГмбХ . Проверено 27 октября 2018 г. Чтобы вычислить графовое представление кода, мы можем просто дизассемблировать его ассемблерный код и создать граф, следуя правилам: ...

[ecst-5] Перейти обратно: ^а ^б Дж. Белзер; А. Кент; А.Г. Хольцман; Дж. Г. Уильямс (1992). Энциклопедия компьютерных наук и технологий . ЦРК Пресс. стр. 367–368.

[harrison-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 г.

[nist-9] Перейти обратно: ^а ^б ^с Артур Х. Уотсон; Томас Дж. Маккейб (1996). «Структурированное тестирование: методология тестирования с использованием метрики цикломатической сложности» (PDF) . Специальная публикация NIST 500-235.

[10] Пол К. Йоргенсен (2002). Тестирование программного обеспечения: подход мастера, второе издание (2-е изд.). ЦРК Пресс. стр. 150–153. ISBN 978-0-8493-0809-3 .

[fenton-12] Перейти обратно: ^а ^б Норман Э. Фентон; Мартин Нил (1999). «Критика моделей прогнозирования дефектов программного обеспечения» (PDF) . Транзакции IEEE по разработке программного обеспечения . 25 (3): 675–689. CiteSeerX 10.1.1.548.2998 . дои : 10.1109/32.815326 .

[schroeder99-13] Шредер, Марк (1999). «Практическое руководство по объектно-ориентированным метрикам». ИТ-специалист . 1 (6): 30–36. дои : 10.1109/6294.806902 . S2CID 14945518 .

[taic-14] Лес Хаттон (2008). «Роль эмпиризма в повышении надежности будущего программного обеспечения» . версия 1.1.

[kan-15] Кан (2003). Метрики и модели в инженерии качества программного обеспечения . Аддисон-Уэсли. стр. 316–317. ISBN 978-0-201-72915-3 .

[cherf-16] Г.С. Черф (1992). «Исследование характеристик сопровождения и поддержки коммерческого программного обеспечения». Журнал качества программного обеспечения . 1 (3): 147–158. дои : 10.1007/bf01720922 . ISSN 1573-1367 . S2CID 37274091 .

[ISO26262Part3-17] ISO 26262-3:2011(ru) Транспорт дорожный. Функциональная безопасность. Часть 3. Фаза концепции . Международная организация по стандартизации.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[а]

[11]

[12]

[13]

[14]

[15]

[16]