Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware
VPS/VDS серверы. 30 локаций на выбор

Серверы VPS/VDS с большим диском

Хорошие условия для реселлеров

4VPS.SU - VPS в 17-ти странах

2Gbit/s безлимит

Современное железо!

Бесплатный конструктор сайтов и Landing Page

Хостинг с DDoS защитой от 2.5$ + Бесплатный SSL и Домен

SSD VPS в Нидерландах под различные задачи от 2.6$

✅ Дешевый VPS-хостинг на AMD EPYC: 1vCore, 3GB DDR4, 15GB NVMe всего за €3,50!

🔥 Anti-DDoS защита 12 Тбит/с!

2006 г.

Критерии полноты тестового покрытия в генетических алгоритмах генерации тестов1

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

Введение

При разработке и сопровождении программного обеспечения, значительная часть усилий тратится на поиск и устранение ошибок. Самым распространённым методом поиска ошибок является тестирование, то есть процесс выполнения программ с целью обнаружения ошибок [1]. Здесь слово «программа» понимается в широком смысле, как любая запись алгоритма. В частности, программами являются отдельные процедуры, функции, классы и т.д.

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

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

Построение полного тестового набора для больших систем вручную может быть крайне трудоёмкой задачей. Автоматизация этого процесса позволяет существенно снизить затраты на тестирование. Существуют различные подходы к решению задачи автоматической генерации тестов: [3,4,6]. Один из них основан на применении генетических алгоритмов [8]. Этот подход во многих случаях даёт хорошие результаты. К сожалению, его эффективность существенно зависит от используемого критерия полноты. Цель данной статьи - проанализировать некоторые широко распространённые критерии полноты тестового набора на их применимость при использовании генетических алгоритмов для генерации тестов.

Основные понятия

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

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

Общая схема генетического алгоритма выглядит следующим образом:

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

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

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

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

Критерии полноты тестового покрытия

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

Пусть P - множество программных систем, T - множество тестов, а Σ - множество тестовых наборов, то есть множество всех конечных подмножеств множества T . Тогда задача генерации тестов может быть сформулирована следующим образом: для заданной тестируемой системы S isin.gif P построить тестовый набор image011.gif, удовлетворяющий заданному критерию полноты тестового покрытия image013.gif, то есть такой набор image015.gif, для которого image017.gif.

Многие критерии полноты тестового покрытия, имеющие практическое применение, строятся по следующей схеме: для тестируемой системы S критерий F определяет множество элементов тестового покрытия image023.gif. Элементом тестового покрытия можно считать некоторый класс событий, которые могут произойти в ходе работы тестируемой программной системы. По появлению в процессе исполнения программы элементов тестового покрытия и различных их комбинаций можно судить о полноте или качестве проверки, которую выполняет данный тестовый набор. Например, элементами тестового покрытия могут быть исполняемые строки исходного кода (соответствующие событиям их исполнения); рёбра графа потока управления; пути в графе потока управления; логические выражения, встречающиеся в исходном коде и т.п. Кроме того, критерий F определяет логическую функцию image026.gif, которая принимает значение image028.gif, если элемент тестового покрытия q покрывается тестом t. Тестовый набор image015.gif для системы S удовлетворяет критерию полноты тестового покрытия F, если каждый элемент тестового покрытия из множества image023.gif покрывается хотя бы одним тестом из тестового набора image015.gif. Иными словами:

image039.gif

(1)

Приведём несколько примеров часто упоминаемых критериев полноты тестового покрытия:

  • каждый оператор в исходном коде выполняется хотя бы один раз;
  • каждая ветвь графа потока управления выполняется хотя бы один раз;
  • каждый путь графа потока управления исполнение выполняется хотя бы один раз;
  • каждое логическое выражение хотя бы один раз вычисляется со значением «истина» и хотя бы один раз - со значением «ложь»;
  • тестовый набор убивает всех мутантов из заданного набора.

Заметим, что все критерии, приведённые в качестве примеров, соответствуют ранее изложенной схеме.

Метрики тестового покрытия

Со многими критериями полноты тестового покрытия можно связать соответствующую метрику тестового покрытия. Метрика тестового покрытия - это функция вида image041.gif. Значение этой функции image043.gif имеет смысл числовой оценки того, насколько хорошо тестовый набор image015.gif покрывает тестируемую систему S. Сам критерий при этом можно записать в виде image047.gif, где image049.gif - это минимальное пороговое значение метрики M для тестируемой системы S.

В частности, для критерия полноты тестового покрытия F, представимого в виде (1), можно ввести следующую метрику:

image055.gif

(2)

Сам критерий при этом примет вид:

image057.gif

(3)

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

image059.gif

(4)

Параметр image061.gif указывает, какая доля элементов тестового покрытия должна быть покрыта тестовым набором. Приведём несколько примеров часто упоминаемых метрик тестового покрытия:

  • количество покрытых (выполненных хотя бы один раз) операторов в исходном коде;
  • количество покрытых ветвей графа потока управления;
  • количество покрытых путей графа потока управления;
  • количество распознанных мутантов (версий тестируемой системы с искусственно привнесёнными ошибками).

Все эти метрики могут быть представлены в виде (2). Подробное описание этих и других, используемых на практике, метрик полноты тестового покрытия можно найти в [9].

Генетический алгоритм генерации тестов

Рассмотрим следующую задачу генерации тестов:

Задача 1. Для заданной тестовой системы S построить тестовый набор image011.gif, удовлетворяющий критерию (4).

Для построения генетического алгоритма решения этой задачи необходимо определить:

  • множество кандидатов;
  • структуру представления кандидатов;
  • оценочную функцию;
  • оператор кроссовера;
  • оператор мутации;
  • условие останова.
Простейший алгоритм

Рассмотрим простейший генетический алгоритм для решения задачи 1. В качестве множества кандидатов возьмём множество Σ; в качестве оценочной функции возьмём метрику тестового покрытия image066.gif для заданной тестируемой системы S. Условием останова будет наличие в текущем поколении решения image015.gif, удовлетворяющего критерию (4). Структуру представления кандидатов, а также операторы кроссовера и мутации мы пока уточнять не будем.

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

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

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

Целенаправленный поиск

Учитывая структуру критерия (4), из задачи 1 можно выделить следующую подзадачу:

Задача 2. Для заданной тестовой системы S и заданного элемента тестового покрытия q, построить тест image075.gif , удовлетворяющий условию image028.gif.

Для решения исходной задачи 1, достаточно решить задачу 2 для image078.gif попарно различных элементов тестового покрытия image080.gif, то есть построить тесты image082.gif такие, что

image084.gif

Решением задачи 1 будет множество image086.gif .

Рассмотрим генетический алгоритм решения задачи 2. В качестве множества кандидатов возьмём множество тестов T. Условие останова: в текущей популяции присутствует тест q такой, что image028.gif. Оценочная функция image091.gif каждому тесту t ставит в соответствие числовую меру image094.gif того, насколько тест t близок к тому, чтобы покрыть элемент тестового покрытия q. При этом оценочная функция image098.gif достигает своего максимального значения на тех и только на тех тестах, которые удовлетворяют условию image028.gif. Иными словами:

image101.gif

(5)

В частности, в качестве оценочной функции можно использовать следующую функцию, удовлетворяющую условию (5):

image103.gif

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

Оценочные функции

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

Покрытие операторов исходного кода

Тестовый набор удовлетворяет критерию покрытия операторов исходного кода, если при выполнении этого тестового набора каждый оператор исходного текста программы выполняется хотя бы один раз. Элементами тестового покрытия в данном случае являются операторы исходного текста. Для заданного оператора q значение оценочной функции image094.gif тем больше, чем ближе тест t к тесту, покрывающему оператор q. Для построения оценочной функции рассмотрим граф потока управления тестируемой системы S. Вершинами графа являются операторы исходного кода, то есть множество image023.gif. В графе существует ребро, идущее из вершины q1 в вершину q2 тогда и только тогда, когда оператор q2 может быть выполнен непосредственно после оператора q1. Пусть image119.gif - это множество всех элементов q' из image023.gif, для которых выполняются следующие условия:

  • существует путь в графе потока управления ведущий из q' в q или q' = q;
  • image128.gif.

Обозначим через dist(q', q) длину кратчайшего пути в графе потока управления, ведущего из q' в q (dist(q, q)≡0). Тогда оценочную функцию можно определить следующим образом:

image136.gif

(6)

Выражение, стоящее справа, определяет, за какое минимальное количество переходов можно добраться до элемента покрытия q от уже покрытых элементов из множества image023.gif. Функция image094.gif принимает значение 0 на тех и только тех тестах, которые покрывают элемент q. Заметим, что

image144.gif

Покрытие ветвей потока управления

Тестовый набор удовлетворяет критерию покрытия ветвей потока управления, если при выполнении этого тестового набора управление хотя бы один раз проходит по каждому ребру графа потока управления. Заметим, что любой тестовый набор, удовлетворяющий этому критерию, удовлетворяет также и критерию покрытия операторов исходного кода. Обратное утверждение, однако, неверно [9]. Элементами тестового покрытия являются переходы в графе потока управления. С каждым переходом в графе потока управления можно связать условие, при котором этот переход может быть выполнен. Переход от оператора q к оператору r, с которым связано условие p, обозначим как image151.gif. Для выполнения перехода image151.gif необходимо и достаточно, чтобы был выполнен оператор q, и чтобы после этого условие p обратилось в истину. Соответственно, для тестов, не покрывающих оператор q, в качестве оценочной подходит функция image157.gif, определённая уравнением (6), так как истинность условия p для оценки таких тестов роли не играет. Для тестов, покрывающих оператор q, функция image094.gif обращается в 0. Для таких тестов оценочная функция должна определять, насколько близок тест к тесту, для которого после выполнения оператора q будет истинным условие p. Таким образом, в общем виде оценочную функцию для критерия покрытия ветвей потока управления можно определить следующим образом:

image165.gif

(7)

Значение функции image167.gif тем больше, чем ближе заданный тест к тесту, в котором условие p выполняется после выполнения оператора q. При этом функция image171.gif достигает своего максимума на тех и только тех тестах, в которых после выполнения оператора q выполняется условие p, то есть тех, которые покрывают переход image151.gif .

Функцию image171.gif можно определять по-разному в зависимости от характера условия p. Если условие имеет форму простого (не)равенства image178.gif , где « image180.gif » обозначает одно из отношений « < », « > », « = », « ≤ » или « ≥ », то для определения функции image171.gif можно использовать значение image193.gif, например, следующим образом:

image195.gif

Если условие представляет собой конъюнкцию image197.gif, то в качестве значения функции image171.gif можно взять количество членов этой конъюнкции, принимающих значение «истина». В общем случае эффективно определить функцию image171.gif затруднительно.

Покрытие путей потока управления

Тестовый набор удовлетворяет критерию покрытия путей потока управления, если его выполнение хотя бы один раз проходит по каждому возможному пути в графе потока управления ведущему от точки входа до точки завершения работы. Этот критерий сильнее критерия покрытия ветвей потока управления. Каждый путь представляет собой последовательность переходов image201.gif, где image203.gif имеет вид image205.gif, при 1 ≤ in . Упорядоченным подмножеством пути image209.gif назовём последовательность image211.gif такую, что image213.gif. Заметим, что в упорядоченном подмножестве пути конечный оператор перехода может не совпадать с начальным оператором следующего за ним перехода.

Пусть есть два пути image215.gif и image217.gif , и пусть

image219.gif

причём image221.gif и image223.gif. Тогда пути image225.gif и image227.gif имеют общее упорядоченное подмножество размера m.

Обозначим через length(R) длину пути R, а через image235.gif - максимальный размер общего упорядоченного подмножества путей image225.gif и image227.gif. Определим оценочную функцию для критерия покрытия путей потока управления следующим образом:

image239.gif

Здесь path(t) - это путь, по которому приходит управление при выполнении теста t. Значение в правой части равно количеству переходов в путях R и path(t), не входящих в максимальное общее упорядоченное подмножество этих путей. Оно равно 0 тогда и только тогда, когда пути R и path(t) совпадают.

Заключение

Применение генетических алгоритмов для генерации тестов предъявляет дополнительные требования к используемым критериям полноты тестового покрытия. Это вызвано тем, что критерий полноты используется не только для оценки качества сгенерированных тестов, но и непосредственно в процессе генерации для оценки близости полученных тестов к нужным результатам. Таким образом, нужно иметь оценочную функцию, позволяющую измерить эту близость, определить, насколько перспективными являются уже построенные тесты с точки зрения их использования в качестве основы для построения новых тестов. Кроме того, нужно иметь в виду, что тривиальные решения - функции вида «покрыто - 0, не покрыто - 1» - работают очень плохо.

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

Литература

[1]обратно Г. Мейерс. Искусство тестирования. М.: Финансы и статистика, 1982.
[2]обратно André Baresel, Harmen Sthamer, and Michael Schmidt. Fitness function design to improve evolutionary structural testing. In GECCO, pages 1329-1336, 2002.
[3]обратно Chandrasekhar Boyapati, Sarfraz Khurshid, and Darko Marinov. Korat: Automated testing based on Java predicates. In Proceedings of the International Symposium on Software Testing and Analysis (ISSTA 2002) , Rome, Italy, 22-24 July 2002. IEEE.
[4]обратно Ugo A. Buy, Alessandro Orso, and Mauro Pezzè. Automated testing of classes. In ISSTA, pages 39-48, 2000.
[5]обратно Yoonsik Cheon and Myoung Kim. A fitness function for modular evolutionary testing of object-oriented programs. Technical Report 05-35, Department of Computer Science, University of Texas El Paso, Nov 2005.
[6]обратно Yoonsik Cheon, Myoung Kim, and Ashaveena Perumendla. A complete automation of unit testing for Java programs. In Hamid R. Arabnia and Hassan Reza, editors, Proceedings of the 2005 International Conference on Software Engineering Research and Practice (SERP '05), Volume I, Las Vegas, Nevada, June 27-29, 2005, pages 290-295. CSREA Press, 2005.
[7]обратно John H. Holland. Adaptation in natural and artificial systems. MIT Press, Cambridge, MA, USA, 1992.
[8]обратно Paolo Tonella. Evolutionary testing of classes. In ISSTA '04: Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, pages 119-128, New York, NY, USA, 2004. ACM Press.
[9]обратно Hong Zhu, Patrick A. V. Hall, and John H. R. May. Software unit test coverage and adequacy. ACM Comput. Surv. , 29(4):366-427, 1997.

1(к тексту)Работа поддержана грантом РФФИ (05-01-999).

VPS в России, Европе и США

Бесплатная поддержка и администрирование

Оплата российскими и международными картами

🔥 VPS до 5.7 ГГц под любые задачи с AntiDDoS в 7 локациях

💸 Гифткод CITFORUM (250р на баланс) и попробуйте уже сейчас!

🛒 Скидка 15% на первый платеж (в течение 24ч)

Скидка до 20% на услуги дата-центра. Аренда серверной стойки. Colocation от 1U!

Миграция в облако #SotelCloud. Виртуальный сервер в облаке. Выбрать конфигурацию на сайте!

Виртуальная АТС для вашего бизнеса. Приветственные бонусы для новых клиентов!

Виртуальные VPS серверы в РФ и ЕС

Dedicated серверы в РФ и ЕС

По промокоду CITFORUM скидка 30% на заказ VPS\VDS

Новости мира IT:

Архив новостей

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 495 7861149
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2019 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...