Дизассемблиры
Министерство образования РФ государственное
образовательное учреждение
высшего профессионального образования
Казанский национальный исследовательский институт
им.А.Н.Туполева-КАИ
Елабужский филиал.
Курсовая работа по дисциплине
“Системное программное обеспечение”
на тему:
«Дизассемблиры»
22575 группы
Борисова Татьяна Игоревна
E-mail:[email protected]
Проверил: Конюхов Михаил Иванович
E-mail:[email protected]
Елабуга
2011
Оглавление
Введение
Дизассемблирование (От англ. disassemble - разбирать, демонтировать) – это процесс или способ получения исходного текста программы на ассемблере из программы в машинных кодах. Полезен при определении степени оптимальности транслятора и при генерации кодов собственной программы. Позволяет понять алгоритм или метод построения программ, у которых отсутствуют исходные тексты. Существуют специальные программы дизассемблеры, которые выполняют этот процесс.
Одним
из передовых продуктов для
IDA
является не только
Целью, данной работы, является задача дизассемблирования программ написанных на языке программирования C/C++ и скомпилированных на компиляторах Microsoft Visual C++ 6.0, Borland C++ 5.0 и WATCOM.
В процесс дизассемблирования входит:
1) идентификация математических операций таких как: сложение, вычитание, деление, операция вычисления остатка, умножение и определения комплексных операций;
2) Идентификация операторов SWITCH - CASE – BREAK.
В ходе работы будет проведен анализ по качеству оптимизации, сгенерированных приведенными выше компиляторами программ, что позволит сравнить их и определить каким из них необходимо воспользоваться для получения наиболее оптимального и быстрого кода в программировании.
Глава1. Идентификация математических операторов
§1.1
Идентификация оператора "+"
В общем случае оператор "+"
транслируется либо в машинную
инструкцию ADD, "перемалывающую" целочисленные
операнды, либо в инструкцию FADDx,
обрабатывающую вещественные
main()
{
int a, b,c;
c = a + b;
printf("%x\n",c);
c=c+1;
printf("%x\n",c);
}
Демонстрация
оператора "+"
Результат
его компиляции компилятором Microsoft
Visual C++ 6.0 с настройками по умолчанию
должен выглядеть так:
main proc near ;
CODE XREF: start+AF p
var_c = dword ptr -0Ch
var_b = dword ptr -8
var_a = dword ptr
-4
push ebp
mov ebp, esp
; Открываем
кадр стека
sub esp, 0Ch
; Резервируем
память для локальных
mov eax, [ebp+var_a]
; Загружаем
в EAX значение переменной var_a
add eax, [ebp+var_b]
; Складываем
EAX со значением переменной var_b и
записываем результат в EAX
mov [ebp+var_c], eax
; Копируем сумму var_a и var_b в переменную var_c, следовательно:
; var_c = var_a
+ var_b
mov ecx, [ebp+var_c]
push ecx
push offset asc_406030 ; "%x\n"
call _printf
add esp, 8
; printf("%x\n",
var_c)
mov edx, [ebp+var_c]
; Загружаем
в EDX значение переменной var_c
add edx, 1
; Складываем
EDX со значением 0х1, записывая
результат в EDX
mov [ebp+var_c], edx
; Обновляем var_c
; var_c = var_c
+1
mov eax, [ebp+var_c]
push eax
push offset asc_406034 ; "%x\n"
call _printf
add esp, 8
; printf("%\n",var_c)
mov esp, ebp
pop ebp
; Закрываем
кадр стека
retn
main endp
Теперь посмотрим, как будет выглядеть тот же самый пример, скомпилированный с ключом "/Ox" (максимальная оптимизация):
main proc near ; CODE XREF: start+AF p
push ecx
; Резервируем место для одной локальной переменной
; (компилятор
посчитал, что три переменные
можно ужать в одну и это
дейст. так)
mov eax, [esp+0]
; Загружаем
в EAX значение переменной var_a
mov ecx, [esp+0]
; Загружаем в EAX значение переменной var_b
; (т.к
.переменная не инициализирована загружать
можно откуда угодно)
push esi
; Сохраняем
регистр ESI в стеке
lea esi, [ecx+eax]
; Используем LEA для быстрого сложения ECX и EAX с последующей записью суммы
; в регистр ESI
; "Быстрое сложение" следует понимать не в смысле, что команда LEA выполняется
; быстрее чем ADD, - количество тактов той и другой одинаково, но LEA
; позволяет
избавиться от создания
; промежуточного результата сложения, сразу направляя результат в ESI
; Таким образом, эта команда декомпилируется как
; reg_ESI =
var_a + var_b
push esi
push offset asc_406030 ; "%x\n"
call _printf
; printf("%x\n",
reg_ESI)
inc esi
; Увеличиваем ESI на единицу
; reg_ESI =
reg_ESI + 1
push esi
push offset asc_406034 ; "%x\n"
call _printf
add esp, 10h
; printf("%x\n",
reg_ESI)
pop esi
pop ecx
retn
main endp
Остальные
компиляторы (Borland C++, WATCOM C) генерируют
приблизительно идентичный код, поэтому,
приводить результаты бессмысленно
- никаких новых "изюминок" они
в себе не несут.
§1.2
Идентификация оператора "-"
В
общем случае оператор "- " транслируется
либо в машинную инструкцию SUB (если
операнды - целочисленные значения),
либо в инструкцию FSUBx (если операнды
- вещественные значения). Оптимизирующие
компиляторы могут заменять "SUB
xxx, 1" более компактной командой "DEC
xxx", а конструкцию "SUB a, const" транслировать
в "ADD a, -const", которая ничуть не компактнее
и ни сколь не быстрей (и та, и другая укладываться
в один так). Рассмотрим это в следующем
примере:
main()
{
int a,b,c;
c = a - b;
printf("%x\n",c);
c = c - 10;
printf("%x\n",c);
}
Демонстрация
идентификации оператора "-"
Не
оптимизированный вариант будет
выглядеть приблизительно так:
main proc near ;
CODE XREF: start+AF p
var_c = dword ptr -0Ch
var_b = dword ptr -8
var_a = dword ptr
-4
push ebp
mov ebp, esp
; Открываем
кадр стека
sub esp, 0Ch
; Резервируем
память под локальные
mov eax, [ebp+var_a]
; Загружаем
в EAX значение переменной var_a
sub eax, [ebp+var_b]
; Вычитаем
из var_a значением переменной var_b, записывая
результат в EAX
mov [ebp+var_c], eax
; Записываем в var_c разность var_a и var_b
; var_c = var_a
- var_b
mov ecx, [ebp+var_c]
push ecx
push offset asc_406030 ; "%x\n"
call _printf
add esp, 8
; printf("%x\n",
var_c)
mov edx, [ebp+var_c]
; Загружаем
в EDX значение переменной var_c
sub edx, 0Ah
; Вычитаем
из var_c значение 0xA, записывая результат
в EDX
mov [ebp+var_c], edx
; Обновляем var_c
; var_c = var_c
- 0xA
mov eax, [ebp+var_c]
push eax
push offset asc_406034 ; "%x\n"
call _printf
add esp, 8
; printf("%x\n",var_c)
mov esp, ebp
pop ebp
; Закрываем кадр стека
retn
main endp
Теперь рассмотрим оптимизированный
вариант того же примера:
main proc near ; CODE XREF: start+AF p
push ecx
; Резервируем
место для локальной переменной var_a
mov eax, [esp+var_a]
; Загружаем
в EAX значение локальной переменной
var_a
push esi
; Резервируем
место для локальной переменной
var_b
mov esi, [esp+var_b]
; Загружаем
в ESI значение переменной var_b
sub esi, eax
; Вычитаем
из var_a значение var_b, записывая результат
в ESI
push esi
push offset asc_406030 ; "%x\n"
call _printf
; printf("%x\n",
var_a - var_b)
add esi, 0FFFFFFF6h
; Добавляем к ESI (разности var_a и var_b) значение 0хFFFFFFF6
; Поскольку, 0xFFFFFFF6 == -0xA, данная строка кода выглядит так:
; ESI = (var_a
- var_b) + (- 0xA) = (var_a - var_b) - 0xA
push esi
push offset asc_406034 ; "%x\n"
call _printf
add esp, 10h
; printf("%x\n",
var_a - var_b - 0xA)
pop esi
pop ecx
; Закрываем
кадр стека
retn
main endp
Компиляторы
(Borland, WATCOM) генерируют практически идентичный
код.
§1.3
Идентификация оператора "/"
В
общем случае оператор "/" транслируется
либо в машинную инструкцию "DIV"
(беззнаковое целочисленное
Несколько сложнее происходит быстрое деление знаковых чисел. Совершенно недостаточно выполнить арифметический сдвиг вправо (команда арифметического сдвига вправо SAR заполняет старшие биты с учетом знака числа), ведь если модуль делимого меньше модуля делителя, то арифметический сдвиг вправо сбросит все значащие биты в "битовую корзину", в результате чего получиться 0xFFFFFFFF, т.е. -1, в то время как правильный ответ - ноль. Однако деление знаковых чисел арифметическим сдвигом вправо дает округление в большую сторону. Для округления знаковых чисел в меньшую сторону необходимо перед выполнением сдвига добавить к делимому число 2^N- 1, где N - количество битов, на которые сдвигается число при делении. Легко видеть, что это приводит к увеличению всех сдвигаемых битов на единицу и переносу в старший разряд, если хотя бы один из них не равен нулю.
Следует
отметить: деление очень медленная
операция, гораздо более медленная
чем умножение (выполнение DIV может
занять свыше 40 тактов, в то время
как MUL обычно укладываться в 4), поэтому,
продвинутые оптимизирующие компиляторы
заменяют деление умножением. Существует
множество формул подобных преобразований,
одной из самых популярных является: a/b
= 2^N/b * a/2^N', где N' - разрядность числа. Следовательно,
грань между умножением и делением очень
тонка, а их идентификация является довольной
сложной процедурой. Рассмотрим следующий
пример:
main()
{
int a;
printf("%x
%x\n",a / 32, a / 10);
}
Идентификация
оператора "/"
Результат
компиляции компилятором Microsoft Visual C++ с
настройками по умолчанию должен выглядеть
так:
main proc near ;
CODE XREF: start+AF p
var_a = dword ptr
-4
push ebp
mov ebp, esp
; Открываем
кадр стека
push ecx
; Резервируем
память для локальной
mov eax, [ebp+var_a]
; Копируем
в EAX значение переменной var_a
cdq
; Расширяем
EAX до четверного слова EDX:EAX
mov ecx, 0Ah
; Заносим
в ECX значение 0xA
idiv ecx
; Делим (учитывая знак) EDX:EAX на 0xA, занося частное в EAX
; EAX = var_a
/ 0xA
push eax
; Передаем
результат вычислений функции
printf
mov eax, [ebp+var_a]
; Загружаем
в EAX значение var_a
cdq
; Расширяем
EAX до четверного слова EDX:EAX
and edx, 1Fh
; Выделяем
пять младших бит EDX
add eax, edx
; Складываем
знак числа для выполнения
округления отрицательных
; в меньшую
сторону
sar eax, 5
; Арифметический сдвиг вправо на 5 позиций
; эквивалентен делению числа на 2^5 = 32
; Таким
образом, последние четыре
; EAX = var_a / 32
; Обратите внимание: даже при выключенном режиме оптимизации компилятор
; оптимизировал
деление
push eax
push offset aXX ; "%x %x\n"
call _printf
add esp, 0Ch
; printf("%x
%x\n", var_a / 0xA, var_a / 32)
mov esp, ebp
pop ebp
; Закрываем
кадр стека
retn
main endp
Теперь,
рассмотрим оптимизированный вариант
того же примера:
main proc near ; CODE XREF: start+AF p
push ecx
; Резервируем
память для локальной
mov ecx, [esp+var_a]
; Загружаем
в ECX значение переменной var_a
mov eax, 66666667h
; В исходном
коде ничего подобного не было!
imul ecx
; Умножаем это число на переменную var_a
; Обратите
внимание: именно умножаем, а не
делим.
sar edx, 2
; Выполняем
арифметический сдвиг всех
; в первом приближении эквивалентно его делению на 4
; Однако ведь в EDX находятся старшее двойное слово результата умножения!
; Поэтому,
три предыдущих команды
; EDX = (66666667h * var_a) >> (32 + 2) = (66666667h * var_a) / 0x400000000
;
; Теперь немного упростим код:
; (66666667h * var_a) / 0x400000000 = var_a * 66666667h / 0x400000000 =
; = var_a *
0,
; Заменяя
по всем правилам математики
умножение на деление и
; выполняя округление до меньшего целого получаем:
; var_a * 0,1000000000 = var_a * (1/0,1000000000) = var_a/10
;
; От такого преобразования код стал намного понятнее!
; Тогда возникает вопрос можно ли распознать такую ситуацию в чужой
; программе, исходный текст которой
; неизвестен? Можно - если встречается умножение, а следом за ним
; сдвиг
вправо, обозначающий деление, сократив
код, по методике показанной выше!
mov eax, edx
; Копируем
полученное частное в EAX
shr eax, 1Fh
; Сдвигаем
на 31 позицию вправо
add edx, eax
; Складываем: EDX = EDX + (EDX >> 31)
; Нетрудно понять, что после сдвига EDX на 31 бит вправо
; в нем останется лишь знаковый бит числа
; Тогда - если число отрицательно, добавляем к результату деления один,
; округляя его в меньшую сторону. Таким образом, весь этот хитрый код
; обозначает ни что иное как тривиальную операцию знакового деления:
; EDX = var_a / 10
; Конечно, программа становится очень громоздкой,
; зато весь этот код выполняется всего лишь за 9 тактов,
; в то время как в не оптимизированном варианте за 28!
; /* Измерения проводились на процессоре CLERION с ядром P6, на других
; процессорах
количество тактов может
; Т.е.
оптимизация дала более чем
трехкратный выигрыш!
mov eax, ecx
; Теперь нужно вспомнить: что находится в ECX.
; В ECX
последний раз разгружалось значение
переменной var_a
push edx
; Передаем
функции printf результат деления var_a на 10
cdq
; Расширяем
EAX (var_a) до четверного слова EDX:EAX
and edx, 1Fh
; Выбираем
младшие 5 бит регистра EDX, содержащие
знак var_a
add eax, edx
; Округляем
до меньшего
sar eax, 5
; Арифметический
сдвиг на 5 эквивалентен делению var_a
на 32
push eax
push offset aXX ; "%x %x\n"
call _printf
