Применение генетических алгоритмов к генерации тестов для автоматных программ Законов Андрей Юрьевич Научный руководитель: Степанов Олег Георгиевич, к.т.н., ассистент кафедры КТ Санкт-Петербургский государственный университет информационных технологий, механики и оптики Кафедра Компьютерных Технологий

Проблема проверки корректности Необходимо проверять корректность автоматной программы: соответствие реализации программы заданнои ̆ спецификации Важно находить ошибки в любой части системы: –в модели; –в объектах управления; –во взаимодействии объектов управления и модели. Доказательство –трудоемко и требует математической подготовки. Model-checking –не тестирует систему целиком (не затрагивает объекты управления) 2

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

Актуальность проблемы Существующие подходы для автоматных программ не позволяют проверять всю систему вцелом Работы про проверку расширенных конечных автоматов (EFSMs) не учитывают существование объектов управления и взаимодействие модели с ними Подходы к тестированию традиционных программ не могут использовать специфику автоматного подхода: –могут тестировать сгенерированный из автомата код; –теряются все преимущества автоматного подхода. Тестирование трудоемко, поэтому автоматизация принципиальна 4

Задачи для тестирования автоматных программ Проверить соответствие реализации автоматной программы заданнои ̆ спецификации. Задачи: I.Перевести спецификацию из естественного языка в формат, пригодный для автоматической проверки. II.Предложить простой и удобный способ записи тестовых сценариев. III.Автоматически создавать из описания тестового сценария код теста пригодный для запуска. IV.Проверять соблюдение условий спецификации во время выполнения теста. 5

I. Спецификация на естественном языке Обычно спецификация создается на естественном языке Пример словесной спецификации банкомата: –система позволяет снимать деньги с определенного счета; –изначально на счету сумма от 0 до ; –пользователь может снимать деньги произвольное количество раз, пока есть деньги на счету; –Ввод суммы для снятия происходит с клавиатуры, пользователь может ввести число от 1000 до 15000; –В день со счета может быть снято не более Такая спецификация пригодна только для ручного тестирования 6

I. Спецификация на естественном языке Разделение требований на группы Требования к автомату: –система позволяет снимать деньги с определенного счета; –пользователь может снимать деньги произвольное количество раз, пока есть деньги на счету; –В день со счета может быть снято не более Требования к объектам управления: –изначально на счету сумма от 0 до ; –пользователь может ввести на клавиатуре число от 1000 до

I. Построение расширенного конечного автомата. Расширенный конечный автомат учитывает переменные и охранные условия на переходах. 8

I. Спецификация системы: расширенный конечный автомат Требования к автомату: –система позволяет снимать деньги с определенного счета; –пользователь может снимать деньги произвольное количество раз, пока есть деньги на счету; –В день со счета может быть снято не более Требования к объектам управления: –изначально на счету сумма от 0 до ; –пользователь может ввести на клавиатуре число от 1000 до

I. Включение в модель требований к объектам управления и системе в целом Требования спецификации можно добавить в модель несколькими способами: –создать новое состояние (ошибка) и добавить переход с охранным условием. Это приведет к большому количеству состояний; –записать требование при помощи контракта к действию на переходе, на котором выполняется обращение к объекту управления При помощи контрактов будем записывать требования в виде пред- и постусловий к переходам, и инвариантов для состояний 10

I. Требования к объектам управления записанные в модель в виде контрактов Добавляем требования в модель при помощи JML-контрактов. Клавиатура: ext_x >= 1000 && ext_x = 0 && ext_sum

I. Спецификация системы: расширенный конечный автомат и контракты Требования к автомату: –система позволяет снимать деньги с определенного счета; –пользователь может снимать деньги произвольное количество раз, пока есть деньги на счету; –В день со счета может быть снято не более Требования к объектам управления: –изначально на счету сумма от 0 до ; –пользователь может ввести на клавиатуре число от 1000 до Контракты Расш. автомат

II. Разработка тестовых сценариев Тестовые сценарии удобно придумывать исходя из спецификации на естественном языке. Определим тестовый сценарий, как последовательность переходов в автомате: –Словесное описание легко записать в терминах переходов между состояниями; –Имея описание в виде последовательности переходов легко соотнести со словесной спецификацией и понять смысл теста. Все переходы в модели нумеруем, и тогда у каждого перехода есть уникальный идентификатор вида tn Тестовый сценарий записываем как список идентификаторов переходов, например: –t1, t2, t4, t5, t2, t4, t5, t2, t4, t5, t2, t4 13

III. Выполнение тестового сценария Для того, чтобы автомат выполнил заданную последовательность переходов (тестовый сценарий): –необходимо подобрать последовательность событий; –выполнить все охранные условия и контракты ОУ. В условиях задействованы переменные, которые автомат получает из среды при помощи объектов управления –сумма введенная с клавиатуры; –количество денег на счету. Для создания кода теста нужны значения этих переменных: –подобрать вручную; –найти автоматически. В данной работе предложен способ автоматизации поиска значений внешних переменных, при которых выполняются охранные условия и контракты объектов управления. 14

III. Поиск значений переменных Для поиска значений используется генетический алгоритм. Фитнес-функция берет на вход набор значений для внешних переменных и оценивает приспособленность для заданной последовательности переходов: –сколько переходов выполненно успешно (выполнены все условия); –для всех невыполненных условий учитывается насколько сильно нарушено это условие (branch distance); –положение нарушенного условия в заданном пути; Генетический алгоритм используется для поиска набора значений с минимальным результатом фитнес-функции. 15

III. Генетический алгоритм Набор внешних переменных (вектор значений) – хромосома: – Одноточечное скрещивание: Мутация – замена произвольного элемента вектора на случайное число. Фитнес-функция: –учитывает охранные условия и контракты объектов управления –расстояние до условия –учитывает положение в пути. Значение для пути m – число шагов в пути f i – расстояние до условия для i-го шага. d i – вес i-го с шага, 16

III. Пример поиска значений переменных (1) Примеры сценариев для тестирования: –три раза снимаются деньги со счета и на счету заканчиваются средства на четвертой попытке; –двадцать раз снимаются деньги со счета и на счету не заканчиваются средства. Необходимо подобрать значения переменных для создания теста, выполняющего выбранный сценарий 17

III. Пример поиска значений переменных (2) Запишем сценарий как последовательность переходов: –t1, t2, t3, t2, t3, t2, t3, t2, t4 На этом пути задействовано пять переменных: –ext_sum - изначальная сумма на счету; –ext_x1 – сняли первый раз; –ext_x2 – сняли второй раз; –ext_x3 – сняли третий раз; –ext_x4 – попробовали снять четвертый раз. Разработан инструмент, реализующий описанный ГА: –на вход получает модель и заданную последовательность переходов –выдает значения переменных для прохождения этого пути 18

III. Автоматическая генерация кода теста для запуска Автоматически найденные значения: –ext_sum = 15673; –ext_x1 = 4357; ext_x2 = 8023; –ext_x3 = 2162; ext_x4 = Найденные значения позволяют сгенерировать автоматически код теста, пригодный для запуска. Наборы тестов удобно применять для регрессионного и стресс-тестирования. 19

IV. Оценка корректности поведения системы во время запуска тестов (1) Необходимо оценить корректность поведения автоматной программы во время выполнения этого теста. Это выполняется автоматически для тех путей, которые содержат контракты. Во время выполнения программой сгенерированных тестов используется инструмент JML Runtime Assertion Checker для динамической проверки JML- контрактов, интегрированных в Java-код. 20

IV. Оценка корректности поведения системы во время запуска тестов (2) Для рассмотренного пути и найденных значений при запуске теста будет проверяться условие: –В день со счета может быть снято не более 50000; today

Поиск значений, нарушающих требования Требования спецификации автомата также можно включить в вычисление функции приспособленности Это позволит искать значения, которые нарушают эти требования Необходимо рассматривать состояния последовательно –нарушить требования для первого состояния –выполнить для первого, нарушить для второго –… –выполнить для первых n-1, нарушить для n-го 22

Конференции Всероссийская межвузовская конференция молодых ученых 2010 Spring/Summer Young Researchers' Colloquium on Software Engineering

Подход к тестированию автоматных программ 1.Максимально возможная часть спецификации вносится в автоматную модель, используя расширенный конечный автомат и JML-контракты. 2.Тестовые сценарии записываются в виде последовательности переходов автомата. 3.Используя разработанный инструмент, определяются соответствующие значения переменных для выполнения заданного сценария и генерируется код для запуска теста. 4.Тесты запускаются автоматически, во время их исполнения при помощи существующего инструмента проверяется выполненность требований спецификации, записанной в виде контрактов. 24

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