ARM-декомпилятор

Задумавшись о «простеньком плагинчике» для исключения тупой ручной работы в IDA — для «трассировки констант», пришёл к выводу, что я изобрёл велосипеддекомпилятор, и что не такая уж это и сложная вещь — декомпилятор.

В какой-то момент я ещё нашёл страничку http://www.backerstreet.com/decompiler/creating_statements.php, и понял, что все мои мысли полностью соответствуют стандартной теории декомпиляции.

Начальный анализ

Потом стало ясно, что парсить вывод IDA (листинги) — занятие тяжкое и приносящее малый профит, и в случае ARM точно лучше использовать objdump, хотя он и не является рекурсивным дизассемблером. Вообще, в случае ARM всё ну очень просто, так как любая инструкция занимает 4 байта и всегда выровнена на границу 4 байт. Поэтому натравленный на файл objdump всегда дизассемблирует его корректно, только некоторые «инструкции», которые на самом деле не инструкции, нужно будет заменить на данные.

Поэтому сначала делаем начальный анализ:

• Дизассемблировать код objdump’ом и разобрать вывод на адреса, инструкции, их аргументы и комментарии — как уже сказано, это гораздо легче, чем парсить бешеные листинги из IDA.
• Представить адреса, которые очевидно читаются/пишутся, данными:
  • Взятые относительно PC и числа — сразу. Которые только читаются, можно сразу принять за константы и подставить в код (аналог LDR xx, =const в IDA).
  • Потом, уже в процессе декомпиляции, могут выявиться новые адреса с данными — нужно уметь их «сделать» данными в будущем. Чувствуете? Уже появляется «интерактивщина», аналогичная букве I в названии IDA.
• Выделяем очевидные функции:
  • Все константные адреса, на которые делается BL или BLX — это «ближние» (short) вызовы функций.
  • В будущем, при трассировке выражений, могут появиться ещё функции — нужно уметь их тоже «сделать» функциями. Ещё чуть-чуть интерактивщины.
• Разобрать код на непрерывные блоки, забыть про условные суффиксы.
• Построить граф ветвлений — литературное название также «Control Flow Graph», или «граф управляющей логики».
  • Граф тоже может меняться в процессе анализа.

Продолжение анализа

Далее начинается более сложный анализ:

• Пройтись по всем возможным ветвям выполнения, на каждом шаге сохраняя выражения для значений регистров и флагов сравнений, транслировать инструкции в выражения, а условия EQ/NE/… — в выражения сравнений. Наибольшая проблема здесь — циклы.
• Отобразить ветвления либо на if’ы, либо на циклы, либо, на крайний случай, на goto («кривые» конструкции).
• Можно выделять ещё не выделенные функции — ими можно сделать всё, на что (ещё?) не найдены BL-переходы, но что оканчивается записью LR в PC (BX LR / MOV PC, LR / LDM …), а начинается с инструкции, к которой нет перехода с предыдущей. То есть когда предыдущая — либо данные (не инструкция), либо когда она содержит безусловный переход, обходящий следующую инструкцию. NOP’ы между предыдущей и началом функции не учитывать.
• Можно выделять дальние вызовы (long call) функции — то есть, вызовы, в которых адрес функции сначала грузится в регистр, а потом вызывается из регистра; это несложно, потому что сложных выражений отслеживать не надо, в качестве адреса используется константа.
• Можно осилить даже часть непрямых вызовов функций (по хз откуда взятому адресу).
• Найти все ASCII-строки в бинарнике, и подставить в обращения к ним.

Выделение блоков

Далее нужно перейти к выделению блоков — то есть, циклов и условных операторов — тому, что обычно называют «структурированием», то есть воссозданием программы из линейного листинга:

Циклы

У любого цикла есть точка входа, на которую можно поставить метку «continue», так как оператор «continue» как раз на неё и переходит, и стандартная точка выхода, на которую можно аналогично поставить метку «break». Внутри цикла переходы на точки входа и выхода для удобочитаемости нужно заменять на continue и break.

Цикл:

• Начинается с какого-либо узла, являющегося к тому же единственной точкой входа в этот цикл.
• Должен включать в себя все пути, ведущие в любой внешний узел, и возвращающиеся в любой внутренний узел (обобщённое требование цикла).
• Если добавили какой-то узел, и получили две точки входа, то этот узел не принадлежит циклу.
• Если добавили какой-то узел и единственная точка входа изменилась, идём нафиг — цикл из изначального узла не растёт.

Циклы бывают с предусловием и с постусловием. Цикл с предусловием:

С постусловием:

Условные операторы

Условный оператор определить легко: если что-то ветвится и это не ветвление, реализующее цикл (то есть не предусловие и не постусловие само по себе), это условный оператор :)

Транслировать его следует так:

• Ищем точку сбора всех веток, выходящих из начального узла (узел, в котором все они объединяются).
• Залезаем в каждую ветку, всё обрабатываем точно так же, как до этого, и точно так же (в обработке линейных участков и циклов тоже помечаем).
• Помечаем пройденные узлы как обработанные.
• Когда где-то видим уже обработанный узел, заменяем переход к нему на goto. То есть, if «без дублирования» кусков веток будет «нормальным», без goto.

Пример «плохого» if’а: 0->1->3->4, 0->2->3, 0->4, 0->5->4.

Декомпилировать его можно как-то так:

if(_1) { 1; 3; }
else if(_2) { 2; goto 3; }
else if(_5) { 5; }
4;

Данные декомпиляции

Что есть у декомпилятора:

• На каждый dword либо метка «данные», либо «код» + разобранная инструкция.
• На каждую инструкцию - блок, к которому она принадлежит. Тупо номер блока.
• Список точек входа, изначально содержащий единственную точку входа в программу.
• Список функций — по сути, адресов, с которых они начинаются.
• Хеш использования переменных, функций и т. п. По сути, каждый адрес может использоваться другими адресами.
• Ориентированный граф ветвлений, состоящий из непрерывных блоков выполнения и переходов между ними.
• На каждую инструкцию внутри блока — отслеженные с начала функции либо всей программы выражения.
• На каждый блок — входные и выходные значения регистров и т. п., относительные входных + транслированное тело.
• Список ASCII-строк с их адресами.

Всё это в процессе анализа может меняться и дополняться.

Отслеживание данных

Отслеживать данные и строить граф ветвлений нужно вместе, а начинать следует сразу после разбора objdump’овского листинга с какой-нибудь точки входа. При этом для каждого непрерывного блока нужно сохранять входные значения и выходные, относительные входных. Выражения, порождаемые и используемые только внутри блока, можно подставлять сразу. Часть выражений, которые после выхода из блока не будут использоваться, можно забыть.

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

Чтобы отслеживать данные, желательно иметь хотя бы некоторый движок, который был бы в состоянии упрощать выражения. К счастью, извращений типа функции, которая по номеру регистра и значению в него что-то пишет, в сишных программах быть не должно, потому что есть EABI — соглашение по вызову функций, но вот в память запись может идти и по адресу, который сам является выражением. И не просто может, а может очень часто.