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

Томский государственный университет

УДК 519.713.4, 519.718.7

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

ТВ ОД

Куфарева Ирина Борисовна

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

Специальность 05.13.01 «Управление в технических системах»

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

Томск-2000

Работа выполнена в Томском государственном университете.

доктор технических наук, профессор Евтушенко Н.В.

доктор технических наук, профессор Сперанский Д.В.

кандидат технических наук, доцент Липский В.Б.

Институт вычислительной математики и математической геофизики СО РАН, г. Новосибирск.

Защита состоится « 2*5 » мая 2000 г. в 14.30 на заседании диссертационно! совета Д063.53.03 при Томском государственном университете по адрес; 634050, г. Томск, пр. Ленина 36.

С диссертацией можно ознакомиться в библиотеке Томског государственного университета.

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

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

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

Автореферат разослан « ? » апреля 2000 г.

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

к. ф.-м. н., доцент Щ/_Б.Е. Тривоженко

£ ¿7Т, о

Общая характеристика работы

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

В качестве математической модели поведения систем логического управления часто используется конечный автомат. При данном подходе предполагается, что исправное поведение тестируемой системы описывается конечным автоматом, равно как и ее поведение при наличии неисправности. Моделью возникающих в системе неисправностей служит некоторое множество конечных автоматов, называемое классом неисправностей. Методам построения полных проверяющих тестов для конечных автоматов посвящен ряд работ российских и зарубежных ученых: А.М.Богомолова, И.С.Грунского, Д.В.Сперанского, В.А.Твердохлебова, М.П.Василевского, Н.В.Евтушенко, А.Ф.Петренко, О.у.ВосЬтапп, Т.8.СЬо\у, 8.РиЦ\уага, Б.Ьее, М.Уаппакак^ и др. В большинстве работ в качестве класса неисправностей рассматривается множество всех автоматов с количеством состояний, не превышающим заданного целого числа; данная модель носит название модели «черного ящика».

В диссертации предлагается новая математическая модель для компактного описания неисправностей различных классов. Данная модель основана на применении так называемого мутационного автомата, то есть недетерминированного автомата, представляющего всевозможные ошибочные переходы, которые могут иметь место в неисправной системе. Класс неисправностей описывается множеством всех подавтоматов мутационного автомата. Прототипом мутационного автомата является введенная И.С.Грунским и А.Ф.Петренко в 1988 г. функция неисправности; но в отличие от нее, мутационный автомат позволяет представить в том числе и неисправности, увеличивающие число состояний системы.

Для описания эталонного поведения системы в диссертации также предлагается использовать недетерминированный автомат. Такой автомат позволяет представлять необнаружгшые или несущественные неисправности в системе, например, при тестировании систем со сниженной управляемостью и/или наблюдаемостью, а также при тестировании протоколов вычислительных сетей. Способы построения таких автоматов для различных задач известны из работ А.Ф.Петренко, Н.В.Евтушенко, К.К.Вгау(:оп, Б.игщег, У.\¥а1апаЬе и др. Система исправна, если реализуемый ей язык входо-выходных последовательностей содержится в языке этого автомата. На данный момент существует очень мало публикаций, посвященных построению тестов для недетерминированного эталонного автомата. В работах Б.ДЛукьянова и С.Ю.Бородая в качестве класса неисправностей рассматривается бесконечное множество автоматов, для которого не обязательно существует конечный тест. В публикациях по тестированию соответствия сетевых протоколов, в частности, в работах Р.Тпра&у, К/Ыа1к, M.Ghriga, Р.О.Ргапк1 и др., рассматривается узкий класс частных случаев, и полнота построенных тестов не гарантируется.

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

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

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

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

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

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

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

Реализация полученных результатов. Исследования, результаты которых изложены в диссертации, проводились в рамках работ по госбюджетной тематике Сибирского физико-технического института при Томском государственном университете (ТГУ) (программа 1995-2000 гг. ;<Исследование и разработка новых методов электромагнитного контроля и [гоагностики материалов, сред и технических систем»). Разработанные в диссертации способы представления необнаружимых неисправностей с помощью недетерминированных автоматов и методы построения тестов для яих нашли применение в теоретических исследованиях по гранту РФФИ

(проект № 99-01-00337 «Решение автоматных уравнений и неравенств* 1999-2000). Методы генерации проверяющих тестов дл недетерминированных автоматов были также использованы в процесс работы по гранту НАТО совместно с научной группой университета г Беркли, США. Полученные теоретические результаты внедрены в учебны] процесс и используются при подготовке курсов «Теория автоматов» i «Техническая диагностика» на радиофизическом факультете и факультет» прикладной математики и кибернетики ТГУ. Предложенные методы синтез; проверяющих тестов были реализованы в виде пакета прикладных програмл в работах по межвузовской научно-технической программе «Конверсия i высокие технологии. 1997-2000 гг.» (проект № 95-1-21 «Информационны! компьютерные технологии дискретного математического моделирования анализа, синтеза и тестирования сверхскоростных интегральных схе.\ логического управления»).

Апробация работы. Научные результаты, составившие основ) данной работы, по мере их получения обсуждались на заседаниях объединенного семинара кафедры математической логики и проектирования радиофизического факультета ТГУ, кафедры программирования факультета прикладной математики и кибернетики ТГУ и лаборатории синтеза дискретных автоматов Сибирского физико-технического института (СФТИ) при ТГУ. Эти результаты докладывались на следующих научных конференциях и семинарах:

- Вторая международная конференция «Автоматизация проектирования дискретных систем», Минск, Белоруссия, 1997.

- Международная конференция «Всесибирские чтения по математике и механике», Томск, 1997.

- Сибирская конференция по исследованию операций SCOR-98, Новосибирск, 1998.

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

- Meeting on Control and FSM Synthesis and Related Testing/Validation Issues, Berkeley, 1998.

- 11th IFIP International Workshop on Testing of Communicating Systems, Budapest, Hungary, 1999.

Результаты диссертации также обсуждались и были одобрены в научной группе научно-исследовательского института СИМ в г. Монреале, Канада.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Объем диссертации составляет 176 страниц, в том числе: титульный лист - 1 стр., оглавление - 3 стр., основной текст - 157 стр., библиография из 55 наименований - б стр., приложение — 9 стр.

Основное содержание работы

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

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

Конечные автоматы представляют специальный класс функций, которые сопоставляют каждому слову во входном алфавите одно или несколько слов той же длины в выходном алфавите. Формально под конечным инициальным недетерминированным автоматом понимается пятерка Л К,/1,.?0),

где 51 - множество состояний с выделенным начальным состоянием .?о, X и У - входной и выходной алфавиты, й - отношение переходов-выходов, /гс5хЛ'х5х У. Элементами множества А являются четверки вида О,*,¿Чу), называемые переходами. Если для каждой пары (5,х) е Бу-Х существует хотя бы одна пара (.?',>') е5хУ, такая что (л,х,5',_у)е/1, то автомат называется полностью определенным. Если для любых ($,х,у)е8хХ*У в автомате существует не более одного перехода из состояния £ под действием входного символа х с выходным символом у, то автомат является наблюдаемым. Автомат называется детерминированным, если для всех (я,*) е£хХ отношение И содержит не более одного перехода из 5 под действием х.

Определение 1. Автомат В=(Т,Х, У,£,/о) называется подавтоматом автомата^ если Гс5, г0=50, и

Пусть А =(5,Х,У,/г,50) — некоторый конечный автомат. Тройка т]*р>у, ...^лб^*, р=Х1Х2--хк&Х*, у^у^г-'-Ук^У*, называется путем в автомате А, если для всех г, !<<<£, состояние л*

называется конечным состоянием пути т]*/3'у. Вхо до-выходная последовательность ¡Ну реализуется автоматом А, если автомат А имеет путь г}*р*у, т;е5*. Для произвольной входной последовательности Р&Х' множество всех входо-выходных последовательностей (Ну, уе Г*, реализуемых автоматом А, обозначается через Языком £(А)

автомата А называется объединение множеств £(А,Р) по всем р<=Х'.

Определение 2. Автомат В есть редукция автомата А (обозначается

В<А), если Дй)сХ(/1); в противном случае автомат В отличим от автомата А, и входная последовательность <ме А'* такая, что ¿£(А, (0)<££(В,(й), отличает В от А. Автоматы А и В эквивалентны

(обозначается В=А), если Х(В)=Ж(А).

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

Определение 3. Пусть А -=(Б,Х,¥,И,^\)) и В=(Т,Х, - два

инициальных недетерминированных автомата. Отношение у/^БхТ называется отношением моделирования, если для любых е хеХ, у&У,? еТ выполняется импликация:

((*,*,*',>>)€£) [((*,*,*» еЛ) & ((«',г')е у/)].

Говорят, что автомат В моделирует автомат Л (обозначается В-<А), если существует отношение моделирования у/с:хТ, такое что е у/.

Утверждение 1. Всякий подавтомат автомата А моделирует Л. Всякий втомат, который моделирует А, является его редукцией. Всякий автомат, оторый является редукцией наблюдаемого автомата А, моделирует Л.

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

Определение 4. Автоматы А и В называются ¿-несовместимыми, если не уществует ни одного полностью определенного автомата, моделирующего дновремешш А и В.

Отношение ¿-несовместимости естественным образом распространяется а тройки, четверки, и вообще п-ки недетерминированных автоматов, [оказано, что для любого набора А2, ..., ¿-несовместимых автоматов ;ожет быть найдено так называемое характеристическое множество ^сЛ'*, для которого справедливо следующее утверждение.

Утверждение 2. Пусть наблюдаемые автоматы Ах, А2, ..., А * -несовместимы и IVс:Х' есть их характеристическое множество. Для юбого полностью определенного детерминированного автомата В найдется оследовательность ае IV, которая отличает В от по крайней мере одного из втоматовЛь^г.

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

этой ситуации в работе А.Ф.Петренко, Н.В.Евтушенко и С.у.ВосЬташ введено понятие модели неисправности как тройки <А,~,£2>, где А -эталонный автомат, £2 - класс неисправностей, а ~ - отношени конформности. Автомат класса неисправностей, который не находится ) отношении ~ с эталонным автоматом, называется неконформныл автоматом.

Параграфы 1.4 и 1.5 посвящены изучению возможносте! применения недетерминированных автоматов для описания эталонной поведения системы и класса неисправностей. Использован» недетерминированного автомата в качестве эталонного бывает необходимо 1 ситуации, когда существует множество неэквивалентных систем, пригодны; к эксплуатации, то есть когда возможны необнаружимые шп несущественные неисправности. Для ряда практических задач существуе-: недетерминированный автомат, редукции которого (и только они описывают необнаружимые неисправности в системе. В частности, I работах А.Ф.Петренко, Н.В.Евтушенко, ШВгауЮп, У.Ша1апаЬс и другю предлагается способ построения такого автомата для задачи тестирован!« компоненты автоматной сети. Метод построения недетерминированной: автомата, описывающего несущественные неисправности в случае, когдг эталонное поведение системы описано не на всех входпы> последовательностях, можно найти в работе БХЬ^ег. В последнее врем* построите тестов относительно редукции с успехом применяется в обласп тестирования протоколов вычислительных сетей, спецификации которые также представляются в виде недетерминированных автоматов.

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

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

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

Параграф 1.6 содержит формальную постановку задачи. Пусть i=(S,X,Y,h,s0) - недетерминированный полностью определенный мблюдаемый эталонный автомат, и M=(T,X,Y,f,t0) -«детерминированный полностью определенный мутационный автомат. Обозначим через Sub(M) множество всех детерминированных полностью >пределенных подавтоматов автомата М.

Определение 5. Конечное множество ЕаХ* конечных входных юследовательностей называется полным проверяющим тестом )тносительно модели <A,<,Sub{M)>, если для всякого автомата % е Sub (Af), который не является редукцией А, найдется

юследовательность аеЕ такая, что jC(B,a)<zJ?(A,a).

Главы 2-4 диссертации посвящены разработке методов построения юлного проверяющего теста относительно модели <A,<,Sub(M)> и »кспериментальной оценке их эффективности.

Вторая глава диссертации посвящена разработке стратегии тостроения тестов относительно модели <A,<,Sub(M)> на основе сличающих автоматов. В ней развивается идея так называемых ^-покрывающих множеств, которая является обобщением известных летодов построения полных проверяющих тестов для детерминированных

автоматов. Одним из основных понятий является понятие множества-ловушки.

Конечное множество ЕаХ* входных последовательностей является ловушкой для автомата BeSub(M) (относительно автомата А), если последовательности Е отличают автомат В от автомата А или для некоторого подмножества {/Зь...,/З*}с£ справедливо: все пути г, 1 <i<k, в автомате В имеют одно и то же конечное состояние t, и состояние t автомата М s -несовместимо с конечными состояниями Sj путей сг, */?, »}',, 1 в автомате А. Если некоторое множество является ловушкой для всех неконформных автоматов из класса неисправностей Sub(M), то полный проверяющий тест относительно модели <A,<,Sub{M)> может быть получен посредством конкатенации последовательностей этого множества и последовательностей характеристических множеств ^-несовместимых состояний эталонного и мутационного автоматов.

В частности, если А является детерминированным приведенным автоматом, а VаХ" есть множество последовательностей, переводящих автомат А в попарно различные состояния, то множество Л= VPref(X"'''у'+1) (где через /Ve/(A"""|K|+1) обозначается множество всех префиксов последовательностей из является ловушкой для всех

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

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

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

Определение 6. Пусть A=(S,X,Y,h,s0) и M=(T,X,Y,g,t0) - два нициальных недетерминированных автомата. Автоматом, отличающим М т А (или отличающим автоматом М\А) назовем максимальный связный одавтомат инициального автомата ((5хГ)и {Fail} ,X,Y<u {fail} ,H,s0t0), в отором отношение Н определено следующим образом: (stjc,s't',y)eH о [(s,x,s',y)eh & (t,x,t',y)eg]; (styX,FaiI,y)eH о [(s,x)xSx{y}nh=0 & (t,x)xTx{y}r\g*@]\ (Fail jc,Fail Jail) e #.

По построению, отличающий автомат В\А имеет путь с конечным остоянием Fail тогда и только тогда, когда автомат В не является редукцией втомата А, причем входная проекция этого пути отличает В от А. Сличающий автомат М\А представляет общие свойства отличающих втоматов В\А, BeSub(M), поскольку всякий такой автомат является одавтоматом автомата М\А. Все пути в отличающих автоматах В\А, ' е Sub(M), представлены среди путей отличающего автомата М\А. Однако автомате М\А есть и такие пути, которые не встречаются ни в одном тличающем автомате В\А, В в Sub (М). Для описания множеств путей, оторые могут одновременно присутствовать в некотором автомате В\А, водится понятие детерминированных и d-совместшшх путей. Для любой ходной последовательности авХ' через Paih(a) обозначается множество сех детерминированных путей с входной проекцией а в отличающем втомате М\А. Если tj*Р*у- некоторый путь в М\А, то Path(a)\rj*fi>y есть шожество всех путей из Path (а), ¿-совместимых с T]*f5>y. Для роизвольного множества VcX* через Path(V) (или Paih{ V)\rj'P'y) бозначается объединение множеств. Path(a) (или Path(a)\r\* Р'у оответственно) по всем йе V.

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

Определение 7. Пусть Р - непустое множество состояний отличающего втомата М\А. Множество Р называется запрещенным, если P={Fail}, или ,= {ji/,i2'> —а состояния si,s2,.--,Sk автомата А и состояние t втомата М s-несовместимы, Состояние автомата М\А называется

запрещенным, если оно образует одноэлементное запрещенное подмножество.

Для каждого запрещенного множества Р существует так называемое характеристическое множество W(P) последовательностей со свойством: если в отличающем автомате В\А имеются все состояния из Р, то найдется состояние д<=Р и последовательность ае W(P), которая переводит автомат В\Л из состояния q в состояние Fail.

Пусть Е - некоторое множество запрещенных подмножеств состояний отличающего автомата М\А ; путь в автомате М\А называется Е-неконформным, если множество его состояний имеет запрещенное подмножество из £, в противном случае путь называется Е-конформным. Очевидно, что всякий проверяемый автомат BeSub(M) такой, что отличающий автомат В\А имеет Х-неконформный путь, не является редукцией А.

Определение 8. Пусть. Е - непустое множество запрещенных подмножеств состояний отличающего автомата М\А. Множество ЕсХ* называется Е-ловушкой для автомата В е Sub(M) (относительно автомата А ), если множество конечных состояний путей в автомате В\А с входными проекциями из Е имеет запрещенное подмножество из Е.

В частности, если ст « а. <5 — Z-неконформный путь в автомате М\А, то множество префиксов последовательности а является ¿'-ловушкой для всякого автомата В е Siib(M) такого, что отличающий автомат В\А имеет путь ст.a.ô.

Определение 9. Пусть М\А - автомат, отличающий M от А, с множеством состояний Q, Е - множество запрещенных подмножеств его состояний, и 3 — множество пар вида {т]'Р*у,У'), где rj• /J.у - путь в автомате М\А, и V'czX'. Множество Л называется М-покрывающим множеством для А (относительно Е), если для любого неконформного автомата ВеSub(M) найдется пара (7}./3«у,Г)е5 такая, что отличающий автомат В\А имеет путь T}*f}*y, и множество V является ^-ловушкой для В.

Если множество Л является М-покрывающим множеством для А относительно Е, то полный проверяющий тест относительно модели <A,<,Sub(M)> может быть построен следующим образом. Для каждой

пары (t]*p*y, F')e Л строится множество Е{т\*Р*у, V) входных последовательностей, которое для всякой системы Р ¿'-конформных ¿/-совместимых представителей множеств Path{%)\t]*p*y, %gV, включает последовательности множеств axW{C), ... , akW(C), где о>а,.5,, 1 <i<k -пути из Р с конечными состояниями, образующими запрещенное подмножество СвЕ, а ЩС) - характеристическое множество для С.

Теорема 3. Пусть М\Л - автомат, отличающий М от А, Е - множество запрещенных подмножеств его состояний, и 3 - ¿/-покрывающее множество для А относительно Е. Объединение множеств E(r]*f}*y,V') по всем шрам (т)*р,у, V) е 3 является полным проверяющим тестом относительно модели <А,<, Sub (М) >.

Предлагаемый в диссертации метод построения М-покрывающего множества основан на ограниченном переборе путей в отличающем автомате М\А, удовлетворяющих достаточным условиям определения 9. Анализ известных методов построения тестов показывает, что перебор может быть сокращен, если при проверке этих условий используется заранее заданное множество входных последовательностей VaX". Именно для него мы находим множество Р путей такое, что множество всех пар (o*a>8,VvPref(a)), а*а*8еР, является Л/-покрывающим множеством. Множество V может быть выбрано, в частности, состоящим из единственной пустой последовательности е\ однако в этом случае оно не приводит к сокращению перебора. Рекомендации по выбору V для получения более короткого М-покрывающего множества приводятся в главах 3 и 4 диссертации.

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

Рассмотрим множество P<zPath(X*) ^-конформных путей в отличающем автомате М\А и путь cr-a^SePalh(X'). Путь arj.afl>Sy в автомате М\Л называется Е-полным продолжением пути а*а*8 в

множестве Р, если он является ¿'-избыточным продолжением ст<а.8 в Р, или некоторое подмножество конечных состояний путей из P\jPref{сгт]*af}*8y) является элементом ¿.

Будем говорить, что путь ог]*а.р*8у является Е-избыпючным (Е-полным) продолжением пути ст.а.8 относительно непустого множества VczX' входных последовательностей, если он является ¿-избыточным (¿-полным) продолжением <у»а*8 в любой системе ¿-конформных ¿/-совместимых представителей множеств Path{x^](rr}*ccp*8y, %eV. Если путь оц<аР'8у является ¿-полным, но не является ¿-избыточным продолжением пути сг-а-8 относительно V, то мы говорим, что at].afi>oy является Z-конфликтным продолжением пути сг*а*8 относительно V.

Путь ori*afi*8y называется минимальным Е-конфликтным продолжением пути а* а* 8 относительно V, если он является ¿-конфликтным продолжением ст.а.8 относительно V, а никакой его собственный префикс не является. Показано, что для всякого пути длина всех его минимальных ¿-конфликтных продолжений ограничена сверху. Поэтому множество всех минимальных ¿-конфликтных продолжений любого пути относительно данного множества V конечно.

Теорема 4. Пусть М\А - автомат, отличающий М от А, и VcX" -множество входных последовательностей, содержащее пустую последовательность е. Тогда множество всевозможных пар (сгт]>af5*8y,VuPref(aP)), где a*a*8&Path(V), и ст)*ар*8у -минимальное детерминированное ¿-конфликтное продолжение сх*а*8 относительно V, является М-покрывающим множеством.

Л/-покрывающее множество Л, построенное в соответствии с теоремой 4, является безызбыточным в том смысле, что для любой пары (rj*fl,y, У')еЗ найдется неконформный автомат В е Sub(M) такой, что ц*р*у является путем в автомате В\А, и множество V является ¿-ловушкой для В.

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

Третья глава посвящена разработке методов построения полного проверяющего теста для частных случаев модели <A,<,Sub(M)>, часто встречающихся в литературе. Все описанные в этой главе методы имеют в своей основе общий метод, предложенный во второй главе, однако при этом упрощены с учетом особенностей каждого частного случая.

В параграфе 3.1 рассматривается модель <A,<,Sub(M)>, где А -недетерминированный автомат с попарно «-несовместимыми состояниями, а М — мутационный автомат произвольной структуры. Частным случаем этой модели является случай, когда эталонный автомат является детерминированным и приведенным. Поскольку всякие два состояния эталонного автомата s-несовместимы, любая пара Sit, s2t (si^s2) состояний отличающего автомата М\А образует запрещенное подмножество. Поэтому удалось сформулировать достаточные условия полноты и избыточности продолжений путей, основанные на подсчете количеств состояний мутационного автомата, которые являются проекциями конечных состояний этих путей. Применение этих условий вместо условий полноты и избыточности продолжений путей позволяет снизить трудоемкость построения Л/-покрывагощего множества.

Показано, что максимальная длина продолжений путей множества Path (V), которые приходится рассматривать при построении М-покрывающего множества, зависит от множества V. С целью сокращения общей длины путей М-покрывающего множества предлагается следующая рекомендация по выбору множества V: в качестве V выбирается максимальное префикс-замкнутое множество входных последовательностей такое, что множества конечных состояний путей в отличающем автомате М\А, помеченных последовательностями из V и не пересекающих запрещенных состояний, попарно не пересекаются. Проведенные эксперименты (глава 4) показали, что тесты, построенные на основе выбранного таким образом множества V, являются наиболее короткими.

В параграфах 3.2 и 3.3 рассматривается мутационный автомат специального вида, множество подавтоматов которого содержит все (с точностью до изоморфизма) детерминированные автоматы с количеством состояний, не превышающим заданного целого числа т. Такой мутационный автомат называется хаос-машиной, обозначается Chm(X,Y) и

позволяет описать известную модель «черного ящика». В параграфе 3.2 предлагается метод построения теста для произвольного недетерминированного эталонного автомата и мутационного автомата типа хаос-машины, не требующий построения отличающего автомата М\А. Другими словами, тест строится только по эталонному автомату. Вместо путей в отличающем автомате М\А анализируются соответствующие им пути в эталонном автомате Л, называемые их Л-проекциями.

В пункте 3.2.2 вводится понятие /и-покрывающего множества, которое является аналогом Д/-покрывающего множества из главы 2, но содержит только пути в эталонном автомате А.

Определение 10. Пусть А - эталонный автомат с множеством состояний S, М - хаос-машина с т состояниями, и 3А - множество пар вида (jj*ß*y,V'), где rj.ß.y - путь в эталонном автомате А, и VсХ*. Множество 3А будем называть т-покрывающим множеством для А, если для любого неконформного автомата BeSub(M) найдется пара (<т.а.<5, V')e3A такая, что либо последовательность а переводит отличающий автомат В\А из начального состояния в состояние ошибки Fail, либо в автомате В\А имеется путь с А -проекцией и V является ловушкой для В.

Полный проверяющий тест на основе /и-покрывающего множества может быть построен следующим образом. Для каждой пары (ri*ß*y,V')eUA строится множество E(t]*ß*y,V) входных последовательностей, которое включает:

- последовательность )3;

- все последовательности множества V;

- все последовательности множества a.ifV(shsак1¥(х¡,sк) для каждой пары совместимых путей cr, .а, »5,, ok.aic,öti=PathA(V')\ri.ß+y, с ¿■-несовместимыми конечными состояниями j ( и sk соответственно. Теорема 5. Пусть А - эталонный автомат, m> 1 - некоторое целое число

3А - /»-покрывающее множество для А. Объединение Е множеств E(t].ß>y,V') по всем парам (r)-ß-ybV')&3A является полным проверяющим тестом относительно модели <A,<,Sub(Chm(X,Y))>.

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

Пусть Р — множество совместимых путей в автомате А и оц*а[}*8у, - продолжение некоторого пути а*а*8&Р, совместимое с путями множества Р. Мы определяем функцию ёР г1 : 5 —> 2, называемую функцией подсчета состояний. Для всякого состояния .V е .5 значение функции (л') вычисляется следующим образом. Рассматривается

множество содержащее всевозможные последовательности

состояний двух видов:

- последовательности вида где 1 </1</2<...</^</ и

- последовательности вида (¡5Пз1г...вцс, где с{ - конечное состояние одного из путей множества Р, 1 </'1 </2<... </*</ и

Значение #Р т) (ж) полагается равным длине самой длинной цепочки множества 97(5).

С применением функции подсчета состояний сформулировано и доказано утверждение о достаточных условиях ¿"-полноты путей с заданными А -проекциями. Как следствие этого утверждения, предлагается следующая схема построения т-по врывающего множества. Для каждого пути с*а.*5еРаЛл(У) строится множество Зл(а>а-8) его всевозможных минимальных продолжений стт}»а/3«(5у таких, что для любой системы Р совместимых представителей множеств Ра&А{х)\сгП*аР*Зу, х^У, выполняется хотя бы одно из двух условий:

(*) некоторый префикс <хц' *а.р' *8у', Р'#е, пути ац*аР*8у содержится в множестве Р;

(**) существует множество О попарно 5-несовместимых состояний автомата Л такое, что X » (•*) > т ■

Далее, строится множество 3А всевозможных пар (аг)*ар*8у,У), где а*а*8еРа(ЬА(У), ац*ар*8у&Зл(<г*а>8) и Р=0, если для всех систем Р выполняется условие (*), и ¥'=У<иаРге/(р) в противном случае.

Теорема 6. Множество 3А является яг-покрывающим множеством для А. Параграф 3.3 содержит метод построения теста для случая, когда все состояния эталонного автомата попарно ^-несовместимы, а М -хаос-машина. Показано, что в рассматриваемом частном случае построение

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

Теорема 7. Пусть А - эталонный недетерминированный наблюдаемый автомат с попарно «-несовместимыми состояниями, т>\ - целое число, V — множество входных последовательностей с пустой последовательностью е такое, что множества конечных состояний путей из РшЬА(а), аеУ, попарно не пересекаются, и ¡V — объединение характеристических множеств пар состояний автомата А. Тогда множество УРге/(Хт~{,'' +1)IV является полным проверяющим тестом относительно модели <А,<,БиЬ{ С к т(Х, У)) >.

Данная теорема является обобщением метода Василевского на случай недетерминированного эталонного автомата.

В четвертой главе приводятся результаты экспериментов с пакетом компьютерных программ, реализующих разработанные в диссертации методы синтеза полных проверяющих тестов относительно модели <А,<,ЗиЬ(М)>. В параграфе 4.1 описаны эксперименты, направленные на разработку рекомендаций по выбору основных параметров метода. В частности, показано, что в качестве основы для построения М-покрывающего множества следует выбирать максимальное префикс-замкнутое множество V входных последовательностей со свойством: для любых двух последовательностей V множества

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

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

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

экспериментов были взяты контрольные примеры схем (benchmarks), традиционно применяемые для оценки качества того или иного метода построения теста. Результаты экспериментов показывают, что тест, полный относительно выходных неисправностей, может быть построен за короткое время, имеет небольшую длину и очень высокую полноту относительно различных классов неисправностей, традиционно рассматриваемых в технической диагностике: одиночных константных неисправностей (около 96%), и неисправностей типа перепутывания входов (около 99%).

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

- перечисление неисправных автоматов сети;

- построение теста для автомата сети методом Василевского;

- построение теста для автомата сети в классе подавтоматов мутационного автомата сети;

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

примеров, позволяют сделать следующее заключение. Тесты, построенные тосредством перечисления неисправностей, имеют небольшую длину, однако могут быть получены лишь для очень маленьких схем из-за шачительных временных затрат. Метод Василевского доставляет тесты с )чень большой общей длиной, которые являются избыточными, поскольку 5олыпая часть автоматов класса неисправностей не описывает сетей с ¡аданной исправной компонентой. При последних двух подходах фименимы методы построения тестов, разработанные в диссертации. Они юзволяют за приемлемое время получать полные тесты для сети с [справной компонентой, значительно более короткие, чем тесты, юстроенные по методу Василевского.

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

Заключение

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

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

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

3) Методы построения полных проверяющих тестов для частных случаев задачи, разработанные на основе общей стратегии:

- метод построения теста для детерминированного приведенного автомата (или недетерминированного автомата с попарно ¿-несовместимыми состояниями) и класса неисправностей, состоящего из подавтоматов произвольного мутационного автомата;

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

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

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

Список публикаций автора по теме диссертации

1) 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. - pp. 215-233.

2) Куфарева И.Б, Петренко А.Ф., Евтушенко Н.В. Синтез проверяющих тестов для недетерминированных автоматов относительно редукции. -Автоматика и вычислительная техника, №3, 1998. - С. 10-21.

3) Куфарева И.Б, Евтушенко Н.В. Синтез проверяющих тестов для недетерминированных автоматов относительно редукции в классе автоматов с неисправностями выходов. - Материалы Второй международной конференции «Автоматизация проектирования дискретных систем». - Минск, 1997. - Т.З. - С. 51 -58.

4) Куфарева И.Б, Евтушенко Н.В. Технология разработки методов построения тестов для недетерминированных автоматов. -Международная конференция «Всесибирские чтения по математике и механике», тезисы докладов. - Томск: изд-во ТГУ, 1997. - Т. 1 -С.156-157.

5) Куфарева И.Б, Евтушенко Н.В. Технология разработки методов построения тестов для недетерминированных автоматов. — Международная конференция «Всесибирские чтения по математике и механике», избранные доклады. - Томск: изд-во ТГУ, 1997. - Т.1. -С.165-171.

6) Евтушенко Н.В., Куфарева И.Б, Петренко А.Ф. К распознаванию свойств конечно-автоматных отображений. - III сибирский конгресс по индустриальной и прикладной математике INPR1M-98. Тезисы докладов, часть 4. - Новосибирск: изд-во ИМ СО РАН, 1998. - С. 94.

7) Куфарева И.Б. Исследование отношений между недетерминированными автоматами. - Тезисы докладов молодых ученых СФТИ на конференции, посвященной 70-летию института. - Томск, 1998. - С. 32-33.

8) I.Koufareva. Test Suite Derivation for a Nondeterministic FSM w.r.t Reduction Relation. - Talks Presented at the Meeting on Control and FSM Synthesis and Related Testing/Validation Issues. - Berkeley, 1998 (на правах рукописи).

Введение.

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

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

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

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

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

1.2.3. Операция ^-пересечения автоматов.

1.2.4. Наблюдаемая форма автомата.

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

1.4. Применение недетерминированного автомата для описания эталонного поведения системы.

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

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

1.7. Обзор существующих методов.

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

2. Стратегия построения тестов относительно модели <А,<,8иЬ(М)> на основе отличающих автоматов.

2.1. Структура теста.

2.1.1. Построение проверяющего теста на основе верхней оценки длины отличающей последовательности.

2.1.2. Структура Василевского.

2.1.3. Обобщение структуры Василевского на случай модели <А,<,ЗиЬ(М)>

2.2. Отличающие автоматы.

2.3. Построение теста относительно модели <А,<,5иЬ(М)>.

2.3.1. М-покрывающие множества.

2.3.2. Построение теста на основе М-покрывающих множеств.

2.3.3. Построение М-покрывающих множеств.

2.3.3.1. ¿-полные и ¿-конфликтные продолжения путей.

2.3.3.2. Множества-спутники ¿-полных продолжений путей в отличающем автомате.

2.3.3.3. Применение достаточных условий ¿'-полноты и ¿-избыточности продолжения путей.

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

3. Методы построения тестов для частных случаев модели

A,<,Sub{M)>

3.1. Построение тестов для детерминированного автомата или недетерминированного автомата с попарно s-несовместимыми состояниями в классе подавтоматов произвольного мутационного автомата М.

3.1.1. Запрещенные подмножества состояний отличающего автомата и их характеристические множества.

3.1.2. Построение М-покрывающих множеств.

3.1.3. Построение теста.

3.2. Построение тестов для недетерминированного автомата в классе автоматов с ограниченным числом состояний.

3.2.1. Представление основных свойств отличающего автомата в терминах эталонного автомата.

3.2.1.1. Свойства А -проекций путей в отличающем автомате.

3.2.1.2. Ловушки.

3.2.2. Построение теста на основе m-покрывающих множеств.

3.2.3. Построение т-покрывающих множеств.

3.2.3.1. Функция подсчета состояний.

3.2.3.2. Алгоритм построения m-покрывающих множеств.

3.3. Построение тестов для недетерминированного автомата с попарно s -несовместимыми состояниями в классе автоматов с ограниченным числом состояний.

3.3.1. Основные свойства m-покрывающих множеств.

3.3.2. Построение теста.

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

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

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

4.1.1. Стратегия М-покрывающих множеств и выбор Е.

4.1.2. Выбор множества V.

4.2. Метод подсчета состояний.

4.3. Исследование качества теста, полного относительно выходных неисправностей.

4.3.1. Одиночные константные неисправности и перепутывания входов

4.3.2. Неисправности, не увеличивающие число состояний.

4.4. Построение тестов для компонент автоматных сетей.

4.4.1. Построение теста на основе автомата сети.

4.4.2. Построение теста на основе сетевого эквивалента компоненты в присутствии контрольной точки.

4.4.3. Построение теста на основе сетевого эквивалента компоненты без контрольной точки.

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

Общая характеристика

Актуальность проблемы. Тестирование является одним из важнейших этапов в процессе проектирования, производства и эксплуатации систем логического управления. Оно имеет своей целью контроль правильности функционирования системы. Проверка функционирования осуществляется путем подачи на вход системы определенных последовательностей входных воздействий - тестов, и наблюдения выходных реакций системы с последующим их анализом [1, 2, 4-6]. Если о характере возникающих в системе неисправностей ничего неизвестно, то в процессе тестирования может быть обнаружена ошибка; однако, если ошибки не обнаружены, это не гарантирует исправности системы. Поэтому обычно тестирование проводится в предположении, что возможны только неисправности определенного класса. Известно, что для всякого конечного множества неисправностей [2], а также для некоторых бесконечных [16, 40-42], существует конечный набор входных последовательностей, при подаче которого на вход тестируемой системы обнаруживаются все неисправности данного множества. Этот набор называется полным проверяющим тестом относительно данного множества неисправностей. Тестирование с применением полных тестов позволяет, в зависимости от выходных реакций системы на последовательности теста, сделать заключение либо о неправильности функционирования системы, либо об ее исправности в смысле отсутствии в ней ошибок данного класса. Проблема генерации полных тестов заключается в нахождении возможно меньшего набора входных воздействий, обнаруживающего все неисправности класса.

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

Существующие методы генерации тестов для систем логического управления могут быть условно разделены на структурные и абстрактные. В основе структурного подхода лежит представление системы в виде сети из элементарных логических элементов - вентилей. Если сеть представляет собой комбинационную схему, то есть ее реакция на очередной входной сигнал не зависит от поступивших ранее сигналов, то тест для нее может быть получен с применением многочисленных методов построения тестов относительно константных неисправностей [3]. Известно [3, 7, 8], что тесты, построенные для таких схем в предположении, что имеют место только одиночные константные неисправности, обнаруживают также высокий процент неисправностей другого рода, то есть являются достаточно качественными, а длина их не слишком велика. Основным недостатком данных методов является необходимость явного перечисления всех константных неисправностей, что представляет собой трудоемкую задачу, поскольку число вентилей в современных схемах огромно. Кроме того, неисправности, возникающие, например, в КМОП-схемах, нередко приводят к увеличению числа состояний [9], в результате чего схема из комбинационной превращается в последовательностную, и полнота тестов, построенных относительно константных неисправностей, резко падает.

Методы построения тестов относительно константных неисправностей могут быть использованы и в случае, когда схема содержит элементы памяти [5, 10]. Однако в этом случае требуется предварительное построение так называемого комбинационного эквивалента схемы, который для реально существующих схем имеет очень большую размерность. Необходимость перечисления константных неисправностей в схеме при построении тестов, а также низкая полнота построенных тестов в связи с возможным увеличением числа состояний в неисправных схемах ограничивают применимость структурного подхода. Структурный подход также неприменим в случае, когда система описана в некотором абстрактном формализме (например, с помощью конечного автомата): при этом сеть элементарных логических элементов, реализующая данную систему, вообще неизвестна.

Абстрактный подход к проблеме генерации тестов состоит в рассмотрении тестируемых систем с точки зрения их поведения, при отвлечении от внутренней структуры. В качестве математической модели поведения систем логического управления часто применяется конечный автомат [2, 4-6], адекватно отражающий специфику последовательностных систем. Модель конечного автомата традиционно используется в технической диагностике [3, 12], а в последнее время с успехом применяется также в области тестирования программного обеспечения и протоколов вычислительных сетей [13-15]. При данном подходе предполагается, что исправное поведение тестируемой системы описывается конечным автоматом, равно как и ее поведение при наличии неисправности. Таким образом, моделью возникающих в системе неисправностей служит некоторое множество конечных автоматов, называемое классом неисправностей, а полным проверяющим тестом - множество входных последовательностей, обнаруживающее все неисправные автоматы этого класса.

Выбор класса неисправностей представляет собой самостоятельную задачу, решение которой требует глубокого изучения предметной области. Выбранный класс должен адекватно отражать неисправности, часто встречающиеся на практике. При этом следует иметь в виду, что чем выше мощность выбранного класса неисправностей, тем длиннее, как правило, тесты, обнаруживающие все неисправности этого класса. В ряде известных работ по построению тестов для конечных автоматов [12, 13, 17-20, 38] делается предположение о том, что неисправности не увеличивают числа состояний в системе, или увеличивают его в некоторых пределах. Другими словами, в качестве класса неисправностей рассматривается множество всех автоматов с количеством состояний, не превышающим заданного целого числа. Методы [12, 13, 17-20, 38] построения полных проверяющих тестов относительно таких классов привлекательны тем, что они не требуют явного перечисления неисправностей. Однако тесты, полные относительно класса неисправностей, не увеличивающих числа состояний системы, имеют очень большую длину, поскольку мощность такого класса экспоненциально возрастает с ростом числа состояний системы; при этом они не являются полными относительно возникающих на практике неисправностей, так как последние в ряде случаев увеличивают число состояний системы. Тесты, построенные в предположении, что количество состояний системы в результате возникновения неисправности может возрасти, но ограничено сверху некоторым целым числом, вообще неприменимы на практике из-за своих огромных размеров. В реальных ситуациях в качестве проверяющего теста часто используется обход графа переходов автомата, описывающего поведение исправной системы [4, 21], однако полнота такого теста остается мало изученной.

В связи с вышесказанным, необходима математическая модель неисправности, которая, будучи достаточно компактной, позволяет в то же время гибко отражать различные реальные ситуации. В данной работе в качестве такой модели предлагается так называемый мутационный автомат, представляющий всевозможные ошибочные переходы, которые могут иметь место в неисправной системе. Таким образом, класс неисправностей описывается множеством всех подавтоматов мутационного автомата. Прототипом мутационного автомата является введенная в работе [22] функция неисправности, которая также фигурировала в ряде других работ [23]. В отличие от функции неисправности, мутационный автомат позволяет представить в том числе и неисправности, увеличивающие число состояний системы. Как подклассы класса подавтоматов мутационного автомата могут быть описаны важнейшие классы неисправностей, рассматриваемые в технической диагностике: константные неисправности, короткие замыкания на входах схемы, перепутывания и инверсии входов и др. [6], а также неисправности элементов памяти [24-27] и протоколов вычислительных сетей [22].

В классической технической диагностике [3, 12] система считается исправной, если и только если ее поведение на всех входных последовательностях совпадает с поведением заданного детерминированного автомата, называемого эталонным автоматом. Это требование оказывается слишком сильным, если речь идет о тестировании устройства со сниженной управляемостью и/или наблюдаемостью [28, 29], или о тестировании сетевых протоколов [35-38]. В этих ситуациях допускаются некоторые изменения в поведении системы, которые не влияют на ее пригодность, то есть система может оказаться пригодной к эксплуатации, несмотря на то, что ее поведение отличается от эталона; в технической диагностике такие изменения носят название необнаружимых или несущественных неисправностей. В ряде случаев [29-38] допустимые отклонения в поведении системы могут быть описаны с помощью недетерминированного автомата, который рассматривается в качестве эталона поведения системы. Система исправна, если ее поведение «содержится» в поведении этого автомата.

На данный момент методов построения тестов для недетерминированного эталона практически не существует. В немногочисленных работах [40-42], посвященных этой теме, в качестве класса неисправностей рассматривается бесконечное множество автоматов, для которого не обязательно существует конечный тест, вследствие чего указанные работы представляют скорее теоретический интерес. В работах по тестированию соответствия сетевых протоколов [35, 36] рассматривается узкий класс частных случаев, и полнота построенных тестов не гарантируется.

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

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

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

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

Практическая ценность. Предложенная в работе модель неисправности может быть использована для описания наиболее часто возникающих неисправностей в элементах памяти [24-27], управляющих автоматах [22], многокомпонентных устройствах при условии, что неисправна не более чем одна компонента [32, 33], и т.д. Разработанные методы позволяют во всех указанных случаях генерировать тесты разумной длины с высоким процентом обнаружения реально возникающих неисправностей.

Реализация полученных результатов. Исследования, результаты которых изложены в диссертации, проводились в рамках работ по госбюджетной тематике Сибирского физико-технического института при Томском государственном университете (ТГУ) (программа 1995-2000 гг. «Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем», шифр «Диаконт», раздел «Разработка методик и аппаратуры исследований»). Разработанные в диссертации способы представления необнаружимых неисправностей с помощью недетерминированных автоматов и методы построения тестов для них нашли применение в теоретических исследованиях по гранту РФФИ (проект № 99-01-00337 «Решение автоматных уравнений и неравенств», 1999-2000). Методы генерации проверяющих тестов для недетерминированных автоматов были также использованы в процессе работы по гранту НАТО совместно с научной группой университета г. Беркли, США. Полученные теоретические результаты внедрены в учебный процесс и используются при подготовке курсов «Теория автоматов» и «Техническая диагностика» на радиофизическом факультете ТГУ и курса «Техническая диагностика» на факультете прикладной математики и кибернетики.

Предложенные методы синтеза проверяющих тестов были реализованы в виде пакета прикладных программ в работах по межвузовской научно-технической программе «Конверсия и высокие технологии. 1997-2000 гг.» (проект № 95-1-21 «Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления»). В пакет входят программы построения полных тестов для недетерминированного эталонного автомата и различных частных случаев предложенного в работе класса неисправностей, а именно: класса всех автоматов с количеством состояний, не превышающим заданного целого числа («метод подсчета состояний»), и класса автоматов с неисправностями выходов.

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

Апробация работы. Научные результаты [48-55], составившие основу данной работы, по мере их получения обсуждались на заседаниях объединенного семинара кафедры математической логики и проектирования радиофизического факультета ТГУ, кафедры программирования факультета прикладной математики и кибернетики ТГУ и лаборатории синтеза дискретных автоматов Сибирского физико-технического института (СФТИ) при ТГУ. Кроме того, они докладывались на конференциях, в том числе международных, в г. г. Будапеште, Минске, Новосибирске и Томске, что подтверждается соответствующими публикациями докладов и тезисов докладов [48-50, 52, 54, 55], и на научном семинаре в г. Беркли, США [53]. Также эти результаты обсуждались и были одобрены в научной группе научно-исследовательского института СИМ в г. Монреале, Канада.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Объем диссертации составляет 176 страниц текста, набранного в редакторе М8

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

В данной главе представлены результаты компьютерных экспериментов по построению полных проверяющих тестов относительно модели <А,<,8иЬ(М)> методами, предложенными в диссертации. Целью проведенных экспериментов было изучение возможности применения

158 мутационного автомата для описания различных неисправностей в системах логического управления, встречающихся на практике, а также исследование качества полных тестов относительно модели <А,<,8иЬ(М)>, построенных по методам глав 2 и 3. Результаты экспериментов позволяют сделать вывод о возможности практического применения данной модели и разработанных в диссертации методов синтеза тестов для нее.

Заключение

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

Разработан общий метод построения теста для недетерминированного автомата относительно редукции, полного в классе подавтоматов произвольного мутационного автомата. На основе этого метода предложены методы построения тестов для различных частных случае задачи. Для тех частных случаев модели <Л,<,8иЪ(М)>, для которых ранее были известны методы построения тестов, метод, предложенный в диссертации, позволяет генерировать тесты не большей, а в некоторых случаях меньшей длины. В частности, это касается случая, когда эталонный автомат А является детерминированным приведенным автоматом, а мутационный автомат М имеет произвольную структуру, и случая, когда А - произвольный недетерминированный автомат, М - мутационный автомат специального вида, описывающий всевозможные автоматы с количеством состояний, не превышающим заданного целого числа т.

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

На защиту выносятся:

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

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

3) Методы построения полных проверяющих тестов для частных случаев задачи, разработанные на основе общей стратегии:

- метод построения теста для детерминированного приведенного автомата (или недетерминированного автомата с попарно ¿-несовместимыми состояниями) и класса неисправностей, состоящего из подавтоматов произвольного мутационного автомата;

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

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

161

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

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

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

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

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

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

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

7. Бадулин С.С., Барнаулов Ю.М., Бердышев В.А. и др. Автоматизированное проектирование цифровых устройств. М.: Радио и связь, 1981, 243 с.

8. I. Kohavi, Z. Kohavi. Detection of Multiple Faults in Combinational Logic Networks. IEEE Transactions on Computers, Vol. C-21, No.6, 1972.

9. C.F. Hawkins, J.M. Soden, A.W. Righter, F.J. Ferguson. Defect classes an overdue paradigm for CMOS 1С testing // International Test Conference, 1994. -pp.413-425.

10. Ю.Матросова А.Ю. Метод обнаружения неисправностей в синхронном устройстве // Автоматика и телемеханика, 1977, №12, с 129-137.

11. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы (Поведение и синтез). -М.: Наука, 1970.

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

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

14. A. Petrenko, G. v. Bochmann, R. Dssouli. Conformance relations and testthderivation // Proceedings of 6 IFIP International Workshop on Protocol Teat Systems, France, 1993.-pp. 161-182.

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

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

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

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

19. S. Fujiwara, G.V. Bochmann, F. Khendek, M. Amalou, A. Ghedamsi. Test selections based on finite state models // IEEE Transactions, SE-17, No.6, 1991, pp. 591-603.

20. M. Yannakakis, D. Lee. Testing finite state machines: fault detection // Journal of Computer and System Sciences, 1995, 50, pp. 209-227.

21. S. Naito, M. Tsunoyama. Fault detection for sequential machines by transition tours // Proceedings of Fault Tolerant Comp, Syst., 1981, p. 238-243.

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

23. A. Petrenko, N. Yevtushenko. Test suite generation for a given type of implementation errors // Proceedings of the IFIP 12th International Conference on Protocol Specification, Testing and Verifications, 1992, pp. 229-243.

24. J.A. Brzozowski, B.F. Cockburn. Detection of Coupling Faults in RAMs // Journal of Electronic Testing: Theory and Applications, No.l, 1990, pp. 151-162.

25. B.F. Cockburn, J.A. Brzozowski. Near-optimal tests for classes of write-triggered coupling faults in RAMs // Journal of Electronic Testing: Theory and Applications, No.3, 1992, pp. 251-264.

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

27. R. David, J.A. Brzozowski, H. Jurgensen. Random test length for bounded faults in RAMs // Proceedings of the 3rd European Test Conference, The Netherlands, 1993, pp. 149-158/

28. Горяшко А.П. Синтез диагностируемых схем вычислительных устройств. -М.: Наука, 1987.-287 с.

29. Watanabe Y., Brayton R.K. The maximum set of permissible behaviors for FSMS network // Trans. Of IEEE / ACM Int. Conf. On Compute-aided design. 1993.-p. 316-328.

30. Т.Кат, T.Villa, R.Brayton, A. Sangiovanni-Vincentelli. Synthesis of finite state machines: functional optimization. Kluwer Academic Publishers, 1997. -283 p.

31. A. Petrenko, N.Yevtushenko, G. v. Bochmann. Fault models for testing in context // Proceedings of the IFIP 1st Joint International Conference FORTE/PSTV. Chapman & Hall, 1996. pp. 163-178.

32. A. Petrenko, N.Yevtushenko, R.Dssouli. Testing strategies for communicating FSMs // Proceedings of the IFIP 7th International Workshop on Testing of Communicating Systems, 1994, pp. 193-208.

33. A. Petrenko, N.Yevtushenko, G. v. Bochmann, R.Dssouli. Testing in context: framework and test derivation // Computer communications, Vol. 19, pp. 1236-1249, 1996.

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

35. M. Ghriga, P.G. Frankl. Adaptive testing of nondeterministic communication protocols // Proceedings of the IFIP 6th International Workshop on Protocol Test Systems, 1993. pp. 349-363.

36. A. Petrenko, N. Yevtushenko., G.v. Bochmann. Testing Deterministic Implementations from Nondeterministic FSM Specifications. Proceedings of IFIP TC6 9th International Workshop on Testing of Communicating Systems, Germany, 1996, pp. 125-140.

37. P.H. Starke. Abstract Automata, North-Holland/American Elsevier, 1972, 4191. P

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

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

40. S. Boroday. Distinguishing tests for nondeterministic finite state machines.th *

41. Testing of Communicating Systems. Proceedings of 11 International Workshop on Testing of Communicating Systems. Kluwer Academic Publishers, 1998.-pp. 101-107.

42. Pomeranz, S.M. Reddy. Test generation for multiple state-table faults in finite-state machines // IEEE Transactions on Computers, Vol. 46, No 7, pp. 782-794, 1997.

43. S.H. Unger. Asynchronous sequential switching circuits. Wiley-interscience.

44. A. Petrenko, N. Yevtushenko, G.v. Bochmann. Experiments on nondeterministic systems with respect to the reduction relation. University of Montreal, Dept. Publ. #932, 1994.

45. A. Petrenko, N. Yevtushenko. Solving asynchronous equations // Formal Description Techniques / Protocol Specification, Testing and Verification. Kluwer Academic Publishers, 1998. pp. 125-140.

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

47. Куфарева И.Б., Евтушенко Н.В. Технология разработки методов построения тестов для недетерминированных автоматов. -Международная конференция "Всесибирские чтения по математике и механике", тезисы докладов. Томск: изд-во ТГУ, 1997. - Т. 1 -С.156-157.

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

49. Евтушенко Н.В., Куфарева И.Б., Петренко А.Ф. К распознаванию свойств конечно-автоматных отображений. III сибирский конгресс по индустриальной и прикладной математике INPRIM-98. Тезисы докладов, часть 4. - Новосибирск, изд-во ИМ СО РАН, 1998. - С. 94.

50. I.Koufareva. Test Suite Derivation for a Nondeterministic FSM w.r.t Reduction Relation. Talks Presented at the Meeting on Control and FSM Synthesis and Related Testing/Validation Issues. - Berkeley, 1998 (на правах рукописи).

51. Куфарева И.Б. Исследование отношений между недетерминированными автоматами. Тезисы докладов молодых ученых СФТИ на конференции, посвященной 70-летию института. - Томск, 1998. - С. 32-33.

52. Зав. кафедрой мат. логики и проектирования РФФпрофессор1. Евтушенко Н.В.

53. УТВЕРЖДАЮ" ;тор СФТИ при ТГУмарта 2000 г.1. Колесник А.Г.1. СПРАВКА

54. Organisation du Traite de l' Atlantique Norjd —p^m"i

55. Division dejAjfairot JcicntifUjucj et llEnt>ironncmtnt / SçUnti/ix and Environmental Affairs Division1. P.T^MT'IOM ÏHA^e CJAH^ér

56. SA.12.302(971217) ^ ^OdiAugtiSt, 19991. Fax: 4-I5IO UI«^1. Prof. RJC. Brayton

57. Electrical Engineering Si. Computer Science

58. University of California p—

59. Room 573 Cory Hall rQc I M H31. Berkeley, CA 94720-17701. USA.1. Dear Professor Brayton,

60. CTRICAT. ENGINEERING & COMPUTER SCIENCE

61. MVERSITY OF CALIFORNIA, BERKELEY

62. RKELEY . DAVIS . IRVINE . LOS ANGELAS • RIVERSIDE • SAN DIEGO . SANFRAN'CSCO

63. SANTA SAJUAK/. • SANTA CRU

64. CORY HAIL t 1770 iRKELEY CA 9472C-1770bnjwn® ecc3.bcrkc!cy,cdu httpi//,w»w.eec5.bei'!«!ey^du/ -brayton (510) 643-9S01 Fax: 643-50521. July 26.19991. Dr. J. A Rausell-Colom

65. Programme Director for Priority Area on High Technology NATO

66. Scientific Affairs Division B-1110 Brussels Belgium1. Dear Dr. Rausell-Colom:

67. We request an extension of the NATO Travel Grant for a period of 9 months.

68. Some results in the case of the asynchronous composition operator have been published by Yevtushenko and Petrenko in the paper "Solving Asynchronous Equations".

69. Robert K. Brayton Professor