Хакер - Фундаментальные основы хакерства. Определяем циклы в двоичном коде программы
hacker_frei
Крис Касперски Юрий Язев
Содержание статьи
- Циклы с условиями в начале
- Циклы с условием в конце
- Циклы со счетчиком
- Циклы с условием в середине
- Циклы с множественными условиями выхода
- Циклы с несколькими счетчиками
- Идентификация continue
- Сложные условия
- Вложенные циклы
- Заключение
В сегодняшней статье мы изучим все типы циклов, которые могут встретиться в языках программирования высокого уровня. Увидим, какие способы есть у компилятора для отражения их в двоичном виде. Разберем плюсы и минусы каждого. Кроме того, мы узнаем, как перемалывают циклы различные трансляторы и что получается на выходе у оптимизирующих и неоптимизирующих компиляторов.
Фундаментальные основы хакерства
Пятнадцать лет назад эпический труд Криса Касперски «Фундаментальные основы хакерства» был настольной книгой каждого начинающего исследователя в области компьютерной безопасности. Однако время идет, и знания, опубликованные Крисом, теряют актуальность. Редакторы «Хакера» попытались обновить этот объемный труд и перенести его из времен Windows 2000 и Visual Studio 6.0 во времена Windows 10 и Visual Studio 2019.
Циклы — единственная (за исключением неприличного GOTO) конструкция языков высокого уровня, имеющая ссылку «назад», то есть в область младших адресов. Все остальные виды ветвлений — будь то IF — THEN — ELSE или оператор множественного выбора SWITCH — всегда направлены «вниз», в область старших адресов. Вследствие этого изображающее цикл логическое дерево настолько характерно, что легко опознается с первого взгляда.
Существуют три основных типа цикла:
- Циклы с условием в начале.
- Циклы с условием в конце.
- Циклы с условием в середине.
Комбинированные циклы имеют несколько условий в разных местах, например в начале и конце одновременно. В свою очередь, условия бывают двух типов: условия завершения цикла и условия продолжения цикла.
В первом случае, если условие завершения истинно, выполняется переход в конец цикла, иначе он продолжается. Во втором, если условие продолжения цикла ложно, выполняется переход в конец цикла, в противном случае он продолжается. Легко показать, что условия продолжения цикла представляют собой инвертированные условия завершения.
Таким образом, со стороны транслятора вполне достаточно поддержки условий одного типа. И действительно, операторы циклов while, do и for языка С/C++ работают исключительно с условиями продолжения цикла. Оператор while языка Delphi также работает с условием продолжения, и исключение составляет один лишь repeat-until, ожидающий условие завершения цикла.
ЦИКЛЫ С УСЛОВИЯМИ В НАЧАЛЕ
Их также называют циклами с предусловием. В языках С/C++ и Delphi поддержка циклов с предусловием обеспечивается оператором while (условие), где условие — это условие продолжения цикла. То есть цикл while (a < 10) a++; выполняется до тех пор, пока условие (a>10) остается истинным. Однако транслятор при желании может инвертировать условие продолжения цикла на условие его завершения. На платформе Intel 80x86 такой трюк экономит от одной до двух машинных команд.
Обрати внимание: ниже приведен цикл с условием завершения цикла.
А далее — с условием продолжения цикла.
Как видно на картинках, цикл с условием завершения на одну команду короче! Поэтому практически все компиляторы (даже неоптимизирующие) всегда генерируют первый вариант. А некоторые особо одаренные даже умеют превращать циклы с предусловием в еще более эффективные циклы с постусловием (см. пункт «Циклы с условием в конце»).
Цикл с условием завершения не может быть непосредственно отображен на оператор while. Кстати, об этом часто забывают начинающие, допуская ошибку «что вижу, то пишу»: while (a >= 10) a++. С таким условием цикл вообще не выполнится ни разу! Но как выполнить инверсию условия и при этом гарантированно не ошибиться? Казалось бы, что может быть проще, а вот попросите знакомого хакера назвать операцию, обратную «больше». Очень может быть (даже наверняка!), что ответом будет... «меньше». А вот и нет, правильный ответ «меньше или равно». Полный перечень обратных операций отношений можно найти в следующей таблице.
ЦИКЛЫ С УСЛОВИЕМ В КОНЦЕ
Их также называют циклами с постусловием. В языке С/C++ поддержка циклов с постусловием обеспечивается парой операторов do … while, а в языке Delphi — repeat … until. Циклы с постусловием без каких‑либо проблем непосредственно отображаются с языка высокого уровня на машинный код и наоборот. То есть, в отличие от циклов с предусловием, инверсии условия не происходит.
Например, do a++; while (a<10); в общем случае компилируется в следующий код (обрати внимание: в переходе использовалась та же самая операция отношения, что и в исходном цикле. Красота, и никаких ошибок при декомпиляции!).
Сравним код цикла с постусловием и код цикла с предусловием. Не правда ли, цикл с условием в конце компактнее и быстрее? Некоторые компиляторы (например, Microsoft Visual C++) умеют транслировать циклы с предусловием в циклы с постусловием. На первый взгляд, это вопиющая самодеятельность компилятора — если программист хочет проверять условие в начале, то какое право имеет транслятор ставить его в конце?
На самом же деле разница между «до» и «после» не столь значительна. Если компилятор уверен, что цикл выполняется хотя бы один раз, то он вправе выполнять проверку когда угодно. Разумеется, при этом необходимо несколько скорректировать условие проверки: while (a<b) не эквивалентно do ... while (a<b), так как в первом случае при (a == b) уже происходит выход из цикла, а во втором — цикл выполняет еще одну итерацию. Однако этой беде легко помочь: увеличим а на единицу (do ... while ((a+1)<b)) или вычтем эту единицу из b (do ... while (ab-1))), и... теперь все будет работать!
Спрашивается: и на кой все эти извращения, значительно раздувающие код? Дело в том, что блок статического предсказания направления ветвлений процессоров Pentium и всех последующих моделей оптимизирован именно под переходы, направленные назад, то есть в область младших адресов. Поэтому циклы с постусловием должны выполняться несколько быстрее аналогичных им циклов с предусловием.
ЦИКЛЫ СО СЧЕТЧИКОМ
Циклы со счетчиком (for) не являются самостоятельным типом циклов, а представляют собой всего лишь синтаксическую разновидность циклов с предусловием. В самом деле, for (a = 0; a < 10; a++) в первом приближении то же самое, что и
a = 0;
while (a < 10) {
...
a++;
}
Однако результаты компиляции двух этих конструкций необязательно будут идентичны!
Оптимизирующие компиляторы (да и значительная часть неоптимизирующих) поступают хитрее, передавая после инициализации переменной‑счетчика управление на команду проверки условия выхода из цикла. Образовавшаяся конструкция, во‑первых, характерна и при анализе программы — она сразу бросается в глаза, — а во‑вторых, не может быть непосредственно отображена на циклы while языка высокого уровня.
Непосредственный прыжок вниз может быть результатом компиляции и цикла for, и оператора GOTO, но GOTO сейчас не в моде и используется крайне редко, а без него оператор условного перехода IF — THEN не может прыгнуть непосредственно в середину цикла while! Выходит, изо всех «кандидатов» остается только цикл for.
Некоторые особо продвинутые компиляторы (Microsoft Visual C++, Embarcadero C++Builder) поступают хитрее: анализируя код, они еще на стадии компиляции пытаются определить, выполняется ли данный цикл хотя бы один раз, и, если видят, что он действительно выполняется, превращают for в типичный цикл с постусловием.
Наконец, самые совершенные компиляторы (из которых можно назвать один лишь Microsoft Visual C++) могут даже заменять циклы с приращением на циклы с убыванием при условии, что параметр цикла не используется операторами цикла, а лишь прокручивает цикл определенное число раз. Зачем это компилятору? Оказывается, циклы с убыванием гораздо короче — однобайтовая инструкция DEC не только уменьшает операнд, но и выставляет Zero-флаг при достижении нуля. В результате необходимость в команде CMP A, xxx отпадает автоматически.
Таким образом, в зависимости от настроек и характера компилятора циклы for могут транслироваться и в циклы с предусловием, и в циклы с постусловием, начинающие свое выполнение с проверки условия продолжения цикла. Причем условие продолжения может инвертироваться в условие завершения, а возрастающий цикл может волшебным образом превратиться в убывающий.
Такая неоднозначность затрудняет идентификацию циклов for. Надежно определяются лишь циклы, начинающиеся с проверки постусловия, так как они не могут быть отображены на do без использования GOTO. Во всех остальных случаях никаких строгих рекомендаций по распознаванию for дать нельзя.
Скажем так: если логика исследуемого цикла синтаксически удобнее выражается через оператор for, то и выражай ее через for! В противном случае используй while или do (repeat\until) для циклов с пред- и постусловием соответственно.
И в заключение пара слов о «кастрированных» циклах. Язык C/C++ позволяет опустить инициализацию переменной цикла, условие выхода из него, оператор приращения переменной или все это вместе. При этом for вырождается во while и становится практически неотличимым от него.
ЦИКЛЫ С УСЛОВИЕМ В СЕРЕДИНЕ
Популярные языки высокого уровня непосредственно не поддерживают циклы с условием в середине, хотя необходимость в них возникает довольно часто. Поэтому программисты их реализуют на основе уже имеющихся циклов while (while\do) и оператора выхода из цикла break. Например, так.
Компилятор (если он не совсем осёл) разворачивает бесконечный цикл в безусловный переход JMP, направленный, естественно, назад (ослы генерируют код вроде MOV EAX, 1\CMP EAX,1\JZ repeat). Направленный назад безусловный переход весьма характерен — за исключением бесконечного цикла, его может порождать один лишь оператор GOTO. А раз у нас есть бесконечный цикл, то условие его завершения может находиться лишь в середине этого цикла (сложные случаи многопоточных защит, модифицирующих из соседнего потока безусловный переход в NOP, мы пока не рассматриваем). Остается прочесать тело цикла и найти это самое условие.
Сделать это будет нетрудно — оператор break транслируется в переход на первую команду, следующую за JMP repeat, а сам break получает управление от ветки IF (условие) — THEN — [ELSE]. Условие ее срабатывания и будет искомым условием завершения цикла. Вот, собственно, и все.
ЦИКЛЫ С МНОЖЕСТВЕННЫМИ УСЛОВИЯМИ ВЫХОДА
Оператор break позволяет организовать выход из цикла в любом удобном для программиста месте, поэтому любой цикл может иметь множество условий выхода, беспорядочно разбросанных по его телу. Это ощутимо усложняет анализ дизассемблируемой программы, так как возникает риск «прозевать» одно из условий завершения цикла, что приведет к неправильному пониманию логики программы.
Идентифицировать условия выхода из цикла очень просто — они всегда направлены «вниз», то есть в область старших адресов, и указывают на команду, непосредственно следующую за инструкцией условного (безусловного) перехода, направленного «вверх», в область младших адресов.
ЦИКЛЫ С НЕСКОЛЬКИМИ СЧЕТЧИКАМИ
Оператор «запятая» языка С/C++ позволяет выполнять множественную инициализацию и модификацию счетчиков цикла for. Например: for (int a = 0, b = 10; a != b; a++, b--)... А как насчет нескольких условий завершения? Подавляющее большинство учебников по программированию на этот счет хранят гробовое молчание.
С помощью Embarcadero C++Builder 10.4 попробуем скомпилировать следующий код (пример some_counters_cb):
int _tmain(int argc, _TCHAR* argv[]) {
for (int a = 0, b = 10; a < 10, b > 5; a++, b--)
std::cout << a << " | " << b << std::endl;
return 0;
}
Он будет благополучно «проглочен» компилятором, однако в области предупреждений выведет
cod1.cpp(15,27): warning W7379: relational comparison result unused
Предупреждение он вывел, а скомпилировал‑то все равно неправильно! Логическое условие (a1, a2, a3, ... ,an) лишено смысла, и компиляторы без малейших колебаний и зазрений совести отбросят все, кроме самого правого выражения an. Оно‑то и будет единолично определять условие продолжения цикла.
Откомпилируем этот же код в Microsoft Visual C++ 2022. Он выведет более осмысленное сообщение: «Предупреждение C6319: Использование оператора „запятая“ в проверяемом выражении приводит к тому, что левый аргумент будет пропущен, если у него нет побочных эффектов».
Такое объяснение более понятно. Если условие продолжения цикла зависит от нескольких переменных, то их сравнения следует объединить в одно выражение посредством логических операций OR, AND и других. Например: for (a=0, b=10; (a > 0 && b < 10); a++, b--) — цикл прерывается сразу же, как только одно из двух условий станет ложно; for (a=0, b=10; (a > 0 || b < 10); a++, b--) — цикл продолжается до тех пор, пока истинно хотя бы одно условие из двух.
Для успокоения совести модифицируем код нашего примера, скомпилируем его и посмотрим на результат:
int main() {
for (int a = 0, b = 10; (a < 10 || b > 5); a++, b--)
std::cout << a << " | " << b << std::endl;
}
В остальном же циклы с несколькими счетчиками транслируются аналогично циклам с одним счетчиком, за исключением того, что инициализируется и модифицируется не одна, а сразу несколько переменных.
ИДЕНТИФИКАЦИЯ CONTINUE
Оператор continue приводит к непосредственной передаче управления на код проверки условия продолжения (завершения) цикла. В общем случае он транслируется в безусловный jump в циклах с предусловием, направленным вверх, а в циклах с постусловием — вниз. Следующий за continue код уже не получает управления, поэтому continue практически всегда используется в условных конструкциях.
Например:
while (a++ < 10)
if (a == 2)
continue;
...
Компилируется приблизительно так.
СЛОЖНЫЕ УСЛОВИЯ
До сих пор, говоря об условиях завершения и продолжения цикла, мы рассматривали лишь элементарные условия отношения, в то время как практически все языки высокого уровня допускают использование составных условий. Однако составные условия можно схематично изобразить в виде абстрактного «черного ящика» с входом/выходом и логическим двоичным деревом внутри. Построение и реконструкция логических деревьев подробно рассматриваются в разделе «Идентификация IF — THEN — ELSE», здесь же нас интересует организация циклов, а не сами условия.
Вложенные циклы
Циклы, понятное дело, могут быть и вложенными. Казалось бы, какие проблемы? Начало каждого цикла надежно определяется по перекрестной ссылке, направленной вниз. Конец цикла — условный или безусловный переход на его начало. У каждого цикла только одно начало и только один конец (хотя условий выхода может быть сколько угодно, но это другое дело). Причем циклы не могут пересекаться; если между началом и концом одного цикла встречается начало другого цикла, то этот цикл — вложенный.
Но не все так просто: тут есть два подводных камня. Первый: оператор continue в циклах с предусловием, второй — сложные условия продолжения цикла с постусловием. Рассмотрим их подробнее.
Поскольку в циклах с предусловием оператор continue транслируется в безусловный переход, направленный «вверх», он становится практически неотличим от конца цикла. Смотри:
while (условие1) {
...
if (условие2) continue;
...
}
Транслируется в следующий код.
Два конца и два начала вполне напоминают два цикла, один из которых вложен в другой. Правда, начала обоих циклов совмещены, но ведь может же такое быть, если в цикл с постусловием вложен цикл с предусловием? На первый взгляд кажется, что да, но если подумать, то... ай‑ай‑ай! А ведь условие1 выхода из цикла прыгает аж за второй конец! Если это предусловие вложенного цикла, то оно прыгало бы за первый конец. А если условие1 — предусловие материнского цикла, то конец вложенного цикла не смог бы передать на него управление. Выходит, это не два цикла, а один. А первый «конец» — результат трансляции оператора continue.
С разбором сложных условий продолжения цикла с постусловием дела обстоят еще лучше. Рассмотрим такой пример:
do {
...
} while(условие1 || условие2);
Ну чем не
do {
do {
...
} while(условие1)
} while(условие2)
Строго говоря, предложенный вариант логически верен, но синтаксически некрасив. Материнский цикл крутит в своем теле один лишь вложенный цикл и не содержит никаких других операторов. Так зачем он тогда, спрашивается, нужен? Следует объединить его с вложенным циклом!
ЗАКЛЮЧЕНИЕ
По большому счету это была теоретическая статья. В ней мы не рассмотрели ни одного дизассемблерного листинга. Однако и цель у нее другая: показать все разнообразие циклов и подготовить тебя к следующему шагу — к осмысленному разбору дизассемблерных листингов настоящих программ с возможностью отмечать корректные и неправильные ходы конкретного компилятора.
Читайте ещё больше платных статей бесплатно: https://t.me/hacker_frei