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

Содержание к диссертации

Введение

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

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

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

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

ГЛАВА 2. Модель промежуточных представлений 32

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

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

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

ГЛАВА 3. Реализация и тестирование генераторов представлений 59

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

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

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

ГЛАВА 4. Реализация, тестирование и оценка эффективности анализаторов 76

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

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

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

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

Заключение 110

Список сокращений и условных обозначений 112

Список литературы 113

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

• Идеи развития представлений
• Автоматная модель генератора промежуточных представлений
• Оценка эффективности использования промежуточных представлений
• Поиск оптимальных входных величин для анализаторов

Введение к работе

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

Большинство анализаторов делают упор на поиск ошибок, специфичных для конкретного языка программирования. Например, популярные анализаторы FindBugs и CheckStyle для Java или PVS Studio для C/C++ узко специализированы именно на ошибках, что показано в работах Н. Айваха (N. Ayewah) и А.Н. Карпова. Такие анализаторы не могут быть расширены или применены где-то кроме их целевого языка. Из такой ситуации следует, что область построения модели для анализа развита недостаточно. Многие просто используют дерево разбора парсера, как наиболее изученную модель в области компиляции, в качестве промежуточного представления — набора машинных данных, семантически эквивалентных исходному коду, над которыми выполняется анализ.

На сегодняшний день существуют научные работы, описывающие использование различных промежуточных представлений. В основном, это труды зарубежных авторов: М. Линтона (M. Linton), Р. Крю (R. Crew), Е. Хаджиева (E. Hajiyev), Д. Бэйера (D. Beyer), С. Джарзабэка (S. Jarzabek). Например, в Omega предлагается использовать реляционные базы данных, в ASTLOG – базу знаний на языке Prolog, а в BLAST – конечный автомат. На практике, в основном, распространенные анализаторы используют AST, что может осложнять некоторые цели анализа, или делать другие неэффективными.

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

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

2 терес. В качестве средства исследования и извлечения знаний из такого программного обеспечения может выступать статический анализ. Извлечение информации и реверс-инжениринг исследуются в работах Р. Коцке (R. Koschke), В.М. Ицыксона, Ю.К. Язова.

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

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

Среди исследований, посвященных анализу потока управления программы, следует выделить работы О. Шиверса (O. Shivers), В.А. Битнера и А.В. Чернова. Эти работы в основном направлены на использование графа потока управления при оптимизации или анализе алгоритмов. Кроме того, стоит выделить исследователей, работы которых посвящены анализу графа вызовов программ, – К. Али (K. Ali), Д. Гроува (D. Grove), О. Костакиса (O. Kostakis).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 ного обеспечения, базирующегося на предложенных моделях и алгоритмах и использованием математического аппарата, а также результатами апробации и внедрения в процесс разработки в компании ЗАО «Нау-Сервис».

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

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

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

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

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

Восьмая международная конференция «Linux Vacation / Eastern Europe» – Республика Беларусь, г. Гродно, 2012 г.;

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

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

Семинары кафедры компьютерной безопасности и прикладной алгебры ЧелГУ — г. Челябинск, 2014, 2016 гг.;

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

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

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

Публикации по теме диссертации

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

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

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

Структура и объем диссертации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Начальному состоянию всегда соответствует обработка проекта целиком, то есть можно считать, что s0 =s11. Когда закончится обработка всех данных, автомат также должен вернуться в состояние s11, которое можно считать конечным. Однако, нахождение автомата в состоянии s11 не показывает, что он завершил работу. Работу он завершает, когда кончается поток входных сигналов.

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

Как видно, состояния s5, s10 и s14 не имеют переходов в новые состояния. Переход из них возможен только при снятии их с вершины стека. Эти состояния связаны с обработкой одиночных идентификаторов типов, пакетов или импортов. Из-за этого они влияют только на выходные данные.

На выходе автомата будем получать поддеревья универсальных многоуровневых представлений вида и,j=(v, US,- ;, I,- ;) . По аналогии со входными сигналами, на выходе будем получать сигналы, состоящие из узлов нового представления, его листьев (характеристик) и признака е . Возможна ситуация, когда на выходе мы имеем не все листья, а лишь часть. В этом случае остальные необходимые листья будут получены в следующих тактах работы автомата.

Структура выходного сигнала - y={v,ItJ,e) , где ує - выходной сигнал, veV - узел получаемого представления, Itj It - некоторое подмножество листьев узла, которые можно выдать в данный момент, е - символ перехода к родительскому узлу. Возможно, что Iij=Ii .

В рассматриваемом универсальном представлении потока управления UCFR множество узлов представления V состоит из следующих элементов:

Так как рассматриваемый генератор представления используется для языка Java, то он не будет выдавать на выходе узлы v2 и v11, потому что в Java нет соответствующих или похожих конструкций. Это объектно-ориентированный язык, и в нем нельзя определить функцию вне класса, все функции являются методами. Конструкций, работающих как with, например, в языке Python, также нет.

Узлы v13 и v14 служат для характеристики узла v12. Они описывают тип вызова. Direct-вызов v13 используется, когда метод или функция вызваны напрямую, например, getValue(). В Java не существует функций отдельно от класса, так что такой вызов всегда будет адресован экземпляру текущего класса или же самому классу (если вызов статический). Если вызов метода происходил с помощью обращения через точку к какой-либо переменной, параметру или полю, тогда используется узел v14, а такой вызов называется getattr. Например, foo.doSomething(). Множество листьев для узлов представления будет состоять из следующих: name - имя (для метода) class - имя класса, которому принадлежит метод id - идентификатор блока кода или управляющей конструкции from_id - идентификатор блока, от которого идет переход to_id - идентификатор блока, к которому идет переход line - строка в коде col - позиция в строке в коде У каждого выходного сигнала yY может отсутствовать или присутствовать различная часть из тройки. Для описания выходных сигналов, генерируемых автоматом, воспользуемся таблицей 4.

В этой главе были формализованы модели промежуточных представлений как в универсальном виде, так и для конкретного представления потока управления. Эта модель позволяет описывать поток управления на многих современных распространенных языках программирования (Java, Python, C++, PHP). Модель была приведена к виду дерева, что дает возможность ее легко обрабатывать и сохранять в различные форматы.

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

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

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

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

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

В качестве оценки эффективности можно воспользоваться критерием быстродействия [65]. В качестве критерия быстродействия можно выбрать время работы утилиты-анализатора. Согласно требованиям к представлениям, анализ должен выполняться достаточно быстро. Для такой оценки будет недостаточно просто измерить время работы анализатора, необходимо количественное сравнение с другой величиной. Ей может являться время выполнения такого же или схожего по алгоритму или сложности анализа на других исходных данных.

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

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

Для практической проверки необходимо было провести численное моделирование скорости анализа универсальных представлений и AST аналогично [29]. Для этого, в свою очередь, необходимо было реализовать один из анализаторов на AST помимо новых представлений. Был выбран анализатор «Контроль разделения ответственности»(BigClassAnalyzer), выполняющий поиск классов, ответственность которых слишком высока. Этот анализатор позволяет выполнить рефакто-ринг таких классов [40]. Он был реализован в двух версиях: на AST и на совместном использовании собственных представлений (рисунок 24).

Для более точного подсчета временных оценок необходимо собирать статистические данные на большом количестве запусков утилит, чтобы исключить случайную составляющую. Кроме того, для исследования роста времени анализа необходимо анализировать несколько проектов. Для имитационного моделирования [28] использовались собственные разработки, выполненные в рамках диссертационной работы [58], и открытый компилятор языка Java из пакета OpenJDK [89]. На звания проектов и их основные характеристики показаны в таблице 6.

Можно теоретически оценить быстродействие на примере небольшого класса – ru.csu.stan.java.classgen.util. ClassIdGenerator из собственного кода и класса, который перегружен ответственностью, – ru.csu.stan.java.classgen.automaton. ClassContext. AST для первого класса содержит 195 узлов, из них 134 приходится на методы. Классовое представление содержит 33 узла, а поток управления – 47. То есть для анализа AST понадобится обойти 195 + 134 = 329 узлов, а для высокоуровневых представлений – 33 + 47 = 80, что в 4 раза меньше. AST для второго класса содержит 3352 узла, из них – 3015 приходятся на методы, UCR – 171, а UCFR – 364. То есть анализатору на AST придется обойти 3352 + 3015 = 6367 узлов, а анализатору высокоуровневых представлений 171 + 364 = 535, что почти в 12 раз меньше. То есть при анализе различных классов должна увеличиваться производительность от 4 до 12 раз.

Так как работа утилит анализа включает в себя чтение входных XML-файлов с промежуточными представлениями, то сравнивать данные простых запусков не имеет смысла. Утилита, использующая AST, выполняет 1 дисковую операцию, а использующая UCR+UCFR — 2. Любая такая операция занимает в несколько раз больше времени и вносит большую случайную составляющую в исследуемые экспериментальные данные. Во избежание этого для эксперимента были созданы специальные цели запуска (отдельные исследовательские версии утилит), которые выполняли анализ заданное число раз, при этом данные с диска читались только один раз, перед первым выполнением, и в дальнейшем брались из оперативной памяти.

Так же необходимо исключить все случайные составляющие, возникающие при работе утилиты на реальной машине. Для этого необходимо выполнить запуск несколько раз, а в результате взять усредненные значения. Для выполнения экспериментов использовался компьютер с 4-ядерным процессором Inter Core i5 760 2,8 ГГц 8 МБ кэша, 8 ГБ оперативной памяти DDR 1333 МГц, жестким диском WD 500ГБ 5400rpm SATA1 с файловой системой ext4, операционная система – Gentoo Linux, ядро версии 3.10.25. Для выполнения использовались следующие версии ПО: JDK – 8u45, Python – 2.7.5, система собрана с GCC – 4.7.3.

В результате работы измерялось общее время работы на нескольких запусках, без учета времени, затрачиваемого на чтение с диска. Также фиксировалось количество этих запусков. То есть, получались следующие величины: TAST - общее время, которое выполнялась утилита, использующая AST TU - общее время, которое выполнялась утилита, использующая универсальные высокоуровневые представления.

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

Из графика на рисунке 33 видно, что после значения порога равного 4 наблюдается внезапный рост для некоторых проектов, что говорит о том, что это начинают проявляться ложные срабатывания. В целом, наиболее линейный участок — это [2, 4]. На нем следует выбирать значения для исследования. Значение 1 выбирать не имеет смысла, так как в этом случае найдутся только те классы, создание которых гарантировано только в 1 месте, а это значит, что в этом нет никакой ошибки. Это значение можно использовать только для результирующего контроля, но не для исследования на наличие ошибок.

В качестве простого, но эффективного анализа универсального представления потока управления можно предложить визуализацию такого представления [85]. Однако, в реальных крупных проектах количество функциональных блоков будет очень велико, поэтому рационально будет как-либо разделить такую визуализацию. Эффективно будет представлять каждый участок потока управления (функциональный блок) в виде отдельной картинки. Тогда для больших объемов данных на выходе будет просто много картинок, среди которых можно выполнять навигацию, используя идентификаторы функциональных блоков.

Эффективным методом визуализации считается графовая визуализация [21]. Простой и понятной формой представления потока управления является блок-схема алгоритма (БСА) [10]. Представление UCFR содержит не все данные, представляемые в блок-схеме, поэтому визуальная форма будет носить БСА-подобный характер, где блоки кода будут представлены в виде прямоугольников, а вершины ветвления в виде ромбов. Все переходы будут атрибутированы стрелками.

Визуализатор написан на Python [68]. Основные его функции — обработка входного XML и формирование картинки. Для обработки XML используется распространенная библиотека lxml [81]. Она позволяет выполнять к нему XPath-запросы [53], на основе которых строятся выходные данные. Для построения картинки используется утилита dot [101] пакета Graphviz [96][98]. Для Python существует библиотека PyDot [91], которая позволяет работать с текстовым форматом dot с помощью объектно-ориентированной обвязки. За обработку исходного XML и формирование результата отвечает класс UCFRVizualizer. В результате визуализации получается набор картинок в векторном формате svg [86]. Таким образом, архитектуру разработанного визуализатора потока управления можно представить, как показано на рисунке 34.

В качестве примера такой визуализации можно рассмотреть пример из листинга 7. Для него результат визуализации будет таким, как на рисунке 35. Рисунок 34. UML-диаграмма компонентов утилиты визуализации представления графа потока управления

Одной из наиболее интересных задач статического анализа является задача анализа потока управления программы [46]. Это позволяет как выполнять оптимизацию разработанных программ [5][103][66] так и выполнять верификацию программ [56][51] и обнаруживать вредоносное программное обеспечение [72].

Трасса – это последовательность вызываемых функциональных блоков (функций или методов), которая может существовать при выполнении программы. Определенная трасса соответствует некоторому возможному сценарию исполнения анализируемой программы. Анализ трассы интересен в первую очередь с точки зрения изучения событий, которые происходят вдоль данной трассы, таких как создание объектов, вызовы функций/методов. Кроме того большой интерес представляет задача поиска трассы между двумя функциональными блоками, что позволит определить возможен ли сценарий, при котором из функционального блока A можно попасть в функциональный блок B, а также поиск недостижимого кода – функционального блока, который не вызывается ни каким другим функциональным блоком. Все это может дать исследователю информацию о потенциальных проблемах.

При анализе потока управления был введен термин трассы. Проект представляется в виде графа вызовов Gcalls Узлами графа выступают функциональные блоки (функции или методы классов), ребрами — вызовы между ними. Множество узлов ExecNodes совпадает с множеством уникальных идентификаторов методов или функций - UCFRJD (12). ExecNodes = UCFRJD (12) Множество ребер совпадает со множеством вызовов, представляя пары идентификаторов функций/методов, между которыми есть вызовы. Определим отношение Calls UCFRJDxUCFRJD , в которое входят все пары идентификаторов функций/методов проекта, между которыми происходят вызовы (формула 13). Calls = {( fl,f2)\flвызывает /2, flUCFR_ID, f2tUCFR_ID] (13) Множество ребер графа вызовов представлено в этом отношении ExecEdges=Calls . Тогда весь граф вызовов можно представить в виде (14). Gcalls = (ExecNodes ,ExecEdges) (14) Трасса — это возможный путь на графе Gcalls . Поиск трассы между двумя функциональными блоками f0 и f„ можно представить в виде поиска пути (f 0, f1, ... , fn-1 fn) на ориентированном графе. Трасса задается пользователем в виде кортежа, в которой входят узлы графа вызовов в порядке, в котором они расположены вдоль пути в графе, соответствующем трассе (15). r=(f0,f1,...,fn-1,f) , (15) где Т - трасса (рисунок 36). Рисунок 36. Пример наличия трассы в графе потока управления проекта Каждый функциональный блок соответствующий отдельному узлу графа вызовов в свою очередь представляется в виде графа, узлами которого выступают блоки потока управления функции или метода (такие как последовательные блоки и блоки изменения потока управления) в представлении UCFR, а ребрами - возможные пути передачи управления между блоками потока управления во время исполнения программы. Можно ввести отношение, в котором представлены блоки потока управления функций и методов (16) Blocks = {(f,b)\fUCFR_ID,b&N} , (16) где Ъ - идентификатор блока потока управления f . Введем отношение в котором представлены потоки управления функций и методов (17) FloWs = {(f,bl,b2)\fUCFR_ID,bl,b2\N} , (17) где тройка (f ,Ь1 ,Ъ2) представляет поток управления между блоками Ъ1 и Ь2 функции или метода f . Также можно ввести отношение, которое описывает в каких блоках функций происходит вызов других функций (18). BlockCalls = {{fl,b,f2)\fl,f2UCFR_ID,b&N} , (18) где b – идентификатор блока потока управления функции или метода f1 , в котором происходит вызов функции или метода f2 . Графически модель показана на рисунке 37, где представлен фрагмент графа вызовов из двух функций, одна из которых вызывает другую.