Математические методы верификации схем и программ

Общая информация

Обязательный курс для магистров 618/2 и 621 групп 3 семестра магистратуры.

Курс читают

• профессор В. А. Захаров
• младший научный сотрудник В. В. Подымов.

Лекционная нагрузка — 32 ч., семинары и практические занятия— 16 ч.

Программа

Программа будет обновляться по мере проведения занятий.

1. Задача верификации аппаратуры и программного обеспечения. Зачем нужна формальная верификация программ? Основные подходы к задаче формальной верификации. Принципы верификации моделей программ. Исторические сведения. Достижения методов формальной верификации программ. Алгоритмические и комбинаторные трудности применения метода верификации моделей программ. Лекция 1.
2. Общие принципы дедуктивной верификации программ. Операционная семантика императивных программ. Формальная постановка задачи верификации программ. Логика Хоара: правила вывода и свойства. Аннотированные программы. Автоматизация проверки правильности программ. Лекция 2.
3. Моделирование схем. Системы переходов - модели Крипке. Представление систем переходов формулами логики предикатов первого порядка. Синхронные и асинхронные схемы. Степень детализации представления. Трансляция описаний программ и схем в модели Крипке. Лекция 3.
4. Темпоральная логика деревьев вычислений CTL. Синтаксис и семантика CTL. Примеры спецификаций моделей в терминах формул CTL. Темпоральная логика линейного времени LTL. Синтаксис и семантика LTL. Свойства живости и безопасности. Ограничения справедливости. Задача верификации моделей (model-checking). Лекция 4.
5. Табличный алгоритм верификации моделей для CTL. Обоснование корректности и сложности табличного алгоритма верификации моделей. Проблема “комбинаторного взрыва”. Символьные средства описания моделей. Двоичные разрешающие диаграммы (BDD). Алгоритм редукции BDD к каноническому виду (OBDD). Выполнение операций над OBDD: унарные и бинарные булевы операции, квантификация, проверка выполнимости, подсчет числа единиц. Общие представления о сложности в классе OBDD. Лекция 5.
6. Представления неподвижной точки в CTL. Алгоритм символьной верификации моделей в CTL. Лекция 6.
7. Табличная верификация моделей для PLTL. Автоматы Бюхи: их свойства и обобщения. Трансляция формул PLTL в автоматы Бюхи. Сведение задачи проверки выполнимости формул PLTL к проблеме пустоты для автоматов Бюхи. Лекция 7.
8. Отношения бисимуляционной эквивалентности (бисимуляции) и симуляционного квазипорядка (симуляции) на моделях Крипке. Равновыполнимость темпоральных формул на бисимуляционно эквивалентных моделях Крипке. Вычисление классов бисимуляционной эквивалентности на конечных моделях Крипке. Упрощение моделей Крипке при помощи отношений симуляции и и бисимуляции. Редукция моделей Крипке по конусу влияния. Абстракции данных при построении моделей Крипке. Лекция 8.
9. Временные автоматы как формальные модели распределенных систем реального времени. Вычисления временных автоматов. Примеры использования временных автоматов для моделирования встроенных систем. Зеноновские вычисления. Синтаксис и семантика Timed CTL. Примеры формальных спецификаций поведения встроенных систем при помощи TCTL. Лекция 9.
10. Задача верификации моделей программ реального времени. Отношение эквивалентности часов и регионы. Регионные системы переходов. Оценка числа регионов. Сведение задачи верификации временных автоматов относительно TCTL к задаче верификации моделей Крипке относительно CTL. Лекция 10.
11. Верификация моделей программ для вычислений ограниченной длины (bounded model checking, BMC). Сведение задачи BMC к задаче проверки выполнимости булевых формул (SAT). Применение автоматических средств решения задачи SAT для решения задачи BMC. Лекция 11.

Материалы семинаров

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

Любые вопросы по темам семинарских занятий можно высылать на почту valdus@yandex.ru.

Семинар 1. Доказательство корректности императивных программ с помощью логики Хоара.

Семинар 2. Модели Крипке. LTL, CTL. Безопасность, живость, справедливость.

Семинар 3. Табличный и символьный алгоритмы проверки CTL-формул на моделях Крипке. ROBDD.

Семинар 4. Обзор средства NuSMV: описание параллельной композиции автоматов, проверка CTL-формул.

Семинар 5-6. NuSMV: практические задания по проверке CTL-спецификаций.

Семинар 7. Обзор средства SPIN: синтаксис, трансляция базовых конструкций в модели Крипке.

Инструкция по работе со средством SPIN.

Семинар 8-9. SPIN: практические задания по проверке LTL-спецификаций.

Семинар 10. UPPAAL: практические задания по проверке временных спецификаций.

Архив, прилагающийся к семинару 10.

Правила проведения экзамена

1. Экзамен по курсу "Математические методы верификации схем и программ " состоится 14 января в ауд. П-14; начало экзамена - 10.00; окончание экзамена - 12.00.
2. Итоговая экзаменационная оценка складывается из оценки за экзаменационную контрольную работу, зачетных оценок за выполнение домашних заданий и премиальных оценок за решение особо сложных задач, объявленных в курсе лекций.
3. Экзаменационная контрольная работа состоит из 5 задач и 5 вопросов. Каждая из задач контрольной относится к одному из типов задач, которые разбирались на семинарских занятиях или на лекциях. Каждый из вопросов касается формулировок определений или ключевых результатов, рассмотренных на лекциях.
4. Выставление экзаменационных оценок и ознакомление с работами будет проводиться 14 января в ауд. 506 в 17.00.
5. Консультация к экзамену состоится 12 января в ауд. 506 в 16.30.

Учет домашних заданий

Домашнее задание 1: предоставившие решение этого задания освобождаются от решения задачи на тему логики Хоара.

Домашние задания 3, 4: предоставившие решения этих заданий будут освобождены от задач, покрываемых темами заданий, а также (задание 4) поощрены дополнительными баллами на экзамене.

Домашние задания 5, 6, 7 (NuSMV, Spin, Uppaal):

• если решены ровно два из трёх заданий, то из итоговой оценки (2, 3, 4, 5) вычитается один балл;
• если решено менее двух заданий, то из итоговой оценки вычитается два балла.

По окончании семестра снова открывается прием заявок на получение домашних заданий 5, 6, 7. Правила получения домашних заданий - в разделе домашних заданий. Крайний срок сдачи: сутки до экзамена. Решения, сданные позднее крайнего срока, могут быть не учтены на экзамене. Внимание: неправильно работающие решения, сданные вблизи крайнего срока, могут быть не приняты ввиду задержек, требуемых для их проверки, отправки на доработку, доработки и повторной проверки.

Домашние задания

Решение домашних заданий, а также любые вопросы по домашним заданиям можно высылать на почту valdus@yandex.ru.

Домашнее задание 1: логика Хоара

Домашнее задание сформулировано в слайдах семинара 1.

Решение должно быть нерукописным (.txt, .doc, TeX-pdf, ...).

Крайний срок сдачи: 27 сентября, 23:59.

Поощрение за сделанное домашнее задание: освобождение от задачи на тему логики Хоара.

Домашнее задание 2, обязательное: установка средств верификации

• (прежде всего) поставить NuSMV
• (чуть позже, но тоже надо) поставить Spin
• (ещё позже, но тоже надо) поставить UPPAAL (лучше версию 4.0, но можно и последнюю)
• настоятельно рекомендуется всё это поставить в Linux (с Windows у студентов постоянно возникают странные проблемы, а в Linux всё работает - проверено)
• проверить, что всё это работает:
  • в выводе "./NuSMV" есть строки, утверждающие, что
    • подключены CUDD и MiniSat, либо нет строк о том, что что-то надо подключить
    • входной файл не подан и работа завершена
  • "./spin -a <папка с примерами spin>/LTL/bakery.pml" успешно завершает работу без вывода
  • "./uppaal" загружает графический интерфейс и для какого-нибудь примера при нажатии на кнопку Check вкладки Verifier при каком-нибудь выделенном свойстве завершает вывод словами Property is satisfied или Property is not satisfied
• Организовать хотя бы один ноутбук на двоих (если совсем не выходит, то на троих) с поставленным NuSMV на занятии 21.10.2016

Домашнее задание 3: формализация систем и свойств, алгоритмы проверки CTL-формул

• написать письмо с любым содержанием и заголовком "[Ver 2016 hw2] Фамилия И.О."
• в ответ будут присланы описание системы и требований к этой системе
• задача: поработать в качестве табличного или символьного алгоритма верификации CTL-формул и донести результат в любом виде
  • табличный алгоритм:
    • нарисовать модель Крипке
    • записать требования в виде CTL-формул
    • описать шаги работы алгоритма настолько (не)строго, чтобы можно было без чрезмерных усилий строго восстановить каждый шаг работы
  • символьный алгоритм:
    • записать набор формул для модели Крипке
    • записать требования в виде CTL-формул
    • описать шаги работы алгоритма (включающие BDD, QBF или аналогичную формальную запись) настолько (не)строго, чтобы можно было без чрезмерных усилий строго восстановить каждый шаг работы

Домашнее задание 4, сложное: символьный алгоритм проверки CTL-формул

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

Домашнее задание 5, обязательное: NuSMV

Внимание, в связи с неоднократными просьбами и неожиданным осознанием сдающих, что в NuSMV всё не так просто, крайний срок домашнего задания сдвинут на несколько дней: 20.11.2016, 23:59.

• задание можно выполнять как в одиночку, так и в паре
• написать письмо с любым содержанием и заголовком
  • "[Ver 2016 nusmv] Фамилия И.О.", если задание выполняется в одиночку
  • "[Ver 2016 nusmv] Фамилия И.О. Фамилия И.О.", если задание выполняется в паре
• в ответ будут присланы описание системы и требований к ней
• задача: описать систему и требования в формате NuSMV так, чтобы можно было проверить требования обычным для NuSMV образом
• необходимо выслать ответом на присланное письмо файл с расширением .smv, содержащий описание системы и требований в формате NuSMV
• если есть предпочтения: из какой области хотелось бы видеть описание системы - то эти предпочтения можно выразить в тексте первого письма
  • если предпочтения разумны, то они могут быть учтены
  • например, на семинаре 5 было озвучено несколько таких областей: параллельно работающие программы, схемы, игры/головоломки, системы общего вида
• крайний срок сдачи: 20.11.2016, 23:59
• поощрение за выполненное домашнее задание: необходимо для допуска к экзамену
• наказание за невыполненное домашнее задание: сдача этого задания перед экзаменом в более сжатые сроки
• в зависимости от степени ошибочности решение может быть принято, не принято или отправлено на доработку; последнее - в том случае, если в системе есть существенные недостатки, но в достаточном количестве присутствуют правильно реализованные разумные идеи
  • рекомендуется задействовать все средства, позволяющие убедиться, что система и требования описаны правильно
  • если задание выполняется в паре, рекомендуется каждому участнику проверить правильность итогового .smv-файла

Домашнее задание 6, обязательное: Spin

• задание можно выполнять как в одиночку, так и в паре
• написать письмо с любым содержанием и заголовком
  • "[Ver 2016 spin] Фамилия И.О.", если задание выполняется в одиночку
  • "[Ver 2016 spin] Фамилия И.О. Фамилия И.О.", если задание выполняется в паре
• в ответ будут присланы описание системы и требований к ней
• задача: описать систему и требования на языке PROMELA так, чтобы можно было проверить требования обычным для средства SPIN образом
• необходимо выслать ответом на присланное письмо файл с расширением .pml, содержащий описание системы и требований на языке PROMELA
• если есть предпочтения: из какой области хотелось бы видеть описание системы - то эти предпочтения можно выразить в тексте первого письма
• крайний срок сдачи: 06.12.2016, 23:59
• поощрение за выполненное домашнее задание: необходимо для допуска к экзамену
• наказание за невыполненное домашнее задание: сдача этого задания перед экзаменом в более сжатые сроки
• в зависимости от степени ошибочности решение может быть принято, не принято или отправлено на доработку; последнее - в том случае, если в системе есть существенные недостатки, но в достаточном количестве присутствуют правильно реализованные разумные идеи
  • рекомендуется задействовать все средства, позволяющие убедиться, что система и требования описаны правильно
  • если задание выполняется в паре, рекомендуется каждому участнику проверить правильность итогового .pml-файла

Домашнее задание 7, обязательное: Uppaal

• задание можно выполнять как в одиночку, так и в паре
• написать письмо с любым содержанием и заголовком
  • "[Ver 2016 uppaal] Фамилия И.О.", если задание выполняется в одиночку
  • "[Ver 2016 uppaal] Фамилия И.О. Фамилия И.О.", если задание выполняется в паре
• в ответ будут присланы описание системы и задачу, которую требуется решить для этой системы
• задача: описать систему в GUI Uppaal, а также составить в этом же GUI набор формул, по результатам проверки которых можно легко выяснить ответ к задаче
• необходимо выслать ответом на присланное письмо два файла, генерируемые GUI Uppaal: с расширением .xml (описание системы) и с расширением .q (описание требований)
• если есть предпочтения, относящиеся к виду анализируемой системы, можно их выражать в тексте первого письма
• крайний срок сдачи: 20.12.2016, 23:59
• поощрение за выполненное домашнее задание: необходимо для допуска к экзамену
• наказание за невыполненное домашнее задание: сдача этого задания перед экзаменом в более сжатые сроки
• в зависимости от степени ошибочности решение может быть принято, не принято или отправлено на доработку; последнее - в том случае, если в системе есть существенные недостатки, но в достаточном количестве присутствуют правильно реализованные разумные идеи

Литература

1. Э.М. Кларк, О. Грамберг, Д. Пелед. Верификация моделей программ: Model Checking. Изд-во МЦНМО, 2002.
2. Ю.Г. Карпов. Model Checking: верификация параллельных и распределенных программных систем. Изд-во БХВ-Петербург, 2010.
3. K. R. Apt, E.-R. Olderog. Verification of sequential and concurrent programs, Springer, 1997.
4. B. Berard, M. Bidoit, A. Finkel, F. Laroussinie, A. Petit, L. Petrucci, P. Schnoebelen. Systems and Software Verification: Model-Checking Techniques and Tools. Springer, 2001.
5. Baier C., Katoen J.-P. Principles of model checking, MIT Press, 2008.