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

Коломеец Антон Владимирович

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

УПРАВЛЯЮ ЩИХ СИСТЕМ НА ОСНОВ Е РАСШИРЕННЫХ

АВТОМАТОВ

05.13.01 Системный анализ, управление и

обработка информации (в отраслях информатики,

вычислительной техники и автоматизации)

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

Томск – 2010

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

Научный руководитель: доктор технических нау к, профессор Евтушенко Нина Владимировна

Официальные оппоненты: доктор технических нау к, профессор Матросова Анжела Юрьевна кандидат технических наук, доцент Громаков Евгений Иванович

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

Защита состоится 14 октября 2010 года в 10.30 на заседании диссертационного совета Д 212.267.12 при ГОУ ВПО «Томский государственный университет» по адресу: 634050, г. Томск, пр.

Ленина, 36, II уч. корпус, ауд. 212 б.

С диссертацией можно ознакомиться в Научной библиотеке ГОУ ВПО «Томский государственный университет» по адресу: 634050, г. Томск, пр. Ленина, 34а.

Автореферат разослан 10 сентября 2010 г.

Ученый секретарь диссертационного совета П.Ф. Тарасенко к. ф.-м. н., доцент

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

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

Поэтому в настоящее время активно исследуется вопрос о построении тестов с гарантированной полнотой на основе б олее компактных моделей, одной из ко торых является расширенный автомат. Мо дель расширенного автомата достаточно часто используется при описании телекоммуникационных протоколов, в частности, расширенный автомат достаточно просто построить по описанию поведения в языке SDL или If или UM L. Однако практически все методы синтеза тестов для расширенных автоматов доставляю т проверяющие тесты, полно та которых остается неизвестной, и соответственно разработка м етодов синтеза проверяющих тестов с гарантированной полнотой для расширенных автоматов является актуальной задачей.

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

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

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

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

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

3. Исследованы ошибки в программных реализациях и установлено соответствие между программными ошибками некоторых классов и ошибками в соответствующем расширенном автомате.

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

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

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

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

1. Проект TA ROT в рамках 6й рамочной программы ЕС «Мобильность молодых ученых», 2003 - 2007 гг.

НИР «Разработка математических и программных средств обеспечения надежного и безопасного доступа к электронным ресурсам коллективного по льзования» (в рамках инновационного проекта ТГУ), 2006 - 2007 гг.

3. НИР «Проведение прикладных и проблемноориентированных поисковых исследований в области участием научных организаций Франции (шифр заявки «2009-04-1.4-00-02-003»)», госконтракт №02.514.12.4002 от Основные положения, выносимые на защиту.

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

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

3. Установленное соответствие между программными ошибками некоторых классов и ошибками в расширенном автомате.

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

Апробация работы. Все теоретические и практические результаты, составившие основу диссертационной работы, по мере их получения обсуждались на семинаре кафедры информационных технологий в исследовании дискретных структур радиофизического факультета ТГУ. Кроме того, результаты работы докладывались на следующих научных конференциях: Российской конференции с международным участием «Новые информационные техно логии в исследовании дискретных структур» (Томск, 2003 и 2008, Ирку тск, 2004, Шу шенское, 2006), международной научной сту денческой конференции «Сту дент и научно – технический прогресс»

(Новосибирск, 2004 и 2006), на международной конференции по тестированию программного обеспечения, ICST’2008, (Лиллехаммер, Норвегия, 2008) Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Диссертация содержит 11 рисунков и 3 таблицы. Объем диссертации составляет страницы, в том числе: титульный лист - о дна страница, оглавление – две страницы, основной текст – 96 страницы, библиография из наименований – 11 страницы, приложение – 21 страниц.

Публикации. По результатам проведенных исследований опубликовано 12 статей в научных журналах, докладах и тезисах докладов на конференциях различного уровня. Работы [1] и [2] опубликованы в изданиях, вхо дящих в список ВА К.

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

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

Первая глава посвящена основным понятиям и обозначениям, относящимся к конечным и расширенным автоматам, и, кроме того, содержит обзор известных методов по синтезу проверяющих тестов для расширенных автоматов. Под ко нечным автоматом (или просто) автоматом понимается пятрка S = (S, I, O, TS, s0 ), где S - непустое конечное множество состояний с выделенным начальным состоянием s0, I - непустое конечное множество вхо дных символов, называемое входным алфавитом, O - непустое конечное множество выхо дных символов, называемое выхо дным алфавитом, TS I S S O отношение поведения. В данной работе мы рассматриваем инициальные автоматы, то есть автоматы с фиксированным начальным состоянием; такие автоматы описываю т поведение систем, обладающих сигналом сброса. Инициальному автомату можно сопоставить специальную словарную функцию, которая описывает отображение входных слов (слов во вхо дном алфавите) в выходные слова. Если каждому вхо дному слову соответствует единственное выходное слово, то автомат называется детерминированным: в противном случае автомат называется недетерми нированным.

Формально под расширенным автоматом M понимается пятерка (S, X, Y, T, V), где S - непустое конечное множество состояний автомата, X - непустое множество вхо дных символов, называемое входным алфавитом, Y - непустое множество выхо дных символов, называемое выходным алфавитом, V - конечное, возможно, пустое множество контекстных переменных, T - множество перехо дов между состояниями из S.

Каждый переход t из множества T есть семрка (s, x, P, op, y, up, s), где s и s принадлежат множеству состояний S и являю тся начальным и конечным состояниями перехода; x X есть входной символ и Dinp x обозначает множество вхо дных векторов, компонентами которых являю тся значения параметров, соответствующих вхо дному символу x (далее входные параметры);

y Y - выхо дной симво л, и Dout y обозначает множество выхо дных векторов, компонентами которых являю тся значения параметров, соответствующих выхо дному символу y (далее выходные параметры);

P, op и up - функции, определенные над вхо дными параметрами и контекстными переменными из V:

- P: Dinp x DV {Истина, Ложь} - предикат, где DV - множество контекстных векторов, то есть векторов, компонентами которых являю тся значения контекстных переменных;

- op : Dinp x DV Dout y - функция вычисления выхо дного параметра;

- up : Dinp x DV DV - функция вычисления значения контекстной переменной.

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

Раздел 1.5 первой главы со держит краткий обзор известных результатов по синтезу тестов для расширенных автоматов. В приведенном обзоре отмечается, что в основном при синтезе тестов по расширенному автомату используются те же критерии, что и при тестировании программного обеспечения. Как показывают проведенные компьютерные эксперименты, такие тесты не являются достаточно качественными при проверке управляющей части расширенного автомата. Мето ды синтеза тестов, основанные на различимости конфигураций, доставляю т проверяющие тесты, полно та которых, вообще говоря, не известна, так же как и мето ды, основанные на частичном моделировании расширенного автомата. Причиной, в частности, является тот факт, что не известны необ хо димые и достаточные условия эквивалентности (или различимости) дву х расширенных автоматов. Мето ды построения проверяющих тестов по соответс твующему мутационному конечному автомату, имеют два недостатка. Во-первых, для каждого класса ошибок определяется специальный набор правил, по ко торым строится мутационный конечный автомат. Во-вторых, как показываю т компьютерные эксперименты, даже для одиночных ошибок переходов в расширенном автомате сложность тестов, построенных по мутационному конечному автомату, практически не отличается о т сложности тестов, построенных по модели «черного ящика», которые являю тся очень длинными. Абстракции и срезы для расширенных автоматов, активно используемые при верификации и тестировании программ, практически не испо льзую тся при синтезе проверяющих тестов для расширенных автоматов. Не известна взаимосвязь между реальными ошибками (например, в программных реализациях) и ошибками в расширенном автомате. Перечисленные выше задачи частично решаются в настоящей диссертационной работе.

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

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

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

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

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

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

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

Вход: Полностью определенный детерминированный связный конечный автомат M = (M, I, O, T, s0 ), который определяет возможные перехо ды в мутационном автомате; приведенная форма S автомата (M, I, O, T, s0 ).

Выход: Полный проверяющий тест относительно модели неисправности (S,, Sub (MMJ)) Шаг 1. Если множество B не является пустым, то в множество BJ заносим максимальное число пар (m, i) B таких, что частичный подавтомат автомата M после удаления всех переходов, соответствующих э тим парам, остается связным.

Шаг 2. Пусть = {B1, …, BK} есть разбиение множества перехо дов расширенного автомата на классы.

Строим мутационный автомат MMJ: для каждой пары (m, i) BJ добавляем все переходы (m, i, o, m), o O, m m, Cтроим полный проверяющий тест TS J относительно модели S,, Sub (MMJ) ;

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

Теорема 1. Проверяющий тест TS, доставляемый алгоритмом 2.2, является по лным относительно модели неисправности (S,, Sub (MMJ)).

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

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

2. По мутационному расширенному автомату строится эквивалентный конечный автомат.

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

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

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

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

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

Алгоритм 2 построения R-среза расширенного автомата Вход: Расширенный автомат M Выход: Срез SliceR (M) автомата M Шаг 1: Переменная vi удаляется из множества контекстных переменных V, если ни о дна из свободных переменных любого предиката расширенного автомата не зависит о т переменной vi.

Другими словами, удаляю тся все контекстные переменные, не влияющие на выпо лнимость предикатов. Пусть V V есть сокращенное множество контекстных переменных.

Шаг 2: Если на некотором перехо де функция определения значения контекстной переменной зависит от некоторой переменной из множества V\V, то данное соотношение удаляется из расширенного автомата.

Шаг 3: Если существует переход в расширенном автомате M, на котором функция определения выхо дного параметра зависит от контекстной переменной из множества V\V, то данное соотношение удаляется из расширенного автомата. Соо тветствующему выхо дному параметру присваивается любое допустимое значение. Конец.

Удаление контекстных переменных, от которых не зависит ни один из предикатов расширенного автомата, не влияет на достижимость состояний. Поэтому справедливо следующее утверждение. Пусть M - расширенный автомат и его срез SliceR (M) получен по алгоритму 2.

последовательность переводит расширенный автомат SliceR (M) из начального состояния s в состояние s, то последовательность также переводит автомат M из начального состояния s в состояние s. Более того, если под действием параметризированного вхо дного симво ла (x,) в автомате SliceR (M) выполним перехо д t = (s,x,P,op,y,up,s), то под действием параметризированного входного символа (x,) выполним соответствующий переход в автомате M.

Для то го чтобы упростить проблему и достижимости, и различимости состояний в расширенном автомате, мы предлагаем построить специальный срез расширенного автомата c конечно автоматным поведением, то есть срез SliceFSM (M), который не содержит контекстных переменных и выходных параметров.

Идея построения среза состоит в удалении перехо дов, на которых предикат зависит от контекстных переменных, т.е. переходов, выполнение которых зависит от значений контекстных переменных.

Тем не менее, некоторые перехо ды, имеющие предикаты, зависящие от контекстных переменных можно сохранить, воспользовавшись следующим свойством. Пусть, например, P есть дизъюнкция предикатов P1 и P2, и предикат P1 не зависит от контекстных переменных. Тогда перехо д с предикатом P будет возбужденным, если для заданных значений входных параметров предикат P1 принимает значение «ИСТИНА». В общем случае такая замена предиката возможна, если предикат P можно представить в виде суперпозиции предикатов P1 и P2, P = f(P1, P2 ), из которых предикат P1 зависит только от вхо дных параметров, и f(1, 0) = f(1, 1) = 1. В этом случае предикат P можно заменить предикатом P1. При такой замене перехо д, возбужденный при наличии предиката P1, останется возбужденным и для предиката P.

Алгоритм 3 построения FSM -среза расширенного автомата Вход: Расширенный автомат M Выход: Конечно автоматный срез SliceFSM (M) автомата M Шаг 1 : Из расширенного автомата M удаляю тся все переходы, на которых предикат зависит только от контекстных переменных. Если предикат P можно представить в виде композиции предикатов P1 и P2, P = f(P1, P2 ), из которых предикат P1 зависит то лько о т вхо дных параметров и f(1, 0) = f(1, 1) = 1, то предикат P заменяется предикатом Шаг 2 : Из полученного расширенного автомата удаляю тся все контекстные переменные и функции вычисления контекстных переменных (up).

Шаг 3 : Из полученного расширенного автомата удаляю тся все выходные параметры и соответствующие функции вычисления выходных параметров (op). Полученный автомат обозначается SliceFSM (M). Конец.

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

Различающим автоматом (M1 /s M2 /q)/(s,q) контекстносвободных расширенных автоматов M1 /s и M2/q называется наибольший связный по давтомат расширенного автомата, где S – множество состояний автомата M 1, Q – множество состояний автомата M2, fail S Q - специальное состояние и специальный выходной символ, X и Y – вхо дной и выхо дной алфавиты, на которых определены автоматы M1 и M2. Множество переходов различающего автомата определяется следующим образом. Для каждой пары состояний (s, q) S Q и для каждой пары переходов из состояний s и q по вхо дному символу x, который определен в каждом из состояний s и q, с предикатами P и R, проверяем, является предикат (P & R) выполнимым, то есть проверяем, существует ли набор значений входных параметров, на котором предикат (P & R) принимает значение «Истина». Если такой набор существует и выхо дной символ b на этих перехо дах о дин и то т же, то в автомате (M1 /s M2 /q)/(s,q) есть перехо д перехо дах из состояний s и q по вхо дному символу x, с предикатами Р и R, не совпадаю т, то в различающем автомате существует переход (s, q) (x, )/fail fail.

На основе R- и FSM-срезов можно предложить следующий алгоритм построения проверяющего теста для расширенного автомата.

Алгоритм 4 построения проверяющего теста для проверки ошибок перехо дов/выхо дов на выделенном подмножестве переходов расширенного автомата Вход : Расширенный автомат M и по дмножество E перехо дов этого автомата, подлежащих проверке, число k, определяющее длину параметризированной входной последовательности, ко торая будет строиться по R-срезу SliceR (M) Выход: Тест, проверяющий наличие одиночных ошибок перехо дов/выхо дов на по дмножестве E переходов (если такой тест можно построить на основе R-среза и среза SliceFSM (M)) Шаг 1: Строятся FSM-срез SliceFSM (M) и R-срез SliceR (M), TS =.

Шаг 2 : Рассматривается каждый перехо д t = (s, x, P, op, y, up, s) из множества E. Если в FSM-срезе SliceFSM (M) состояние s достижимо из начально го состояния по параметризированной вхо дной последовательности и существует перехо д из состояния s под действием вхо дного символа x, то x заносится в тест TS, и Шаг 3.

Если состояние s недостижимо в FSM-срезе, то посредством последовательность длины k, переводящую R-срез из начального Последовательность x заносится в тест TS, и Шаг 3. Если состояние s недостижимо в R-срезе по последовательности длины k, то перехо дим к проверке следующего перехода.

Шаг 3: На основе алгоритма 3 проверяется, с какими состояниями различимо состояние s в FSM-срезе и строится множество Ws различающих последовательностей. В тест TS заносятся последовательности xWs.

Шаг 4 : Если рассмотрены все перехо ды из множества E, то из множества TS удаляю тся последовательности, которые являются собственными начальными отрезками других тестовых последовательностей. Конец.

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

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

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

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

В заключении формулируются основные результаты работы.

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

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

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

4. Установлено соответствие между программными ошибками некоторых классов и ошибками в расширенном автомате; проведенные компьютерные эксперименты показали, что такие программные ошибки могут быть обнаружены тестами, построенными на основе соответствующего расширенного автомата.

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

Список публикаций по теме д иссертации 1. Громов М.Л., Евтушенко Н.В., Коломеец А.В. К синтезу условных тестов для недетерминированных автоматов // Программирование. – 2008. – № 6. – С. 1–11.

2. Жигулин М.В., Коломеец А.В. Оценка полноты проверки при пассивном тестировании на основе автоматной модели // Известия ТПУ. – 2009. – Т. 314, № 5. – С. 225–228.

3. Коломеец А.В., Прокопенко С.А. Метод синтеза диагностических тестов для расширенных конечных автоматов // Вестник ТГУ. Приложение. – 2003. – № 6. – С. 174–177.

4. Коломеец А.В. Метод синтеза проверяющих тестов для расширенных конечных автоматов // Студент и научно-технический прогресс. Информационные техно логии : материалы XLII международной научной студенческой конференции. – Новосибирск, 2004. – C. 174–176.

5. Громов М.Л., Коломеец А.В., Евтушенко Н.В. Синтез диагностических тестов для автоматных сетей // Вестник ТГУ.

Приложение. – 2004. – № 9 (I). – С. 204–209.

диагностических тестов для ло кализации о диночных выхо дных ошибок и ошибок перехо дов в расширенных автоматах // Наука.

Технологии. Инновации : материалы всероссийской научной конференции молодых ученых : в 7 ч. – Новосибирск : Изд-во НГТУ, 2006. – Ч. 1. – С. 238–240.

Автоматизация тестирования реализаций протоколов прикладного уровня в лабораторном практикуме // Современные средства и системы автоматизации : материалы IV научно-практической конференции. – Томск : Изд-во ТУСУР, 2003. – C. 222–225.

8. Коломеец А.В., Прокопенко С.А. Соответствие между ошибками в программных реализациях протоко лов и расширенн ых автоматах // Вестник ТГ У. Приложение. – 2005. – № 14. – С. 154–157.

проверяющих тестов для расширенных автоматов без построения эквивалентного конечного автомата // Вестник ТГУ. Приложение. – 2006. – № 18. – С. 62– 66.

10. Михайлов Ю.В., Коломеец А.В. Автоматизация внесения ошибок в программные реализации протоколов на основе модели расширенного автомата // Наука. Технологии. Инновация : материалы всероссийской научной конференции молодых ученых : в 7 ч. – Новосибирск : Изд-во НГТУ, 2006. – Ч. 1. – С. 49–51.

11. El-Fakih K., Kolomeez A., Pro kopenko S., Yevtushenko N.

Extended Finite State Machine Based Test Derivation Driving By User Defined Faults // International Conference ICST’2008 / IEEE. – 2008. – P. 308-317.

12. Михайлов Ю.В., Коломеец А.В. Проверка переходов в расширенном автомате на основе срезов // Вестник ТГУ. Управление, вычислительная те хника и информатика. – 2008. – № 3 (4). – С. 110–118.

Отпечатано в ООО «Позитив-НБ»

634050 г. Томск, пр. Ленина 34а