Совместное применение генетического программирования и верификации моделей для построения автоматов управления системами со сложным поведением К. В. Егоров, гр Научный руководитель – докт. техн. наук, проф., зав. каф. ТП СПбГУ ИТМО А. А. Шалыто

2/22 Решаемая проблема Автоматное программирование Часто эвристическое построение автоматов затруднено Построенные вручную автоматы зачастую не оптимальны Автоматизированное построение конечных автоматов с помощью генетического программирования

3/22 Методика построения автоматных программ на основе тестов

4/22 Верификация автоматных программ «Тестирование позволяет показать наличие ошибок, но не их отсутствие» (Э. Дейкстра, 1970 г.) Тесты позволяют описать поведение системы только для конечного числа вариантов входных данных Верификация позволяет проверить соответствие программы спецификации Спецификация задается в виде набора формул на языке темпоральной логики (LTL = Linear-Time Logic)

5/22 Темпоральные операторы языка LTL X (neXt) – «Xp» – в следующий момент выполнено p; F (in the Future) – «Fp» – в некоторый момент в будущем будет выполнено p; G (Globally in the future) – «Gp» – всегда в будущем выполняется p; U (Until) – «pUq» – существует состояние, в котором выполнено q и во всех предыдущих выполняется p; R (Release) – «pRq» – либо во всех состояниях выполняется q, либо существует состояние, в котором выполняется p, а во всех предыдущих выполнено q.

6/22 Схема работы верификатора

7/22 Методика построения автоматных программ на основе тестов и LTL- формул

8/22 Особь алгоритма генетического программирования Списки переходов для каждого состояния + номер начального состояния Для каждого перехода хранится событие, по которому он выполняется, и число выходных воздействий, но не хранятся выходные воздействия

9/22 Алгоритм расстановки пометок

10/22 Функция приспособленности Учет поведения автомата на тестах ED – редакционное расстояние n 1 – число верных формул n 2 – общее число формул M – число, большее максимального числа переходов

11/22 Функция приспособленности Учет поведения автомата на тестах ED – редакционное расстояние n 1 – число верных формул n 2 – общее число формул M – число, большее максимального числа переходов Учет числа переходов

12/22 Функция приспособленности Учет поведения автомата на тестах Учет LTL-формул ED – редакционное расстояние n 1 – число верных формул n 2 – общее число формул M – число, большее максимального числа переходов Учет LTL-формул

13/22 Учет верификации в функции приспособленности n – число LTL формул; T – число достижимых переходов в особи; ti – число верифицируемых переходов.

14/22 Пример учета верификации в функции приспособленности 3 – число верифицируемых переходов из первого подмножества; 7 – число переходов в конечном автомате.

15/22 Учет результата верификации при скрещивании и мутации Верификатор помечает путь в модели, опровергающий формулу. Удалить переход из контрпримера. Изменить входное воздействие, количество выходных или состояние в которое перейдет автомат. Когда верификатор покидает вершину при обходе в глубину, он помечает все исходящие переходы. Такие переходы соответствуют LTL-формуле. Подграф из таких переходом может перейти в новую особь без изменений при кроссовере.

16/22 Пример верификации G(!wasEvent(T)) Автомат Бюхи, построенный по отрицанию формулы

17/22 Пример скрещивания с учетом верификации

18/22 Пример – система управления дверьми лифта Пять событий, три выходных воздействия Девять тестов Одиннадцать LTL-формул: G(wasEvent(e11) => wasAction(z1)) – начать открытие дверей после того, как нажата кнопка «Открыть двери» G(wasEvent(e4) wasAction(z3)) G(wasEvent(e3) => wasAction(z1)) G(wasEvent(e11) => X(wasEvent(e4) or wasEvent(e2))) – если нажали «Кнопку открыть двери», то следующим событием будет либо e2 (открывание дверей успешно завершено) или e4 (двери заклинило) G(wasAction(z1) => X(!wasAction(z1) U(wasAction(z2) or wasEvent(e4))))

19/22 Построенные автоматы Только тесты Тесты + верификация После поломки дверей может быть отдана команда на их закрытие!

20/22 Показатели производительности ЛифтЧасы с будильником Тесты Тесты и формулы Тесты Тесты и формулы Среднее7.479 × × × × 10 6 Среднеквадрати чное отклонение 2.54 × × × × 10 6 Минимальное2.184 × × × × 10 5 Максимальное2.999 × × × × 10 7 Измерялось число вычислений функции приспособленности 1000 экспериментов

21/22 Результаты работы Предложен метод построения конечных автоматов с заранее заданным поведением на основе генетических алгоритмов. На основе тестовых примеров На основе темпоральных свойств Учет верификации на этапах: вычисления функции приспособленности; скрещивания; мутации. Построение автомата управления дверьми лифта. Построение автомата управления часами с будильником.

22/22 Спасибо за внимание!