Введение
1 Автоматизированное обнаружение уязвимостей в программах на языке C 10
1.1 Типы существующих программных дефектов 11
1.1.1 Некорректные операции с памятью 12
1.1.2 Некорректные операции с целыми типами 15
1.1.3 Операции чтения неопределенного значения 18
1.1.4 Некорректное использование функций стандартной библиотеки 19
1.1.5 Утечки памяти v 20
1.2 Методы и средства обнаружения программных дефектов 20
1.2.1 Методы лексического и синтаксического анализа 22
1.2.2 Программный комплекс Splint 30
1.2.3 Программный комплекс BOON 35
1.2.4 Метод абстрактной интерпретации программ 35
1.3 Выводы 37
2 Метод обнаружения дефектов в программах на языке С 38
2.1 Введение 38
2.2 Общий подход к решению задачи обнаружения дефектов в программах на языке С 39
2.2.1 Лексический и синтаксический анализ С-программы 39
2.2.2 Преобразование .дерева разбора в промежуточное представление 39
2.2.3 Верификация программы на языке промежуточного представления . 41
2.3 Описание языка IAL 42
2.3.1 Синтаксическая структура IAL-программы 43
2.3.2 Типы данных 43
2.3.3 Константы 48
2.3.4 Инструкции 48
2.4 Математическая модель языка IAL 59
2.5 Инварианты IAL-программы 66
2.6 Базовый алгоритм генерирования инвариантов 68
2.6.1 Алгоритм обхода управляющего графа 69
2.6.2 Свойства систем интервальных уравнений 75
2.6.3 Определение инвариантов в вершинах 83
2.6.4 Теорема о корректности алгоритма генерирования инвариантов 86
2.7 Построение и проверка индуктивных гипотез 91
2.8 Выводы 92
3 Программная реализация средства автоматизированного обнаружения дефектов в программах на языке С 94
3.1 Требования к программному комплексу 94
3.2 Основные этапы метода автоматизированного обнаружения уязвимостей 95
3.2.1 Лексический и синтаксический анализ С программы 95
3.2.2 Трансляция абстрактного синтаксического дерева в промежуточное представление 96
3.2.3 Верификация IAL-программы 96
3.3 Выводы -. 104
4 Исследование эффективности средства автоматизированного обнаружения уязвимостей в программах на языке С 105
4.1 Модельные примеры 105
4.1.1 Модельный пример stack-overflow 105
4.1.2 Модельный пример heap-overflow 107
4.2 Анализ программы xorg-server 109
4.3 Выводы 112
Заключение 113
Список использованных источников 114
