Строительные исследования
страница - 0
ОБЗОР АЛГОРИТМОВ ДЕКОМПИЛЯЦИИ Щеглов К.Е. (k scheglov@stinol.ru)
Липецкий государственный технический университет
1. Введение
1.1.Определение
В литературе можно встретить несколько различных определений декомпилятора. Например, в [1]:
Декомпилятор - программа, получающая на вход программу в машинном коде и выдающая эквивалентную программу на языке программирования.
Это определение страдает некоторой неопределенностью и излишней оптимистичностью. В определении следует подчеркнуть тесную связь между компилятором и декомпилятором, а также то, что, как будет описано ниже, процесс декомпиляции не является безусловным и всегда успешным. Поэтому стоит переформулировать определение следующим образом:
Декомпилятор - это программа, которая пытается осуществить процесс, обратный производимому компилятором: по данному исполняемому файлу программы, скомпилированному любым высокоуровневым языком, она стремится выдать программу на языке высокого уровня (причем не обязательно это будет язык, на котором программа была написана исходно), которая будет выполнять те же самые функции, что и входная исполняемая программа.
1.2.История развития декомпиляции
Первые декомпиляторы появились в 60-х годах и сразу же стали рассматриваться как полезные инструменты для практического применения. В то время они использовались для облегчения переноса программ с ЭВМ второго поколения на третье [2,3,4]. Речь, разумеется, шла не о полностью автоматической декомпиляции (даже сейчас это не получится), хорошим результатом считалось получение программы, в которой правильно восстановлено 90% кода.
В 70-е и 80-е декомпиляторы также использовались для переноса программ, а также для документирования, отладки, восстановления утерянных исходных текстов и модификации существующих исполняемых модулей [5,6,7].
В 90-х годах декомпиляторы стали использоваться как средство reverse engineeringа, помогающее пользователю в таких задачах как проверка программного обеспечения на наличие злонамеренного кода, тестирование компиляторов, а также перевод программ с одной машины на другую.
В настоящее время существует ряд фирм, предлагающих услуги по декомпиляции программ для IBM 360/370/390 в исходный код на Cobol [8,9,10]. Это было особенно актуально в конце 20-го века из-за "проблемы 2000", так как часто программы были написаны много лет назад, а исходные тексты полностью или частично утрачены из-за сбоя диска, износа магнитной ленты и
т.д.
В связи с высокой популярностью языка Java, а также из-за особенностей хранения скомпилированных программ (байт-код), несколько фирм предлагают услуги по восстановлению кода и защите от подобного восстановления, например [11].
Также существуют программы, облегчающие reverse engineering (в основном под ЭВМ на базе Intel-процессоров), например Sourcer, IDA Pro [12].
Существуют различные мнения и законодательные акты по поводу возможности и правомерности декомпиляции и вообще анализа коммерческого программного обеспечения. В разных странах этот вопрос решается по-разному.
В принятом в 1999 году дополнении к закону об охране авторских прав [13] разработчикам программного обеспечения дается право декомпилировать чужие программные продукты, с тем, чтобы добиться их совместимости с существующим программным обеспечением. «Декомпиляцию программы можно будет осуществлять без разрешения владельца только в целях обеспечения интероперабельности или проверки уровня защиты, если информация о программных интерфейсах или о гарантиях безопасности не является общедоступной», - говорится в документе. При этом информация, извлеченная из декомпилированной программы, не может использоваться для каких-либо иных целей или передаваться другим лицам без разрешения владельца авторского права.
Исследование легально приобретенной вами программы, её изучение или изменение её кода совершенно законно в Евросоюзе [14], пока:
•Вы делаете это только для собственного использования или в «образовательных целях» (т. е. изучаете)
•Вы не используете больших фрагментов кода для написания программ, которые вы продаете
Вы можете, например, полностью переделать Wordpad для вашего собственного использования, чтобы открывать им по умолчанию файлы *.txt, *.alf и *.asm, вместо практически бесполезных файлов *.doc. Вы можете извлечь любой код из любой программы на ваше усмотрение, чтобы его использовать, изменить или выбросить в мусор.
Что касается России, то здесь ситуация весьма запутанная. Как указано в [15], в России, как и в Евросоюзе, разрешено исследование программ, однако (цитата закона): "Предоставляемая настоящим Законом правовая охрана не распространяется на идеи и принципы, лежащие в основе программы для ЭВМ или базы данных или какого-либо их элемента, в том числе на идеи и принципы организации интерфейса и алгоритма, а также языки программирования". Таким образом, алгоритмы не охраняются законом об авторских правах! Поэтому можно дизассемблировать программу для извлечения оных с очевидной выгодой. (Строго говоря, они могут быть защищены другими законами, например патентными, но, в отличие от авторского права, они автоматически не попадают под защиту закона).
Таким образом, декомпиляция программ является законной при соблюдении определенных условий. Однако в любом случае, исследование методов и алгоритмов декомпиляции является вполне законным, чем мы и займемся.
1.3. Проблемы декомпиляции
Перед разработчиком декомпилятора встает ряд теоретических и практических проблем. Некоторые из них могут быть решены эвристическими методами, другие же не могут быть решены полностью. Из-за этих ограничений декомпиляторы, как правило, способны автоматически декомпилировать определенный класс программ, а остальные программы должны обрабатываться в полуавтоматическом режиме, с помощью человека. Это отличает декомпилятор от компилятора, который производит автоматическую трансляцию всех программ.
Вот список некоторых проблем, выявленных автором, и методы, которые помогают (иногда) в их решении:
•Разделение кода и данных. В архитектуре Фон-Неймана инструкции и данные представляются в памяти одинаково. Взяв случайную последовательность байт из бинарного файла, мы не может однозначно сказать, что это - инструкции или данные. Даже если процессор поддерживает разделение сегментов кода и данных, небольшое количество данных (например, таблицы ветвлений типа case) может оставаться в сегменте кода. Есть несколько путей решения этой проблемы. Один подходит в случае, когда множество инструкций процессора разреженное и не покрывает весь диапазон значений машинного слова, как, например, в процессоре ЭВМ PDP-11 [16]. Другой, более универсальный способ заключается в эмуляции работы процессора и последовательной трассировке программы, начиная с точки старта и заканчивая точкой останова. При этом также учитываются условные и безусловные переходы, вызовы подпрограмм, плюс параллельно происходит построение графа управления. Именно этот подход мы и будем использовать.
•Самомодифицирующийся код. Иногда, в силу разных обстоятельств (экономия памяти, шифрование кода, написание вирусов), программы используют одни и те же адреса памяти для хранения и исполняемого кода, и данных. Мы не будем рассматривать подобные программы, так как сейчас использование подобных трюков не является необходимым.
•Идиомы. Идиома - это последовательность инструкций, которая формирует логическую единицу, действие, которое не является просто использованием первичного назначения используемых инструкций. Например, умножение и деление на степень 2-ки является известной и широко используемой идиомой: вместо использования обычных инструкций умножения и деления применяют сдвиг аргумента влево и вправо соответственно.
•Подпрограммы, добавляемые компилятором и линковщиком. Компилятор почти всегда добавляет подпрограммы для инициализации, а также библиотеки поддержки выполнения (RTL). Такие процедуры обычно написаны на ассемблере и в большинстве случаев не могут быть декомпилированны в высокоуровневый язык. Решение состоит в том, чтобы, зная с помощью какого компилятора создавалась программа, идентифицировать библиотечные подпрограммы и не проводить их декомпиляцию. Хорошая статья на эту тему может быть найдена на сервере разработчика программы IDA [10].
содержание:
[стр.Введение] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5]