Прототип программного инструмента для анализа связности потока управления программ с открытым исходным текстом (Алексей Пустыгин, OSEDUCONF-2017)
Материал из 0x1.tv
Содержание
Аннотация
- Докладчик
- Алексей Пустыгин
Описано использования эквивалентных представлений исходного текста для получения участков связности потока управления на этапе статического анализа, для чего был разработан формат эквивалентного представления потока управления, пригодный для текстов на нескольких языках программирования. На основе этого формата написаны прототипы утилит получения такого представления, и на их основе разработаны прототипы утилит анализа, выходные данные визуализируются.
Видео
Слайды
Тезисы
Анализ пути исполнения на этапе статического анализа — часто встречающееся действие при разработке, сдаче в эксплуатацию и сопровождении программ[1][2]. Использование универсальных промежуточных представлений позволяет применять унифицированный функционал для текстов на нескольких языках[3][4].
Для анализа потока управления исходного кода необходимо разработать соответствующее эквивалентное представление[5]. Поток управления — множество всех возможных путей исполнения программы[6].
Универсальное представление графа потока управления (Universal Control Flow Representation, UCFR) будет описывать только конкретный участок выполнения программы — функцию или метод класса. Назовём такой участок потока управления функциональным блоком. Граф потока управления является ориентированным графом общего вида, допускающим циклы.
Основным элементом потока управления является функция (метод класса), а для построения формата достаточно удержать в промежуточном представлении элементы (узлы) дерева разбора, приведённые в таблице для избранного круга языков программирования.
| Язык | project | method / function | block / flow | tryExcept | finally | for | if | while | call |
|---|---|---|---|---|---|---|---|---|---|
| Java | + | методы | try / catch | + | for / foreach | + | while / dowhile | + | |
| Python | + | методы / функции | + | try / except | + | foreach | + | while | + |
| C++ | + | методы / функции | + | try / catch | — | for | + | while / dowhile | + |
| PHP | + | методы / функции | + | try / catch | (с версии 5.5) | for / foreach | + | while / dowhile | + |
В качестве текстовой нотации эквивалентного представления выбран формат XML[7], что позволяет сохранять эквивалентное представление в текстовом файле и проводить его анализ (возможно предварительный) вручную.
Анализ графа вызовов целиком — задача, требующая значительных ресурсов и порождающая слишком много данных. Предложено ограничить анализ графа вызовов только отдельными участками или трассами. Трасса — это последовательность вызываемых функций или методов на графе потока управления. Определённая трасса соответствует некоторому возможному сценарию исполнения анализируемой программы и представляется в виде ориентированного графа. Вначале выделяются функциональные блоки, входящие в трассу. Начальной вершиной ребра, связывающего блоки, выступает вызывающий функциональный блок, конечной — вызываемый. Внутри функционального блока трасса также представляется в виде ориентированного графа, узлами выступают блоки, представленные в блок-схеме (БСА) данной функции или метода, располагающиеся вдоль трассы, а рёбра соответствуют рёбрам БСА.
На основе функционала построения трасс были созданы прототипы анализаторов для поиска создаваемых вдоль трассы объектов и для поиска вдоль трассы интересующих вызовов.
Выводы
Для выполнения статического анализа возможных путей исполнения программ по исходному коду был предложен формат универсального эквивалентного представления потока управления, на основе которого реализованы ряд прототипов анализаторов, предназначенных для графовых визуализаций. На основе этих моделей были предложены различные виды анализа трасс. Используя полученные графические модели, можно анализировать исполнение программ с целью обнаружения логических ошибок на ранних этапах разработки, а также исследовать функционирование и алгоритмы существующих программ.
Примечания и отзывы
- ↑ Пустыгин А. Н. Построение эквивалентного представления зависимостей классов, полей, методов, функций и их перекрёстного использования в исходных текстах программ / А. Н. Пустыгин, А. А. Ковалевский, И. С. Белоусов // Одиннадцатая конференция «Свободное программное обеспечение в высшей школе»: материалы конференции. — Переславль-Залесский, 30–31 января 2016. — С. 40–44.
- ↑ Зубов М. В. Подходы к статическому анализу открытого исходного кода / М. В. Зубов, Е. В. Старцев, А. Н. Пустыгин // Сб. материалов Восьмой Междунар. конф. разработчиков и пользователей свободного программного обеспечения Linux Vacation / Eastern Europe. — Брест: Альтернатива, 2012. — С. 36–40.
- ↑ Зубов М. В. Построение универсального представления графа потока управления для статического анализа исходного кода / М. В. Зубов, А. Н. Пустыгин, Е. В. Старцев // Девятая конференция «Свободное программное обеспечение в высшей школе»: тез. докл. — М.: Альт Линукс, 2014. — С. 46–51.
- ↑ Ошнуров Н. А. Построение универсального промежуточного представления исходных текстов на языках C++ и C# / Н. А. Ошнуров, А. Н. Пустыгин, А. А. Ковалевский // Доклады Томского государственного университета систем управления и радиоэлектроники. — 2014. — Т. 33, № 3. — С. 135–139.
- ↑ Пустыгин А. Н. Построение эквивалентного представления зависимостей классов, полей, методов, функций и их перекрёстного использования в исходных текстах программ / А. Н. Пустыгин, А. А. Ковалевский, И. С. Белоусов // Одиннадцатая конференция «Свободное программное обеспечение в высшей школе»: материалы конференции. — Переславль-Залесский, 30–31 января 2016. — С. 40–44.
- ↑ Зубов М. В. Подходы к статическому анализу открытого исходного кода / М. В. Зубов, Е. В. Старцев, А. Н. Пустыгин // Сб. материалов Восьмой Междунар. конф. разработчиков и пользователей свободного программного обеспечения Linux Vacation / Eastern Europe. — Брест: Альтернатива, 2012. — С. 36–40.
- ↑ Зубов М. В. Подходы к статическому анализу открытого исходного кода / М. В. Зубов, Е. В. Старцев, А. Н. Пустыгин // Сб. материалов Восьмой Междунар. конф. разработчиков и пользователей свободного программного обеспечения Linux Vacation / Eastern Europe. — Брест: Альтернатива, 2012. — С. 36–40.
Plays:97
Comments:0