Тестирование софта - статьи


         

Универсальные покрывающие последовательности


Теперь рассмотрим другой способ интерпретации «как можно более разнообразного» поведения m-слова. Можно считать, что тестируемая система является некоторым небольшим конечным автоматом и строить искомое слово как покрывающее все возможные конечные автоматы с числом состояний, меньшим некоторого k (нужно рассматривать только сильно связные автоматы, в которых все входные стимулы допустимы во всех состояниях, иначе их нельзя покрыть с помощью одного слова, кроме того, остановимся пока на детерминированных автоматах). Нужное k можно выбрать как максимальное, допускающее покрывающее все автоматы слово длины, не большей N.

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

Универсальной покрывающей m-последовательностью или универсальным покрывающим m-словом шага k ? 1  и глубины l ? 0 (universal covering word) назовем m-слово, которое, будучи подано на вход любому детерминированному сильно связному m-регулярному автомату с k состояниями, определит в нем маршрут, содержащий все возможные маршруты длины l данного автомата. При l= 0 считаем маршрутами длины 0 все его состояния. Обозначим множество универсальных покрывающих m-слов шага k и глубины l через UC(m, k, l).

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

Содержание  Назад  Вперед