Качество и надежность программного обеспечения

Качество и надежность программного обеспечения

(для программы UPROG подготовки магистров для фирмы «Моторола»)

Авторы к.т.н., доцент В.А.Кирьянчиков

к.т.н., доцент Э.А.Опалева

Санкт-Петербург

Содержание

Лекция 1. Введение. Основные стандарты и термины по качеству программного обеспечения. Метрики и критерии качества программных продуктов. Составляющие качества программных продуктов.................................................................. 3

Лекция 2. Классификация видов сложности программных продуктов. Метрические характеристики программ по М.Холстеду................................................................................................................................................................................................................... 8

Лекция 3. Уровень программ. Интеллектуальное содержание программы.................................................................... 14

Лекция 4. Работа в программировании. Уровни языков программирования. Метрика числа ошибок в программе. 17

Лекция 5. Метрики структурной сложности программ.......................................................................................................... 22

Лекция 6. Методы и средства измерения характеристик программ. Аппаратные измерительные мониторы..... 29

Лекция 7. Программные измерительные мониторы................................................................................................................ 36

Лекция 8. Понятие корректности программ.............................................................................................................................. 42

Лекция 9. Аналитическая проверка корректности программ. Верификация программ.............................................. 45

Лекция 10. Тестирование программных продуктов.............................................................................................................. 53

Лекция 11. Виды, критерии и методы тестирования. Методы структурного тестирования программ................... 58

Лекция 12. Методы функционального тестирование программных продуктов............................................................. 62

Лекция 13. Основные показатели надежности программного обеспечения (ПО). Математические модели оценки надежности ПО................................................................................................................................................................................................................. 68

Лекция 14. Модели, основанные на методе "посева" и разметки ошибок, и модели на основе учета структуры входных данных................................................................................................................................................................................................................ 76

Лекция 15. Методы повышения надежности программ и оценка эффективности их применения......................... 80

ЛИТЕРАТУРА..................................................................................................................................................................................... 86

Лекция 1. Введение. Основные стандарты и термины по качеству программного обеспечения. Метрики и критерии качества программных продуктов. Составляющие качества программных продуктов.

1.1. Цели и задачи курса, его связь с другими дисциплинами учебного плана.

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

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

В результате от подхода "лишь бы программа работала" к настоящему времени выполнен переход к подходу "с какими характеристиками качества создается и функционирует программа и при каких затратах достигаются результаты".

Дисциплина “Software quality, testing and verification” или в русскоязычном варианте «Качество и надежность программного обеспечения» как раз и предназначена для обучения будущих инженеров–программистов методам и средствам оценки характеристик качества и надежности ПП как при выборе готовых программных средств, так и при их разработке. Дисциплина базируется на знаниях полученных при изучении математики, основ программирования, формальных моделей программ, архитектур программных систем и технологий разработки ПП.

ГОСТы . Основные понятия и ключевые слова по качеству и надежности ПП.

Основными ГОСТами, регламентирующими в нашей стране использование термино-логии по качеству ПП являются:

1) ГОСТ 28806—90 «КАЧЕСТВО ПРОГРАММНЫХ СРЕДСТВ. Термины и определения (Software quality. Terms and definitions)»;

2) ГОСТ 28195-89 «ОЦЕНКА КАЧЕСТВА ПРОГРАММНЫХ СРЕДСТВ. Общие положения (Quality control of software systems. General principles)».

В соответствии с ГОСТ 28806—90 основные термины, используемые в настоящем курсе могут быть определены следующим образом.

ОБЩИЕ ТЕРМИНЫ

1. Качество программного средства(software quality)

Совокупность свойств программного средства (ПС), которые обусловливают его пригодность удовлетворять заданные или подразумеваемые потребности в соответствии с его назначением.

Критерии этапа разработки

1. Трудоемкость ( статическая сложность )

2. Корректность ( правильность ) программы

Длина программы

С использованием рассмотренных программных параметров можно получить уравнение для оценки количественного соотношения между длиной программыN и словарем h. Это уравнение на первый взгляд может показаться несколько неожиданным. Однако тщательный анализ доказывает его правомерность, кроме этого его правильность подтверждается экспериментально.

Строка длины N, образуемая символами, входящими в словарь из hсимволов, должна подчиняться ряду ограничений. Требование, согласно которому каждый символ словаря должен появиться по меньшей мере хотя бы один раз, гарантирует выполнение условия

h £ N,

что определяет нижнюю границу для N, выраженную черезh.

Найдем верхнюю границу для N. Разобьем строку длины N на подстроки длины h. Разделенная таким образом программа для ЭВМ оказывается состоящей из N/h операторов длины h каждый. Теперь если мы потребуем, чтобы строка не содержала двух одинаковых подстрок длины h, то появится искомая верхняя граница.

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

Число возможных комбинаций из h элементов взятых по h за раз, хорошо известно из школьного курса математики и составляет

N £ h^h+1

Если учесть, что операторы и операнды, как правило, чередуются, то можно получить другое соотношение

N £ h´h₁^h1´h₂^h2

Верхняя граница для этого неравенства должна включать не только упорядоченное множество из N элементов, представляющих исследуемую программу, но и его всевозможные подмножества. Семейство всевозможных подмножеств из N элементов содержит 2^N элементов. Следовательно, мы можем приравнять число возможных комбинаций из операторов и операндов (равное числу подстрок N/h) числу подмножеств из N элементов и выразить длину реализации алгоритма через его словарь. Из уравнения

2^N = h₁^h1´h₂^h2

получаем

N = log₂ (h₁^h1´h₂^h2)

или

N = log₂ h₁^h1 + log₂ h₂^h2

Это дает нам уравнение оценки длины

h₁ log₂h₁ + h₂ log₂h₂ (2.1)

В этом выражении символ N снабдили Ù для того, чтобы отличать вычисленную (теоретическую) оценку длины от значения N полученного в результате непосредственного измерения (опытной длины). Эта оценка соответствует основным концепциям теории информации, по которым частота использования операторов и операндов в программе пропорциональна двоичному логарифму количества их типов. Выражение (2.1) представляет собой идеализированную аппроксимацию измеренной длины N=N₁+N₂ , справедливую для программ, не содержащих несовершенств (стилистических ошибок) [1]. Экспериментальные исследования ряда авторов на представительной группе программ показали, что для стилистически корректных программ отклонения в оценке их теоретической длины от опытной не превышают (10-15)% .

Объем программы.

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

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

Решение этой проблемы связано с тем, что можно определить абсолютный минимум длины представления самого длинного оператора или имени операнда. Минимальная длина зависит только от числа элементов в словаре h. В общем случае log₂ h есть минимальная длина (в битах) всей программы. Под битом здесь понимается логическая единица информации – символ, оператор, операнд – то, чем оперирует программист при создании программы.

Соответствующая метрическая характеристика размера любой реализации какого-либо алгоритма, называемая объемом V, может быть определена как

V = N log₂ h (2.2)

где N = N₁ + N₂ -длина реализации; а h = h₁ + h₂ - ее словарь.

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

Потенциальный объем V^*

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

Обозначив соответствующие программные параметры возможно кратчайшей или наиболее сжатой формы алгоритма звездочками, из уравнения (2.1) получим, что минимальный (или потенциальный ) объем равен

V^* = (N₁^* + N₂^*) log₂(h₁^* ₊ h₂^*) (2.3)

Но в минимальной форме ни операторы, ни операнды не требуют повторений, поэтому

N₁^* = h₁^* ; N₂^* = h₂^*

что дает нам

V^* = (h₁^* ₊ h₂^*) log₂(h₁^* ₊ h₂^*)

Кроме того, известно минимально возможное число операторов h₁^* для любого алгоритма. Каждый алгоритм должен включать один оператор для имени функции или процедуры и один в качестве символа присваивания или группировки, т.е. минимальное значение h₁^*=2.

Уравнение теперь примет вид:

V^* = (2₊ h₂^*) log₂( 2₊ h₂^*) , (2.4)

где h₂^* должно представлять собой число различных входных и выходных параметров.

Из уравнения (3.4) следует, что потенциальный объем V^* любого алгоритма не должен зависеть от языка, на котором он может быть выражен. Если h₂^* расценивается как число единых по смыслу (неизбыточных) операндов, то V^* оказывается наиболее полезной мерой содержания алгоритма.

Вернемся к примеру программы для алгоритма Евклида и определим его объем для программ на Паскале и СИ.

Паскаль: V =N * log₂ h = 61* log₂ 18 = 254.4 бита.

СИ: V =N * log₂ h = 55* log₂ 18 = 224.8 бита.

Чтобы найти потенциальный объем, нам нужно подсчитать число требуемых входных и выходных параметров. В данном случае это А, В и GCD, так что h₂^*=3. Следовательно, потенциальный объем:

V^* = (2 +h₂^*) log₂( 2 + h₂^*) = (2+3) log₂(2+3) = 11,6 бита

Как уже упоминалось выше, при переводе алгоритма с одного языка на другой его потенциальный объем V^* не меняется, но действительный объем V увеличивается или уменьшается в зависимости от развитости рассматриваемых языков. Однако легко заметить, что не может быть гладкого перехода от выражения на потенциальном языке, для которого V = V^* , к любому менее развитому языку, для которого V > V^*. Такой резкий переход обусловлен тем, что для потенциального языка N^*= h^* , в то время как для всех других языков применяется уравнение длины и N > h.

Лекция 3. Уровень программ. Интеллектуальное содержание программы.

1. Уровень программы.

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

Прежде, чем вводить метрическую характеристику уровня программы, необходимо заметить, что уровень языка и уровень программы являются разными понятиями, хотя и тесно связанными. Функциональное соотношение между ними и способы измерения уровня языка будут рассмотрены позднее. Сейчас ограничимся измерением уровня отдельных программ. Ранее выведенные выражения для определения объема V программы и потенциального объема V^* подсказывают простой метод количественного выражения данного понятия. Если записать уровень L программы, являющейся реализацией какого либо алгоритма, как

; (3.1)

то лишь наиболее сжатое выражение , какое только возможно для алгоритма, будет иметь уровень, равный единице.

Более объемные реализации будут иметь меньшие значения уровня, так что L£1.

Перестроив выражение (3.1) и выделив независящий от реализации член получим

V^* = L´V (3.2)

при увеличении объема уровень программы уменьшается, и наоборот.

Обычно легче написать вызов процедуры, чем саму процедуру. С этой точки зрения проще всего было бы использовать потенциальный язык (L = 1). Однако из самого определения потенциального языка следует, что любая процедура, которая когда либо могла бы понадобиться, в нем уже присутствует. Так как число таких процедур бесконечно, процесс простого ознакомления с их списком тоже бесконечен. Поэтому реализация и использование потенциальных языков невозможны для выполнения реальных заданий.

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

Работа в программировании

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

Вывод уравнения работы

1. Как и ранее, допустим, что любая реализация какого­­-либо алгоритма заключается в N­-кратном выборе из словаря, состоящего из h элементов.

2. Предположим далее, что каждый выбор из словаря h неслучаен. Исследования методов сортировки показали, что, за исключением хеширования, самым быстрым способом поиска в упорядоченном списке является двоичный поиск, при котором список многократно делится пополам до тех пор, пока не будет найден нужный элемент. Полученное в результате число сравнений равно двоичному логарифму числа элементов в списке. Следовательно, эффективный процесс, эквивалентный двоичному поиску , требует log₂h сравнений для нахождения элемента.

3. На основании шагов 1 и 2 можно заключить, что программа порождается выполнением N ´ log₂h мысленных сравнений.

4. Поскольку объем программы V определяется как

V = N log₂h, (4.1)

из шага 3 следует, что он равен числу мысленных сравнений, затрачиваемых на порождение программы.

5. Каждое мысленное сравнение содержит ряд элементарных мысленных различений, число которых является мерой сложности задачи. Из предыдущих результатов вытекает, что именно уровень программы L является величиной, обратной ее сложности.

6. Так как объем V равен числу мысленных сравнений, а величина, обратная уровню программы, т.е. 1/L, есть среднее число элементарных мысленных различений, входящих в каждое мысленное сравнение, общее число элементарных мысленных различений Е, требуемых для порождения программы, должно задаваться выражением

Е = (4.2)

Можно выявить более глубокий смысл уравнения работы, если вспомнить уравнение (3.1)

L =

и подставить его в уравнение (4.2)

E = (4.3)

Уравнение (4.3) показывает, что мысленная работа по реализации любого алгоритма с данным потенциальным объемом в каждом языке пропорциональна квадрату объема программы. Как будет детально показано далее, из уравнения (4.3) следует, что, так как «квадрат суммы больше суммы двух квадратов», правильное разбиение на модули может уменьшить работу по программированию реализаций, разбитых на отдельные части. Теперь перейдем от подсчета элементарных мысленных различений к измерению времени.

Уровень языка.

Материал, изложенный в лекции 3, выявил полезное соотношение между уровнем программы L и ее объемом V. Для любого алгоритма, который переводится с одного языка на другой, с увеличением объема уровень уменьшается в той же пропорции. В результате произведение L на V равняется потенциальному объему V^* данного алгоритма. С другой стороны, если язык реализации остается одним и тем же, а разрешено менять сам алгоритм, имеется другое, но похожее соотношение. В этом случае с увеличением потенциального объема V^* уровень программы L уменьшится в том же отношении. Следовательно, произведение L на V^* остается неизменным для любого языка. Это произведение, называемое уровнем языка, обозначается через l и записывается в виде:

l = L´V^* (4.7)

Значение уровня языка.

В течение последних десятилетий значительная доля усилий специалистов в области языков программирования была направлена на разработку и реализацию новых языков и часто при этом выполнялось усовершенствование ранее существовавших языков. Но из-за отсутствия количественного измерения вывод о реальном улучшении языка был весьма субъективным. Без принятия гипотезы, соотносящей конкретный язык с мысленной работой по его использованию, нельзя с уверенностью сказать, положительно или отрицательно его введение. Объединяя уравнение (4.7) с уравнением работы, получаем, что число элементарных мысленных различений, требуемых для написания некоторой программы, должно подчиняться ²закону обратных квадратов² относительно уровня языка, или

Е = V^*3/l² (4.8)

Из соотношений Е = V²/V^* и V = V^*/L следует, что Е = V^*/L², откуда при помощи равенства L = l/V^* выводим (4.8). Для небольшой выборки программ, написанных на двух языках, можно определить средние значения l и с их помощью найти сравнительную трудоемкость. Так выигрыш во времени программирования при переходе от языка низкого уровня l₁ к языку высокого уровня l₂ определяется соотношением

ΔT/T = (T₁ - T₂) / T₁ = 1 - T₂ / T₁ = 1 - (l₁)² / (l₂)² (4.9)

Тогда по данным табл.6 при переходе от Ассемблера к Фортрану выигрыш во времени составит 40% , от Ассемблера к ПЛ-1 - 67%.

Важность понятия уровня языка подтверждается также из уравнения (4.8) следующими обстоятельствами. Поскольку потенциальный объем V^* и среднее значение l должны быть известны или вычислимы сразу после определения программистского проекта и выбора языка, это дает рациональную основу для планирования времени программирования.

С другой стороны, подставляя в (4.7) выражение для L из (3.2), получим

l = (V^*)² / V (4.10)

Из этого выражения видно, что для постоянства l увеличение объема программы должно квадратично зависеть от увеличения количества информации по внешним связям. Поэтому алгоритмически сложные программы вычисления малого числа переменных будут давать значительно более низкое значение l, чем программы вычисления большого числа

переменных по элементарным выражениям. Поэтому применение метрики l для сравнения языков программирования следует делать только для конкретной предметной области и близких типов задач.

M1: 1 – 2 – 14

M2: 1 – 3 – 4 – 6 – 8 – 6 – 8 – 14

M3: 1 – 3 – 5 – 7 – 9 – 10 – 11 – 12 – 13 – 14

M4: 1 – 3 – 4 – 5 – 7 – 9 – 10 – 9 – 10 – 11 – 7 – 9 – 10 – 11 – 12 – 14

Рис.3

Структурная сложность программы по первому критерию вычисляется следующим образом:

m

S = S p_{i ,}

i =1

гдеp_i –количество вершин ветвления в i-том маршруте без учета последней вершины

m1: 1 - 2 - 14 = 1

m2: 1 - 3 - 4 - 6 -8 - 6 - 8- 14 = 5

m3: 1 - 3 - 5 - 7 - 9 - 10 - 11 - 12 - 13 - 14 = 5

m4: 1 - 3 - 4 - 5 - 7 -9- 10 - 9 - 10 - 11 - 7 - 9 - 10 - 11 - 12 - 14 = 9

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

Недостаток первого критерия: не учитывается комбинаторика сочетания условий на разных участках маршрутов (например, при сочетаниях ветвлений в вершинах 3 и 12).

Критерий 2. Основан на анализе базовых маршрутов в программе, формируемых и оцениваемых на основе цикломатического числа графа потока управления программы (см. работы Т.МcCabe и В.В.Липаева).

Цикломатическое число Z исходного графа программы определяется формулой

Z = Y - N +2*W,

где Y – общее число дуг в графе;

N – общее число вершин в графе;

W – число связных компонент графа.

Число связных компонент графа Wравно количеству дуг, необходимых для превращения исходного графа в максимально связный граф.

Максимально связным графом называется граф, у которого любая вершина доступна из любой другой вершины.

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

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

Z = Y - N + 2´P = 20 - 14 + 2´1 = 8

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

При использовании второго критерия количество проверяемых маршрутовравно цикломатическому числу.

M1: 6 – 8

m2: 9 – 10Линейно-независимые циклические маршруты

m3: 7 – 9 – 10 – 11

m4: 1 – 2 – 14Линейно-

M5: 1 – 3 – 4 – 6 – 8 – 14 независимые

m6: 1 – 3 – 5 – 7 – 9 – 10 – 11 – 12 – 14ациклические

m7: 1 – 3 – 4 – 5 – 7 – 9 – 10 – 11 – 12 – 13 – 14маршруты

M8: 1 – 3 – 4 – 5 – 7 – 9 – 10 – 11 – 12 – 14

Определение структурной сложности по второму критерию:

m1: 6 - 8= 1

m2: 9 - 10= 1

m3: 7 - 9 - 10 – 11 = 2

m4: 1 - 2 – 14 = 1

m5: 1- 3 - 4 - 6 - 8 – 14 = 4

m6: 1 - 3 - 5 - 7 - 9 - 10 - 11 - 12 – 14 = 5

m7: 1 - 3 - 4 - 5 - 7 - 9 - 10 - 11 - 12 – 14 = 6

m8: 1 - 3 - 4 - 5 - 7 - 9 - 10 - 11 - 12 - 13 – 14 = 6

Для правильно структурированных программ (программ, которые не имеют циклов с несколькими выходами, не имеют переходов внутрь циклов или условных операторов и не имеют принудительных выходов из внутренней части циклов или условных операторов) цикломатическое число Z можно определить путем подсчета числа вершинn_в, в которых происходит ветвление. Тогда

Z = n_в +1

Для рассматриваемого примера Z = 7 + 1 = 8(ветвления имеют место ввершинах графа 1, 3, 4, 8, 10, 11, 12).

Исследования графов реальных программных модулей с достаточно большим фиксированным числом вершин показали, что:

· Суммарная сложность тестов почти не зависит от детальной структуры графа и в основном определяется числом предикатов – ветвлений графа;

· При неизменном числе вершин в широких графах имеется большее количество маршрутов, чем в узких графах, но маршруты в среднем короткие. В узких графах число маршрутов сокращается по сравнению с широкими, но маршруты становятся длиннее. В результате величина S₂ при изменении структуры графов изменяется меньше, чем цикломатическое число и сильнее коррелирована с числом вершин.

В.В. Липаев показал, что для Z £ 10 модули корректно проверяемы и число ошибок в таких модулях будет минимальным. Приемлемыми значениями Z считаются 10 £ Z £30. При Z > 30 устранить ошибки в процессе тестирования практически невозможно.

Для автоматического анализа графов по второму критерию с помощью ЭВМ используются матрицы смежности и достижимости графов.

Матрица смежности – это квадратная матрица, в которой 1 располагается в позиции (i, j),если в графе имеется дуга (i, j).

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

Таблица 7

Матрицей достижимости называется квадратная матрица, в которой 1 располага-ется в позиции, соответствующей дуге (i, j). Для рассматриваемого графа программы матри-ца достижимости имеет вид, показанный в табл.8.

Таблица 8

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

С помощью матрицы достижимости можно сравнительно просто выделить циклы, отмечая диагональные элементы, равные 1, и идентичныестрок.

Для рассматриваемого примера одинаковыми являются строки 6и 8, которые имеют 1на диагонали, следовательно, вершины 6и 8образуют цикл. Аналогично можно выделить еще два маршрута с циклами, образованными вершинами 9и10 и 7, 9, 10и11 соответственно.

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

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

Если из некоторого ациклического маршрута исходного графа достижимы несколько элементарных циклов, то при тестировании должны исполняться все достижимые циклы.

Для рассматриваемого примера по данному критерию необходимо исполнить 6 ациклических маршрутов и 5 маршрутов, из которых достижимы элементарные циклы.

M1: 1 – 2 – 14

m2: 1– 3– 4– 6 – 8 – 14

M3: 1 – 3 – 5 – 7 – 9 – 10 – 11 – 12 – 14

M4: 1 – 3 – 4 – 5 – 7 – 9 – 10 – 11 – 12 – 14

M5: 1 – 3 – 5 – 7 – 9 – 10 – 11 – 12 – 13 – 14

m6: 1 – 3– 4 – 5 – 7 – 9 – 10 – 11 – 12 – 13 – 14

m7: 1 – 3– 4– 6 – 8– 6 – 8