Модели и алгоритмы универсальных промежуточных представлений для статического анализа потока управления программ по их исходному коду тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Зубов Максим Валерьевич

• Зубов Максим Валерьевич
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Зубов Максим Валерьевич

ВВЕДЕНИЕ

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

1.1.Статический анализ, промежуточные представлени

1.2.Идеи развития представлений

1.3.Выводы к первой главе

ГЛАВА 2.МОДЕЛЬ ПРОМЕЖУТОЧНЫХ ПРЕДСТАВЛЕНИЙ

2.1.Модель промежуточного представления

2.2.Автоматная модель генератора промежуточных представлений

2.3.Выводы ко второй главе

ГЛАВА 3.РЕАЛИЗАЦИЯ И ТЕСТИРОВАНИЕ ГЕНЕРАТОРОВ ПРЕДСТАВЛЕНИЙ

3.1.Разработка прототипов программных утилит

3.2.Оценка эффективности использования промежуточных представлений

3.3.Выводы к третьей главе

ГЛАВА 4.РЕАЛИЗАЦИЯ, ТЕСТИРОВАНИЕ И ОЦЕНКА ЭФФЕКТИВНОСТИ АНАЛИЗАТОРОВ

4.1.Разработка анализаторов для промежуточного представления

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

4.3.Визуализация потока управления и анализ трасс

4.4.Выводы к четвертой главе

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

СПИСОК ЛИТЕРАТУРЫ

СПИСОК ИЛЛЮСТРАТИВНОГО МАТЕРИАЛА

ПРИЛОЖЕНИЯ

1. Фрагмент исходного кода программы получения промежуточного представления

Введение

Актуальность темы исследования

Разработка программного обеспечения в современных условиях — это задача, требующая быстроты и эффективности. Если программа выпускается не вовремя, не содержит важных функций или имеет ошибки, то она проигрывает в конкурентной борьбе. Для решения этих проблем некоторые задачи выполняются машинно и в автоматическом режиме. Это позволяет экономить время программистов, а также повысить эффективность выполнения таких задач. К таким задачам можно отнести: интегрированную отладку, автоматизированное тестирование, непрерывную интеграцию [14] и статический анализ [2]. Статический анализ позволяет находить множество ошибок в программах на ранней стадии разработки, помогает лучше понимать структуру программ [3]. Он берет свое начало с разработок Bell Labs в 70-х годах XX века и работ Кусо (Cousot)[56] и Аллена (Allen)[46].

Большинство анализаторов делают упор на поиск конкретных ошибок[17], привязанных к конкретным языкам. Например, популярные анализаторы FindBugs[61] и Checkstyle[55] для языка Java или PVS Studio[90] для C/C++ узко специализированы именно на ошибках, что показано в работах Айваха (Ayewah) [49] и Карпова [20]. Такие анализаторы не могут быть расширены или применены где-то кроме их целевого языка. Из такой ситуации следует, что область построения модели для анализа развита недостаточно. Многие просто используют дерево разбора парсера, как наиболее изученную модель в области компиляции, в качестве промежуточного представления — набора машинных данных, семантически эквивалентных исходному коду, над которыми выполняется анализ [23].

На сегодняшний день имеются различные научные работы, описывающие использование различных промежуточных представлений. Например, Линтон (Linton) в 0mega[80] предлагал использовать реляционные базы данных, Крю (Crew) в ASTL0G[57] - базу знаний на языке Prolog, а Бэйер (Beyer) в BLAST[87] - конеч-

ный автомат. На практике, в основном, распространенные анализаторы используют AST, что может осложнять некоторые цели анализа, или делать другие неэффективными.

При разработке программного обеспечения человеком всегда имеют место ошибки определенного рода. Это могут быть ошибки проектирования - построение архитектуры, затрудняющей расширение системы, ошибки такого рода связаны с используемой парадигмой программирования, особо остро этот вопрос стоит в области объектно-ориентированного проектирования[27]. Подобные ошибки зачастую не могут быть однозначно определены, так как они связаны со взглядом человека на принципы проектирования ПО. Один и тот же паттерн[35] в определенной ситуации может быть расценен разными проектировщиками по разному. Кроме того, существует широкий круг ошибок некорректного использования конструкция языка, работы с памятью, логических ошибок, ошибок использования API и прочих, от которых не застрахован ни один проект[25].

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

Кроме того иногда требуется выполнять верификацию[32] - проверить соответствие программного обеспечения некоторым требованиям, предъявленным к нему на этапе проектирования.

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

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

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

Кроме того, в настоящее время огромное распространение получает программное обеспечение с открытым исходным кодом. Такое программное обеспечение содержит в себе много информации об архитектурных решениях и алгоритмах. Однако, в случае больших программных комплексов технических систем, таких как сервера приложений, исследование исходного кода достаточно затруднительно ввиду больших его объемов. Таким примером может выступить веб-сервер Apache, под управлением которого работает большинство веб-серверов. Исследование такого программного кода представляет очень большой интерес. В качестве средства исследования и извлечения знаний из такого программного обеспечения может выступать статический анализ. Извлечение информации и реверс-инжениринг исследуются в работах Коцке (Koschke) [76], Ицыксона [19], Язова [43].

Степень разработанности темы исследования

Развитию статического анализа в области поиска ошибок, а также предложения подсказок по рефакторингу посвящено большое количество работ российских и зарубежных исследователей:: Дамнса (Damns)[60], Аветисяна[2], Ицыксо-на[18].

Идеи развития модели промежуточных представлений предлагались Це-рански (Czeranski) [59], Коцке (Koschke) [75], Веббом (Webb) [105] в их анализаторах Bauhaus и MALPAS. Основные идеи — это использование некоторого псевдо-

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

Среди исследований, посвященных анализу потока управления программы, следует выделить работы Шиверса (Shivers) [97], Битнера [5] и Чернова [42]. Эти работы в основном направлены на использование графа потока управления при оптимизации или анализе алгоритмов. Кроме того, стоит выделить исследователей, работы которых посвящены анализу графа вызовов программ, - Али (Ali) [45], Гроува (Grove) [64], Костакиса (Kostakis) [77].

Введение диссертации (часть автореферата) на тему «Модели и алгоритмы универсальных промежуточных представлений для статического анализа потока управления программ по их исходному коду»

Цель работы

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

Задачи исследования

Для достижения цели в работе решаются следующие задачи:

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

2. Разработка методов и алгоритмов получения предложенного промежуточного представления в разработанном формате из исходного кода.

3. Разработка методов и алгоритмов проверки эффективности использования полученного универсального промежуточного представления при выполнении анализа, программная реализация, и проведение вычислительного эксперимента.

4. Разработка методов и алгоритмов анализа предложенного промежуточного представления в задачах рефакторинга, анализа потока управления и извлечения информации.

5. Реализация предложенных методов и алгоритмов получения и анализа промежуточного представления в виде программного комплекса. Выполнение вычислительных экспериментов для выработки оптимальных входных значений разработанных инструментов.

Методы исследования

Основные результаты диссертационной работы получены с использованием математического аппарата теории множеств, теории графов, теории автоматов; методов вычислительных экспериментов, методов объектно-ориентированного анализа, проектирования и программирования.

Научная новизна

1. Модель универсального промежуточного представления графа потока управления для статического анализа программ, в отличии от известных, позволяет без потери и избыточности данных анализировать граф потока управления, отличительной особенностью которого являются свойства узлов, позволяющие построить граф вызовов. Такая модель описывает в виде дерева ориентированный граф произвольной структуры, а также позволяет взаимодействовать универсальным утилитам с генераторами для различных языков программирования.

2. Метод получения промежуточного представления использует синтаксический анализатор компилятора с открытым исходным кодом, что отличает его от типового решения — генератора парсера по входной грамматике языка программирования, что обеспечивает точность получаемых данных. Кроме того, алгоритм преобразования дерева разбора в целевое промежуточное представление с его обходом в глубину отличается использованием аб-

страктного цифрового автомата, что позволяет описать его получение в виде модели.

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

4. Методы визуализации для анализа исходного кода программ, в отличие от известных, используют предложенные модели универсальных представлений, что позволяет получать графические изображения потока управления и графа вызовов из единого формата данных для нескольких языков программирования.

Практическая значимость работы

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

2. Предложенные алгоритмы выполнения статического анализа, основанные на универсальном формате, позволяют получать количественные оценки для улучшения существующего кода, а так же визуализировать исходный код для извлечения информации о его функционировании.

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

Разработанное программное обеспечение может использоваться в процессе разработки нового программного обеспечения или улучшения существующего. Результаты работы внедрены в рабочий процесс разработки продуктов и сервисов направления решений в образовании ЗАО «Нау-сервис» (ГК КЛиМБК). В результате внедрения упростился процесс доработки, модернизации и развития существующих программных модулей систем путем проведения исследования кода и выполнения предложений по рефакторингу.

Положения, выносимые на защиту

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

2. Метод и алгоритм получения предложенного промежуточного представления для статического анализа, основанный на использовании абстрактного цифрового автомата с памятью, который позволяет формализовать процесс получения представления, что ускоряет разработку новых генераторов по готовой модели. Генератор представления основан на открытом исходном коде компилятора, что, в отличие от типового решения — генератора парсе-ра, позволяет избежать дополнительной верификации результатов работы, так как такую реализацию можно считать эталонной.

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

4. Методы и алгоритмы выполнения анализа потока управления с целью оценки качества исходного кода, использующие разработанные универсальные промежуточные представления, выполняют анализ исходного кода единообразно для нескольких входных языков без их модификации.

5. Программный комплекс, выполняющий статический анализ исходных текстов на нескольких языках программирования, реализующий предложенные модели и алгоритмы получения и обработки универсального промежуточного представления в 9 анализаторах.

Апробация работы

Основные положения диссертационной работы были представлены на следующих 15 конференциях и семинарах, 6 из которых — международные:

1. Седьмая конференция «Свободное программное обеспечение в высшей школе» - Переславль-Залесский, ИПС РАН, январь, 2012 г.

2. Семинар Научно-Практического Центра СКВ и ОПО - Челябинск, ЧелГУ, февраль, 2012 г.

3. Международная научно-практическая конференция «FOSS Lviv-2012» -Украина, Львов, Львовский национальный университет имени Ивана Франко, апрель 2012 г.

4. 4-я корпоративная конференция «Naumen Devel Camp #4» - Екатеринбург, Naumen, май 2012 г.

5. Восьмая международная конференция «Linux Vacation / Eastern Europe» -Беларусь, Гродно, июнь, 2012 г.

6. Восьмая конференция «Свободное программное обеспечение в высшей школе» - Переславль-Залесский, ИПС РАН, январь, 2013 г.

7. Научно-практическая конференция «Тверские интернет технологии» -Тверь, ТвГУ, апрель, 2013 г.

8. Девятая конференция «Свободное программное обеспечение в высшей школе» - Переславль-Залесский, ИПС РАН, январь, 2014 г.

9. Семинар Сектора визуализации ОСО ИММ УрО РАН - Екатеринбург, ИММ УрО РАН, июнь, 2014 г.

10. Семинар Сектора визуализации ОСО ИММ УрО РАН - Екатеринбург, ИММ УрО РАН, октябрь, 2014 г.

11. Семинар кафедры компьютерной безопасности и прикладной алгебры ЧелГУ

— г. Челябинск, ЧелГУ, декабрь 2014 г.

12. Научный семинар под руководством профессора В.Е. Федорова на кафедре математического анализа ЧелГУ — г. Челябинск, ЧелГУ, январь 2015 г.

13. Корпоративная конференция «Naumen Devel Camp 15#2» - г. Екатеринбург, Naumen, октябрь 2015 г.

14. III Международная конференция «Интеллектуальные технологии обработки информации и управления» (ITIPM'2015) — г. Уфа, УГАТУ, ноябрь 2015 г.

15. Семинар кафедры компьютерной безопасности и прикладной алгебры ЧелГУ

— г. Челябинск, ЧелГУ, февраль 2016 г.

Список публикаций автора

Основные материалы диссертационной работы опубликованы в 16 работах, среди них 8 статей - в журналах из списка периодических изданий, рекомендованных ВАК РФ; 8 работ - в трудах ведущих тематических изданий и трудах российских и международных конференций. Имеется свидетельство о регистрации программы для ЭВМ.

Личный вклад автора

Все результаты получены лично автором. Из совместных публикаций в работу включены только результаты, которые получены соискателем. В совместных работах с А.Н. Пустыгиным научному руководителю принадлежат постановка за-

дачи, общее руководство и частично выводы. Результаты совместных статей с Е.В. Старцевым использовались в части, относящейся к диссертации автора. В работе [111] диссертанту принадлежат основные идеи и результаты. В статье [115] диссертантом написаны разделы «Постановка задачи», «Список реализованных анализов», «Анализ недостижимых функциональных блоков», «Поиск трассы между заданными функциональными блоками», «Математические модели анализаторов с пороговыми функциями», «Практические результаты использования анализаторов». В работе [114] - разделы «Промежуточные представления исходных текстов программ», «Применение универсальных и многоуровневых представлений». В статье [112] - раздел «Отношение агрегирования». В работе [116] диссертанту принадлежит разработка прототипа примера получения представления исходного кода на естественном языке. В статье [118] диссертантом написаны разделы «Промежуточные представления», «Классификация представлений», «Представления по типу используемых данных». В статье [123] - разделы «Инструменты Java», «Многоязыковые инструменты анализа». В материалах конференции [122] диссертантом подготовлены материалы на с. 82; в материалах конференции [124] - на с. 165, 166; в материалах конференции [119] - на с. 36, 37; в материалах конференции [117] - на с. 53, 56, 57; в материалах конференции [120] - на с. 53; в материалах конференции [121] - на с. 46, 47, 50, 51.

Структура диссертации

Диссертация состоит из введения, четырех глав, заключения и списка используемой литературы. Текст диссертации изложен на 134 листах, включая 46 рисунков, 15 таблиц, библиографический список из 125 наименований, список сокращений и условных обозначений, список иллюстративного материала, одно приложение.

Глава 1. Статический анализ с использованием промежуточных представлений

1.1. Статический анализ, промежуточные представлени

1.1.1. Общие сведения и определения

Существуют 2 основных способа анализа программного обеспечения: динамический и статический [2]. К динамическим методам анализа относятся способы проверки кода в процессе его исполнения (в динамике). Можно выделить следующие виды таких анализаторов:

1) Отладчики (просмотр состояния программы в любой момент ее выполнения);

2) Профайлеры (анализ производительности и потребления памяти под нагруз-кй);

3) Фазеры (специфические анализаторы, занимающиеся перебором всех возможных входных данных).

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

К достоинствам статического анализа можно отнести следующие:

1) Не требуется подготовка (или случайный поток) входных данных, специально созданное окружение для исполнения кода;

2) Можно анализировать программы, разработанные для любой целевой архитектуры или платформы, что очень удобно, например, для кросс-компилиру-емых приложений;

3) При тестировании могут быть упущены специфичные, редко встречающиеся ситуации, которые будут учтены в анализе, так как анализатор оперирует со

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

Среди недостатков статического анализа можно выделить следующие:

1) Для определения ошибок интеграции требуются дополнительные знания (например, доступ к исходному коду)

2) Для больших программ время выполнения анализа может быть очень большим

3) В реальности приходится использовать упрощенные модели, что сказывается на качестве анализа. В частности при верификации обнаруживаются не все ошибки и происходят "ложные срабатывания" [32]

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

Исходный код программы — текст, который можно обрабатывать только как текст (поиск, регулярные выражения). Для эффективной обработки требуется представить его в виде машинных данных. В данном случае, для статического анализа требуется «промежуточное представление» - набор машинных данных, над которыми выполняется анализ [124] (рисунок 1).

Основным способом перевода исходного кода из текстового формата является синтаксический анализ [23] (рисунок 1). Он используется при компиляции программ на первой стадии, когда считывается исходный код, и из него получается абстрактное дерево разбора. Исходный код является текстом на формальном языке — языке программирования. Такой текст легко представляется в виде деревьев (графов без циклов) разбора согласно его формальной грамматике [11]. Для описания формальных грамматик в основном использует форма Бэкуса-Наура (БНФ)

(используется в yacc[82], bison[79]), или ее усовершенствованный вариант расширенная форма Бэкуса-Наура (antlr[47]).

Исходный код

Синтаксический

анализ

(БНФ-РБНФ)

Промежуточное представление

Преобразование машинных данных (деревьев)

ПП

пп

Рисунок 1. Получение промежуточного представления из исходного кода

Так как эффективной, изученной и неоднократно используемой формой представления исходного кода является дерево, то будем считать, что любое промежуточное представление должно являться деревом (рисунок 1). Если рассмотреть другие варианты, например БД, то внутри БД данные так же представлены B-деревьями и В*-деревьями, а кроме того, исходно при использовании БД в качестве представления, предлагалось заполнять БД согласно данным, полученным из AST. Если рассмотреть логические языки в качестве представления, то становится понятно, что базы знаний логических языков — есть деревья, и в любом случае текст на таких языках так же можно представить в виде дерева разбора по формальной грамматике.

Существует множество различных готовых программ, выполняющих статический анализ исходного кода [123]. Самая большая часть из них узко-направлена на поиск конкретных ошибок в конкретных языках программирования [17]. Такие анализаторы, в основном используют в качестве представления абстрактное син-

таксическое дерево разбора, потому что для обнаружения ошибок требуются детали, присущие только одному входному языку.

Тем не менее на практике встречается использование большого количества других вариантов промежуточных представлений [118]. Многие такие представления разрабатывались для целей отличных от поиска ошибок в конкретном языке программирования. Необходимо провести обзор всех используемых промежуточных представлений с целью выявления идей, подходящих для решения поставленных задач [99].

1.1.2. Промежуточное представление на основе абстрактного

синтаксического дерева

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

Для примера в листинге 1 можно построить абстрактное синтаксическое дерево разбора, представленное на рисунке 2. Оно демонстрирует детальность получаемого представления.

Листинг 1. Пример исходного кода на языке C.

int func (int a, int b){ int c=2; if (a>b) { c++;

}

else { c--;

}

return c;

}

Рисунок 2. Пример абстрактного синтаксического дерева разбора в виде графа

Рассмотрим примеры современных анализаторов, использующих абстрактное дерево разбора. Checkstyle [55] для языка Java получает дерево с помощью

инструмента генерации парсеров ANTLR. Compass/ROSE для анализа на C/C++ и Fortran [93] создает дерево на основе собственной инфраструктуры компилятора ROSE [54]. PyLint [92] - анализатор для языка Python, он выполняет анализ кода на основе отдельного проекта logilab-astng. DMS Software Reengineering Toolkit [95] позволяет генерировать AST для COBOL, C/C++, Java, Fortran и VHDL, реализуя отдельный генератор для каждого языка на уровне Rule Compiler.

1.1.3. Реляционное представление

Реляционное представление или представление в виде базы данных предполагает принципиально другой подход в сравнении с AST. Каждый элемент грамматики представляется в виде реляционного отношения. Эти отношения отражаются в реляционной базе данных. За счет возможности создания связей по ключам и ограничений реализуются взаимосвязи элементов грамматики. Стоит отметить, что реляционное представление вовсе не формируется напрямую из кода. Сначала по коду получается AST, а уже потом по нему заполняется БД. Первоначально использовать реляционные базы данных было предложено M. Linton в его анализаторе Omega [80]. Основной современный проект, использующий подобный подход, — Semmle Limited Analysis [100], который является коммерческим и закрытым, по нему отсутствуют публикации. Он использует собственный язык .QL для выполнения запросов к базе данных с исходным кодом и сопутствующими артефактами, такими как задачи из баг-трекера или ревизиями из системы контроля версий.

Такое представление достаточно избыточно, что свойственно всем базам данных. Оно может достигать весьма существенных объемов на больших проектах. Но это представление очень удобно при больших объемах, так как получение данных об узлах кода сводится к выполнению запросов. Для человека такое представление может оказаться весьма непонятным, так как будет затруднена ручная корректировка и анализ. Кроме того, такое представление требует индивидуальное проектирование БД (таблиц, индексов, ключей) для каждой грамматики. Это увеличивает затраты на его получение. Например, для примера на языке C из листинга

1 потребуется база данных, описываемая следующей схемой [12], представленной на рисунке 3. Заполнение такой базы данных для этого примера представлено на рисунке 4.

Рисунок 3. Схема базы данных для хранения промежуточного представления

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

function

ID name body

1 tunc 1

argument

ID function var

1 1 1

2 1 2

code block

ID

statement

ID block order

1 1 1

2 1 2

3 2 1

4 3 1

5 1 3

const

ID value

1 2

2 b

if

statement cond ition true block false block

2 1 2 3

return

statement var

5 с

unary op

state men var type

3 3 post++

4 3 post-

variable

ID name type

1 a int

2 b mt

3 с int

assign

statement lvalue rvalue

1 3 1

compare

ID lvalue rvalue type

1 1 2 g

Рисунок 4. Пример заполнения таблиц в базе данных, содержащей промежуточное представление

1.1.4. Применение логических языков и баз знаний

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

С помощью SQL невозможно разрешить транзитивные замыкания, возникающие при анализе циклически-зависимых отношений. Однако, выполнение такой операции может быть ключевым объектом некоторых видов анализа. Как например, простейшая зависимость в иерархии классов (рисунок 5).

Для представления иерархии предложенных классов логично предположить использование простого отношения Class=(name, parent) (рисунок 6).

— Class

name parent

Рисунок 6. Схема базы данных для хранения отношения иерархии классов

Тогда таблица для такого отношения Class будет заполнена следующим образом (рисунок 7).

Class

name parent

A

В A

С В

D С

Рисунок 7. Пример заполнения таблицы, хранящей иерархию наследования классов

Можно заметить, что проверить, является ли 1 класс родителем другого с помощью классического SQL не так то просто. Если это два подряд идущих класса, то ситуация тривиальна. Если нет, то необходимо выполнять сцепление таблиц ровно столько раз, сколько уровней рекурсивной вложенности имеется.

Логические языки не просто допускают рекурсию на своих предикатах, это одна из их ключевых особенностей, как ближайших родственников функциональных. Легко понять, как указанные предикаты будут выполнены в виде SQL. Однако, запись в таком виде куда более наглядная и понятная.

Логические языки оперируют не с базами данных, а с базами знаний (Prolog) или дедуктивными базами (Datalog). Представление в виде таких баз происходит только на этапе анализа. В реальности, при реализации используется реляционное представление или AST. При использовании логических языков возрастает повторная используемость однажды написанных предикатов, потому что их поведение легко понять из описания.

Так как интерпретация БД в виде базы знаний — это дополнительный уровень в архитектуре и представлении, то такой подход требует больших затрат на реализацию. Также при большей наглядности логических языков, они распространены куда меньше, чем SQL, который знает почти что каждый.

Стоит отметить, что реальные анализаторы, использующие представление в виде базы данных, в основном, оперируют с логическими языками или с собственными расширениями SQL, позволяющими решать проблему зацикливания. Например, система CodeQuest[67] работает с Datalog, а ASTLOG[57] с языком Prolog.

1.1.5. Автоматное представление

Основное применение такого представления - анализ потока управления

программы. При таком представлении поведении порграммы описывается автоматом. Примером может служить инструмент BLAST [87]. В нем строится автомат потока управления (control-flow automat). Для каждой из функций программы, с состояниями связываются управляющие точки программы, а с переходами - опера-

ции. Для верификации из автомата строятся абстрактные деревья достижимости (ART), объединяющие переходы между состояниями различных автоматов для функций (при вызове одной из другой), а также связывающие с этими состояниями логические предикаты, описывающие с определенной долей абстракции состояние переменных. Такое представление является похожим на представление Static Single Assignment (SSA) [52], распространенное в области компиляции. Для примера из листинга 1 подобный автомат будет выглядеть как показано на рисунке 8.

Рисунок 8. Пример представления исходного кода в виде графа автомата Деревья строятся по итерациям в соответствии с алгоритмом уточнения абстракции по контр-примерам - counterexample-guided abstraction refinement (CEGAR). Также инструмент BLAST также позволяет выполнять генерацию тестовых наборов данных (test-case), позволяющих сформировать ряд таких наборов, которые в сумме позволят проверить попадание во все возможные состояния функций (вернее их CFA). Инструмент успешно завершает работу далеко не всегда - это во многом зависит от конкретного случая. Зачастую, это связано с ограниченностью ресурсов.

int с=2

1.1.6. Прочие представления

Существует ряд уникальных решений, которые отличаются от всех вышеперечисленных, однако, во многом с ними схожи. Самый яркий представитель — популярный анализатор FindBugs [61] для языка Java. Он использует Java байт-код в качестве промежуточного представления. Такое представление во многом очень похоже на классическое AST, так как, фактически, Java байт-код сам по себе является языком и анализируется схожими средствами, как и AST (с помощью обхода всего дерева и анализа узлов). Существуют также статические анализаторы скомпилированного бинарного кода [34].

Список литературы диссертационного исследования кандидат наук Зубов Максим Валерьевич, 2016 год

СПИСОК ЛИТЕРАТУРЫ

1. Аветисян, А.И. Двухэтапная компиляция для оптимизации и развертывания программ на языках общего назначения / А.И. Аветисян // Труды Института системного программирования РАН. - 2012. - Т. 22. - С. 11-17.

2. Аветисян, А.И. Технологии статического и динамического анализа уязвимостей программного обеспечения / А.И. Аветисян, А.А. Белеванцев, И.И. Чукляев // Вопросы кибербезопасности. - 2014. - Т. 14, № 3. - С. 20-28.

3. Автоматический синтез комментариев к программным кодам: перспективы развития и применения / А.Н. Пустыгин, А.И. Иванов, Ю.К. Язов, С.В. Соловьев // Программная инженерия. - 2012. - № 3. - С. 30-34.

4. Алгоритм построения МП-автомата по КС-грамматике [Электронный ресурс]. -Режим доступа: http://mathhelpplaneLcom/static.php?p=algoritm-postroyeniya-mp-avtomata-po-ks-grammatike, свободный (дата обращения 1 марта 2016)

5. Битнер, В.А. Построение универсального линеаризованного графа потока управления для использования в статическом анализе кода алгоритмов / В.А. Битнер, Н.В. Заборовский // Моделирование и анализ информационных систем.

- 2013. - Т. 20, № 2. - С. 166-177.

6. Буйневич, М.В. Модель машинного кода, специализированная для поиска уязвимостей / М.В. Буйневич, К.Е. Израилов, О.В. Щербаков // Вестник Воронежского института ГПС МЧС России. - 2014. - Т. 11, № 2. - С. 46-51.

7. Буч, Г. Язык UML. Руководство пользователя / Г. Буч, Д. Рамбо, А. Джекобсон.

- СПБ.: Питер, 2004. - 432 с.

8. Гавриленко, С.Ю. Использование языка XML для промежуточного представления программы / С.Ю. Гавриленко, П.А. Шитьков // Вестник Национального технического университета Харьковский политехнический институт. Серия: Информатика и моделирование. - 2008. - № 24. - С. 19-24.

9. Гнетов, Е.А. Использование численных методов расчетов в научных исследованиях / Е.А. Гнетов, Е.Н. Горохов, А.А. Маленов // Международный журнал экспериментального образования. - 2012. - № 9. - С. 46-47.

10. ГОСТ 19.701-90 Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения. — М.: Стандартинформ, 1992. — 24 с.

11. Гросс, М. Теория формальных грамматик / М. Гросс, А. Лантен. - М.: Мир, 1971. - 296 с.

12. Дейт, К. Введение в системы баз данных / К. Дейт. - М.: Вильямс, 2006. - 1328 с.

13. Дубов, Ю. А. Многокритериальные модели формирования и выбора вариантов систем / Ю.А. Дубов, С.И. Травкин, В.Н. Якимец. - М.: Наука, 1986. - 48 с.

14. Дюваль, П.М. Непрерывная интеграция: улучшение качества программного обеспечения и снижение риска / П.М. Дюваль, С.М. Матиас III, Э. Гловер. - М.: Вильямс, 2008. - 240 с.

15. Звездин, С.В. Проблемы измерения качества программного кода / С.В. Звездин // Вестник Южно-Уральского государственного университета. Серия: Компьютерные технологии, управление, радиоэлектроника. - 2010. - Т. 178, № 2. - С. 62-66.

16. Использование статического анализа для поиска уязвимостей и критических ошибок в исходном коде программ / А. Аветисян, А. Белеванцев, А. Бородин, В. Несов // Труды Института системного программирования РАН. - 2011. - Т. 21. - С. 23-38.

17. Использование StAX для обработки XML [Электронный ресурс]. - Режим доступа: http://www.ibm.com/developerworks/ru/library/x-stax1/, свободный (дата обращения 1 марта 2016)

18. Исследование систем автоматизации обнаружения дефектов в исходном коде программного обеспечения / В. М. Ицыксон, М. Ю. Моисеев, В. А. Цесько и др. // Научно-технические ведомости СПбГПУ. Информатика. Телекоммуникации. Управление. - 2008. - № 5. - С. 119-127.

19. Ицыксон, В. М. Автоматизация реинжиниринга программного обеспечения при портировании на новые библиотеки с помощью частичных спецификаций / В. М. Ицыксон // Информационно-управляющие системы. - 2012. - № 2. - С. 31-38.

20. Карпов, А.Н. Как статический анализ дополняет TDD [Электронный ресурс]. -Режим доступа: http://www.viva64.eom/ru/a/0080/, свободный (дата обращения 1 марта 2016)

21. Касьянов, В.Н. Визуализация информации на основе графовых моделей / В.Н. Касьянов // Доклады Седьмой Международной Азиатской школы-семинара «Проблемы сложных систем». - Узбекистан, Ташкент: Ташкентский Университет Информационных Технологий, 2011. - С. 50-55.

22. Кнут, Д. Искусство программирования. Том 1. Основные алгоритмы / Д. Кнут.

- М.: Вильямс, 2006. - 720 с.

23. Компиляторы: принципы, технологии и инструментарий / А. Ахо, М. Лам, Р. Сети, Д. Ульман. - М.: Вильямс, 2010. - 1184 с.

24. Композиционный подход к построению программных приложений визуализации / В.А. Семенов, Е.В. Алексеева, С.В. Морозов, О.А. Тарлапан // Труды Института системного программирования РАН. - 2004. - Т. 5. - С. 175213.

25. Кулик, А.С. Модели и алгоритмы поиска ошибок при решении задач с использованием компьютерных средств обучения / А.С. Кулик, О.А. Пищухина, А.Ю. Ключок // Радюелектрошка, шформатика, управлшня. - 2012.

- Т. 26, № 1. - С. 59-63.

26. Ледовских, И.Н. Подход к восстановлению потока управления запутанной программы / И.Н. Ледовских, М.Г. Бакулин // Труды Института системного программирования РАН. - 2012. - № 22. - С. 153-168.

27. Литвинов, В.В. Формальная верификация диаграммы классов / В.В. Литвинов, И.В. Богдан // Математические машины и системы. - 2013. - № 2. - С. 41-47.

28. Моисеев, А.Н. Разработка объектно-ориентированной модели системы иммитационного моделирования процессов массового обслуживания / А.Н. Моисеев, М.В. Синяков // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2010. - № 1. - С. 89-93.

29. Никонов, О.Я. Оценка точности вычислений специальных функций при разработке компьютерных программ математического моделирования / О.Я. Никонов, О.В. Мнушка, В.Н. Савченко // Вестник Национального технического университета Харьковский политехнический институт. Серия: Информатика и моделирование. - 2011. - № 17. - С. 115-120.

30. Новиков, Е.М. Использование аспектно-ориентированного программирования для выполнения запросов по исходному коду программ / Е.М. Новиков, А.В. Хорошилов // Труды Института системного программирования РАН. - 2012. -Т. 23. - С. 371-384.

31. Новиков, Ф.А. Автоматный метод определения проблемно-ориентированных языков / Ф.А. Новиков, У.Н. Тихонова // Информационно-управляющие системы. - 2009. - № 6. - С. 34-40.

32. Обзор инструментов статической верификации Си программ в применении к драйверам устройств операционной системы Linux / М.У. Мандрыкин, В.С. Мутилин, Е.М. Новиков, А.В. Хорошилов // Труды Института системного программирования РАН. - 2012. - Т. 22. - С. 293-326.

33. Окишев, А.С. Формирование и исследование численных методов оптимизации, учитывающих высшие производные / А.С. Окишев // Омский научный вестник. - 2010. - Т. 93, № 3. - С. 20-25.

34. Падарян, В.А. Методы и программные средства, поддерживающие комбинированный анализ бинарного кода / В.А. Падарян, А.И. Гетьман, М.А. Соловьев // Труды Института системного программирования РАН. - 2014. - Т. 26, № 1. - С. 251-276.

35. Приемы объектно-ориентированного проек-тирования. Паттерны проектирования / Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес. - СПБ.: Питер, 2007. - 366 с.

36. Романов, В.Ю. Визуализация для измерения и рефакторинга программного обеспечения / В.Ю. Романов // International Journal of Open Information Technologies. - 2013. - Т. 1, № 9. - С. 1-10.

37. Россум, Г. Язык программирования Python / Г.Россум, Ф.Л.Дж.Дрейк, Д.С.Откидач. - СпБ.: АНО «Институт логики». Невский Диалект, 2001. - 454 с.

38. Савицкий, В.О. Инкрементальный анализ исходного кода на языках C/C++ / В.О. Савицкий, Д.В. Сидоров // Труды Института системного программирования РАН. - 2012. - № 22. - С. 119-130.

39. Стандартная общественная лицензия GNU (GPL), версия 2 [Электронный ресурс]. - Режим доступа: http://www.gnu.Org/licenses/gpl-2.0.html, свободный (дата обращения 1 марта 2016)

40. Фаулер, М. Рефакторинг. Улучшение существующего кода / М. Фаулер. -СпБ.: Символ-Плюс, 2003. - 268 с.

41. Хопкрофт, Дж. Введение в теорию автоматов, языков и вычислений / Дж. Хопкрофт, Р. Мотвани, Дж. Ульман. - М.: Вильямс, 2008. - 528 с.

42. Чернов, А.В. Анализ запутывающих преобразований программ / А.В. Чернов // Труды Института системного программирования РАН. - 2002. - Т. 3. - С. 7-38.

43. Язов, Ю.К. Методический подход к оцениванию эффективности ложных информационных систем / Ю.К. Язов, А.Л. Сердечный, И.А. Шаров // Вопросы кибербезопасности. - 2014. - № 1. - С. 55-60.

44. Control Flow - GNU Compiler Collection (GCC) Internals [Электронный ресурс].

- Режим доступа: http://gcc.gnu.org/onlinedocs/gccint/Control-Flow.html, свободный (дата обращения 1 марта 2016)

45. Ali, K. Application-Only call graph construction / K. Ali, O. Lhotak // Proceedings of the 26th European conference on Object-Oriented Programming. - Berlin: Springer, 2012. - С. 688-712.

46. Allen, F. Control flow analysis / F. Allen // ACM SIGPLAN Notices - Proceedings of a symposium on Compiler optimization. - 1970. - № 5. - С. 1-19.

47. ANother Tool for Language Recognition [Электронный ресурс]. - Режим доступа: http://www.antlr.org/, свободный (дата обращения 1 марта 2016)

48. Avdagic, Z. Code Evaluation Using Fuzzy Logic / Z. Avdagic, D. Boskovic, A. Delic // Proceedings of the 9th WSEAS International Conference on Fuzzy Systems.

- Wisconsin, USA: WSEAS, 2008. - С. 20-25.

49. Ayewah, N. Null dereference analysis in practice / N. Ayewah, W. Pugh // Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering. - NY, USA: ACM Ney York, 2010. - С. 65-72.

50. Bazaar [Электронный ресурс]. - Режим доступа: http://bazaar.canonical.com, свободный (дата обращения 1 марта 2016)

51. Beyer, D. The software model checker Blast: Applications to software engineering / D. Beyer, T. A.Henzinger, R. Jhala // International Journal on Software Tools for Technology Transfer. - 2007. - № 9. - С. 505-525.

52. Bilardi, G. Algorithms for computing the static single assignment form / G. Bilardi, K. Pingali // Journal of the ACM. - 2003. - Т. 50, № 3. - С. 375-425.

53. Bjorklund, H. Incremental XPath evaluation / H. Bjorklund, W. Gelade, W. Martens // ACM Transactions on Database Systems. - 2010. - № 35. - С. 162-173.

54. Carpenter, J. ROSE: Making compiler technology more accessible / J. Carpenter // Science & Technology Review. - 2009. - № 6. - С. 12-13.

55. Checkstyle - Checkstyle 6.0 [Электронный ресурс]. - Режим доступа: checkstyle.sourceforge.net/index.html, свободный (дата обращения 1 марта 2016)

56. Cousot, P. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints / P. Cousot, R. Cousot // Conference Record of theFourth ACM Symposium on Principles of Programming Languages, Los Angeles. - NY, USA: ACM New York, 1977. - С. 238-252.

57. Crew, R. ASTLOG: A Language for Examining Abstract Syntax Trees / R. Crew. -Redmond, WA, USA: Microsoft Research, 1997. - 15 с.

58. Csu-code-analysis GitHub [Электронный ресурс]. - Режим доступа: https://github.com/exbluesbreaker/csu-code-analysis, свободный (дата обращения 1 марта 2016)

59. Czeranski, J. Data Exchange in Bauhaus / J.Czeranski, T.Eisenbarth, R. Koschke // Proceedings of the Seventh Working Conference on Reverse Engineering. -Washington, USA: IEEE Computer Society Press, 2000. - С. 293-299.

60. Damns, D. Orion: high-precision methods for static error analysis of c and c++ programs / D. Damns, K. Namjoshi // FMC0'05 Proceedings of the 4th international conference on Formal Methods for Components and Objects. - Berlin: Springer, 2006. - С. 138-160.

61. FindBugs. finding bugs in Java Programs [Электронный ресурс]. - Режим доступа: http://findbugs.sourceforge.net/, свободный (дата обращения 1 марта 2016)

62. Geneves, P. Eliminating deadcodefrom XQuery programs / P. Geneves, N. Layaida // Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering. - NY, USA: ACM New York, 2010. - С. 305-306.

63. Gold, R. Control flow graphs and code coverage / R. Gold // International Journal of Applied Mathematics and Computer Science. - 2010. - № 20. - С. 739-749.

64. Grove, D. / D. Grove, C. Chambers // ACM Transactions on Programming Languages and Systems. - 2001. - Т. 23, № 6. - С. 685-746.

65. Gulwani, S. SPEED: precise and efficient static estimation of program computational complexity / S. Gulwani, K. Mehra, T. Chilimbi // ACM SIGPLAN Notices. - 2009. - № 44. - С. 127-139.

66. Gupta, S. Coordinated parallelizing compiler optimizations and highlevelsynthesis / S.Gupta, R. Gupta, N. Dutt // ACM Transactions on Design Automation of Electronic Systems. - 2004. - № 9. - С. 441-470.

67. Hajiyev, E. CodeQuest: Scalable Source Code Queries with Datalog / E. Hajiyev, V. Verbaere, O. de Moor // 20th European Conference. - Germany, Berlin: Springer, 2006. - С. 2-27.

68. Holkner, A. Evaluating the dynamic behaviour of Python applications / A. Holkner, J. Harland // Computer Science. - 2009. - № 91. - С. 19-28.

69. Index (Logilab.org) [Электронный ресурс]. - Режим доступа: http://www.logilab.org, свободный (дата обращения 1 марта 2016)

70. Jarzabek, S. Design of Flexible Static Program Analyzers with PQL / S. Jarzabek // IEEE Transactions on Software Engineering. - 1998. - № 24. - С. 197-215.

71. JAXB Reference Implementation [Электронный ресурс]. - Режим доступа: https://jaxb.java.net/, свободный (дата обращения 1 марта 2016)

72. Kang, B. Fast malware family detection method using control flow graphs / B. Kang, H.S. Kim,T. Kim // Proceedings of the 2011 ACM Symposium on Research in Applied Computation. - NY, USA: ACM New York, 2011. - С. 287-292.

73. Kim, S.M. DOM tree browsing of a very large XML document: Design and implementation / S.M. Kim, S.I. Yoo // Journal of Systems and Software. - 2009. -№ 82. - С. 1843-1858.

74. Kodaganallur, V. Incorporating Language Processing into Java Applications: A JavaCC Tutorial / V. Kodaganallur // IEEE Software. - 2004. - № 21. - С. 70-77.

75. Koschke, R. An intermediate representation for integrating reverse engineering analyses / R. Koschke, J. Girard, M. Wurthner // Proceedings of the Working Conference on Reverse Engineering. - Washington, USA: IEEE Computer Society Press, 1998. - С. 241-250.

76. Koschke, R. On Dynamic Feature Location / R. Koschke, J. Quante // International Conference on Automated Software Engineering. - NY, USA: ACM Ney York, 2005. - С. 86-95.

77. Kostakis, O. Classy: fast clustering streams of call-graphs / O. Kostakis // Data Mining and Knowledge Discovery. - 2014. - Т. 28, № 5. - С. 1554-1585.

78. Lerthathairat, P. An Approach for Source Code Classification Using Software Metrics and Fuzzy Logic to Improve Code Quality with Refactoring Techniques / P. Lerthathairat, N. Prompoon // Second International Conference. - Pahang, Malaysia: Springer, 2011. - С. 478-492.

79. Leviene, J. Flex & Bison / J. Leviene. - CA, USA: O'Reilly, 2009. - 294 с.

80. Linton, M. Queries and Views of Programs Using a Relational Database System / M. Linton. - CA, USA: EECS Department, 1983. - 102 с.

81. lxml - XML and HTML with Python [Электронный ресурс]. - Режим доступа: http://lxml.de/, свободный (дата обращения 1 марта 2016)

82. Mason, T. Lex & yacc / T. Mason, D. Brown. - CA, USA: O'Reilly, 1990. - 216 с.

83. McLaughlin, B. Java and XML data binding / B. McLaughlin. - CA, USA: O'Reilly, 2002. - 218 с.

84. Midtgaard, J. Control-flow analysis of function calls and returns by abstract interpretation / J. Midtgaard, T. Jensen // Proceedings of the 14th ACM SIGPLAN international conference on Functional programming. - NY, USA: ACM New York, 2009. - С. 287-298.

85. Modeling and visualizing object-oriented programs with Codecharts / A. H. Eden, E. Gasparis, J. Nicholson, R. Kazman // Formal Methods in System Design. - 2013. -№ 43. - С. 1-28.

86. Moreno, E.D. Architectural impact of the SVG-based graphical components in web applications / E.D. Moreno, J.I.F. de Oliveira // Computer Standards & Interfaces. -2009. - № 31. - С. 1150-1157.

87. MTC (Models and Theory of Computation): BLAST Project [Электронный ресурс]. - Режим доступа: , свободный (дата обращения 1 марта 2016)

88. NumPy [Электронный ресурс]. - Режим доступа: www.numpy.org, свободный (дата обращения 1 марта 2016)

89. OpenJDK [Электронный ресурс]. - Режим доступа: http://openjdk.java.net/, свободный (дата обращения 1 марта 2016)

90. PVS-Studio: Статический анализ кода для C, C++ и C# [Электронный ресурс].

- Режим доступа: http://www.viva64.com/ru/pvs-studio/, свободный (дата обращения 1 марта 2016)

91. PyDot, a Python interface to Graphviz's Dot language [Электронный ресурс]. -Режим доступа: https://code.google.com/pZpydot/, свободный (дата обращения 15 декабря 2014)

92. Pylint - code analysis for Python [Электронный ресурс]. - Режим доступа: www.pylint.org/, свободный (дата обращения 11 ноября 2014)

93. Quinlan, D. Source Code and Binary Analysis of Software Defects / D. Quinlan, T. Panas // Annual Workshop on Cyber Security and Information Intelligence Research.

- 2009. - № 5. - С. 40-44.

94. Raza, A. Bauhaus { a Tool Suite for Program Analysisand Reverse Engineering / A. Raza, G. Vogel, E. Plodereder // Reliable Software Technologies. Ada-Europe. -2006. - № 11. - С. 71-82.

95. Re-engineering C++ component models via automatic program transformation / R. Akers, I. Baxter, M. Mechlich, B. Ellis, K. Luecke // Information and Software Technology. - 2007. - Т. 49, № 3. - С. 275-291.

96. Riesco, M. Using Graphviz as a Low-cost Option to Facilitate the Understanding of Unix Process System Calls / M. Riesco, M.D. Fondon, D. Alvarez // Electronic Notes in Theoretical Computer Science. - 2009. - № 224. - С. 89-95.

97. Shivers, O. Pushdown flow analysis of first-class control / O. Shivers, D. Vardoulakis // Proceedings of the 16th ACM SIGPLAN international conference on Functional programming. - NY, USA: ACM Ney York, 2011. - С. 69-80.

98. Spinellis, D. Drawing Tools / D. Spinellis // IEEE Software. - 2009. - № 26. - С. 12-13.

99. Steiner, J. Intermediate representations in imperative compilers: A survey / J. Steiner, D. Watson // ACM Computing Surveys. - 2013. - № 45. - С. 37-49.

100. Technical. Semmle [Электронный ресурс]. - Режим доступа: http://semmle.com/solutions/technical/, свободный (дата обращения 1 марта 2016)

101. The DOT Language | Graphviz GraphVisualization Software [Электронный ресурс]. - Режим доступа: http://www.graphviz.org/content/dotlanguage, свободный (дата обращения 1 марта 2016)

102. Twisted [Электронный ресурс]. - Режим доступа: https://twistedmatrix.com, свободный (дата обращения 1 марта 2016)

103. Unger, S. Handling Irreducible Loops: Optimized Node Splitting vs. DJGraphs / S. Unger, F.Mueller // ACM Transactions on Programming Languages. - 2002. - № 4. - С. 299-333.

104. Utz, W. Capturing Learning Activities in Heterogeneous Environments: A ModelBased Approach for Data Marshalling / W. Utz, P. Reimann, D. Karagiannis // Proceedings of the 2014 IEEE 14th International Conference on Advanced Learning Technologies. - Washington DC, USA: IEEE Computer Society, 2014. - С. 624-626.

105. Webb, J. MALPAS—an automatic static analysis tool for software validation and verification / J. Webb // Edited papers presented at the 1st International Conference on Reliability and robustness of engineering software. - Amsterdam: Elsevier Science Publishers, 1987. - С. 67-75.

106. XML Schema [Электронный ресурс]. - Режим доступа: www.w3.org/XML/Schema, свободный (дата обращения 1 марта 2016)

107. XML. Работа с XML / Д. Хантер, Д. Рафтер, Д. Фаусетт, Э. ван дер Влист, и др.. - М.: Диалектика, 2009. - 1344 с.

108. Xue, J. Partial dead code elimination on predicated code regions / J. Xue, Q. Cai, L. Gao // Software—Practice & Experience. - 2006. - № 36. - С. 1655-1685.

Публикации автора диссертации в журналах, входящих в Перечень ведущих периодических изданий, рекомендованных ВАК РФ

109. Зубов, М.В. Анализ путей исполнения программ по исходному коду с использованием универсальных промежуточных представлений / М.В. Зубов, А.Н. Пустыгин // Известия Юго-Западного государственного университета. -2015. - Т. 61, № 4. - С. 12-19.

110. Зубов, М.В. Использование абстрактного цифрового автомата для получения универсального промежуточного представления исходного кода программ / М.В. Зубов, А.Н. Пустыгин // Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика. - 2015. - № 4. - С. 57-65.

111. Зубов, М.В. Математическое моделирование универсальных многоуровневых промежуточных представлений для статического анализа исходного кода / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Доклады ТУСУРа. - 2014. - Т. 33, № 3. -С. 94-99.

112. Зубов, М.В. Получение типов данных в языках с динамичексой типизацией для статического анализа исходного кода с помощью универсального классового представления / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Вестник АСТУ. - 2013. - № 1. - С. 66-74.

113. Зубов, М.В. Применение пороговых функций для извлечения информации о типах данных при получении промежуточных представлений текстов программ для языков с динамической типизацией / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Инфокоммуникационные технологии. - 2014. - Т. 12, № 4. - С. 5156.

114. Зубов, М.В. Применение универсальных промежуточных представлений для статического анализа исходного программного кода / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Доклады ТУСУР. - 2013. - Т. 27, № 1. - С. 64-68.

115. Зубов, М.В. Численное моделирование анализа исходного кода с использованием промежуточных представлений / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Вестник АГТУ. - 2014. - № 4. - С. 55-66.

116. К вопросу об автоматическом комментировании на естественном языке исходных текстов программ / М.В. Зубов, О.А. Машин, А.Н. Пустыгин, Ю.К. Язов // Программная инженерия. - 2013. - №11. - С. 17-21.

Другие публикации автора

117. Зубов, М.В. Выделение типов в универсальном классовом представлении для статическгого анализа исходного кода / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Восьмая конференция «Свободное программное обеспечение в высшей школе». Тезисы докладов. - М.: Альт-Линукс, 2013. - С. 53-58.

118. Зубов, М.В. Краткий анализ и исследование помежуточных представлений исходного текста программ / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Суперкомпьютерные технологии и открытое программное обеспечение. - 2013. - №1. - С. 45-53.

119. Зубов, М.В. Подходы к статическому анализу открытого исходного кода / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Сборник материалов Восьмой Международной конференции разработчиков и пользователей свободного программного обеспечения LVEE. - Беларусь, Брест: Альтернатива, 2012. - С. 36-40.

120. Зубов, М.В. Получение типов данных в динамических языках при статическом анализе / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Тверские интернет технологии. Научно-практическая конференция: Сборник трудов. -Тверь: ТвГУ, 2013. - С. 53-57.

121. Зубов, М.В. Построение универсального представления графа потока управления для статического анализа исходного кода / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Девятая конференция «Свободное программное обеспечение в высшей школе». - М.: Альт-Линукс, 2014. - С. 46-51.

122. Зубов, М.В. Прототипы построителей промежуточных представлений исходных текстов программ, основанные на компиляторах с открытым исходным кодом / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Седьмая конференция «Свободное программное обеспечение в высшей школе». - М.: Альт-Линукс, 2012. - С. 82-86.

123. Зубов, М.В. Сравнительный анализ существующих инструментов исследования программ по исходному коду / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Суперкомпьютерные технологии и открытое программное обеспечение. - 2013. - №1. - С. 37-44.

124. Зубов, М.В. Статический анализ ПО с помощью его промежуточных представлений и технологий с открытым исходным кодом / М.В. Зубов, А.Н. Пустыгин, Е.В. Старцев // Материалы второй научно-практической конференции FOSS LVIV 2012. - Украина, Львов: Львiв, 2012. - С. 165-168.

125. Свидетельство о государственной регистрации программ для ЭВМ № 2014663489. Генератор универсального классового промежуточного представления в формате XML из представления AST исходного текста на языке Java / М.В. Зубов, А.Н. Пустыгин. - Заявка № 2014663489; зарегистрирована в Реестре программ для ЭВМ 24.12.2014.

Список иллюстративного материала

Рисунок 1. Получение промежуточного представления из исходного кода.

с. 15.

Рисунок 2. Пример абстрактного синтаксического дерева разбора в виде графа. с. 17.

Рисунок 3. Схема базы данных для хранения промежуточного представления. с. 19.

Рисунок 4. Пример заполнения таблиц в базе данных, содержащей промежуточное представление. с. 20.

Рисунок 5. иМЬ-диаграмма простой иерархии из 4 классов. с. 21. Рисунок 6. Схема базы данных для хранения отношения иерархии классов.

с. 21.

Рисунок 7. Пример заполнения таблицы, хранящей иерархию наследования классов. с. 21.

Рисунок 8. Пример представления исходного кода в виде графа автомата .

с. 23.

Рисунок 9. Схема выполнения анализа при использовании универсальных представлений. с. 25.

Рисунок 10. Схема выполнения анализа при использовании частных представлений. с. 25.

Рисунок 11. Схематичное выполенение анализа а) над одним промежуточным представлением, б) над несколькими представлениями совместно. с. 28.

Рисунок 12. Представление кода в виде абстрактного дерева разбора. с. 33. Рисунок 13. Обобщенная модель промежуточного представления в виде дерева. с. 35.

Рисунок 14. Пример графа потока управления а) в классической модели, б) в расширенной с условными вершинами. с. 38.

Рисунок 15. Представление графа потока управления в виде дерева. с. 39.

Рисунок 16. Математическая модель графа потока управления в виде дерева, разделенного на уровни. с. 40.

Рисунок 17. Пример представление графа потока управления в виде предложенной модели. с. 42.

Рисунок 18. Схема абстрактного цифрового автомата для генерации промежуточного представления. с. 57.

Рисунок 20. UML-диаграмма классов генератора AST-XML для языка Java на основе препарата компилятора javac. с. 64.

Рисунок 21. Визуальный вид XML-схемы универсального представления потока управления. с. 66.

Рисунок 22. UML-диаграмма компонентов генератора представления UCFR для языка Java. с. 69.

Рисунок 23. UML-диаграмма, описывающая обработчик состояния автомата генератора промежуточного представления. с. 70.

Рисунок 26. UML-диаграмма компонентов реализованных анализаторов.. с.

84.

Рисунок 27. Зависимость количества "жадных" методов от порога для проектов jclassgen, jcfgen и pylint. с. 86.

Рисунок 28. Зависимость количества "жадных" методов от порога для проектов javac, numpy, logilab. с. 87.

Рисунок 29. Зависимость количества "жадных" методов от порога для проектов twisted и bazaar. с. 87.

Рисунок 30. График зависимости процента найденных методов от значения порога. с. 88.

Рисунок 31. Зависимость количества классов от порога для проектов jclassgen, jcfgen, javac, logilab, pylint, numpy. с. 90.

Рисунок 32. Зависимость количества классов от порога для проектов twisted и bazaar. с. 91.

Рисунок 33. График зависимости процента найденных классов от значения порога. с. 92.

Рисунок 24. Архитектура выполнения анализа "Контроль разделения ответственности" а) над универсальными представлениями б) над представлением AST языка Java. с. 72.

Рисунок 25. Графическая зависимость времени выполнения одного анализа от количества классов. с. 76.

Рисунок 34. UML-диаграмма компонентов утилиты визуализации представления графа потока управления. с. 94.

Рисунок 35. Пример результата визуализации потока управления. с. 94.

Рисунок 36. Пример наличия трассы в графе потока управления проекта. с.

97.

Рисунок 37. Модель графа вызовов из двух функций. с. 98.

Рисунок 38. Различные пути распространения потока управления в примере

. с. 99.

Рисунок 39. Блок-схема алгоритма извлечения путей распространения трассы. с. 100.

Рисунок 40. Пример визуализации двух функциональных блоков, между которыми существует трасса. с. 103.

Рисунок 41. Пример визуализации одной из трасс между двумя функциональными блоками. с. 104.

Рисунок 42. Пример визуализации одной из трасс между двумя функциональными блоками. с. 104.

Рисунок 43. Пример визуализации трассы в анализе поиска создаваемых объектов вдоль заданной трассы. с. 105.

Рисунок 44. Пример визуализации трассы в анализе поиска интересующих вызовов вдоль заданной трассы. с. 106.

Рисунок 45. Диаграмма значений метрики reachable по исследуемым проектам. с. 108.

Рисунок 46. Диаграмма значений функциональной компоненты по исследуемым проектам. с. 110.

Приложения

1. Фрагмент исходного кода программы получения промежуточного

пред ставления

Программа состоит из более чем 50 классов и 5000 строк исходного кода на языке Java. Имеет смысл указать наиболее интересные фрагменты этого кода, отвечающие за реализацию автоматного подхода. Это интерфейс IContext, описывающий основные операции, которые выполняются с объектом-состоянием; класс Con-textBase, отвечающий за базовую реализацию состояния и формирования магазинной памяти; класс ControlFlowContext, описывающий обработку участка потока управления.

Интерфейс ru.csu.stan.java.classgen.automaton.IContext: package ru.csu.stan.java.classgen.automaton;

import ru.csu.stan.java.classgen.handlers.NodeAttributes;

/**

* Состояние автомата обработчика AST.

* Описывает основные методы обработки узлов дерева разбора.

* Позволяет определить выходные данных по входым данным для текущего состояния.

*

* @param <T> public interface IContext<T> {

IContext<T> getPreviousState(String eventName); IContext<T> getNextState(IContext<T> context, String eventName); void processTag(String name, NodeAttributes attrs); void finish(String eventName); T getResultRoot();

}

Класс ru.csu.stan.java.cfg.automaton.base.ContextBase: package ru.csu.stan.java.cfg.automaton.base;

import java.util.Iterator;

import javax.xml.stream.events.Attribute;

import ru.csu.stan.java.cfg.jaxb.ObjectFactory;

import ru.csu.stan.java.cfg.jaxb.Project;

import ru.csu.stan.java.cfg.util.MethodRegistry;

import ru.csu.stan.java.classgen.automaton.IContext;

import ru.csu.stan.java.classgen.util.ImportRegistry;

import ru.csu.stan.java.classgen.util.PackageRegistry;

/**

* Базовый класс (состояние автомата).

* Описывает общие поля и методы для всех состояний.

*

*/

public abstract class ContextBase implements IContext<Project>{

private Project resultRoot;

private ContextBase previousState;

protected final static String NAME_ATTRIBUTE = "name";

private static ObjectFactory objectFactory = new ObjectFactory();

private MethodRegistry registry;

private ImportRegistry imports;

private PackageRegistry packages;

protected ContextBase(ContextBase previousState) { this.resultRoot = previousState.getResultRoot(); this.previousState = previousState; this.registry = previousState.getMethodRegistry(); this.imports = previousState.getImportRegistry(); this.packages = previousState.getPackageRegistry();

}

protected ContextBase(Project resultRoot, MethodRegistry registry, ImportRegistry imports, PackageRegistry packages){ this.resultRoot = resultRoot; this.previousState = null; this.registry = registry; this.imports = imports; this.packages = packages;

}

public ContextBase getUpperState() { return previousState;

}

@Override

public Project getResultRoot() { return resultRoot;

}

protected String getNameAttr(Iterator<Attribute> attrs){ String result = ""; while (attrs.hasNext()){

Attribute a = attrs.next();

if (NAME_ATTRIBUTE.equals(a.getName().toString())) return a.getValue();

}

return result;

}

protected String getAttribute(Iterator<Attribute> attrs, String attrName){

String result = ""; while (attrs.hasNext()){

Attribute a = attrs.next(); if (attrName.equals(a.getName().toString())) return a.getValue();

}

return result;

}

protected static ObjectFactory getObjectFactory(){ return objectFactory;

}

public MethodRegistry getMethodRegistry() { return registry;

}

public ImportRegistry getImportRegistry(){ return imports;

}

public PackageRegistry getPackageRegistry(){ return packages;

}

}

Класс ru.csu.stan.java.cfg.automaton.ControlFlowContext: package ru.csu.stan.java.cfg.automaton; import java.math.BigInteger;

import ru.csu.stan.java.cfg.automaton.base.ContextBase; import ru.csu.stan.java.cfg.automaton.base.FlowCursor; import ru.csu.stan.java.cfg.automaton.base.IClassInsidePart; import ru.csu.stan.java.cfg.jaxb.Block; import ru.csu.stan.java.cfg.jaxb.Flow;

import ru.csu.stan.java.cfg.jaxb.Method; import ru.csu.stan.java.cfg.jaxb.Project; import ru.csu.stan.java.cfg.util.scope.VariableScope; import ru.csu.stan.java.classgen.automaton.IContext; import ru.csu.stan.java.classgen.handlers.NodeAttributes; import ru.csu.stan.java.classgen.util.CompilationUnit;

public class ControlFlowContext extends ContextBase implements IclassInsidePart{

private Method method;

private final FlowCursor cursor;

private CompilationUnit compilationUnit;

private Block block;

private String startTag = "";

private VariableScope scope = new VariableScope();

public ControlFlowContext(ContextBase previousState, Method method, final FlowCursor cursor, CompilationUnit compilationUnit){ super(previousState); this.method = method; this.cursor = cursor; this.compilationUnit = compilationUnit;

}

@Override

public IContext<Project> getPreviousState(String eventName){ if ("block".equals(eventName))

return getUpperState(); if (startTag.equals(eventName))

return getUpperState(); return this;

}

@Override

public IContext<Project> getNextState(IContext<Project> context, String eventName){

if ("class".equals(eventName))

return new ClassContext(this, compilationUnit); if ("if".equals(eventName)){ block = null;

return new IfContext(this, cursor, compilationUnit,

method);

}

if ("while_loop".equals(eventName) || "do_while_loop".equals(eventName)){ block = null;

return new WhileContext(this, cursor, compilationUnit,

method);

}

if ("for_loop".equals(eventName) || "enhanced_for_loop".equals(eventName)){ block = null;

return new ForContext(this, cursor, compilationUnit,

method);

}

if ("try".equals(eventName)){ block = null;

return new TryCatchContext(this, cursor, compilatio-

nUnit, method); }

if ("method_invocation".equals(eventName)){

return new MethodInvocationContext(this, block, get-

ClassName(), compilationUnit); }

if ("new_class".equals(eventName)){

return new NewClassContext(this, block, getClassName(),

compilationUnit); }

if ("variable".equals(eventName))

return new VariableContext(this, scope, block, compilationUnit);

return this;

}

@Override

public void processTag(String name, NodeAttributes attrs){ if (startTag == null || "".equals(startTag))

startTag = name; if (block == null && isNotOpeningTag(name)){ makeFlowsToCurrent();

block = getObjectFactory().createBlock(); block.setId(BigInteger.valueOf(cursor.getCurrentId())); if (attrs.isAttributeExist(NodeAttributes.LINE_AT-

TRIBUTE))

block.setFromlineno(BigInteger.valueOf(attrs.get-IntAttribute(NodeAttributes.LINE_ATTRIBUTE))); if

(attrs.isAttributeExist(NodeAttributes.COL_ATTRIBUTE))

block.setColOffset(BigInteger.valueOf(attrs.get-IntAttribute(NodeAttributes.COL_ATTRIBUTE)));

method.getTryExceptOrTryFinallyOrWith().add(block); cursor.clearParentIds(); cursor.addParentId(cursor.getCurrentId()); cursor.incrementCurrentId();

}

if ("return".equals(name)){ cursor.clearParentIds();

cursor.addParentId(-1 * block.getId().intValue());

}

if ("throw".equals(name)){ cursor.clearParentIds();

cursor.addParentId(-1 * block.getId().intValue());

}

}

private void makeFlowsToCurrent(){

for (Integer parent: cursor.getParentIds()){ if (parent.intValue() > 0){

Flow flow = getObjectFactory().createFlow();

flow.setFromId(BigInteger.valueOf( parent.longValue()));

flow.setToId(cursor.getCurrentIdBigInteger()); method.getTryExceptOrTryFinallyOrWith().add(flow);

}

}

}

@Override

public void finish(String eventName){

if ("block".equals(eventName) || startTag.equals(eventName))

{

this.scope.setName(method.getName()); this.scope.setParentScope(getVariableScope());

}

}

private boolean isNotOpeningTag(String tag){

return !("block".equals(tag) || "body".equals(tag) || "node-name.statements".equals(tag) || "then_part".equals(tag) || "else_part".equals(tag) || "finally".equals(tag) ||

"catch".equals(tag) || "modifier".equals(tag)); }

@Override

public String getClassName() {

return findParentClassNameHolder().getClassName();

}

@Override

public int getNextInnerCount() {

return findParentClassNameHolder().getNextInnerCount();

}

private IClassInsidePart findParentClassNameHolder(){ ContextBase ctx = this.getUpperState();

while (!(ctx instanceof IClassInsidePart) && ctx != null)

ctx = ctx.getUpperState(); return (IClassInsidePart) ctx;

}

@Override

public VariableScope getVariableScope() {

return findParentClassNameHolder().getVariableScope();

}

}