logo
инт

5.2.4.6. Декомпиляторы

Декомпилятор - программа, позволяющая по программе на языке низкого уровня (обычно это коды некоторой машины) получить программу на высокоуровневом языке, в некотором смысле ей эквивалентную. Под эквивалентностью чаще всего понимают эквивалентность внешних проявлений работы исходной программы и декомпилированной (http://www.it.uq.edu.au/groups/csm/dcc.html).

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

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

Теория анализа потоков управления появилась давно, т. к. анализ активно применялся в компиляторах практически с момента их появления. Однако анализ потоков управления при компиляции имеет свою специфику - он используется в основном для целей оптимизации. Большинство алгоритмов анализа потоков управления, которые ориентированы на декомпиляцию, ставят своей целью уменьшение количества goto-выражений посредством введения новых логических переменных, дублирования кода (code replication) или использования конструкций высокого уровня, недоступных в большинстве широко используемых языков, таких как Pascal, С или C++.

В работах Кристины Цифуентес (Cristina Cifuentes) (http://www.itee.uq.edu.au/~cristina) представлены алгоритмы, использующие минимальный набор инструкций высокого уровня: циклы типов while и do...while, if- и case-выражения. Управление выполнением объемлющих конструкций из вложенных не допускается. Причем эти алгоритмы используют оператор goto лишь тогда, когда граф управления не может быть структурирован никаким иным способом в пределах перечисленных конструкций.

Анализ практических достижений в области декомпиляции языка Java выполнил Дэйв Дайер (Dave Dyer) (http://www.javaworld.com/). Он сравнил между собой три наиболее известных к середине 1997 года декомпилятора: DejaVu, Mocha и WingDis. Дайер предложил систему тестирования декомпиляторов, основанную на интересной классификации допускаемых ими ошибок. В соответствии с этой системой все ошибки делятся на шесть категорий. "Тяжесть" ошибки возрастает с номером категории. Ошибки, в результате которых декомпилированная программа перестает собираться, но которые могут быть легко исправлены (например, отсутствие явного приведения типов там, где оно с очевидностью должно быть), относятся к первой, самой легкой категории, тогда как генерация правильного, но нечитаемого текста на Java считается ошибкой третьей категории. Заметим, что некоторые ошибки, проявляясь у одних декомпиляторов, полностью отсутствуют у других. Это свидетельствует о жизнеспособности такой классификации - она позволяет определить области, в которых одни декомпиляторы имеют преимущество над другими.

В настоящее время наиболее известны следующие декомпиляторы: