Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Фундаментальные основы хакерства. Определяем циклы в двоичном коде программы
Содержание статьи
- Циклы с условиями в начале
- Циклы с условием в конце
- Циклы со счетчиком
- Циклы с условием в середине
- Циклы с множественными условиями выхода
- Циклы с несколькими счетчиками
- Идентификация 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 80×86 такой трюк экономит от одной до двух машинных команд.
Обрати внимание: ниже приведен цикл с условием завершения цикла.
А далее — с условием продолжения цикла.
Как видно на картинках, цикл с условием завершения на одну команду короче! Поэтому практически все компиляторы (даже неоптимизирующие) всегда генерируют первый вариант. А некоторые особо одаренные даже умеют превращать циклы с предусловием в еще более эффективные циклы с постусловием (см. пункт «Циклы с условием в конце»).
Цикл с условием завершения не может быть непосредственно отображен на оператор 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 и всех последующих моделей оптимизирован именно под переходы, направленные назад, то есть в область младших адресов. Поэтому циклы с постусловием должны выполняться несколько быстрее аналогичных им циклов с предусловием.
Источник: xakep.ru
