Научные публикации

Метод разбора исходных текстов по упрощенной грамматике языка

Введение

Данная статья содержит начальные представления о разрабатываемом специальном комплексе, предназначенном для контроля уязвимостей программ. Данный комплекс работает с исходными текстами и был создан с целью повышения эффективности существующих методов контроля. Существующие разные методы предполагают прямой поиск заданных выражений, другие используют отладочную информацию, третьи справедливо считают, что для корректного исследования программы необходимо выполнить полный лексический и синтаксический анализы. При разработке данного комплекса был учтен опыт практического применения этих методов и в данной статье предлагается исследование метода разбора по упрощенной грамматике языка. Для эксперимента был выбран язык ANSI C (99) по нескольким причинам. Среди них те, что язык широко применяется в промышленности, достаточно прост для разбора и что он обладает низкой защищенностью.

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

Основная часть

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

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

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

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

Весь список достаточно велик для приведения его здесь и видимо в этом нет никакой необходимости, так как при более подробном рассмотрении пришлось бы переписывать полную грамматику языка. Именно такой подход был использован в разработке анализатора, основывающегося на формальных грамматиках. Надо отметить, что технически он наиболее совершенен по сравнению с другими подходами, но имеет достаточно трудную реализацию в связи с тем, что для каждого (пусть даже такого специфического языка, как “Avenue”) необходимо написать полную грамматику, что может занять больше времени, чем даже ручной анализ. Для того, чтобы не идти таким сложным путем, несколько лет назад в анализаторе «ST» (разработка одного из ведущих российский специалистов по безопасности В.Н.Стрельца) был реализован подход, основывающийся на отладочной информации. Суть этого подхода заключается в следующем: «Visual Studio» формирует во время компиляции специальный файл, в котором содержится отладочная информация. Этой информации достаточно для того, чтобы выполнить анализ по 3-му уровню контроля недекларированных возможностей соответственно руководящему документу. Другой, достаточно простой подход используют английские и американские исследователи Джон Виега (JohnViega), Гари МакГроу (Gary McGraw) и др. В своей статье о статическом сканере безопасности «ITS4» они приводят аргументы в пользу упрощенной грамматики языка и доказывают её эффективность. Сканер безопасности «ITS4» предназначен для контроля таких ошибок, как переполнения буфера, утечка памяти, ошибки в работе механизма указателей, ошибки инициализации создаваемых объектов и др. Он успешно находит некорректное использование стандартных функций вроде strcpy, strcut и sprintf используя предложенную методику. Фактически, грамматика языка, используемая сканером, должна содержать правила объявления функций, переменных, указателей и некоторые другие. Этот подход позволяет им безошибочно находить необходимые места текста и анализировать их степень уязвимости.

В наших исследования было решено использовать как опыт использования формальных грамматик, так и опыт зарубежных специалистов. Вернемся к тому, что перед разбором исходных текстов были выбраны только те файлы, которые действительно входят в проект. А также, отметим, что все из отобранных файлов компилируются. Это последнее обстоятельство позволяет нам положить основополагающее условие опыта – для исходного текста, подлежащего лексическому и синтаксическому анализу, существует такая однозначная контекстно-свободная грамматика, которая порождает язык, являющийся либо подмножеством исходного языка, либо совпадающий с ним. Под исходным языком в нашем опыте понимается стандарт ANSI C (99), но это лишь частный случай, на самом деле им может быть любой существующий на сегодняшний день язык программирования. В таком случае, мы можем построить такой синтаксический анализатор, который будет работать на основе только тех структурных правил языка, которые используются в текстах разбираемой программы.

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

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


Рисунок 1 – Упрощенная схема комплекса контроля уязвимостей

Некоторые принципы взаимодействия модулей целесообразно рассмотреть ниже. Исходные тексты (см. № 12 на рис. 1) исследуются на наличие избыточности в модуле №9 (см. рис. 1). Те файлы, которые были отобраны, как «используемые» участвуют в дальнейшем анализе, а избыточные файлы помечаются в базе данных (БД, см. № 10 на рис. 1). Файлы попадают на вход модуля разбора исходных текстов (см. № 1 на рис. 1). Именно методы, применяемые в данном модуле исследуются в данной статье. Информация о файлах сохраняется после разбора в БД, после чего используется на стадии статического анализа (см. № 2 на рис. 1). Статический анализ предназначен для исследования исходного текста программы на соответствие стандартам программирования, на наличие дефектов и уязвимостей, в частности, программных закладок. Подготовка к динамическому анализу реализуется в модуле вставки датчиков (см. № 4 на рис. 1). Датчики вставляются в каждый линейный участок, информация о которых хранится в БД, заполненной после разбора исходных текстов. Версия исходных текстов проекта со вставленными датчиками называется лабораторной (см. № 6 на рис. 1). Последовательность сработавших датчиков формирует «трассу» программы (см. № 11 на рис. 1), которая затем попадает на вход модуля динамического анализа (см. № 14 на рис. 1). Блок № 13 (см. рис. 1) формирует отчеты по результатам статического и динамического анализа (список функций, связей, переменных, и т.п. ). В блоках №№ 5, 7, 8 (см. рис. 1) показаны некоторые модули, теоретически входящие в процесс статического анализа, но фактически реализованы, как отдельные программные модули. Среди них соответственно «Модуль построитель блок-схем», «Модуль контроля уязвимостей из БД» и «Модуль обнаружения пассивных программных закладок».

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


Рисунок 2 – Концептуальная схема разбора исходных текстов

Исходные тексты (см. № 7 на рис. 2), которые не являются избыточными и собираются в проект, попадают на вход лексического анализатора (см. № 4 на рис. 2). В результате лексического разбора, исходные тексты представляются в виде множества лексем (см. № 5 на рис. 2) с соответствующими им атрибутами. Терминальный словарь (см. № 1 на рис. 2), на стадии лексического анализа, способствует выделению лексемы в тексте. Словарь формируется исследователем самостоятельно, либо экспортируется ранее созданный. Инструмент, позволяющий сформировать словарь для какого-либо языка, показан на рис.2 под номером 2 – «Редактор порождающих правил и словаря». Данный инструмент позволяет расширять или сокращать список терминальных символов, в зависимости от необходимости. Теоретически, необходимость может состоять в прикладном использовании, например, если исследуемые исходные тексты написаны на узкоспециализированном языке, например, «Avenue », то при определенных условиях может отсутствовать необходимость вводить все терминальные символы из которых формируется язык. Таким условием, например, может быть небольшой объем исходных текстов, в которых набирается десяток терминальных символов. В таком случае может оказаться целесообразным сформировать подобный список вручную и затем его использовать для создания множества порождающих правил (см. № 3 на рис. 2). Множество правил построения предложений языка порождают схему грамматики. Полная схема включает в себя все правила, позволяющие сформировать множество конечных цепочек терминального алфавита (словарь) – т.е. конечный язык. Редактор позволяет исследователю самостоятельно сформировать порождающие правила. На рис. 3 показана обобщенная схема работы модуля «Редактор порождающих правил и словаря».


Рисунок 3 – Схема получения упрощенной грамматики языка

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

  • 1) Исследователь определяет язык программирования исходных текстов и формирует терминальный словарь (см. № 6 на рис.3).

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

  • 2) Исследователь берет для анализа те файлы, которые успешно компилируются (см. № 10 на рис.3).

    Это гарантирует то, что все цепочки терминальных символов (исходные тексты) сформированы посредством некоторого множества порождающих правил, которое в свою очередь является подмножеством правил полной грамматики языка. Допустим, в полной грамматике существует 1000 различных правил вывода цепочек. А в исходных текстах используется мощность языка всего лишь на 30% т.е. реализовано всего 300 различных цепочек. Если по ним составить выводящие правила, то мы получим упрощенный вариант правил, характерный именно для этих исходных текстов. Данный способ может быть удобен в двух основных случаях: грамматика языка отсутствует и необходимо формировать о самого начала; грамматика языка имеется, но устаревшая, требующая доработки. В первом случае, упрощенная грамматика позволяет избежать формирования полной схемы. Во втором случае позволяет избежать конфликтов, новых правил со старыми правилами.

  • 3) Формируются лексемы.

    Исходные тексnы обрабатываются лексическим анализатором (см. № 7 на рис. 3), в результате чего формируется массив лексем (см. № 4 на рис. 3). Тип каждой лексемы определяется и затем все типы выстраиваются в соответствии с последовательностью, описанной в исходных текстах. Например, если в программе есть строчка объявления переменной: «int a;», то последовательность типов лексем будет выглядеть так: «Type ID;», где «Type» – это «тип данных», «ID» - последовательность латинских букв, не являющихся служебным словом и удовлетворяющая правилам составления идентификатора. Вся эта информация отображается в окне модуля «Обозреватель типов лексем исходного текста» (см. № 2 на рис.3)..

  • 4) Формируется множество порождающих правил.

    Порождающие правило формируется исследователем вручную на основе последовательности типов лексем. Например, для последовательности типов «Type ID;» будет сформировано такое правило:

    «Редактор порождающих правил» (см. № 3 на рис.3) позволяет создавать и изменять набор правил. Множество порождающих правил (см. № 5 на рис.3) формируется по результатам проработки исходных текстов исследователем.

  • 5) Формирование конечной грамматики.

    Модуль «Компилятор грамматики» (см. № 8 на рис.3) приводит набранную грамматику к удобному для автоматической обработки виду и сохраняет в отдельный файл, который и формирует упрощенную грамматику языка (см. № 9 на рис.3 и № 3 на рис.2).

Компоненты модуля, выполняющего разбор исходных текстов (см. № 1 на рис.1), можно представить в виде двух групп. Первая группа – это компоненты, изменяемые при исследовании нового языка. Например, «терминальный словарь», «множество порождающих правил», «массив лексем» и «упрощенная грамматика языка». Т.е. фактически это входные данные, которые изменяются вместе с исследуемыми исходными текстами. Вторая группа – это алгоритмы, остающиеся неизменными при новых исследованиях. Например, при исследовании программ, написанных на языках, для которых отсутствует сформированный словарь и набор порождающих правил. К таким компонентам относятся программы: «лексический анализатор», «Обозреватель типов лексем исходного текста», «Редактор терминального словаря», «Редактор порождающих правил» и «Компилятор грамматики». В результате, получаем инструмент, который позволяет проводить разбор и анализ программ, написанных на различных языках.

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

Эксперимент, проводимый при аппробации методика анализа, заключается в следующем. Целью является определить корректность методики анализа исходных текстов по упрощенной грамматике языка. Файлы с исходными текстами подаются на вход анализатору, над ними производятся лексический, синтаксический и статический анализы, в результате чего в БД сохраняется определенная информация . Среди этой информации имеются сведения о функциях, линейных участках, переменных и связях между ними. Критерием правильности выполнения анализа исходных текстов, является соответствие списка функций, линейных участков и переменных действительному состоянию в исходных текстах. Исходными условиями следует считать нижеперечисленные:

  • 1) 1539 исходных файлов, написанных на языке ANSI C (99);
  • 2) все файлы компилируются и собираются в конечные исполняемые файлы;
  • 3) в исходных текстах отсутствуют правила не учтенные в грамматике
  • 4) компилятор «Watcom C 10.6»;
  • 5) среда компиляции - операционная система реального времени «QNX» версии 4.25;
  • 6) среда анализа – MS Windows XP (SP2) + драйвер поддержки файловой системы «ext2»;

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

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

Результаты, полученные на первом этапе, были записаны в БД в виде таблиц. Концептуальное представление таблиц можно видеть на примере (см. таблицу).


Таблица 1 - Пример формата представления данных в БД

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

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

На основании этого можно сделать вывод, о возможном применении упрощенной грамматики при анализе исходных текстов.

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

Заключение

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

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

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