ARM-декомпилятор — различия между версиями

Материал из YourcmcWiki
Перейти к: навигация, поиск
м (Этап 2 — Разбиение на блоки и анализ статических ветвлений)
м (Этап 2 — Разбиение на блоки и анализ статических ветвлений)
Строка 61: Строка 61:
 
== Этап 2 — Разбиение на блоки и анализ статических ветвлений ==
 
== Этап 2 — Разбиение на блоки и анализ статических ветвлений ==
  
@TODO.
+
На этом этапе программу нужно представить в виде набора блоков, то есть, последовательностей команд, всегда выполняющихся друг за другом, и переходов между ними. То, что получится, называется «control flow graph», или граф ветвлений.
 +
 
 +
На блоки ARM-программу разбить легко, хотя есть нюансы — в ARM-коде почти все инструкции могут быть условными. Соответственно, каждая последовательность условных команд с одним и тем же суффиксом — блок, а все условные переходы генерируются как раз из суффиксов.
 +
 
 +
Чтобы выделить блоки, нужно сначала пройтись по всему бинарю и на каждый адрес сохранить флаги, а потом опять пройтись, но уже рекурсивно и начиная с точки входа программы. Новый блок в позиции нужно начать, если (флаг EPI_N):
 +
* Если на этот адрес обнаружены переходы.
 +
* Если по предыдущему адресу другой условный суффикс.
 +
* Если по предыдущему адресу условная инструкция, меняющая флаги.
 +
* Если по предыдущему адресу переход без ссылки (то есть переход, но не вызов функции).
 +
 
 +
Также нужно сохранить информацию о переходе:
 +
* Со ссылкой/без ссылки.
 +
* Тип адреса:
 +
** Известный и вычислен
 +
** Динамический регистровый
 +
** Динамический из памяти (<tt><nowiki>LDR PC, [...]</nowiki></tt>)
 +
** Возврат из функции
 +
 
 +
Переходы в ARM могут инициироваться следующими инструкциями:
 +
* B / BX / BL / BLX
 +
* MOV PC, …
 +
* Арифметико-логические инструкции типа ADD PC, …
 +
* LDR PC, […]. Перед этой инструкцией часто встречается MOV LR, PC — тогда такой переход надо считать вызовом функции.
 +
* LDMxx … {..PC..} / POP {..PC..}. Это, кстати, почти наверняка возврат из функции, компилятор совмещает его с восстановлением значений регистров из стека.
 +
 
 +
Отследить на этом этапе '''все''' переходы мы не сможем, потому что адрес может вычисляться более или менее динамически, а мы пока что не смотрим на данные. Однако есть два плюса:
 +
* Большинство «динамических» переходов — вызовы функций. Управляющие конструкции, как правило, состоят из ближних переходов.
 +
* Даже если мы не знаем цель перехода, сам факт наличия перехода всё равно нам известен.
 +
Поэтому разбиение на блоки будет почти наверняка корректным. Единственное, что может повлиять на разбиение — неизвестный переход в середину блока.
 +
 
 +
Далее нужно разобраться с условными суффиксами. Тут есть нюансы:
 +
# Как отобразить на граф последовательность условных блоков с разными суффиксами?
 +
# Как отобразить на граф переход на условную инструкцию?
 +
 
 +
Для решения (1) нужно добавить все переходы, «перескакивающие» один или несколько условных блоков, начиная с последней безусловной инструкции. Для этого при обработке нужно сохранять номера условных блоков + номер последнего безусловного, и при встрече нового блока добавлять переходы на этот новый блок с каждого из сохранённых с условием, равным конъюнкции отрицаний суффиксов блоков, которые мы перескакиваем, и суффикса нового блока, если он условный.
 +
 
 +
Для решения (2) нужно действовать похоже — переход на условную инструкцию заменяется на набор переходов, которые могут перескакивать условные инструкции. Правда, так мы всё равно ничего не сможем сделать, если первая инструкция функции — условная. В такой ситуации можно только вводить «псевдо-блок», не включающий в себя ни одной инструкции, в начало функции. Но такого кода компиляторы, к счастью, не генерируют, поэтому если не пытаться декомпилировать вирусы и кряки — всё будет нормально.
 +
 
 +
В результате все инструкции переходов на графе у нас будут безусловными, а условными могут быть только переходы к условным блокам инструкций.
  
 
Пример графа ветвлений с этого этапа:
 
Пример графа ветвлений с этого этапа:

Версия 12:41, 18 апреля 2011

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

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

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

Этап 1 — Дизассемблировать файл целиком

Удобно делать так — дизассемблировать код objdump’ом и разобрать вывод на инструкции и их аргументы — как уже сказано, это гораздо легче, чем парсить бешеные листинги из IDA.

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

Внутри дизассемблера код удобно представлять в специальном виде, который всё ещё бинарный, но удобный для анализа. Каждая инструкция превращается в:

  • Имя инструкции без условных суффиксов и суффикса «s» (adds/movs/…). С запасом 8 байт.
  • Байт условий: S000CCCC.
    • Бит S = 1, если инструкция меняет флаги — либо явное «s» adds/movs/…, либо инструкции, всегда меняющие флаги — cmp, cmn, tst, teq.
    • Биты CCCC — номер условия или 0, если выполняется всегда. Номера условий см.ниже.
  • Опционально — байт с количеством аргументов (хотя их самый максимум 6 в инструкциях сопроцессора).
  • Аргументы.
  • Все поля можно добивать нулями до фиксированных размеров.

Формат аргумента:

  • Непосредственный аргумент: 'I', dword.
  • Регистр, м.б со сдвигом: 'R', 0SSSRRRR, [ N10IIIII | N000RRRR ]. По порядку:
    • RRRR — номер регистра (0-15)
    • SSS — номер функции сдвига или 000, если без сдвига, тогда аргумент занимает только 2 байта.
    • N — если дописан флаг ! (бывает по сути только в LDM/STM)
    • IIIII — непосредственное значение сдвига (0-32)
    • RRRR — номер регистра (0-15), на значение которого сдвигаем базовый
  • Обращение к памяти: 'M', 0000RRRR, M0BA00IR, [ (0SSSRRRR, [ N10IIIII | N000RRRR ]) | IIIIIIII 0000IIII ]. По порядку:
    • RRRR — номер базового регистра (0-15)
    • M — если смещение со знаком «-»
    • B — пре-индексированное обращение (увеличить базовый регистр на смещение, потом обратиться)
    • A — пост-индексированное обращение (обратиться, потом увеличить базовый регистр на смещение)
    • I — если смещение непосредственное. Тогда IIIIIIII 0000IIII — 12-битное значение смещения (0-4095).
    • R — если смещение регистровое. Тогда последующие два байта полностью эквивалентны формату регистрового аргумента (см. предыдущий пукт).
  • Список регистров для LDM/STM: 'L', 16 бит маска включения регистров.
  • Обращение к спец.регистру (регистры сопроцессора и т. п.): 'X', 8 бит номер спец.регистра.

Номера условий удобно использовать не какие-нибудь, а такие, чтобы изменением одного бита условие можно было обратить. У меня сейчас сделаны свои номера, можно их переделать на стандартные ARM’овские: 0..13 это eq, ne, cs, cc, mi, pl, vs, vc, hi, ls, ge, lt, gt, le. А можно и не переделывать. Смысл «моих» номеров в том чтобы это было более человекочитаемо. Младший бит = 1, если это одно из сравнений на >/</>=/<=, знаковых или беззнаковых. Тогда биты выглядят как GUE1. G = Greater, U = Unsigned, E = allow Equal. Не сравнения - младший бит=1 и остаются только eq/ne (N010), vs/vc (N100), pl/mi (N110). Бит N = Negate, т.е. отрицание. Итак, получаются следующие номера:

Код xx Значение
Сравнения
1111 cs беззнаковое >=
0111 cc беззнаковое <
1101 hi беззнаковое >
0101 ls беззнаковое <=
1011 ge знаковое >=
0011 lt знаковое <
1001 gt знаковое >
0001 le знаковое <=
Остальные
0010 eq ==
1010 ne  !=
0100 vs переполнение
1100 vc нет переполнения
0110 mi результат < 0
1110 pl результат >= 0

Этап 2 — Разбиение на блоки и анализ статических ветвлений

На этом этапе программу нужно представить в виде набора блоков, то есть, последовательностей команд, всегда выполняющихся друг за другом, и переходов между ними. То, что получится, называется «control flow graph», или граф ветвлений.

На блоки ARM-программу разбить легко, хотя есть нюансы — в ARM-коде почти все инструкции могут быть условными. Соответственно, каждая последовательность условных команд с одним и тем же суффиксом — блок, а все условные переходы генерируются как раз из суффиксов.

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

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

Также нужно сохранить информацию о переходе:

  • Со ссылкой/без ссылки.
  • Тип адреса:
    • Известный и вычислен
    • Динамический регистровый
    • Динамический из памяти (LDR PC, [...])
    • Возврат из функции

Переходы в ARM могут инициироваться следующими инструкциями:

  • B / BX / BL / BLX
  • MOV PC, …
  • Арифметико-логические инструкции типа ADD PC, …
  • LDR PC, […]. Перед этой инструкцией часто встречается MOV LR, PC — тогда такой переход надо считать вызовом функции.
  • LDMxx … {..PC..} / POP {..PC..}. Это, кстати, почти наверняка возврат из функции, компилятор совмещает его с восстановлением значений регистров из стека.

Отследить на этом этапе все переходы мы не сможем, потому что адрес может вычисляться более или менее динамически, а мы пока что не смотрим на данные. Однако есть два плюса:

  • Большинство «динамических» переходов — вызовы функций. Управляющие конструкции, как правило, состоят из ближних переходов.
  • Даже если мы не знаем цель перехода, сам факт наличия перехода всё равно нам известен.

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

Далее нужно разобраться с условными суффиксами. Тут есть нюансы:

  1. Как отобразить на граф последовательность условных блоков с разными суффиксами?
  2. Как отобразить на граф переход на условную инструкцию?

Для решения (1) нужно добавить все переходы, «перескакивающие» один или несколько условных блоков, начиная с последней безусловной инструкции. Для этого при обработке нужно сохранять номера условных блоков + номер последнего безусловного, и при встрече нового блока добавлять переходы на этот новый блок с каждого из сохранённых с условием, равным конъюнкции отрицаний суффиксов блоков, которые мы перескакиваем, и суффикса нового блока, если он условный.

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

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

Пример графа ветвлений с этого этапа:

DisasmExampleGraph.svg

Этап 3 — Отслеживание данных в рамках блоков

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

  • Представить адреса, которые очевидно читаются/пишутся, данными:
    • Взятые относительно 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.

Цикл:

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

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

[svg]

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

[svg]

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

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

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

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

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

[svg]

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

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

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

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

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

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

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

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

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

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