Методика генерации тестов для протоколов информационного обмена на основе недетерминированного конечного автомата с предикатами

Размещено на http://www.allbest.ru/

Методика генерации тестов для протоколов информационного обмена на основе недетерминированного конечного автомата с предикатами

Парамохина Т.М.

Еременко А.В.

The methods of test generation for information exchange protocols based on pseudo-equivalence criterion of not determined final automatic device (NDFAD) are described in the article. Search of unique sequence in NDFAD, search of unique entrance area and procedures of identification of conditions NDFAD which allowed to estimate the maximal length of covering sequence and to optimize search procedure of transition covering are considered.

протокол автомат информационный

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

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

Вместе с тем большинство современных ПИО описываются моделью конечного автомата только приближенно, что существенно сокращает возможности использования данной модели. Более точное и компактное описание ПИО можно получить на основе модели недетерминированного конечного автомата с предикатами в виде целочисленных линейных неравенств (НКА с предикатами), рассматривая несколько отдельных переменных, совокупность которых описывает состояние протокола, а также выделяя параметры во входных и выходных сигналах.

Для конечных автоматов разработан ряд методов генерации тестовых последовательностей: уникальных последовательностей (УП); различающих последовательностей и характеристических последовательностей [1]. По типу описываемого протокола данные методы можно разделить на методы, использующие сигнал «надежного сброса», и методы, не использующие сигнал «надежного сброса». Функция «надежного сброса», как правило, присутствует в современных технических средствах в виде возможности выполнения цикла включения/выключения (или перезагрузки устройства). В процессе перезагрузки оперативная память средства информационного обмена (СИО) в силу конструктивных особенностей гарантированно очищается, поэтому факт возврата в исходное состояние при перезагрузке не требует дополнительной проверки.

Оценивая количество циклов перезагрузки, которые включают в себя тесты, построенные с использованием УП (UIO-метод, W-метод) и отвечающие критерию n-покрытия, установлено, что тест, полученный W-методом, содержит (n2 + n2p) сигналов "надежный сброс", тест, полученный UIOv-методом, содержит n2L+np сигналов "надежный сброс". Учитывая, что количество состояний и количество различных входных сигналов в ПИО может достигать нескольких десятков, количество сигналов «надежный сброс» в тесте может достигать нескольких сотен. Как правило, в современных СИО цикл перезагрузки занимает достаточно длительное время - от нескольких секунд до нескольких минут. В таких случаях большую часть времени исполнение теста будет приходиться на перезагрузки. Часто перезагрузить СИО можно только по команде с консоли управления либо разрывая его цепи питания, что затрудняет исполнение теста в полностью автоматическом режиме. Поэтому тесты, использующие сигнал «надежный сброс» как можно меньше, являются более предпочтительными с практической точки зрения.

Для тестирования протоколов без функции "надежный сброс" были предложены модификации W-метода и UIOv-метода [2]. Данные методы значительно сложнее своих аналогов, использующих "надежный сброс". В то же время более простые методы не позволяют в теории достичь 100%-го покрытия при критерии псевдо-эквивалентности. Ниже проведены результаты исследования покрытия версии метода УП для протоколов без сигнала "надежный сброс", показывающие, что метод УП позволяет при сохранении относительной простоты и тестах небольшой длины достичь практически 100%-го покрытия.

Рассмотрим процедуру построения УП для недетерминированного конечного автомата. Будем считать, что НКА полностью определен. Отношение переходов h1(s, б) возвращает множество состояний, в которые входная последовательность может перевести автомат, первоначально находящийся в состоянии s. Отношение выходов h2(s, а) возвращает множество выходных последовательностей, которое может выдать автомат при подаче на него в состоянии s входной последовательности а. d-последовательностью автомата, переводящей автомат из состояния si в состояние sj, будем называть aij:

h1(si, aij) =sj;

|h1 (sj, aij)| = 1;

|h2(si, aij)| = 1.

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

Уникальная последовательность для состояния si, используемая в детерминированном безусловном тесте, должна обладать следующими свойствами:

1) детерминированностью: |h1(si, )| = 1;

2) уникальностью: не существует такого состояния s', в котором для входной последовательности может быть получена выходная последовательность, идентичная выходной последовательности для состояния s:

Путем НКА назовем последовательность смежных переходов. Пусть Т* - множество путей автомата. Т1 - множество путей графа автомата, имеющих длину 1; Т1 Т*. Рассмотрим ряд вложенных разбиений множества Т1, позволяющих выделить УП.

DS-группой назовем подмножество путей, исходящих из состояния s и помеченных входной последовательностью б:

= {psб: psб П(s, б)}.

D-группой назовем множество всех DS-групп:

Da = { , s S}.

По определению количество элементов D-группы больше либо равно количеству состояний.

D-разбиением назовем множество D-rpynn:

D1 = {Da; б X1}.

D-группу Da назовем si-уникальной, если существует принадлежащая ей DS-группа, состоящая из одного пути, причем выходная последовательность, помечающая этот путь, не совпадает с выходными последовательностями, помечающими остальные пути в данном автомате:

Рассмотрим алгоритм поиска УП в недетерминированном автомате.

Обозначения:

D, Е - D-группы;

D_QUEUE - очередь D-rpynn;

UTO - множество УП;

IS_FULL(UIO) - функция, возвращающая 1, когда множество уникальных последовательностей содержит как минимум по одной УП для каждого состояния и 0 в противном случае;

EXTRACT_UIO(D) - функция, выделяющая УП из s-уникальной D-группы;

X = {х1 .., хm} - множество входных сигналов;

S = {s1, .., sn} - множество состояний;

IS_UNIQUE(D) - функция, возвращающая 1, когда D-группа D является уникальной;

PATH (D, i) - функция, возвращающая путь р в i-й паре <р, в> P(D);

EXTEND(p, x) - функция, возвращающая множество путей, полученных добавлением к пути р дуги, помеченной входным сигналом х.

Алгоритм 1. Поиск набора уникальных последовательностей для НКА

1. D:=0

2. D_QUEUE D

3. while IS_FULL(UIO)=0

4. D D_QUEUE

5. if (IS_UNIQUE(D)) UIO EXTRACT_UIO(D)

6. for j:=l,.., m do

7. E:=0

8. for i:=l,.., |D| do

9. p:=PATH(Di)

10. E EXTEND(p,j)

11. endfor

12. E=PARTITION(E)

13. D_QUEUE E

14. endfor

15. endwhile

Рассматриваемый метод УП отличается от UIOv-метода отсутствием проверки наличия n состояний, для которых найденные УП сохраняют уникальность. Сегменты теста, проверяющие отдельные переходы, не разделяются сигналами "сброс", а "склеиваются" в единую последовательность. Ниже представлена процедура получения УП-теста.

1. Tseg:=Ш

// тестируем все nр переходов

2. for j:=l,.., n do

3. for i:=l,.., p do Tseg := Tseg @ Qд(1>Tseg), i @ <i/л(j, i)> @ UIOд(j, i)

Оценка покрытия теста выполнялась с помощью вычислительного эксперимента, в процессе которого генерировались автоматы с внесенной по отношению к эквивалентной модели ошибкой. Для сгенерированных автоматов эмулировалось выполнение теста. Результаты эксперимента позволяют сделать вывод, что для автоматов, моделирующих ПИО, метод УП без использования сигнала «надежный сброс» позволяет достичь 99,99%-го покрытия с доверительной вероятностью 0,99.

Это позволяет рассмотреть НКА с предикатами в виде целочисленных линейных неравенств (далее НКА с предикатами); может рассматриваться, как упрощенная модель расширенного автомата и использоваться для построения частичного теста расширенного автомата.

На рис.1 показан пример расширенного автомата и включающего его недетерминированного автомата. При представлении расширенного автомата недетерминированным автоматом УП найденные для недетерминированного автомата будут оставаться уникальными и для расширенного автомата. Для нахождения УП может использоваться алгоритм 1. Как видно из примера, приведенного на рис. 1, для расширенного автомата существует множество включающих его НКА, различающихся размером входного алфавита. В общем случае максимальный размер входного алфавита будет составлять |I|, где I - множество входных сигналов расширенного автомата. УП существуют практически для всех известных детерминированных конечных автомаов, моделирующих протоколы информационного обмена [4].

Расширенный автомат Е.

Недетерминированные автоматы, покрывающие расширенный автомат Е

Рисунок 1 - Пример расширенного автомата и покрывающих его недетерминированных конечных автоматов.

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

Однако, если разбиение множества глобальных состояний расширенного автомата уже задано (например, определено SDL-описанием), то можно предложить следующий критерий ограничения мощности разбиения множества входных сигналов:

Для идентификации состояний в НКА с предикатами введем аналог уникальной последовательности - уникальной входной области (УВО). УВО можно интерпретировать следующим образом: не существует таких начальных состояний (s0, ), (si, ) и входных последовательностей , что, подавая на НКА с предикатами в состоянии (s0, ), a на НКА с предикатами в состоянии (si, ), будут получены одинаковые выходные последовательности. На основе представленного алгоритма поиска УП для НКА можно построить алгоритм поиска УВО для НКА с предикатами. Единственным различием в алгоритмах поиска УП для НКА и УВО для НКА с предикатами будет реализация функции IS_UNIQUE.

Процедура построения тестового комплекта состоит в следующем: тестовая последовательность состоит из m сегментов, идентифицирующих отдельные переходы НКА с предикатами, где m - общее количество переходов НКА с предикатами. Каждый сегмент состоит из преамбулы, шага эксперимента и постамбулы. Преамбула переводит объект в исходное состояние тестируемого перехода; шаг эксперимента выполняет тестируемый переход; с помощью постамбулы выполняется идентификация конечного состояния перехода.

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

- TS = < In, Out >;

- In = < x > - входная последовательность;

- Out = <y >0 - выходная последовательность.

Можно доказать, что необходимым условием применимости разработанной процедуры является выполнение свойства «корректности» НКА с предикатами.

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

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

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

ЛИТЕРАТУРА

1. Еременко В.Т. Моделирование процессов информационного обмена в распределенных управляющих системах: Монография./ Под общ. Редакцией И.С. Константинова. - М.: Машиностроение-1, 2004.- 224с.

2. Еременко В.Т. Концепция обнаружения и коррекции логических ошибок в реализациях профилей протоколов безопасности // Телекоммуникации - 2003. - №8. - С.30-35.

3. Еременко В.Т., Парамохина Т.М. Методика оценки неопределенных данных при аттестационном тестировании реализации профилей протоколов информационного обмена // Вестник компьютерных и информационных технологий - 2005. - №8. - с.45-48.

4. Фунтиков В.Б. Проблемы автоматизированного построения аттестационных тестов для протоколов передачи данных. - сборн. «Перспективы развития российского сегмента Интернет», деп. в ЦНТИ «Информсвязь», №2166 от 14.04.2000. - с.38-49.

Размещено на Allbest.ru