• Простая связь по данным – значение ячейки A во входной точке блока влияет на значение ячейки B в выходной точке блока. Таким зависимостям соответствуют любые инструкции перемещения значения из одной ячейки в другую (например MOVE) и преобразования ячейки (например ADD)
• Косвенная связь по данным – адрес ячейки B в выходной точке блока зависит от значения ячейки A во входной точке блока; Таким зависимостям соответствуют операции с указателями, при которых адрес ячейки вычисляется на основании значения другой ячейки, например при работе с массивом: a[i] – адрес искомой ячейки памяти зависит от значения индекса i.

Рассмотрим подробнее преобразование «свёртка». Фактически требуется для всех входных и выходных ячеек, между которыми существует путь по рёбрам графа зависимостей добавить ребро в граф свёртки. Однако возникает проблема задания атрибута этого ребра. Таким образом, требуется:

1. Для каждой пары ячеек, одна из которых является входной, а другая выходной в графе зависимостей, найти все пути между ними.
2. Для каждого найденного пути на основе встречающихся в нём инструкций сгенерировать атрибут типа зависимости между входной и выходной ячейкой.
3. На основании же имеющегося атрибута, полученного при анализе прошлых путей и вновь созданного атрибута получить итоговый атрибут типа зависимости.

Алгоритм поиска путей в графе является стандартным, поэтому остановимся подробнее на 2 и 3 пункте. Рассмотрим различные виды путей типы атрибутов, им соответствующие.

• Путь из простых зависимостей. То есть входная переменная x участвовала в некоторых вычислениях, результатом которых явилось значение выходной переменной y. В этом случае атрибут, полученный на основании всего пути, соответствует простой зависимости y(x).
• Путь из простых зависимостей, в котором присутствует одна или несколько косвенных зависимостей. В этом случае атрибут, полученный на основании всего пути, соответствует косвенной зависимости y(x).

Из вышесказанного следует, что приоритет выставления атрибутов при анализе зависимостей следующий:

• Косвенная зависимость.
• Простая зависимость.

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

Пусть a – текущая выходная ячейка блока, b – текущая входная ячейка блока, а c и d – некоторые другие выходные ячейки блока. Пусть между ячейками с и b есть простая зависимость, а между ячейками d и b – зависимость косвенная. Пусть есть инструкция, реализующая простую зависимость a(c,d). Требуется определить атрибут зависимости a(b). Видно, что существует 2 пути из b в a: b – c – a и b – d – a. Причём первому пути соответствует атрибут простой зависимости, а второму – атрибут косвенной зависимости.

В этом случае итоговый атрибут будет соответствовать «объединению» этих двух типов зависимости. Очевидно, что в случае объединения атрибутов одного типа, итоговый атрибут будет равен каждому из исходных. Следовательно, атрибуты на рёбрах могут принимать три значения:

• атрибут простой зависимости
• атрибут косвенной зависимости
• атрибут объединения простой и косвенной зависимости.

Предлагается хранить зависимости выходных ячеек от входных в виде битовых масок, где отдельные биты соответствуют типам зависимостей. А объединённым зависимостям соответствуют группы выставленных битов. Это позволит эффективно добавлять новые типы зависимостей, не меняя модели.

В случае представления значения атрибута, как битовой маски, объединение атрибутов представляет собой просто выполнение побитового "или" над их масками.

Алгоритм построения свёрток зависимостей по заданному блоку инструкций реализован в виде компонента FurlMaker. Промежуточные результаты алгоритма в процессе его работы хранятся в специальном компоненте, DependencyContainerTree оптимизированном по скорости доступа с учётом специфики алгоритма. Окончательные результаты хранятся в компоненте CDependencyFurl, который аналогичен компоненту визуальных свёрток, но дополнительно хранит отображение входных элементов на выходные и наоборот с учётом видов зависимостей.

Основные методы алгоритма FurlMaker:

• analyzeMinstr() – проанализировать текущую микроинструкцию;
• removeLocals() – убрать из зависимостей временные ячейки (используются для промежуточного хранения значений);
• fillFurl() – Заполнение свёртки найденными зависимостями;
• addDependency() – Функция добавления зависимости;

Для визуализации свёрток зависимостей была использована сторонняя библиотека Microsoft GLEE. Так как библиотека была написана на С#, то для её использования в C++ проекте был написан специальный переходник с использованием промежуточного языка Managed C++.

Класс DependencyExtractor осуществляет извлечение требуемых зависимостей из компонента CDependencyFurl. Необходимость этого класса обусловлена тем, что для больших свёрток количество зависимостей может быть велико и для улучшения восприятия пользователь может выбрать, как ячейки, зависимости между которыми его интересуют, так и виды зависимостей.

3.3. Связывание интерфейсов среды TrEx со скриптовым языком

В качестве инструментального языка, при разработке среды TrEx был использован язык С++, что позволило добиться в критических местах кода должного уровня производительности. Однако с точки зрения пользователя среды она является «монолитом», обладающим фиксированным набором возможностей, и предоставляющим их средствами графического интерфейса. Разработка и встраивание собственных модулей-расширений способна решить эту проблему, однако такой подход сопряжен со значительными временными задержками, не приемлемыми для пользователя. Подходящим решением в данной ситуации является встраивание в среду интерпретатора скриптового языка, обеспеченного привязкой к методам и классам Common API.

В качестве кандидата на встраивание рассматривались следующие языки: Lua, Ch, Java/Javascript, Perl, Ruby. Были сформулированы следующие обязательные требования, которым должен удовлетворять скриптовый язык и его окружение.

• Возможность удобной работы с классами языка C++.
• Поддержка шаблонов.
• Перехват исключительных ситуаций.
• Наличие средств автоматизации для построения привязки.

В результате рассмотрения была выбрана связка Lua/SWIG. Ключевыми достоинствами выбранного решения является: открытый код, наличие сообщества, занимающегося развитием этих программных средств, малые накладные расходы на встраивание при использовании генератора кода привязки SWIG.

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

1. Тип number, соответствующий в стандартном Lua C-типу double, в TrEx является 64-битным знаковым целым.
2. Формат ввода чисел соответствует стандартному: число «10» воспринимается как десятичное 10, число «0x10» как десятичное 16, число «010» как восьмеричное 8. Формат вывода чисел всегда шестнадцатеричный, без префикса «0x».
3. Операция возведения в степень в силу слабой применимости для целых чисел заменена на «исключающее или».
4. Набор стандартных библиотек сохранен без изменений, за исключением библиотеки math, которая отключена по причине переопределения типа number.

При открытии трассы в ее контексте автоматически выполняется скрипт autoload.lua, расположенный в каталоге TrEx. Предоставляемый скрипт создает окружение, позволяющее получить доступ к элементам трассы в более простом виде, нежели при использовании C++-интерфейсов напрямую.

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

Таблица TrEx.Util содержит следующие два поля.

• TrEx.Util.loggerInstance хранит ссылку на объект Logger, позволяющий выводить сообщения в консоль и файл журнала.
• TrEx.Util.traceContext хранит ссылку на объект TraceContext открытой трассы.

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

Таблица TrEx.Trace содержит механизмы для работы с шагами трассы. Помимо получения количества шагов в трассе по ключу n, она позволяет обратиться к отдельному шагу по ключу, соответствующему его порядковому номеру. Помимо того, через ключ TrEx.Trace.position доступен номер выбранного пользователем шага.

Для доступа к декомпозиции на зависимости используется поле Dep объекта шага трассы, например TrEx.Trace[0].Dep. Данная таблица содержит количество зависимостей в ключе n, а также сами зависимости в виде объектов класса Dep по числовым ключам с 0 до n - 1.

Разбор на зависимости управляется флагами, содержащимися в TrEx.Trace.depFlags. В начальном состоянии флаги устанавливаются в значение 15, соответствующее наиболее полному набору флагов.

Рассмотрим пример использования TrEx.Trace.Dep: выводим все зависимости инструкции в шаге stepIndex (Рис. 2).

Таблица TrEx.Notepad предоставляет расширенные возможности вывода для скриптов с использованием окон «блокнотов». В каждом из таких блокнотов может содержаться список шагов и сопоставленной им текстовой информации с возможностью перехода к соответствующему шагу в трассе по двойному клику.

Для создания нового или доступа к уже существующему блокноту применяется индексированный доступ к таблице по имени блокнота (имя может являться произвольной строкой). Пример работы с блокнотом показан на Рис. 3.

local dumpDeps = function(stepIndex)
  local i
  
  -- Цикл по зависимостям.
  for i = 0, TrEx.Trace[stepIndex].Dep.n - 1 do
    -- Выводим номер зависимости и ее текстовый вид.
    print(i, TrEx.Trace[stepIndex].Dep[i])
  end
end

for i = 0, TrEx.Trace.n - 1 do
  -- Проверяем eax.
  if 0 == TrEx.Trace[i].eax then
    -- Добавляем в блокнот "Zero EAX".
    TrEx.Notepad["Zero EAX"]:print(i, "На этом шаге eax == 0")
  end

  -- Проверяем ebx.
  if 0 == TrEx.Trace[i].ebx then
    -- Добавляем в блокнот "Zero EBX".
    TrEx.Notepad["Zero EBX"]:print(i, "На этом шаге ebx == 0")
  end

  -- Если на каком-то шаге eax и ebx равны нулю одновременно, добавляем текст в оба блокнота
  -- и выделяем его красным (0x0000FF) цветом.
  if (0 == TrEx.Trace[i].eax) and (0 == TrEx.Trace[i].ebx) then
    -- Добавляем в оба блокнота красный текст.
    TrEx.Notepad["Zero EAX"]:cprint(i, "Причем ebx тоже 0!", 0x0000FF)
    TrEx.Notepad["Zero EBX"]:cprint(i, "Причем eax тоже 0!", 0x0000FF)
  end
end

В блокноте, таким образом, определены два метода: print(stepIndex, message) и cprint(stepIndex, message, color). В качестве color могут использоваться произвольные RGB-цвета.

4. Дальнейшие работы

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

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

Задача декомпиляции является естественным продолжением в поднятии абстракции при работе с низкоуровневым представлением программы. Ассемблерный листинг является нижней границей среди возможных статических представлений исследуемой программы. Верхней границей является представление в виде математической модели соответствующей проблемной области. Однако, даже задачу декомпиляция в традиционный язык программирования, такой как C, нельзя считать решенной. Известные декомпиляторы (Boomerang [5], DCC [6], REC [7] и Hex-Rays [8]) не всегда корректно восстанавливают структурные конструкции, языковые типы, затрудняются в распознавании библиотечных функций (за исключением Hex-Rays). Декомпиляция оптимизированной программы также нерешена – перечисленные декомпиляторы выдают результат, который либо не компи-лируется, либо работает некорректно, либо содержит ассемблерные вставки.

Разрабатываемый в ИСП РАН декомпилятор [9] в язык C, обладает развитыми возможностями в восстановлении типов. В ближайшее время стоит задача адаптация этого декомпилятора к среде TrEx, когда восстановление происходит не из исполняемого файла, а из внутреннего представления среды. Важной особенностью является то, что рассматриваемая программа не всегда разрабатывалась на языке C, потенциально возможно появление в трассе кода, написанного на языке ассемблера. Помимо того, исследуемая программа может содержать в себе результаты различных преобразований как с целью оптимизации, так и обфускации.

Еще одна смежная задача – выявление уязвимостей в бинарном коде. На протяжении ряда лет в ИСП РАН проводились работы, целью которых было выявление уязвимостей в исходном коде программ [10, 11]. Система выполняет поиск дефектов (ситуаций в исходном коде) в программах, написанных на Си и Си++, при помощи межпроцедурного анализа потока данных. Анализ выполняется по частям, что позволяет искать дефекты в программах неограниченного размера, а также в программах, полный набор исходного кода которых недоступен. Для обнаружения конкретных видов дефектов используются шаблоны ситуаций, в которых эти дефекты могут проявляться.

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

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

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

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

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

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

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

Назад Содержание Вперёд