13.4. Процессы тестирования структуры программных компонентов

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

• верификацией  последовательным прослеживанием сверху вниз реализации требований к системе и ПС программными компонентами нижних уровней;

• определением полноты покрытия тестами их структуры и проверками выполнения исходных требований к ПС и его компонентам.

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

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

На практике при отсутствии упорядоченного анализа потоков управления, некоторые маршруты в программе оказываются пропущенными при тестировании (до 50%), поэтому первая задача, которая должна решаться при тестировании структуры программ,  это получение информации о полной совокупности реальных маршрутов исполнения в каждой программе и ее структурной сложности. Такое представление покрытия программы позволяет упорядоченно контролировать достигнутую проверку маршрутов и, в некоторой степени, предохраняет от случайного пропуска отдельных не тестировавшихся маршрутов и их элементов.

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

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

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

X₁  покрытие графа программы минимальным количеством маршрутов, охватывающих каждую дугу графа хотя бы один раз;

Х₂  выделение всех линейно независимых маршрутов, отличающихся хотя бы одной дугой в маршруте от остальных;

Х₃  выделение маршрутов при всех возможных комбинациях дуг, входящих в маршруты.

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

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

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

• стратегия 1 учитывает число строк текста программы в выделенных маршрутах или расчетную длительность их исполнения при функционировании программы;

• стратегия 2 анализирует число альтернатив или условных переходов, определяющих образование каждого маршрута;

• стратегия 3 базируется на использовании вероятности исполнения маршрутов при реальном функционировании программы.

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

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

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

Эффективность тестирования определяется полнотой проверки программного модуля или вероятностью наличия не выявленных ошибок в зависимости от затрат ресурсов: на создание тестов, исполнение программ и анализ результатов тестирования. Затраты в значительной степени зависят от суммарной сложности формирования тестов, проверяющих маршруты исполнения программы. На каждой дуге графа программы между условными переходами производятся вычисления и преобразования переменных, объем которых может изменяться в широких пределах. Для упрощения анализа и оценивания тестирования структуры программ предположим, что длительность и сложность вычислений на дугах графов программ одинаковы и относительно невелики. Некоторые вершины графа программы могут образовываться в результате схождения дуг без последующего ветвления. Такие вершины не влияют на число маршрутов, и их можно обобщать с ближайшей последующей вершиной, в которой происходит ветвление. При этих предположениях сложность теста, проверяющего каждый i-й маршрут, в первом приближении пропорциональна числу дуг графа программы, входящих в этот маршрут, или числу E _i условий, которые необходимо задать в тесте.

Экспериментально подтверждена адекватность использования структурной сложности программ для оценки трудоемкости тестиро­вания, а также вероятности наличия не выявленных ошибок и затрат на раз­работку программных модулей в целом. Сложность тестирования ПМ можно оценивать по числу маршрутов M _X , не­обходимых для их проверки, или более полно по суммарному числу условий Е _X , которое необходимо задать в тестах для прохождения всех маршрутов программы, выделенных по Х-му критерию:

(13.1)

где Е _i  число условий-предикатов, определяющих i-й маршрут.

Маршруты исполнения программного модуля можно разделить на два вида:

• маршруты исполнения преимущественно вы­числительной части программы и преобразования непрерывных переменных;

• маршруты принятия логических решений и преобразова­ния логических переменных.

Маршруты первого вида обычно логичес­ки проще и короче, чем второго, и предназначены для преобразова­ния величин, являющихся квантованными результатами измерения не­которых непрерывных физических характеристик (непрерывные переменные). Значения таких переменных связаны условиями гладкости, т.е. условиями малых изменений производных этих переменных по времени или по другим параметрам. При оценке сложности вычислительных маршрутов программ не­обходим учет числа операндов, участвующих в вычислениях. Кроме того, исходные и результирующие данные при тестировании должны принимать несколько значений. Во всем диапазоне исходных пере­менных следует выбирать несколько характерных точек (предельные значения и несколько промежуточных), при которых проверяется программа. В особых точках значений и сочетаний переменных и в точках разрыва функции необходимо планировать дополнительные проверки. Таким образом, сложность проверки программного модуля будет определяться числом маршрутов M _Х исполнения программы и числом обрабатываемых операндов l _i на каждом i-м маршру­те, умноженном на число значений s _{i j} для каждой исходной j-й ве­личины на этом маршруте:

(13.2)

Расчет показателя сложности тестирования программного моду­ля по такой схеме имеет значительную неопределенность из-за про­извола в выборе числа значений s _{i j} (в основном, особых точек) при варьировании исходных данных в тесте. В то же время доля вычислительной части во многих сложных ПС относительно не­велика.

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

Структурная сложность программного модуля может быть рассчитана по числу маршрутов М _Х в программе и сложности каждого i-го маршрута Е _i . Эти показатели в совокупности определяют мини­мальную сложность Е _Х тестов для проверки программного модуля (13.1), а следовательно, трудоемкость его разработки и тестирования, и вероят­ность пропуска логической ошибки в программе. Программные модули являются наиболее массовыми компонентами в ПС и требуют для тестирования суммарно наибольших затрат ресурсов. Затра­ты на тестирование каждого модуля прямо пропорциональны сложности, которая зависит от его структуры и объема вычислений l _i . При тестировании программного модуля необходимо задать и проа­нализировать число значений параметров:

(13.3)

Суммарные затраты ресурсов на тестирование модуля пропорциональны значению его сложности В _Х и, с учетом удельных затрат на создание каждого теста  с, определяются выражением:

(13.4)

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

Сложность тестирования программ, содержащих циклы. Наличие циклов в программе способно резко увеличивать сложность их тестирования. Полное, исчерпывающее тестирование должно охватывать проверку каждого маршрута в цикле при всех возможных итерациях цикла и при всех сочетаниях циклов с маршрутами ациклической части программы. Предположим для простоты, что число марш­рутов в нижней ациклической части программы равно М ₃ =1. Тогда полное множество маршрутов M состоит из полной совокуп­ности всех маршрутов M₁ в верхней ациклической части программы и группы маршрутов M ₂, в которой к каждому маршруту из M ₁ присое­динено 1..2..3... итерации (витка) цикла. При этом на каждой итерации выполняется, по крайней мере, один из внутренних маршрутов тела цикла.

Например, для графа, имеющего один цикл, требующего испол­нения пяти итераций (витков) с тремя внутренними маршрутами, а также содержащего M ₁ = 10 ациклических маршрутов, проходящих че­рез цикл, суммарное число маршрутов для исчерпывающего тестиро­вания равно M = (3 x 5) x 10 = 150. При возрастании любого из сомно­жителей (числа независимых ациклических маршрутов, проходящих через цикл, числа внутренних маршрутов тела цикла или числа его итераций) пропорционально растет их произведение, а, следователь­но, и сложность тестирования. Поэтому исчерпывающее тестирование реальных сложных программ с циклами может быть практически невозможно.

На сложность тестирования цикла оказывает влияние его структура и два параметра: число маршрутов в теле цикла и число итераций цикла. В динамике реального исполнения простейшего цик­ла между его итерациями могут существовать зависимости, по край­ней мере, трех видов:

- на разных итерациях цикла исполняются независимо все воз­можные маршруты тела цикла;

- на всех итерациях цикла исполняется один и тот же маршрут тела цикла или некоторая определенная их последовательность;

- на разных итерациях цикла в силу наличия семантических связей исполняется подмножество реализуемых маршрутов тела цик­ла, зависящее от данных или от номера итерации.

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

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

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

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

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

Сложность тестирования программных компонентов (функциональных групп прог­рамм) определяется суммарной сложностью модулей и межмодульных связей по управлению и по информации. Каждый модуль должен тестироваться автономно до включения в группу программ и частично в составе группы. Затраты на тестирование модулей в составе группы программ должны учитывать относительные суммарные затраты на тестирование всех входящих модулей с коэффициентом d _k < 1, зависящим от степени предшествующей проверки модуля. Если модули автономно не тестировались (например, при нисходящем тестировании), то d _k = 1 и затраты на тестирование каждого модуля войдут в затраты при тестировании группы программ в полном объеме. При тщательном автономном тестировании модулей можно полагать d _k = 0,1-0,01, т.е. в составе ПС затраты на тестирование каждого из модулей составляют несколько процентов.

13.5. Примеры оценок сложности тестирования программ

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

На рис. 13.7 представлен пример исходного графа модуля програм­мы, содержащего 14 вершин, 20 дуг и 3 цикла. Такая программа сравнительно невысокой сложности содержит около 30-50 операторов на языке высокого уровня и может рассматриваться как достаточно типичная. Для полной про­верки модуля по первому критерию достаточно четырех маршрутов. По этому критерию гарантируется проверка всех передач управления между операторами программы и каждого оператора не менее одного раза. Самый длинный по числу вершин маршрут не охватывает только 3 вершины из 14 и только 6 дуг из 20.

После проверки еще двух маршрутов вне контроля остается одна вершина и две дуги. Однако при этом критерии не учитывается комбинаторика сочетания условий на разных участках маршрутов, например, при сочетаниях направлений ветвлений в вершинах 3 и 12. Сложность программы при выделении маршрутов по этому критерию характеризуется числом маршрутов равным четырем и сложностью тестирования равной 20. Эта величина характеризует суммарное число условий, которое необходимо задать в тестах для полной проверки всех маршрутов, выделенных по первому критерию. Условия в вершинах каждого маршрута могут использоваться для автоматизированного формирования предикатов в соответствующих тестах.

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

Наиболее глубокий третий критерий проверки и определения сложности тестирования структуры программы включает требования однократной проверки не только линейно независимых, но и всех линейно зависимых циклов и ациклических маршрутов. Он заключает­ся в анализе хотя бы один раз каждого из реальных ациклических маршрутов исходного графа программы и каждого цикла, достижимого из всех этих маршрутов. Для примера графа программы, представ­ленного на рис. 13.7, по данному критерию необходимо исполнить 6 ациклических и 5 маршрутов, из которых достижимы элементарные циклы. Для реализации выделенных маршрутов в 11 тестах необходи­мо в совокупности задать 66 условий. При этом особенностью четы­рех последних маршрутов с циклами, также как соответствующих им ациклических маршрутов, является полный перебор сочетаний ветвле­ний в 3 и 12 вершинах.

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

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

Анализ проведен для двух типов ациклических графов при выделении маршрутов по критерию охвата каждой дуги графа программы хотя бы один раз X₁ и по критерию выделения всех маршрутов, различающихся хотя бы одной дугой Х₂ . В числе выбранных содержатся структуры, охватывающие наиболее типовые варианты компонентов графов программ. Структуры различались шириной графов, вследствие чего отличались число маршрутов и сложность полного тестирования таких структур. Сложность тестирования ПМ оценивалась по числу маршрутов исполнения программы, отражающих число тестов, необходимых для полной проверки корректности структуры модуля. Кроме того, в качестве показателя структурной сложности тестирования анализировалось суммарное число условий, которое необходимо задать в тестах (сложность тестирования) для проверки модуля.

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

Структурная сложность тестирования графов ПМ изменяется в более широком диапазоне, чем число маршрутов, что определило выбор логарифмического масштаба по оси ординат на рис. 13.8. Наименьшей структурной сложностью характеризуется граф Г₂ при выделении маршрутов по первому критерию. Для таких графов структурная сложность возрастает практически линейно в зависимости от числа вершин. При выделении маршрутов по второму критерию тот же граф характеризуется наибольшей структурной сложностью. При 30 и более вершинах структурная сложность этого графа почти на порядок выше, чем графа Г₁ при том же числе вершин. Относительная разница сложности тестирования этих графов при критерии Х₂ приблизительно сохраняется при изменении числа вершин от 16 до 100. Такое распределение значений структурной сложности от типов графов обусловлено различием их ширины. Так как число маршрутов при критерии Х₂ в зависимости от числа вершин во всех графах изменяется практически одинаково, то определяющим различия структурной сложности является число условий анализируемых в каждом маршруте. Во всех маршрутах графа Г₂ участвуют все его вершины, что определило его наибольшую структурную сложность.

На рис 13.8 точками (с указанием числа совпадающих значений) отмечены значения структурной сложности тестирования около 70 реальных ациклических ПМ в двух системах. Характеристики абстрактных графов Г₁ и Г₂ действительно охватывают диапазон изменения показателей сложности тестов для реальных программ, которые по каждому критерию группируются приблизительно посередине. Максимальная сложность тестов по второму критерию для произвольных ациклических программ близка к числу вершин в квадрате. По тому же критерию минимальная сложность тестов для широких структурированных графов типа дерево на порядок меньше максимальной сложности. Для усредненных оценок сложности полных тестов произвольных ациклических программ хорошее приближение для инженерных оценок при n _в > 10 дает выражение n _в ² /3 (штриховая линия на рис. 13.8). Характерно, что увеличение числа вершин в 4 раза (от 32 до 128) для рассмотренных графов приводит к возрастанию структурной сложности более чем в 10 раз. Если же программу, имеющую 128 вершин, разделить на 4 модуля, то их суммарная сложность практически равна только учетверенной сложности модулей, содержащих по 32 вершины. Исследованные реальные ПМ 80% случаев содержат не более 10 вершин и имеют структурную сложность тестирования < 50.

Показано, что при разработке ПМ целесообразно учитывать рациональное ограничение размеров модулей на уровне трехсот строк текста, что соответствует приблизительно тридцати альтернативам в ациклических программах. При этом для полного покрытия таких ПМ тестами необходимо задавать до 1000 условий, что обычно достаточно трудно или невозможно реализовать практически. В среднем полное тестирование программ с 30-ю вершинами ветвления производится тестами с суммарной сложностью около 300 – 500. Суммарная сложность тестов, необходимых для полного тестирования программ, имеющих различные структуры, может отличаться в несколько раз.

Поэтому при разработке ПМ рекомендован рациональный размер программ модулей в пределах 100 – 200 строк текста, для полного тестирования которых достаточно использовать 10 – 20 тестов с суммарным числом условий ветвления до 100. При превышении рекомендуемых размеров ПМ их трудно протестировать полностью и целесообразно делить на более мелкие компоненты, доступные для практически полного покрытия тестами.

Для получения практических оценок достигаемой корректности программы при покрытии тестами ее структуры, необходимо оценить диапазон реальной вероятности ошибки допускаемой квалифицированным программистом первично в каждой дуге графа программы. Экспериментально установлено, что для слабо структурированных программ число ошибок, выявляемых в процессе тестирования программных модулей, составляет около одного процента числа строк текста этих модулей. Для программ обработки информации и управления число условных переходов составляет около 10% числа строк в программе, т.е. ветвление в программе происходит в среднем после исполнения 10 строк текста линейных участков. Следовательно, порядка 10% линейных участков (или дуг в графе) программных модулей могут содержать первоначально ошибки перед тестированием, что соответствует вероятности q _{i j}  0,l .

Использование правил структурного программирования, спецификаций требований на модули и группы программ, а также современной технологии программирования позволяет снизить первичную вероятность ошибок приблизительно на порядок, т.е. до уровня q _{i j}  0,01. Поэтому оценивание стратегий тестирования и достигаемой при этом корректности целесообразно проводить в диапазоне q _{i j} = 0,10,01, соответствующем практически наихудшим и наилучшим значениям вероятностей ошибок в дуге до тестирования.

Для простейших оценок можно предположить, что все дуги в графе программы имеют одинаковую длину и эквивалентны по вероятности появления в них ошибок, т.е. q _{i j} = const в начале тестирования модуля. В действительности дуги графов реальных программ содержат различные типы операторов, которые в разной степени подвержены искажениям и ошибкам. Операторы в программе различаются по своей сложности и соответственно по вероятности искажения их программистами в процессе создания программ. В зависимости от типа оператора, в котором допущена первичная ошибка, различаются последствия проявления искажений (вторичные ошибки).

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

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