Алгоритмы синтеза проверяющих тестов для управляющих систем на основе расширенных автоматов

• Автор: Коломеец, Антон Владимирович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Томск
• Количество страниц: 130 с.

Оглавление
Введение

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

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

1.2. Расширенные автоматы

1.3. Построение эквивалентного конечного автомата

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

1.4.1 Модели неисправности и тесты для конечных автоматов

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

1.5. Обзор методов по синтезу тестов для расширенных автоматов.

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

2. Модели неисправности на основе мутационного расширенного автомата
2.1. Модель неисправности на основе мутационного расширенного автомата
2.2. Ошибки в расширенном автомате.
2.2.1 Выходные неисправности.
2.2.2. Ошибки переходов
2.2.3. Предикатные ошибки
2.2.4. Ошибки присвоения.
2.3. Тестирование на основе мутационного автомата
2.4. Основные результата главы 2.
3. Синтез тестов для расширенного автомата на основе срезов
3.1. Построение среза расширенного автомата с сохранением достижимости состояний.
3.2. Построение РБМсреза расширенного автомата
3.3. Построение различающего автомата для двух контекстносвободных расширенных автоматов.
3.4. Алгори тм построения проверяющего теста для проверки ошибок переходоввыходов на выделенных переходах расширенного автомата
3.5. Экспериментальные результаты.
3.6. Построение проверяющего теста на основе эквивалентного конечного автомата с ограничением на число состояний
3.7. Основные результаты главы 3
4. Соответствие между ошибками в программных реализациях и ошибками в расширенных автоматах.
4.1. Соответствие между программными ошибками и ошибками в расширенном автомате
4.1.1. Тесты, построенные по расширенному автома ту для проверки ошибок переходов
4.1.2. Тесты, построенные но расширенному автомагу для проверки ошибок выходов
4.1.3. Тесты, построенные по расширенному автомату для проверки предикатных ошибок
4.1.4. Тесты, построенные по расширенному автомату для проверки ошибок присвоения.
4.1.5. Более сложные ошибки
4.2. Генерация программных реализаций на основе модели расширенного автомата...
4.3. Экспериментальные результаты.
4.4. Основные результаты главы 4
Заключение
Литература


B., Спицына Н. Современные средства и системы автоматизации : материалы IV научно-практической конференции. Томск : Изд-во. ГУСУР, . С. 2-5. Коломеец А. В.у Прокопенко С. А. Соответствие между ошибками в программных реализациях протоколов и расширенных автоматах // Вестник ТГУ. Приложение. С.4-7. Коломеец A. B., Прокопенко С. А. Метод синтеза проверяющих тестов для расширенных автоматов без построения эквивалентного конечного автомата // Вестник ТГУ. Приложение. С.-. Михайлов Ю. В., Коломеец A. B. Автоматизация внесения ошибок в программные реализации протоколов на основе модели расширенного автомата // Наука. Технологии. Инновация : материалы всероссийской научной конференции молодых ученых в 7 ч. Новосибирск : Изд-во НГТУ, . Ч. 1. С. -. El-Fakih K. Kolomeez A. Prokopenko S. Finite State Machine Based Test Derivation Driving By User Defined Faults // International Conference ICST’ / IEEE. P. 8-7. Михайлов Ю. В., Коломеец A. B. Проверка переходов- в расширенном автомате на основе срезов // Вестник ТГУ. Управление, вычислительная техника и информатика. С. 0—8. Громов^ МЛ. Евтушенко Н. В., Коломеец. A.B. К синтезу условных тестов для недетерминированных автоматов; Программирование. Жигулин М. В., Коломеец A. B. Оценка полноты проверки, при пассивном тестировании на основе автоматной модели // Известия ТПУ. Т. 4, №5. С. 5-8. Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка используемой литературы. Диссертация содержит рисунков и 3 таблицы. Объем диссертации составляет 8 страницы, в том числе: титульный лист - одна страница, оглавление - две страницы, основной текст - страниц, библиография из наименований - страниц, приложение - страница. Краткое содержание работы. Первая глава посвящена основным понятиям и обозначениям, относящимся к конечным и расширенным автоматам. Под конечным автоматом (или просто) автоматом понимается система с конечным множеством состояний, входных и выходных символов, которая переходит из состояния в состояние при подаче входных воздействий, и производит при этом выходные реакции. В данной работе мы рассматриваем инициальные автоматы, то есть автоматы с фиксированным начальным состоянием. Инициальному автомату можно сопоставить специальную словарную функцию, которая описывает отображение входных слов (слов во входном алфавите) в выходные слова. Расширенный автомат получается из конечного, автомата добавлением так называемых контекстных переменных и входных и выходных параметров. Кроме того, выполнение перехода из заданного состояния может зависеть от значений контекстных переменных и входных параметров в текущий, момент времени. Поэтому каждый переход содержит предикат, описывающий соответствующие условия срабатывания перехода. После выполнения перехода контекстным переменным и выходным параметрам присваиваются новые значения, которые вычисляются но функциям присвоения данного перехода. Известно, что если область определения контекстных переменных и входных параметров конечна, то по расширенному автомату можно построить эквивалентный конечный автомат, который реализует ту же словарную функцию. В общем случае эквивалентный конечный автомат строится путем моделирования поведения расширенного автомата на входных последовательностях. Состояниями конечного автоматаявляются пары «состояние, вектор значений контекстных переменных», которые называются конфигурациями, а входами - нары «входной символ, вектор значений входных параметров». В главе 1 также приводится краткий обзор известных результатов по синтезу тестов для расширенных автоматов: Следует отмстить, что первые тесты по модели расширенного автомата строились для проверки передачи данных, и такие теста должны были удовлетворять так называемым критериям all-use (IO-df-chain) [6, 7], то есть в тесте обычно прослеживались все пути, где используется некоторая переменная. Основной проблемой при синтезе таких тестовых последовательностей было требование использования только выполнимых (executable) входных последовательное гей.