Модификация метода построения тестов для конечных автоматов относительно неразделимости (стр. 2 из 3)
Также в работе[4] показано, что если автоматы A и B имеют соответственно не более n и m состояний, то длина кратчайшей разделяющей последовательности будет не более чем 2nm−1, и данная экспоненциальная оценка является достижимой.
Теорема 1. Для заданных целых чиселn и m, n³ 1, m³ 1, всегда найдутся разделимые автоматы Aи B с числом состояний n и m, соответственно, такие что для них кратчайшая разделяющая последовательность имеет длину 2nm−1.
1.3 Модель неисправности и проверяющий тест
Для построения качественных тестов необходима не только формальная модель описания эталонной и проверяемой систем, но и формальное задание модели неисправности. Традиционно под моделью неисправности понимают тройку <S, », Â>, в которой S- эталонный автомат, »- отношение конформности, »Î {@, £, ~}. Область неисправности  есть множество автоматов, входной и выходной алфавиты которых совпадают с входным и выходным алфавитом эталонного автомата. Автоматы из множества Âпредставляют все возможные неисправности в соответствующей дискретной системе. Тогда конечное непустое множество TS конечных входных последовательностей называется полным проверяющим тестом относительно модели <S, », Â>, если TS обнаруживает всякий автомат TÎÂ, не конформный эталонному автоматуS.
Для моделей неисправности <S, @, Â> и <S, £, Â>, где S – нд‑эталон, – множество проверяемых нд-автоматов, известны методы построение полных проверяющих тестов для случаев, когда Âесть множество всех автоматов с ограниченным числом состояний или множество всех подавтоматов специального мутационного автомата. Однако, применить на практике эти тесты можно только в случае, если выполняется предположение о "всех погодных условиях", т.е. каждая тестовая последовательность подается на тестируемый автомат до тех пор, пока проверяемый автомат "не покажет" все возможные реакции на эту последовательность. Такое предположение перестает быть реалистичным, если при тестировании нет возможности полностью контролировать проверяемый автомат, что имеет место, например, при удаленном тестировании реализаций телекоммуникационных протоколов.
В данной работе изучен метод построения полного проверяющего теста относительно модели неисправности <S, (£,≁),Âm>, предложенный в работе [1]. Область неисправности Âm содержит все полностью определенные реализации эталона S с теми же входным и выходным алфавитами, что и у S, и числом состояний не более m, где m – целое положительное число. Такую модель неисправности часто называют моделью "черного ящика".
2.Метод построения полного проверяющего теста относительно модели неисправности <S, (£,≁), Âm>
Алгоритм 2. Построение полного проверяющего теста относительно модели неисправности <S, (£,≁),Âm >
Вход: Полностью определенный автомат Sи верхняя граница m числа состояний любой реализации S
Выход: Полный проверяющий тест TS относительно модели неисправности <S, (£,≁),Âm >
Шаг 1. Построим усеченное дерево преемников автомата спецификации S. Корнем дерева на нулевом уровне является начальное состояние s0 автомата S; вершины дерева помечены подмножествами состояний автомата S . Пусть уже построены j уровней дерева, j³ 0. Для заданной нетерминальной вершины jго уровня, помеченной подмножеством состояний К, и для заданного входного символа i, в дереве есть ребра, помеченные символом i, в вершину, помеченную i-преемниками подмножества К. Текущая вершина Current на kм уровне, k > 0, помеченная подмножеством К состояний из множества S, объявляется листом дерева, если путь из корня в эту вершину содержит 2|K|×m вершин, помеченных подмножествами множества К, и начальное состояние s0 не содержится в К. Если начальное состояние принадлежит К, то вершина Current объявляется листом, если путь из корня в эту вершину покрывает (2|K|×m-1+1) вершин, помеченных подмножествами множества К.
Шаг 2. Включаем в TS каждую входную последовательность, которая помечает путь из корня к листу в усеченном дереве.
В качестве примера рассмотрим спецификацию S, представленную на рисунке 5, и построим полный проверяющий тест относительно модели неисправности <S, (£,≁), Â2>.
| S | a | b |
| x | a/0,1,2,3 | a/1,2 |
| y | b/1,2 | a/0b/3 |
Рисунок 5 - Автомат S
На втором шаге текущая вершина, помеченная состоянием a, объявляется листом, если путь из корня в эту вершину покрывает (2m−1 + 1) = 3 вершин, помеченных a. Текущая вершина, помеченная состоянием b, объявляется листом, если путь из корня в эту вершину покрывает 2m= 4 вершин, помеченных b. Наконец, текущая вершина, помеченная подмножеством {a, b}, объявляется листом, если путь из корня в эту вершину покрывает (22m−1 + 1) = 9 вершин, помеченных a, bили {a, b}.Полученное по данному алгоритму усеченное дерево преемников представлено на рисунке 6. Суммарная длина полного проверяющего теста составляет 277 символов.
Рисунок 6 – Усеченное дерево преемников, построенное по алгоритму 2
3. Улучшение метода построения полного проверяющего теста относительно модели неисправности <S, (£,≁), Âm>
3.1 Исследование условий усечения дерева
Алгоритм 2 не доставляет кратчайшего теста. Для иллюстрации этого факта рассмотрим тестовую последовательность xyyyyyyy из предыдущего примера, которой в усеченном дереве преемников (рис. 6) соответствует путь axayby{a,b}y{a,b}y{a,b}y{a,b}y{a,b}y{a,b}. Прямым перебором можно убедиться, что если автомат-реализация имеет состояния 1 и 2, тогда соответствующий путь в усеченном дереве TreeSÇT, построенном по пересечению эталонного автомата и реализации, будет уже усечен после {a1}x{a2}y{b1,b2}y{b1}y{b2}y{a,b}, т.к. для подмножества а были перебраны все варианты и из последующих подмножеств его можно исключить. Таким образом, при уточнении условий усечения дерева данную тестовую последовательность можно сократить на 3 символа.
Сократить тестовую последовательность можно также и в более общем случае, когда на рассматриваемом пути дерева перебраны все возможные варианты для состояний некоторого множества P, являющегося подмножеством множества K. Рассмотрим эталонный автомат S, изображенный на рисунке 7, и m=2.
| S | a | b | c |
| x | a/0b/1 | a,b/1 | a/1 |
| y | a,b/0 | c/1 | b/1c/0 |
| z | b/1 | b/0 | a/0 |
Рисунок 7 - Автомат S
Для подмножества состояний {a, b, c} для усечения дерева по алгоритму 2 необходимо, чтобы путь из корня дерева в листовую вершину покрывал 23m-1+1=33 вершины, помеченные подмножествами этого множества. Однако, т.к. на левом пути дерева, представленного на рисунке 8, сначала встречается 8 вершин, помеченных подмножествами {a, b}, а именно такое число вариантов обеспечивает перебор всех подмножеств {a1, a2, b1, b2} в дереве TreeSÇT, то далее на данном пути подмножество {a, b} из рассмотрения исключается. Таким образом, соответствующий путь в дереве TreeSÇTбудет усечен после {a1}x{a2,b1,b2}x{a2,b1}x{a2,b2}x{a2}x{b1}x{b2}x{b1,b2}y{c1,c2}y{c1}y{c2}y{a,b,c}, и длина тестовой последовательности составляет всего 11 символов.
Рисунок 8 – Часть усеченного дерева преемников
Естественно, сокращение тестовой последовательности можно также обобщить и для случая, когда на рассматриваемом пути дерева перебираются все подмножества для нескольких подмножеств Pi множества K, в том числе и в случае, когда эти подмножества пересекаются. Данный случай иллюстрирует правый путь дерева, изображенного на рисунке 8. На этом пути дерева сначала перебираются все возможные подмножества для P1={b}. Для пересекающегося с P1 множества P2={a,b} теперь достаточно всего трех вершин, помеченных подмножествами P2, чтобы были перебраны все возможные подмножества P2. И соответствующий путь в дереве TreeSÇTусекаетсяпосле {a1}z{b1,b2}z{b1}z{b2}x{a2}y{c1,c2}y{c1}y{c2}y{a,b,c}, а длина тестовой последовательности составляет 8 символов.
Таким образом, можно модифицировать метод построения полного проверяющего теста относительно модели неисправности <S, (£,≁), Âm> (алгоритм 2), уточнив условия усечения дерева преемников.