Автореферат (Синтаксический анализ динамически формируемых программ)

На правах рукописиГригорьев Семён ВячеславовичCинтаксический анализ динамическиформируемых программСпециальность 05.13.11 —Математическое и программное обеспечение вычислительныхмашин, комплексов и компьютерных сетейАвторефератдиссертации на соискание учёной степеникандидата физико-математических наукСанкт-Петербург — 2015Работа выполнена на кафедре системногоПетербургского государственного университетаНаучный руководитель:программированияСанкт-кандидат физико-математических наук, доцентКознов Дмитрий ВладимировичОфициальные оппоненты: Марчук Александр Гурьевич,доктор физико-математических наук, профессор,федеральное государственное бюджетное учреждение науки Институт систем информатики им. А.П.Ершова Сибирского отделения Российской академии наук, директорИцыксон Владимир Михайлович,кандидат технических наук, доцент,федеральное государственное автономное образовательное учреждение высшего образования “СанктПетербургский политехнический университет Петра Великого”, исполняющий обязанности заведующего кафедройВедущая организация:Федеральное государственное бюджетное учреждение науки Институт системного программированияРоссийской академии наук (ИСП РАН)г.

вчасов на заседаЗащита состоитсянии диссертационного совета Д 212.232.51 на базе Санкт-Петербургского государcтвенного университета по адресу: 198504, Санкт-Петербург, Петродворец,Университетский пр., 28, математико-механический факультет, ауд. 405.С диссертацией можно ознакомиться в Научной библиотеке СанктПетербургского государственного университета по адресу: 199034, СанктПетербург, Университетская наб., д. 7/9, а также на сайте http://spbu.ru/science/disser/.Автореферат разосланУченый секретарьдиссертационного советаД 212.232.51, д.ф.-м.н., профессор20годаДемьянович Юрий КазимировичОбщая характеристика работыАктуальность темы исследованияВзаимодействие различных компонент приложений часто реализуется спомощью встроенных языков, то есть приложение, созданное на одном языке, генерирует код на другом языке и передаёт этот код на выполнение в соответствующее окружение. Примерами могут служить динамические SQL-запросы к базам данных в Java-коде или формирование HTML-страниц в PHP-приложениях.Генерируемая программа строится таким образом, чтобы в момент выполнениярезультирующий фрагмент кода (строка) представлял собой корректное выражение на соответствующем языке.

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

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

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

Ахо, А. Брукера, С. Джонсона, А. П. Ершова, А. Н. Терехова, В. О. Сафонова, Б. К. Мартыненко и др. Однако изложенные там алгоритмы синтаксического анализа, как и методы обобщённого синтаксическогоанализа, исследованные такими учёными как Масару Томита (Masaru Tomita),Элизабет Скотт (Elizabeth Scott) и Адриан Джонстон (Adrian Johnstone) из университета Royal Holloway (Великобритания), Ян Рекерс (Jan Rekers, University ofAmsterdam), Элко Виссер (Eelco Visser), не могут быть применены к решениюзадачи анализа динамически формируемых программ, поскольку предназначеныдля обработки входных данных, представимых в виде линейной последовательности символов, а такое представление динамически формируемых программ невозможно.Анализу динамически формируемых строковых выражений посвященыработы таких зарубежных учёных как Кюнг-Гу Дох (Kyung-Goo Doh), ЯсухикоМинамиде (Minamide Yasuhiko), Андерс Мёллер (Anders Møller) и отечественных учёных А.

А. Бреслава, М. Д. Шапот. Хорошо изучены вопросы проверкикорректности динамически формируемых выражений и поиска фрагментов кода, уязвимых для SQL-инъекций. Однако данные работы исследуют отдельныепроблемы статического анализа динамически формируемых программ, оставляя в стороне создание готовых алгоритмов (в частности, не строят структурноепредставление анализируемых программ).

В связи с этим возникают проблемымасштабируемости данных результатов, например, создание на их основе болеесложных видов статического анализа.Также важным является предоставление компонентов, упрощающих создание новых инструментов для решения конкретных задач. Данный подход хорошо исследован в области разработки компиляторов, где широкое распространение получили генераторы анализаторов и пакеты стандартных библиотек (работы А. Ахо, А. Брукера, С. Джонсона и др.), однако его применение в областианализа динамически формируемого кода не исследовано.В работах отечественных учёных М.

Д. Шапот и Э. В. Попова, а также зарубежных учёных Антони Клеви (Anthony Cleve), Жан-Люк Эно (Jean-LucHainaut), Йост Виссер (Joost Visser) рассматривается реинжиниринг информационных систем, использующих встроенные SQL-запросы, однако не формулируется общего метода для решения таких задач. Этот вопрос также не затрагивается в классических работах, посвященных реинжиниригу (Х. Миллера,А. Н. Терехова, Р. С. Арнольда и др.).Таким образом, актуальной является задача дальнейшего исследованиястатического анализа динамически формируемых строковых выражений. Кромеэтого важным является решение вопросов практического применения средстванализа динамически формируемого кода: упрощение разработки инструмен4тов анализа и создание методов их применения в реинжиниринге программногообеспечения.Объект исследованияОбъектом исследования являются методы, алгоритмы и программныесредства обработки динамически формируемых программ, а также задача реинжиниринга информационных систем.Цель и задачи диссертационной работыЦелью данной работы является создание комплексного подхода к статическому анализу динамически формируемых программ.Достижение поставленной цели обеспечивается решением следующихзадач.1.

Разработать алгоритм синтаксического анализа динамически формируемыхпрограмм, позволяющий обрабатывать регулярную аппроксимацию множества значений выражения в точке выполнения, и гарантирующий конечность представления леса вывода.2. Создать архитектуру инструментария для разработки программных средствстатического анализа динамически формируемых строковых выражений.3. Разработать метод анализа и обработки встроенного программного кода впроектах по реинжинирингу информационных систем.Цели и задачи диссертационной работы соответствуют области исследований паспорта специальности 05.13.11 “Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей” — пункту 1(модели, методы и алгоритмы проектирования и анализа программ и программных систем, их эквивалентных преобразований, верификации и тестирования),пункту 2 (языки программирования и системы программирования, семантикапрограмм) и пункту 10 (оценка качества, стандартизация и сопровождение программных систем).Методология и методы исследованияМетодология исследования основана на подходе к спецификации и анализу формальных языков, который начал активно развиваться в 50-х годах 20-говека в связи с изучением естественных языков (работы Н.

Хомского). В последствии этот подход получил широкое распространение в областях, связанных собработкой языков программирования. При этом основными элементами данного подхода являются алфавит и грамматика исследуемого языка, разбиение5автоматической обработки языка на выполнение таких шагов, как лексический,синтаксический и семантический анализ. Решаемые в связи с этим задачи связаны с поиском эффективных алгоритмов, выполняющих эти шаги.В работе применяется алгоритм обобщённого восходящего синтаксического анализа RNGLR, созданный Элизабет Скотт (Elizabeth Scott) и АдрианДжонстон (Adrian Johnstone) из университета Royal Holloway (Великобритания).Для компактного хранения леса вывода используется структура данных SharedPacked Parse Forest (SPPF), которую предложил Ян Рекерс (Jan Rekers, Universityof Amsterdam).