Построение универсального представления графа потока управления для статического анализа исходного кода (Алексей Пустыгин, OSEDUCONF-2014) — различия между версиями

Версия 13:15, 1 ноября 2014

Содержание

1 Аннотация
2 Видео
3 Слайды
4 Расширенные тезисы
- 4.1 Литература
5 Примечания и отзывы

Аннотация

Докладчик: Алексей Пустыгин

Анализ потока управления — важный этап статического анализа. Граф потока управления может быть описан в форме универсального высокоуровневого промежуточного представления. Получение такого представления реализовано для языков Java и Python.
Для повышения эффективности анализа потока управления предложено связать его с универсальным классовым представлением. Реализована методика уменьшения количества информации в эквивалентном представлении по какому-либо критерию (слайсинг).

Видео

on youtube

Оцените доклад «Построение универсального представления графа потока управления для статического анализа исходного кода (Алексей Пустыгин, OSEDUCONF-2014)»:

Отлично!
Хорошо.
Нормально…
Не очень :(
Просто хочу узнать результаты.

Слайды

Расширенные тезисы

В разработке программного обеспечения важную роль играют программные инструменты, позволяющие автоматически выполнять за программиста различную рутинную работу. К таким средствам можно отнести статический анализ исходного текста. Ранее было предложено использовать универсальные промежуточные представления для статического анализа как эффективное решение для двух и более языков [1].

Для анализа исходного кода на объектно-ориентированных языках было предложено универсальное классовое представление, позволяющее эффективно анализировать структуру классов проекта [2].

Интерес представляет анализ потока управления программы, который можно выполнять для всех языков программирования, поддерживающих процедурную парадигму. Основой для такого анализа является граф потока управления [3].

Формат графа потока управления вполне может быть универсальным для нескольких языков; в нем содержатся только блоки линейного текста и ветвления, вызванные циклами или условными переходами. В разных языках имеются синтаксические отличия в части условных операторов, циклов и обработки исключений. Таким образом, одной структурой данных можно описать поток управления для нескольких языков, например Java и Python, для которых уже реализовано получение универсального представления уровня классов.

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

Текст промежуточного представления графа потока управления хранится в формате XML, для чего создана схема [7]. На рисунке 1 показан простой случай графа потока управления с 2-мя параллельными ветвями, однако даже в такой простой форме он не является деревом, в листинге 1 показан текст на XML, полученный для него.

Как видно, для условной вершины выделен отдельный узел — A_if, и ветви альтернатив выходят из него. Данный формат базируется на формате GraphML [5] — открытом формате представления графов в виде текста XML.

Получение универсального представления графа потока управления было реализовано для языков Java и Python на основе разработанного ранее генератора абстрактного синтаксического дерева (AST) [6], который также используется для генерации UCR. Следует отметить, что в данном случае само AST не является промежуточным представлением, так как над ним не выполняется никакого анализа. Оно является просто набором данных,получаемым при разборе исходного текста.

Совместное использование двух универсальных представлений: графа потока управления (далее CFG) и диаграммы классов (далее UCR) открывает новые возможности анализа. Для объектно-ориентированных языков каждый отдельный участок потока управления — метод класса, поэтому методу сопоставляется атрибут класса, к которому метод принадлежит. В языке Python разрешены функции, не принадлежащие какому-либо классу; указания на класс функции не будет. Однако это не вызывает ошибок анализа, так как такие функции не связаны с диаграммой классов.

На рисунке схематично изображена работа всей программной системы, в том числе с анализаторами, основанных на совместном использовании представлений.

Визуализация потока управления производится с помощью утилиты dot из пакета graphviz [8]. Отметим, что внутри блоков графа выделяются вызовы функций/методов (именуемые с использованием префикса «Call»). Вызовы функций/методов безусловно представляют основной интерес, так как обеспечивают связи по управлению между отдельными функциями/методами (связность графа). Пример результата визуализации приведен на рисунке 2. На нем представлен метод set_color_formatter() класса logilab.common.logging_ext.ColorFormatter из пакета Logilab Common [9].

Также интерес представляет слайсинг-преобразование — метод уменьшения количества данных в представлении по какому-либо критерию [10]. Наиболее интересен совместный слайсинг двух представлений. Особый интерес представляет слайсинг одного из представлений по критерию, относящемуся к другому. Так, например, для CFG можно выделять те методы классов, в которых создается указанный класс (вызывается его метод-конструктор). Для UCR можно получать срезы тех классов, которые создаются в указанном блоке потока управления, или получать срез тех классов, в методах которых создается указанный класс.

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

Литература

[1] Зубов М.В., Пустыгин А.Н., Старцев Е.В. Подходы к статическому анализу открытого исходного кода — Брест: Альтернатива, 2012. — 158с. — С. 36–40.
[2] Зубов М.В., Пустыгин А.Н., Старцев Е.В. Применение универсальных промежуточных представлений для статического анализа исходного программного кода. — Томск: Издательство ТУСУР, 2013. — 142 с. — С 64-69.
[3] Граф потока управления — Википедия
[4] Control Flow — GNU Compiler Collection (GCC) Internals.
[5] The GraphML File Format.
[6] А. Ахо, М. Лам, Р. Сети, Д. Ульман. Компиляторы: принципы, технологии и инструментарий — М.: Вильямс, 2010. — 1184 с.
[7] XML-схема универсального представления графа потока управления.
[8] Graphviz — Graph Vizualization software.
[9] Logilab-Common.
[10] Program slicing — Википедия.

Примечания и отзывы