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

На правах рукописи

Дорофеева Маргарита Юрьевна

ИССЛЕДОВАНИЕ И РАЗРАБОТКА КОНЕЧНО-АВТОМАТНЫХ МЕТОДОВ СИНТЕЗА ПРОВЕРЯЮЩИХ ТЕСТОВ ДЛЯ УПРАВЛЯЮЩИХ СИСТЕМ

05 13 01 - Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

Автореферат диссертации на соискание ученой степени кандидата технических наук

□0307 15 1Б

Томск-2007

003071516

Работа выполнена на кафедре информационных технологий в исследовании дискретных структур ГОУ ВПО «Томский государственный университет»

Научный руководитель: доктор технических наук,

профессор Евтушенко Нина Владимировна

Официальные оппоненты:

доктор технических наук, профессор

Матросова Анжела Юрьевна

кандидат физико-математических наук Бурдонов Игорь Борисович

Ведущая организация:

Институт вычислительного моделирования СО РАН, Красноярск

Защита состоится 24 мая 2007 г. в 10 30 на заседании диссертационного совета Д 212.267 12 при ГОУ ВПО «Томский государственный университет» по адресу 634050, г Томск, пр Ленина, 36

С диссертацией можно ознакомиться:

В Научной библиотеке Томского государственного университета по адресу: г. Томск, пр Ленина, 34а

Автореферат разослан: 23 апреля 2007 г.

Ученый секретарь диссертационного совета

д т.н, профессор Цо^ В И Смагин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Конечные автоматы широко используются в качестве математической модели при синтезе тестов для контроля правильности функционирования управляющих систем, в частности, при синтезе проверяющих тестов для телекоммуникационных протоколов, а в последнее время и при тестировании программного обеспечения Тестирование осуществляется путем подачи на вход системы определенных последовательностей входных воздействий -тестов и наблюдения выходных реакций системы с последующим их анализом Качественный тест, с одной стороны, должен обнаруживать все наиболее вероятные неисправности в системе, а с другой стороны, быть достаточно коротким, чтобы анализ правильности функционирования системы происходил в реальном времени Сложность управляющих систем постоянно возрастает, соответственно длина качественных тестов постоянно увеличивается Автоматная модель является очень привлекательной для построения качественных тестов, т к существуют методы построения тестов, которые не требуют явного перечисления возможных неисправностей Тестирование управляющих систем автоматными методами активно развивалось в работах МП Василевского, И С Грунского, Н В Евтушенко, А Ф Петренко, Б Д Лукьянова, А Ю Матросовой, И Б Бурдонова, А С Косачева, В В Кулямина, Т Чоу, Г Бокмана, Д Ли, М Янакакиса, С Вуонга, К Сабнани и других авторов Однако, несмотря на большое количество исследований по синтезу проверяющих тестов для автоматов, задача далека от того, чтобы считаться решенной, т к практически все известные методы без явного перечисления возможных неисправностей относительно так называемых моделей «черного и серого ящиков» доставляют проверяющие тесты с большой избыточностью Поэтому разработка методов синтеза проверяющих тестов для автоматной модели с целью построения безызбыточных тестов или тестов с минимальной избыточностью остается актуальной

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

Методы исследования. Для решения поставленных задач применяется аппарат теории автоматов, математической логики, а также компьютерные экспе-

рименты для исследования методов построения проверяющих тестов, в том числе, для оценки эффективности предложенных методов.

Научная новизна.

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

2) Установлены достаточные условия полноты проверяющих тестов для недетерминированных автоматов относительно отношений эквивалентности и редукции На основе предложенных достаточных условий Я-метод адаптирован для проверки этих отношений для случая, когда эталонный автомат является недетерминированным

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

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

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

Реализация полученных результатов. Исследования, результаты которых изложены в диссертации, проводились, в частности, в рамках работ по программе МО РФ «Научные исследования высшей школы в области производственных технологий» (2000 г.), в рамках проекта МО РФ Е00-2 0-33 «Исследование отношений редукции и эквивалентности между недетерминированными автоматами» (2001-2002 гг), а также в рамках федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 годы по приоритетному направлению «Развитие

инфраструктуры». НИР «Экспериментальное исследование методов синтеза проверяющих тестов для детерминированных автоматов» (2005 г.), НИР «Тестирование программного обеспечения телекоммуникационного оборудования на основе автоматных моделей» (2005 г.), НИР «Пассивное тестирование элементов телекоммуникационных систем с возможностью обнаружения несанкционированного доступа к системе» (2006 г).

Апробация работы. Научные результаты, составившие основу данной работы, обсуждались на заседаниях объединенного семинара кафедры информационных технологий в исследовании дискретных структур радиофизического факультета, кафедры защиты информации и криптографии и кафедры программирования факультета прикладной математики и кибернетики ТГУ Полученные результаты докладывались на следующих конференциях ]) III всероссийская конференция с международным участием «Новые информационные технологии в исследовании дискретных структур», Томск, 2000 г.; 2) VII международная конференция «Теория и техника передачи, приема и обработки информации», Туапсе, 2001 г., 3) IV (V, VI) всероссийская конференция с международным участием «Новые информационные технологии в исследовании сложных структур», Томск, 2002 г (Иркутск, 2004 г, Шушенское, 2006 г ), 4) международная конференция молодых ученых по математическому моделированию и информационным технологиям, Новосибирск, 2002 г , 5) П сибирская научная школа-семинар с международным участием «Проблемы компьютерной безопасности и криптографии», посвященная 125-летию основания Томского государственного университета, Томск, 2003 г, 6) 3rd IEEE International Conference on Software Engineering and Formal Methods, Koblenz, Germany, 2005; 7) 23th IFIP International Conference on Formal Techniques For Networked and Distributed Systems, Taipei, Taiwan, 2005

Структура и объем диссертации. Диссертация состоит из введения, 5 глав, заключения и списка используемой литературы Объем диссертации составляет 160 страниц текста, набранного в редакторе MS Word 2000 (шрифт - Times New Roman, размер шрифта - 14 pt, межстрочный интервал - 1 5 строки), в том числе титульный лист — 1 стр, оглавление - 4 стр, основной текст, включающий 22 рисунка и 5 таблиц, — 143 стр, библиография из 77 наименований - 9 стр, приложение - 8 стр.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Конечные автоматы представляют специальный класс функций, которые сопоставляют каждому слову во входном алфавите одно или несколько слов той же длины в выходном алфавите Формально под конечным, возможно, недетерминированным автоматом понимается пятерка 5={5,Х, где 5 -конечное непустое множество состояний с выделенным начальным состоянием 5Ь X и У - конечные входной и выходной алфавиты соответственно, а

/?5с:5хАгх,5,х У - отношение поведения Если для каждой пары (.?,*) е5хЛ" существует хотя бы одна пара {б' ,у) вБу.У, такая что ,.у)е/г5, то автомат называется полностью определенным Если для любых (я,х,у)^8хХхУ в автомате существует не более одного состояния ¿'еЗ такого что (5,х,х',>,)е/25, то автомат называется наблюдаемым. Автомат называется детерминированным, если для всех отношение Аг содержит не более одного перехода из ^

под действием х В детерминированном полностью определенном автомате вместо отношения поведения обычно используют функцию переходов и функцию выходов 8$. и 5хА'—»К Отношение поведения, функции переходов и выходов обычным образом распространяются на входные и выходные последовательности Пара а1р называется входо-выходной последовательностью автомата в состоянии я, если существует состояние такое, что четверка

(ж,аг,уб)е/15, вэтомслучаеу0еомг(5Ьа), т е ои((51,а) есть множество выходных последовательностей, которые автомат в состоянии ^ | может выдать на входную последовательность а Автомат /=(1,Х,У,к/,ц) называется подавтоматом автомата 5=(5,А',7,/г5,50, если /о?, гг^ь и /г/сй^ Полностью определенные автоматы 5 и / эквивалентны, 5к/, если их реакции на любую входную последовательность совпадают, те VаеХ* [ои/(гь«)=ом/(5ьа)]; в противном случае автоматы различимы Последовательность аеХ*, для которой справедливо называется различающей последовательностью Ав-

томат /естьредукция автомата Б, /<5, если УаеЛГ* [оы^(/ьОг)сом?(л,,«)] Если существует последовательность а^Х*, для которой справедливо ои((1иа)<Хои^1,а), то а называется г-различающей последовательностью В задачах тестирования отношения редукции и эквивалентности используются в качестве отношений конформности (соответствия) между проверяемой и эталонной системами Автомат 5 называется приведенным, если любые два состояния автомата различимы Известно, что для любого полностью определенного недетерминированного автомата существует эквивалентный ему приведенный (наблюдаемый) автомат, который называется приведенной (соответственно наблюдаемой) формой автомата Автомат 5 называется связным, если в нем для каждого состояния я е 5 существует последовательность, переводящая автомат из начального состояния в состояние 5 Множеством достижимости V связного автомата называется множество входных последовательностей, переводящих автомат из начального состояния в каждое состояние

Как обычно, под моделью неисправности понимается тройка <5,~,£2>, где 5 - эталонный автомат, описывающий поведение эталонной системы, £2 - область неисправности, т е множество автоматов, которые описывают поведение систем со всеми интересующими нас неисправностями, и--отношение

конформности, характеризующее критерий исправности проверяемого автомата Проверяемый автомат /считается исправным (конформным), если 1-5. Конечное множество ТБ конечных входных последовательностей эталонного автомата называется полным проверяющим тестом относительно модели

<5,~,С2>, если для всякого автомата /еО, /-+-5", найдется последовательность а из ТБ, по реакции на которую автомата / этот факт можно обнаружить, т е.

/+а5 В параграфе 1 4 рассмотрены две наиболее часто используемые модели неисправности - модели «черного и серого ящиков» В случае модели «черного ящика» в качестве области неисправности рассматривается множество Зт{Х, У) всех конечных автоматов с числом состояний не больше, чем т, т е модель «черного ящика» есть тройка <5,=,Зт(Х,У)> При использован™ модели «серого

ящика» <5,=,БиЬ(0)> предполагается, что известна некоторая информация о структуре переходов в проверяемом автомате В этом случае область неисправности БиЬ^О) есть множество всех детерминированных полностью определенных подавтоматов специального недетерминированного мутационного авто-

7

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

<5,=,Зт{Х,У)> наиболее известными являются IV-, ОБ-, 1ЛО-, ШОу-, НБ1-, 1¥р-методы. Основой теста, построенною любым из этих методов, является множество последовательностей ИХ*"""*1, где V есть множество достижимости эталонного автомата, т - число состояний проверяемого автомата, п - число состояний эталонного автомата. Однако соответствие между состояниями и переходами в проверяемом и эталонном автоматах устанавливается различными способами. Для установления такого соответствия в ^-методе используется множество различимости эталонного автомата, в ЯХЛ-методе - семейство гармонизированных идентификаторов, в £)5-методе - диагностическая последовательность и тд Вопросы об избыточности тестов, построенных различными методами, а также об эффективном выборе последовательностей, различающих состояния эталонного автомата и позволяющих строить оптимальные тесты, до сих пор остаются слабо исследованными В то же время известно, что тест, построенный посредством перебора всех автоматов из области неисправности, является безызбыточным в том смысле, что каждая входящая в него последовательность обнаруживает хотя бы один автомат из области неисправности, и соответственно такой тест по длине близок к оптимальному тесту. В случае, когда эталонная и проверяемая системы имеют недетерминированное поведение, в качестве отношений конформности используются отношения эквивалентности и редукции Известные 0¥р- и 5'С-методы построения тестов относительно данных моделей являются обобщением \Ур- и Ж7-методов для детерминированных автоматов, и соответственно имеют похожую структуру, в частности, различающие последовательности строятся заранее перед синтезом теста В случае, когда известна некоторая информация о структуре переходов в проверяемом автомате, тесты можно строить относительно модели «серого ящика», те относительно модели <5,~,8иЬ(0)> Наиболее известные методы синтеза проверяющих тестов относительно данной модели разработаны для случая, когда эталонный и мутационный автоматы имеют одинаковое число состояний (Петренко А Ф, Грунский И С., К Эль-Факи, Евтушенко Н В ) Для случая, когда мутационный автомат имеет больше состояний, чем эталонный автомат, метод синтеза проверяющего теста предложен в работе Куфаревой И Б

8

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

Вторая глава диссертации посвящена экспериментальному исследованию

методов построения проверяющих тестов относительно модели <5,=,^Ут(Х,Т)>,

в которой 5 - детерминированный приведенный полностью определенный автомат Для проведения экспериментальных исследований был реализован генератор конечных автоматов и создан программный комплекс, в который вошли программы по построению тестов известными методами В параграфе 2 1 исследуются свойства генератора случайных автоматов и делается вывод о том, что реализованный генератор доставляет автоматы с достаточно «хорошими» параметрами, влияющими на длину проверяющего теста В частности, длины различающих последовательностей и последовательностей в множестве достижимости в генерируемых эталонных автоматах являются достаточно короткими Параграф 2 2 посвящен оценке избыточности тестов, построенных без перебора автоматов множества Зт(Х, У) Экспериментально показано (рисунок 1), что даже для небольших автоматов (л<5) тесты, построенные без перебора автоматов из множества Зт(Х,Г), являются избыточными относительно теста, построенного посредством перебора проверяемых автоматов Эксперименты по построению теста посредством перебора автоматов из множества Зт(Х,У) для автоматов с большим числом состояний провести не удалось вследствие огромного количества автоматов множества Зт(Х,У)' |Ди(Х,}/)|=(т|)/|)'я'*4. Согласно проведенным экспериментам, структура теста при случайном переборе автоматов из области неисправности аналогична структуре тестов, доставляемых методами без перебора проверяемых автоматов. Таким образом, длина теста существенно зависит от используемых в тесте различающих последовательностей для проверки необходимого соответствия между состояниями эталонного и проверяемого автоматов

В параграфе 2 3 проводится экспериментальное исследование IV-, \¥р-, ШО-, ШОу-, Д^-методов построения тестов на одном и том же множестве случайно сгенерированных автоматов На рисунке 2 приведены отношения длин тестов, доставляемых ШО-, 1Ур-, //57-методами к длине теста, доставляемого ^-методом Эксперименты показали, что это отношение практически не зависит от размеров эталонного автомата Длина ШО-теста в среднем составляет 30% от длины й^-теста, длины Шр-, //5/-тестов - 60%. При увеличении числа состояний проверяемого автомата это отношение возрастает Заметим, что ШО- и £)5-методы доставляют тесты с наименьшей избыточностью Однако, диагностическая последовательность, используемая при построении теста £>5-методом, существует для 30% случайно сгенерированных автоматов, а тесты, доставляемые ¡У/Ометодом, в большинстве случаев не являются полными

0 7 г --■■■

180 300 400 360 600 360 480 800 720 600 1000 Количество переводов в автомате

Рисунок 2 - Отношение длин ШО-, №р-(Я57) тестов к длине К-теста

Таким образом, из рассмотренных методов, применимых к любому связному приведенному автомату, самые короткие тесты доставляют 1Ур- и НБ1-методы В параграфе 2 4 известные методы построения тестов применяются к

реальным протоколам, а именно к протоколу Simple Connection (SCP) и к протоколу V 76. Полученные результаты не противоречат экспериментам со случайно сгенерированными автоматами в том смысле, что отношения между длинами тестов, построенных различными методами, для случайно сгенерированных автоматов и для автоматов, описывающих протоколы, сохраняются. Третья глава диссертации посвящена исследованию достаточных условий

полноты проверяющего теста относительно модели <S,=,3m(X,Y}> и разработке метода, который позволяет строить тесты, близкие к оптимальным, на основе более эффективного использования последовательностей, различающих состояния эталонного автомата В параграфе 3 1 устанавливаются новые достаточные условия полноты проверяющего теста, построенного относительно модели <S, =, Зт(Х, У)>

Теорема 1. Пусть TS - множество входных последовательностей эталонного автомата 5= (S>X, Y, 8s, Л t), содержащее подмножество VX"~n'\ где V-множество достижимости автомата S Множество TS является полным проверяющим тестом относительно модели <S,=,3m(X,Y)>, если выполняются следующие условия: 1) для любых двух (различных) состояний автомата 5, достижимых по последовательностям а и Д из V, множество TS содержит последовательности am и Р&, где со есть последовательность, различающая состояния Ssis^a) и £$(5, ,Д), 2) для любой последовательности аД ае V, \Д=т-п+], и каждого непустого начального отрезка Р\ последовательности Д который переводит автомат 5 из состояния Ss(s j, а) в состояние s, множество TS содержит последовательности аР\ а) и ут, где уе V, Ss(svf)^s, и а есть последовательность, различающая состояния S£svap{) и Ss(spy), 3) для любой последовательности огД ае V, |Д]=/и-и+1, и любых двух непустых начальных отрезков Д и Д последовательности Д таких, что S^svap\)^S£sv арт), множество TS содержит последовательности архсапаРгЮ, где со- последовательность, различающая состояния аД) и&Су^сгД)

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

параграфе 3 2 на основе установленных достаточных условий предлагается метод построения полного проверяющего теста относительно модели

<S,=,3m(X,Y)>. В разделе 3 2 1 рассматривается несколько стратегий перебора последовательностей множества VX™'"*1 для добавления к ним соответствующих различающих последовательностей, так чтобы полученный тест был оптимальным Предлагаются функции вычисления цены продолжения двух последовательностей На основе теоремы 1 и исследований раздела 3 2.1 в разделе 3 2 2 предлагается Я-метод построения полного проверяющего теста относительно модели «черного ящика».

Алгоритм 1. //-метод построения теста

Вход: Связный детерминированный эталонный автомат Y,Ss,i)

с n состояниями, префикс замкнутое множество достижимости V, число состояний т проверяемого автомата, т>п

Выход: Полный проверяющий тест относительно модели <S,=, Зт(Х, К)> Шаг 1. Строим множество последовательностей TS= VPrejlX"'"'') Шаг 2. Для каждой пары последовательностей а„ a¡&V проверяем, содержит ли множество TS последовательности а, а и а}со, где со различает состояния Sj(s},a,) и Sdsi,0Cj) Если для некоторой пары таких последовательностей в TS нет, то включаем в TS последовательности а,со tí a¡a>

Шаг 3. Для каждой пары последовательностей а,Ре VPrefiX™'"*1), а,е V, и Gj, ctj& V, S^svaj)^s, проверяем, содержит ли множество TS последовательности афт и oíjCü, где ©различает состояния S£s\,a,P) и 8£sva¡) Если для некоторой пары таких последовательностей в TS нет, то включаем в TS последовательности afleo ч а ¡со

Шаг 4. Для каждой последовательности афе VPrefiX"'"n), а,е V, рассматриваем все пары непустых префиксов Д и ^ последовательности /? такие, что

Ss(si,a,/3i)J=Ss(s\,а,/32) Проверяем, содержатся ли в тесте последовательности а,Р\ а> и а,Рг су, где со - последовательность, различающая состояния 8&иаф\) и 8^\,аф2) Если для некоторой пары Д и таких последовательностей в TS нет, то включаем в TS последовательности а,рхсо и а,ргю

Теорема 2. Пусть S - связный приведенный детерминированный автомат Множество последовательностей TS, построенное в результате выполнения ша-

гов алгоритма 1, является полным проверяющим тестом относительно модели <5,=,Зт(Х,Г)>.

Таким образом, различающие последовательности в //-методе, который гарантирует полноту теста относительно модели <5,=,Зт(Х,Г)>, строятся не заранее, как в известных методах, а в процессе построения теста с использованием информации об уже построенной части теста

В параграфе 3 3 эффективность предложенного метода оценивается посредством компьютерных экспериментов Проведенные эксперименты показали, что в среднем для небольших автоматов длины тестов, построенных //-методом и методом, основанным на переборе всех автоматов из множества Зт(Х,Т), совпадают (рисунок 3)

Число СОСТОЯНИЙ п

Рисунок 3 - Избыгочность теста, построенного Я-методом

Длина Я-теста в среднем составляет 66% от длины Я57-теста в случае, когда число состояний проверяемого и эталонного автоматов совпадают Как показывают эксперименты, это отношение практически не зависит от размеров эталонного автомата и при увеличении числа состояний проверяемого автомата выигрыш от использования Я-метода по сравнению с #57 увеличивается Результаты, полученные при использовании Я-метода для протоколов БСР и V 76, также показали, что соотношение между длинами тестов, построенных Я-и Я5/-методами, сохраняется В разделе 3 4 Я-метод адаптируется для случая, когда эталонный автомат является частичным

В четвертой главе рассматривается задача построения полного проверяющего теста относительно моделей <5,<,Дя(Х,У)> и <5,~,От(Х,У)> при недетерминированном автомате 5 В основе предлагаемых методов лежит общий подход, когда различающие последовательности строятся в процессе построе-

ния теста В параграфе 4 2 рассматривается модель <5,~,С1т(Х,У)>, где 5- недетерминированный эталонный автомат, й1т(Х,У) - множество всех полностью определенных, в том числе, недетерминированных автоматов, наблюдаемая форма которых имеет не более т состояний При построении тестов предполагается, что все возможные реакции недетерминированного проверяемого автомата на входную (тестовую) последовательность можно пронаблюдать в процессе многократной подачи этой тестовой последовательности В параграфе 4 2 формулируются достаточные условия полноты теста относительно модели

<5,=,0.т(Х,У)> Аналогично случаю детерминированных автоматов множество входных последовательностей (^РгеДХ"'^1) является основой при построении теста, где Q - множество достижимости недетерминированного эталонного автомата На основе сформулированных достаточных условий предлагается метод построения полного проверяющего теста, в котором различающие последовательности строятся непосредственно в процессе построения теста с использованием информации об уже построенной части теста, и соответственно для идентификации одного и того же состояния могут использоваться различные последовательности

В параграфе 4 3 рассматривается модель <5<>Зт(Х, ¥)>, где 5- недетерминированный эталонный автомат, Зт(Х, У) - множество всех полностью определенных детерминированных автоматов с числом состояний не более т, а в качестве отношения конформности используется отношение редукции В разделе 4 3 1 напоминается понятие г-различимости между состояниями недетерминированного автомата, которое отличается от понятия различимости состояний Если в эталонном автомате любая пара состояний является г-различимой, то можно гарантировать, что никакое состояние проверяемого автомата не будет редукцией двух различных состояний эталонного автомата Отмечается, что основой при построении проверяющего теста является множество входных последовательностей ()Рге/(Хт'к+'), где () есть множество входных последовательностей, по которым детерминировано (д-) достижимы к состояний эталонного автомата В разделе 4 3 2 устанавливаются достаточные условия, которыми должны обладать различающие последовательности, добавленные к последовательностям из (¿РгеАХ"1'1*чтобы полученное множество было полным

проверяющим тестом относительно модели неисправности <Б<,Зт(Х,У)> при

условии, что любая пара состояний автомата S является /--различимой На основе установленных достаточных условий в разделе 4 3 3 предлагается адапта-

ция Я-метода для построения проверяющего теста относительно модели неисправности <5<,3'т(Х,У)>. Аналогично случаю детерминированных автоматов, /•-различающие множества определяются в процессе построения теста, и соответственно для проверки одного и того же финального состояния различных переходов можно использовать различные /--различающие множества Предложенные в данной главе методы позволяют строить более короткие тесты относительно моделей <5,<,-Зт(Х,У)> и^,=,£}т(Х,¥)>. Подобно Я-методу, эти методы могут быть использованы в случае, когда эталонный автомат является частичным

Пятая глава посвящена задаче синтеза проверяющих тестов относительно

модели <5,=,8иЬ(0)>. Мы предполагаем, что в мутационном автомате имеется небольшое количество пар «состояние, вход», которым соответствует более одной пары «следующее состояние, выход», однако каждый такой переход в проверяемом автомате может быть переходом в любое состояние с любым выходным символом. Такие автоматы, в частности, особенно интересны при так называемом регрессивном тестировании, когда эталонная система модифицируется в процессе жизненного цикла, и при каждой модификации тест генерируется только для проверки внесенных изменений В параграфе 5 2 предлагается метод синтеза полного проверяющего теста относительно модели

<5,=,5мЬ(0)>. В предлагаемом методе, как и в Я-методе, при построении различающих последовательностей используется информация об уже построенной части теста Кроме того, при построении теста используется информация о детерминированных переходах в мутационном автомате, что в ряде случаев позволяет построить основу проверяющего теста, которая не обязательно будет включать все входные последовательности длины т-п+1, те будет короче, чем множество УХ™'"*1, построенное для модели «черного ящика»

Алгоритм 2. Построение полного проверяющего теста относительно модели

<5,=,5,мй(0)>

Вход: - связный приведенный детерминированный

эталонный автомат с и состояниями и входным алфавитом X, - мутационный автомат с т состояниями, т>п.

Выход: Полный проверяющий тест относительно модели <5,=,5иЬ( 0)>

Шаг 1. Строим префикс замкнутое множество достижимости У=У^У2 эталонного автомата 5такое, что по последовательностям множества детерми-

15

нировано достижимы все д-достижимые состояния мутационного автомата Q, множество состояний, достижимых в эталонном автомате по последовательностям множества Уг, обозначаем S2. Для каждого состояния seS определяем множество d(s)ciQ состояний мутационного автомата <3, детерминировано (д-) различимых с состоянием s

Шаг 2. Строим основу CS проверяющего теста Рассматриваем каждую последовательность ае V и каждую последовательность*^ длины m-\V\+\ такие, что ае V2 или ае Vx и из состояния, достижимого из начального состояния по последовательности а в мутационном автомате, под действием входного символа х существует больше одного перехода

Для пары а их/1 определяем наименьшее подмножество непустых префиксов Хъ ,Хк последовательности xju такое, что число где

S-S2ri{Ss(si,ax,) i=1, Л}, больше мощности множества

к

( U б \ d{Ss (5,, ах,)) -Qi), где Qx - множество состояний автомата Q, дос-

7=1

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

Шаг 3. Для каждой последовательности ахк из множества CS, ае V, |хА<т~\ 1 > и непустых префиксов последовательности Хк со свойст-

к

вом A+|5j>| U Q\d(8s(si,ax, f)-Q\\ рассматриваем каждый префикс ах,, 7=1

7=1, ,к Для каждого состояния q мутационного автомата, д-различимого с состоянием 5£s\,aXj), проверяем, содержит ли множество TS последовательность

axjco, где «-последовательность, д-различающая состояния 8&s\,aXj) иq Если TS не содержит такой последовательности, то включаем в 75 последовательность ах;со

Шаг 4. Для каждой последовательности aeCS рассматриваем каждую последовательность /Зе V'uPrefia) Если S^s\,a)^8s{si,p), то проверяем, содержит ли множество TS последовательности асо и Ра, где со — последовательность, различающая состояния 8s(sx,a) и 8s(svP) Если TS не содержит таких последовательностей, то включаем в TS последовательности аа> и рсо.

В параграфе 5 3 эффективность предложенного метода оценивается посредством компьютерных экспериментов в зависимости от размеров эталонного и мутационного автоматов и числа пар «состояние, входной символ», для которых в мутационном автомате существует более одного перехода. Эксперименты показали, что в случае, когда число таких пар в мутационном автомате не превышает 30%, длина теста, построенного по алгоритму 2, в большинстве случаев пропорциональна произведению числа состояний мутационного автомата на число пар «состояние, входной символ», для которых в мутационном автомате существует более одного перехода

Заключение

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

На защиту выносятся следующие результаты:

1 Установлены новые достаточные условия полноты проверяющих тестов для детерминированных автоматов относительно модели «черного ящика» На основе этих достаточных условий предложен новый метод (Я-метод) синтеза полных проверяющих тестов без перебора проверяемых автоматов, в котором различающие последовательности строятся непосредственно в процессе построения теста Экспериментально показано, что предложенный метод доставляет проверяющие тесты с меньшей избыточностью, чем известные методы.

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

3 Предложен новый метод синтеза проверяющего теста относительно мутационного автомата, который для определенных классов мутационных автоматов доставляет более короткие проверяющие тесты, чем известные методы Экспериментально показано, что в большинстве случаев, когда число пар «состояние, входной символ», для которых в мутационном автомате существует более одного перехода, не превышает 30%, длина теста полиномиально зависит от числа состояний мутационного автомата

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Куфарева И Б, Дорофеева М Ю Исследование методов построения проверяющих тестов для детерминированных автоматов Доклады третьей всероссийской конференции с международным участием «новые информационные технологии в исследовании дискретных структур» — Томск, 2000 - С 204-209

2 Куфарева И Б, Дорофеева М Ю. Об оценке длины переборного теста для конечного автомата Сборник научных трудов по материалам 7-й международной конференции «теория и техника передачи, приема и обработки информации» - Харьков, 2001.-С 299-300

3 Куфарева И Б., Дорофеева М Ю Минимизация проверяющих тестов для конечных автоматов // Вестник ТГУ Приложение - 2002 - № 1 (2) - С 357-362

4 Дорофеева М Ю Анализ методов построения регрессивных проверяющих тестов на основе компьютерных экспериментов Тезисы докладов международной конференции молодых ученых по математическому моделированию и информационным технологиям - Новосибирск, 2002 - С 52

5 I Koufareva, М Dorofeeva A novel modification of W-method // Joint bulletin of the Novosibirsk computing center and A P Ershov institute of informatics systems Series computing science -2002 - Vol 18 -P 69-81.

6 Дорофеева M Ю , Евтушенко H В. Усовершенствование метода синтеза проверяющих тестов по мутационному автомату // Вестник ТГУ Приложение - 2003 -№ 6 - С 164-168

7 М. Dorofeeva, Kh. El-Fakih, N Yevtushenko Incremental testing methods for implementations with more states than specifications // Вестник ТГУ. Приложение -2004 - № 9(1) - С 163-168

8 М Dorofeeva, A Petrenko, М Vetrova, N Yevtushenko Adaptive test generation from a nondetermmistic FSM // Радиоэлектроника и информатика —2004 — №3 -С 91-95

9 Дорофеева М Ю Экспериментальное сравнение методов синтеза проверяющих тестов для детерминированных автоматов // Вестник ТГУ Приложение - 2005 -№14 -С 148-154

ЮМ Dorofeeva, Kh El-Fakih, N Yevtushenko An improved conformance testing method//Lecture notes in computer science No 3731 -P 204-218.

11 M Dorofeeva, К El-Fakih, S Maag, A R. Cavalli, N Yevtushenko Experimental evaluation of FSM-based testing methods // In proceedings of the IEEE international conference on software engineering and formal methods - Koblenz, 2005 - P 23-32

12 Дорофеева МЮ Адаптация Н-метода для тестирования недетерминированных автоматов относительно редукции//Вестник ТГУ Приложение -2006 —№18 — С 49-54

13 Громов М JI, Дорофеева М Ю, Коломеец А В К синтезу тестов по мутационному автомату//Вестник ТГУ Приложение -2006 -№18 -С 43-49

Отпечатано в ООО «Компания «Мипон», лиц ПД № 12-0151 от 16 11.2001г Заказ № 126, тираж 110 экземпляров, подписано в печать 23.04.2007г. г Томск, пр.Фрунзе, 7. т.585 053

Введение.

1. Основные понятия, постановка задачи и обзор существующих методов ее решения.

1.1. Конечные автоматы.

1.2. Отношения между автоматами.

1.2.1. Отношения конформности.

1.2.2. Отношения различимости.

1.3. Модели неисправности и проверяющие тесты.

1.3.1. Модель неисправности.

1.3.2. Проверяющие тесты.

1.4. Выбор модели неисправности.

1.4.1. Модель «черного ящика» <S,=,3M(X,Y)>.

1.4.2. Мутационный автомат и его использование для описания модели неисправности.

1.5. Постановка задачи синтеза тестов.

1.6. Методы синтеза проверяющих тестов для конечных автоматов относительно модели <S,=,-Jm(X,Y)>.

1.6.1. Построение теста перечислением неисправностей.

1.6.2. Идентификация состояний.

1.6.3. Методы построения тестов.

1.7. Методы синтеза проверяющих тестов для недетерминированных автоматов.

1.8. Методы синтеза проверяющих тестов относительно мутационного автомата.

1.9. Теоретические оценки длины проверяющего теста.

1.10. Выводы по главе.

2. Экспериментальное сравнение методов синтеза проверяющих тестов для детерминированных автоматов.

2.1. Генератор псевдослучайных автоматов.

2.1.1. Способ генерации автомата.

2.1.2. Анализ свойств генерируемых автоматов.

2.2. Экспериментальное исследование избыточности тестов, доставляемых различными методами.

2.3. Экспериментальное исследование абстрактных методов синтеза тестов относительно модели «черного ящика».

2.3.1. Исследование зависимости длин тестов от числа состояний эталонного автомата.

2.3.2. Сравнение с теоретическими оценками.

2.3.3. Исследование зависимости длины теста от числа выходных символов в автомате.

2.3.4. Полнота UIO-тестов.

2.4. Результаты экспериментов с протоколами Simple Connection Protocol и V.76 Protocol.

2.4.1. Сравнение длин тестов, построенных различными методами, для протокола SCP.

2.4.2. Сравнение длин тестов, построенных различными методами, для протокола V.76.

2.5. Выводы по главе.

3. Метод синтеза проверяющих тестов для детерминированных автоматов с использованием построенной части теста (Я-метод).

3.1. Достаточные условия полноты теста.

3.2. Я-метод построения полного проверяющего теста.

3.2.1. Стратегии перебора последовательностей.

3.2.2. Алгоритм построения проверяющего теста.

3.3. Экспериментальные результаты по оценке длины тестов, доставляемых Я-методом.

3.4. //-метод для частичных приведенных автоматов.

3.4.1. Определения и обозначения.

3.4.2. Достаточные условия полноты теста.

3.4.3. Я-метод построения полного проверяющего теста для частичного эталонного автомата.

3.5. Выводы по главе.

4. Метод синтеза проверяющих тестов для недетерминированных автоматов с использованием построенной части теста (адаптация Я-метода).

4.1. Определения и обозначения.

4.2. Построение полного проверяющего теста относительно эквивалентности.

4.2.1. Достаточные условия полноты относительно модели неисправности <S,=,Qm(X,Y)>.

4.2.2. Метод построения полного проверяющего теста относительно модели неисправности <5,s,Qm(X,y)>.

4.3. Построение полного проверяющего теста относительно редукции.

4.3.1. Понятие г-различимости.

4.3.2. Достаточные условия полноты теста.

4.3.3. Метод построения полного проверяющего теста.

4.4. Основные результаты главы.

5. Метод синтеза полных проверяющих тестов по мутационному автомату.

5.1. Основные понятия и определения.

5.2. Построение полного проверяющего теста относительно модели <S,=,Sub(Q)>.

5.3. Экспериментальные результаты.

5.4. Основные результаты главы.

Актуальность проблемы. Конечные автоматы широко используются в качестве математической модели при синтезе тестов для контроля правильности функционирования систем логического управления [1-6], в частности, при тестировании телекоммуникационных протоколов [7-11], а в последнее время и при тестировании программного обеспечения [12 и др.]. Математической моделью процесса контроля является эксперимент с автоматом [2], т.е. процесс приложения тестовых последовательностей к проверяемой системе, поведение которой описано автоматом, наблюдении соответствующих реакций и вывода заключения на основе этих наблюдений о пригодности или непригодности тестируемой системы к дальнейшему использованию. При использовании автоматного подхода обычно предполагается, что множество проверяемых автоматов описывает поведение систем со всеми возможными неисправностями, и если множество входных воздействий (проверяющий тест) может обнаружить каждую систему, не пригодную к использованию, то такое множество входных воздействий называется полным проверяющим тестом (относительно заданного множества неисправностей). Несмотря на большое количество публикаций по синтезу проверяющих тестов для автоматов [1324 и др.], задача далека от того, чтобы считаться решенной. По-прежнему неизвестны необходимые и достаточные условия полноты проверяющих тестов относительно различных моделей, что не позволяет строить оптимальные тесты. Полные тесты, построенные относительно известных моделей, в частности, относительно модели «черного ящика», т.е. для случая, когда известна только верхняя оценка числа состояний в проверяемой системе [13, 18, 19], обладают высокой полнотой, но их размерность ограничивает практическое применение. Более того, в большинстве случаев тесты, доставляемые известными методами, обладают большой избыточностью. В связи с этим продолжается поиск новых моделей неисправности, отражающих ошибки в реальных системах, и допускающих построение тестов достаточно высокого качества. Одной из таких моделей является модель «серого ящика», когда полный проверяющий тест строится относительно множества всех подавтоматов специального мутационного автомата [7, 23, 24]. Модель мутационного автомата при синтезе проверяющих тестов активно используется при тестировании, в том числе, программного обеспечения [12 и др.]. Таким образом, задача синтеза проверяющих тестов для контроля функционирования систем логического управления методами теории автоматов является актуальной.

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

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

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

Научная новизна. Научная новизна работы состоит в следующем.

1. Проведен экспериментальный анализ методов синтеза проверяющих тестов без перечисления проверяемых автоматов относительно модели черного ящика», т.е. относительно модели неисправности <S,=,Sm(X,V)> на одном и том же множестве автоматов, сгенерированных псевдослучайным способом, а также на автоматах, описывающих телекоммуникационные протоколы, с целью сравнения длин тестов, доставляемых различными методами. Экспериментально показано, что 1) тесты, построенные без перебора автоматов из множества 3m{X,Y), являются избыточными относительно теста, построенного посредством перебора проверяемых автоматов; 2) UIO- и £>£-методы доставляют тесты с наименьшей избыточностью, но эти методы не всегда применимы; 3) из рассмотренных методов, применимых к любому связному приведенному автомату, самые короткие тесты доставляют Wp- и Я57-методы. Согласно проведенным экспериментам, соотношения между длинами тестов, построенных различными методами, для случайно сгенерированных автоматов и для автоматов, описывающих протоколы, сохраняются.

2. Установлены новые достаточные условия полноты проверяющих тестов для детерминированных автоматов относительно модели неисправности <S,=,3m(X,Y)>. На основе этих достаточных условий предложен метод (Я-метод) синтеза полных проверяющих тестов, который не требует перебора автоматов из области неисправности, и основан на использовании уже построенной части теста при идентификации состояний проверяемого автомата. Экспериментально показано, что в среднем для небольших автоматов длины тестов, построенных Я-методом и методом, основанным на переборе всех автоматов из множества 3m{X,Y), совпадают. Кроме того, Я-метод имеет значительное преимущество перед Я57-методом (а, следовательно, и перед другими известными абстрактными методами) по длине доставляемого теста. Показано, что Я-метод применим и для случая, когда эталонный автомат является частичным.

3. Разработанный Я-метод адаптирован для случая, когда эталонный автомат является недетерминированным для проверки отношений редукции и эквивалентности.

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

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

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

1. Научная Программа МО РФ «Научные исследования высшей школы в области производственных технологий» (2000 г.)

2. Проект МО РФ Е00-2.0-33 «Исследование отношений редукции и эквивалентности между недетерминированными автоматами» (2001-2002 гг.)

3.Грант Роснауки по мероприятию 1.11 «Развитие системы стажировок молодых ученых и преподавателей в крупных научно-образовательных центрах (включая зарубежные) и участие в конференциях, симпозиумах, семинарах, школах (в том числе за рубежом)» федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 гг. по приоритетному направлению «Развитие инфраструктуры» (XVII очередь) (2005 г.)

4. Грант Роснауки по мероприятию 1.9 «Проведение молодыми учеными научных исследований по приоритетным направлениям науки, высоких технологий и образования» федерельной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 гг. по приоритетному направлению «Развитие инфраструктуры» (XXII очередь) (2005 г.)

5. Грант Роснауки по мероприятию 1.9 «Проведение молодыми учеными научных исследований по приоритетным направлениям науки, высоких технологий и образования» федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 гг. по приоритетному направлению «Развитие инфраструктуры» (IV очередь -Молодые ученые) (2006 г.)

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

Апробация работы. Научные результаты, составившие основу данной работы, обсуждались на заседаниях объединенного семинара кафедры информационных технологий в исследовании дискретных структур радиофизического факультета ТГУ, кафедры защиты информации и криптографии и кафедры программирования факультета прикладной математики и кибернетики ТГУ. Кроме того, они докладывались на конференциях, в том числе международных, в гг. Томске, Туапсе,

Новосибирске, Иркутске, Кобленце, Тайпее. Результаты работы опубликованы в [65-77].

Структура и объем диссертации. Диссертация состоит из введения, 5 глав, заключения и списка используемой литературы. Объем диссертации составляет 151 страницу текста, набранного в редакторе MS Word 2000 (шрифт - Times New Roman, размер шрифта - 14 pt, межстрочный интервал - 1.5 строки), в том числе: титульный лист - 1 стр., оглавление - 4 стр., основной текст, включающий 17 рисунков и 3 таблицы, - 124 стр., библиография из 77 наименований - 8 стр., приложение - 13 стр.

5.4. Основные результаты главы

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

Заключение

В диссертации предложены методы синтеза проверяющих тестов для дискретных управляющих систем методами теории автоматов. В работе проведен теоретический и экспериментальный анализ методов построения проверяющих тестов для детерминированных и недетерминированных автоматов относительно различных моделей неисправностей, а именно относительно модели «черного ящика», когда известна только верхняя оценка числа состояний проверяемых автоматов, и относительно модели «серого ящика» (мутационного автомата). Проведен сравнительный анализ известных методов построения проверяющих тестов для детерминированных автоматов при ограниченном числе состояний проверяемого автомата. Исследована зависимость средней длины тестов, построенных с использованием различных методов, от размера эталонного автомата. Кроме того, экспериментально определено, как часто применимы методы, основанные на использовании уникальных входо-выходных последовательностей (UIO) и диагностической последовательности (DS). Эксперименты проводились на одном и том же множестве автоматов, сгенерированных псевдослучайным способом. Эксперименты, проведенные с автоматами, построенными по протоколам Simple Connection и V.76, показали, что соотношения между длинами тестов, построенных различными методами для случайно сгенерированных автоматов и для автоматов, описывающих протоколы, сохраняются. Отмечается, что проверяющий тест можно оптимизировать, т.е. существенно сократить его длину, при более удачном выборе различающих последовательностей.

В работе сформулированы новые достаточные условия полноты проверяющего теста относительно модели «черного ящика», т.е. в предположении, что число состояний проверяемого автомата не больше числа т. На основе сформулированных условий разработан метод синтеза теста для полностью определенного детерминированного автомата относительно эквивалентности. Предложенный метод основан на использовании информации об уже построенной части теста при выборе различающих последовательностей для идентификации состояний и переходов. Показано, что предложенный метод применим и для случая, когда эталонный автомат является частичным. Экспериментально показано, что, предложенный метод имеет значительное преимущество перед известными методами построения тестов относительно модели «черного ящика» по длине доставляемого теста. Это преимущество возрастает с ростом разности числа состояний проверяемого и эталонного автоматов. Экспериментально также показано, что для автоматов с небольшим числом состояний, предложенный метод доставляет тесты по длине близкие к оптимальным, т.е. избыточность тестов, построенных этим методом, минимальна по сравнению с другими известными методами. Предложенный метод адаптирован для случая, когда поведение эталонной и проверяемой систем описываются недетерминированными автоматами. В этом случае в качестве отношения конформности используется отношение эквивалентности, и проверяющий тест строится относительно модели <S,=,Q.m(X,Y)>, где Q.m(X,Y) - множество всех недетерминированных автоматов не более чем с т состояниями. Также предложенный метод адаптирован для модели <S,<,3m(X,Y)>, где 5- недетерминированный эталонный автомат, < - отношение редукции, 3m(X,Y) - множество всех детерминированных автоматов не более чем с т состояниями. Однако, хотя предложенный метод доставляет тесты, по длине близкие к оптимальным, тесты, построенные относительно модели «черного ящика» по-прежнему являются достаточно длинными. Поэтому в работе также рассматривается модель неисправности, в которой пользователь определяет наиболее типичные (часто встречающиеся) неисправности. Такая модель известна под названием модели «серого ящика» и успешно применяется в технической диагностике. В этом случае проверяющий тест строится относительно множества подавтоматов специального мутационного, в общем случае недетерминированного, автомата. В разделе предлагается метод построения проверяющих тестов для специального вида мутационного автомата, в котором имеется небольшое количество пар «текущеесостояние, входнойсимвол», которым соответствует более одной пары «следующеесостояние, выходнойсимвол», однако каждый такой переход в проверяемом автомате может быть переходом в любое состояние с любым выходным символом. Такие автоматы особенно интересны при регрессивном тестировании, когда тест генерируется только для проверки небольших модификаций в эталонной системе. В данной работе предложен метод построения тестов относительно мутационного автомата в случае, когда число состояний проверяемого автомата может превышать число состояний эталонного автомата. В предложенном методе используется известная информация о детерминированных переходах в мутационном автомате, что позволяет значительно оптимизировать проверяющий тест, т.е. сократить его длину. Экспериментально показано, что если в мутационном автомате количество пар «текущеесостояние, входнойсимвол», для которых существует больше одного перехода, составляет не более 20%, то для всех случайно сгенерированных автоматов длина теста, построенного по алгоритму 5.1, пропорциональна произведению числа состояний мутационного автомата на число пар «текущеесостояние, входнойсимвол», для которых в мутационном автомате существует более одного перехода.

На защиту выносятся следующие результаты:

1. Сформулированы новые достаточные условия полноты проверяющих тестов для детерминированных автоматов. На основе этих достаточных условий предложен новый метод (Я-метод) синтеза полных проверяющих тестов без перебора автоматов из области неисправности относительно модели «черного ящика», который основан на использовании уже построенной части теста при идентификации состояний проверяемого автомата. Экспериментально показано, что предложенный метод доставляет проверяющие тесты с меньшей избыточностью, чем другие известные методы.

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

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

1. Мур Э. Ф. Умозрительные эксперименты с последовательными машинами // Автоматы. - М.: Изд-во иностр. лит., 1956. - С. 179-210.

2. Гилл А. Введение в теорию конечных автоматов. М.: Наука, 1966-272с.

3. Богомолов A.M., Грунский И.С., Сперанский Д.В. Контроль и преобразования дискретных автоматов. Киев: Наук. Думка, 1975. - 176с.

4. Сперанский Д.В., Боголюбов A.M. Контроль и преобразование дискретных автоматов. Киев, 1975.

5. Богомолов A.M., Сперанский Д.В. Аналитические методы в задачах контроля и анализа дискретных устройств. Саратов: Изд-во Сарат. ун-та, 1986.-240с.

6. Грунский И.С., Козловский В.А., Пономаренко Г.Г. Представление конечных автоматов фрагментами поведения. Киев: Наук. Думка, 1990. -232с.

7. Грунский И.С., Петренко А.Ф. Построение проверяющих экспериментов с автоматами, описывающими протоколы // Автоматика и вычислительная техника. 1988, № 4. - С. 7-14.

8. Петренко А.Ф. Эксперименты над протокольными объектами // Автоматика и вычислительная техника. 1987, № 1. - С. 16-21.

9. G.v. Bochmann, A. Petrenko. Protocol testing: review of methods and relevance for software testing. // ISSTA'94, ACM Intern. Symp. on Software Testing and Analysis, Seattle, U.S.A., 1994. P. 109-124.

10. G. v. Bochmann, C. A. Sunshine. Formal methods in communication protocol design // IEEE Trans, on Comm., Vol 28,1980. P. 624-631.

11. A. Petrenko. Checking experiments with protocol machines // Proceedings of the IFIP TC6 4th International Workshop on Protocol Test Systems, 1991, North-Holland.-P. 83-94.

12. Бурдонов И. Б., Косачев А. С., Кулямин В. В. Использование конечных автоматов для тестирования программ // Программирование. -2000, №2.-С. 12-28.

13. Василевский М.П. О распознавании неисправности автоматов // Кибернетика. 1973, № 4. - С. 93-108.

14. T.S. Chow. Test software design modeled by finite state machine // IEEE Transactions. 1978, SE-4, No.3. - P. 178-187.

15. G. Gonenc. A method for the design of fault detection experiments // IEEE Trans. Computers. 1970, vol. C-19. No. 6. - P. 551-558.

16. Sabnani K., Dahbura A. A protocol test generation procedure // Computer Networks and ISDN Systems. 1988, vol. 15, No. 4. - P. 285-297.

17. S.T. Vuong, W.W. L. Chan, and M.R. Ito. The UlOv-method for protocol test sequence generation // Proc. of the IFIP TC6 2nd IWPTS, North-Holland, 1989.-P. 161-175.

18. Евтушенко H.B., Петренко А.Ф. Метод построения эксперимента для произвольного детерминированного автомата // Автоматика и вычислительная техника. 1990, № 5. - С. 73-76.

19. Fujiwara S., Bochmann G. v., Khendek F., Amalou M., Ghedamsi A. Test selection based on finite state models // IEEE Trans. 1991, SE-17, No. 6. - P. 591-603.

20. A. Petrenko, G.v. Bochmann, R. Dssouli. Conformance relations and test derivation // Proceedings of 6th IFIP International Workshop on Protocol Test Systems, France, 1993.-P. 161-182.

21. Pomeranz, S.M. Reddy. Test Generation for Multiple State-Table Faults in Finite State Machines // IEEE Transactions on Computers. 1997, vol.48, №7. -P. 783-794.

22. D. Lee, M. Yannakakis. Testing FSMs: state identification and verification // IEEE Transactions on Computers. 1994, vol. 43, №3. - P. 306-320.

23. A. Petrenko, N. Yevtushenko. Test Suite Generation for a Given Type of Implementation Errors // Proceedings of IFIP 12th International Conference on Protocol Specification, Testing and Verification, 1992. P. 229-243.

24. I. Koufareva, A. Petrenko, N. Yevtushenko. Test Generation Driven by User-Defined Fault Models // Testing of Communicating systems: Methods and Applications. Kluwer Academic Publishers, 1999. - P. 215-223.

25. Куфарева И. Б. Применение недетерминированных автоматов в задачах синтеза проверяющих тестов в системах логического проектирования. ТГУ, Томск, диссертационная работа, 2000.

26. К. El-Fakih, N. Yevtushenko, and G. v. Bochmann. FSM-based incremental conformance testing methods // IEEE Transactions on Software Engineering. 2004, vol. 30 No.7. - P. 425-436.

27. Евтушенко H.B., Петренко А.Ф., Тренькаев B.H. Метод тестирования автоматных сетей, основанный на тестируемом поведении компоненты // Автоматика и вычислительная техника. 1996, № 2. - С. 48-59.

28. Евтушенко Н.В., Тренькаев В.Н. Методы синтеза проверяющих тестов для компоненты автоматной сети //Новые информационные технологии в исследовании дискретных структур. Доклады второй всероссийской конференции. Екатеринбург, 1998. - С. 219-223.

29. Пархоменко П.П. Основы технической диагностики. М.: Энергия, 1976.-464 с.

30. Матросова А. Ю. Алгоритмические методы синтеза тестов. Томск: Изд-во Томского госуниверситета, 1990. - 207 с.

31. A. Petrenko, N. Yevtushenko, G.v. Bochmann. Testing Deterministic Implementations from Nondeterministic FSM Specifications // Proceedings of

32. IP TC6 9th International Workshop on Testing Of Communicating Sytems. -Germany, 1996.-P. 125-140.

33. P.H. Starke. Abstract Automata. North-Holland: American Elsevier, 1972. -419p.

34. Лукьянов Б.Д. О различающих и контрольных экспериментах с недетерминированными автоматами // Кибернетика и системный анализ. -1995, №5.-С. 69-76.

35. Лукьянов Б.Д. Детерминированные реализации недетерминированных автоматов // Кибернетика и системный анализ. 1996, №4. - С. 34-50.

36. S. Boroday. Distinguishing Tests for Nondeterministic Finite State Machines // Proceedings of 11th International Workshop on Testing of Communicating Systems. Kluwer Academic Publishers, 1998. - P. 101-107.

37. T. Kim, T. Villa, R. Brayton, A. Sangiovanni-Vincentelli. Synthesis of FSMs: functional optimization. Kluwer Academic Publishers, 1997.

38. B. Yang, H. Ural. Protocol conformance test generation using multiple UIO sequences with overlapping // Computer Communication Review. 1990, No. 4. -P. 118-125.

39. Luo G., Petrenko A., Bochman G.v. Selecting test sequences for partially-specified nondeterministic state machines // Proceedings of IFIP 6th International Workshop on Protocol Test Systems, 1995. P. 95-110.

40. D.Lee, K. Sabnani, D. Kristol, S. Paul. Conformance testing of protocols specified as communicating finite state machines a guided random walk based approach // IEEE Transactions on Communications. - 1996, vol. 44, No. 5. - P. 631-640.

41. Kang D., Kang S., Kim M., Yoo S. A weighted random walk approach for conformance testing of system specified as communicating finite state machines // Proceedings of the Inter. Conf. FORTE X /PSTV XVII, 1997. P. 267-282.

42. Gerard J. Holzmann. Design and validation of computer protocols // Prentice-Hall, Englewood Cliffs. 1991.

43. A. Petrenko, N. Yevtushenko, G.v. Bochmann. Fault models for testing in context // Proceedings of IFIP 1th Joint International Conference FORTE/PSTV. -Chapmann & Hall, 1996.-P. 163-178.

44. A. Petrenko, and N. Yevtushenko. Conformance tests as checking experiments for partial nondeterministic FSM // Proceedings of the 5th International Workshop on Formal Approaches to Testing of Software, 2005.

45. R. M. Hieron, Adaptive Testing of a deterministic implementation against a non-deterministic finite state machines // The computer journal. 1998, vol.41.-P. 349-355.

46. W.-H. Chen. Executable test sequence for the protocol data flow property // Proceedings of Formal Description Techniques for Distributed Systems and Communication Protocols, and Protocol Specification, Testing, and Verification, FORTE/PSTV'01. 2001.

47. ITU-T Recommendation V.76, "Generic multiplexer using V.42 LAPM-based procedures". 1996, Series V: Data communication over the telephone network.

48. ITU-T Recommendation V.42, "Error-Correcting Procedures for DCEs Using Asynchronous-to Synchronous Conversion". 2002, AAP29-03/02.

49. A. Petrenko, N. Yevtushenko. Testing from partial deterministic FSM specifications // IEEE Transactions on Computers. 2005, 54(9). - P. 1154-1165.

50. Евтушенко H.B., Петренко А.Ф. Синтез проверяющих экспериментов в некоторых классах автоматов // Автоматика и Вычислительная техника. -1990,№4.-С. 59-64.

51. Hennie F.C. Fault detecting experiments for sequential circuits // Proceedings of the 5th Annual Symposium on Switching Circuit Theory and Logical Design. 1964. - P. 95-110.

52. Hartmams J., Steams R. Algebraic structure theory of sequential machines. Prentice-Hall, New York, 1966. - 210 p.

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

54. Ветрова М.В. Разработка алгоритмов синтеза и тестирования конечно-автоматных компенсаторов. ТГУ, Томск, диссертационная работа, 2004. -152с.

55. Спицына Н.В. Синтез тестов для проверки взаимодействия дискретных управляющих систем методами теории автоматов. ТГУ, Томск, диссертационная работа, 2005. 158с.

56. RoseM. Post Office Protocol Version 3. RFC 1460, June 1993. // http://www.faqs.org/rfcs/rfcl460.html.

57. J.A. Brzozowski, H. Jurgensen. A model for sequential machine testing and diagnosis // Journal of Electronic Testing: Theory and Applications. 1992, No. 2.-P. 219-234.

58. Евтушенко H.B., Петренко А.Ф. О проверяющих возможностях кратных экспериментов // Автоматика и Вычислительная техника. 1989, №3.-С. 9-14.

59. Luo G., Petrenko A., Bochman G.v. Selecting test sequences for partiallythspecified nondeterministic state machines // Proceedings of IFIP 6 International Workshop on Protocol Test Systems, 1995. P. 95-110.

60. R. Milner. A Calculus of Communicating Systems. Lecture Notes in Computer Science, vol. 92,1980.

61. Куфарева И.Б., Евтушенко H.B., Петренко А.Ф. Синтез проверяющих тестов для недетерминированного автомата относительно редукции // Автоматика и вычислительная техника. 1998, № 3. - С. 10-20.

62. Евтушенко Н.В., Лебедев А.В., Петренко А.Ф. О проверяющих экспериментах с недетерминированными автоматами // Автоматика и Вычислительная техника. 1991, № 6. - С. 81-85.

63. R. Alur, С. Courcoubetis, М. Yannakakis. Distinguishing tests for nondeterministic and probabilistic machines // Proceedings the 27th ACM Symposium on Theory of Computing, 1995. pp. 363-372.

64. Куфарева И.Б., Дорофеева М.Ю. Об оценке длины переборного теста для конечного автомата. Сборник научных трудов по материалам 7-й международной конференции «Теория и техника передачи, приема и обработки информации». Харьков, 2001. - С. 299-300.

65. Куфарева И.Б., Дорофеева М.Ю. Минимизация проверяющих тестов для конечных автоматов // Вестник ТГУ. Приложение. 2002. - № 1 (2). -С. 357-362.

66. I. Koufareva, М. Dorofeeva. A novel modification of W-method // Joint Bulletin of the Novosibirsk computing center and A.P. Ershov institute ofinformatics systems. Series: Computing science, issue: 18, 2002, NCC Publisher, Novosibirsk. P. 69-81.

67. Дорофеева М.Ю., Евтушенко H.B. Усовершенствование метода синтеза проверяющих тестов по мутационному автомату // Вестник ТГУ. Приложение. 2003. -№ 6. - С. 164-168.

68. М. Dorofeeva, Kh. El-Fakih, N. Yevtushenko. Incremental testing methods for implementations with more states than specifications // Вестник ТГУ. Приложение. 2004. - № 9(1). - С. 163-168.

69. Дорофеева М.Ю. Экспериментальное сравнение методов синтеза проверяющих тестов для детерминированных автоматов // Вестник ТГУ. Приложение. 2005. - №14. - С. 148-154.

70. М. Dorofeeva, Kh. El-Fakih, N. Yevtushenko. An improved conformance testing method // Lecture Notes in Computer Science No. 3731. P. 204-218.

71. Дорофеева М.Ю. Адаптация Н-метода для тестирования недетерминированных автоматов относительно редукции // Вестник ТГУ. Приложение. 2006. -№18. - С. 49-54.

72. Громов М.Л., Дорофеева М.Ю., Коломеец А.В. К синтезу тестов по мутационному автомату // Вестник ТГУ. Приложение. 2006. - №18. - С. 43-49.

73. М. Dorofeeva, A. Petrenko, М. Vetrova, N. Yevtushenko. Adaptive test generation from a nondeterministic FSM // Радиоэлектроника и информатика. 2004.-№3.-С. 91-95.