Изменения

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

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

== Этап 1 — Дизассемблировать файл целиком == Удобно делать так — дизассемблировать код objdump’ом и разобрать вывод на инструкции и их аргументы — как уже сказано, это гораздо легче, чем парсить бешеные листинги из IDA. В случае ARM это самое простое, так как любая инструкция занимает 4 байта и всегда выровнена на границу 4 байт. Поэтому рекурсивный дизассемблер, учитывающий переходы, нам нафиг не нужен, и натравленный на файл objdump всегда дизассемблирует его корректно. Только потом нужно будет определить, что некоторые «инструкции», которые на самом деле не инструкции, действительно не инструкции. Внутри дизассемблера код удобно представлять в специальном виде, который всё ещё бинарный, но удобный для анализа. Каждая инструкция превращается в:* Имя инструкции '''без''' условных суффиксов и суффикса «s» (adds/movs/…). С запасом 8 байт.* Байт условий: <tt>S000CCCC</tt>.** Бит <tt>S</tt> = 1, если инструкция меняет флаги — либо явное «s» adds/movs/…, либо инструкции, всегда меняющие флаги — cmp, cmn, tst, teq.** Биты <tt>CCCC</tt> — номер условия или 0, если выполняется всегда. Номера условий см.ниже.* Опционально — байт с количеством аргументов (хотя их самый максимум 6 в инструкциях сопроцессора).* Аргументы.* Все 3 имеют поля можно добивать нулями до фиксированных размеров. Формат аргумента:* Непосредственный аргумент: <tt>'I', dword</tt>.* Регистр, м.б со сдвигом: <tt>'R', 0SSSRRRR, [ N10IIIII | N000RRRR ]</tt>. По порядку:** <tt>RRRR</tt> — номер регистра (0-15)** <tt>SSS</tt> — номер функции сдвига или 000, если без сдвига, тогда аргумент занимает только 2 байта.** <tt>N</tt> — если дописан флаг ! (бывает по одной точке входасути только в LDM/STM)** <tt>IIIII</tt> — непосредственное значение сдвига (0-32)** <tt>RRRR</tt> — номер регистра (0-15), на значение которого сдвигаем базовый* Обращение к памяти: <tt>'M', 0000RRRR, M0BA00IR, [ (0SSSRRRR, [ N10IIIII | N000RRRR ]) | IIIIIIII 0000IIII ]</tt>. ТПо порядку:** <tt>RRRR</tt> — номер базового регистра (0-15)** <tt>M</tt> — если смещение со знаком «-»** <tt>B</tt> — пре-индексированное обращение (увеличить базовый регистр на смещение, потом обратиться)** <tt>A</tt> — пост-индексированное обращение (обратиться, потом увеличить базовый регистр на смещение)** <tt>I</tt> — если смещение непосредственное.еТогда <tt>IIIIIIII 0000IIII</tt> — 12-битное значение смещения (0-4095). ** <tt>R</tt> — если смещение регистровое. Тогда последующие два байта полностью эквивалентны формату регистрового аргумента (см. предыдущий пукт).* Список регистров для LDM/STM: <tt>'L'</tt>, 16 бит маска включения регистров.* Обращение к спец.регистру (регистры сопроцессора и т. п.): <tt>'X'</tt>, 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. Остальные суффиксы: младший бит=0 и остаются только eq/ne (N010), vs/vc (N100), pl/mi (N110). Бит N = Negate, т.е. отрицание. Итак, получаются следующие номера:<tab sep=bar class="wikitable sortable" head="top">Код | 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 | результат < 01110 | pl | результат >= 0</tab> == Этап 2 — Разбиение на блоки и анализ статических ветвлений == На этом этапе программу нужно представить в виде набора блоков, то есть, последовательностей команд, всегда выполняющихся друг за другом, и переходов между ними. То, что получится, называется «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) нужно действовать похоже — переход на условную инструкцию заменяется на набор переходов, которые могут перескакивать условные инструкции. Правда, так мы всё равно ничего не разветвляетсясможем сделать, если условной будет первая инструкция '''функции''' — функция должна представлять из себя единицу с одной точкой входа. В такой ситуации можно только вводить «псевдо-блок», не включающий в себя ни одной инструкции, в начало функции. Но такого кода компиляторы, к счастью, не генерируют, поэтому если не пытаться декомпилировать вирусы и кряки — всё будет нормально. В результате все инструкции переходов на графе у нас будут безусловными, а условными могут быть только переходы к условным блокам инструкций. Пример графа ветвлений с этого этапа: [[Файл:DisasmExampleGraph.svg|640px]] == Этап 3 — Отслеживание данных в рамках блоков == == Начальный анализ == * циклПредставить адреса, которые очевидно читаются/пишутся, данными: если через текущий узел проходит цикл** Взятые относительно PC и числа — сразу. Которые только читаются, добавляем можно сразу принять за константы и подставить в него этот циклкод (аналог <tt>LDR xx, потом добавляем =const</tt> в 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. Цикл:* Начинается с какого-либо узла, являющегося к тому же единственной точкой входа в этот цикл.* Должен включать в себя все пути, ведущие в любой внешний узел раздваивается , и через него возвращающиеся в любой внутренний узел (''обобщённое требование цикла'').* Если добавили какой-то узел, и получили две точки входа, то этот узел не проходит принадлежит циклу.* Если добавили какой-то узел и единственная точка входа изменилась, идём нафиг — циклиз изначального узла не растёт. Циклы бывают с предусловием и с постусловием. Цикл с предусловием: <graph>digraph G { continue->1->2->continue; continue->break; }</graph> С постусловием: <graph>digraph G { continue->1->continue; 1->break; }</graph> === Условные операторы === Условный оператор определить легко: если что-то ветвится и это не ветвление, можно добавить реализующее цикл (то есть не предусловие и не постусловие само по себе), это условный оператор :) Транслировать его следует так:* Ищем точку сбора всех веток, выходящих из начального узла (узел, в котором все они объединяются).* Залезаем в каждую ветку, всё обрабатываем точно так же, как до этого, и точно так же (в обработке линейных участков и циклов тоже помечаем).* Помечаем пройденные узлы как обработанные.* Когда где-то видим уже обработанный узел, заменяем переход к нему дочерниена goto. То есть, if «без дублирования» кусков веток будет «нормальным», без goto. Пример «плохого» if’а: 0->1->3->4, 0->2->3, 0->4, 0->5->4. <graph>digraph G { 0->1->3->4; 0->2->3; 0->4; 0->5->4; }</graph> Декомпилировать его можно как-то так:<code-c>if(_1) { 1; 3; }else if(_2) { 2; goto 3; }else if(_5) { 5; }4;</code-c> == Данные декомпиляции == Что есть у декомпилятора: * На каждый dword либо метка «данные», либо «код» + разобранная инструкция.* На каждую инструкцию — блок, к которому она принадлежит. Тупо номер блока.* Список точек входа, изначально содержащий единственную точку входа в программу.* Список функций — по сути, адресов, с которых они начинаются.* Хеш использования переменных, функций и т. п. По сути, каждый адрес может использоваться другими адресами.* Ориентированный граф ветвлений, состоящий из непрерывных блоков выполнения и переходов между ними.* На каждую инструкцию внутри блока — отслеженные с начала функции либо всей программы выражения.* На каждый блок — входные и выходные значения регистров и т. п., относительные входных + транслированное тело.* Список ASCII-строк с их адресами. Всё это в процессе анализа может меняться и дополняться. == Отслеживание данных == Отслеживать данные и строить граф ветвлений нужно вместе, а начинать следует сразу после разбора objdump’овского листинга с какой-нибудь точки входа. При этом для каждого непрерывного блока нужно сохранять входные значения и выходные, относительные входных. Выражения, порождаемые и используемые только внутри блока, можно подставлять сразу. Часть выражений, которые после выхода из блока не будут использоваться, можно забыть. Выделять циклы и условные операторы на этом этапе ещё не нужно, потому что граф ветвлений может поменяться в процессе анализа, а от интерпретации циклов и условных операторов зависят и окончательные выражения. Правда, нужно иметь ввиду, что после выделения блоков могут появиться и новые переходы, влияющие и на граф и снова на циклы и т. п., но в основном такие переходы будут, скорее всего, вызовами функций, поэтому пока что можно сильно не заморачиваться. Чтобы отслеживать данные, желательно иметь хотя бы некоторый движок, который был бы в состоянии упрощать выражения. К счастью, извращений типа функции, которая по номеру регистра и значению в него что-то пишет, в сишных программах быть не должно, потому что есть EABI — соглашение по вызову функций, но вот в память запись может идти и по адресу, который сам является выражением. И не просто может, а может очень часто.