Автоматический поиск ошибок в компьютерных программах с применением динамического анализа

• Автор: Исходжанов, Тимур Равилевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 133 с. : ил.

Содержание

1 Обзор систем поиска ошибок

1.1 Сценарии тестирования с применением детекторов

1.2 Ошибки первого и второго рода

1.3 Инструментирование программ

1.3.1 Динамическая инструментация

1.3.2 Статическая инструментация

1.3.3 Компиляторная инструментация

1.4 Библиотеки времени исполнения

1.5 Обработка и хранение состояния памяти

1.6 Поиск переполнений переменных целых типов
1.7 Поиск ошибок работы с памятью
1.7.1 МетсЬеск
1.7.2 Подавление ошибок первого рода
1.7.3 АсШгеэвЗапИлгег
1.7.4 Функции работы со строками и массивами байт
1.8 Поиск состояний гонок
1.8.1 Алгоритм Ьоскве!
1.8.2 Алгоритмы, основанные на отношении предшествования .
1.8.3 Гибридные алгоритмы
2 Детектор состояний гонок ТЪгеасШапШгег
2.1 Методология разработки
2.2 Алгоритм ТЬгеабБапШгег
2.2.1 Вспомогательные определения
2.2.2 Описание базового алгоритма
2.3 Информация об ошибках
2.3.1 Точность стеков предыдущих доступов к памяти
2.3.2 Пример сообщения об ошибке
2.4 Особенности программной реализации алгоритма
2.5 Модификации алгоритма
2.5.1 Режим Happens-before
2.5.2 Оптимизация fast mode
2.6 Сравнение с классическими алгоритмами
2.7 Динамические аннотации
2.8 Обработка событий синхронизации
2.9 Рекомендации по применению
2.10 Производительность детектора ThreadSanitizer
2.11 Переход к компиляторному инструментированию
2.12 Пример найденной критической ошибки
2.13 Заключение
3 Комбинированное инструментирование
3.1 Применение комбинированного инструментирования
3.2 Производительность систем инструментирования
3.3 Ускорение модуля инструментирования DynamoRIO
3.3.1 Быстрая трансляция уже инструментированного кода
3.3.2 Расходы на оптимизацию цепочек базовых блоков
3.3.3 Файловый кэш инструментированного кода
3.3.4 Исполнение отдельных модулей без трансляции
3.4 Направления дальнейших исследований
4 Практическое применение
4.1 Обзор инфраструктуры тестирования Chromium
4.2 Применение детекторов в системе тестирования
4.3 Доработка динамических детекторов ошибок
4.4 Заключение
5 Заключение
А Приложение
А.1 Примеры работы алгоритма ThreadSanitizer
А. 1.1 Простейшее состояние гонки
А. 1.2 Записи в память с синхронизацией посредством мьютекса
А. 1.3 Пропуск состояния гонки в режиме happens-before
А.1.4 Синхронизация, требующая аннотирования
А.2 Примеры распространенных состояний гонок

А.2.1 Состояние гонки на составных типах данных
А.2.2 Передача данных через переменную простого типа
А.2.3 Создание объекта без синхронизации
А.2.4 Инициализация с двойной проверкой условия
А.2.5 Использование блокировки на чтение при записи
А.2.6 Битовые поля
А.2.7 Состояние гонки на указателе виртуальной таблицы
А.З Ошибки первого рода гибридного алгоритма
А.3.1 Условная переменная РОЭ1Х
А.3.2 Очереди сообщений
А.3.3 Подсчет ссылок

Таким образом, удается избежать повторного исследования ложных срабатываний детектора и достичь нулевого количества сообщений об ошибках даже для программ, которые не полностью корректно обрабатываются алгоритмом Memcheck. Подобный подход применяется и в некоторых других детекторах ошибок.
1.7.3 AddressSanitizer
AddressSanitizer [23] — новый детектор ошибок работы с памятью, таких как выходы за границы переменных (массивов) на стеке, в куче и в глобальной памяти: а также доступы к освобожденной динамической памяти. Одной из основных целей при разработке AddressSanitizer было достижение высокой производительности, так как применение Memcheck в масштабах больших проектов стало не всегда приемлемым.
В результате анализа, основными причинами медленной работы Memcheck были признаны:
• Сложная процедура вычисления адреса теневой памяти по адресу основной памяти. Это требует либо сложного и объемного инструментирования каждого доступа к памяти, либо вызова вспомогательной функции.
• Для поиска одновременно и ошибок адресуемости, и ошибок инициализированное требуется большее количество теневой памяти, а также более сложная и менее эффективная инструментация, чем для поиска этих ошибок по отдельности.
• Даже если упростить доступы к теневой памяти и искать ошибки только одного вида, система инструментирования Valgrind сама по себе существенно замедляет работу тестируемой программы (см. раздел 1.3.1).
Ради достижения высокой производительности было принято несколько важных решений. Во-первых, AddressSanitizer не пытается находить ошибки использования неинициализированных данных. Это позволяет существенно уменьшить количество используемой теневой памяти, благодаря чему значительно упрощается и дополнительный код инструментации. Во-вторых, вместо устаревшей системы динамического инструментирования Valgrind используется более эффективная компиляторная инструментация, реализованная в виде