Диссертация (1150733), страница 5
Текст из файла (страница 5)
Рассмотримпример и поясним, какие задачи необходимо решать и каким образом анализстроковых выражений помогает решать данные задачи. Мы рассмотрим примервстроенного SQL, однако все рассмотренные задачи актуальны и для другихязыков.Одной из широко распространённых задач, является оценка качества кодаи его сложности с использованием различных формальных метрик [59]. Привычислении таких метрик важно учитывать, что использование динамическиформируемых выражений, сложность их конструирования, количество и содержание возможных значений и многие другие характеристики влияют на качествои сложность содержащего их кода.
По этой причине необходимо иметь возможность оценивать сложность динамически формируемых выражений с различных23123public void NewReport(int prodId = 0, int status = 0, int nType = 0){int nProdIdL = prodId;4string sMagicKey = "[" + prodId.ToString() + "]";56string tbl = status == 0 ? "InOrders " : "OutOrders ";78while (nProdIdL > 0){sMagicKey = "[" + sMagicKey + "]";nProdIdL = nProdIdL - 1;}91011121314string sExec ="SELECT sOrderDescription, cderitInfo, " + sMagicKey+ " FROM ts." + tbl +"as t1 JOIN tCreData cd (NOLOCK) ON cd.ncredataid "+ " = t1.ncredataid";151617181920string sWhere = nType == 0? "WHERE nOrderType = 0 AND nStatus > 2 ": "WHERE nStatus > 0 ";21222324sExec = "INSERT INTO reports (description, creditInfo, id)"+ " VALUES " + sExec + sWhere;252627db.Execute(sExec);2829}Листинг 5: Пример кода метода на языке программирования C#,формирующего и выполняющего динамический SQL-запросточек зрения [37, 60].
С одной стороны, необходимо оценивать сложность формирования выражения. Так в примере, представленном в листинге 5, для формирования запроса используется цикл (строки 9–13), что может приводить кпотенциально бесконечному множеству различных значений выражения. С другой стороны, важна сложность возможных значений выражения. В листинге 5, вдинамически формируемом запросе используется конструкция соединения таблиц (JOIN, строка 17).
Большое количество соединений и сложность условийчасто становится причиной проблем с производительностью и может служитьпризнаком неудачного проектирования схемы данных [60].Другой набор задач, связанный с сопровождением и модификацией систем,разработанных с активным использованием динамически формируемых выраже-24ний — это извлечение знаний о системе [61] и автоматизированный реинжиниринг программного обеспечения [36].
Например, при активном использованиивстроенного SQL может возникать задача анализа или восстановления схемыданных [58]. Проанализировав структурное представление динамически формируемого SQL-кода в примере из листинга 5, можно сделать вывод о том, чтоданный код обращается к таблицам InOrders, OutOrders и tCreData начтение, а к таблице reports на запись. Без анализа строковых выражений этаинформация не может быть получена, а она может быть полезна, например, примодификации схемы данных.Так как встроенные языки активно используются на практике, то важна ихподдержка в интегрированных средах разработки, что может быть полезно нетолько при непосредственной разработке, но и при автоматизированном и ручном изучении кода, совмещённом с решением перечисленных выше задач.
Дополнительная поддержка встроенных языков в средах разработки может включать подсветку синтаксиса и парных элементов, навигацию по коду с учётомдинамически формируемого выражения, диагностику и подсветку ошибок, чтоупрощает работу с кодом. Например, в листинге 5 пропущен пробел между блоком WHERE (переменная sWhere, строки 20–22) и началом конструкции SELECT(переменная sExec, строки 15–18).
То есть при выполнении данного метода будет формироваться некорректный запрос, но об этом станет известно только вмомент выполнения метода. Однако ошибки такого рода можно обнаруживатьбез запуска программы и сообщать об этом разработчику.1.4Подходы к анализу встроенных языковСуществуют два вида подходов к анализу программного кода: динамическийи статический [62]. Динамический анализ подразумевает изучение поведенияпрограммы во время её работы.
Статический анализ позволяет получать знаниео программе без её выполнения. Анализ динамически формируемых выражений, как вид анализа кода программ, актуален как в задачах обеспечения безопасности программного обеспечения (поиск мест в коде, уязвимых для SQLинъекций [33]), так и для разработки, сопровождения и модернизации систем,разработанных с применением встроенных языков. Для решения подобных за-25дач применимы оба вида анализов: существуют работы по анализу динамическиформируемых программ во время выполнения (например работа [35], посвященная трансляции встроенных SQL-запросов во время выполнения), а так же рядработ по статическому анализу динамически генерируемого кода ( [29–31, 55] идр.).
Динамический анализ обладает одним принципиальным недостатком — оннедостоверен (unsound), так как анализируются только те части программы, которые были выполнены [62]. Статический анализ, напротив, обрабатывает всюпрограмму целиком и избавлен от этого недостатка. По этой причине наиболееинтересны подходы к статическому анализу встроенных языков, основные изкоторых рассмотрены ниже.Проверка включения языков. В рамках данного подхода в результате анализа внешнего кода строится язык 1 , являющийся приближением языка , задаваемого программой-генератором, после чего проверяется включение 1 в язык2 (), описанный эталонной грамматикой [29, 30].
Основной недостаток данного подхода — невозможность получить какую-либо информацию, кроме знания о включении или невключении одного языка в другой. Как следствие, проведение более сложных видов статического анализа или трансформации невозможно. Можно выделить несколько вариантов данного подхода, различающихсяклассом языка 1 .– Регулярная аппроксимация: 1 является регулярным языком. Однако язык не обязан быть регулярным, так как программа-генератор может быть реализована на тьюринг-полном языке, что может приводить к существеннойпотере точности при построении приближения.
Достоинством такого подхода является разрешимость задачи проверки включения 1 в 2 для регулярного 1 и 2 , являющегося однозначным контекстно-свободным языком [63]. Данный подход реализует инструмент Java String Analizer [30],являющийся анализатором строковых выражений в коде на Java.– Контекстно-свободное приближение: 1 является контекстно-свободнымязыком. Достоинством такого приближения является его бо́льшая точность, однако проверка включения одного контекстно-свободного языкав другой является неразрешимой в общем случае [63]. По этой причинепри использовании такого приближения будет получено неточное реше-26ние, так как потребуется применение эвристик. Данный подход реализованв инструменте PHPSA [29], предназначенном для проверки корректностидинамически формируемых программами на PHP выражений.Синтаксический анализ.
Данный подход основан на применении техниксинтаксического анализа для работы с динамически формируемыми выражениями. Благодаря этому, кроме проверки корректности выражений, становится возможным решение более сложных задач, требующих знаний о структуре выводаили работы с деревом разбора, таких как семантический анализ или трансформации. Ниже перечислены существующие на текущий момент варианты данногоподхода.– Абстрактный LR-анализ.
В исследованиях группы во главе с Kyung-GooDoh (Hanyang University, South Korea) предлагается комбинация анализапотока данных и синтаксического анализа на основе LALR(k) алгоритма, позволяющая строить множество LR-стеков для всех значений строкового выражения [26–28]. Так как задача проверки включения для двухконтекстно-свободных языков неразрешима, то представлено приближённое решение.
В работе [28] обоснована возможность семантического анализа на основе классического для LR-анализа механизма: атрибутныхграмматик [11] и выполнения семантических действий при свёртке продукций. Однако не до конца исследована эффективность данного подходапри работе с семантическими действиями, требующими больших ресурсовпри вычислении.– Синтаксический анализ регулярного множества. Для языка строится регулярная аппроксимация. Далее для построенной аппроксимации решаются задачи лексического и синтаксического анализа. Данный подход рассмотрен в работах [31, 32] и реализован в инструменте Alvor [64].
Данныйинструмент является плагином к среде разработки Eclipse и предоставляетподдержку встроенного SQL в Java: статический поиск ошибок, тестирование запросов в базе данных. Его достоинством является разделение обработки на независимые шаги: построение аппроксимации, лексический анализ, синтаксический анализ [32]. Это позволяет более гибко переиспользовать существующие реализации отдельных шагов и упрощает создание27нового инструмента на базе имеющихся. Использование атрибутных грамматик — классического для LR-анализа способа задания семантики — ипостроение леса разбора в рамках данного подхода отсутствует.1.5Обзор инструментов для работы со встроенными языкамиЗадачи анализа динамически формируемых строковых выражений возникаютв различных контекстах и используются для различных языков, что приводит кпоявлению разнообразных программных инструментов.Среди языков, используемых для линамически формируемых программ, одним из наиболее распространённых является SQL с его многочисленными диалектами.
При этом часто используется динамический SQL: генерация выражений на SQL в рамках кода на SQL (например в хранимых процедурах). Однаиз актуальных задач, при решении которой необходимо обрабатывать динамический SQL, — это миграция приложений баз данных. Для её решения существуетряд промышленных инструментов. В силу особенностей решаемой задачи насинтересуют инструменты для трансляции хранимого кода приложений баз данных. Самыми известными инструментами в данной области являются PL-SQLDeveloper [65], SwisSQL [66], SQL Ways [67]. Они применяются для трансляциихранимого SQL-кода, однако только SQL Ways обладает возможностью трансформации строковых SQL-запросов в ряде простых случаев. Динамически формируемые запросы со сложной логикой построения не поддерживаются современными промышленными инструментами.Далее рассмотрим инструменты, которые изначально ориентированы на решение различных задач анализа динамически формируемых выражений. Многие из них предназначены для предоставления поддержки встроенных языков винтегрированных средах разработки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
