Отладка программ и программных комплексов (стр. 2 из 4)

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

Необходимо отметить, что исчерпывающее тестирование программы на всех допустимых множествах входных данных неосуществимо, так как даже для программы с двумя целочисленными входами (32-битовых входа) общее число входных наборов составляет 2³² х 2³² = 2⁶⁴. При наличии в программе циклов, число итераций которых зависит от исходных данных, количество элементов или структур, которые необходимо проверить, становится неопределенно большим. При использовании схем в качестве моделей программ не могут быть выявлены ошибки в неисполнимых операторах, используемых для описания переменных, выделения им определенных областей оперативной памяти и т.п.

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

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

называют операционным профилем программы. Из каждого множества S_j случайным образом выбираются данные для n_j тестов. Количество тестов n_jопределяется в соответствии с вероятностями p_i(S_j).

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

содержит входные векторы, называемые эффективными. Для каждой координаты эффективного входного вектора с помощью генератора случайных чисел выбирается некоторое значение а_β из х и строится тест , который реализуется программой. В процессе реализации теста определяется множество дуг γ_i на графе возможных реализаций программы, которые входят в расчетный путь теста , и объединение множеств Среди этих дуг определяют дуги, не входившие в множество γ, полученное на предыдущем шаге. Если такие дуги есть, проверяют, не превышает ли отношение общего числа пройденных дуг ко всему множеству дуг графа возможных реализаций программы заданной величины . Если этот критерий не удовлетворяется, пытаются найти данные для непокрытых проведенными тестами дуг графа методами, аналогичными методам символического тестирования, которые описываются ниже.

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

На практике обычно используется множество М*(Р), содержащее мутанты Р, полученные многократным применением мутационных операторов к Р. Считается, что программа прошла мутационный тест с входным набором

, если: 1) программа Р функционирует верно на данных Т; 2) для каждого mмутанта из М*(Р) либо mне проходит на данных Р, либо mэквивалентен Р. Здесь D – входная область программы Р. Таким образом, если программа Р проходит мутационный тест, то она свободна от простых ошибок. Относительно комплексных ошибок делается предположение, что вероятность того, что композиция нескольких простых ошибок приведет к успешному выполнению на данных Т соответствующего мутанта, равна нулю.

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

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

Методы, использующие символическое исполнение программы, являются промежуточными между методами формального доказательства правильности программ и методами эмпирического тестирования. Эти методы дают возможность значительно сократить число используемых тестовых прогонов и позволяют обнаруживать до 70% ошибок.

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

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

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

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

Известные методы и модели формализации процесса локализации ошибок обеспечивают лишь автоматизацию процедур выделения областей локализации ошибок. При этом используется диагностическая модель программы, задаваемая совокупностью <Х, V, Г₁, Г₂, Г₃, Г₄> и представляемая графом, где X– множество вершин, соответствующих переменным комплекса программ; V – множество дуг, соответствующее линейным участкам команд; Г₁ – отображение множества Vв V; Г₂и Г₃ -отображения множества Xв Vи Vв Xсоответственно; Г₄ – отображение множества Xв X. Параметры тестового набора задаются точкой входа v_b, точкой выхода v_l, множеством вершин исходных данных X_b и множеством вершин результатов X_l. Кроме того, задана булева функция правильности результатов F(x_j) для

и правильности точки выхода F(v_b).

Решение задачи определения области локализации ошибок сводится к выделению подграфа, связывающего вершины v_l и v_b,. Дальнейшие операции по установлению места расположения ошибки проводят вручную. Недостатком рассмотренного метода локализации является то обстоятельство, что выделенные подграфы локализации ошибки имеют, как правило, весьма большие размеры и в предельных случаях включают все элементы диагностической модели. Это объясняется тем, что в данном методе не учитывается конкретное содержание тестовых наборов и их направленность на выявление определенных свойств проверяемой программы.