Трассировка процедур.

Sp1n

Мудрец
Сообщения
61
Реакции
29
Задумал такое сделать.

Что бы отследить нужную инструкцию сентер цпид етц нужно покрыть весь код апп. Взять текущую исполняемую процедуру и всю её в буфер изолировать. Там установить ловушки на инструкции, которые передают управление на вычисляемый адрес - indir call/jmp & ret.

Получится что процедура как целый объект, в который есть входы и выходы. Так покрыть следующий весь код. При этом не нужно будет хранить описатели каждой инструкции, а только процедуры; при исключениях адреса можно пересчитать, событие не частое.

Не совсем ясно как такое сработает и что делать если передача управления не на начало процедуры - строить новую.. Такое вообще бывает в тех же протах например ?
 

PE_Kill

Мудрец
Сообщения
135
Реакции
825
Уверен, что индирект процедуры отработают как надо на смыкании ветвей. Та же армадилла через гуард картирование выравнивает PF на границу 4 байт. Т.е. описатели, как ты верно заметил, не нужны, достаточно рассматривать flow как макро процедуры. Тогда входы и выходы будут как на ладоне, даже стек выравнивать не надо. Думаю это автоматически решит проблему сентеров.
 

mak

Соломенные сандалии
Администратор
Сообщения
930
Реакции
855
Static binary rewriting - такая же техника, только будет динамическая в готовом виде.

Не совсем ясно как такое сработает и что делать если передача управления не на начало процедуры - строить новую.. Такое вообще бывает в тех же протах например ?
В твоём DBI так, переход из одной процедуры сразу в другую :D Вопрос, что такое процедура в этом контексте? Если две процедуры с разными параметрами, то переход из одной в другую может быть через CPS, при этом архитектурно должен быть учтён стек.

Архив доступных материалов - https://github.com/SystemSecurityStorm/Awesome-Binary-Rewriting

A powerful static binary rewriting tool - https://github.com/GJDuck/e9patch

E9Patch - A Powerful Static Binary Rewriter
E9Patch is a powerful static binary rewriting tool for x86_64 Linux ELF binaries. E9Patch is:

  • Scalable: E9Patch can reliably rewrite large/complex binaries including web browsers (>100MB in size).
  • Compatible: The rewritten binary is a drop-in replacement of the original, with no additional dependencies.
  • Fast: E9Patch can rewrite most binaries in a few seconds.
  • Low Overheads: Both performance and memory.
  • Programmable: E9Patch is designed so that it can be easily integrated into other projects. See the E9Tool User's Guide and the E9Patch Programmer's Guide for more information.
NEW (9th Sep 2021): Experimental support for Windows PE binaries has been added.

Background
Static binary rewriting takes as input a binary file (ELF executable or shared object, e.g. a.out) and outputs a new binary file (e.g., b.out) with some patch/modification applied to it. The patched b.out can then be used as a drop-in replacement of the original a.out. Typical binary rewriting applications include instrumentation (the addition of new instructions) or patching (replacing binary code with a new version).

Static binary rewriting is notoriously difficult. One problem is that space for the new instructions must be allocated, and this typically means that existing instructions will need to be moved in order to make room. However, some of these existing instructions may also be jump targets, meaning that the all jump/call instructions in the original binary will also need to be adjusted in the rewritten binary. Unfortunately, things get complicated very quickly:
  • The complete set of targets cannot be determined statically (it is an undecidable problem in the general case of indirect calls or jumps).
  • Cross-binary calls/jumps are not uncommon, for example the compare function pointer argument to libc's qsort(). Since code pointers cannot be reliably distinguished from other data in the general case, this can mean that the entire shared library dependency tree also needs to be rewritten.
Unless all jumps and calls are perfectly adjusted, the rewritten binary will likely crash or otherwise misbehave. This is why existing static binary rewriting tools tend to scale poorly.

How E9Patch is Different
E9Patch is different to other tools in that it can statically rewrite x86_64 Linux ELF binaries without modifying the set of jump targets. To do so, E9Patch uses a set of novel low-level binary rewriting techniques, such as instruction punning, padding and eviction that can insert or replace binary code without the need to move existing instructions. Since existing instructions are not moved, the set of jump targets remains unchanged, meaning that calls/jumps do not need to be corrected (including cross binary calls/jumps).

E9Patch is therefore highly scalable by design, and can reliably rewrite very large binaries such as Google Chrome and FireFox (>100MB in size).

To find out more on how E9Patch works, please see our PLDI'2020 paper:
Additional Notes
The key to E9Patch's scalability is that it makes minimal assumptions about the input binary. However, E9Patch is not 100% assumption-free, and does assume:
  • The binary can be disassembled and does not use overlapping instructions. The default E9Tool frontend uses the Zydis disassembler.
  • The binary does not read from, or write, to the patched executable segments. For example, self-modifying code is not supported.
Most off-the-self x86_64 Linux binaries will satisfy these assumptions.

The instruction patching methodology that E9Patch uses is not guaranteed to work for every instruction. As such, the coverage of the patching may not be 100%. E9Patch will print coverage information after the rewriting process, e.g.:

num_patched = 2766 / 2766 (100.00%)

Most applications can expect at or near 100% coverage. However, coverage can be diminished by several factors, including:
  • Patching single-byte instructions such as rets, pushes and pops. These are difficult to patch, affecting coverage.
  • Patching too many instructions.
  • Binaries with large static code or data segments that limit the space available for trampolines.
A patched binary with less than 100% coverage will still run correctly, albeit with some instructions remaining unpatched. Whether or not this is an issue depends largely on the application.

Projects
Some other projects that use E9Patch include:
  • RedFat: A binary hardening system based on low-fat pointers.
  • E9AFL: Automatically insert AFL instrumentation into binaries.
  • E9Syscall: System call interception using static binary rewriting of libc.so.
Documentation
If you just want to test E9Patch out, then please try the above examples.

E9Patch is a low-level tool that is designed to be integrable into other projects. To find out more, please see the following documentation:
 

Vamit

Мудрец
Сообщения
12
Реакции
569
Там установить ловушки на инструкции, которые передают управление на вычисляемый адрес - indir call/jmp & ret.
Сначала определись что-такое процедура, первоначально любой call нужно рассматривать как вызов процедуры с её начала, переходы по jmp только фиксируются в сортированном буфере. Ret, как и любой индирект call побоку, т.к. адреса переходов тут не вычислить.
Писал я свой локализатор процедур, стояла задача определить границы процедуры, tail области (при их наличии) и аргументы.
Задача статически решаема по безусловным call.
Не совсем ясно как такое сработает и что делать если передача управления не на начало процедуры - строить новую.. Такое вообще бывает в тех же протах например ?
Бывает и не только в протах. Если определена "большая" процедура, то строить новую не надо, можно оформить как побочную точку входа в уже рассмотренную процедуру, иначе наоборот, расширение процедуры до "большей".
 

Sp1n

Мудрец
Сообщения
61
Реакции
29
mak

> Static binary rewriting

В этих кучах публикаций смысла нет вообще никакого. Тоесть обычный патч кода, а расписывают всяким матаном, иначе академия не одобрит, в общем хлам.

Vamit

> что-такое процедура

Инструкции связанные статик ветвлениями, это которые не нужно вычислять - релатив call/jmp. В ином случае на для рет адрес вычисляется, как и для косвенных. Сначала в кэше посмотреть изменился ли адрес возврата после call или call/jmp [P], если изменился транслировать адрес на буфер; если его нет то собирать процедуру.

> строить новую не надо

Тогда нужно хранить описатели всех инструкций, а не только процедуры. Что бы найти соотв собранную инструкцию, а на это нужно очень много памяти. Либо вычислять смещение собранной интр налету.

> Бывает и не только в протах

Нужно проверить, как это сделать ?

Выделять все процедуры по call/icall/imp и смотреть адрес ветвления внутрь ?

Для начала нужна быстрая рутина для сборки кода в буфер с оптимизацией ветвление.
 

Vamit

Мудрец
Сообщения
12
Реакции
569
Так как ИДА имеет очень приличный анализатор процедур (функций), то для начала предлагаю частично ознакомиться с её SDK, поймешь что требуется и примерный объем реализации кода, которого будет немало. Посмотри файл funcs.hpp (класс функции class func_t : public area_t).
 

Sp1n

Мудрец
Сообщения
61
Реакции
29
Зачем мне Ида и что то анализить ?

Пройти по ветвям, маркера в два массива(кэша) - body/entry, затем на каждом ветвление проверять маркера; так будут обнаружены ветвления внутрь процедур. Проверю это.
 

Sp1n

Мудрец
Сообщения
61
Реакции
29
В общем нужно маркировать код в пределах процедуры. Алго такой получается для проверки, отладить осталось, интересно что выдаст. На такую маркировку нужно 250М памяти..
 

Прикрепленные файлы:

Sp1n

Мудрец
Сообщения
61
Реакции
29
В общем уже что то завелось:
crl.png

- все корреляции на jmp [P+ i].
 
  • Понравилось
Реакции: mak

Sp1n

Мудрец
Сообщения
61
Реакции
29
Собрал семпл, фактически секвенсор(обработка и накопление кодовой последовательности) это детектор op-инжектов. Крутилось визором, вынес в отдельную либу, что бы можно было обычной трассировкой пустить. Много интересного в семплах находит.
se_dbgview.png
se_olly.png
se_ori.png

Первая проблема, code vs data:
se_rpc.png
 

Прикрепленные файлы:

  • Понравилось
Реакции: mak

mak

Соломенные сандалии
Администратор
Сообщения
930
Реакции
855
Ранее уже что-то подобное делали, как плагин для отладчика, правда линк на файлшаринг не работает, запостил здесь
 

Sp1n

Мудрец
Сообщения
61
Реакции
29
mak

Посмотрю что там. Поправил для wow.

Нужно невалид инструкции определять, может есть список сигнатур ?

Есчо нужно сделать быструю сборку процедур, тоже такого ничего нет ?
 

Прикрепленные файлы:

  • Понравилось
Реакции: mak

Sp1n

Мудрец
Сообщения
61
Реакции
29
Посмотрел профайл трансляции указателя в описатель:
i2h.png
- до 256 адресов не медленее авл. Это если использовать таблицу указателей, индексирующую таблицу описателей.

Очевидно что ветвь должна находиться по указателю, а не по диапазону. Тогда не будет трабл с пересекающихся кодом.

Тут есть алго оптимизации ветвлений(branch displacement optimization). Используется массив отсортир. ветвление, а это не профайл. Как сделать быстро(структура у графа) хз, хранить для каждой инструкции список ветвленией.. тогда проход по списку медленный из за проверок диапазона. Короче ничего не понятно :(
 

Прикрепленные файлы:

  • Понравилось
Реакции: mak

mak

Соломенные сандалии
Администратор
Сообщения
930
Реакции
855
Нужно невалид инструкции определять, может есть список сигнатур ?
Возможно ли такое, вручную такой анализ не сделать мне кажется, у интел такого не встречал.

Есчо нужно сделать быструю сборку процедур, тоже такого ничего нет ?
А чем отличается от доступа по указателю? Этапы такие же, как я вижу, разница лишь в определении границ и ловушках. Всё как и ранее, когда блоками исполнение идёт .. но вопрос о быстром доступе к описателю остаётся.
 

Прикрепленные файлы:

mak

Соломенные сандалии
Администратор
Сообщения
930
Реакции
855
Тут есть алго оптимизации ветвлений(branch displacement optimization). Используется массив отсортир. ветвление, а это не профайл. Как сделать быстро(структура у графа) хз, хранить для каждой инструкции список ветвленией.. тогда проход по списку медленный из за проверок диапазона. Короче ничего не понятно
Такие задачи я решаю визуально, на листе бумаге или используя MindMap или более сложные в UML, далее когда схема построена и логически верна, начинается оптимизация и постановка задачи.

Для обзора можно посмотреть вот этот топик - Hash tables for ultra fast dictionaries

Этот код к пдф-ке ниже, в репе есть эта PDF тоже.
https://github.com/Shrey-Viradiya/MultiLevelHash_Tree
https://github.com/Shrey-Viradiya/MultiLevelHash_Tree/archive/refs/heads/master.zip

Можно посмотреть тему по Nearest neighbour, https://github.com/norouzi/mih, http://www.cs.toronto.edu/~norouzi/research/mih/, многое зависит от самой структуры данных.

Ещё стоит учесть размер адреса для подбора алгоритма хеширования, выше по линку это обсуждают. Не знаю как будет по скорости, но глянуть можно. Каждый алго нужно тестить и свой билд делать, т.к. тесты в реальных условиях показательнее чем логический расчёт.
 

Прикрепленные файлы:

Sp1n

Мудрец
Сообщения
61
Реакции
29
mak

> когда схема построена

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

> А чем отличается от доступа по указателю?

Когда найдено ветвление нужно в графе найти описатель те ветвь может описана. Сделать можно по адресу, транслируя на описатель - таблицы, либо проход по спискам с проверкой диапазона как тот же авл. Можно использовать адресную трансляцию, учитывая что релоцируется все апп, вот только это ценный механизм в плане ресурсов. Нужно очень много памяти, причем на описатель типа dword, а размер поболее нужен - синхрон маркера всякие..
 
Верх Низ