Алгоритм построения тестового набора

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

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

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

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

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

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

|S| - мощность множества S
Len(t) ? длина теста t, измеряемая в количестве тестовых воздействий
{} ? пустое множество
<> - пустой упорядоченный список

Фиксируем ограничение длины тестов M, которое является параметром данного алгоритма. Полагаем множество непокрытых тестовых ситуаций C:= полный набор построенных ранее тестовых ситуаций, множество доступных тестов T:= полный набор ранее построенных тестов, а тестовый набор R:=<>. Тестовый набор строится в две итерации: на первой рассматриваются только тесты с длиной, не превышающей M, а на второй рассматриваются все оставшиеся тесты. На каждой итерации применяется следующий «жадный» алгоритм:

Для каждого теста t из T вычисляем Cov(t):= множество тестовых ситуаций из C, покрываемых им. Если Cov(t)={}, то удаляем t из T.
Перебираем в произвольном порядке все тесты t из всего множества T на второй итерации, и только те тесты, длина которых не превышает M, на первой. Если перебираемое множество пусто, то завершаем текущую итерацию. Ищем среди перебираемых тестов лучший следующим образом:
1. Первый встреченный в ходе перебора тест объявляем лучшим.
2. Каждый следующий тест в ходе перебора сравниваем с текущим лучшим по следующим критериям сравнения, по порядку:
  1. если Len(t1) ≤ M и Len(t2) > M, то t1 лучше;
  2. если тесты t1 и t2 оба укладываются в ограничения по длине и при этом |Cov(t1)| > |Cov(t2)|, то t1 лучше;
  3. если |Cov(t1)| ≥ |Cov(t2)| и Len(t1) < Len(t2), то t1 лучше;
  4. если |Cov(t1)| > |Cov(t2)| и Len(t1) ≤ Len(t2), то t1 лучше;
  5. если оба теста t1 и t2 не укладываются в ограничения по длине и (Len(t1 - Len(t2))*P < (|Cov(t1)|-|Cov(t2)|), где P ? параметр алгоритма, то t1 лучше.
3. Если проверки 2.2.1?2.2.5 показывают, что проверяемый тест лучше предыдущего лучшего, то объявляем лучшим его, и далее сравниваем другие перебираемые тесты уже с ним.
  
  Если проверяемый тест признан хуже или ни одна проверка не выносит вердикт, что один тест лучше другого, то продолжаем считать лучшим тот же тест, что и раньше.
Добавляем найденный лучший тест t в конец списка R и удаляем из множества непокрытых тестовых ситуаций C все элементы множества Cov(t).
Переходим к шагу 1.

Правило сравнения 2.2.1 гарантирует, что в первую очередь все возможные тестовые ситуации будут покрываться тестами с длиной, не превышающей максимальную. Правило 2.2.2 выбирает тесты с максимально возможным (в пределах ограничения длины) тестовым покрытием ? в большинстве случаев эта эвристика позволяет уменьшить суммарную длину тестов в наборе за счёт уменьшения их количества. Правила 2.2.3 и 3.2.4 отдают предпочтение тестам, улучшающим покрытие или длину и не ухудшающим притом другую из этих двух характеристик. Согласно правилу 2.2.5 из двух тестов, превышающих максимальную длину, один предпочтительнее другого, если увеличение длины компенсируется (с учётом весового параметра P) увеличением покрытия. Поскольку алгоритм эвристический, и в нём используется перебор по неупорядоченному множеству, в общем случае результаты его работы не детерминированы: при разных запусках на одних и тех же данных возможна генерация различных тестовых наборов; однако в большинстве случаев сгенерированные таким образом наборы имеют одинаковые метрики. Для настройки алгоритма используются параметры M и P. M: задаёт максимальную длину тестов генерируемого набора, превышение которой допускается только для покрытия недостижимых иными способами тестовых ситуаций. Допустимые значения: целое положительное число или +∞. P: задаёт вес превышения максимальной длины тестов по отношению к повышению покрытия. При больших значениях параметра алгоритм в первую очередь выбирает из тестов, превышающих максимальную длину и добавляющих хотя бы какое-то тестовое покрытие, самые короткие, что позволяет уменьшить максимальную длину тестов, но может приводить к существенному увеличению суммарной сложности тестового набора; при малых значениях алгоритм в первую очередь выбирает тесты, покрывающие большее количество тестовых ситуаций, что позволяет минимизировать суммарную сложность тестового набора за счёт добавления в него очень длинных тестов.Допустимые значения: неотрицательные числа (можно нецелые). Оптимальные значения обоих параметров зависят от размера и структуры графа состояний документа, от требований к тестовому покрытию и от возможностей тестировщиков исполнять длинные тесты. В ходе апробации алгоритма установлено, что в большинстве случаев оптимальное значение для параметра M немного превосходит длину самого длинного возможного в графе маршрута без циклов, ведущего из начального состояния в конечное, а для параметра P лежит в диапазоне [0; 2].

Содержание раздела