Обычно целью тестирования является обнаружить как можно больше из имеющихся в программе ошибок. Но определять качество теста по количеству найденных ошибок - все равно что определять качество работы ГАИ по количеству оштрафованных водителей… Поэтому в качестве критериев адекватности теста используются другие признаки.

 

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

 

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

 

if (a >= b) {ветвь 1}
else {ветвь 2}

 

должен иметь два набора входных данных: первый, при котором переменная a принимает значение, больше или равное значению переменной b, и второй при котором значение a становится меньше b.

 

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

 

Случайное генерирование тестовых данных

 

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

 

Символическое генерирование тестовых данных

 

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

 

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

Проблемы возникают и при косвенных ссылках на данные. Например, в коде

 

a = B [c+d]/2
 

неизвестно, какой элемент массива B, индекс которого описан выражением c+d, участвует в выражении, так как переменные c и d не имеют конкретных значений.

 

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

 

*a=3;
*b=5;
c=*a;
 

Здесь переменная с принимает значение 3, если только указатели a и b не ссылаются на одну и ту же ячейку. В противном случае она принимает значение 5. Поскольку в ходе символического выполнения переменные a и b не имеют численных значений, результирующее значение переменной c не может быть определено.

 

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

 

Динамическое генерирование тестовых данных

 

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

 

Например, предположим, что в строке 123 некой программы содержится условие:

 

if (v >= 13){ветвь v}
 

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

 

Пусть v123(x) - значение переменной v, зафиксированное в строке 123, когда программа выполнялась с набором входных данных x. Тогда функция

 

 13 - v123 (x), если v123 (x) < 13;
I = 
 0

 

принимает минимальное значение, если условие в строке 123 истинно. Таким образом, генерирование тестовых данных сводится к нахождению минимума функции: необходимо найти значение x, при котором функция I(x) принимает минимальное значение.

 

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

 

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

 

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

 


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

 

Генетические алгоритмы

 

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

 

Вначале генетический алгоритм создает исходную популяцию индивидов, каждый из которых представлен случайно генерированным генотипом. Способ, которым определяется жизнеспособность индивидов, зависит от конкретной задачи. Генетический алгоритм стремится выявить из начальной популяции индивидов с высокой жизнеспособностью. В нашем случае индивид тем жизнеспособнее, чем больше он удовлетворяет условиям теста. Например, если целью теста является добиться, чтобы значение переменной v в строке 123 было больше или равно 12, то входные данные, которые приведут к тому, что переменная v в стоке 123 примет значение 10, будут считаться более жизнеспособным индивидом, чем входные данные, которые приведут к значению -125.

 

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

 

Базовый алгоритм, где P (t) - популяция строк в поколении t, выглядит так:

 

Инициализировать P (t)
Вычислить P (t)
До тех пор пока (условие окончания не выполнено)
выполнять цикл
Отобрать P (t+1) из P (t)
Рекомбинировать P (t+1)
Вычислить P (t+1)
t = t+1

 

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

 

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

 

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

 

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

 

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

 

main (int argc, char **argv)
{
int a = atoi (argv [1]);
if (a > 100)
puts ("hello world\n");
}

 

Как видим, входные данные нашей программы считываются оператором int a = atoi (argv [1]), который получает первый аргумент из командной строки и присваивает его переменной a. Предположим, что требование теста - выполнить оператор puts в строке 6, в результате чего будет напечатана фраза hello world.

 

Таким образом, целевая функция основывается на значении переменной a в строке 3. Именно здесь эта переменная определяет, будет ли достигнута строка 4. Поэтому при тестировании после выполнения строки 3 тестовому генератору передается значение a-100. Это и есть значение целевой функции I(a).

 

Генетический алгоритм начинает работу с генерирования исходной популяции входных тестовых данных. Каждый набор входных данных рассматривается генетическим алгоритмом как один индивид. Предположим, что на первой итерации алгоритм генерировал четыре индивида со значениями 94, 91, 49 и -112.

 

Для определения жизнеспособности каждого из четырех наборов входных данных тестируемая программа выполняется с этим набором данных. Чем меньше полученное значение, тем соответствующий набор входных тестовых данных ближе к удовлетворению поставленного условия. Но в генетическом поиске с большей жизнеспособностью традиционно ассоциируются большие значения. Последуем этому соглашению и мы. Тогда жизнеспособность каждого набора входных данных будет равна обратной величине от значения, полученного после выполнения тестируемой программы. Для входных значений -112, 49, 91 и 94 программа вернула значения 222, 51, 9 и 6, соответственно. Таким образом, относительная жизнеспособность четырех наборов входных данных составляет 1/222, 1/51, 1/9 и 1/6.

После того как получена жизнеспособность каждого набора входных тестовых данных, начинается репродуктивная фаза генетического алгоритма. Для репродукции выбираются два набора входных данных в соответствии с их жизнеспособностью. Они выбираются путем нормализации значений жизнеспособности и использования их в качестве относительных вероятностей выбора каждого набора входных данных в качестве родителя для последующего воспроизводства. Таким образом, вероятности выбора значений -112, 49, 91 и 94 составляют 0,015, 0,065, 0,368 и 0,552, соответственно. Поскольку индивидов только четыре, существует значительная вероятность выбора одного и того же индивида дважды. Но во многих генетических алгоритмах заложены явные механизмы по предотвращению этого. Предположим, что в нашем алгоритме такая возможность тоже есть.

 

Предположим, что два выбранных родителя - это 91 и 94, как наиболее вероятные. Для воспроизводства каждое из чисел представляется в двоичной форме - 01011011 и 01100000, соответственно. Точка скрещивания выбирается случайным образом - предположим, 3. Скрещивание происходит путем обмена первых трех битов двух родителей. Получаем двух потомков - 01000000 и 01111011, то есть 64 и 123.

 

Воспроизводство продолжается до тех пор, пока количество потомков не станет равным исходному размеру популяции. Поэтому алгоритм выбирает следующую пару родителей. Предположим, это -112 и 91, а точка скрещивания - 5. Если преобразовать входные значения в 8-битовые строки, то получим 10010000 и 01011011, соответственно. Скрещивание даст потомков 10010011 и 01011000, или -109 и 88.

 

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

 

Заключение

 

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

 

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

2004.04.28
19.03.2009
В IV квартале 2008 г. украинский рынок серверов по сравнению с аналогичным периодом прошлого года сократился в денежном выражении на 34% – до $30 млн (в ценах для конечных пользователей), а за весь календарный год – более чем на 5%, до 132 млн долл.


12.03.2009
4 марта в Киеве компания Telco провела конференцию "Инновационные телекоммуникации", посвященную новым эффективным телекоммуникационным технологиям для решения задач современного бизнеса.


05.03.2009
25 февраля в Киеве компания IBM, при информационной поддержке "1С" и Canonical, провела конференцию "Как сохранить деньги в условиях кризиса?"


26.02.2009
18-19 февраля в Киеве прошел юбилейный съезд ИТ-директоров Украины. Участниками данного мероприятия стали ИТ-директора, ИТ-менеджеры, поставщики ИТ-решений из Киева, Николаева, Днепропетровска, Чернигова и других городов Украины...


19.02.2009
10 февраля в Киеве состоялась пресс-конференция, посвященная итогам деятельности компании "DiaWest – Комп’ютерний світ" в 2008 году.


12.02.2009
С 5 февраля 2009 г. в Киеве начали работу учебные курсы по использованию услуг "электронного предприятия/ учреждения" на базе сети информационно-маркетинговых центров (ИМЦ).


04.02.2009
29 января 2009 года в редакции еженедельника "Computer World/Украина" состоялось награждение победителей акции "Оформи подписку – получи приз!".


29.01.2009
22 января в Киеве компания "МУК" и представительство компании Cisco в Украине провели семинар для партнеров "Обзор продуктов и решений Cisco Small Business"

 

 
 
Copyright © 1997-2008 ИД "Комиздат".