№37 (Надежность программного обеспечения) (1006294), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

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

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

Генерирование структурных тестов. Названных выше недостатков лишено структурное тестирование программ на конкретных числовых исходных данных.

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

Граф программы (граф управления) — структурная модель программы, показывающая связь между ее эле­ментами. Вершины графа изображают операторы разветвления и объединения, а дуги — операторы обработки и передачи данных. Граф представляется в виде упако­ванной матрицы смежности (УМС). Упакованная матри­ца смежности графа с v вершинами —это матрица (l — максимальная степень выхода i-й верши­ны). Степень входа d_вх(v_i) и выхода d_вых(v_i) некоторой вершины графа означает соответственно количество вхо­дящих и выходящих из вершин дуг. Каждая строка i УМС заполняется в произвольном порядке номерами вершин, которые являются смежными с вершиной i.

Представление графов в виде УМС имеет следующие преимущества по сравнению с другими существующими представлениями:

для больших графов число столбцов УМС значитель­но меньше, чем число столбцов соответствующей матри­цы смежности;

относительно просто моделируется процесс движения по графу для построения путей;

уменьшается время обработки графов.

За критерий тестирования взят критерий ветвей, где под ветвью программы понимается некоторая последовательность операторов, выполняемых строго один за дру­гим. Таким образом, ветвь — линейный участок програм­мы. Для построения минимального покрытия граф разби­вается па DD-пути с использованием УМС исходного графа. Множество вершин, у которых степень выхода d_вых(v_i)>1 , входная и выходная вершины обозначаются как D-вершины. Тогда DD-путь— простой путь между двумя D-вершинами, такой, что в его пределах нет D-вершин. Затем определяются циклы и петли и исключаются замыкающие их дуги.

Предлагаемый алгоритм построения минимального покрытия (МПОК) графа состоит из следующих этапов,

Этап 1. Просматривается i-я вершина и определяет­ся смежная вершина j, номер которой

является макси­мальным среди номеров смежных вершин, где i {1, N-1;} N - количество

вершин графа.

Этап 2. Просматривается дуга (v_i, v_j). Если d_вых( )>1 и d_вх( )>1, го дуга g(v_i, v_j) исключается.

Если d_вых( )>1 и d_вх( )=1,то дуга h(v_i, v_j) отме­чается/

Этап 3. Если d_вых( )=1 и d_вх( )>1 и если на пути не имеется дуги типа g, то исключаются

рассматривае­мая дуга и дуга типа h. отмеченная в этапе 2.

Этап 4. Подставляется i = j и повторяются этапы I—3 до тех пор, пока j не приравнивается

номеру конечной (выходной) вершины. Зафиксируется путь в виде последовательности

значений j.

Этап 5. Повторяются этапы 1—4 до тех пор, пока в построенном пути не останется дуг типа g и

h..

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

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

ФУНКЦИОНАЛЬНЫЕ МЕТОДЫ ТЕСТИРОВАНИЯ ПРОГРАММ

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

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

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

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

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

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

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

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

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

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

оценки центрального момента к-го порядка для i-й пере­меной

оценки
корреляционного момента между i-й и j-й пере­меной

где - измеренное значение i-й переменной в v-м экс­перименте; п — число экспериментов; r — число перемен­ных.

Характеристики

Список файлов ответов (шпаргалок)