Автоматическое обнаружение дефектов в многопоточных программах методами статического анализа

• Автор: Моисеев, Михаил Юрьевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Санкт-Петербург
• Количество страниц: 174 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. СРАВНИТЕЛЬНЫЙ АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ И СРЕДСТВ ОБНАРУЖЕНИЯ ОШИБОК В МНОГОПОТОЧНЫХ ПРОГРАММАХ

1.1. Критерии оценки методов и средств обнаружения ошибок

1.2. Общие подходы к анализу параллельных программ

1.2.1. Подходы на основе анализа частичных порядков

1.2.2. Подходы на основе анализа наборов конструкций синхронизации

1.2.3. Подходы на основе извлечения инвариантов

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

1.3. Методы обнаружения ошибок в многопоточных программах

1.3.1. Комбинирование алгоритмов анализа

1.3.2. Использование аппроксимаций
1.4. Средства обнаружения ошибок в многопоточных программах на языке С
Выводы
ГЛАВА 2. МОДЕЛЬ МНОГОПОТОЧНОЙ ПРОГРАММЫ И ПРЕДСТАВЛЕНИЕ РЕЗУЛЬТАТОВ СТАТИЧЕСКОГО АНАЛИЗА
2.1. Общая структура предлагаемого подхода
2.2. Модель многопоточной программы
2.2.1 Объекты и функции РИтгеасП
2.2.2 Представление объектов и функций РЛнеасП в модели программы
2.3. Представление динамических свойств многопоточной программы
2.3.1. Состояние программы
2.3.2. Представление информации о параллельном выполнении программы

ГЛАВА 3. МЕТОДЫ АНАЛИЗА ПАРАЛЛЕЛЬНОГО ВЫПОЛНЕНИЯ
ПРОГРАММЫ
ЗЛ. Организация совместного выполнения алгоритмов анализа
3.2. Алгоритм определения действий над объектами синхронизации
3.3. Алгоритм определения состояний объектов синхронизации
3.3.1 Способы построения допустимых комбинаций
3.3.2 Построение неполных комбинаций
3.3.3 Правила расчета состояний объектов синхронизации
3.3.4 Анализ конструкции state
3.4. Алгоритм построения отношений параллельности
3.5. Алгоритм построения отношений синхронизации
3.6. Алгоритм учета взаимного влияния потоков программы
3.7. Итеративный алгоритм анализа конструкций
3.7.1 Правила работы итеративного алгоритма
3.7.2 Завершимость итеративного алгоритма
3.7.3 Сохранение полноты результатов анализа
ГЛАВА 4. АЛГОРИТМЫ ОБНАРУЖЕНИЯ ОШИБОК В
МНОГОПОТОЧНЫХ ПРОГРАММАХ
4.1 Классификация программных ошибок
4.2 Правила обнаружения программных дефектов
4.2.1 Правила обнаружения ошибок управления ресурсами и динамической памятью
4.2.2 Правила обнаружения утечек ресурсов и памяти
4.2.3 Правила обнаружения ошибок работы с буферами
4.2.4 Правила обнаружения ошибок отсутствия инициализации
4.2.5 Правила обнаружения ошибок синхронизации
4.3 Обнаружение множественных дефектов
ГЛАВА 5. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ И ОЦЕНКА ЭФФЕКТИВНОСТИ РАЗРАБОТАННЫХ МЕТОДОВ
5.1 Реализация разработанных методов

5.2 Проведение экспериментальных исследований
5.3 Оценки полноты и точности
5.4 Оценка вычислительной сложности
5.4.1 Вычислительная сложность правил, использующих
допустимые комбинации
5.4.2 Вычислительная сложность итеративного алгоритма.
5.4.3 Сравнение с существующими подходами
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЕ 1. РАСШИРЕНИЕ ПРЕДЛОЖЕННОГО ПОДХОДА НА
ДРУГИЕ ОБЪЕКТЫ СИНХРОНИЗАЦИИ РТНКЕАБЗ
ПРИЛОЖЕНИЕ 2. КОРРЕКТНОСТЬ ПРЕДСТАВЛЕНИЯ АТОМАРНЫХ
КОНСТРУКЦИЙ
ПРИЛОЖЕНИЕ 3. КОРРЕКТНОСТЬ ПРАВИЛ ПОСТРОЕНИЯ ОТНОШЕНИЙ ПАРАЛЛЕЛЬНОСТИ С ВИРТУАЛЬНЫМИ БЛОКАМИ ..169 ПРИЛОЖЕНИЕ 4. СОХРАНЕНИЕ ПОЛНОТЫ РЕЗУЛЬТАТОВ ПРИ АНАЛИЗЕ МНОГОПОТОЧНЫХ ПРОГРАММ

единственным источником недетерминизма выполнения программы является планировщик ОС, то вычислительную сложность методов, не использующих
аппроксимации, можно оценить как ), где I — максимально возможное число переключения контекста, с - число выбора потоков при каждом переключении контекста. Величина I прямо пропорциональна размеру программы, величина С - числу параллельно выполняющихся потоков.
Предлагается подход, основанный на аппроксимации поведения планировщика, ограничивающей недетерминизм планировщика некоторым число выполняемых конструкций (Delay-bounding). Для этого используется детерминированный планировщик и рассматриваются все возможные варианты переключения контекста в течение выполнения 1 конструкций. Утверждается, что предложенная аппроксимация несущественно влияет на полноту анализа и позволяет обнаруживать большое число программных ошибок. Вычислительная сложность предложенной аппроксимации
оценивается как

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