Изменения

Потом В какой-то момент я ещё нашёл страничку http://www.backerstreet.com/decompiler/creating_statements.php, и понял, что все мои мысли полностью соответствуют стандартной теории декомпиляции. Потом стало ясно, что парсить вывод IDA — IDA (листинги) — занятие тяжкое и приносящее малый профит, и в случае ARM точно лучше использовать objdump, хотя он и не является рекурсивным дизассемблером. Вообще == Этап 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 в инструкциях сопроцессора).* Аргументы.* Все поля можно добивать нулями до фиксированных размеров. Формат аргумента:* Непосредственный аргумент: <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 — Отслеживание данных в рамках блоков == == Начальный анализ ==

== Выделение блоков == Далее нужно перейти к выделению блоков — то есть, циклов и условных операторовоператоров — тому, что обычно называют «структурированием», то есть воссозданием программы из линейного листинга: === Циклы === У любого цикла есть точка входа, на которую можно поставить метку «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’овского листинга с какой-нибудь точки входа. При этом для каждого непрерывного блока нужно сохранять входные значения и выходные, относительные входных. Выражения, порождаемые и используемые только внутри блока, можно подставлять сразу. Часть выражений, которые после выхода из блока не будут использоваться, можно забыть.

* Каждый цикл:** Начинается с какого-либо узлаВыделять циклы и условные операторы на этом этапе ещё не нужно, являющегося к тому же единственной точкой входа потому что граф ветвлений может поменяться в этот цикл.** Должен включать в себя все пути, ведущие в любой внешний узелпроцессе анализа, а от интерпретации циклов и возвращающиеся в любой внутренний узел (''обобщённое требование цикла'')условных операторов зависят и окончательные выражения.** Если добавили какой-то узелПравда, нужно иметь ввиду, что после выделения блоков могут появиться и получили две точки входановые переходы, то этот узел не принадлежит циклу.** Если добавили какой-то узел влияющие и единственная точка входа изменилась, идём нафиг — цикл из изначального узла не растёт.*: Когда залезаем в цикл, переходы на начало граф и выход из цикла заменяем снова на continue и break для удобочитаемостициклы и т.* Условный оператор:** Если что-то откуда-то ветвится и это не цикл, это условный оператор :)*: Транслировать его следует так:** Ищем точку сбора всех веток, выходящих из начального узла (узел, в котором все они объединяются) п.** Залезаем в каждую ветку, всё обрабатываем точно так же, как до этого, и точно так же (но в обработке линейных участков и циклов тоже помечаем).** Помечаем пройденные узлы как обработанные.** Когда где-то видим уже обработанный узелосновном такие переходы будут, заменяем переход к нему на 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>

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