ИСПОЛЬЗОВАНИЕ АБСТРАКТНОГО ЦИФРОВОГО АВТОМАТА ДЛЯ ПОЛУЧЕНИЯ УНИВЕРСАЛЬНОГО ПРОМЕЖУТОЧНОГО ПРЕДСТАВЛЕНИЯ ИСХОДНОГО КОДА ПРОГРАММ
Авторы:
1.
Челябинский государственный университет
2.
Челябинский государственный университет
Тип:
Статья
Страницы:
с 57
по 65
Статус:
Опубликован
Получено:
05.10.2015
Одобрено:
25.10.2015
Опубликовано:
25.10.2015
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 004.41
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 004.41
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
статический анализ, промежуточное представление, абстрактный автомат, конечный автомат, программирование, исходный код
Аннотация (русский):
Для выполнения статического анализа предложено использовать универсальные многоуровневые промежуточные представления. Были формализованы модели следующих представлений: для анализа архитектуры проекта - модель представления уровня классов, для анализа функциональных модулей - потока управления. Необходимо формализовать метод получения таких представлений для соответствия предложенной модели. Это позволяет единообразно добавлять новые языки путем создания стандартного генератора универсального промежуточного представления. Предлагается использовать абстрактный цифровой автомат с магазинной памятью. В качестве базового способа преобразования текста в машинные данные используется синтаксический анализ. Такой конечный автомат обрабатывает последовательность сигналов, описывающих входное дерево разбора, и формирует последовательность сигналов, описывающих дерево промежуточного представления. Хранение в памяти предыдущих состояний автомата дает возможность анализировать произвольную вложенность входного дерева. Введение специального свойства для входных и выходных сигналов позволяет описать дерево в виде последовательности узлов в соответствии с его обходом в глубину. Для программной реализации такого подхода был выбран язык Java, промежуточное представление строилось также для Java. Каждое состояние автомата реализовано в виде активного объекта, обрабатывающего входной поток сигналов. Реализуя такие шаблоны проектирования, как «цепочка ответственности», «состояние» и «стратегия», состояния образовывали таблицу переходов автомата Мили и магазинную память. Для хранения входных и выходных данных был выбран формат XML. Тестирование путем проверки преобразования синтаксических конструкций языка в текст универсального промежуточного представления на собственном коде и проектах с открытым исходным кодом показало полное соответствие реализации предложенным моделям.
Для выполнения статического анализа предложено использовать универсальные многоуровневые промежуточные представления. Были формализованы модели следующих представлений: для анализа архитектуры проекта - модель представления уровня классов, для анализа функциональных модулей - потока управления. Необходимо формализовать метод получения таких представлений для соответствия предложенной модели. Это позволяет единообразно добавлять новые языки путем создания стандартного генератора универсального промежуточного представления. Предлагается использовать абстрактный цифровой автомат с магазинной памятью. В качестве базового способа преобразования текста в машинные данные используется синтаксический анализ. Такой конечный автомат обрабатывает последовательность сигналов, описывающих входное дерево разбора, и формирует последовательность сигналов, описывающих дерево промежуточного представления. Хранение в памяти предыдущих состояний автомата дает возможность анализировать произвольную вложенность входного дерева. Введение специального свойства для входных и выходных сигналов позволяет описать дерево в виде последовательности узлов в соответствии с его обходом в глубину. Для программной реализации такого подхода был выбран язык Java, промежуточное представление строилось также для Java. Каждое состояние автомата реализовано в виде активного объекта, обрабатывающего входной поток сигналов. Реализуя такие шаблоны проектирования, как «цепочка ответственности», «состояние» и «стратегия», состояния образовывали таблицу переходов автомата Мили и магазинную память. Для хранения входных и выходных данных был выбран формат XML. Тестирование путем проверки преобразования синтаксических конструкций языка в текст универсального промежуточного представления на собственном коде и проектах с открытым исходным кодом показало полное соответствие реализации предложенным моделям.
Ключевые слова:
статический анализ, промежуточное представление, абстрактный автомат, конечный автомат, программирование, исходный код
статический анализ, промежуточное представление, абстрактный автомат, конечный автомат, программирование, исходный код
Введение Статический анализ - это изучение исходного текста программ без их непосредственного выполнения. Он может использоваться для решения задач по извлечению информации из исходного кода, анализа архитектуры проекта, анализа потока управления и проведения рефакторинга [1]. Для выполнения статического анализа обычно используются промежуточные представления исходного кода в качестве входных данных. Достоинства применения универсальных промежуточных представлений при статическом анализе исходного кода были освещены в [2]. Универсальные промежуточные представления (УПП) - это представления, которые можно использовать более чем для одного языка. Были разработаны математические модели таких представлений [3]. Формализация позволяет строго описывать формат данных и требования к их свойствам. Так как анализ универсального представления не зависит от входного языка, то для каждого нового языка требуется только реализация генератора такого представления. Формальный метод получения представления позволит единообразно добавлять новые языки путем создания стандартного генератора УПП. Постановка задачи Основным способом перевода исходного кода из текстового формата в машинные данные, удобные для обработки программным образом, является синтаксический анализ [4]. Исходный код является текстом на формальном языке - языке программирования. Такой текст легко представляется в виде абстрактных синтаксических деревьев разбора (AST) согласно его формальной грамматике в виде абстрактного синтаксического дерева разбора [5]. Для получения промежуточного представления сначала нужно выполнить синтаксический анализ, а затем, на основе AST, получать необходимые данные (рис. 1). Рис. 1. Получение промежуточного представления из исходного кода Для получения разрабатываемого представления потока управления из абстрактного дерева разбора необходимо выполнить обход дерева AST и формирование дерева УПП. Такие деревья можно представить в виде потока его узлов и атрибутов в соответствии с алгоритмом обхода в прямом порядке в глубину. Задачи преобразования и обработки потока некоторых входных данных эффективно решаются с помощью абстрактных цифровых автоматов [6]. Ранее было предложено получение абстрактного синтаксического дерева разбора в формате XML для языка Java [7], поэтому будем рассматривать разработку генератора представлений, использующую этот функционал. Соответственно, разрабатываемый генератор представлений предназначен для языка Java. Общая автоматная модель Воспользуемся конечным автоматом для преобразования AST в УПП. Один узел выходного представления может соответствовать комбинации узлов входного, поэтому целесообразно воспользоваться моделью автомата Мили, в котором выходные сигналы зависят не только от состояния, но и входных данных. Степень ветвления в AST велика, а вложенность может быть произвольной, однако она соответствует контекстно-свободной грамматике входного языка. В AST могут существовать структуры произвольного уровня вложенности. Канонический автомат Мили не подходит для обработки таких структур. Либо для каждого уровня вложенности необходимо свое состояние, но тогда автомат не будет конечным, либо будет происходить потеря данных. Для разбора последовательностей, описываемых контекстно-свободными грамматиками, используются конечные автоматы с магазинной (стековой) памятью (МП-автоматы) [8]. В отличие от классической модели, будем хранить в стеке не входные сигналы, а состояния автомата. Общую модель такого автомата для получения промежуточных представлений можно формализовать в следующем виде: , (1) где - конечное множество состояний автомата; - алфавит стека состояний, являющийся надмножеством , т. е. (любое состояние можно поместить в стек); - нулевой (начальный) символ стековой памяти состояний ; - множество входных сигналов; - множество выходных сигналов; - функция переходов; - функция выходов; - функция получения следующего элемента для записи в память (функция памяти); - начальное состояние. Будем пользоваться определением автомата с помощью функций, а не с помощью команд МП-автомата. Это делается для удобства, т. к. входные сигналы можно разделить на однотипные группы, что упростит формализацию таких функций [9]. Каждое состояние автомата будет соответствовать преобразованию определенного узла AST или группы узлов, которые описывают одну сущность высокоуровневого представления. Таким образом, функция переходов в автомате (1) является отображением , а функция выходов для автомата Мили, в свою очередь, отображением . Функция памяти будет показывать, какой символ необходимо записать в стек в конце такта [10]. Обозначим символом некоторый сигнал, обозначающий завершение обработки узла и переход к его родительскому узлу. Этот символ будет показывать, что необходимо перейти к предыдущему состоянию. Он также будет использоваться в выходных данных. Входные и выходные сигналы будут основаны на моделях AST и универсальных представлений, предложенных в [3]. На вход автомата будут поступать элементы абстрактного синтаксического дерева разбора Java, а именно поддеревья вида , где - конструкция из множества конструкций языка программирования (узел дерева разбора), являющаяся корнем поддерева ; - множество поддеревьев AST для текущего корня; - множество листьев текущего корня (операндов текущего оператора), - множество всех возможных операндов для конструкций языка. Будем считать, что входной сигнал автомата состоит из узла входного представления, множества листьев и возможного сигнала для перехода к предыдущему состоянию. Таким образом, , где - входной сигнал; ; - листья текущего узла, которые можно извлечь в данный момент; - символ перехода к родительскому узлу. На выходе автомата будем получать поддеревья универсальных многоуровневых представлений вида , где - узел промежуточного представления, являющийся корнем поддерева ; - множество поддеревьев представления для текущего корня; - множество атрибутов текущего узла; - множество всех возможных атрибутов. По аналогии с входными сигналами, на выходе будем получать сигналы, состоящие из узлов нового представления, его листьев (характеристик) и признака . Структура выходного сигнала - , где - выходной сигнал; ; - некоторое подмножество листьев узла, которые можно выдать в данный момент; - символ перехода к родительскому узлу. Структура магазинной памяти в автомате будет такова, что в нее будет записываться обработанное состояние (в случае перехода к следующему вложенному узлу) или же будет извлекаться состояние из вершины (при окончании обработки текущего узла). Обозначим как любой символ, находящийся на вершине стека состояний в текущий момент. Таким образом, указывая в качестве состояния , будем обращаться к текущему состоянию. Обозначим как пустой символ для записи в стек состояний. Если верхний символ заменяется пустой цепочкой , то после его записи верхним символом становится некоторое , записанное под верхней ячейкой. Если записывается некоторый символ , то он помещается на вершину, а все остальные ячейки сдвигаются на одну в глубину. Таким образом, текущий символ на момент начала такта оказывается записанным во второй ячейке. Если в качестве входного сигнала памяти указывается непосредственно сам , тогда записи в память не происходит, считаем, что стек не меняется. Множество входных сигналов содержит те входные сигналы, у которых присутствует - признак того, что обработка текущего узла закончена. Таким образом, при любом значении входного сигнала из этого множества будет осуществляться переход к состоянию, находящемуся в вершине стека состояний. Следует также выделить множество входных сигналов , отвечающих за узлы, соответствующие описанию идентификаторов, обращений к типу через точку и обращению к примитивному типу. Все эти сигналы ни при каких условиях не меняют состояние автомата, а влияют только на выходной сигнал. Все множество остальных входных сигналов, которые заставляют автомат выполнить переход по таблице, обозначим как . Других типов входных сигналов не будет, . Разделив входные сигналы на несколько групп, можно сформировать единую функцию переходов. где - некоторое состояние, определяемое по таблице переходов автомата. Таким образом, при использовании такой функции только при определенных значениях входного сигнала будет осуществляться переход по таблице переходов. При этом значение состояния, хранящееся в стеке, не влияет на переход. Получается, что таблица переходов будет более простым отображением, чем функция переходов , где левая часть является отношением, содержащим допустимые входные пары, приводящие к переходу , где . Функция памяти автомата также определяется на основе группы входных сигналов. Как видно, запись нового состояния автомата, полученного из этой функции, происходит только в случае явного перехода по таблице, т. е. когда появилось новое состояние. Общая схема разработанного автомата представлена на рис. 2. Рис. 2. Схема абстрактного цифрового автомата для генерации промежуточного представления Использование такого автомата, разработанного через описание функций существенно сокращает его затраты на реализацию, так как не требуется явно обрабатывать все узлы входного AST с помощью канонического метода синтеза МП-автомата [9]. Кроме того, из его выходных сигналов можно напрямую получать узлы требуемого промежуточного представления. Реализация предложенного подхода Для реализации абстрактного автомата основным классом будет состояние автомата. В каждом таком состоянии на основе входных данных будут осуществляться переходы, получаться новые состояния и формироваться выходные данные. Состояние автомата само по себе может быть представлено активным объектом [11]. Тогда магазинную память можно реализовать с помощью шаблона проектирования «цепочка ответственности» [12]. При получении состояния по таблице переходов новое заменяет старое, а все вызовы уже идут к нему. Таким образом, ответственность за обработку входных сигналов перекладывается на полученное состояние, а сохранение предыдущего позволит перейти к нему как к расположенному глубже элементу магазинной памяти. Кроме того, при установке нового состояния будет меняться логика получения выходных данных, что соответствует шаблону проектирования «состояние». Изменение алгоритма получения выходных сигналов в зависимости от состояния, в свою очередь, соответствует шаблону «стратегия». UML-диаграмма классов для интерфейса, описывающего обработку каждого состояния абстрактного автомата, предложенного ранее, показана на рис. 3. Рис. 3. UML-диаграмма Java-интерфейса, описывающего обработчик состояния автомата - генератора промежуточного представления Разрабатываемое промежуточное представление должно быть экспортируемым в файл и легкодоступным для анализа и проверки вручную. Кроме того, представление должно являться деревом. Хорошим способом для хранения древовидной информации в удобном для восприятия виде является XML-формат [13]. Этот формат рекомендован Консорциумом всемирной паутины (W3C) и поддерживает возможность описания структуры документов с помощью XML-схем [14]. Кроме того, исходные данные с AST также можно получать в формате XML [7]. Входные события, возникающие при чтении исходного XML-документа, можно разделить на открывающиеся теги и закрывающиеся. Это вполне соответствует признаку во входном сигнале автомата. Если тег открывается, значит, входной сигнал содержит некоторый набор листьев и сам узел (тег), но не содержит . Закрывающийся тег, наоборот, говорит о том, что обработка узла (тега) завершена. В качестве примера рассмотрим предложенное ранее универсальное представление потока управления (UCFR - universal control-flow representation) [15]. Такое представление хранит в себе в виде дерева граф потока управления по отдельности для каждой функции и метода. Само представление строится для языка Java, его генератор также написан на языке Java. В исходном коде на языке программирования Java для удобства программирования можно не указывать полные имена используемых типов. Они могут быть получены из локальных с помощью инструкций import или взяты из текущего пакета. Это накладывает некоторые ограничения на получение представления, т. к. в исходном виде в коде нет связей с конкретными типами данных. Для решения этой проблемы обработка представления осуществляется в 3 прохода. 1. Автоматное преобразование, получение «сырого» представления. На этом проходе в представлении типы данных находятся в том виде, в котором они хранятся в коде. 2. Генерация ID для методов и классов, формирование таблиц этих ID. 3. Поиск внутрипроектных типов данных для переменных/полей/аргументов, которые являются источниками вызовов, и самих вызовов. Расстановка связей по ID. Поиск внутрипроектных типов данных осуществляется по такому же алгоритму, который используется при компиляции. Типы ищутся среди классов всего проекта по порядку в следующих местах: 1. В именованных вложенных классах текущего класса. 2. В именованных вложенных классах родителя текущего класса. 3. В проекте, в котором расположен текущий класс. 4. В списке проектов, подключенных к текущему с помощью import (для подключения пакетов используется инструкция со звездочкой). 5. В списке классов, подключенных к текущему с помощью import. Если в ходе обработки по этому алгоритму подходящих классов не нашлось, искомый считается внешним (системным или библиотечным) по отношению к проекту и не рассматривается в дальнейшем, хотя и не исключается из представления. Связь с ним помечается как внешняя. Для считывания XML используется библиотека потоковой обработки XML для языка Java - StAX (Streaming API for XML) [16]. Сам по себе StAX описывает только интерфейс и подход к потоковому вводу/выводу в XML для Java. Существует множество его реализаций. Базовая реализация StAX входит в состав стандартной поставки JavaSE начиная с 6 версии. Работа с XML в StAX основана на событиях, возникающих на входном потоке. Для записи выходного представления в XML-формате используется технология связывания данных [17]. Связывание данных заключается в том, что на основе описания данных XML в виде схемы генерируется исходный код, описывающий в удобном объектно-ориентированном виде данные, хранимые в XML. Используя этот код, можно выполнять маршалинг (преобразование данных из XML в объекты в памяти) и демаршалинг (преобразование данных из памяти в XML). Связывание данных реализуется на основе технологии Java Architecture for XML Binding (JAXB) [18]. Эта технология включается в поставку Java EE начиная с версии 6. Кроме того, интерфейсы для работы с ней стандартизованы, имеется несколько реализаций этих интерфейсов. Для разработки использовалась базовая реализация, включаемая в пакет JDK. Как отмечалось ранее, получить полные данные представления по коду в один проход невозможно, требуются 2 дополнительных прохода по получаемому дереву для расстановки связей внутрипроектных вызовов и разрешения идентификаторов. На первом проходе с помощью автоматной обработки генерируются базовые данные JAXB, описывающие выходное дерево, на втором проходе класс MethodRegistryItem выполняет расстановку целочисленных идентификаторов для всех методов проекта и классов, в которых они описаны. На третьем проходе класс VariableScope проходит по всем переменным проекта и непосредственным вызовам, расставляя идентификаторы целей внутрипроектных вызовов и удаляя лишние. Полученный генератор представления UCFR на основе трех проходов, обработки XML, связывания данных и автоматного подхода может быть представлен в виде схемы (рис. 4). Рис. 4. Схема работы генераторов промежуточного представления UCFR для языка Java Применение разработанного функционала показало полное соответствие предложенным моделям. Для тестирования использовался собственный код генератора представлений и генератора абстрактного дерева разбора в формате XML, а также проекты с открытым исходным кодом: javac, squirrel и log4j. Общий объем тестируемого кода превысил десятки тысяч строк. Тестирование производилось путем проверки преобразования синтаксических конструкций языка в текст универсального промежуточного представления. Результаты разработки генератора представлений зарегистрированы в государственном реестре программ для ЭВМ [19]. Заключение Статический анализ использует в качестве входных данных промежуточные представления. Был предложен формальный метод получения УПП на основе абстрактного цифрового автомата с магазинной памятью. Он основывается на предложенных ранее математических моделях промежуточных представлений и позволяет формировать данные, соответствующие им. Хранение в памяти предыдущих состояний автомата позволяет простым эвристическим способом описать переходы и выходы без использования синтеза команд по входной грамматике. Формализованная модель автомата была реализована в программном коде на языке Java. Разработанные программные утилиты позволяют получать XML-документы с промежуточным представлением из исходного кода. В дальнейшем эти документы используются для выполнения статического анализа. Формализация метода получения промежуточного представления позволяет использовать его для других языков с целью получения данных, описываемых той же самой моделью. Выполненная реализация на Java показывает простоту разработки генераторов представлений при наличии готовой модели.
1. Зубов М. В. Численное моделирование анализа исходного кода с использованием промежуточных представлений / М. В. Зубов, А. Н. Пустыгин, Е. В. Старцев // Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. 2014. № 4. С. 55-66.
2. Зубов М. В. Применение универсальных промежуточных представлений для статического анализа исходного программного кода / М. В. Зубов, А. Н. Пустыгин, Е. В. Старцев // Докл. Томск. гос. ун-та систем управления и радиоэлектроники. 2013. Т. 27, № 1. С. 64-69.
3. Зубов М. В. Математическое моделирование универсальных многоуровневых промежуточных представлений для статического анализа исходного кода / М. В. Зубов, А. Н. Пустыгин, Е. В. Старцев // Докл. Томск. гос. ун-та систем управления и радиоэлектроники. 2014. Т. 33, № 3. С. 94-99.
4. Ахо А. Компиляторы: принципы, технологии и инструментарий / А. Ахо, М. Лам, Р. Сети, Д. Ульман. М.: Вильямс, 2010. 1184 с.
5. Серебряков В. А. Основы конструирования компиляторов / В. А. Серебряков, М. П. Галочкин. М.: Эдиториал УРСС, 2001. 224 с.
6. Хопкрофт Дж. Введение в теорию автоматов, языков и вычислений / Дж. Хопкрофт, Р. Мотвани, Дж. Ульман. М.: Вильямс, 2008. 528 с.
7. Зубов М. В. Прототипы построителей промежуточных представлений исходных текстов программ, основанные на компиляторах с открытым исходным кодом / М. В. Зубов, А. Н. Пустыгин, Е. В. Старцев // Седьмая конференция «Свободное программное обеспечение в высшей школе»: тез. докл. М.: Альт-Линукс, 2012. С. 82-86.
8. Алгоритм построения МП-автомата по КС-грамматике // URL: http://mathhelpplanet.com/static.php?p= algoritm-postroyeniya-mp-avtomata-po-ks-grammatike (дата обращения: 25.07.2015).
9. Новиков Ф. А. Автоматный метод определения проблемно-ориентированных языков / Ф. А. Новиков, У. Н. Тихонова // Информационно-управляющие системы. 2009. № 6. С. 34-40.
10. Новиков Ф. А. Дискретная математика для программистов / Ф. А. Новиков. СПб.: Питер, 2007. 386 с.
11. Schmidt D. Pattern-Oriented Software Architecture. Vol. 2: Patterns for Concurrent and Networked Objects / D. Schmidt, M. Stal, H. Rohnert. New York, USA: Wiley. 631 p.
12. Гамма Э. Приемы объектно-ориентированного проектирования. Паттерны проектирования / Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес. СПБ.: Питер, 2007. 366 с.
13. Хантер Д. XML. Работа с XML / Д. Хантер, Д. Рафтер, Д. Фаусетт, Э. ван дер Влист и др. М.: Диалектика, 2009. 1344 с.
14. XML Schema // URL: www.w3.org/XML/Schema (дата обращения: 25.07.2015).
15. Зубов М. В. Построение универсального представления графа потока управления для статического анализа исходного кода / М. В. Зубов, А. Н. Пустыгин, Е. В. Старцев // Девятая конференция «Свободное программное обеспечение в высшей школе»: тез. докл. М.: Альт-Линукс, 2014. С. 46-51.
16. Использование StAX для обработки XML // URL: http://www.ibm.com/developerworks/ru/library/ x-stax1 (дата обращения: 25.07.2015).
17. McLaughlin B. Java and XML data binding / B. McLaughlin. CA, USA: O'Reilly, 2002. 218 p.
18. JAXB Reference Implementation // URL: https://jaxb.java.net (дата обращения: 25.07.2015).
19. Зубов М. В. Генератор универсального классового промежуточного представления в формате XML из представления AST исходного текста на языке Java / М. В. Зубов, А. Н. Пустыгин // Свид-во о гос. регистрации программ для ЭВМ № 2014663489; Заявка № 2014663489; зарегистрирована в Реестре программ для ЭВМ 24.12.2014.
