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

2010

ВВЕДЕНИЕ

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

1. Основные определения и обозначения

1.1 Конечные автоматы и отношения между ними

Автоматом называется пятерка A = (S, I, O, h, s_>1>), где S  множество состояний с выделенным начальным состоянием s_>1>, I и O  соответственно входной и выходной алфавиты, h  S  I  S  O  отношение переходов выходов. Элементами множества h являются четверки вида (s, i, s, o), называемые переходами; при этом говорят, что автомат может перейти из состояния s  S под действием входного символа i  I в состояние s S с выдачей выходного символа o  O, если четверка (s, i, s, o) содержится в h.

В случае, когда каждой паре вход-состояние соответствует не более одного перехода, автомат называется детерминированным, а в противном случае – недетерминированным (нд-автомат).

Рисунок 1 – Недетерминированный автомат A (а) и детерминированный автомат B (b)

Обозначим out(s, ) = {:  sS [(s, , s, )  h]}, т. е. out(s, ) есть множество выходных реакций автомата в состоянии s на входную последовательность .

Состояние s называется i-преемником состояния s, если существует такой выходной символ o  O, что четверка (s, i, s, o) содержится в h. Множество состояний M   S называется i-преемником множества состояний M  S, если M  есть множество всех i-преемников всех состояний множества M.

Если для любых (s, i, o)  S  I  O в нд-автомате A существует не более одного перехода из состояния s под действием входного символа i с выходным символом o, то говорят, что нд-автомат A является наблюдаемым. Если для каждой пары (s, i)  S  I существует хотя бы одна пара (s, o)  S  O, такая что (s, i, s, o)  h, то нд-автомат A называется полностью определенным. В противном случае автомат называется частично определенным или частичным.

Автомат A = (S, I, O, h, s_>1>) называется инициальным, если в множестве состояний S выделено начальное состояние s_>1>.

Говорят, что состояние s' достижимо из состояния s в автомате A, если существует входная последовательность, которая переводит автомат A из состояния s в состояние s'. Автомат называется связным, если любое его состояние достижимо из начального состояния[3].

Пусть A = (S, I, O, h, s_>1>), B = (T, I, O, g, t_>1>) – полностью определенные автоматы. Автомат B называется подавтоматом автомата A, если T  S, t_>1>= s_>1>и g  h. Пересечением автоматов A = (S, I, O, h, s_>1>) и B = (T, I, O, g, t_>1>) (обозначение A  B), назовем максимальный связный подавтомат инициального автомата (ST, I, O, H, s_>1>t_>1>), в котором отношение переходов H определено следующим образом: (st, i, st, o)  H  [(s, i, s, o)  h  (t, i, t, o)  g]. Пересечение автоматов описывает общую часть поведения автоматов A и B и используется для построения входных последовательностей, различающих эти автоматы.

На рисунке 2 представлены автоматы A, B.

2/1

3/0

2/0

4/1

3/1

1/0

2/1

3/0

2/1

2/0

4/1

2/0

2/1

1/0

1/1

1/0

2/1

3/0

2/1

Рисунок 2 – Автоматы A, B

На рисунке 3 представлен автомат A∩B.

AB

1,1

3,2

2,2

2,4

3,2/0

2,4/1

2,2/0

—

1,1/0

—

2,2/1

Рисунок 3 – Автомат AB

При тестировании проверяются различные отношения соответствия между эталонным и проверяемым автоматами.

Пусть A и B – полностью определенные автоматы. Говорят, что состояние s автомата A и состояние t автомата B эквивалентны (обозначение: s  t), если    I* [ out(s, ) = out(t, ) ]. Иными словами, множество реакций автомата A в состоянии s на любую входную последовательность α совпадает с множеством реакций автомата B в состоянии t на данную входную последовательность α. В противном случае, состояния s и t не эквивалентны [2].

Автоматы A и B называются эквивалентными (обозначение: A  B), если эквивалентны их начальные состояния, т.е. s_>1>  t_>1>. В противном случае, автоматы A и B не эквивалентны. Таким образом, по определению, два автомата эквивалентны, если и только если множества их выходных реакций на каждую входную последовательность совпадают.

Состояние t автомата B называется редукцией состояния s автомата A (обозначение: t  s), если    I* [ out(t, )  out(s, ) ], т.е. если для любой входной последовательности множество выходных последовательностей автомата B содержится во множестве выходных последовательностей автомата A. Если t_>1>  s_>1>, то автомат B называется редукцией автомата A.

Состояние s автомата A и состояние t автомата B неразделимы (обозначение: s ~ t), если    I* [ out(s, )  out(t, )  ]. Если    I* [ out(s, )  out(t, ) = ], то состояния s и t разделимы по  (обозначение: s ≁_>> t), или просто разделимы (обозначение: s ≁ t). Автоматы A и B неразделимы, если s_>1> ~ t_>1>. Если s_>1> ≁_>> t_>1>, то автоматы A и B разделимы по  (обозначение: A ≁_>> B), или просто разделимы (обозначение: A ≁ B); последовательность  называется разделяющей последовательностью автоматов A и B. Таким образом, автоматы разделимы, если существует входная последовательность, для которой множества выходных последовательностей автоматов не пересекаются. Разделяющая последовательность   I* называется кратчайшей, если любая другая входная последовательность, разделяющая автоматы A и B, не короче . Если автоматы неразделимы, то для любой входной последовательности множества выходных последовательностей автоматов пересекаются.

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, объявляется терминальной вершиной, если выполняется одно из следующих условий:

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

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

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

Также в работе [4] показано, что если автоматы A и B имеют соответственно не более n и m состояний, то длина кратчайшей разделяющей последовательности будет не более чем 2^nm⁻¹, и данная экспоненциальная оценка является достижимой.

Теорема 1. Для заданных целых чисел n и m, n  1, m  1, всегда найдутся разделимые автоматы A и B с числом состояний n и m, соответственно, такие что для них кратчайшая разделяющая последовательность имеет длину 2^nm⁻¹.

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. Корнем дерева на нулевом уровне является начальное состояние s_>0> автомата S; вершины дерева помечены подмножествами состояний автомата S . Пусть уже построены j уровней дерева, j  0. Для заданной нетерминальной вершины j^го уровня, помеченной подмножеством состояний К, и для заданного входного символа i, в дереве есть ребра, помеченные символом i, в вершину, помеченную i-преемниками подмножества К. Текущая вершина Current на k^м уровне, k > 0, помеченная подмножеством К состояний из множества S, объявляется листом дерева, если путь из корня в эту вершину содержит 2^|^K^|^^m вершин, помеченных подмножествами множества К, и начальное состояние s_>0> не содержится в К. Если начальное состояние принадлежит К, то вершина Current объявляется листом, если путь из корня в эту вершину покрывает (2^|^K^|^^m^-1+1) вершин, помеченных подмножествами множества К.

Шаг 2. Включаем в TS каждую входную последовательность, которая помечает путь из корня к листу в усеченном дереве.

В качестве примера рассмотрим спецификацию S, представленную на рисунке 5, и построим полный проверяющий тест относительно модели неисправности <S, ≁_>>>.

a/0,1,2,3

a/1,2

b/1,2

a/0

b/3

Рисунок 5 - Автомат S

На втором шаге текущая вершина, помеченная состоянием a, объявляется листом, если путь из корня в эту вершину покрывает (2^m⁻¹+ 1) = 3 вершин, помеченных a. Текущая вершина, помеченная состоянием b, объявляется листом, если путь из корня в эту вершину покрывает 2^m = 4 вершин, помеченных b. Наконец, текущая вершина, помеченная подмножеством {a, b}, объявляется листом, если путь из корня в эту вершину покрывает (2²^m⁻¹+ 1) = 9 вершин, помеченных a, b или {a, b}.Полученное по данному алгоритму усеченное дерево преемников представлено на рисунке 6. Суммарная длина полного проверяющего теста составляет 277 символов.

Рисунок 6 – Усеченное дерево преемников, построенное по алгоритму 2

3. Улучшение метода построения полного проверяющего теста относительно модели неисправности <S, (,≁), _>m>>

3.1 Исследование условий усечения дерева

Алгоритм 2 не доставляет кратчайшего теста. Для иллюстрации этого факта рассмотрим тестовую последовательность xyyyyyyy из предыдущего примера, которой в усеченном дереве преемников (рис. 6) соответствует путь a_>x>a_>y>b_>y>{a,b}_>y>{a,b}_>y>{a,b}_>y>{a,b}_>y>{a,b}_>y>{a,b}. Прямым перебором можно убедиться, что если автомат-реализация имеет состояния 1 и 2, тогда соответствующий путь в усеченном дереве Tree_>S>_>>_>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/0 b/1	a,b/1	a/1
y	a,b/0	c/1	b/1 c/0
z	b/1	b/0	a/0

Рисунок 7 - Автомат S

Для подмножества состояний {a, b, c} для усечения дерева по алгоритму 2 необходимо, чтобы путь из корня дерева в листовую вершину покрывал 2³^m^-1+1=33 вершины, помеченные подмножествами этого множества. Однако, т.к. на левом пути дерева, представленного на рисунке 8, сначала встречается 8 вершин, помеченных подмножествами {a, b}, а именно такое число вариантов обеспечивает перебор всех подмножеств {a1, a2, b1, b2} в дереве Tree_>S>_>>_>T>, то далее на данном пути подмножество {a, b} из рассмотрения исключается. Таким образом, соответствующий путь в дереве Tree_>S>_>>_>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 – Часть усеченного дерева преемников

Естественно, сокращение тестовой последовательности можно также обобщить и для случая, когда на рассматриваемом пути дерева перебираются все подмножества для нескольких подмножеств P_>i> множества K, в том числе и в случае, когда эти подмножества пересекаются. Данный случай иллюстрирует правый путь дерева, изображенного на рисунке 8. На этом пути дерева сначала перебираются все возможные подмножества для P_>1>={b}. Для пересекающегося с P_>1> множества P_>2>={a, b} теперь достаточно всего трех вершин, помеченных подмножествами P_>2>, чтобы были перебраны все возможные подмножества P_>2>. И соответствующий путь в дереве Tree_>S>_>>_>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), уточнив условия усечения дерева преемников.

3.2 Модифицированный метод построения полного проверяющего теста относительно модели неисправности <S, (,≁), _>m>>

Алгоритм 3. Построение полного проверяющего теста относительно модели неисправности <S, (,≁),_>m> >

Вход: Полностью определенный автомат S и верхняя граница m числа состояний любой реализации S

Выход: Полный проверяющий тест TS относительно модели неисправности <S, (,≁),_>m> >

2^(|^K^|-|^P^|)^^m+n вершин, помеченных подмножествами множества К, если s_>0>  K или s_>0>  K и s_>0>  P;

2^(|^K^|-|^P^|)^^m^-1+n+1 вершин, помеченных подмножествами множества К, если s_>0>  K и s_>0>  P;

где P – это такое подмножество состояний из множества K, что до некоторого l^го уровня (l < k) перебраны все возможные подмножества P, а n – это количество вершин на данном пути, помеченных подмножествами К, содержащими подмножества P, которые находятся на уровнях не ниже l^го уровня дерева (если P = , то n = 0). Множество P строится итеративно:

P = ;

P = P  P_>i> для каждого подмножества P_>i> множества K, для которого путь из корня в вершину Current содержит (2^|^Pⁱ^|^^m-1) вершин, помеченных подмножествами P_>i> (или (2^|^Pⁱ^|^^m^-1) вершин в случае s_>0>  P_>i>);

P = P  P_>j> для всех существующих пар P_>i>  P и P_>j>  P (P_>j>  K) таких, что P_>i>  P_>j> = Q и путь из корня в вершину Current содержит (2^(|^Pj^|-|^Q^|)^^m-1) вершин, помеченных подмножествами P_>j>, если s_>0>  P_>j> или s_>0>  Q, либо (2^(|^Pj^|-|^Q^|)^^m^-1) вершин в случае s_>0>  P_>j>.

Теорема 2.

Для заданного эталонного автомата S и целого числа m алгоритм 3 доставляет полный проверяющий тест относительно модели неисправности <S, (,≁),_>m> >.

Доказательство.

Рассмотрим самый общий случай – подмножество K состояний из множества S, и начальное состояние s_>0>  K. Согласно алгоритму 1, вершина усеченного дерева преемников Tree_>S>, помеченная подмножеством K, объявляется листом дерева, если путь из корня в эту вершину содержит 2^|^K^|^^m вершин, помеченных подмножествами множества К. Это соответствует перебору всех возможных подмножеств К в усеченном дереве приемников Tree_>S>_>>_>T>, построенному по пересечению эталонного автомата S и некоторой реализации T, где К – это подмножество состояний пересечения S  T таких, что первый символ каждой пары из К содержится в К.

Предположим, что существует такое подмножество состояний P из множества K, что до некоторого l^го уровня дерева на пути из корня в вершину Current перебраны все возможные подмножества P. Множество P строится итеративно следующим образом:

Шаг 1. P = .

Шаг 2. P = P  P_>i> для каждого подмножества P_>i> множества K, для которого путь из корня в вершину Current содержит (2^|^Pⁱ^|^^m-1) вершин, помеченных подмножествами P_>i>. Добавление каждого такого P_>i> в множество P справедливо, т.к. если путь содержит указанное количество повторов, то этим перебираются все возможные варианты подмножеств P_>i>.

Шаг 3. P = P  P_>j> для всех существующих пар P_>i>  P и P_>j>  P (P_>j>  K) таких, что P_>i>  P_>j> = Q и путь из корня в вершину Current содержит (2^(|^Pj^|-|^Q^|)^^m-1) вершин, помеченных подмножествами P_>j>. В данном случае P_>i> уже было добавлено в P на шаге 2, и для него уже встретилось (2^|^Pⁱ^|^^m-1) вершин, помеченных подмножествами P_>i>. Следовательно, для P_>j>, пересекающегося с P_>i>, на данном пути дерева уже точно содержится (2^|^Q^|^^m-1) вершин, помеченных подмножествами P_>j>, значит для того, чтобы были перебраны все варианты подмножеств P_>j>, достаточно встретить еще (2^(|^Pj^|-|^Q^|)^^m-1) вершин.

Для построенного таким образом P (если P  ) на соответствующем пути в дереве Tree_>S>_>>_>T>_>>будут перебраны все возможные подмножества P (P – это подмножество состояний S  T таких, что первый символ каждой пары из P содержится в P). Значит, далее на данном пути в дереве Tree_>S>_>>_>T> из рассмотрения можно исключить вершины, помеченные подмножествами К, которые содержат подмножества P – поэтому рассматриваемых вершин, помеченных подмножествами K, не содержащих подмножеств P, будет 2^(|^K^|-|^P^|)^^m . Но также необходимо учесть все n вершин, помеченных подмножествами К, содержащими подмножества P, которые встретились на рассматриваемом пути в дереве Tree_>S> выше, чем l_>й> уровень, т.к. из данных вершин подмножества P исключать не можем. Следовательно, количество вершин, помеченных подмножествами K, для усечения дерева в таком случае составляет 2^(|^K^|-|^P^|)^^m+n вершин.

Далее рассмотрим случай, когда s_>0>  K, но s_>0> не принадлежит множеству P. По алгоритму 1 для случая s_>0>  K вершина, помеченная подмножеством K, объявляется листом, если путь из корня в данную вершину содержит (2^|^K^|^^m^-1+1) вершин, помеченных подмножествами множества K. Если же на данном пути для каждого P_>i>_>> P встретилось, как и в предыдущем случае, необходимое число вершин, помеченных подмножествами P_>i>, то листовой будет являться вершина, путь из корня в которую содержит 2^(|^K^|-|^P^|)^^m^-1+n+1 вершин, помеченных подмножествами K.

Если s_>0>  K и s_>0>  P, т.е. s_>0> принадлежит одному из подмножеств P_>j>  P, то необходимо, чтобы на рассматриваемом пути дерева встретилось (2^|^Pj^|^^m^-1) вершин, помеченных подмножествами P_>j>, если P_>j> добавляется к P на шаге 2 построения множества P, либо (2^(|^Pj^|-|^Q^|)^^m^-1) вершин – если на шаге 3. Для остальных подмножеств P_>i> из P требуется встретить такое же количество вершин, как и в случае 1. Тогда можно исключить подмножества P из вершин, помеченных подмножествами K начиная с l_>го> уровня, и вершина, помеченная подмножеством K, объявляется листом, если путь из корня в данную вершину содержит 2^(|^K^|-|^P^|)^^m+n вершин, помеченных подмножествами множества K.

Если для данного пути дерева P = , то |P| = 0, n = 0 и пользуемся алгоритмом 2.

На рисунке 9 представлено усеченное дерево преемников для спецификации, изображенной на рис. 5, построенное согласно алгоритму 3. Суммарная длина полного проверяющего теста в этом случае составляет 200 символов, что на 77 символов меньше, чем для алгоритма 2.

Рисунок 9 – Усеченное дерево преемников, построенное по алгоритму 3

ЗАКЛЮЧЕНИЕ

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

ЛИТЕРАТУРА

Natalia Shabaldina, Khaled El-Fakih, Nina Yevtushenko. Testing Nondeterministic Finite State Machines With Respect to the Separability Relation. Lecture Notes in Computer Science, 2007(4581), pp. 305-318.

Шабалдина Н.В., Евтушенко Н.В. Построение тестов для конечных автоматов относительно неразделимости. Вестник ТГУ. Приложение. Серия "Математика. Кибернетика. Информатика". 2007. № 23. С. 287– 290.

Евтушенко Н.В., Петренко А.Ф., Ветрова М.В. Недетерминированные автоматы: анализ и синтез. Ч. 1. Отношения и операции. – Томск: Томский государственный университет, 2006. – 142 с.

Евтушенко Н.В., Спицина Н.В. О верхней оценке длины разделяющей последовательности

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