Моделирование простых логических неисправностей вычислительных процессов программ

Немолочнов О.Ф., Зыков А.Г., Поляков В.И., Петров К.В.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ

ФЕДЕРАЦИИ


ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ


САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

Источник: http://books.ifmo.ru/ntv/ntv/32/ntv_32.pdf

Введение

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

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

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

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

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

Моделирование логических неисправностей

Для анализа качества тестовых последовательностей используют специально ге- нерируемые логические неисправности, которые при этом могут быть самыми разны- ми. Такой обобщенный подход получил название мутационного тестирования [3]. В данной статье мы рассмотрим более специализированный метод, моделирующий оди- ночные логические неисправности особого вида. Проявление логических неисправно- стей при этом фиксируется путем сравнения результатов выполнения программы без неисправностей (эталонные результаты) с результатами работы программы с внесенной в нее неисправностью [4]. В соответствии с описываемым методом, неисправности должны моделироваться по очереди в каждой из команд условного перехода, содержащихся в тестируемой программе. Внесение неисправностей будет, как правило, сводиться к замене таких команд на команды безусловной передачи управления. В общем случае каждой команде условного перехода (КУП), содержащейся в тестируемой программе, могут соответствовать две моделируемые неисправности:

• неисправность, при которой всегда происходит переход по указанному в команде адресу;
• неисправность, при которой перехода по указанному адресу никогда не происходит, и всегда выполняется команда, располагающаяся в памяти непосредственно за КУП.

Очевидно, что в первом случае условие перехода всегда становится истинным, во втором – ложным. Поэтому будем называть такие неисправности «константная 1» и «константный 0». Введем следующие математические обозначения: при моделировании неисправности «константная 1» в условии Cond будем писать Cond = 1 или Cond = true ; аналогично при моделировании неисправности «константный 0» будем писать Cond = 0 или Cond = false.

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

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

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

Пример использования логических неисправностей при тестировании программ

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

Для наглядности не будем изучать машинный код, а вместо этого сразу построим граф вычислительного процесса, порождаемого рассматриваемой программой (рис.2). Теперь предположим, что для тестирования этой программы предложено два набора входных данных: a = 0, b = 0, c = 1 и a = 1, b = 1, c = 0 . Если мы запустим программу с каждым из этих наборов, мы получим правильные результаты (табл. 2). Таким образом, программа успешно прошла предложенные тесты. Теперь необходимо ответить на вопрос, насколько качественным получилось это тестирование. Мы видим, что по разу были получены оба возможных ответа – 0 и 1, но для структурного тестирования такой критерий нельзя признать удовлетворительным. Для более точной оценки качества тестовых наборов используем метод моделирования логических неисправностей.

Сначала определяем, что программа содержит три условные вершины. Это значит, что для исчерпывающей проверки тестовых наборов нам необходимо последовательно промоделировать 3·2 = 6 логических неисправностей. При внесении неисправностей получим следующие результаты (табл.3. Жирным шрифтом выделены результаты, отличающиеся от эталонных, т. е. от полученных без неисправностей). Анализируя полученные данные, устанавливаем, что первый тестовый набор обнаруживает две неисправности, в то время как второй только одну; всего, таким образом, были обнаружены три различные неисправности, и внесение еще трех никак не отразилось на результатах работы программы.

Отдельно отметим интересный момент. Неисправность A = true должна с неизбежностью приводить к неправильной работе программы в случае входного набора (1, 1, 0). Действительно, в этом наборе a =1 <> 0> A = false . Однако результат работы программы при этом оказывается корректным. Рассматривая граф, можно определить причину этого: оказывается, что имеет место совпадение. Неисправность изменяет путь через программу, но на новом, неправильном пути происходит присвоение выходной переменной res того же значения, которое было бы присвоено в исходной программе. Такую ситуацию будем называть компенсацией неисправности. Компенсации уменьшают качество тестовых наборов, так как при их возникновении сокращается количество обнаруживаемых этими наборами неисправностей. res = 1

Все вышеизложенное означает, что для улучшения качества тестов необходимо к уже имеющимся двум добавить дополнительные наборы, которые могли бы выявить неисправности A = true , B = true и C = true . Поиск таких дополнительных наборов – это отдельная задача. Для такой простой программы, впрочем, особых трудностей здесь не возникает. Введем еще два тестовых набора: a = 1, b = 1, c = 1 и a = 0, b = 1, c = 1. После моделирования оставшихся неисправностей получим следующие результаты (табл.4). Теперь мы можем утверждать, что четыре рассмотренных тестовых набора в совокупности обеспечивают полноту контроля моделируемых логических неисправностей. Выше мы отметили, что при выполнении данного условия мы будем считать качество тестирования приемлемым, и обосновали причину этого. Таким образом, используя описываемый в статье метод, получаем решение поставленной задачи.

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

Заключение

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