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

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

РГВ од

1 з он

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

Тренькаев Вадим Николаевич

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

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

АВТОРЕФЕРАТ

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

ТОМСК - 2000

УДК 519.713.1; 519.718.7

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

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

профессор Н.В. Евтушенко

Официальные оппоненты: доктор технических наук,

профессор Г.П. Агибалов

кандидат технических наук, доцент Е.И. Громаков

Ведущая организация: Институт Вычислительного

Моделирования СО РАН, г. Красноярск

Защита состоится " июня 2000 г. в на заседании

диссертационного Совета Д063.53.03 при Томском

государственном университете по адресу: 634050 г. Томск, пр. Ленина,. 36.

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

Автореферат разослан " /I " мая 2000 г.

Ученый секретарь ^ 4

диссертационного Совета, к.ф.-м.н. /Э / Б.Е. Тривоженко

ЪМ^ИГп.П 1- 01«, -Г-пК О

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

Актуальность проблемы. Процесс тестирования является неотъемлемой частью проектирования, производства и эксплуатации управляющих систем. Задача синтеза проверяющего теста заключается в построении конечного множества последовательностей входных сигналов системы (теста), по реакции на которые можно определить правильность ее функционирования. При этом тест должен строиться за реальное время, иметь минимальную длину и обнаруживать большинство неисправностей заданного класса. Генерация тестов для современных систем управления невозможна без применения средств вычислительной техники, т.е. без' соответствующей математической модели. Сети из конечных автоматов или автоматные сети являются одной из математических моделей, которые используются при синтезе тестов, в частности, для систем логического управления. Компоненты такой сети описывают поведение функционально законченных блоков системы. Таким образом, задача разработки методов синтеза качественных проверяющих тестов для сетей из конечных автоматов является

актуальной. ..........

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

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

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

Научная новизна работы состоит в следующем: 1) Разработан метод представления несущественных неисправностей в компоненте автоматной сети с помощью недетерминированного автомата, который можно эффективно

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

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

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

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

Реализация полученных результатов. Предложенные методы синтеза проверяющих тестов для компоненты автоматной сети алгоритмизированы и реализованы программно. Разработанные методы и алгоритмы были использованы при выполнении научно-исследовательских работ и отражены в промежуточных и итоговых отчетах по следующим грантам и программам: . - Грант Госкомвуза (МОПО) 1998-2000 гг, раздел "Автоматика и телемеханика. Вычислительная техника", научно-исследовательская работа "Разработка математических и программных средств для проектирования оптимальных контроллеров методами структурной теории автоматов" .

. - Обменный фант НАТО 1997-2000 гг. (NATO linkage grant) между Томским госуниверситетом и Калифорнийским университетом, Беркли, "Finite State Machine Networks Design and Testing"

- Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1997-2000 гг.", раздел "Информационные технологии, электроника и связь", проект 95-1-21 "Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления"

- Госбюджетная тема "Диаконт" 1996-2000 гг., выполняемая на базе Сибирского физико-технического института при Томском госуниверситете, научно-исследовательская работа "Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред, объектов и технических систем", раздел "Разработка методик и аппаратуры исследований"

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

AI ! робиния работы. Все теоретические и практические результаты, составившие основу диссертационной работы, по мере их получения обсуждались на совместных семинарах кафедры математической логики и проектирования, кафедры программирования Томского госуниверситета и лаборатории синтеза дискретных автоматов Сибирского физико-технического института при Томском госуниверситете. Кроме того, результаты работы докладывались на российских и международных научных конференциях в Санкт-Петербурге. Гурзуфе, Томске и Екатеринбурге.

Публикации. По теме диссертации опубликовано 10 печатных научных работ, из них 1 статья в центральном издании, 2 рецензируемых доклада и 7 тезисов докладов в трудах российских п международных конференций и семинаров.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка цитированной литературы. Объем диссертации составляет 188 страниц текста (Шрифт - Times New Roman Суг, размер шрифта - 14 pt, межстрочный интервал - 1.5 строки), и том числе, титульный лист - 1с., оглавление - 4с., основной гексг, включающий 59 рис. и 5 таблиц, - 176 е., библиография из 58 наименований - 6 е., и приложения - 6 с.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ . Во введении обоснована актуальность темы диссертации, сформулирована цель исследований, излагаются научная новизна и практическая ценность полученных результатов. Приводится краткое изложение содержания работы по главам.

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

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

Формально инициальный недетерминированный автомат А есть пятерка (5Д, К,/*,.%), где 5- множество состояний с выделенным начальным состоянием X и У - соответственно входной и выходной алфавиты, /г - функция поведения автомата, которая каждой паре "состояние-входной символ" ставит в соответствие множество пар "состояние-выходной символ", т.е. ¡г£хХ->Р(5хУ). Автомат А называется детерминированным автоматом, если автомат из любого состояния под действием любого входного символа переходит в единственное состояние и выдает единственный выходной символ, т.е. |Л(,у,х)|=1 для всех и хеХ. . В детерминированном автомате вместо одной функции поведения используют две функции: функцию переходов у/ и функцию выходов <р, отображающие множество БхХ в множества 5 и У соответственно. Детерминированный автомат, в котором функция выходов не зависит существенно от входного символа называется автоматом Мура. Автомат А (5'Д", К,/;'л'0) называется подавтоматом автомата А ~ (Б,Х, У,Ь,.ч0), если Х'сХ и

/г(>Л> для всех хХ'.

Функция поведения /г обычным образом распространяется на • множество X* всех конечных последовательностей в алфавите X, включая и пустое слово, как функция А :

Функция И имеет проекцию Иу на множество У*. Множество /г Х^.а) содержит выходные последовательности, которые выдает

автомат А, находясь в состояния .у, под действием входной последовательности а. Последовательность [)е к >(.?о,«) называется реакцией автомата А на последовательность а.

Пару (а,Д), аеХ*, /?е У*, где av.fi последовательности одной и той же длины, назовем вход-выходной парой (в алфавитах X и ¥). Вход-выходная пара (а,р) в алфавитах X и У называется вход-выходной последовательностью (вход-выходным словом) автомата Л, если р есть реакция автомата Л на а. Под поведением автомата А будем понимать множество всех его конечных вход-выходных последовательностей.

Задача синтеза проверяющих тестов для автоматов заключается в построении минимального конечного множества конечных входных последовательностей такого, что по реакциям проверяемого автомата на последовательности из этого множества можно определить, соответствует ли его поведение эталонному. Проверяемый автомат считается исправным, если он находится в определенном отношении (отношении конформности) с эталонным автоматом. В диссертационной работе рассматриваются два отношения конформности: эквивалентность и редукция. Автоматы Л и В эквивалентны (обозначение: А=В), если они имеют одинаковое поведение. Автомат Л является редукцией автомата В (обозначение: А<Б), если поведение автомат Л содержится в поведении автомата В, т.е. для каждой входной последовательности множество выходных последовательностей автомата А содержится в множестве выходных последовательное гей автомата В.

Моделью неисправности называется тройка VI,-,УЛ--, где А -эталонный автомат, ~ е {=,<}- отношение конформности между эталонным и проверяемым автоматами, - область

неисправности, т.е. конечное множество автоматов с тем же входным и выходным алфавитом, что и у эталона, причем АеМ.

Полным проверяющим тестом относительно модели <А,=,9?> называется конечное множество Ее.X* такое, что для любого автомата В&91, неэквивалентного эталону А, в множестве Е существует последовательность, множества реакций на которую автоматов А и В различны.

Полным проверяющим тестом относительно модели <А<,Ш> называется конечное множество ЕаХ* такое, что для

любого автомата Бе Ж, не являющего редукцией эталона А, в множестве Е существует последовательность, множество реакций на которую автомата В не со держится, в множестве реакций эталона А.

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

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

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

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

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

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

Х\

х.з Х2

А

1

С

»

Рис. 1 Двухкомпонентная автоматная сеть Пусть /1= (^Д^х^хб-', и

С={Т^Х1уХ^7,У2хи:щ-,<рс,1()) компоненты сети /V (рис.1) суть детерминированные автоматы Мура. Тогда поведение сети /V описывается автоматом Мура хЛ'зхЛ'?, х У2, де^оХ

который называется автоматом сети Л', и в котором л'о=<7о'и11 для любых х\Х2Хт,&Х\*Х2><Хт, справедливо

Ч/ы (с/Л х,*,*-,) - у/А (с/, х,х3 <рс" (/)) у/( ( /, Х2Х3 1 (д)),

<Ры(чО= <рАу{ (я)(рсу1 (I)-Здесь и далее, если значения функции <рА определены на 2уУ, декартовом произведении алфавитов 7 и Кь то (р/х обозначает проекцию значения функции на множество IV Последовательности в алфавитах V и 2 будем называть внутренними, а в алфавитах Х\, Х2, Х3 - внешними.

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

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

Пусть Я? есть множество детерминированных автоматов Мура с тем же входным и выходным алфавитом, что и у компоненты А&9{, т.е. 91-область неисправности компоненты А. Детерминированный автомат А' называется внешне эквивалентным компоненте А, если при замене компоненты А на автомат А\ внешнее поведение сети не изменится. Обозначим через Ы множество автоматов из 91 внешне эквивалентных компоненте А. ' ~ ■

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

Технология "скобок". Полный проверяющий тест для компоненты А при доступе к ее входу и выходу относительно области неисправности 9! есть полный проверяющий тест относительно модели <А,=,9КК>.

Технология контрольных точек. Пусть N - сеть, которая получается из сети /V, при условии, что внутренний выход 2 компоненты А доступен для наблюдения, т.е. является выходом сети N , А ~ - автомат сети /V , р - множество автоматов сетей,

полученных из сети /V заменой компоненты А на автомат из множества 9АМ. Полный проверяющий тест для компоненты А при доступе к ее выходу относительно области неисправности 91 есть полный проверяющий тест относительно модели < А ~ р>.

Тестирование в контексте. Пусть Я - множество автоматов проверяемых сетей, полученных из эталонной сети /V заменой компоненты А на автомат из множества 9!. Полный проверяющий тест для компоненты при отсутствии доступа к ее входу и выходу относительно области неисправности 91 есть полный проверяющий теста относительно модели <Ан,=,3>.

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

из-за чрезмерно больших размеров области неисправности.

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

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

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

Пусть Л'=/1@С - эталонная сеть. Обозначим через 1Щ.С сеть, имеющую тот же вид, что и сеть Л-, с автоматом Мура I) вместо компоненты А.

Рассмотрим последовательности одинаковой длины а1азуе(Х1хЛ'}хи)*, а2еХ2*. Вход-выходную пару

(П] о-у.5будем называть аг-обпаружимой или обпаружимой последовательностью а2, если для любого автомата Мура£> с вход-выходным словом (сс\азу,6\р) сеть 1Ха:С и эталонная сеть !\-А@С имеют различные реакции на входную последовательность а\а2аъ. В противном случае вход-выходная пара {щи^З^р) называется аг-псо()пиружимои или пеобнарузкимой последовательностью а2.

Из определения обнаружимости вход-выходной пары {а\а,у,8]р) последовательностью а2 следует, что последовательность а,а2а3 может быть использована, как тест для обнаружения любой неисправности, преобразующей компоненту А

в автомат Мура D с вход-выходной последовательностью (iахаъу,5\Р). С другой стороны, если неисправность преобразует компоненту /1 в автомат D с вход-выходной последовательностью {щагу,5\р), которая необнаружима последовательностью аъ и компонента D реализует вход-выходную последовательность {а\аъу,д\Р) при входной последовательности сети ща2а^ то такая неисправность необнаружима тестом а.\а2аъ.

Аппроксимация B\(N,C) поведения компоненты в сети строится таким образом, чтобы описать все необнаружимые вход-выходные пары относительно каждой последовательности из алфавита Х2. Поскольку а2-необнаружимых вход-выходных пар (а\Сьу,б\Р) с одной и той же «i«3y может быть несколько, то аппроксимация в общем случае является недетерминированным автоматом. Обнаружимые вход-выходные пары представляются в аппроксимации специальным состоянием "ошибки" У7', причем переход аппроксимации в состояние 'F' отмечается выдачей выходного, символа 'f g YlxZ.

Формально, при известных (S^ViхХ2у-Х3,У1 х У2, y/N,<pN,s0) и

функция поведения аппроксимации Bx{K,C)=(PXxxX2xX3xlJ,YxxZvj{f},h,pb\ где P^{SxTyj{l,F}, pa=s0l0 имеет следующий вид. Для всех xtx2x3иеХххХ2хХ3хи и steSxT справедливо

h(st, х\х2х3 и)~

• {щ (spctx^i^c (tjc2x3z), <pN z): zeZ},

если <p( ■. "(0 = u& (pcy 2(t) = <pN y\s)\

• {(/,y,z):ytzer,xZ}, если <pc"(t) ф и;

{(F,J)}, если <p( ■" (/) -u& <pc y2 (/) * q>N y2 (s)

и h{I,xlx2x3u)={{ I,y{z):ytzeYtxZ}, h(F,xxx2x3 u)={{F,J)}.

По построенню аппроксимации, имеет место следующее теорема.

Теорема 1. Вход-выходная пара {ахагаъу,5ф) является вход-выходной последовательностью аппроксимации, если и только если пара {аха.гу,5\.Р) является а2-необнаружимой.

В разделе 2.2 предлагается метод построения сетевого эквивалента компоненты, имеющего входной алфавит Х\xX^xU и выходной алфавит Y\xZ<u{f), который в общем случае также является недетерминированным автоматом и представляет все

возможные необнаружимые вход-выходных пары в алфавитах компоненты. Состояние 'Г' в сетевом эквиваленте представляет множество всех вход-выходных пар в алфавитах компоненты обнаружимых хотя бы одной последовательностью а^Хп*.

Сетевой эквивалент В2(Л\С) строится за два шага. Вначале определяются все вход-выходные нары, необнаружимые хотя бы одной последовательностью из Х2*. Для каждого состояния и каждого входного символа л-1х1гуеА'|хЛ',х(7 множество переходов получается как объединение переходов аппроксимации по всем входным символам с проекцией равной х,х-^и. На следующем шаге полученный автомат приводится к его наблюдаемой форме, т.е. к автомату, эквивалентному исходному, в котором из любого соеюяния по любому входному символу не существует переходов в различные состояния с одним и тем же выходным символом. Состояниями полученного автомата являются подмножества состояний исходного автомата, причем соблюдается следующее условие. Если хотя бы у одного из объединяемых состояний имеется переход в состояние Т', то из получаемого объединенного состояния существует единственный переход, а именно переход в состояние Т7'. По построению сетевого эквивалента, вход-выходная пара (а^а^у.З^р) является вход-выходной последовательностью сетевого 'эквивалента, если и только если для любой ffiE.ii* данная пара ¿ь-нсобнаружима.

Теорема 2. Автоматы сетей /)(а.С и N-=Л(П-С эквивалентны, если и только если автомат й есть редукция сетевого эквивалента

к2(/\',0.

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

Гели неисправность преобразует компоненту в автомат Мура, не являющийся редукцией сетевого эквивалента, то неисправный автомат содержит хотя бы одну вход-выходную последовательность (а.\ат,у,8\р), которая не является вход-выходной последовательностью сетевого эквивалента, а следовательно обнаружима некоторой а:еХ2*. Тогда входная последовательность а^аз может служить тестом для обнаружения данной неисправности. Таким образом, сетевой

-И-

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

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

Определим индуктивно нереализуемые состояния сетевого эквивалента. Состояние 7*" нереализуемо. Если из некоторого состояния по какому-либо входному символу существует переход только в нереализуемые состояния, то это состояние также объявляется нереализуемым. Каждое нереализуемое состояние р сетевого эквивалента характеризуется множеством Ь(р) входных последовательностей компоненты, которое отличает его от любого состояния любого автомата в алфавитах компоненты. Далее такое множество будем называть характеристическим.

Приведенная форма В3(М,С) получается посредством удаления из сетевого эквивалента нереализуемых состояний и переходов в нереализуемые состояния.

Теорема 3. Автоматы сетей Ц@С и 1Ч=А@С эквивалентны, если и только если автомат Мура О есть редукция приведенной формы сетевого эквивалента В3^,С).

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

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

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

входные последовательности сети.

В разделе 3.1 рассматривается синтез тестов для компоненты при доступе к ее входу и выходу. В параграфе 3.1.1 обсуждается построение теста для компоненты, как для изолированного детерминированного автомата, т.е. как полного проверяющего теста относительно модели < А,Показывается, что тест, построенный таким образом, можег оказаться избыточным для компоненты сети. Ьолее того, данный тест определяет автоматы, внешне эквивалентные компоненте, т.е. автоматы, соответствующие несущественным неисправностям компоненты, как неисправные. В параграфе 3.1.2 показывается, чго данный недостаток можно устранить, если строить тест для компоненты, как тест для приведенной формы сетевого эквивалента компоненты, т.е. как полный проверяющий тест относительно модели <В^,С),<,!Н>.

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

I? разделе 3.2 рассматривается синтез тестов для компоненты при доступе к ее выходу, т.е. при технологии контрольных точек. Показывается, что полный проверяющий тест для компоненты можно строить, как полный проверяющий тест для сети Л'г, состоящей из приведенной формы сетевого эквивалента с наблюдаемым внутренним выходом 7 и контекста. В общем случае автомат А(!ЧХ), описывающий поведение такой сети, является недетерминированным.

Напомним, что сеть А' получается из эталонной сети /V, при наличии доступа к внутреннему выходу 2 компоненты А. Пусть 9!@2С есть множество детерминированных автоматов сетей, полученных из сети N заменой компоненты А на автомат В из множества ¡Н.

Теорема 4. Полный проверяющий тест относительно модели <А{!\у)<,Щ(1/(У' является полным проверяющим тестом для

компоненты А относительно области неисправности 91 при доступе к выходу компоненты.

Если область неисправности задана в виде списка, то тест для компоненты можно строить как объединение последовательностей, на которых поведение эталонного автомата А(Лу отличается от поведения детерминированных автоматов сетей 0@гС, Ое9?. Недостатком такого подхода является то, что не всегда область неисправности компоненты можно задать в явном виде. Например, такой подход неприемлем, если область неисправности 91 „, компоненты содержит все детерминированные автоматы с числом состояний не более некоторого числа т. В этом случае все автоматы из множества 9{(а^7С тоже имеют ограниченное число состояний равное произведению числа т и числа п состояний контекста. Тогда полный проверяющий тест относительно модели <А{№г),<,&тхп>, где ртхп есть множество детерминированных автоматов с тем же входным и выходным алфавитами, что и автомат сети Л^ и числом состояний не более т*п, является полным проверяющим тестом для компоненты А относительно области неисправности 91 т при доступе к выходу компоненты.

Отметим, что относительно модели <А(ртх„> известны методы синтеза полных проверяющих тестов, , не требующие перебора всех автоматов из области неисправности ртх„. Однако, полный проверяющий тест относительно модели <Л{1УХ)<, ртхп> является избыточным относительно модели <А(ЛУ, <,9Ки)г/С>, т.к. проверяет правильность функционирования не только компоненты, но и контекста, который предполагается исправным.

В параграфе 3.2.2.3 показывается, что для построения полного проверяющего теста относительно модели </1(А'^),<, 9Щ/С> необходимо и достаточно построить множество 9!) вход-выходных пар в алфавитах компоненты со следующим свойством. Для каждого автомата /) е 91, который не является редукцией приведенной формы сетевого эквивалента, множество Б{9Г) содержит, по крайней мере, одно вход-выходное слово автомата 1>, которое не является вход-выходным словом приведенной формы сетевого эквивалента.

Пусть а2еХ2*, ауаъу&{Х\хХ3%Ц)*, суть

последовательности одной и той же длины. Будем говорить, что пара (с^аэУД/Т) транслируется во входную последовательность

сети а,а2аз, если н-проекция выходной последовательности

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

Лемма 1. Ихли вход-выходная пара (a\a-\y,S\fi) является вход-выходным словом приведенной формы сетевого эквивалента, в то время как при добавлении вход-выходного символа (jc^hj^z) перестает обладать таким свойством, то пара ((ai.V|)(a3jc4)(yi/),(i)'i_yi)(j&)) транслируется в некоторую внешнюю входную последовательность (а^ХаусгХазХз).

Согласно данному утверждению, для каждой пары (fbiby.thfl) множества S(!ft) задача трансляции разрешима, по крайней мере для каждого кратчайшего начального отрезка со свойством из утверждения леммы, т.е. существует внешний тест аха2а^, обнаруживающий любой неисправный автомат De9? с вход-выходным словом (а{аъу,д\Р).

Множество S(ifi) транслируемых вход-выходных пар предлагается строить на основе полного проверяющего теста Т для приведенной 'формы сетевого эквивалента, т.е. полного проверяющего геста относительно модели <S3(/V,Q,<,i/f>. Если множество iff задано в виде списка, причем !){ имеет небольшую размерность, то множество S{t)i) можно построить прямым перебором автоматов из этого списка и последовательностей из множества Т. В противном случае множество S(*Ji) строится следующим образом. Для каждой вход-выходной пары в алфавитах компоненты, входная проекция которой содержится в множестве 7', в множество S( У!) включается ее минимальный непустой начальный отрезок (если существует), который не является вход-выходным словом приведенной формы.

. Для вход-выходной пары Aib в алфавитах

компоненты через а2(р) обозначим последовательность из Х2* такую, что пара (а^у^Р) транслируется во входную последовательность сети Пусть Т - полный

проверяющий тест относительно модели <B3(/V,(7),<,№> и Л\УГ) есть множество транслируемых вход-выходных пар, построенных на основе теста Т, описанным выше способом. Тогда справедлива следующая теорема.

Теорема 5. Множество а2(р) а3: /т=( а, аъ у, 8ф)с У Г)}

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

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

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

Трансляция также может быть осуществлена на основе аппроксимации поведения компоненты в сети, т.к. аппроксимация представляет множество внешних тестов для каждой существенной неисправности. По построению, состояниями сетевого эквивалента являются подмножества состояний аппроксимации. Задача трансляции сводится к выбору соответствующего внешнего входного символа х2еХ2 и состояния из предшествующего подмножества состояний сетевого эквивалента по состоянию-преемнику аппроксимации и вход-выходной паре {х^Х2,и,у\г)&Х\У.Х-!,хихУ\х2. При трансляции на основе аппроксимации для поиска входной последовательности, соответствующей данной вход-выходной паре из транслируемого множества, мы имеем обход усеченного дерева поиска и задача трансляции разрешима полиномиальным алгоритмом относительно числа символов в алфавите Х2 и числа состояний аппроксимации.

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

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

Пусть известна верхняя оценка числа состояний проверяемой компоненты т. Тогда число состояний автомата любой неисправной сети не более тхп, где п - число состояний контекста. Пусть Зту„ есть множество детерминированных автоматов с тем же входным и выходным алфавитами, что и детерминированный автомат эталонной сети А^ и числом состояний не более тхп. Тогда полный проверяющий тест относительно модели <А\,=,Зту„> является полным проверяющим тестом для компоненты Л относительно области неисправности 91т при отсутствии доступа ко входу и выходу компоненты.

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

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

область неисправности автомата Ац обозначим через /ч-СЛл1)- Если неисправность проверяемой компоненты не выводит ее из области неисправности Ш, то автомат сети с любой неисправностью в компоненте будет принадлежать множеству Г,л(Л^. Обратное, в общем случае, неверно.

Теорема 6. Полный проверяющий тест относительно модели <Ац>=,Ря^Агд>. является полным проверяющим тестом для компоненты А относительно области неисправности № при отсутствии доступа ко входу и выходу компоненты.

При данном подходе к построению полного проверяющего теста для компоненты учитывается предположение об исправности контекста, отражаются особенности области неисправности компоненты, обеспечивается компактное представление множества автоматов проверяемых сетей. Также существуют методы синтеза полных проверяющих тестов относительно модели <Ду,з,/7у,{/1,\,)>> причем без перечисления автоматов из множества

Однако, отметим, что, в общем случае, множество /'я(Ал) также содержит "лишние" автоматы, которые не описывают поведение ни одной проверяемой сети из множества неисправных сетей.

Во разделе 4.2 предложены методы синтеза полных проверяющих тестов для компоненты автоматной сети на основе недетерминированных автоматов, представляющих

несущественные неисправности в компоненте сети.

В параграфе 4.2.1 описано использование аппроксимации поведения компоненты в сети при синтезе тестов для компоненты сети.

Автомат хХ2 хХ3 х и, У, у//, <р/,(/0) называется

Хг-расширением автомата АхХ3хI], Ухц/А,<рА,Цъ), если для любых х2еХ2, х^зиеХ^Хзх/У, де^ выполняется

У л (я^ 1-ад «)= \Хзи) & гр/ (д)~<Рл(д).

Пусть по-прежнему 1)@С~сеть, имеющая тот же вид, что и эталонная сеть ЛЧ4@С, с автоматом Мура О вместо компоненты А. По построению аппроксимации, автоматы сетей 0@С и ^А@С эквивалентны, если и толь ко если ^-расширение автомата О есть редукция аппроксимации В\(1\[,С). Иными словами, детерминированные редукции аппроксимации и только они являются ^-расширениями автоматов, внешне эквивалентных проверяемой компоненте.

Теорема 7. Пусть 9?х - множество Л'2-расширений автоматов из области неисправности 9} проверяемой компоненты А. Тогда проекция полного проверяющего теста относительно модели <B](N,C),<,9?> на входной алфавит сети Xi*X2xX3 есть полный проверяющий тест для компоненты А относительно области неисправности 9t при отсутствии доступа ко входу и выходу компонент!,I.

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

говоря, является безызбыточным тестом для компоненты сети, в том смысле, что если Е есть полный проверяющий тест для компоненты А относительно области неисправности iti, то его полный прообраз есть полный проверяющий тест относительно модели <B1(N,C),<9fx>.

В параграфе 4.2.2 показывается, что для построения полного проверяющего теста для компонешы необходимо и достаточно построить множество Q( УТ) вход-выходных пар в алфавитах компоненты со следующим свойством. Для каждого автомата Dc 1>{, который не является редукцией сетевого эквивалента, множество Q{i>T) содержит вход-выходное слово автомата D, которое не является вход-выходным словом сетевого эквивалента.

В диссертационной работе показано, что если вход-выходная пара (о^а^Д/У) является вход-выходным словом сетевого эквивалента, в то время как при добавлении вход-выходного символа перестает обладать таким свойством, то пара

((а1л',)(а3х'3)(}/!(),((5',у1)(Дг)) транслируется в некоторую внешнюю входную последовательность (aw)(«№)(«л)-

Согласно данному утверждению для каждой пары (с^а^Д/?) множества {?(•'#) существует внешний тест а\а2щ, обнаруживающий любой неисправный автомат />е с вход-выходным словом («,«•,7,<У]/?). Трансляция вход-выходных пар из множества £>(А') во внешние последовательности сети можно осуществить методами, предложенными в главе 3.

Множество 0{!Н) предлагается строить на основе полного проверяющего теста для сетевого эквивалента, т.е. полного проверяющего теста относительно модели <B2(N,C)<,9I>,

аналогично способам построения множества приведенным в главе 3.

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

В параграфе 4.2.3 показано, что множество можно

строить, на основе полного проверяющего теста Т относительно модели <В^,С)<,91>, где В3(1У,С) - приведенная форма сетевого эквивалента, предварительно "расширенного" следующим образом. Для каждого начального отрезка ¡л последовательности из теста Т, который является передаточной последовательностью сетевого эквивалента из начального состояния в нереализуемое состояние р :£"/*"'' с характеристическим множеством Ц р), добавить в тест Т всс последовательности из множества //¿( р ).'

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

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

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

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

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

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

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

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

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

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

1) Метод представления несущественных неисправностей в компоненте автоматной сети недетерминированными автоматами: аппроксимацией поведения компоненты, сетевым эквивалентом и

приведенном формой сетевого эквивалента.

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

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

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

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

1. Тренькаев В.II. Метод построения функционального теста для микросхем // Диагностика, информатика и метрология - 94 (ДИМ'94): Тез. докл. науч.-техн. конф., Россия, Санкт-Петербург, 28-30 июня 1994г., С.130-131.

2. Yevtushenko N., Trenjkaev V. Digital circuit test suite derivation method based on a testable representation of a component behavior // Proceedings of XII International school and conference on computer aided design CAD-95 "New information technologies applications in science, education, medicine and business" v. I, Ukraine, Crimea, Yalta-Gurzuff, May 4-14, 1995, pp. 140-141.

3. Тренькаев B.H. Метод построения проверяющих тестов для компоненты автоматной сети // Автоматизация проектирования дискретных систем : Тез. докл. межд. конф., т.1, Беларусь, Минск, 15-17 ноября 1995 г., С. 91.

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

5. Евтушенко Н.В., Тренькаев В.Н. Синтез контрольных тестов для компоненты автоматной сети // Проблемы теоретической кибернетики: тез. докл. XI межд. конф. под ред. С.В.Яблонского.-Ульяновск: из-во СВНЦ, 1996, С. 60-61.

6. Yevtushenko N., Petrenko A., Trenkaev V. A Testing Strategy for Interacting Finite State Machines // Procceedings of the 5th Biennial Baltic Electronics Conference (BBC'96), Estonia,Tallinn, October 7-11, 1996, pp. 137-141. ....... - ...

7. Тренькаев B.H. Использование сетевого эквивалента компоненты для тестирования автоматной сети // Всесибирские чтения по математике и механике: Тез. докл. межд. конф., т.1., Математика.-'Гомск: Изд-во Том. ун-та. - 1997. - С.168-169.

8. Тренькаев В Н. Метод тестирования компоненты автоматной сети в присутствии контрольной точки /У Юбилейная конференция, посвященная 70-летию Сибирского физико-технического института при Томском госуниверситете: Тез. докл. конф., Томск, 29 сентября-2 октября 1998г., С. 48-49.

9. Евтушенко Н.В., Тренькаев В.Н. Методы синтеза тестов для компоненты автоматной сети // Доклады 2-ой всероссийской конф. "Новые информационные технологии в исследовании дискретных структур" . Екатеринбург: УрО РАН, 1998, С. 219-223.

10. N. Yevtushenko, I.Kufareva, V.Trenkaev Fault detection in embedded components of synchronous networks // Talks Presented at the Meeting on Control and FSM Synthesis and Related Testing/Validation Issues. Held in Berkeley at the Cadcnce Berkeley Labs, 1998 (на нравах рукописи).

Введение.

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

1.1. Необходимые определения и обозначения.

1.1.1. Автоматы.

1.1.2. Отношения эквивалентности и редукции между автоматами.

1.1.3. Полные проверяющие тесты для автоматов и модель неисправности.

1.1.4. Автоматные сети.

1.1.5. Синтез проверяющих тестов для компоненты автоматной сети.

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

1.1.5.2. Описание автоматом поведения двухкомпонентной сети.

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

1.2.1. Контрольные эксперименты с детерминированными автоматами.

1.2.2. Универсальный тест для модели "черного ящика".

1.2.3. Метод М.Василевского.

1.2.4. Метод идентификаторов.

1.2.5. Метод гармонизированных идентификаторов.

1.2.6. Метод на базе функции неисправности.

1.2.6.1. Функция неисправности.

1.2.6.2. Процедура построения теста.

1.2.7. Выходные неисправности.

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

1.3.1. Модифицированный метод гармонизированных идентификаторов.

1.3.2. Выходные неисправности.

1.4. Выводы по главе 1.

2. Представление несущественных неисправностей в компоненте сети с помощью недетерминированного автомата.

2.1. Аппроксимация поведения компоненты в сети.

2.2. Сетевой эквивалент компоненты.

2.3. Приведенная форма сетевого эквивалента.

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

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

3.1. Внутрисхемный контроль (технология "скобок").

3.1.1. Синтез тестов для компоненты сети, как для изолированного детерминированного автомата.

3.1.2. Синтез тестов на основе внешней эквивалентности.

3.2. Наличие контрольной точки.

3.2.1. Описание эталонного поведения проверяемой сети недетерминированным автоматом.

3.2.2. Методы синтеза тестов для компоненты в присутствии контрольной точки.

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

3.2.2.2. Ограничение числа состояний автомата проверяемой сети.

3.2.2.3. Использование приведенной формы сетевого эквивалента.

3.2.3. Трансляция внутреннего теста.

3.2.3.1. Трансляция на основе контекста.

3.2.3.2. Трансляция на основе аппроксимации.

3.3. Выводы по главе 3.

4. Синтез полных проверяющих тестов для компоненты автоматной сети при отсутствии прямого доступа к выходу компоненты.

4,1. Синтез тестов на основе автомата эталонной сети.

4.1.1. Перечисление проверяемых сетей в явном виде.

4.1.2. Ограничение числа состояний автомата проверяемой сети.

4.1.3. Задание множества проверяемых сетей с помощью функции неисправности.

4.2. Синтез тестов на основе недетерминированных автоматов, представляющих несущественные неисправности в компоненте сети.

4.2.1. Использование аппроксимации поведения компоненты в сети.

4.2.2. Использование сетевого эквивалента компоненты.

4.2.3. Использование приведенной формы сетевого эквивалента компоненты.

4.3. Выводы по главе 4.

5. Результаты компьютерных экспериментов по синтезу проверяющих тестов для компоненты сети.

5.1. Характер проведенных экспериментов.

5.2. Экспериментальное подтверждение выбранной модели неисправности.

5.3. Сравнение проверяющих тестов, полученных различными методами.

5.3.1. Синтез полных проверяющих тестов.

5.3.1.1. Описание методов.

5.3.1.2. Результаты экспериментов и их анализ.

5.3.2. Синтез неполных проверяющих тестов.

5.3.2.1. Описание методов.

5.3.2.2. Результаты экспериментов и их анализ.

5.4. Выводы по главе 5.

Актуальность проблемы. Процесс тестирования является неотъемлемой частью проектирования, производства и эксплуатации управляющих систем [1-3]. Задача синтеза проверяющего теста заключается в построении конечного множества последовательностей входных сигналов системы (теста), по реакции на которые можно определить правильность ее функционирования. При этом тест должен строиться за реальное время, иметь минимальную длину и обнаруживать большинство неисправностей заданного класса. Генерация тестов для современных систем управления невозможна без применения средств вычислительной техники, т.е. без соответствующей математической модели. Сети из конечных автоматов или автоматные сети являются одной из математических моделей, которые используются при синтезе тестов, в частности, для систем логического управления. Компоненты такой сети описывают поведение функционально законченных блоков системы.

Методы синтеза проверяющих тестов для автоматных сетей хорошо развиты для сетей специального вида, например, для сетей из вентилей [3,4] или из автоматов без потери информации [5]. Для сетей из автоматов произвольного вида существующие методы доставляют либо чрезмерно длинные тесты, что значительно затрудняет их практическое применение, либо тесты, полнота которых неизвестна, т.е. неизвестно множество обнаруживаемых тестом неисправностей. С другой стороны в теории автоматов разработаны методы синтеза проверяющих тестов с гарантированной полнотой относительно различных классов неисправностей. Таким образом, задача разработки методов синтеза качественных и достаточно коротких проверяющих тестов для сетей из автоматов произвольного вида на основе методов теории автоматов является актуальной.

Отметим, что методы синтеза проверяющих тестов для автоматных сетей должны разрабатываться при различных технологиях тестирования, т.е. при различных условиях доступа ко входам и выходам компонент сети, в частности, при технологии внутрисхемного контроля [6,7] или при наличии контрольных точек [3,8].

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

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

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

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

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

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

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

- Грант Госкомвуза (МОПО) 1998-2000 гг., раздел "Автоматика и телемеханика. Вычислительная техника", научно-исследовательская работа "Разработка математических и программных средств для проектирования оптимальных контроллеров методами структурной теории автоматов"

- Обменный грант НАТО 1997-2000 гг. (NATO linkage grant) между Томским госуниверситетом и Калифорнийским университетом, Беркли, "Finite State Machine Networks Design and Testing"

- Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1997-2000 гг.", раздел "Информационные технологии, электроника и связь", проект 95-1-21 "Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления"

- Госбюджетная тема "Диаконт" 1996-2000 гг., выполняемая на базе Сибирского физико-технического института при Томском госуниверситете, научно-исследовательская работа "Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред, объектов и технических систем", раздел "Разработка методик и аппаратуры исследований"

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

Апробация работы. Все теоретические и практические результаты [49-58], составившие основу диссертационной работы, по мере их получения обсуждались на совместных семинарах кафедры математической логики и проектирования, кафедры программирования Томского госуниверситета и лаборатории синтеза дискретных автоматов Сибирского физико-технического института при Томском госуниверситете. Кроме того, результаты работы докладывались на российских и международных конференциях в Санкт-Петербурге, Гурзуфе, Томске, Екатеринбурге.

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

Структура и объем диссертации. Диссертация состоит из введения, пяти глав, заключения и списка цитированной литературы. Объем диссертации составляет 188 страниц текста (Шрифт - Times New Roman Суг, размер шрифта - 14 pt, межстрочный интервал -1.5 строки), в том числе, титульный лист - 1с., оглавление - Зс., основной текст, включающий 59 рис. и 5 таблиц, -176 е., библиография из 58 наименований - 6 е., и приложения - 6 с.

5.4 Выводы по главе 5

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

1) Метод представления несущественных неисправностей в компоненте автоматной сети с помощью недетерминированного автомата: аппроксимации поведения компоненты, сетевого эквивалента и приведенной формой сетевого эквивалента.

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

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

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

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

1. Киносита К., Асада К., Карацу О. Логическое проектирование СБИС: Пер с япон. - М.: Мир, 1988,- 309 с.

2. Скляров В.А., Новиков С.В., Ярмолик В.Н. Автоматизация проектирования ЭВМ: Учебное пособие для вузов. Мн.: Выш.шк., 1990. -356 с.

3. Основы технической диагностики. В 2-х книгах. Книга1. Модели объектов, методы и алгоритмы диагноза. Под ред.П.П.Пархоменко-М:Энергия, 1976.-464с.

4. Гольдман Р.С., Чипулис В.П. Техническая диагностика цифровых устройств. -М.: Энергия, 1976,- 224 с.

5. Chia-Hsiasing Sung Testable sequential cellular arrays // IEEE Trans.Comput., V.C-25, №1, 1976, pp.11-18

6. Байда Н.П., Кузьмин И.В., Шпилевой B.T. Микропроцессорные системы поэлементного диагностирования РЭА,- М.: Радио и связь, 1987.- 256с.

7. Данилин Н.С., Нуров Ю.Л. Диагностика и контроль качества изделий цифровой микроэлектроники.-М.: Издательство стандартов, 1990.-176 с.

8. Убар Р. Проектирование контролепригодных дискретных систем (учебное пособие), Таллин, Таллинский политехнический институт, 1988, 68с.

9. Petrenko A., Yevtushenko N., Bochmann G.v. Fault models for testing in context // FORTE'96, 1996, September, Germany

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

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

12. Petrenko A., Yevtushenko N. Test suite generation for a FSM with a given type of implementation errors // Proceedings of the 12th IFIP TC6 International

13. Symposium on Protocol Specification, Testing and Verification, North-Holland, 1992, pp. 229-243

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

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

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

17. Тоценко В.Г. Алгоритмы технического диагностирования дискретных устройств.- М.: Радио и связь, 1985.-240с.

18. Евтушенко Н.В., Матросова А.Ю. Об одном подходе к синтезу проверяющих последовательностей для автоматных сетей // Автоматика и вычислительная техника.-1991.- №2,- С.3-7

19. Евтушенко Н.В., Лебедев А.В., Петренко А.Ф. Построение проверяющего множества для компоненты последовательной автоматной сети // Автоматика и телемеханика, 1994, № 8, с. 145-153

20. A.Petrenko, N. Yevtushenko, R.Dssouli. Testing strategies for communicating FMSs // Proc. of the 7th International Workshop Protocol Test Systems, Japan, 1994, p.181-196

21. Watanabe Y., Brayton R.K. The maximal set of permissible behaviors for FSM network // Trans, of IEEE/ACM Int. Conf. on Computer-Aided Design, 1993, pp.316-328.

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

23. Гилл А. Введение в теорию конечных автоматов. -М.: Наука, 1966,- 272 с.-17923. Hartmanis J., Stearns R. Algebraic structure theory of sequential machines. -Prentice-Hall, New York, 1966, 210 p.

24. A.Petrenko, N.Yevtushenko, G.v.Bochmann. Experiments on nondeterministic systems for (with respect to) the reduction relation, Dept.Publ.\#932 of Universite de Monreal, 1994, 24 p.

25. Hennie F.C. Fault detecting experiments for sequential circuits // Proc. of the 5th Ann. Symp. Switching Circuit Theory and Logical Design. Princeton, N.Y., November, 1964. - p. 95-110.

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

27. Агибалов Г.П., Евтушенко Н.В. Декомпозиция конечных автоматов. -Томск: Изд-во Том. ун-та, 1985. 127 с.

28. Грунский И.С. Контрольный эксперимент с сильносвязным диагностируемым автоматом // Автоматика и телемеханика.-1972.- №3.-С.138-141

29. Мур Э.Ф. Умозрительные эксперименты с последовательностными машинами.- В кн.: Автоматы. Под ред. К.Э. Шеннона и Дж. Маккарти. М., Изд-во иностр. лит., 1956, с. 179-210

30. J.I.Poage and E.J McCluskey Derivation of optimal test sequences for sequential machines // Proceedings of the IEEE fifth annual symposium on switching circuits theory and logical design, 1964, pp. 121-132

31. Fujiwara S., Bochmann v.G., Khendek F., Amalou M., Ghedamsi A. Test selection based on finite state machine models // IEEE Transactions on Software Engineering, Vol. SE-17, №6, 1991, pp. 591-603

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

33. Грунский И.С. Контроль неисправностей автомата, заданных оценочной функцией // Кибернетика и системный анализ.-1994

34. Koufareva I., Petrenko A., Yevtushenko N. Test generation driven by user defined fault models // Proceedings of IFIP TC6 12th International Workkshop on Testing of Communicating Systems, Hungary, 1999. pp. 215-233.

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

36. Chow T.S. Testing software design modelled by finite-state machines // IEEE Transactions on Software Engineering, Vol. SE-4, №3, 1978, pp. 178-187

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

38. Bochmann G.v., Petrenko A. Protocol testing: Review of methods and relevanee for software testing // In ACM 1994 Intern. Symp. on Software Testing and Analysis, pp. 109-124

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

40. Petrenko A., Yevtushenko N., Lebedev A., and Das A. Nondeterministic state machines in protocol conformance testing // Proceedings of IFIP TC6 Fifth International Workshop on Protocol Test Systems, North-Holland, 1994, pp.363378

41. Евтушенко Н.В., Лебедев А.В. О контрольном эксперименте с детерминированной реализацией при недетерминированном эталоне // Кибернетика и системный анализ.-1998.- №1.- С.57-65

42. Unger S.H. Asynchronous sequential switching circuits, New York: Wiley-Interscience, 1969

43. Закревский А.Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1979.-272 с.

44. Евтушенко Н.В., Тренькаев В.Н. Методы синтеза тестов для цифровых автоматов (Учебно-методическое пособие), Томск, Томский госуниверситет, 1997,34 с.

45. Тренькаев В.Н. Метод построения функционального теста для микросхем // Диагностика, информатика и метрология 94 (ДИМ-94): Тез. докл. науч.-техн. конф., Россия, Санкт-Петербург, 28-30 июня 1994г., С. 130-131

46. Тренькаев В.Н. Метод построения проверяющих тестов для компоненты автоматной сети // Автоматизация проектирования дискретных систем : Тез. докл. межд. конф., т.1, Беларусь, Минск, 15-17 ноября 1995 г., С. 91

47. Yevtushenko N., Petrenko A., Trenkaev V. A Testing Strategy for Interacting Finite State Machines // Procceedings of the 5th Biennial Baltic Electronics Conference (BEC'96), Estonia,Tallinn, October 7-11, 1996, pp. 137-141

48. Тренькаев В.Н. Использование сетевого эквивалента компоненты для тестирования автоматной сети // Всесибирские чтения по математике и механике: Тез. докл. межд. конф., т.1., Математика.-Томск: Изд-во Том. ун-та. 1997.-С. 168-169

49. Евтушенко Н.В., Тренькаев В.Н. Методы синтеза тестов для компоненты автоматной сети // Доклады 2-ой всероссийской конф. "Новые информационные технологии в исследовании дискретных структур". Екатеринбург: УрО РАН, 1998, С. 219-223

50. Декан палиосЬтического Факультета ТГУ1. Малянов А.М.1. Зав. кг 1 "1. УТВЕРЖДАЮ

51. Проектор по научной работе ТГУ1 ^¿Т апреля 20001т апреля 2000 г,•Л- Ъ п1. СПРАВКА

52. Научный руководитель раздела,профессор1. Евтушенко Н.В.1. Заведующий отделом 102профессор1. Семенов В.С.2 II2 99 12:34 ©51064330521. VCB CADGR01P0 Cl

53. UNIVERSITY OF CALIFORNIA, BERKELEYtv op c\ berk elf. v tofes.sor rxmt.n braver. x>m cory i all

54. Programme Director for Priority Area on High Technology NATO

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

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

57. Robert K. Brayton Professor12:33 ©5106435032 ucb cadgrgup ©mi212!2d SEA DIVISION NATO HQ 32 2 7074232 P.01/01

58. North Atlantic treaty Organization ^"titl

59. Organisation du Traite de l' Atlantique nord —o^i.