Возможность автоматизации процесса генерирования тестовых наборов

АННОТАЦИЯ

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

ABSTRACT

Most of the automated correctness-checking systems use test sets consisting of input and output files. These test sets are mostly man-made. This paper studies the feasibility of the automation of the generation of test sets (according to specifications of input and output data).

Введение

Автоматическая проверка решений задач применяется как в учебном процессе, так и на олимпиадах различных уровней. Для задач по программированию такую проверку осуществляют по принципу «черного ящика», используя только исполняемый программный модуль (ИПМ) и тестовый набор, анализ же исходного текста программы не производится. При успешном прохождении тестового набора решение признается правильным.

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

1. Автоматическая проверка правильности работы программ

Существует большое количество систем автоматической проверки (САП) правильности работы программ, однако все они работают по одному и тому же принципу.

Тестовые наборы  состоят из отдельных тестов, каждый тест является парой «входные данные – выходные данные». В олимпиадной практике эти данные записываются в виде отдельных текстовых файлов (input.txt и output.txt), однако в других случаях могут храниться, например, в общей базе данных иного формата.

Для каждого теста, входящего в тестовый набор, САП выполняет следующие действия:

1. Производит запуск проверяемого ИПМ, подставляя во входной поток данные, взятые из входного файла очередного теста.
2. Фиксирует ошибки, возникшие в процессе выполнения ИПМ и повлекшие преждевременную остановку работы программы (переполнение памяти, «деление на ноль», т.п.), а также следит за соблюдением временных ограничений, если таковые прописаны в условии задачи. При превышении лимита времени (его причинами могут быть ожидание ввода с неверного потока входных данных, зацикливание, неэффективный алгоритм, т.п.) выполнение ИПМ прерывается искусственно.
3. Если после регулярного или принудительного завершения работы ИПМ получен файл с выходными данными, то САП производит проверку полученного ответа: либо методом вычисления его допустимости, либо методом сравнения его на совпадение с одним или несколькими эталонными ответами. Выбор метода проверки зависит от типа решения (единственный ответ, один из нескольких верных ответов, все возможные верные ответы, попадание в заданный интервал).
4. Если ответ получен и принято решение о его правильности, САП рапортует об успешном прохождении теста. В противном случае тест считается «проваленным», весь тестовый набор не пройденным, а решение ошибочным.

Тестовый набор считается успешно пройденным лишь тогда, когда все тесты из этого набора были успешно пройдены. Только в этом случае САП признает проверяемый ИПМ правильным решением исходной задачи.

2. Создание тестовых наборов: человеческий фактор

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

Зачастую автором эталонного решения и тестового набора является один и тот же человек (преподаватель, организатор олимпиады, т.п.), причём некоторые тесты из «рабочего» тестового набора, использованного при отладке эталонного решения, затем входят и в итоговый тестовый набор.

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

3. Генерирование и проверка тестовых наборов

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

3.1. Генерирование входных данных

Автоматическая проверка задач по программированию является тестированием по принципу «черного ящика», и потому существенно зависит от полноты покрытия тестами пространства возможных входных данных.

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

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

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

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

При адекватном учете всех классов эквивалентности и граничных условий (напомним, что особые точки из рассмотрения заведомо исключаются), полученный тестовый набор будет максимально полно покрывать пространство допустимых входных данных. Доказательство полноты покрытия в каждом конкретном случае также остаётся «на совести» человека.

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

3.2. Генерирование выходных данных

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

4. Извлечение спецификаций из текста

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

Заключение

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

•  Определение спецификаций форматов входных и выходных данных, дополнительных условий и ограничений
•  Задание разбиения пространства возможных входных данных на классы эквивалентности
•  Генерация входных данных
•  Проверка соответствия формата входных данных заданным спецификациям и ограничениям – для всех тестов из созданного тестового набора
•  Получение выходных данных
•  Проверка соответствия формата выходных данных заданным спецификациям