Введение к работе
Актуальность проблемы. Тестирование является одним из важнейших этапов в процессе проектирования, производства и эксплуатации систем логического управления. Целью тестирования является проверка правильности функционирования системы посредством анализа ее реакций на определенные последовательности входных воздействий - тесты. Обычно тестирование проводится в предположении, что возможны только неисправности определенного класса. Проблема генерации полных тестов заключается в нахождении возможно меньшего набора входных воздействий, обнаруживающего все неисправности класса.
В качестве математической модели поведения систем логического управления часто используется конечный автомат. При данном подходе предполагается, что исправное поведение тестируемой системы описывается конечным автоматом, равно как и ее поведение при наличии неисправности. Моделью возникающих в системе неисправностей служит некоторое множество конечных автоматов, называемое классом неисправностей. Методам построения полных проверяющих тестов для конечных автоматов посвящен ряд работ российских и зарубежных ученых: А.М.Богомолова, И.С.Грунского, Д.В.Сперанского, В.А.Твердохлебова, М.П.Василевского, Н.В.Евтушенко, А.Ф.Петренко, G.v.Bochmann, T.S.Chow, S.Fujiwara, D.Lee, M.Yannakakis и др. В большинстве работ в качестве класса неисправностей рассматривается множество всех автоматов с количеством состояний, не превышающим заданного целого числа; данная модель носит название модели «черного ящика».
В диссертации предлагается новая математическая модель для компактного описания неисправностей различных классов. Данная модель основана на применении так называемого мутационного автомата, то есть недетерминированного автомата, представляющего всевозможные ошибочные переходы, которые могут иметь место в неисправной системе. Класс неисправностей описывается множеством всех подавтоматов мутационного автомата. Прототипом мутационного автомата является введенная И.С.Грунским и А.Ф.Петренко в 1988 г. функция неисправности; но в отличие от нее, мутационный автомат позволяет представить в том числе и неисправности, увеличивающие число состояний системы.
Для описания эталонного поведения системы в диссертации также предлагается использовать недетерминированный автомат. Такой автомат позволяет представлять необнаружимые или несущественные неисправности в системе, например, при тестировании систем со сниженной управляемостью и/или наблюдаемостью, а также при тестировании протоколов вычислительных сетей. Способы построения таких автоматов для различных задач известны из работ А.Ф.Петренко, Н.В.Евтушенко, R.K.Brayton, S.Unger, Y.Watanabe и др. Система исправна, если реализуемый ей язык входо-выходных последовательностей содержится в языке этого автомата. На данный момент существует очень мало публикаций, посвященных построению тестов для недетерминированного эталонного автомата. В работах Б.ДЛукьянова и С.Ю.Бородая в качестве класса неисправностей рассматривается бесконечное множество автоматов, для которого не обязательно существует конечный тест. В публикациях по тестированию соответствия сетевых протоколов, в частности, в работах P.Tripathy, K.Naik, M.Ghriga, P.G.Frankl и др., рассматривается узкий класс частных случаев, и полнота построенных тестов не гарантируется.
Таким образом, разработка методов построения потных проверяющих тестов для недетерминированных автоматов относительно класса подавтоматов произвольного мутационного автомата представляется актуальной проблемой, требующей активного исследования.
Цель работы. Создание общей стратегии построения тестов с гарантированной полнотой для недетерминированных автоматов и классов неисправностей, описанных при помощи мутационных автоматов. Разработка на базе этой стратегии методов построения полных проверяющих тестов для различных частных случаев задачи. Экспериментальная оценка эффективности разработанных методов.
Методы исследования. Для достижения поставленной цели применяется аппарат дискретной математики, теории автоматов, теории множеств и математической логики, а также компьютерные эксперименты для оценки эффективности разработанных методов.
Научная новизна. В работе предложен новый подход к проблеме синтеза проверяющих тестов с гарантированной полнотой для систем логического управления. Данный подход основан на представлении эталонного поведения системы и класса возможных ошибок в ней при
помощи недетерминированных конечных автоматов, что отличает его от существующих подходов. Предложен способ представления неисправностей в системах логического управления при помощи мутационного автомата, который позволяет компактно и гибко описывать различные виды неисправностей, встречающиеся на практике. Разработана стратегия построения полных проверяющих тестов для модели неисправности, в которой эталонный автомат является недетерминированным, а класс неисправностей задан при помощи мутационного автомата. На основе полученной стратегии предложены методы построения тестов для ряда частных случаев задачи, для которых ранее не было известно регулярных методов построения тестов, а также улучшены существующие методы для ряда других случаев.
Достоверность полученных результатов. Все научные положения и выводы, содержащиеся в диссертации, основаны на утверждениях, доказываемых с использованием аппарата дискретной математики, теории автоматов, теории множеств и математической логики. Адекватность разработанной модели неисправностей и работоспособность предложенных методов построения тестов подтверждены с помощью компьютерных экспериментов.
Практическая ценность. Предложенная в работе модель неисправности может быть использована для описания наиболее часто возникающих неисправностей в элементах памяти, управляющих автоматах, многокомпонентных устройствах при условии, что неисправна не более чем одна компонента, и т.д. Разработанные методы позволяют во всех указанных случаях генерировать тесты разумной длины с высоким процентом обнаружения реально возникающих неисправностей.
Реализация полученных результатов. Исследования, результаты которых изложены в диссертации, проводились в рамках работ по госбюджетной тематике Сибирского физико-технического института при Томском государственном университете (ТГУ) (программа 1995-2000 гг. «Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем»). Разработанные в диссертации способы представления необнаружимых неисправностей с помощью недетерминированных автоматов и методы построения тестов для них нашли применение в теоретических исследованиях по гранту РФФИ
(проект № 99-01-00337 «Решение автоматных уравнений и неравенств» 1999-2000). Методы генерации проверяющих тестов дл недетерминированных автоматов были также использованы в процесс работы по гранту НАТО совместно с научной группой университета г Беркли, США. Полученные теоретические результаты внедрены в учебны] процесс и используются при подготовке курсов «Теория автоматов» і «Техническая диагностика» на радиофизическом факультете и факультет» прикладной математики и кибернетики ТГУ. Предложенные методы синтез; проверяющих тестов были реализованы в виде пакета прикладных програмл в работах по межвузовской научно-технической программе «Конверсия і высокие технологии. 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.
11* IFIP International Workshop on Testing of Communicating Systems, Budapest, Hungary, 1999.
Результаты диссертации также обсуждались и были одобрены в научной группе научно-исследовательского института CRIM в г. Монреале, Канада.
Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Объем диссертации составляет 176 страниц, в том числе: титульный лист - 1 стр., оглавление - 3 стр., основной текст - 157 стр., библиография из 55 наименований - б стр., приложение — 9 стр.