Cтраница 3
К сожалению, данный алгоритм применим только для разрезания линейных участков. Проблема разрезания естественных частей, представляющих собой циклические участки, более сложна. Для решения ее в [68] указан точный метод, а в [51] - приближенный, являющийся частью общего метода сегментации, который может быть полезен, если программа допускает эффективное разделение по циклам. Укажем еще на метод С. Н. Бушева [13], который основан на методе Д. А. Поспелова и имеет трудоемкость, пропорциональную числу вершин в управляющем графе сегментируемой программы. В методе Бушева на первом этапе производится разрезание на уровне операторов. На следующих этапах операторы склеиваются согласно требованиям, предъявляемым к сегментированию, которые преследуют цель получения оптимального в некотором смысле разрезания. [31]
Уровень подсистем представляется целесообразным выделять при проверке сложных систем программного обеспечения. Различают следующие способы тестирования: тестирование путей и программных модулей, символическое тестирование, тестирование экстремальных значений и необычных ситуаций и адаптивное тестирование. Пусть тестирование определяется в виде последовательности реализуемых инструкций для графа Gt для каждого теста. Из-за большого числа обратных связей в структуре любой программы невозможно проверить все пути графа. Поэтому практически этот вид тестирования представляет собой проверку отдельных подграфов графа программы. [32]
Выделение циклов и маршрутов в них позволяет преобразовать программу к ациклическому виду. При этом циклы заменяются их ациклическими эквивалентами с фиксированным и ограниченным числом итераций. Для выделения тестируемых маршрутов в такой ациклической программе разработчик должен указать критерий, по которому следует формировать маршруты. Кроме того, разработчик указывает стратегию для составления упорядоченного списка маршрутов, по которому надлежит планировать тестирование. Упорядочение маршрутов производится по длительности их исполнения или по вероятности реализации при случайных данных на входе программы. Если ряд маршрутов может быть нереализуемым по сочетаниям условий в вершинах графа программы, то такие маршруты целесообразно исключить из последующего анализа. [33]
Все функциональные характеристики выборочно связаны с каждой вершиной в зависимости от предполагаемого анализа. Размерность графа программы находится в прямой зависимости от размера программы. При увеличении размера программы существенно возрастает сложность анализа. Разработаны достаточно эффективные процедуры, позволяющие снижать сложность анализа. В основу таких процедур положены методы итеративной абстракции, которая имеет два аспекта: абстракция цикла и абстракция подграфа связи. Цикл является трудным элементом для эффективной проверки программ, так как он резко увеличивает число логических путей, усложняя тем самым структурную программу. Рассмотрение цикла и анализ его независимо от осталыной части графа программы делают общий процесс проверки более простым и однородным. Такая абстракция цикла приводит к значительному уменьшению размерности модели и снижению структурной сложности. Если вследствие большой размерности приведенного графа желательна дальнейшая абстракция, то может быть применена абстракция подграфа связи, когда максимально сильно связанный подграф в графе программы заменяется одной вершиной. [34]