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

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

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

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

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

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

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

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