Асинхронные тестовые сценарии

Генерация тестовых данных для асинхронных систем

В данном разделе мы рассмотрим проблему генерации тестовых данных для асинхронных систем. Решение этой проблемы сильно осложняется большой временной сложностью алгоритмов оценки корректности поведения асинхронных систем. Область применимости этих алгоритмов ограничена асинхронными моделями поведения, состоящими из нескольких десятков взаимодействий.

Одного теста такого размера явно не достаточно для достижения приемлемого качества тестирования. Построение наборов независимых тестов небольшого размера приведет к потере одного из основных достоинств технологии UniTesK - автоматическому построению сложных последовательностей тестовых воздействий.

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

С учетом этого ограничения данный подход позволяет сохранить автоматическое построение сложных последовательностей тестовых воздействий, несмотря на ограниченную применимость алгоритма оценки корректности поведения.

В последующих разделах мы рассмотрим вопрос построения тестов для систем с асинхронным интерфейсом более формально.

Взаимодействующие автоматы

Определение 13.

Взаимодействующим автоматом будем называть шестерку ( S, s₀, X, Y, E, Q ), где

• S - множество состояний,
• s₀ S - начальное состояние,
• X - множество стимулов,
• Y - множество реакций,
• E S x ( X Y {τ} ) x S - множество переходов, которые мы будем называть
  • посылающими, если второй элемент перехода является стимулом,
  • принимающими, если второй элемент перехода является реакцией,
  • внутренним, если второй элемент перехода является τ;
• Q S - множество заключительных состояний.

Взаимодействующий автомат может посылать стимулы и получать реакции, изменяя при этом свое состояние. При возможности выбора очередного перехода этот выбор осуществляется в зависимости от доступности реакций для получения. Выбор перехода среди различных доступных переходов осуществляется недетерминировано.

Первый элемент перехода взаимодействующего автомата мы будем называть пресостоянием перехода, второй - сообщением, а третий - постсостоянием.

Заметим, что множества стимулов и реакций могут пересекаться (X Y ≠ Ø), и поэтому в определении множества переходов используется операция дизъюнктивного объединения. Для обозначения того факта, что сообщение является стимулом мы будем использовать символ !, помещаемый следом за элементом множества X (например, x!), а для обозначения принадлежности сообщения к множеству реакций будет использоваться символ ?: (например, y?).

Конечная последовательность переходов ( e₁, e₂, …, e_n ) взаимодействующего автомата A = ( S, s₀, X, Y, E, Q ) называется путем, если для каждого i = 1, …, n-1 постсостояние перехода e_i совпадает с пресостоянием перехода e_i+1. При этом мы будем говорить, что путь ведет из пресостояния перехода e₁ в постсостояние перехода e_n.

Бесконечным путем мы будем называть бесконечную последовательность переходов, любой префикс которой является конечным путем.

Путь ( e₁, e₂, …, e_n ) взаимодействующего автомата A = ( S, s₀, X, Y, E, Q ) называется функционированием, если пресостоянием перехода e₁ является начальное состояние s₀, а постсостояние перехода e_n принадлежит множеству конечных состояний Q.

Линейно-упорядоченное мультимножество стимулов и реакций ( T, ) называется трассой взаимодействующего автомата A = ( S, s₀, X, Y, E, Q ), если существует такое функционирование ( e₁, e₂, …, e_n ) автомата A, что

• мультимножество T совпадает с мультимножеством всех сообщений функционирования ( e₁, e₂, …, e_n ), отличающихся от τ;
• порядок совпадает с порядком этих сообщений в функционировании ( e₁, e₂, …, e_n ).

Множество всех возможных трасс взаимодействующего автомата A мы будем обозначать Traces(A).

Определение 14.

Дадим определение распределенного взаимодействующего автомата в рекурсивной форме.

• взаимодействующий автомат A = ( S, s₀, X, Y, E, Q ) является распределенным взаимодействующим автоматом;
• если A₁, A₂, …, A_n - распределенные взаимодействующие автоматы, а M - множество сообщений, то система взаимодействующих автоматов с множеством внутренних сообщений M (A₁,A₂,…,A_n)\M является распределенным взаимодействующим автоматом.

Множеством стимулов распределенного взаимодействующего автомата DA будем называть

• множество стимулов X, если автомат DA является взаимодействующим автоматом A = ( S, s₀, X, Y, E, Q ),
• , если автомат DA является системой взаимодействующих автоматов A₁, A₂, …, A_n с множеством внутренних сообщений M.

Аналогично, множеством реакций распределенного взаимодействующего автомата DA будем называть

• множество реакций Y, если автомат DA является взаимодействующим автоматом A = ( S, s₀, X, Y, E, Q ),
• , если автомат DA является системой взаимодействующих автоматов A₁, A₂, …, A_n с множеством внутренних сообщений M.

В системе взаимодействующих автоматов с множеством внутренних сообщений M все взаимодействующие автоматы обмениваются сообщениями из множества M только между собой и не могут обмениваться ими с окружением.

Предположим, что взаимодействующий автомат A = ( S, s₀, X, Y, E, Q ) входит в состав системы взаимодействующих автоматов SA = (A₁,A₂,…,A_n)\M. Тогда мы будем говорить, что сообщение m X Y автомата A сокрыто в SA, если m M и не существует системы взаимодействующих автоматов SA' = (A'₁,A'₂,…,A'_n')\M', входящей в SA, такой что m M' и A входит в состав SA'.

Предположим, что взаимодействующий автомат A = ( S, s₀, X, Y, E, Q ) входит в состав распределенного взаимодействующего автоматов DA. Переходы автомата A ( s₁, m, s₂ ) E будем называть внутренними для DA, если сообщение m сокрыто в одной из систем взаимодействующих автоматов, входящей в состав DA. В противном случае, переходы будем называть внешними для DA.

Функционированием распределенного взаимодействующего автомата DA называется тройка ( E, , μ ), где

• E - набор функционирований { ( e_i,1, e_i,2, …, e_i,n(i) ) } всех взаимодействующих автоматов, входящих в DA;
• - частичный порядок на множестве всех переходов { e_i,_j }_{i, j=1,…,n(i)} набора E;
• μ : { e_i,j } { e_i,j } - отображение на этом же множестве переходов;

при условии, что E, и μ удовлетворяют следующим ограничениям:

• областью определения μ является множество всех принимающих переходов e_i,j = ( s₁, m?, s₂ ) автомата A, сообщение m которых сокрыто в некоторой системе взаимодействующих автоматов SA, входящей в состав DA;
• для каждого такого перехода e_i,j = ( s₁, m?, s₂ ) значением μ(e_i,_j) является посылающий переход e_i',_j' = ( s'₁, m!, s'₂ ) автомата A', входящего в состав той же системы взаимодействующих автоматов SA, но не совпадающего с A (A ≠ A');
• частичный порядок сохраняет порядок переходов, относящихся к функционированию одного взаимодействующего автомата, то есть

  e_i,_j, e_i',_j' { e_i,_j } (i = i') (j < j') e_i,_j e_i',_j';

• переходы, связанные отношением μ, являются неразличимыми относительно частичного порядка , то есть

  e_i,_j, e_i',_j' { e_i,_j } e_i',_j' = μ(e_i,_j)
  e { e_i,_j } ( (e e_i,_j) (e e_i',_j') ) ( (e_i,_j e) (e _i',j' e) ).

Распределенный взаимодействующий автомат функционирует таким образом, что его компоненты обмениваются внутренними сообщениями между собой, а остальными сообщениями как между собой, так и с окружением. Функционирование такого автомата состоит из набора функционирований составляющих его взаимодействующих автоматов, а также из частичного порядка, определяющего порядок осуществления переходов во времени, и отображения μ, связывающее каждое получение внутреннего сообщения с его посылкой.

Заметим, что одной посылке сообщения может соответствовать несколько получений этого сообщения, то есть посылка сообщений может быть широковещательной. Все взаимодействия между автоматами осуществляются синхронным образом, а асинхронные взаимодействия должны моделироваться явно, например, при помощи дополнительного автомата моделирующего работу канала связи или буфера.

Частично упорядоченное мультимножество стимулов и реакций ( T, _T ) называется трассой распределенного взаимодействующего автомата DA, если существует такое функционирование ( E, , μ ) автомата DA, что

• мультимножество T совпадает с мультимножеством всех сообщений набора функционирований { ( e_i,₁, e_i,₂, …, e_i,_{n (i)} ) }, отличающихся от τ и не являющихся внутренними для DA;
• частичный порядок _T является сужением порядка на переходах из { ( e_i,₁, e_i,₂, …, e_i,_n(i) ) }, соответствующих этим сообщениям, то есть

  t₁, t₂ T (t_{1 T} t₂) (e(t₁) e(t₂)).

Множество всех возможных трасс распределенного взаимодействующего автомата DA мы будем обозначать Traces(DA).

Асинхронные функции

Для вычисления функций в распределенных взаимодействующих автоматах реализуется посредством использования выделенных взаимодействующих автоматов, получающих входные параметры функции и возвращающих результат.

Асинхронной функцией AF из множества входных значений IS во множество выходных значений OS называется взаимодействующий автомат SA = ( S, s₀, X, Y, E, Q ), в котором

• PY = { call_AF,is | is IS } Y - множество входных значений параметризует выделенное подмножество реакций автомата,
• RX = { result_AF,os | os OS } X - множество выходных значений параметризует выделенное подмножество стимулов автомата,
• RX PY = Ø,
• ( s, m, s' ) E (s = s₀) m PY,
• ( s, m, s' ) E m PY m' PY s'' S: ( s, m', s'' ) E,
• ( s, m, s' ) E (m RX) ( s', m', s'' ) E m' PY,
• пути ( e₁, e₂, …, e_n ) в SA (n > 1)
  e₁ = ( s₁, py₁, s'₁ ) e_n = ( s_n, py_n, s'_n ) j { 2, ..., n-1 } e_j = ( s_j, rx, s'_j ),
• q Q ( s, m, s' ) E (s' = q) m RX.

Данные ограничения определяют ту специфическую роль, которую играют сообщения из PY и RX в работе автомата SA. Эта роль заключается в том, что функционирование автомата SA состоит из последовательных циклов, каждый из которых начинается получением параметризующей реакции call_AF,ip и завершается посылкой результирующего стимула result_AF,op. Внутри этого цикла автомат SA произвольным образом взаимодействует со своим окружением, но только посредством сообщений, не входящих в PY RX.

Множество всех асинхронных функций, у которых множество входных значений равно IS, а множество выходных значений равно OS, мы будем обозначать как Ã(IS,OS).

Чтобы работа распределенного взаимодействующего автомата завершилась, необходимо, чтобы все составляющие его автоматы перешли в заключительное состояние. Для этого вместо асинхронных функций обычно используют их замыкания по выделенному множеству терминирующих реакций.

Замыканием взаимодействующего автомата ( S, s₀, X, Y, E, Q ) по множеству реакций R мы будем называть взаимодействующий автомат ( S', s'₀, X', Y', E', Q' ), в котором

• S' = S {final},
• s'₀ = s₀,
• X' = X,
• Y' = Y R,
• E' = E { ( s, r, final ) | s S, r R },
• Q' = Q {final}.

Замыкание взаимодействующего автомата дополняет исходный автомат специальным завершающим состоянием и множеством переходов, ведущих в это состояние изо всех остальных состояний по получению реакции из множества R.

Асинхронные тесты

Асинхронным тестом целевой системы с асинхронным интерфейсом ( X, Y, Z ) называется конечное или бесконечное частично упорядоченное мультимножество асинхронных взаимодействий ( P, ), которое совпадает с моделью поведения целевой системы в ходе этого теста.

Асинхронный тест ( P, ) целевой системы с асинхронным интерфейсом ( X, Y, Z ) будем называть успешным относительно асинхронной модели требований A = ( V, X, Y, Z, E ) с начальным состоянием v₀ V, если модель поведения в ходе теста ( P, ) удовлетворяет модели требований A с начальным состоянием v₀. В противном случае, тест будет называться неуспешным.

Определение 15.

Асинхронным тестовым сценарием для целевой системы с асинхронным интерфейсом ( X, Y, Z ) называется распределенный взаимодействующий автомат DA, в котором

• множество стимулов совпадает с X;
• множество реакций совпадает с Y Z;
• для любого взаимодействующего автомата A' = ( S', s'₀, X', Y', E', Q' ), входящего в состав DA, для любого внешнего для DA посылающего перехода ( s₁, x!, s₂ ) E', сообщение x которого принадлежит X X', любой переход ( s₂, m, s₃ ) E', начинающийся в состоянии s₂, является принимающим и внешним для DA, а его сообщение m принадлежат множеству Y;
• для любого взаимодействующего автомата A' = ( S', s'₀, X', Y', E', Q' ), входящего в состав DA, для любого внешнего для DA принимающего перехода ( s₂, y?, s₃ ) E', сообщение y которого принадлежит Y Y', любой переход ( s₁, m, s₂ ) E', завершающийся в состоянии s₂, является посылающим и внешним для DA.

Состояния взаимодействующих автоматов, из которых выходят только принимающие переходы, помеченные сообщениями из Y, будут далее называться промежуточными.

Асинхронный тестовый сценарий предназначен для управлением процессом тестирования систем с асинхронным интерфейсом. Такой тестовый сценарий подает тестовые стимулы целевой системе и получает от нее непосредственные и отложенные реакции, используя эту информацию для продолжения тестирования.

Множество всех асинхронных тестовых сценариев для целевой системы с асинхронным интерфейсом ( X, Y, Z ) будем обозначать символом ( X, Y, Z ).

Асинхронный тест ( P, ) называется результатом применения тестового сценария DA для целевой системы с асинхронным интерфейсом ( X, Y, Z ) к соответствующей целевой системе, если ( P, ) Traces(DA).

Асинхронный тестовый сценарий определяет правила посылки тестовых стимулов, которые могут зависеть от ответа целевой системы. Результатом работы сценария является асинхронный тест, состоящий из набора взаимодействий с целевой системой и информации о порядке, в котором происходили эти взаимодействия. Этот порядок в точности соответствует порядку взаимодействий между тестовым сценарием и целевой системой, наблюдаемому в процессе работы тестового сценария.

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

Определение 16.

Механизмом построения асинхронного тестового сценария будем называть функцию, значением которой является асинхронный тестовый сценарий.

Также как и для обычных тестовых сценариев, для асинхронных тестовых сценариев мы определим автоматный механизм их построения, который обеспечивает автоматическое формирование последовательности тестовых воздействий на основе обхода ориентированного графа.

Автоматный механизм построения асинхронного тестового сценария

Асинхронным автоматным тестовым сценарием для целевой системы с асинхронным интерфейсом ( X, Y, Z ) называется пятерка ( DA, A_fsm, IG, vg₀, α ), где

• DA - асинхронный тестовый сценарий для целевой системы с асинхронным интерфейсом ( X, Y, Z ),
• A_fsm = ( S_fsm, s₀, X_fsm, Y_fsm, E_fsm, Q_fsm ) - выделенный взаимодействующий автомат, входящий в состав DA, и называемый ведущим автоматом асинхронного тестового сценария DA,
• IG = ( VG, XG, π ) - неизбыточное описание ориентированного графа, называемого графом сценария,
• vg₀ VG - начальное состояние графа сценария,
• α - неизбыточный алгоритм движения по графу сценария;

и для которой выполнены следующие ограничения:

• S_fsm = ( VG x EG^* x (XG { ε }) ) { final } - состояние ведущего автомата является либо выделенным состоянием final, либо содержит:
  • текущую вершину графа сценария vg,
  • пройденный маршрут в графе сценария path (здесь множество EG^* обозначает множество всех конечных списков элементов из множества дуг EG = VG x XG x VG),
  • последний посланный стимул графа, на который не был получен ответ, либо ε, обозначающее отсутствие такового стимула;
• s₀ = ( vg₀, , ε ) - начальное состояние ведущего автомата состоит из
  • начальной вершины графа сценария,
  • пройденного пути, равного пустому списку,
  • специального значения ε;
• X_fsm = { start_vg,xg | vg VG, xg XG } { stop } - множество стимулов ведущего автомата состоит из набора стимулов, помеченных вершиной и стимулом графа, и из дополнительного стимула, символизирующего завершение работы, причем все эти стимулы являются внутренними для DA;
• Y_fsm = { finish_vg | vg VG } { abort } - множество реакций ведущего автомата состоит из набора реакций, помеченных вершинами графа, и из дополнительной реакции, символизирующей аварийное завершение работы, причем все эти реакции являются внутренними для DA;
• E_fsm = { ( ( vg, path, ε ), start_vg,xg, ( vg, path, xg ) ) | xg = α( IG, vg, path ) }
  
  { ( ( vg, path, ε ), stop, final ) | α( IG, vg, path ) = τ }
  
  { ( ( vg, path, xg ), finish_vg*, ( vg', path', ε ) |
  vg' = vg*
  path' = path ^ ( vg, xg, vg' )
  }
  
  { ( ( vg, path, xg ), abort, final ) }
• Q_fsm = { final } - множество заключительных состояний ведущего автомата состоит из единственного состояния final.

Автоматным механизмом построения асинхронного тестового сценария называется функция, которая преобразует асинхронный автоматный тестовый сценарий ( DA, A_fsm, IG, vg₀, α ) в асинхронный тестовый сценарий DA.

Работа автоматного тестового сценария устроена следующим образом. Граф сценария описывает некоторым образом пространство тестовых ситуаций. Ведущий автомат двигается по данному графу, используя заданный алгоритм движения.

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

Асинхронные сценарные функции

Для описания стимулов графа автоматного сценария в асинхронном случае так же, как и в синхронном, используется понятие сценарной функции. В данном случае, в качестве сценарной функции выступает обычная асинхронная функция, а множество допустимых стимулов определяется на основе множества ее входных параметров.

Асинхронной сценарной функцией мы будем называть асинхронную функцию, в которой множество входных значений может быть произвольным, а множество выходных значений Bool состоит из двух элементов true и false.

Множество всех асинхронных сценарных функций, у которых множество входных значений равно IS, мы будем обозначать как Σ(IS).

Асинхронным автоматным тестовым сценарием со сценарными функциями для целевой системы с асинхронным интерфейсом ( X, Y, Z ) называется семерка ( DA, A_fsm, VG, XG, vg₀, α, ), где

• DA - асинхронный тестовый сценарий для целевой системы с асинхронным интерфейсом ( X, Y, Z ),
• A_fsm ( S_fsm, s₀, X_fsm, Y_fsm, E_fsm, Q_fsm ) - выделенный взаимодействующий автомат, входящий в состав DA, и называемый ведущим автоматом асинхронного тестового сценария DA,
• VG - множество состояний графа сценария,
• XG - множество стимулов графа сценария,
• vg₀ - начальное состояние графа сценария,
• α - неизбыточный алгоритм движения по графу сценария,
• - конечный набор асинхронных сценарных функций Σ_i = ( S_i, s₀,_i, X_i, Y_i, E_i, Q_i ) Σ(IS_i);

и для которой выполнены следующие ограничения:

• замыкания взаимодействующих автоматов Σ_i по множеству { stop, abort } входят в состав DA, причем все эти вхождения и вхождение A_fsm в DA различаются между собой,
• i { 1, …, k } IS_i VG x XG,
• i, j { 1, …, k } i ≠ j XG_i XG_j = Ø,
  где XG_i = { xg XG | vg VG: ( vg, xg ) IS_i },
• X_fsm = { stop }, где PY_i = { call_i,is | is IS_i },
• сообщения из присутствуют только в ведущем автомате и автоматах-сценарных функциях,
• пятерка ( DA, A_fsm, IG, vg₀, α ), в которой IG состоит из
  • множества состояний графа сценария VG,
  • множества стимулов графа сценария XG,
  • функции π: π(vg) = { xg XG | i { 1, …, k }: ( vg, xg ) IS_i },
    является асинхронным автоматным тестовым сценарием для целевой системы с асинхронным интерфейсом ( X, Y, Z ).

Стационарное тестирование асинхронных систем

Тестирование систем с асинхронным интерфейсом значительно осложнено большой временной сложностью алгоритмов оценки корректности поведения тестируемой системы. Область применимости этих алгоритмов ограничена асинхронными моделями поведения, состоящими из нескольких десятков взаимодействий.

В большинстве случаев одного теста такого размера оказывается недостаточно для достижения требуемого качества тестирования. Как следствие, появляется необходимость в построении набора тестов небольшого размера. Если разрабатывать такие наборы тестов независимо друг от друга, то при этом теряется одно из основных достоинств технологии UniTesK - автоматическое построении сложных последовательностей тестовых воздействий.

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

Оценка корректности поведения целевой системы, в этом случае, выполняется каждый раз после завершения работы локального тестового сценария. Так как размеры такого сценария небольшие, то алгоритм оценки корректности поведения обрабатывает его результаты за приемлемое время. По завершении этой проверки автоматный тестовый сценарий продолжает обход графа, то есть выбирает следующую дугу и выполняет соответствующий локальный тестовый сценарий.

В результате, такое решение сохраняет генерацию последовательности тестовых воздействий, позволяющую автоматически выполнять набор тестовых воздействий в различных состояниях графа, и в то же время обходит ограничения алгоритма оценки корректности поведения.

В настоящей работе мы ограничимся рассмотрением случае, когда во время проверки корректности поведения после завершения локального сценария тестируемая система не выполняет никаких активных действий. Это означает, что при корректном поведении целевой системы ожидается, что после завершения работы локального тестового сценария целевая система не будет посылать никаких отложенных реакций. Или другими словами, предполагается, что тестируемая система находится в стационарном состоянии.

Определение 17.

Стационарными состояниями асинхронной модели требований ( V, X, Y, Z, E ) называются такие состояния v V, из которых выходят только переходы, помеченные стимулом и непосредственной реакцией, то есть ( v, p, v' ) E p X x Y.

Определение 18.

Тестируемые системы мы будем называть пассивными, если после подачи произвольного набора стимулов в произвольном состоянии тестируемая система за конечное время переходит в стационарное состояние.

На первый взгляд пассивные тестируемые системы составляют лишь небольшую часть всех асинхронных систем, но с точки зрения предлагаемого подхода бОльшая часть "активных" систем может быть переведена в класс пассивных. Действительно, если асинхронная система проявляет свою активность через некоторые промежутки времени, то есть периодически посылает сообщения, не инициированные внешним воздействием, то такое поведение можно моделировать как переход системы в стационарное состояние, получение ею специального стимула "время" и последующую посылку отложенных реакций. В этом случае, тестируемая система может рассматриваться как пассивная, если времени до очередной отложенной реакции достаточно, чтобы тестовая система завершила оценку корректности поведения и инициировала следующий локальный тестовый сценарий. Таким образом, класс пассивных асинхронных систем является достаточно большим и далее мы будем рассматривать тестирование только таких целевых систем.

Тестирование пассивных целевых систем, построенное по рассмотренным выше принципам, мы будем называть стационарным тестированием.

Если после завершения работы локального тестового сценария некоторые ожидаемые отложенные реакции не были получены, то состояние модели требований не будет стационарным. Таким образом, проверка стационарности состояния модели требований после завершения работы локального тестового сценария может служить решением проблемы проверки полноты набора отложенных реакций, обсуждавшийся ранее в разделе "Требования к полноте набора асинхронных реакций".

С другой стороны, непосредственная проверка стационарности не слишком удобна при наличии опциональных отложенных реакций, которые могут быть посланы тестируемой системой, а могут и отсутствовать. Для описания таких реакций разработчику теста придется вводить псевдостимул done, описывающий завершение ожидания опциональных реакций.

Чтобы упростить работу разработчика тестов, мы определим неявные трансформации асинхронной модели требований и асинхронной модели поведения, построенной по результатам работы локального сценария. При помощи данных трансформаций мы решим проблему проверки полноты набора отложенных реакций, включающего как обязательные, так и опциональные реакции.

Стабилизирующей трансформацией ST[A,V_S] асинхронной модели требований A = ( V, X, Y, Z, E ) относительно множества стабильных состояний V_S V будем называть асинхронную модель требований A' = ( V', X', Y', Z', E' ), в которой:

• множество состояний V' = V x {T,F}, первую составляющую которого мы будем называть основной,
• множество стимулов X' = X {done},
• множество непосредственных реакций Y' = Y {ε},
• множество отложенных реакций Z' = Z,
• множество переходов E' = { ( (v₁,T), p, (v₂,F) ) | ( v₁, p, v₂ ) E p X x Y }
  { ( (v₁,F), p, (v₂,F) ) | ( v₁, p, v₂ ) E }
  { ( (v,F), (done,ε), (v,T) ) | v V_S }.

Заметим, что все состояния стабилизирующей трансформации вида (v,T) гарантированно являются стационарными, так как из них, по определению, не выходит переходов, помеченных отложенными реакциями. Семантика множества стабильных состояний заключается в том, что стабильными состояниями считаются такие состояния, в которых не ожидается ни одной обязательной отложенной реакции.

Стабилизирующей трансформацией ST[(P,)] асинхронной модели поведения ( P, ) будем называть асинхронную модель поведения ( P', ' ), в которой:

• P' = P {(done,ε)},
• ' = { ( p, (done,ε) ) | p P }.

Стабилизирующая трансформация модели поведения содержит дополнительное псевдовзаимодействие (done,ε), которое является максимальным элементом относительно частичного порядка '.

Стабилизирующие трансформации обоих моделей единообразно модифицируют асинхронный интерфейс целевой системы, добавляя в него псевдостимул done и непосредственную реакцию ε. Таким образом, если исходные модели были построены для общего асинхронного интерфейса ( X, Y, Z ), то их стабилизирующие трансформации будут для общего асинхронного интерфейса ( X {done}, Y {ε}, Z ).

При реализации стационарного тестирования на основе асинхронного автоматного тестового сценария со сценарными функциями, в качестве локальных тестовых сценариев будут выступать автоматы-сценарные функции, а построение обхода графа сценария будет выполнять ведущий автомат. Для оценки корректности поведения целевой системы после работы локального сценария мы введем дополнительный взаимодействующий автомат, который будем называть стабилизирующим. Этот автомат будет получать сообщения о завершении очередного цикла работы автомата-сценарной функции (rx RX_i), инициировать проверку корректности поведения целевой системы и в случае ее успешного завершения вычислять новую вершину графа сценария и передавать ее ведущему автомату. В случае обнаружения некорректности поведения целевой системы стабилизирующий автомат будет посылать сообщение abort, завершая таким образом работу тестового сценария.

Входными данными для алгоритма проверки корректности поведения являются конечная асинхронная модель поведения целевой системы ( P, ) и асинхронная модель требований A = ( V, X, Y, Z, E ) с начальным состоянием v₀ V. Модель поведения содержит информацию о взаимодействиях с целевой системой в процессе работы автомата-сценарной функции и строится динамически. Модель требований задается заранее и является неизменной на протяжении всей работы тестового сценария. А вот начальное состояние модели требований изменяется в процессе тестирования и соответствует текущему состоянию целевой системы.

Единственность такого состояния накладывает дополнительное ограничение на работу тестового сценария. От него требуется, чтобы все корректные линеаризации асинхронной модели поведения P завершались в одном и том же состоянии, то есть

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

Заметим, что алгоритм проверки корректности поведения легко обобщается на случай, когда начальное состояние модели требований задано неоднозначно. То есть, когда вместо конкретного начального состояния v₀ задано множество возможных начальных состояний V₀. Для этого требуется только изменить инициализацию первого элемента массива path: вместо инициализации path[0] множеством, содержащим начальное состояние {v₀}, использовать инициализацию множеством возможных начальных состояний V₀.

Но в настоящей работе мы не будем рассматривать способы построения тестовых сценариев без данного ограничения, а оставим эту задачу в качестве направления дальнейшего развития.

Стационарный автоматный тестовый сценарий

Рассмотрим реализацию предложенного подхода более формально.

Стационарным автоматным тестовым сценарием относительно асинхронной модели требований A = ( V, X, Y, Z, E ) с множеством стабильных состояний V_S V и начальным состоянием v₀ V_S, называется пятерка ( SA, A_St, A_IR, A_HO, A_GS ), где

• SA = ( DA, A_fsm, VG, XG, vg₀, α, ) - асинхронный автоматный тестовый сценарий со сценарными функциями для целевой системы с асинхронным интерфейсом ( X, Y, Z ),
• A_St = ( S_St, s_0,St, X_St, Y_St, E_St, Q_St ) - выделенный взаимодействующий автомат, входящий в состав DA, и называемый стабилизирующим автоматом асинхронного тестового сценария DA,
• A_IR Ã( Unit, ( Ω(X,Y,Z) ) ) - асинхронная функция, замыкание которой по множеству { stop, abort } входит в состав DA,
• A_HO Ã( ( Ω(X,Y,Z) ) x V, Bool x V ) ⁸ - асинхронная функция, замыкание которой по множеству { stop, abort } входит в состав DA,
• A_GS Ã( Unit, VG ) - асинхронная функция, замыкание которой по множеству { stop, abort } входит в состав DA;

и для которой выполнены следующие ограничения:

• вхождения замыканий взаимодействующих автоматов A_IR, A_HO и A_GS и вхождения A_St, A_fsm и Σ_i в DA различаются между собой,
• S_St = ( { s₀, s₁, s₂, s₄, s₅, s₆, final } Ω(X,Y,Z) ) x V,
• s_0,St = ( s₀, v₀ ),
• X_St = { call_IR, call_GS, abort } { call_HO,P,v | P Ω(X,Y,Z), v V },
• Y_St = { stop, abort } { result_HO,verdict,v | verdict Bool, v V }
  { result_IR,P | P Ω(X,Y,Z) },
  где RX_i = { result_i,true, result_i,false },
• E_St = { ( ( s₀, v ) result_i,true?, ( s₁, v ) ) | i = 1, …, k }
  { ( ( s₁, v ), call_IR!, ( s₂, v ) ) }
  { ( ( s₂, v ), result_IR,P?, ( P, v ) ) | P Ω(X,Y,Z) }
  { ( ( P, v ), call_HO,P,v!, ( s₄, v ) ) | P Ω(X,Y,Z) }
  { ( ( s₄, v ), result_HO,true,v'?, ( s₅, v' ) ) }
  { ( ( s₄, v ), result_HO,false,v'?, ( s₆, v ) ) }
  { ( ( s₅, v ), call_GS!, ( s₀, v ) ) }
  { ( ( s₆, v ), abort!, ( final, v ) ) }
  { ( ( s₀, v ), result_i,false?, ( s₆, v ) ) | i = 1, …, k }
  { ( ( s₀, v ), stop?, ( final, v ) ) }
  { ( ( s₀, v ), abort?, ( final, v ) ) }
  
• Q_St = { ( final, v ) | v V },
  
• Y_fsm = { result_GS,vg | vg VG } { abort },
• асинхронная функция A_IR возвращает асинхронную модель поведения, описывающую все взаимодействия с целевой системой, зафиксированные за время работы сценарной функции,
• асинхронная функция A_HO получает асинхронную модель поведения P и текущее состояние модели v и возвращает true, если стабилизирующая трансформация этой модели ST[P] удовлетворяет стабилизирующей трансформации ST[A,V_S] с начальным состоянием (v,T), и false - в противном случае, причем, в первом случае она также возвращает основную составляющую конечного состояния линеаризации,
• асинхронная функция A_GS возвращает текущую вершину графа автомата,
• все стимулы и реакции стабилизирующего автомата являются внутренними для DA:
  (X_St Y_St) (X Y Z) = Ø,
• всем стимулам, вызывающим асинхронные функции из стабилизирующего автомата, соответствуют единственные в рамках DA реакции, принадлежащие соответствующим асинхронным функциям,
• всем реакциям получения результата асинхронных функций из стабилизирующего автомата, соответствуют единственные в рамках DA стимулы, принадлежащие соответствующим асинхронным функциям.

Стационарный автоматный тестовый сценарий определяет правила организации стационарного тестирования на основе асинхронного автоматного тестового сценария со сценарными функциями. Основную роль здесь играет стабилизирующий автомат, который после завершения каждого цикла работы сценарной функции запрашивает модель поведения, описывающую все взаимодействия с целевой системой за время этого цикла, и проверяет корректность этой модели поведения. В случае успешной проверки стабилизирующий автомат возвращает управление управляющему автомату с указанием новой вершины в графе автомата. В противном случае тест завершается посылкой стимула abort.

Работа по оценке корректности модели поведения выполняется в асинхронной функции A_HO, которая получает на вход текущее состояние модели требований и асинхронную модель поведения. К модели поведения применяется стабилизирующая трансформация и затем проверяется корректность этой трансформации относительно стабилизирующей трансформации модели требований ST[A,V_S] с начальным состоянием, равным текущему состоянию модели требований. В дополнение к оценке корректности A_HO возвращает основную составляющую конечного состояния линеаризации, которая становится новым текущим состоянием модели требований.

Однако, конечное состояние линеаризации может быть найдено только в том случае, когда все успешные линеаризации модели поведения ST[P] завершаются в одном и том же состоянии. Если это условие не выполняется, то асинхронная функция A_HO не может выполнить свою задачу и, соответственно, стационарный автоматный тестовый сценарий не может быть применен.

Далее, мы обратимся к вопросу применимости стационарного автоматного тестового сценария и определим достаточные условия для его корректной работы.

Асинхронная модель требований A = ( V, X, Y, Z, E ) называется стационарно-детерминированной относительно множества стабильных состояний V_S V, если для любого конечного мультимножества асинхронных взаимодействий P и для любого состояния v V_S

Лемма.

Если асинхронная модель требований A = ( V, X, Y, Z, E ) является стационарно-детерминированной относительно множества стабильных состояний V_S V, то произвольный стационарный автоматный тестовый сценарий относительно модели требований A с множеством стабильных состояний V_S и начальным состоянием v₀ V_S применим независимо от поведения целевой системы.

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

1. Сначала мы докажем по индукции, что асинхронная функция A_HO в качестве текущего состояния модели требований всегда получает стабильное состояние.

Функция A_HO получает на вход состояние модели требований, которое хранится в стабилизирующем автомате сценария. В начале работы сценария это состояние инициализируется начальным состоянием v₀, которое является стабильным по определению (v₀ V_S).

В дальнейшем, это состояние может измениться только в переходе ( ( s₄, v ), result_HO,true,v'?, ( s₅, v' ) ), при получении результата от асинхронной функции A_HO, так как согласно четырнадцатому ограничению стационарного автоматного тестового сценария реакции получения результата асинхронной функции A_HO из стабилизирующего автомата result_HO,true,v' соответствует единственный в рамках DA стимул, принадлежащий соответствующей асинхронной функции. При этом новое состояние совпадает с конечным состоянием линеаризации, которое возвращается функцией A_HO.

В качестве индуктивного перехода покажем, что для любой асинхронной модели поведения P, если стабилизирующая трансформация этой модели ST[P] удовлетворяет стабилизирующей трансформации ST[A,V_S] с начальным состоянием (v,T), где v стабильно (v V_S), и конечное состояние линеаризации (v',x') существует, то оно также является стабильным (v' V_S).

Действительно, по определению, { (v',x') } = Г^* ( (v,T), ( p₁, p₂, …, p_n ) ) для некоторой линеаризации ( p₁, p₂, …, p_n ) модели поведения ST[P]. Так как псевдовзаимодействие (done,ε) является максимальным элементом в стабилизирующей трансформации ST[P], то p_n = (done,ε). С другой стороны, по определению стабилизирующей трансформации ST[A,V_S], все переходы, помеченные (done,ε), могут быть только вида ( (w,F), (done,ε), (w,T) ), где w V_S. Следовательно

W V x {T,F} ( W, p_n ) V_S x {T},

и

{ (v',x') } = Г^* ( (v,T), ( p₁, p₂, …, p_n ) ) = Г( … Г( {(v,T)}, p₁ ), … p_n ) V_S x {T}.

То есть v' V_S, что и требовалось доказать.

2. В качестве завершающего шага мы докажем, что для любой асинхронной модели поведения P, если стабилизирующая трансформация этой модели ST[P] удовлетворяет стабилизирующей трансформации ST[A,V_S] с начальным состоянием (v,T), где v стабильно (v V_S), то конечное состояние линеаризации (v',x') существует. Из этого следует, что асинхронная функция A_HO всегда может выполнить свою задачу, так как согласно первому пункту она всегда получает на вход только стабильные состояния модели требований.

Предположим, что это не так. То есть существует асинхронная модель поведения P, стабильное состояние модели требований v V_S и два состояния (v',x') и (v'',x'') такие, что

{ (v',x'), (v'',x'') } и (v',x') ≠ (v'',x'').

Тогда существует две линеаризации модели поведения ST[P] ( p₁,₁, p_1,2, …, p_1,n ) и ( p_2,1, p_2,2, …, p_2,n ) такие, что

(v', x') ( (v,T), ( p_1,1, p_1,2, …, p_1,n ) ) и

(v'',x'') ( (v,T), ( p_2,1, p_2,2, …, p_2,n ) ).

Повторяя рассуждения из первого пункта, можно показать, что x' = x'' = T, p_1,n = p_2,n = (done,ε), v' V_S, v'' V_S и

(v', F) ( (v,T), ( p_1,1, p_1,2, …, p_1,n-1 ) ) и

(v'',F) ( (v,T), ( p_2,1, p_2,2, …, p_2,n-1 ) ).

То есть в асинхронной модели требований ST[A,V_S] существует путь, начинающийся в (v,T), помеченный ( p_1,1, p_1,2, …, p_1,n-1 ) и заканчивающийся в (v', F):

(v,T) (v₂,x₂) … (v', F).

Так как { p_1,1, p_1,2, …, p_1,n-1 } ( (X x Y) Z ), то из определения ST[A,V_S] следует, что в исходной модели требований A существует путь

v v₂ … v'.

Следовательно, v' ( v, ( p_1,1, p_1,2, …, p_1,n-1 ) ).

Аналогично, v'' ( v, ( p_2,1, p_2,2, …, p_2,n-1 ) ).

И так как мультимножества взаимодействий { p_1,1, p_1,2, …, p_1,n-1 } и { p_2,1, p_2,2, …, p_2,n-1 } совпадают, то существует мультимножество взаимодействий P^* = { p_1,1, p_1,2, …, p_{1,n 1} }:

{ v', v'' } , причем v' ≠ v'' и v' V_S, v'' V_S.

То есть

и асинхронная модель требований A = ( V, X, Y, Z, E ) не является стационарно-детерминированной относительно множества стабильных состояний V_S V.

Следовательно, наше предположение не верно и v' = v'', что и требовалось доказать.

Таким образом, стационарные автоматные тестовые сценарии могут применяться для тестирования относительно стационарно-детерминированных моделей требований, которые представляют широкий класс моделей требований. С другой стороны, требование стационарной-детерминированности не является необходимым, и стационарные автоматные тестовые сценарии могут работать с другими моделями при условии, что в процессе тестирования не встретится ситуация с отсутствием конечного состояния линеаризации по причине наличия нескольких успешных линеаризаций, заканчивающихся в различных состояниях.

Асинхронная функция A_HO может быть реализована в предположении, что модель требований является стационарно-детерминированной. В этом случае она может возвращать в качестве конечного состояния постсостояние первой успешной линеаризации. Также возможна реализация функция A_HO, которая будет верифицировать корректность модели требований, находя все успешные линеаризации и проверяя, что все их постсостояния совпадают.

Последовательной композицией набора асинхронных моделей поведения мы будем называть асинхронную модель поведения ( P, ), в которой мультимножество P получено объединением элементов мультимножеств P_i (P = ), а частичный порядок составлен из частичных порядков _i:

{ ( p₁, p₂ ) | p₁ P_i p₂ P_j i < j }.

Последовательная композиция моделей поведения представляет собой объединенную модель поведения, в которой присутствуют все взаимодействия из этих моделей поведения, причем считается, что любое взаимодействие из i-ой модели поведения происходило позже всех взаимодействий, принадлежащих предыдущим моделям.

Лемма.

Предположим, что модель требований A = ( V, X, Y, Z, E ) является стационарно-детерминированной относительно множества стабильных состояний V_S V. Предположим также, что в процессе работы стационарного автоматного тестового сценария ( SA, A_St, A_IR, A_HO, A_GS ) относительно модели требований A с множеством стабильных состояний V_S и начальным состоянием v₀ V_S асинхронная функция A_IR последовательно возвращала стабилизирующему автомату асинхронные модели поведения . Тогда, все вердикты функции A_HO, посланные стабилизирующему автомату, были положительными, в том, и только в том случае, когда последовательная композиция стабилизирующих трансформаций моделей поведения удовлетворяет стабилизирующей трансформации модели требований ST[A] с начальным состоянием v₀.

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

1. Докажем утверждение леммы в прямую сторону. Предположим, что все вердикты функции A_HO, посланные стабилизирующему автомату, были положительными, и покажем, что последовательная композиция удовлетворяет ST[A] с начальным состоянием v₀.

В пункте 2 предыдущей леммы мы показали, что если асинхронная функция A_HO получает на вход асинхронную модель поведения P_i и состояние модели требований v и возвращает положительный вердикт и конечное состояние линеаризации v', то в модели требований ST[A] существует путь (v,T) … (v',F) (v',T) для некоторой линеаризации ( p_i,1, p_i,2, …, p_i,n(i)-1, p_i,n(i) ) модели ST[P_i] и p_{i,n (i)} = done.

Как мы уже отмечали, функция A_HO получает на вход состояние модели требований, которое хранится в стабилизирующем автомате сценария. Это состояние инициализируется в начале работы сценария начальным состоянием v₀, а в дальнейшем оно изменяется только в переходах вида ( ( s₄, v ), result_HO,true,v'?, ( s₅, v' ) ). Эти переходы осуществляются при получении результата от асинхронной функции A_HO, так как согласно четырнадцатому ограничению стационарного автоматного тестового сценария каждой реакции получения результата асинхронной функции A_HO из стабилизирующего автомата result_HO,true,v' соответствует единственный в рамках DA стимул, принадлежащий соответствующей асинхронной функции.

Отсюда следует, что в модели требований ST[A] существует путь

(v₀,T) … (v'₁,F) (v'₁,T) … (v'₂,F) (v'₂,T) …
… (v'_k-1,T) … (v'_k,F) (v'_k,T).

Покажем, что последовательность
( p_1,1, …, p_1,n(1)-1, p_1,n(1), p_2,1, …, p_2,n(2)-1, p_2,n(2), …, p_k,1, …, p_k,n(k)-1, p_k,n(k) )

является линеаризацией ( P, ), где ( P, ) обозначается последовательная композиция .

Действительно, все элементы мультимножества P присутствуют в этой последовательности, а порядок элементов последовательности не противоречит частичному порядку .

Предположим, что последнее утверждение не верно. Тогда в последовательности существуют два таких элемента p_i,r и p_j,s, что p_j,s p_i,r, но p_i,r расположен раньше, чем p_j,s, то есть (i < j) (i = j) (r < s).

В первом случае, если i < j, то p_i,r p_j,s, согласно определению частичного порядка , и следовательно ¬ p_j,s p_i,r.

Во втором случае, если i = j и r < s, то из p_j,s p_i,r следует, что p_{j,s i} p_i,r. Но тогда ( p_i,1, p_i,2, …, p_i,n(i) ) не может быть линеаризацией модели ST[P_i], так как порядок элементов p_j,s и p_i,r противоречит частичному порядку ST[_i]. Следовательно, наше предположение не верно и порядок элементов последовательности не противоречит частичному порядку .

Таким образом, рассматриваемая последовательность является линеаризацией последовательной композиции , а из существования пути

(v₀,T) … (v'₁,F) (v'₁,T) … (v'₂,F) (v'₂,T) …
… (v'_k-1,T) … (v'_k,F) (v'_k,T).

в автомате A следует, что последовательная композиция удовлетворяет модели требований A с начальным состоянием v₀.

2. Докажем утверждение леммы в обратную сторону. Предположим, что первые k-1 вердикта функции A_HO, посланные стабилизирующему автомату, были положительными, а k-й вердикт - отрицательный. Покажем, что в этом случае последовательная композиция не удовлетворяет ST[A] с начальным состоянием v₀.

Предположим, что это не так и последовательная композиция удовлетворяет ST[A] с начальным состоянием v₀. То есть в модели требований ST[A] существует путь

(v₀,T) … (v_{1,n (1)-1}, x_1,n(1)-1) (_v1,n(1) , x_1,n(1) ) …
… (v_k-1,n(k-1) , x_k-1,n(k-1) ) … (v_k,n(k)-1, x _k,n(k)-1) (v_k,n(k) , x _k,n(k) ),

где ( p_1,1, …, p_1,n(1)-1, p_1,n(1) , p_2,1, …, p_2,n(2)-1, p_2,n(2) , …, p_k,1, …, p_k,n(k)-1, p_k,n(k) ) - некоторая линеаризацией последовательной композиции . Согласно определению стабилизирующей трансформации максимальным элементом в SP[ (P_i,_i) ] является псевдовзаимодействие (done,ε). Следовательно i {1,…,k} p_i,n(i) = (done,ε).

По определению стабилизирующей трансформации модели требований ST[A] все переходы, помеченные (done,ε), имеют вид ( (w,F), (done,ε), (w,T) ), где w V_S. То есть

i {1,…,k} (v_i,_n(1)-1, x_i,n(i)-1) (v_i,n(i) , x_i,n(i) ) ≡ (v'_i,F) (v'_i,T),

где v'_i V_S.

Докажем по индукции, что i {1, …, k-1} в результате i-го вызова функции A_HO из стабилизирующего автомата, та возвращает состояние модели требований равное v'_i.

База индукции . Согласно определению стабилизирующего автомата функция A_HO в первый раз получает модель поведения (P₁,₁) и состояние v₀ V_S. Если k > 1, то функция возвращает положительный вердикт и основную составляющую конечного состояния линеаризации ( v', x' ). Так как модель требований A является стационарно-детерминированной, то конечное состояние линеаризации существует, причем v' = v'₁, так как (v₀,T) … (v'₁,F) (v'₁,T) является успешной линеаризацией модели (P₁,₁).

Предположение индукции . Предположим, что после i-го вызова функции A_HO из стабилизирующего автомата, та возвращает состояние модели требований v'_i.

Шаг индукции . Докажем, что если после i+1-го вызова функция A_HO возвращает положительный вердикт и состояние модели требований w, то w = v'_i+1.

По определению стабилизирующего автомата при i+1-ом вызове функция A_HO получает модель поведения (P_i+1,_i+1) и состояние v'_i V_S. Если i+1 < k, то по условиям леммы функция возвращает положительный вердикт и основную составляющую конечного состояния линеаризации w. Заметим, что в автомате ST[A] существует путь (v'_i,T) … (v'_i+1,F) (v'_i+1,T), который является одной из успешных линеаризаций модели (P_i+1,_i+1). Следовательно, состояние w совпадает с состоянием v'_i+1.

Рассмотрим работу функции A_HO при k-ом вызове. Стабилизирующий автомат передает ей модель поведения (P_k,_k) и состояние w V, полученное от функции A_HO на предыдущем вызове, если k > 1, или v₀ V, если k = 1. В первом случае, как мы показали по индукции, состояние модели требований w равно v'_k-1.

Исходя из предположения второго пункта леммы, существует линеаризация модели поведения SP[ (P_k,_k) ] ( p_k,1, …, p_k,n(k)-1, p_k,n(k) ), такая что в автомате ST[A] существует путь (v'_k-1,T) … (v'_k,F) (v'_k,T). И так как модель требований A является стационарно-детерминированной, то согласно предыдущей лемме конечное состояние линеаризации существует и совпадает с (v'_k,T). Следовательно, функция A_HO, по определению, должна вернуть положительный вердикт и состояние v'_k. Но эта функция вернула на k-ом шаге отрицательный вердикт, то есть наше предположение не верно, и последовательная композиция не удовлетворяет модели требований ST[A] с начальным состоянием v₀.

Из данной леммы можно сделать вывод, что стационарный автоматный тестовый сценарий, проверяя корректность небольших моделей поведения, описывающих только часть поведения целевой системы в процессе тестирования, в итоге проверяет корректность поведения целевой системы в процессе всего тестирования в целом. Таким образом, декомпозиция задачи оценки корректности осуществлена корректным образом.

Асинхронный тестовый сценарий dfsm

Основным механизмом построения тестовых сценариев в синхронном случае является механизм построения тестового сценария dfsm. Этот механизм основан на неизбыточном алгоритме обхода на классе детерминированных сильно-связных конечных ориентированных графов α_dfsm[26]. Для стационарного тестирования асинхронных систем данный алгоритм обхода также будет выступать в качестве одного из основных.

Определение 19.

Асинхронным тестовым сценарием dfsm относительно асинхронной модели требований A ( V, X, Y, Z, E ) с множеством стабильных состояний V_S V и начальным состоянием v₀ V_S, называется стационарный автоматный тестовый сценарий, в котором в качестве алгоритма движения по графу сценария используется алгоритм обхода α_dfsm.

Любое конечное функционирование алгоритма обхода α_dfsm приводит

• либо к обнаружению нарушения требований детерминированности или сильно-связности графа сценария,
• либо к построению обхода этого графа.

Таким образом, если граф сценария при любом корректном функционировании целевой системы является детерминированным и сильно-связным, то в результате успешной работы асинхронного тестового сценария dfsm путь, пройденный по графу сценария, является обходом этого графа. В этом случае, в каждом достижимом состоянии графа сценария будет вызвана каждая допустимая в данном состоянии асинхронная сценарная функция. Это позволяет строить асинхронные тестовые сценарии на основе так называемой автоматной композиции, которая продемонстрировала свои достоинства в ходе применения технологии UniTesK для тестирования синхронных систем различного рода.

Однако, при тестировании асинхронных систем недетерминированное поведение встречается значительно чаще, так как в случае параллельных взаимодействий результат может определяться последовательностью внутренних событий целевой системы, не поддающихся наблюдению и тем более управлению со стороны тестовой системы. Поэтому потребность в использовании алгоритмов обхода, способных работать с недетерминированными графами, для асинхронных тестовых сценариев выше, чем в синхронном случае. Один из таких алгоритмов, мы рассмотрим в следующем разделе.

Алгоритм обхода ndfsm

Основная идея алгоритма обхода ndfsm заключается в следующем. Если в недетерминированном графе существует детерминированный сильносвязный полный остовный подграф, то алгоритм движения может использовать этот подграф для построения обхода, не сталкиваясь непосредственно с проблемами недетерминизма.

Ориентированный граф G' = ( VG', XG', EG' ) называется остовным подграфом ориентированного графа G = ( VG, XG, EG ), если VG' = VG, XG' = XG и EG' EG.

Остовный подграф G' = ( VG', XG', EG' ) ориентированного графа G = ( VG, XG, EG ) называется полным остовным подграфом, если
( v, xg, v' ) EG ( v, xg, v'' ) EG ( v, xg, v' ) EG' ( v, xg, v'' ) EG'.

Напомним, что алгоритмом движения на ориентированных графах называется функция α, которая по ориентированному графу G = ( VG, XG, EG ), текущей вершине v VG и пройденному маршруту ( e₁, e₂, …, e_n ) определяет следующее действие a XG { τ }.

Пусть e = ( e₁, e₂, …, e_n ) - пройденный маршрут в графе G = ( VG, XG, EG ). Тогда мы будем использовать следующие обозначения. Множеством пройденных вершин VG_e мы будем называть множество вершин пройденного маршрута:

VG_e = { vg VG | e_i: e_i = ( v_i, xg_i, v'_i ) (v_i = vg v'_i = vg) }

Пройденным подграфом мы будем называть граф G'_e = ( VG_e, XG, { e₁, e₂, …, e_n } ).

Пусть e_i = ( v_i, xg_i, v'_i ). Тогда детерминированным пройденным подграфом мы будем называть граф G''_e = ( VG_e, XG, { e_i | j { 1, … , n } (v_i ≠ v_j xg_i ≠ xg_j v'_i = v'_j) } ).

Будем говорить, что стимул xg пройден в вершине vg, если существуют такая вершина vg' VG и дуга e_i e, что e_i = ( vg, xg, vg' ).

Если в вершине vg все допустимые стимулы являются пройденными, то такая вершина будет называться завершенной.

Для обеспечения детерминированности функции мы будем считать, что множество стимулов XG является фундированным, то есть множество линейно упорядоченно и в нем отсутствует бесконечно убывающая последовательность элементов.

Определение 20.

Алгоритмом движения ndfsm мы будем называть функцию α_ndfsm, которая по неизбыточному описанию ориентированного графа G = ( VG, XG, π ), текущей вершине v VG и пройденному маршруту e = ( e₁, e₂, …, e_n ) вычисляет действие a XG { τ } следующим образом:

• Если текущая вершина не является завершенной, то функция возвращает минимальный стимул из π(v), который не является пройденным в текущей вершине;
• Иначе, если в детерминированном пройденном подграфе существует маршрут, ведущий из текущей вершины в какую-либо из незавершенных пройденных вершин, то функция возвращает стимул, приписанный к дуге e_i пройденного маршрута, которая обладает минимальным индексом среди всех дуг, являющихся первыми дугами в кратчайших маршрутах детерминированного пройденного подграфа, ведущих из текущей вершины в какую-либо из незавершенных пройденных вершин;
• В противном случае функция возвращает τ.

Корректность определения следует из фундированности множества стимулов и конечности пройденного подграфа.

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

Обходом по стимулам [27] конечного ориентированного графа G = ( VG, XG, EG ) называется маршрут v₁ v₂ … v_n, в котором для каждой дуги ( v, x, v' ) EG существует i { 1, … , n-1 }, такое что v = v_i и x = x_i.

Алгоритм движения α называется алгоритмом обхода по стимулам на классе конечных ориентированных графов Æ, если на любом графе G из класса Æ любое функционирование алгоритма движения α является конечным обходом по стимулам графа G.

Лемма.

Алгоритм движения ndfsm является алгоритмом обхода по стимулам на классе конечных графов, обладающих детерминированным сильносвязным полным остовным подграфом.

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

Предположим, что это не так. Тогда существует конечный граф G = ( VG, XG, EG ), обладающий детерминированным сильносвязным полным остовным подграфом, и функционирование e = ( e₁, e₂, …, e_n, … ) алгоритма ndfsm на этом графе такие, что e не является конечным обходом по стимулам графа G. Такое может быть в двух случаях: если функционирование e является конечным, но не является обходом по стимулам графа G, и если функционирование e является бесконечным.

1. Предположим, что функционирование e = ( e₁, e₂, …, e_n ) является конечным, но не является обходом по стимулам графа G. Тогда из определения функционирования следует, что α_ndfsm( A, v'_n, e ) = τ ⁹. Следовательно вершина v'_n является завершенной и в детерминированном пройденном подграфе G''_e не существует маршрута, ведущего из вершины v'_n в какую-либо из незавершенных пройденных вершин.

С другой стороны e не является обходом по стимулам графа G, то есть в графе G существует такая дуга ( v, x, v' ) EG, что не существует такого i { 1, … , n }, что v = v_i и x = x_i.

Рассмотрим детерминированный сильносвязный полный остовный подграф G' = ( VG', XG', EG' ) графа G. Так как подграф является остовным, то обе вершины v и v'_n принадлежат VG'. Так как граф G конечный, а его подграф G' - сильносвязный, то существует конечный маршрут f = ( f₁, f₂, …, f_k ), ведущий из v'_n в v. Пусть f_i = ( w_i, y_i, w'_i ). Тогда для всех i { 1, … , k } из вершины w_i в графе G выходит одна единственная дуга f_i, помеченная стимулом y_i. Предположим, что существует вторая такая дуга: ( w_i, y_i, w''_i ) EG. Тогда эта дуга также принадлежит и подграфу G' ( ( w_i, y_i, w''_i ) EG' ), так как подграф G' является полным остовным подграфом. А это противоречит тому, что подграф G' является детерминированным. Следовательно, наше предположение относительно существования второй дуги ( w_i, y_i, w''_i ) EG неверно и дуга ( w_i, y_i, w'_i ) является единственной дугой в графе G, выходящей из w_i и помеченной стимулом y_i.

Докажем индукцией по пути f = ( f₁, f₂, …, f_k ), что все вершины w'_i являются завершенными для i { 1, … , k }.

База индукции . Вершина w₁ = v'_n VG_e является завершенной, по определению функционирования и функции α_ndfsm.

Предположение индукции . Пусть вершина w'_i-1 = w_i является завершенной.

Шаг индукции . Так как вершина w_i является завершенной, стимул y_i является допустимым в этой вершине и дуга ( w_i, y_i, w'_i ) является единственной дугой, выходящей из w_i и помеченной стимулом y_i, то дуга ( w_i, y_i, w'_i ) также является пройденной, то есть ( w_i, y_i, w'_i ) e. Отсюда следует, что дуга ( w_i, y_i, w'_i ) принадлежит детерминированному пройденному подграфу G''_e, так как эта дуга является пройденной и детерминированной. На этом основании можно сделать вывод, что вершина w'_i является завершенной, так как в противном случае мы нашли маршрут ( f₁, f₂, …, f_i ) в детерминированном пройденном подграфе G''_e, ведущий из v'_n в одну из незавершенных пройденных вершин.

Мы доказали, что все вершины w'_i являются завершенными. Следовательно, и вершина w'_k = v VG_e также является завершенной, что противоречит нашему предположению о том, что e не является обходом по стимулам графа G. Следовательно, это предположение не верно и функционирование e не является конечным.

2. Предположим, что функционирование e = ( e₁, e₂, …, e_n, … ) является бесконечным. Тогда для всех i ≥ 0 α_ndfsm( A, v'_i, ( e₁, …, e_i ) ) ≠ τ.

Определим функцию β_G на графе G, устанавливающую соответствие между маршрутом ( e₁, …, e_i ) в графе G и парой натуральных чисел (b₁,b₂), следующим образом:

• b₁ равно числу дуг графа G, отсутствующих в маршруте ( e₁, …, e_i ), |EG \ { e₁, …, e_i }|;
• b₂ равно
  • 0, если i = 0, вершина v'_i является незавершенной или в детерминированном пройденном подграфе нет маршрута, ведущего из вершины v'_i и в какую-либо из незавершенных пройденных вершин;
  • минимальной длине маршрута в детерминированном пройденном подграфе, начинающегося в вершине v'_i и заканчивающегося в какой-либо из незавершенных пройденных вершин, в противном случае.

Определим на множестве пар натуральных чисел линейный порядок:
(b₁,b₂) < (b'₁,b'₂) b₁ < b'₁ (b₁ = b'₁ b₂ < b'₂)

Отметим, что множество пар натуральных чисел с данным линейным порядком образуют фундированное множество, то есть множество, в котором отсутствует бесконечно убывающая последовательность элементов.

Согласно определению β_G( () ) = (|EG|,0).

Покажем, что для любого префикса ( e₁, …, e_i ) функционирования e
β_G( ( e₁, …, e_i, e_i+1 ) ) < β_G( ( e₁, …, e_i ) )

Для всех i ≥ 0 α_ndfsm( A, v'_i, ( e₁, …, e_i ) ) ≠ τ. Следовательно, либо вершина v'_i не является завершенной, либо в детерминированном пройденном подграфе существует маршрут, ведущий из вершины v'_i в какую-либо из незавершенных пройденных вершин.

Рассмотрим первый случай. Если вершина v'_i не является завершенной, то α_ndfsm возвращает минимальный стимул из π(v), который не является пройденным в вершине v'_i. На этом основании можно сделать вывод, что e_i+1 является дугой, не принадлежащей { e₁, …, e_i }. Поэтому первый компонент β_G( ( e₁, …, e_i+1 ) ) на единицу меньше первого компонента β_G( ( e₁, …, e_i ) ), откуда следует, что β_G( ( e₁, …, e_i, e_i+1 ) ) < β_G( ( e₁, …, e_i ) ).

Рассмотрим второй случай. Если вершина v'_i является завершенной и в детерминированном пройденном подграфе существует маршрут, ведущий из вершины v'_i в какую-либо из незавершенных пройденных вершин, то α_ndfsm возвращает стимул, приписанный к дуге e_j пройденного маршрута, которая обладает минимальным индексом среди всех дуг, являющихся первыми дугами в кратчайших маршрутах детерминированного пройденного подграфа, ведущих из текущей вершины в какую-либо из незавершенных пройденных вершин. При этом дуга e_i+1 может либо совпасть c дугой e_j, либо нет.

Если дуга e_i+1 совпадает c дугой e_j, то уменьшается на единицу второй компонент функции β_G, так как кратчайший маршрут в детерминированном пройденном подграфе станет на одну дугу короче, или же в результате перехода будет достигнута незавершенная вершина. При этом первая компонента функции β_G останется неизменной, поэтому β_G( ( e₁, …, e_i, e_i+1 ) ) будет меньше β_G( ( e₁, …, e_i ) ).

Если дуга e_i+1 не совпадает c дугой e_j, то эта дуга не принадлежит { e₁, …, e_i }, так как в противном случае дуга e_j не была бы частью детерминированного пройденного подграфа. Следовательно первый компонент β_G( ( e₁, …, e_i+1 ) ) на единицу меньше первого компонента β_G( ( e₁, …, e_i ) ), то есть β_G( ( e₁, …, e_i, e_i+1 ) ) < β_G( ( e₁, …, e_i ) ).

Мы показали, что для всех i ≥ 0 β_G( ( e₁, …, e_i, e_i+1 ) ) < β_G( ( e₁, …, e_i ) ). Следовательно функционирование e не может быть бесконечным, так как в противном случае последовательность β_G( ( e₁, …, e_i ) ) образует бесконечно убывающую подпоследовательность в фундированном множестве.

Алгоритм движения ndfsm позволяет заменять стандартный алгоритм dfsm, в тех случаях когда отдельные сценарные функции имеют недетерминированную природу, а другие гарантировано обеспечивают детерминированное движение по графу.

Определение 21.

Асинхронным тестовым сценарием ndfsm относительно асинхронной модели требований A = ( V, X, Y, Z, E ) с множеством стабильных состояний V_S V и начальным состоянием v₀ V_S, называется стационарный автоматный тестовый сценарий, в котором в качестве алгоритма движения по графу сценария используется алгоритм обхода α_ndfsm.

Параллельные воздействия на целевую систему

Асинхронные тестовые сценарии, рассмотренные ранее, не предоставляют разработчику тестов никакой автоматизации в осуществлении параллельных тестовых воздействий на целевую систему. Чтобы выполнять параллельные тестовые воздействия в стационарных автоматных тестовых сценариях необходимо вручную описывать правила их осуществления.

В данном разделе мы рассмотрим возможные варианты осуществления параллельных тестовых воздействий в автоматизированном режиме. В качестве таких вариантов были выделены следующие возможности:

• параллельная работа независимых тестовых сценариев;
• параллельное выполнение сценарных функций в рамках работы одного тестового сценария;
• организация параллельных воздействий на уровне сценарных функций.

Наиболее высокий уровень на котором можно организовать параллелизм - это уровень тестовых сценариев. Несколько тестовых сценариев можно запустить независимо друг от друга при условии, что каждый из них будет работать со своей собственной копией модельного состояния. Если отсутствие учета влияния параллельно работающих тестовых сценариев не может привести к ошибкам в оценке корректности поведения целевой системы, то тогда такой независимый запуск сценариев является корректным и может быть использован для того, чтобы удостовериться, что такие параллельные активности в целевой системе не приводят к аномальному поведения.

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

Другим вариантом организации параллельной работы сценарных функций может быть комбинация нескольких тестовых сценариев, работающих с общим модельным состоянием. В этом случае работа теста также должна выполняться в двух режимах. В одном режиме работает только одна сценарная функция одного из сценариев, а в другом происходит параллельный запуск нескольких сценарных функций.

Общий недостаток рассмотренных выше подходов заключается в слишком большом удалении уровня параллелизма от целевой системы. Параллелизм на уровне тестовых сценариев и сценарных функций не может гарантировать параллельного выполнения функций целевой системы и, таким образом, не позволяет обеспечить даже минимального уровня тестирования одновременной работы компонентов целевой системы.

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

Обращения к такому управляющему механизму можно осуществлять непосредственно из асинхронных сценарных функций. В результате разработчик тестового сценария получает возможность управлять не только набором модельных воздействий, предназначенным для одновременного выполнения, но и перебирать различные параметры такого выполнения.

Рассмотрим пример системы с асинхронным интерфейсом, в которой асинхронность проявляется как возможность блокировки вызовов отдельных интерфейсных функций вплоть до наступления некоторого события, например, вызова другой интерфейсной функции системы в параллельном потоке управления. Такая целевая система предполагает работу с общими данными из различных потоков управления. Поэтому проверка корректности синхронизации доступа к общим данным является необходимой составляющей качественного тестирования. Для осуществления такой проверки требуется организовать параллельное выполнение кода, осуществляющего доступ к общим данным, в нескольких потоках управления и обеспечить переключение этих потоков в процессе выполнения тестируемого кода.

В данном примере, управляющий механизм может быть построен на основе имеющейся информации о работе планировщика потоков операционной системы. В качестве указаний со стороны сценарных функций механизм может получать набор целевых функций, которые необходимо выполнять параллельно, а также итерируемые значения параметров, управляющих переключениями потоков.

Таким образом, предлагается отказаться от разработки универсального способа организации параллельных воздействий, так как нет оснований полагать, что такой метод может обеспечить требуемый уровень качества тестирования. Вместо этого предлагается разрабатывать специализированные механизмы организации параллельных воздействий, общие для определенных классов целевых систем, и обращаться к этим механизмам непосредственно из сценарных функций.

Такое решение оказывает минимальное влияние на архитектуру тестового набора. Оно влечет появление опционального компонента, ответственного за организацию параллельных воздействий. Через этот компонент некоторые асинхронные сценарные функции могут управлять генерацией тестовых воздействия, в то время как другие сценарные функции могут осуществлять тестовые воздействия самостоятельно.