Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Введение в формальные методы верификации программ

Покупка
Новинка
Артикул: 890554.01.99
Доступ онлайн
1 049 ₽
В корзину
Книга основана на курсах лекций по формальным методам верификации программ, читаемых автором на кафедрах системного программирования МГУ, МФТИ и ВШЭ. Список тем включает: методы формализации семантики языков программирования (операционная и аксиоматическая семантика), методы формальной спецификации требований (программные контракты и темпоральная логика линейного времени), методы доказательства корректности программ (метод индуктивных утверждений и метод фундированных множеств) и методы проверки моделей (теоретико-автоматный подход в явной и символической формах); затрагиваются вопросы абстрактной интерпретации, разрешения ограничений, применения формальных методов в тестировании; даются сведения об инструментах Frama-C/AstraVer, Spin и SMV. Каждая глава сопровождается примерами и упражнениями. Книга предназначена для студентов и аспирантов программистских специальностей, а также преподавателей и исследователей в области информатики и программной инженерии.
Камкин, А. С. Введение в формальные методы верификации программ : учебное пособие / А. С. Камкин. – 2-е изд., испр. и доп. - Москва : ДМК Пресс, 2024. - 306 с. – ISBN 978-5-93700-340-9. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2274623 (дата обращения: 20.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Александр Камкин
Введение 
в формальные методы 
верификации программ
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 рассматриваются вопросы автоматизации дедуктивной верификации программ, в частности вопросы автоматического синтеза инвариантов циклов. Задача синтеза оценочных функций может быть сведена 
к построению инвариантов программ, расширенных счетчиками. Описываются два класса методов: эвристические методы и методы, основанные на 
абстрактной интерпретации, т. е. символьном исполнении в упрощенных 
предметных областях – абстрактных моделях. Определяются основные понятия абстрактной интерпретации; приводятся примеры для таких областей, 
как интервальная арифметика и теория выпуклых многогранников.


Доступ онлайн
1 049 ₽
В корзину