Введение в формальные методы верификации программ
Покупка
Новинка
Тематика:
Программирование и алгоритмизация
Издательство:
ДМК Пресс
Автор:
Камкин Александр Сергеевич
Год издания: 2024
Кол-во страниц: 306
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-93700-340-9
Артикул: 890554.01.99
Книга основана на курсах лекций по формальным методам верификации программ, читаемых автором на кафедрах системного программирования МГУ, МФТИ и ВШЭ. Список тем включает: методы формализации семантики языков программирования (операционная и аксиоматическая семантика), методы формальной спецификации требований (программные контракты и темпоральная логика линейного времени), методы доказательства корректности программ (метод индуктивных утверждений и метод фундированных множеств) и методы проверки моделей (теоретико-автоматный подход в явной и символической формах); затрагиваются вопросы абстрактной интерпретации, разрешения ограничений, применения формальных методов в тестировании; даются сведения об инструментах Frama-C/AstraVer, Spin и SMV. Каждая глава сопровождается примерами и упражнениями.
Книга предназначена для студентов и аспирантов программистских специальностей, а также преподавателей и исследователей в области информатики и программной инженерии.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.02: Информационные системы и технологии
- 09.03.03: Прикладная информатика
- 09.03.04: Программная инженерия
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Александр Камкин Введение в формальные методы верификации программ 2-е издание, исправленное и дополненное Москва, 2025
УДК 004.415.5 ББК 37.972 К18 Камкин А. С. К18 Введение в формальные методы верификации программ. – 2-е изд., испр. и доп. – М.: ДМК Пресс, 2024. – 304 с.: ил. ISBN 978-5-93700-340-9 Книга основана на курсах лекций по формальным методам верификации программ, читаемых автором на кафедрах системного программирования МГУ, МФТИ и ВШЭ. Список тем включает: методы формализации семантики языков программирования (операционная и аксиоматическая семантика), методы формальной спецификации требований (программные контракты и темпоральная логика линейного времени), методы доказательства корректности программ (метод индуктивных утверждений и метод фундированных множеств) и методы проверки моделей (теоретико-автоматный подход в явной и символической формах); затрагиваются вопросы абстрактной интерпретации, разрешения ограничений, применения формальных методов в тестировании; даются сведения об инструментах Frama-C/AstraVer, Spin и SMV. Каждая глава сопровождается примерами и упражнениями. Книга предназначена для студентов и аспирантов программистских специальностей, а также преподавателей и исследователей в области информатики и программной инженерии. УДК 004.415.5 ББК 37.972 Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. © Камкин А. С., 2024 ISBN 978-5-93700-340-9 © Оформление, издание, ДМК Пресс, 2024
Содержание От издательства.........................................................................................................8 Предисловие ко второму изданию.....................................................................9 Предисловие к первому изданию.....................................................................14 Лекция 1. Введение в формальные методы верификации программ....16 1.1. Ошибки в программах........................................................................................17 1.2. Верификация программ.....................................................................................19 1.3. Формальная верификация программ...............................................................20 1.3.1. Проверка эквивалентности.........................................................................22 1.3.2. Проверка модели..........................................................................................26 1.3.3. Дедуктивный анализ....................................................................................28 1.4. Вопросы и упражнения.......................................................................................30 Лекция 2. Формализация семантики языков программирования.......32 2.1. Язык программирования while.........................................................................33 2.2. Формальная семантика.......................................................................................35 2.2.1. Операционная семантика...........................................................................37 2.2.2. Аксиоматическая семантика......................................................................39 2.2.3. Доказательное программирование...........................................................44 2.3. Вопросы и упражнения.......................................................................................45 Лекция 3. Дедуктивная верификация последовательных программ....47 3.1. Дедуктивные системы и доказательства..........................................................48 3.1.1. Примеры дедуктивных систем...................................................................49 3.1.2. Значимость и полнота дедуктивных систем............................................50 3.2. Дедуктивная верификация программ..............................................................51 3.2.1. Верификация программ на языке while...................................................52 3.2.2. Верификация линейных программ...........................................................56 3.2.3. Верификация ациклических программ....................................................57 3.2.4. Верификация циклических программ......................................................58 3.3. Вопросы и упражнения.......................................................................................60 Лекция 4. Инструменты дедуктивной верификации программ............63 4.1. Введение в язык ACSL.........................................................................................63 4.1.1. Базовые сведения о языке...........................................................................64 4.1.2. Типы данных.................................................................................................66
4 Содержание 4.1.3. Вспомогательные определения..................................................................66 4.1.4. Контракты функций.....................................................................................68 4.1.5. Утверждения и аннотации циклов............................................................71 4.2. Обзор платформы Frama-C................................................................................73 4.2.1. Платформа Frama-C.....................................................................................73 4.2.2. Модули Jessie/AstraVer и платформа Why3...............................................74 4.3. Вопросы и упражнения.......................................................................................75 Лекция 5. Метод индуктивных утверждений...............................................78 5.1. Синтаксис блок-схем...........................................................................................79 5.2. Семантика блок-схем..........................................................................................82 5.3. Метод индуктивных утверждений....................................................................83 5.3.1. Метод обратных подстановок....................................................................83 5.3.2. Точки сечения, индуктивные утверждения и условия верификации.....84 5.3.3. Общая схема метода индуктивных утверждений...................................86 5.4. Вопросы и упражнения.......................................................................................88 Лекция 6. Метод фундированных множеств................................................91 6.1. Завершимость программ и полная корректность..........................................91 6.2. Метод фундированных множеств.....................................................................92 6.2.1. Оценочные функции и условия завершимости.......................................94 6.2.2. Общая схема метода Флойда......................................................................94 6.3. Метод счетчиков..................................................................................................96 6.4. Дедуктивная система для доказательства полной корректности................97 6.5. Аннотирование программ для доказательства завершимости....................99 6.6. Вопросы и упражнения.....................................................................................100 Лекция 7. Автоматический синтез инвариантов циклов.........................103 7.1. Автоматизация дедуктивной верификации программ...............................103 7.2. Эвристические методы синтеза инвариантов циклов.................................105 7.2.1. Ослабление постусловия............................................................................105 7.2.2. Комбинирование пред- и постусловий...................................................107 7.3. Методы синтеза инвариантов на основе абстрактной интерпретации....108 7.3.1. Интервальная арифметика.......................................................................109 7.3.2. Общие сведения об абстрактной интерпретации.................................110 7.3.3. Теория выпуклых многогранников..........................................................113 7.4. Вопросы и упражнения.....................................................................................116 Лекция 8. Автоматическое доказательство теорем, SAT- и SMT-решатели.....................................................................................................118 8.1. Формальные теории и разрешающие процедуры........................................118 8.1.1. Примеры разрешимых и неразрешимых теорий..................................120 8.1.2. Задача выполнимости, SAT- и SMT-решатели.......................................122 8.2. Логика высказываний и SAT-решатели..........................................................123 8.2.1. Кодировка Цейтина....................................................................................123
Содержание 5 8.2.2. Метод резолюций для логики высказываний........................................125 8.2.3. Алгоритм DPLL проверки выполнимости..............................................127 8.3. Теории первого порядка и SMT-решатели.....................................................130 8.3.1. Метод резолюций для логики первого порядка....................................131 8.3.2. Теория равенства........................................................................................133 8.3.3. Комбинирование теорий...........................................................................135 8.4. Вопросы и упражнения.....................................................................................138 Лекция 9. Параллельные программы и логика LTL..................................140 9.1. Параллельные программы...............................................................................140 9.1.1. Параллельные программы над общей памятью...................................141 9.1.2. Асинхронный параллелизм: семантика чередований.........................142 9.1.3. Реагирующие системы и справедливость планировщика...................144 9.2. Спецификация реагирующих систем.............................................................145 9.2.1. Темпоральная логика LTL..........................................................................146 9.2.2. Структуры Крипке и семантика LTL........................................................149 9.2.3. Аксиоматическое определение LTL.........................................................150 9.3. Взаимное исключение процессов...................................................................151 9.3.1. Алгоритм Петерсона..................................................................................151 9.3.2. Справедливость планировщика while-программ.................................153 9.4. Вопросы и упражнения.....................................................................................153 Лекция 10. Инструмент проверки моделей Spin.......................................156 10.1. Введение в язык Promela................................................................................156 10.1.1. Типы данных, переменные и выражения.............................................157 10.1.2. Процессные типы и процессы................................................................161 10.1.3. Средства межпроцессной коммуникации............................................162 10.1.4. Управляющие операторы........................................................................165 10.1.5. Средства спецификации требований....................................................167 10.2. Введение в инструмент Spin..........................................................................170 10.2.1. Функции инструмента.............................................................................171 10.2.2. Основные опции.......................................................................................171 10.3. Вопросы и упражнения...................................................................................172 Лекция 11. Моделирование программ и предикатная абстракция......175 11.1. Представление программ структурами Крипке.........................................176 11.1.1. Обобщенные состояния (абстракция данных).....................................176 11.1.2. Обобщенные переходы (гранулярность действий).............................180 11.2. Модели последовательных и параллельных программ.............................181 11.2.1. Целочисленное деление..........................................................................181 11.2.2. Алгоритм Петерсона................................................................................183 11.2.3. Построение асинхронной композиции систем переходов................185 11.3. Предикатная абстракция и уточнение абстракции по контрпримерам...................................................................................................186 11.3.1. Декартова предикатная абстракция......................................................186
6 Содержание 11.3.2. Уточнение абстракции по контрпримерам (CEGAR)..........................188 11.4. Вопросы и упражнения...................................................................................192 Лекция 12. Автоматы Бюхи и регулярные ω-языки.................................194 12.1. Контрольный автомат.....................................................................................194 12.2. Конечные автоматы и регулярные языки....................................................195 12.2.1. Описание языков конечными автоматами..........................................196 12.2.2. Прямое произведение конечных автоматов........................................198 12.2.3. Проверка регулярного языка на пустоту..............................................199 12.3. Автоматы Бюхи и регулярные ω-языки.......................................................199 12.3.1. Описание ω-языков автоматами Бюхи.................................................200 12.3.2. Прямое произведение автоматов Бюхи................................................201 12.3.3. Проверка регулярного ω-языка на пустоту..........................................203 12.4. Теоретико-автоматный подход к проверке моделей.................................205 12.5. Вопросы и упражнения...................................................................................208 Лекция 13. Синтез автомата Бюхи по формуле LTL.................................210 13.1. Постановка задачи и предварительные замечания...................................210 13.2. Состояния автомата........................................................................................213 13.3. Переходы автомата..........................................................................................215 13.4. Начальные и допускающие состояния автомата........................................216 13.5. Алгоритм построения автомата....................................................................217 13.6. Общая схема проверки моделей для логики LTL........................................221 13.7. Вопросы и упражнения...................................................................................222 Лекция 14. Символьная проверка моделей................................................223 14.1. Символьные методы верификации..............................................................224 14.1.1. Символьное представление множеств и отношений.........................225 14.1.2. Символьное представление структур Крипке.....................................227 14.1.3. Символьные алгоритмы..........................................................................229 14.1.4. Ограниченная проверка моделей и k-индукция.................................230 14.2. Символьная проверка моделей для LTL.......................................................231 14.2.1. Символьное представление модели программы................................232 14.2.2. Символьное представление модели требований................................235 14.2.3. Проверка соответствия модели программы и модели требований....235 14.3. Двоичные решающие диаграммы.................................................................236 14.3.1. Синтаксис и семантика диаграмм.........................................................237 14.3.2. Сокращенные упорядоченные диаграммы..........................................238 14.3.3. Синтез диаграмм и манипуляции с ними............................................240 14.4. Вопросы и упражнения...................................................................................243 Лекция 15. Инструменты символьной проверки моделей семейства SMV.......................................................................................................246 15.1. Введение в язык SMV......................................................................................246 15.1.1. Типы данных, переменные и выражения.............................................247
Содержание 7 15.1.2. Встроенные функции...............................................................................251 15.1.3. Модули и их экземпляры........................................................................253 15.1.4. Конструкция выбора................................................................................257 15.1.5. Средства спецификации требований....................................................258 15.2. Примеры SMV-моделей..................................................................................258 15.2.1. Алгоритм Петерсона................................................................................258 15.2.2. Головоломка «Волк–коза–капуста».......................................................261 15.3. Введение в инструмент NuSMV.....................................................................263 15.3.1. Функции инструмента.............................................................................263 15.3.2. Основные опции.......................................................................................263 15.4. Вопросы и упражнения...................................................................................265 Лекция 16. Использование формальных методов в тестировании...269 16.1. Тестирование vs формальная верификация................................................270 16.2. Тестирование программ без состояния........................................................271 16.2.1. Тестирование на основе программных контрактов...........................271 16.2.2. Тестирование черного ящика.................................................................273 16.2.3. Тестирование белого ящика...................................................................276 16.3. Тестирование программ с состоянием.........................................................279 16.3.1. Обход графа состояний программы......................................................279 16.3.2. Абстракция состояний программы.......................................................280 16.4. Тестирование реагирующих систем и параллельных программ.............281 16.5. Заключение.......................................................................................................282 16.6. Вопросы и упражнения...................................................................................282 Используемые сокращения и обозначения................................................284 Список источников...............................................................................................290 Именной указатель...............................................................................................301
От издательства Отзывы и пожелания Мы всегда рады отзывам наших читателей. Расскажите нам, что вы думаете об этой книге – что понравилось или, может быть, не понравилось. Отзывы важны для нас, чтобы выпускать книги, которые будут для вас максимально полезны. Вы можете написать отзыв на нашем сайте www.dmkpress.com, зайдя на страницу книги и оставив комментарий в разделе «Отзывы и рецензии». Также можно послать письмо главному редактору по адресу dmkpress@gmail. com; при этом укажите название книги в теме письма. Если вы являетесь экспертом в какой-либо области и заинтересованы в написании новой книги, заполните форму на нашем сайте по адресу http:// dmkpress.com/authors/publish_book/ или напишите в издательство по адресу dmkpress@gmail.com. Список опечаток Хотя мы приняли все возможные меры для того, чтобы обеспечить высокое качество наших текстов, ошибки все равно случаются. Если вы найдете ошибку в одной из наших книг, мы будем очень благодарны, если вы сообщите о ней главному редактору по адресу dmkpress@gmail.com. Сделав это, вы избавите других читателей от недопонимания и поможете нам улучшить последующие издания этой книги. Нарушение авторских прав Пиратство в интернете по-прежнему остается насущной проблемой. Издательство «ДМК Пресс» очень серьезно относится к вопросам защиты авторских прав и лицензирования. Если вы столкнетесь в интернете с незаконной публикацией какой-либо из наших книг, пожалуйста, пришлите нам ссылку на интернет-ресурс, чтобы мы могли применить санкции. Ссылку на подозрительные материалы можно прислать по адресу электронной почты dmkpress@gmail.com. Мы высоко ценим любую помощь по защите наших авторов, благодаря которой мы можем предоставлять вам качественные материалы.
Предисловие ко второму изданию Второе издание по большей части совпадает с первым, но есть некоторые отличия. Во-первых, были устранены обнаруженные опечатки и неточности, переработан текст, добавлены иллюстрации и примеры. Во-вторых, была написана новая лекция (глава 15), посвященная SMV-подобным инструментам символьной проверки моделей (теперь теоретический материал лекции 14 подкреплен практикой). Кроме того, в книгу был добавлен именной указатель, а также сноски с краткой информацией о математиках, логиках и программистах, внесших вклад в становление и развитие формальных методов. Структура книги Книга состоит из 16 лекций (глав), снабженных вопросами для самопроверки и упражнениями: лекция 1 – вводная; лекции 2–8 посвящены дедуктивному анализу программ; лекции 9–15 – проверке моделей; лекция 16 – использованию формальных методов в тестировании. Более подробная информация о содержании лекций приведена ниже. В лекции 1 дается представление о корректности программ, т. е. их соответствии требованиям, и верификации – процессе проверки корректности. Делается обзор базовых методов верификации, как формальных (проверка эквивалентности, проверка моделей, дедуктивный анализ), так и неформальных (экспертиза, тестирование). Рассматривается общая схема формальной верификации: программе ставится в соответствие формальная модель программы, требованиям – формальная модель требований; проверка корректности программы сводится к формальной процедуре, устанавливающей соответствие между первой и второй моделями. Приводятся некоторые типы моделей и отношений соответствия. В лекции 2 на примере простого императивного языка while рассматриваются два метода формализации семантики языков программирования: операционная семантика (структурная операционная семантика Плоткина) и аксиоматическая семантика (дедуктивная система Хоара и метод Дейкстры, основанный на понятии слабейшего предусловия). Показывается, что программа – код на языке с формализованной семантикой – является математическим объектом, к которому применимы строгие логические рассуждения, в частности о его корректности или некорректности (конечно, при наличии формальных спецификаций требований). В лекции 3 рассматриваются основы дедуктивной верификации последовательных программ: приводятся сведения о дедуктивных системах и теории
10 Предисловие ко второму изданию доказательств; дается представление о верификации программы как поиске доказательства условия корректности в дедуктивной системе, формализующей язык программирования (платформу). Показывается, что инварианты циклов не выводимы из структуры программы. Задание инвариантов дает набросок доказательства корректности, проверку которого можно автоматизировать. В лекции 4 рассматриваются элементы языка ACSL (ANSI/ISO C Specification Language), предназначенного для формальной спецификации (аннотирования) программ на языке C. Делается обзор платформы статического анализа Frama-C (Framework for Modular Analysis of C Programs), а также модулей (plugins) Jessie и AstraVer, автоматизирующих дедуктивную верификацию C-программ на соответствие ACSL-спецификациям. Изложение базируется на примерах (подробное описание языка ACSL и основанных на нем инструментов можно найти в документации). Описанные средства могут использоваться в повседневной программистской практике. В лекции 5 рассматривается один из первых подходов к формальной верификации программ – метод Флойда. Подход состоит из двух частей: первая (метод индуктивных утверждений) предназначена для доказательства частичной корректности, т. е. корректности без учета завершимости; вторая (метод фундированных множеств) используется для доказательства завершимости и полной корректности (этой части посвящена лекция 6). Метод Флойда имеет дело с блок-схемами и позволяет анализировать программы с общим видом потока управления, в том числе не отвечающие принципам структурного программирования. Подход состоит в рассечении циклов, сопоставлении точкам сечения утверждений, построении условий верификации, связывающих утверждения соседних точек (индуктивных переходов), и их доказательстве. В лекции 6 рассматривается метод фундированных множеств, применяемый в паре с методом индуктивных утверждений для доказательства завершимости и полной корректности программ. Идея подхода заключается в следующем: каждой точке сечения сопоставляется оценочная функция; значение функции уменьшается при каждом прохождении через эту точку (при условии что истинно индуктивное утверждение), но в то же время не может уменьшаться бесконечно долго в силу характера изменений и ограничений на область значений. Если удается найти такие функции и доказать условия верификации, программа завершается и, более того, является полностью корректной. В лекции 7 рассматриваются вопросы автоматизации дедуктивной верификации программ, в частности вопросы автоматического синтеза инвариантов циклов. Задача синтеза оценочных функций может быть сведена к построению инвариантов программ, расширенных счетчиками. Описываются два класса методов: эвристические методы и методы, основанные на абстрактной интерпретации, т. е. символьном исполнении в упрощенных предметных областях – абстрактных моделях. Определяются основные понятия абстрактной интерпретации; приводятся примеры для таких областей, как интервальная арифметика и теория выпуклых многогранников.