Test suites derivation for nondeterministic finite state mashines with respect to the separability relation.pdf Поведение многих дискретных систем можно описать моделью с конечным числомпереходов, например моделью конечного автомата. Для детерминированных автоматовметоды построения проверяющих тестов достаточно хорошо развиты. Длянедетерминированных автоматов, в которых одной входной последовательности можетсопоставляться несколько выходных последовательностей, методы построения тестовактивно развиваются, но в основном при тестировании используется предположение«о всех погодных условиях», т. е. предполагается, что есть возможность подавать входнуюпоследовательность, пока не пронаблюдаем все выходные реакции на нее. Такоепредположение перестает быть реалистичным, если при тестировании нет возможностиполностью контролировать проверяемый автомат, что имеет место, например, приудаленном тестировании реализаций телекоммуникационных протоколов. В даннойработе предлагается улучшение метода построения тестов для недетерминированныхавтоматов относительно неразделимости для модели «черного ящика», предложенногов работе [1], в котором не используется ограничение «все погодные условия».Недетерминированным автоматом называется пятерка A = (S, I, O, h, s1), где S -множество состояний с выделенным начальным состоянием s1; I и O - соответственновходной и выходной алфавиты; h С S х I х S х O - отношение переходов - выходов.Обозначим out(s,a) = {в : 3 s' e S [(s ,a ,s ',e ) e h]}.Состояние s' называется i- преемником состояния s, если существует такой выходнойсимвол o e O, что четверка (s ,i,s ',o ) содержится в h. Множество состоянийM' С S называется i- преемником множества состояний M С S , если M' есть множествовсех i- преемников всех состояний множества M .При тестировании проверяются различные отношения соответствия между эталонными проверяемым автоматами.Пусть A и B - полностью определенные автоматы. Состояние t автомата B называетсяредукцией состояния s автомата A (обозначение: t ^ s), если Va e I * [out(t, a) Сout(s,a)]. Если t1 ^ s1, то автомат B называется редукцией автомата A.Состояние s автомата A и состояние t автомата B неразделимы (обозначение: s ~ t),если Va e I *[out(s, a) П out(t, a) = 0]. Если 3a e I * [out(s, a) П out(t, a) = 0], то состоянияs и t разделимы по a (обозначение: s Za t), или просто разделимы (обозначение:s Z t). Автоматы A и B неразделимы, если s1 ~ t1. Если s1 Za t1, то автоматыи B разделимы по a (обозначение: A B), или просто разделимы (обозначение:A Z B ); последовательность a называется разделяющей последовательностью дляавтоматов A и B . Разделяющая последовательность a e I * называется кратчайшей,если любая другая входная последовательность, разделяющая автоматы A и B, некороче а.В работе [2] был предложен алгоритм построения кратчайшей разделяющей последовательностидля автоматов A и B и показано, что если данные автоматы имеютсоответственно не более n и m состояний, то длина кратчайшей разделяющей последовательностибудет не более чем 2nm-1, и данная экспоненциальная оценка являетсядостижимой.Для построения качественных тестов необходима не только формальная модельописания эталонной и проверяемой систем, но и формальное задание модели неисправности.В работе [1] был предложен метод построения полного проверяющего тестаотносительно модели неисправности (A, ~ ,Rm(A)), где область неисправности Rm(A)есть множество всех полностью определенных автоматов с теми же входным и выходнымалфавитами, что и у A, и числом состояний не более m, разделимых с эталономили являющихся редукциями эталона, где m - целое положительное число. Отношениеконформности ~ предполагает, что полный проверяющий тест обнаружит всякийавтомат из области неисправности Rm(A), разделимый с эталоном.Метод [1] основан на построении разделяющей последовательности для двух автоматов,и при формулировке условия усечения дерева используется экспоненциальнаяоценка длины разделяющей последовательности. Однако этот метод не доставляеткратчайшего теста, поэтому он был модифицирован путем уточнения условия усечениядерева преемников. Ниже приводится модифицированный алгоритм.Алгоритм 1. Построение полного проверяющего теста относительно модели неисправности(A, Rm(A)).Вход: Полностью определенный автомат A и верхняя граница m числа состояний автоматовиз области неисправности Rm(A).Выход: Полный проверяющий тест TS относительно модели неисправности(A, ~,Rm(A)).Ш!аг 1. Построим усеченное дерево преемников автомата спецификации A. Корнемдерева на нулевом уровне является начальное состояние s1 автомата A; вершины деревапомечены подмножествами состояний автомата A. Пусть уже построены j уровнейдерева, j ^ 0. Для заданной нетерминальной вершины j -го уровня, помеченной подмножествомсостояний K , и для заданного входного символа i в дереве есть ребра,помеченные символомi, в вершину, помеченную i-преемниками подмножества K . Текущаявершина Current на k-м уровне, k > 0, помеченная подмножеством K состоянийиз множества S , объявляется листом дерева, если выполняется любое из перечисленныхусловий усечения, т. е. путь из корня в вершину Current содержит:- 2lKl-m вершин, помеченных подмножествами множества K , если s1 Е K ;- 2|K|-m-1 + 1 вершин, помеченных подмножествами множества K , если s1 Е K ;- 2(|K|-|Pl)^m + n вершин, помеченных подмножествами множества K , если s1 Е K илиs1 Е K и s1 Е Р ;- 2(|K|-|P|)^m-1 +n+1 вершин, помеченных подмножествами множества K , если s1 Е Kи s1 Е Р ,где Р - это такое подмножество состояний из множества K , что до некоторого /-гоуровня (/ < k) перебраны все возможные подмножества Р , а n - это количество вершинна данном пути, помеченных подмножествами K , содержащими подмножества Р ,которые находятся на уровнях не ниже /-го уровня дерева (если Р = 0 , то n = 0).Множество Р строится итеративно:1) P = 0 ;2) P = P U Pj для каждого подмножества Pj множества K , такого, что Pj П P = Q ипуть из корня в вершину Current содержит (2(|Pj|-|Q|)^m - 1) вершин, помеченныхподмножествами Pj, если s1 e Pj или s1 e Q (для Q = 0 ), либо (2(|PjHQ|)^m-1)вершин в случае s1 e Pj.Ш!аг 2. Включаем в TS каждую входную последовательность, которая помечает путьиз корня к листу в усеченном дереве.Построенный согласно алгоритму 1 тест также будет полным относительно моделинеисправности (A, ~ ,Rm(A)), но при этом в большинстве случаев менее избыточным,что доказано теоретически.

Скачать электронную версию публикации