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

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

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

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

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

Эта статья может содержать слишком много повторений или излишней лексики . Пожалуйста, помогите улучшить его , объединив похожий текст или удалив повторяющиеся утверждения. ( Июль 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

Цикломатическая сложность раздела исходного кода - это максимальное количество линейно независимых путей внутри него - где «линейно независимый» означает, что каждый путь имеет по крайней мере одно ребро, которое не находится ни в одном из других путей. Например, если исходный код не содержал операторов потока управления (условных выражений или точек принятия решения), сложность была бы 1, поскольку в коде был бы только один путь. Если бы в коде был один оператор IF с одним условием, в коде было бы два пути: один, где оператор IF принимает значение ИСТИНА, а другой, где он оценивается как ЛОЖЬ, поэтому сложность будет равна 2. Два вложенных оператора ЕСЛИ с одним условием , или один IF с двумя условиями, даст сложность 3.

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

M = E - N + 2 P ,

где

E = количество ребер графа.

N = количество узлов графа.

P = количество подключенных компонентов .

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

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

М = Е - Н + Р .

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

Для отдельной программы (или подпрограммы, или метода) P всегда равно 1. Таким образом, более простая формула для одной подпрограммы:

M = E - N + 2. ^[3]

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

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

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

π - s + 2,

где π - количество точек принятия решения в программе, а s - количество точек выхода. ^[5]^[6]

Объяснение в терминах алгебраической топологии [ править ]

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

Множество всех четных подграфов графа замкнуто относительно симметричной разности и, таким образом, может рассматриваться как векторное пространство над 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}}).}

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

Это соответствует описанию цикломатической сложности как «количество петель плюс количество компонентов».

Приложения [ править ]

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

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

Измерение "структурированности" программы [ править ]

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

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

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

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

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

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

Все три из вышеперечисленных чисел могут быть равны: покрытие ветвления, цикломатическая сложность, количество путей. ${\ 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, заключается в использовании цикломатической сложности модуля для определения количества тестов белого ящика , необходимых для получения достаточного покрытия модуля. Почти во всех случаях, согласно такой методологии, модуль должен иметь как минимум столько тестов, сколько его цикломатическая сложность; в большинстве случаев этого количества тестов достаточно для проверки всех соответствующих путей выполнения функции. ^[8]

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

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

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

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

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

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

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

Искусственный интеллект [ править ]

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

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

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

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

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

Заметки [ править ]

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

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

^ AJ Sobey. «Тестирование базового пути» .
^ a b c d e МакКейб (декабрь 1976 г.). «Мера сложности» . IEEE Transactions по разработке программного обеспечения (4): 308–320. DOI : 10.1109 / tse.1976.233837 .
↑ Филип А. Лапланте (25 апреля 2007 г.). Что должен знать каждый инженер о программной инженерии . CRC Press. п. 176. ISBN. 978-1-4200-0674-2.
^ Fricker, Себастьен (апрель 2018). "Что такое цикломатическая сложность?" . froglogic GmbH . Проверено 27 октября 2018 года . Чтобы вычислить графическое представление кода, мы можем просто дизассемблировать его ассемблерный код и создать граф, следуя правилам: ...
^ a b Белзер, Кент, Хольцман и Уильямс (1992). Энциклопедия компьютерных наук и технологий . CRC Press. С. 367–368.CS1 maint: несколько имен: список авторов ( ссылка )
^ Харрисон (октябрь 1984). «Применение меры сложности Маккабе к программам с несколькими выходами». Программное обеспечение: практика и опыт . 14 (10): 1004–1007. DOI : 10.1002 / spe.4380141009 .
^ Дистель, Рейнхард (2000). Теория графов . Тексты для выпускников по математике 173 (2-е изд.). Нью-Йорк: Спрингер. ISBN 978-0-387-98976-1.
^ a b c Артур Х. Уотсон; Томас Дж. Маккейб (1996). «Структурированное тестирование: методология тестирования с использованием метрики цикломатической сложности» (PDF) . Специальная публикация NIST 500-235.
Перейти ↑ Paul C. Jorgensen (2002). Тестирование программного обеспечения: подход мастера, второе издание (2-е изд.). CRC Press. С. 150–153. ISBN 978-0-8493-0809-3.
^ а б Норман Э. Фентон; Мартин Нил (1999). «Критика моделей прогнозирования дефектов программного обеспечения» (PDF) . IEEE Transactions по разработке программного обеспечения . 25 (3): 675–689. CiteSeerX 10.1.1.548.2998 . DOI : 10.1109 / 32.815326 .
^ Шредер, Марк (1999). «Практическое руководство по объектно-ориентированным метрикам». ИТ-специалист . 1 (6): 30–36. DOI : 10.1109 / 6294.806902 . S2CID 14945518 .
^ Les Хаттон (2008). «Роль эмпиризма в повышении надежности программного обеспечения будущего» . версия 1.1.
^ Кан (2003). Метрики и модели в инженерии качества программного обеспечения . Эддисон-Уэсли. С. 316–317. ISBN 978-0-201-72915-3.
^ GS Черф (1992). «Исследование характеристик обслуживания и поддержки коммерческого программного обеспечения». Журнал качества программного обеспечения . 1 (3): 147–158. DOI : 10.1007 / bf01720922 . ISSN 1573-1367 .
^ ISO 26262-3: 2011 (ru) Транспорт дорожный - Функциональная безопасность - Часть 3: Фаза концепции . Международная организация по стандартизации.
^ Papadimitriou, Fivos (2012). «Искусственный интеллект в моделировании сложности трансформации средиземноморского ландшафта». Компьютеры и электроника в сельском хозяйстве . 81 : 87–96. DOI : 10.1016 / j.compag.2011.11.009 .
^ Papadimitriou, Fivos (2013). «Математическое моделирование землепользования и ландшафтной сложности с ультраметрической топологией». Журнал науки о землепользовании . 8 (2): 234–254. DOI : 10.1080 / 1747423X.2011.637136 .

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

Создание показателей цикломатической сложности с помощью Polyspace
Роль эмпиризма в повышении надежности программного обеспечения будущего
Небольшой анализатор исходного кода C / C ++, использующий метрику циклометрической сложности (только для Windows, без исходного кода)
Цикломатическая сложность Маккейба и почему мы ее не используем

[2] Здесь «структурированный» означает, в частности, «с одним выходом ( оператором возврата ) для каждой функции».

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

[1] AJ Sobey. «Тестирование базового пути» .

[mccabe76-3] МакКейб (декабрь 1976 г.). «Мера сложности» . IEEE Transactions по разработке программного обеспечения (4): 308–320. DOI : 10.1109 / tse.1976.233837 .

[Laplante2007-4] Филип А. Лапланте (25 апреля 2007 г.). Что должен знать каждый инженер о программной инженерии . CRC Press. п. 176. ISBN. 978-1-4200-0674-2.

[5] Fricker, Себастьен (апрель 2018). "Что такое цикломатическая сложность?" . froglogic GmbH . Проверено 27 октября 2018 года . Чтобы вычислить графическое представление кода, мы можем просто дизассемблировать его ассемблерный код и создать граф, следуя правилам: ...

[ecst-6] Белзер, Кент, Хольцман и Уильямс (1992). Энциклопедия компьютерных наук и технологий . CRC Press. С. 367–368.CS1 maint: несколько имен: список авторов ( ссылка )

[harrison-7] Харрисон (октябрь 1984). «Применение меры сложности Маккабе к программам с несколькими выходами». Программное обеспечение: практика и опыт . 14 (10): 1004–1007. DOI : 10.1002 / spe.4380141009 .

[8] Дистель, Рейнхард (2000). Теория графов . Тексты для выпускников по математике 173 (2-е изд.). Нью-Йорк: Спрингер. ISBN 978-0-387-98976-1.

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

[10] Перейти ↑ Paul C. Jorgensen (2002). Тестирование программного обеспечения: подход мастера, второе издание (2-е изд.). CRC Press. С. 150–153. ISBN 978-0-8493-0809-3.

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

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

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

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

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

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

[18] Papadimitriou, Fivos (2012). «Искусственный интеллект в моделировании сложности трансформации средиземноморского ландшафта». Компьютеры и электроника в сельском хозяйстве . 81 : 87–96. DOI : 10.1016 / j.compag.2011.11.009 .

[19] Papadimitriou, Fivos (2013). «Математическое моделирование землепользования и ландшафтной сложности с ультраметрической топологией». Журнал науки о землепользовании . 8 (2): 234–254. DOI : 10.1080 / 1747423X.2011.637136 .

[1]