Модификация метода построения тестов для конечных автоматов относительно неразделимости

Состояние t автомата B называется редукцией состояния s автомата A (обозначение: t £ s), если " a Î I* [ out(t, a) Í out(s, a) ], т.е. если для любой входной последовательности множество выходных последовательностей автомата B содержится во множестве выходных последовательностей автомата A. Если t1 £ s1, то автомат B называется редукциейавтомата A.

Состояние s

автомата A и состояние t автомата B неразделимы (обозначение: s ~ t), если " a Î I* [ out(s, a) Ç out(t, a) ¹ Æ]. Если $ a Î I* [ out(s, a) Ç out(t, a) = Æ], то состояния s и t разделимы по a (обозначение: s ≁ t), или просто разделимы (обозначение: s ≁ t). Автоматы A и B неразделимы, если s1 ~ t1. Если s1 ≁ t1, то автоматы A и B разделимы по a (обозначение: A ≁ B), или просто разделимы (обозначение: A ≁ B); последовательность a называется разделяющей последовательностью автоматов A и B. Таким образом, автоматы разделимы, если существует входная последовательность, для которой множества выходных последовательностей автоматов не пересекаются. Разделяющая последовательность a Î I* называется кратчайшей, если любая другая входная последовательность, разделяющая автоматы A и B, не короче a. Если автоматы неразделимы, то для любой входной последовательности множества выходных последовательностей автоматов пересекаются.

1.2 Построение разделяющей последовательности

Рассмотрим алгоритм построения разделяющей последовательности, предложенный в работе [4].

Алгоритм 1. Построение разделяющей последовательности для автоматов A и B

Вход: Автоматы A и B с входным алфавитом I и выходным алфавитом O

Выход: Кратчайшая разделяющая последовательность для автоматов A и B (если существует)

Шаг 1. Построить A Ç B. Если автомат A Ç B полностью определенный, то автоматы A и B неразделимы. КОНЕЦ.

Шаг 2. Построить усеченное дерево преемников автомата A Ç B. Корень дерева (0-й уровень дерева) – начальное состояние пересечения; вершины дерева помечены подмножествами состояний пересечения. Пусть уже построены k уровней дерева, k ³ 0, для заданной промежуточной вершины k-го уровня, которая помечена подмножеством состояний пересечения P и для заданного входного символа i, в дереве есть ребро, помеченное i, в вершину, помеченную подмножеством всех i-преемников состояний подмножества P. Текущая вершина Current на k-м уровне, помеченная подмножеством состояний P, объявляется терминальной вершиной, если выполняется одно из следующих условий:

1) Существует такой входной символ i, что множество i-преемников подмножества P – пустое множество;

2) Существует вершина на j-м уровне, j < k, помеченная подмножеством состояний R со следующим свойством: для всякого состояния (s',t') Î R найдется такое состояние (s,t) Î P, что выполняется (s',t') £ (s,t).

Шаг 3. Если ни один путь в усеченном дереве преемников, построенном на Шаге 2, ни усекается согласно условию 1, то автоматы A и B неразделимы. КОНЕЦ. Если есть терминальная вершина Leaf, помеченная подмножеством состояний P таким, что для некоторого входного символа i всякое состояние подмножества P не имеет i-преемников, то последовательность ai, где a помечает путь от корня к терминальной вершине Leaf, является разделяющей последовательностью для автоматов A и B.

Также в работе[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) вершин, помеченных подмножествами множества К.

 Скачать реферат