■ ТЕСТИРОВАНИЕ, ВЕРИФИКАЦИЯ И ВАЛИДАЦИЯ ПРОГРАММ
УДК 004.92+004.94
ИСПОЛЬЗОВАНИЕ АБСТРАКТНЫХ МОДЕЛЕЙ ДЛЯ ГЕНЕРАЦИИ ТЕСТОВЫХ ДАННЫХ СЛОЖНОЙ СТРУКТУРЫ*
© 2008 г. А. В. Демаков, С. В. Зеленов, С. А. Зеленова
Институт системного программирования РАН 109004 Москва, ул. Б. Коммунистическая, 25 E-mail: demakov@ispras.ru, zelenov@ispras.ru, sophia@ispras.ru Поступила в редакцию 10.04.2008 г.
В статье представлен подход к автоматической генерации тестовых данных сложной структуры (таких, как XML-документы, программы на языках программирования и т.п.), основанный на использовании абстрактных моделей, которые отражают различные срезы структуры требуемых данных. Подход позволяет получать небольшие множества тестовых данных, нацеленных на тестирование заданной функциональности целевой системы. Использование абстрактных моделей делает процесс конфигурирования генерации легким и понимаемым, а также облегчает сопровождение и переиспользование существующих конфигураций генератора тестовых данных. Подход реализован в генераторе тестовых данных Pinery и успешно применялся в ряде проектов, в том числе в проектах по тестированию промышленных компиляторов языков С/С++.
ВВЕДЕНИЕ
Тестирование является важнейшим этапом каждого проекта по разработке программного обеспечения (ПО). С увеличением сложности разрабатываемого ПО стремительно возрастает трудоемкость тестирования. Повысить качество и снизить стоимость тестирования возможно лишь при использовании эффективных инструментов, позволяющих автоматизировать разработку тестов.
Одной из рутинных задач при тестировании сложных программных систем сейчас является генерация данных, обладающих некоторой сложной структурой. Такая задача встает при тестировании ПО, в котором используются протоколы Internet, базы данных, XML-интерфей-сы, а также ПО, занимающегося обработкой формальных текстов, таких, как исходные тексты программ, спецификации, скрипты и т.п.
* Работа частично поддержана грантом Российского фонда фундаментальных исследований №08-01-00889.
В настоящее время существует ряд подходов и инструментов к автоматической генерации тестовых данных сложной структуры. Их обзор приведен в разделе 1.
Авторы занимаются проблемами генерации данных сложной структуры уже на протяжении более чем десяти лет. Полученный опыт показывает, что для генерации небольших наборов тестов, нацеленных на тестирование заданной функциональности ПО, недостаточно использовать лишь такие простейшие настройки генерации, как ограничение длин списков, ограничение глубины дерева, ограничение рекурсии, настройка зависимостей (см., например, [1]) и т.п. Используя подобный спектр настроек, возможно лишь в некоторой степени сократить количество генерируемых тестов. Однако, заставить генератор сгенерировать тесты некоторой специфической структуры (см. пример в разделе 2), используя такие простейшие настройки, практически невозможно.
В настоящей статье мы описываем подход к автоматической генерации тестовых данных сложной структуры, основанный на использова-
нии абстрактных моделей. Ключевая идея подхода состоит в том, чтобы с помощью небольших абстрактных моделей, выраженных в подходящих математических терминах (таких, как разного рода графы, числовые последовательности и т.д.) отражать различные интересные срезы1 структуры генерируемых тестов (см. пример в разделе 2). Экземпляры абстрактных моделей генерируются отдельно, после чего строится их отображение в общую конкретную модель тестовых данных. В результате удается получить небольшие множества тестовых данных, нацеленных на тестирование особенностей целевой системы.
Подход базируется на многолетнем опыте ИСП РАН в области разработки тестов для разного рода промышленного ПО, а также на опыте разработки генераторов тестов на основе использования языковых моделей (см. [2-10]). Подход поддерживается инструментом Pinery и применялся в ряде проектов, в том числе в проектах по тестированию промышленных компиляторов языков C/C++ (см. раздел 5), а также генераторов кода по графическим моделям [11].
Статья состоит из введения и шести разделов. В первом разделе представлены близкие работы. Во втором разделе дается мотивация подхода на примере тестирования оптимизаторов в компиляторе языка С. В третьем разделе приводится описание подхода. В четвертом разделе представлена реализация подхода в инструменте Pinery. В пятом разделе описываются результаты применения подхода для тестирования механизма обработки исключений в промышленном компиляторе языка С++ компании Intel. Шестой раздел завершает статью.
1. БЛИЗКИЕ РАБОТЫ
В настоящее время имеется ряд инструментов для автоматической генерации разного рода тестовых данных сложной структуры: для тестирования приложений над базами данных [12, 13], для тестирования обработчиков XML-
1 Мы употребляем слово "срез" (близким к нему является "аспект") для обозначения такой части структуры, которая может пронизывать все компоненты этой структуры. С математической точки зрения, срез структуры является в некотором смысле фактор-структурой.
документов [14, 15] и др. Существенным недостатком этих инструментов является то, что в них предоставляется слишком бедный набор возможностей для настройки процесса генерации. В результате для достижения приемлемого качества тестирования приходится генерировать огромные множества тестовых данных, что ведет к чрезмерным затратам ресурсов как на этапе генерации, так и на этапе запуска тестов.
В подходах, представленных в работах [11, 16, 17], используются грамматики в виде расширенной BNF, снабженные специальными фрагментами программного кода, которые содержат информацию семантического характера: разного рода вспомогательные вычисления и проверки условий. Такое представление семантики в виде произвольного программного кода, разбросанного во многих разных местах описания, приводит к высокой трудоемкости сопровождения входных данных генератора.
В статье [18] описан основанный на грамматиках генератор DGL, который в первую очередь предназначен для генерации тестов на случайной основе. Генерация регулируется путем присвоения продукциям некоторых значений весов. Кроме того, имеется возможность вводить вспомогательные вычисления, а также устраивать систематическую итерацию атрибутов и альтернатив.
Все перечисленные выше подходы нацелены на то, чтобы сгенерировать какие-нибудь тестовые данные, удовлетворяющие предоставленному описанию. Однако в них не рассматриваются какие бы то ни было критерии полноты получаемых наборов тестовых данных.
В статьях [19-21] описываются подходы к автоматической генерации тестов для семантических анализаторов, основанные на спецификации семантики в виде атрибутных грамматик [22]. Другой подход [8, 23] к этой задаче использует спецификации в виде ASM [24]. Авторы этих подходов рассматривают различные критерии тестового покрытия для семантических анализаторов и описывают соответствующие автоматические генераторы тестов, которые в общих чертах работают так: сперва генератор создает множество синтаксически корректных предложений, которые затем проверяются на семантическую корректность с по-
мощью интерпретатора атрибутной грамматики или ASM, и все семантически некорректные предложения отбрасываются. Такие генераторы оказываются чрезвычайно ресурсоемкими: как показывает практика, для генерации 3000 семантически корректных тестов требуется предварительно сгенерировать порядка 3000000 синтаксически корректных тестов.
В работе [25] описан генератор тестов Korat, который использует спецификацию тестовых данных в виде java-метода, проверяющего корректность структуры данных. Кроме того, генератору требуется предоставить набор параметров, отвечающих за то, чтобы множество генерируемых данных было конечным.
В статье [26] описан основанный на грамматиках генератор тестов Geno. Этот генератор имеет ряд простых механизмов настройки генерации, таких, как ограничение длин списков, ограничение глубины дерева, ограничение глубины рекурсии, задание комбинатора и т.п.
Общим недостатком всех перечисленных выше подходов является то, что в них отсутствует возможность тонкой настройки генератора для построения тестов, нацеленных на тестирование некоторого заданного аспекта функциональности целевого ПО. Имеющиеся возможности позволяют лишь тем или иным образом уменьшить количество генерируемых тестов и избежать комбинаторного взрыва.
В работе [16] представлен метод для автоматического тестирования ПО, осуществляющего рефакторинг программного кода. Для генерации тестов, нацеленных на тестирование определенного вида рефакторинга, требуется разработать соответствующий генератор с использованием библиотеки ASTGen, созданной авторами метода.
В предыдущих работах авторов [9, 27] описан метод ОТК для тестирования оптимизирующих компиляторов на основе моделей. Метод описывает способ построения модели по абстрактному описанию алгоритма оптимизации, выраженного на естественном языке. Для генерации тестов на основе построенной модели требуется разработать определенные компоненты генератора. Метод ОТК снабжен одноименным инструментом, который предоставляет поддержку для формального описания модели данных, а
также для разработки всех требующихся компонентов генератора тестов.
Главным достоинством подходов, использующих ASTGen и ОТК, является следующее: поскольку генераторы тестовых данных фактически разрабатываются вручную, их довольно легко нацелить на генерацию данных для тестирования требуемого аспекта функциональности целевого ПО (например, определенного вида рефакторинга или определенного оптимизатора). Однако платой за это является высокая трудоемкость сопровождения каждого конкретного генератора: часто для модернизации имеющегося генератора с тем, чтобы генерируемые данные обладали некоторым дополнительным свойством, требуется заново разработать порядка половины кода генератора.
Итак, основными недостатками существующих в настоящее время подходов и генераторов тестовых данных являются следующие (и/или):
- бедный набор возможностей для настройки процесса генерации;
- высокая трудоемкость соп
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.