Диссертация (1150733), страница 2
Текст из файла (страница 2)
Такая функциональность значительно упрощаетпроцесс разработки и отладки приложений и полезна не только для основногоязыка, но и для встроенных языков.Для решения всех перечисленных выше задач необходимы инструменты,проводящие статический анализ динамически формируемых программ. Такойанализ может дать существенную информацию о таких программах, посколькуредко встречается ситуация полной динамической неопределённости (например,при создании динамических программ исключительно на основе пользовательского ввода). В большинстве случаев, имея программу, генерирующую динамические вставки, с помощью статического анализа можно получить достаточноинформации для решения поставленных выше задач.
Решению этой проблемыи посвящена данная диссертационная работа.Степень разработанности темыСуществуют классические исследования, посвященные разработке компиляторов — работы А. Ахо [11], А. Брукера [12], С. Джонсона [13], А. П. Ершова [14, 15], А. Н. Терехова [16], В. О. Сафонова [17], Б. К. Мартыненко [18, 19] идр. Однако содержащиеся там алгоритмы синтаксического анализа, как и методыобобщённого синтаксического анализа, использованные в данной работе и исследованные такими учёными как Масару Томита (Masaru Tomita) [20], ЭлизабетСкотт (Elizabeth Scott) и Адриан Джонстон (Adrian Johnstone) [21, 22] из университета Royal Holloway (Великобритания), Ян Рекерс (Jan Rekers, University ofAmsterdam) [23], Элко Виссер (Eelco Visser) [24, 25] и другими, не могут бытьприменены к решению задачи анализа динамически формируемых программ,поскольку предназначены для обработки входных данных, представимых в виде линейной последовательности символов, а такое представление динамическиформируемых программ не возможно.Анализу динамически формируемых строковых выражений посвящены работы таких зарубежных учёных как Кюнг-Гу Дох (Kyung-Goo Doh) [26–28], Ясухико Минамиде (Minamide Yasuhiko) [29], Андерс Мёллер (Anders Møller) [30]и отечественных учёных А.А.
Бреслава [31, 32] и других. Хорошо изучены вопросы проверки корректности динамически формируемых выражений и поискафрагментов кода, уязвимых для SQL-инъекций [33, 34]. Однако данные работы исследуют отдельные аспекты проблемы статического анализа динамически8формируемых программ, оставляя в стороне создание готовых алгоритмов (вчастности, не строят структурное представление анализируемых программ). Всвязи с этим возникают проблемы масштабируемости данных результатов, например, реализация на их основе более сложных видов статического анализа.Так же важным является предоставление компонентов, упрощающих создание новых инструментов для решения конкретных задач.
Данных подход хорошоисследован в области разработки компиляторов, где широкое распространениеполучили генераторы анализаторов и пакеты стандартных библиотек (работыА. Ахо [11], А. Брукера [12], С. Джонсона [13] и др.).В работах отечественных учёных М. Д. Шапот и Э. В. Попова [35], а также зарубежных учёных Антони Клеви (Anthony Cleve), Жан-Люк Эно (Jean-LucHainaut) [36], Йост Виссер (Joost Visser) [37] и других рассматриваются различные аспекты реинжиниринга информационных систем, использующих встроенные SQL-запросы, однако не формулируется общего метода для решения такихзадач.
Этот вопрос также не затрагивается в классических работах, посвященных реинжиниригу [4, 38–40].Таким образом, актуальной является задача дальнейшего исследования статического анализа динамически формируемых строковых выражений. Кроме этоговажным является решение вопросов практического применения средств анализадинамически формируемого кода: упрощение разработки инструментов анализаи создание методов их применения в реинжиниринге программного обеспечения.Объект исследованияОбъектом исследования являются методы, алгоритмы и программные средства обработки динамически формируемых программ, а также задача реинжиниринга информационных систем.Цель и задачи диссертационной работыЦелью данной работы является создание комплексного подхода к статическому синтаксическому анализу динамически формируемых программ.Достижение поставленной цели обеспечивается решением следующих задач.1.
Разработать универсальный алгоритм синтаксического анализа динамически формируемых программ, не зависящий от целевого языка программи-9рования и допускающий реализацию различных видов статического анализа.2. Создать архитектуру инструментария для автоматизации разработки программных средств статического анализа динамически формируемых программ.3. Создать метод реинжиниринга динамически формируемых программ.Методология и методы исследованияМетодология исследования основана на подходе к спецификации и анализу формальных языков, активно развивающемуся с 50-х годов 20-го века (см.,например, работы Н.
Хомского [41, 42]). В последствии этот подход получилширокое распространение в областях, связанных с обработкой языков программирования. Основными элементами данного подхода являются алфавит и грамматика языка, разбиение автоматической обработки языка на выполнение такихшагов как лексический, синтаксический и семантический анализ. Решаемые всвязи с этим задачи связаны с поиском эффективных алгоритмов, выполняющихэти шаги.В работе применяется алгоритм обобщённого восходящего синтаксического анализа RNGLR [21], созданный Элизабет Скотт (Elizabeth Scott) и АдрианДжонстон (Adrian Johnstone) из университета Royal Holloway (Великобритания).Для компактного хранения леса вывода использовалась структура данных SharedPacked Parse Forest (SPPF), которую предложил Ян Рекерс (Jan Rekers, Universityof Amsterdam) [23].Доказательство завершаемости и корректности предложенного алгоритмапроводилось с применением теории формальных языков, теории графов и теории сложности алгоритмов.
Приближение множества значений динамическиформируемого выражения строилось в виде регулярного множества, описываемого с помощью конечного автомата.Положения, выносимые на защиту1. Разработан алгоритм синтаксического анализа динамически формируемыхпрограмм, позволяющий обрабатывать произвольную регулярную аппроксимацию множества значений выражения в точке выполнения, реализую-10щий эффективное управление стеком и гарантирующий конечность представления леса вывода.
Доказана завершаемость и корректность предложенного алгоритма при обработке регулярной аппроксимации, представимой в виде произвольного конечного автомата без -переходов.2. Создана архитектура инструментария для разработки программныхсредств статического анализа динамически формируемых программ.3. Разработан метод анализа и обработки динамически формируемых программ в проектах по реинжинирингу информационных систем.Научная новизна работыНаучная новизна полученных в ходе исследования результатов заключаетсяв следующем.1. Алгоритм, предложенный в диссертации, отличается от аналогов (работыАндрея Бреслава [31, 32], Кюнг-Гу Дох [26, 27], Ясухико Минамиде [29])возможностью построения компактной структуры данных, содержащей деревья вывода для всех корректных значений выражения.
Это позволяет использовать результаты работы алгоритма для проведения более сложныхвидов анализа. Алгоритмы, представленные в JSA [30] [31,32], PHPSA [29]предназначены только для проверки корректности выражений, основаннойна решении задачи о включении одного языка в другой. Выполнение болеесложных видов анализа, трансформаций или построения леса разбора непредполагается.2. Новизна представленной архитектуры заключается в том, что данная архитектура позволяет создать платформу для разработки целевых инструментов, решающих широкий круг задач анализа динамически формируемого кода.
Существующие архитектуры готовых инструментов (JSA, PHPSA,Alvor, Varis) предназначены для решения конкретных задач для определённых языков. Решение новых задач или поддержка других языков с помощью этих инструментов затруднены ввиду ограничений, накладываемыхархитектурой и возможностями используемого алгоритма анализа.113. Метод анализа и обработки встроенного программного кода в проектах пореинжинирингу информационных систем предложен впервые. К. В.
Ахтырченко и Т. П. Сорокваша отмечают [43], что существующие работы вобласти реинжиниринга программного обеспечения либо содержат высокоуровневые решения, не касающиеся деталей, важных при решении прикладных задач (например, работы К. Вагнера [40], Х. Миллера [39]), либоявляются набором подходов к решению конкретных задач (например, работы [4, 38, 44]). При этом, задача анализа встроенного программного кодане учитывается. С другой стороны, работы М. Д. Шапот и Э. В.
Попова [35], С. Л. Трошина [4], А. Клеви [36] посвящены решению конкретныхзадач обработки встроенного программного кода в контексте реинжиниринга информационных систем, но не предлагают обобщённого и масштабируемого метода.Теоретическая и практическая значимость работыТеоретическая значимость диссертационного исследования заключается вразработке формального алгоритма синтаксического анализа динамически формируемого кода, решающего задачу построения конечного представления лесавывода, не решенную полностью ранее, а также в формальном доказательствезавершаемости и корректности разработанного алгоритма.На основе полученных в работе научных результатов был разработан инструментарий (Software Development Kit, SDK), предназначенный для созданиясредств статического анализа динамически формируемых программ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
