ПОТОКО-ЧУВСТВИТЕЛЬНЫЙ АНАЛИЗ УКАЗАТЕЛЕЙ ЯЗЫКА С, ОСНОВАННЫЙ НА ДИАГРАММАХ ДВОИЧНЫХ РЕШЕНИЙ Санкт-Петербургский Государственный Университет Математико-Механический. - презентация

1 ПОТОКО-ЧУВСТВИТЕЛЬНЫЙ АНАЛИЗ УКАЗАТЕЛЕЙ ЯЗЫКА С, ОСНОВАННЫЙ НА ДИАГРАММАХ ДВОИЧНЫХ РЕШЕНИЙ Санкт-Петербургский Государственный Университет Математико-Механический факультет Кафедра системного программирования Дипломная работа студента 544 группы Н. М. Тимофеева Научный руководитель Д.Ю. Булычев

2 Введение Классическая задача анализа потока данных Пример: анализ достигающих определений без анализа указателей void f() { … *p = 13; … }

3 Постановка задачи Creen – инструмент статического анализа языка C Потоко-чувствительный, контекстно- независимый анализ указателей языка С Потоко-чувствительность – учитывает порядок и количество исполнений операторов, влияющих на значения указателей Контекстная-независимость – анализ не учитывает контекст вызова процедур

4 void f() { … int* a = &b; if (y == &b) { a = &c }; … } Представление значений указателей бинарными деревьями предсказателей Предлагаемый подход

5 Сокращенные диаграммы двоичных решений Компактное представление больших множеств Эффективные операции над множествами Интерпретация операций на указателях в диаграммах двоичных решений Предлагаемый подход

6 Абстракция памяти Удобство хранения в диаграммах двоичных решений Аппроксимация значений выражений. Простейшая арифметика на указателях Итеративный анализ потока данных библиотеки PRANLIB

7 Пример void main() { while (p == &k) x = &y; if (y == 0) x = malloc(4); else k = &m; p = &k; d = x; return 1; }

8 Результаты Разработана абстракция памяти, удобная для хранения в диаграммах двоичных решений Интерпретация действий с указателями в диаграммах двоичных решений Реализован потоко-чувствительный алгоритм анализа указателей в инструменте Creen