ПРОГРАММИРОВАНИЕ, 2008, № 6, с. 24-34
■ ТЕСТИРОВАНИЕ, ВЕРИФИКАЦИЯ И ВАЛИДАЦИЯ ПРОГРАММ
УДК 004.92+004.94
К СИНТЕЗУ УСЛОВНЫХ ТЕСТОВ ДЛЯ НЕДЕТЕРМИНИРОВАННЫХ АВТОМАТОВ*
© 2008 г. М. JT. Громов, Н. В. Евтушенко, А. В. Коломеец
Томский государственный университет Томск
E-mail: gromov@sibmail.com, ninayevtushenko@yahoo.com, admiral@sibmail.com
Поступила в редакцию 23.04.2008 г.
В данной работе мы предлагаем метод синтеза условных тестов с гарантированной полнотой для проверки функционирования дискретных систем, поведение которых описано недетерминированными автоматами. В отличие от других известных методов, мы не представляем полный тест в виде дерева, а перечисляем тестовые примеры один за другим, проверяя функционирование тестируемого автомата на каждом тестовом примере. Полный тест обнаруживает все неисправные системы, r-различимые с эталонной системой. Кроме того, тест обнаруживает также и другие неисправные системы, которые содержат трассы, которых нет в эталонном автомате; однако обнаружение всех таких систем, r-совместимых с эталонным автоматом, не гарантируется.
ВВЕДЕНИЕ
В последнее время большое внимание уделяется тестированию протокольных, в том числе программных, реализаций, поведение которых описывается недетерминированными автоматами [1-14]. Причины появления недетерминизма в спецификациях и реализациях, вообще говоря, различные (см., например, [4, 6, 10, 13]); среди них можно выделить возможность различных опций при реализации, уровень абстракции описания, невозможность полной управляемости и наблюдаемости для реализации и т.д. В случае, когда поведение спецификации и реализации описывается недетерминированными автоматами, обычно требуется, чтобы конформная реализация была квази-редукцией спецификации. Под квази-редукцией эталонного автомата [12] понимается полностью определенный автомат, множество трасс которого для каждой входной последовательности, допустимой в эталонном автомате, содержится в эталонном автомате.
* Работа частично поддержана грантом Российского фонда фундаментальных исследований №07-08-12243.
Одной из основных проблем при синтезе тестов с гарантированной полнотой при тестировании недетерминированных реализаций является тот факт, что в общем случае недетерминированный (проверяемый) автомат может реагировать различными выходными последовательностями на одну и ту же входную последовательность. Поэтому обычно при тестировании реализаций с недетерминированным поведением делается допущение о "всех погодных условиях", то есть предполагается, что каждая тестовая входная последовательность подается на реализацию достаточно большое число раз в "различных погодных условиях", и поэтому можно считать, что тестер пронаблюдал все возможные выходные реакции реализации на каждую входную последовательность.
Допущение о "всех погодных условиях" является скорее теоретическим, так как никто не знает, сколько раз достаточно подать входную последовательность, чтобы дать возможность тестеру "увидеть" все выходные реакции реализации. Более того, такому предположению невозможно удовлетворить, если проверяемый автомат является только частично контролируемым, что имеет место, например, при удален-
ном тестировании реализаций телекоммуникационных протоколов. В [15] отмечается, что, если отсутствует предположение о "всех погодных условиях", то единственным отношением между проверяемым и эталонным автоматами, проверку которого можно гарантировать при проведении безусловного эксперимента с проверяемым автоматом, является отношение неразделимости между автоматами, когда реакции двух автоматов на любую входную последовательность пересекаются. В данной работе мы предполагаем, что возможен условный проверяющий эксперимент [1, 2], и соответственно гарантированно можно обнаружить любую реализацию, г-различимую с эталонным автоматом, то есть реализацию, которая не имеет общих квази-редукций с эталонным автоматом. Вообще говоря, при таком тестировании могут быть обнаружены и реализации, г-совместимые с эталонным автоматом, то есть реализации, которые имеют общие квази-редукции с эталонным автоматом, но обнаружение всех таких реализаций проверяющим тестом не гарантируется.
В данной работе мы предлагаем метод построения полного проверяющего теста относительно модели неисправности, в которой эталонный автомат является недетерминированным, область неисправности состоит из конечного числа недетерминированных автоматов, и отношением конформности является отношение г-совместимости между проверяемым и эталонным автоматами. Мы используем понятие (условного или адаптивного) тестового примера [4, 12], и, поскольку число последовательностей в тестовом примере в общем случае экспоненциально зависит от числа состояний различаемых автоматов [16], мы строим тестовый пример как ациклический автомат [12], поведение которого в каждом состоянии определено не более чем для одного входного символа. Мы также отмечаем, что мы не строим множество всех тестовых примеров в виде общего дерева последовательностей, как принято в большинстве публикаций по синтезу проверяющих тестов для недетерминированных автоматов (см., например, [4, 5, 11, 12]), а перечисляем тестовые примеры один за другим, тестируя проверяемый автомат на каждом примере. Мы иллюстрируем предлагаемый подход для случая, когда область не-
исправности есть множество всех подавтоматов специального мутационного автомата.
Структура статьи следующая. В разделе 1 вводятся необходимые определения; в разделе 2 представлены алгоритм построения тестовых примеров и построение полного проверяющего теста относительно множества подавтоматов мутационного автомата. В заключение, как обычно, обсуждаются полученные результаты.
1. ОПРЕДЕЛЕНИЯ И ОБОЗНАЧЕНИЯ
1.1. Недетерминированные автоматы
Недетерминированным автоматом (или далее просто автоматом) S называется пятерка (S, 1,0, hs, so), где S - множество состояний с выделенным начальным состоянием sq> I и О -соответственно входной и выходной алфавиты, hsCSxIxOxS - отношение переходов. Элементами множества hs являются четверки вида (s, i, о, s'), называемые переходами; при этом говорят, что автомат может перейти из состояния s £ S под действием входного символа i £ I в состояние s' G S с выдачей выходного символа о G О (обозначение: s —>■ s'), если четверка (s, i, о, s') содержится в hs- Кроме того, для s G S через ins(s) обозначается множество входных символов i G / таких, что существуют о G О и s' G S со свойством s —s'. Для s G S и i G ins(s) через outs(s,i) обозначается множество выходных символов о £ О таких, что
существует s со свойством s —s .
Если для любых (s, i) G S X / в автомате существует не более одного перехода (s, i, о, s') G £ hs, то автомат называется детерминированным. Если для любых (s,i,o) £ S X / X О в автомате существует не более одного перехода (s, i, о, s') £ hs, то автомат называется наблюдаемым. По определению, любой детерминированный автомат является наблюдаемым. Если для каждой пары (s,i) £ S X / существует хотя бы одна пара (s',o) £ S X О, такая, что (s,i,o,s') £ hs, то автомат называется полностью определенным; в противном случае автомат называется частичным. Обычным образом отношение переходов hs автомата S распространяется на множество I* входных и О* выходных последовательностей. Пусть s, s' £ S,
а = iii2...ik G Г, (3 = ого2...ок G О*. Тогда (s, o¿, [3, s') G hs, если существует последовательность СОСТОЯНИЙ Si = S, S2, . . • , Sjfc, = s' таких, что (si,ii,Oi,si+1) G hs, i = 1,..., к. В этом случае пара а/[3 называется вход-выходной последовательностью или трассой автомата S в состоянии s. Трасса автомата в начальном состоянии называется просто трассой автомата S.
Пусть S = (S,I,O,hs,s0), Т = (T,I,0,hT, ¿o) - автоматы. Автомат Т называется подавтоматом автомата S, если Т С S, to = so и hj С hs- Пересечением автоматов S = (S,I,0, hs,so) и Т = {Т, 1,0 ,hj,to) (обозначение: SП ПГ) называется максимальный связный подавтомат автомата (S X Т, /,0,h, «(/о), в котором (sí, i, о, s'í') G h, если и только если (s, i, о, s') G G hs и (t,i,o,t!) G /гт- Пересечение автоматов описывает общую часть поведения автоматов <5 и Т и используется для построения входных последовательностей, различающих эти автоматы. В следующем утверждении описываются свойства пересечения Sí)T для случая, когда S и Т - наблюдаемые автоматы.
Утверждение 1 [12, 18]. Если S и Т -наблюдаемые автоматы, то пересечение Q = = (Q, 1,0, h,q, soto) автоматов S и Т обладает следующими свойствами.
1. Для любого состояния (s, t) G Q справедливо: íuq{s, t) = ins(s) П inx(t).
2. Для любого состояния (s, t) G Q и ¿ G ins(s,t) справедливо: outq((s,t), i) = = outs(s, i) П outx(t, i).
3. Для любого состояния (s, t) G Q справедливо: TrQ(s,t) = Trs(s) í]TrT(t).
. / 4 i/o , , ,4 ij o .
4. (s,t) —(s ,t), если и только если 8 —у s
г/о .
и t ——^ t .
1.2. Отношение г-различимости
Пусть S = (S, I, О, hs, s0) и Т = (T,I,0,hT, до) _ наблюдаемые, возможно, частичные, автоматы. Состояние s автомата S и состояние t автомата Т называются 1 -г-различимыми, если существует входной символ i G ¿ras(s)fl Пinx(t) такой, что outs(s,i) П outx(t,i) = 0,
то есть множества выходных символов автоматов Т и S в состояниях t и s на входной символ i не пересекаются. Состояния tus называются к-г-различимыми, если они являются (к — 1)-г-различимыми, или для них существует входной символ i G ins(s) П inx(t) такой, что для любого О G OUts(s, i) П OUtx(t, i) состояния s' и t' из переходов (s, i, o, s') G hs и (t, i, o, t') G hj являются (к — 1)-г-различимыми. Состояния t и s являются г-различимыми (обозначение: ф), если они /г-г-различимы для некоторого к. В противном случае состояния называются г-со-вместимыми [4, 11] (обозначение: ~).
Для l-r-различимых состояний s автомата S и t автомата Т входной символ i G ¿ras(s)fl Пinx(t) такой, что outs(s,i) П outx(t,i) = 0, будем называть 1 -различающим входным символом. Для /г-г-различимых, к > 1, состояний s и t, если они не являются (к — 1)-г-различимыми, к-различающим входным символом называется входной символ i G ins(s) П inx(t) так
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.