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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск

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

Обязательный курс для магистров групп 618мк_дс, 618мк_дус и 621асвк 3 семестра магистратуры (группа 621асвк - "Методы верификации программ").

В 2020/2021 учебном году курс читают


Программа

Видеозаписи лекций размещены по адресу [1] в разделе ЗахаровВА

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

  1. Verification problem for hardware and software systems. Why do we need formal verification of information processing systems? Basic approaches to formal verification of hardware and software systems. Principles of model checking. Historical overview. Achievements of formal verification techniques. Лекция 1.
  2. General principles of deductive program verification. Operational semantics of imperative programs. Problem statement for deductive verification of imperative programs. Hoare logic: theory and practice. Automation of program correctness checking. Лекция 2.
  3. General principles of model checking. Kripke structures as formal models of information processing systems. First-order representation of Kripke structures. Synchronous and asynchronous models. Granularity of models. Translation of programs into Kripke structure. Лекция 3.
  4. Properties of program computations. Classification of computational properties. Fairness constraints. Generalized Computational Tree Logic CTL*: syntax and semantics. Temporal Logics CTL and LTL. Formal setting of model checking problem. Лекция 4.
  5. Табличный алгоритм верификации моделей для CTL. Обоснование корректности и сложности табличного алгоритма верификации моделей. Проблема “комбинаторного взрыва”. Символьные средства описания моделей. Двоичные разрешающие диаграммы (BDD). Алгоритм редукции BDD к каноническому виду (OBDD). Выполнение операций над OBDD: унарные и бинарные булевы операции, квантификация, проверка выполнимости, подсчет числа единиц. Общие представления о сложности в классе OBDD. Лекция 5.
  6. Представления неподвижной точки в CTL. Алгоритм символьной верификации моделей в CTL. Лекция 6.
  7. Табличный алгоритм верификации моделей для LTL. Автоматы Бюхи, их свойства и обобщения. Трансляция моделей Крипке и формул LTL в автоматы Бюхи. Автоматный алгоритм верификации моделей для LTL. Лекция 7.
  8. Отношения бисимуляционной эквивалентности (бисимуляции) и симуляционного квазипорядка (симуляции) на моделях Крипке. Равновыполнимость темпоральных формул на бисимуляционно эквивалентных моделях Крипке. Вычисление классов бисимуляционной эквивалентности на конечных моделях Крипке. Упрощение моделей Крипке при помощи отношений симуляции и и бисимуляции. Редукция моделей Крипке по конусу влияния. Абстракции данных при построении моделей Крипке. Лекция 8.
  9. Системы реального времени. Временные автоматы. Неправдоподобные вычисления временных автоматов. Вычисления Зенона. Timed CTL. Задача model checking для Timed CTL. Лекция 9.
  10. Алгоритм верификации временных автоматов относительно Timed CTL. Временные регионы. Оценка числа регионов. Системы регионов. Сети временных автоматов. Лекция 10.
  11. Верификация моделей программ для вычислений ограниченной длины (bounded model checking, BMC). Сведение задачи BMC к задаче проверки выполнимости булевых формул (SAT). Применение автоматических средств решения задачи SAT для решения задачи BMC. Лекция 11.

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

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

Любые вопросы по темам семинарских занятий можно задавать ему.

Семинар 1. Deductive verification of imperative programs based on Hoare logic.

Семинар 2. Kripke structures. LTL. Safety and liveness. Fairness.

Семинар 3. Справедливость. CTL: формализация, табличный и символьный алгоритмы. ROBDD.

Семинар 4. NuSMV: обзор средства.

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

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

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

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

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

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

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

  1. Итоговая экзаменационная оценка складывается из оценки за экзаменационную контрольную работу, зачетных оценок за выполнение домашних заданий и премиальных оценок за решение особо сложных задач, объявленных в курсе лекций.
  2. Экзаменационная контрольная работа состоит из 5 задач и 5 вопросов. Каждая из задач контрольной относится к одному из типов задач, которые разбирались на семинарских занятиях или на лекциях. Каждый из вопросов касается формулировок определений или ключевых результатов, рассмотренных на лекциях.

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

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

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

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

NuSMV, Spin, Uppaal:

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

Обязательные домашние задания "NuSMV", "Spin", "Uppaal"

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

Установка средств верификации

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

Общие правила выполнения заданий "NuSMV", "Spin" и "Uppaal"

  • Каждое из заданий можно выполнять как в одиночку, так и в паре.
  • Срок выполнения задания (кроме индивидуально согласованных случаев) - от начала проведения соответствующих семинаров и до начала проведения следующего тематического блока семинаров (для последнего блока семинаров - до окончания семестра).
  • Первый шаг выполнения - выслать ему на почту письмо с любым текстом и специальным заголовком:
    • для выполнения задания "NuSMV" в одиночку: [ver-nusmv] группа Фамилия И.О.
    • для выполнения задания "NuSMV" в паре: [ver-nusmv] группа Фамилия И.О., Фамилия И.О.
    • для выполнения задания "Spin" в одиночку: [ver-spin] группа Фамилия И.О.
    • для выполнения задания "Spin" в паре: [ver-spin] группа Фамилия И.О., Фамилия И.О.
    • для выполнения задания "Uppaal" в одиночку: [ver-uppaal] группа Фамилия И.О.
    • для выполнения задания "Uppaal" в паре: [ver-uppaal] группа Фамилия И.О., Фамилия И.О.
  • В ответ будет выслано письмо, содержащее описание системы и цели исследования этой системы при помощи проверки требований.
  • В тексте первого письма можно сформулировать пожелания по виду системы и целей исследования, вплоть до полной формулировки:
    • если пожелания разумны, они с немалой вероятностью будут учтены в задании;
    • типовые примеры пожеланий: "хочу исследовать параллельно работающие программы", "... схему", "... игру/головоломку", "... систему общего вида, без программистско-математической специализации".
  • Решение задания должно быть выслано в ответ на письмо с формулировкой задания в установленный срок.
  • Присланное решение
    • принимается, если оно полностью или с незначительными недочётами верно;
    • не принимается, если оно демонстрирует, что выполнявшие его не пытались вдумчиво разобраться в принципах работы со средством верификации;
    • отправляется на доработку, если оно содержит существенные ошибки, но демонстрирует осознанную и правильную работу со средством верификации.

NuSMV

Решение этого задания - это

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

Spin

Решение этого задания - это

  • файл с расширением ".pml", содержащий формализацию системы и требований на языке PROMELA, и
  • пояснение того, как результаты проверки требований, выдаваемые средством Spin, соотносятся с поставленными целями, в свободной форме.

Uppaal

Решение этого задания - это

  • файл или файлы, сгенерированные средством Uppaal и содержащие формализацию системы и требований (Uppaal 4.1: файл ".xml"; Uppaal 4.0: файлы ".xml" и ".q"), и
  • пояснение того, как результаты проверки требований, выдаваемые средством Uppaal, соотносятся с поставленными целями, в свободной форме.

Поощряемые домашние задания

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

Логика Хоара

Крайний срок выполнения задания: начало семинара 3 (по CTL).

Задание сформулировано на последнем слайде материалов семинара 1.

CTL: формализация требований и алгоритмы проверки формул

Крайний срок выполнения задания: конец семестра.

Как выполнить это задание:

  • написать письмо с любым содержанием и заголовком [ver-ctl] группа Фамилия И.О.;
  • в ответ будут присланы описание системы и требований к этой системе;
  • требуется адекватно формализовать требования в логике ветвящегося времени, изобразить шаги работы табличного или символьного алгоритма и донести результат до него в любом виде.

Если сомневаетесь, что означает "изобразить шаги работы алгоритма", то по умолчанию поступайте так:

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

CTL и справедливость

Это трудное домашнее задание.

Крайний срок выполнения задания: конец семестра.

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

Как выполнить это задание:

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

Литература

  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.
  6. Clarke E., Henzinger T.A., Veith H., Bloem R. Handbook of model checking, Springer, 2018.
Источник — «https://mk.cs.msu.ru/index.php?title=Математические_методы_верификации_схем_и_программ&oldid=7593»