Ответ 1
Один из величайших декомпиляторов, который сейчас находится здесь, - это, безусловно, Hex-Rays Decompiler. Если вы хотите видеть, что он может выводить, посмотрите http://www.hex-rays.com/products/decompiler/compare_vs_disassembly.shtml.
Его автор, Илфак Гильфанов, произнес речь о внутренней работе своего декомпилятора при некотором конфликте, и вот белая статья: http://www.hex-rays.com/products/ida/support/ppt/decompilers_and_beyond_white_paper.pdf и презентация здесь: http://www.hex-rays.com/products/ida/support/ppt/decompilers_and_beyond.ppt Это описывает хороший обзор, в чем все трудности при создании декомпилятора и о том, как заставить все это работать.
Кроме того, есть некоторые довольно старые документы, например. классическая кандидатская диссертация Кристины Чифунтес: http://itee.uq.edu.au/~cristina/dcc.html#thesis
Что касается сложности, все "декомпиляционные" вещи зависят от языка и времени исполнения двоичного файла. Например, декомпиляция .NET и Java считается "выполненной", так как есть свободные декомпиляторы, которые имеют очень высокий коэффициент успеха (они создают исходный источник). Но это вызвано спецификой виртуальных машин, которые используют эти среды выполнения.
Что касается действительно скомпилированных языков, таких как C, С++, Obj-C, Delphi, Pascal,... задача усложняется. Прочтите приведенные выше документы для деталей.
В чем разница между дизассемблером и декомпилятором?
Когда у вас есть двоичная программа (исполняемый файл, библиотека DLL,...), она состоит из инструкций процессора. Язык этих инструкций называется сборкой (или сборщиком). В двоичном коде эти команды кодируются двоично, поэтому процессор может их напрямую выполнять. Дисассемблер принимает этот двоичный код и переводит его в текстовое представление. Этот перевод обычно 1 к 1, то есть одна команда показана как одна строка текста. Эта задача сложна, но проста, программа просто должна знать все разные инструкции и как они представлены в двоичном формате.
С другой стороны, декомпилятор выполняет гораздо более сложную задачу. Он принимает либо двоичный код, либо вывод дизассемблера (который в основном тот же, что и 1-к-1), и создает высокоуровневый код. Позвольте мне показать вам пример. Скажем, у нас есть эта функция C:
int twotimes(int a) {
return a * 2;
}
Когда вы его компилируете, компилятор сначала генерирует и собирает файл для этой функции, он может выглядеть примерно так:
_twotimes:
SHL EAX, 1
RET
(первая строка - это просто метка, а не настоящая инструкция, SHL выполняет операцию сдвига влево, которая быстро умножается на два, RET означает, что функция выполнена). В двоичном результате результат выглядит следующим образом:
08 6A CF 45 37 1A
(Я сделал это, а не настоящие двоичные инструкции). Теперь вы знаете, что дизассемблер выводит вас из двоичной формы в форму сборки. Декомпилятор переводит вас в код C (или какой-либо другой язык более высокого уровня).