Нужен алгос/абстракция для следующей задачи.

Имеется массив областей памяти, занимаемых некоторым кодом, это блоки памяти, в которых код расположен, они соответственно могут располагаться по разным базовым адресам, иметь произвольный размер и не пересекаться.

Необходимо записать новый код поверх этих блоков, расположить его в этих областях памяти.

Проблема заключается в следующем. Записать код нужно с оптимизацией по размеру ветвлений, если возможно короткое ветвление, то не использовать длинное. Если заполнять блок инструкциями и ветвь(процедура) не поместиться, то следующие инструкции располагаются в новом блоке и оба блока связываются ветвлением. Размер его так же может быть длинным или коротким, он зависит от адреса самого ветвления в блоке и адреса следующего блока. Что бы это вычислить необходимо заполнить текущий блок до конца и определить пригодность следующего блока для записи хотя бы одной инструкции и ветвления при необходимости, опять же размер ветвления будет завесить от последующих блоков, тоесть это рекурсия и довольно запутанная задача. Если при заполнении блока он окажется не пригоден, то это может повлиять на все предыдущие блоки из за удлинения ветвлений

-----
vx

| Сообщение посчитали полезным:

difexacaw вы что курили перед сном? вцелом все что вы описали.. если я правильно понял, это код вирусняка

-----
Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....

| Сообщение посчитали полезным:

лихо закручен сюжет.

| Сообщение посчитали полезным:

VodoleY

К малваре отношения не имеет(там такое не юзается), это скорее наоборот.

-----
vx

| Сообщение посчитали полезным:

За такое описание задачи нужно клавиатурой бить.
Что мешает завести список адресов ветвлений и при переходе на новый блок обрабатывать неправильные ветви?
Адреса предыдущего блока известны, адрес нового блока известен и стало быть вычисления тривиальны.
Вектора достаточно и нет никакой необходимости в рекурсии, достаточно цикла на размер буфера, при каждом новом блоке править старый, и так до полной записи буфера.
Можно отложить запись первого блока до нахождения второго, после нехитрых вычислений можно писать часть буфера на размер первого блока и так до финального, в этом варианте правок не нужно вносить, поскольку буфер можно формировать, как душе угодно, поскольку о предыдущем блоке известно все, можно перезаписывать, морфить или выкидывать ветви. В данном случае нет необходимости в рекурсии, достаточно записать начальный и конечный адрес блока.
Профит.
Скорее всего не осилил задачу, ибо описание удручает.
Ps. DBI тул пишите?

| Сообщение посчитали полезным:

VodoleY пишет:
difexacaw вы что курили перед сном? вцелом все что вы описали.. если я правильно понял, это код вирусняка

Сначала была тема - обход аверов, теперь и до вкусняшек добрались )))) Видимо кто-то во истину хочет в голове ничего не имея Дядю Женю отшлепать..

| Сообщение посчитали полезным:

Не понятно зачем какие-то крутые алго. Тот же код что пишет новые инстракшн будет проверять длину блоков?
Влазит мой блок в старый блок? Нет, добавим еще один следующий старый блок и посмотрим можно ли на него в 127 байт прыгнуть, итд.

| Сообщение посчитали полезным:

neshta

> Что мешает завести список адресов ветвлений и при переходе на новый блок обрабатывать неправильные ветви?
...

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

> Ps. DBI тул пишите?

Ага.

-----
vx

| Сообщение посчитали полезным:

Rainbow пишет: Сначала была тема - обход аверов, теперь и до вкусняшек добрались

Задача к аверам не имеет отношения, здесь более фундаментальные вещи CFI\CFG, а это можно использовать и в вполне светлых целях, например защита от ROP.

| Сообщение посчитали полезным:

hash87szf

> Тот же код что пишет новые инстракшн будет проверять длину блоков?

Да.

> Влазит мой блок в старый блок?

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

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Нужно не такое, а последовательно заполнить

В первом цикле пройтись по всем блокам, записать адреса в массив, а вторым циклом записать блоки.
Читаем блоки с учетом размера буфера, когда получаем достаточное количество блоков (с учетом ссылок), то вторым циклом пишем все блоки. На размер памяти нет ограничений?

| Сообщение посчитали полезным:

neshta

Покажите плз на примере, а то не понятно

На буфер ограничений нет.

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет:Покажите плз на примере, а то не понятно

Уже года три как забросил кодинг и на машине нет компиля, поэтому псевдокод.
Для удобства буду использовать dict.

vec = [] наш вектор для сохранения промежуточных данных.
буду исходить из предположения, что у вас уже есть трейсер\читалка памяти.
x,y,z = 0 переменные для хранения промежуточного результата
крутим цикл до нахождения необходимого места, если оно конечно есть
for инструкция in листинг[начало, конец] je 0x000, call 0x000, etc
{
сохраняем промежуточные данные, начало блока, размер блока
if инструкция == ссылка // проверяем на ребро je\jmp\jnz\etc
{
vec.add( { начало=x, конеч=y, длина=z } )
обнуляем переменные
}
}
for v in vec
{
листинг[v.x, v.y].write(buffer[v.z]) не забываем учитывать длину инструкций, можно проверить влезет ли данный размер в данный блок, сложение длин инструкций.
pos+= v.z сохраняем размер записанного блока, ибо незачем усложнять описание с позицией массива -1. Далее смещаем начальную позицию буфера на pos, хотя это и так очевидно.
}
собственно все, думаю промежуточные данные незачем описывать, ибо все очевидно.

| Сообщение посчитали полезным: difexacaw

neshta

Всё равно не понимаю. Vec[] будет содержать массив блоков, на которые есть ссылки или текущих. Но ветвление же не обязательно на начало массива, тоесть ветви(рёбра") расположены не в начале блоков, они могут быть где угодно.

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Vec[] будет содержать массив блоков, на которые есть ссылки или текущих

Vec[] будет содержать адрес начала блока и адрес конца блока пригодного для записи.
Лучше скину в ЛС пример с линком на описание графа.

| Сообщение посчитали полезным:

neshta

Мне саму идею понять нужно. Вот проходим мы по графу, обнаружили что на инструкцию есть ветвление. Как дальше поступить. Если такая конструкция есть, то по мойму можно только удлинить размер ветвления(если расстояние до ветви не позволяет использовать короткое) и начать перезапись в блоки ветвления.

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Вот проходим мы по графу, обнаружили что на инструкцию есть ветвление. Как дальше поступить

Зависит от того, что и с какими целями пишем, думаю буфер в любом случае придется выравнивать (блок записи), поскольку блоки под буфер явно никто делать не будет (размер), можно выровнять нопами или удлинить ветвь, но опять же, зависит от того, что там идет дальше (тут уже нужно смотреть индивидуально, от размера блока и куда ведет переход), граф лучше собирать после сбора всех ребер, после уже билдить буфер под расстояния, иначе придется пилить анализатор кода.

| Сообщение посчитали полезным:

neshta

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

> удлинить ветвь, но опять же, зависит от того, что там идет дальше

Именно про это и вопрос, а заполнить абы как блоки куда что влезет это не проблема.

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Именно про это и вопрос

проверяем ссылку на возможность модификации, смотрим размер блока (с учетом длин инструкций, дизассемблер шинглов, где блок является шинглом, реализации кстати есть и именно для таких же целей) если возможно, то увеличиваем блок и исправляем адресацию с учетом смещения, если нет, меняем размер буфера до максимально возможного (поиск расстояний, мин и макс) по необходимости выравниваем нопами, если остался кусок какой то инструкции, а что то еще придумывать даже не знаю. часть анализа можно выполнить в первом цикле, часть во втором, хотя в принципе все влезает в один проход, но излишне усложняет цикл.
по поводу того, что там идет дальше, так вы всегда можете проверить, ведь у вас есть адреса всех блоков и можете проверить, что там по ссылке + смещение блока.

| Сообщение посчитали полезным:

neshta

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

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

-----
vx

| Сообщение посчитали полезным:

difexacaw пишет: Если при этом длина удлиниться, то придётся выполнять повторное заполнение блоков, но не ясно с каких начать.

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

difexacaw пишет: На счёт рекурсии - я описал в первом посте, мы не можем знать заранее, сколько инструкций влезет в текущий блок

завести еще один буфер на адреса смещений и в третьем цикле уже точно будем знать что где и что куда может влезть.

| Сообщение посчитали полезным:

Накидали бесполезных ссылок на теорию графов в лк, эта матчасть всегда оторвана от реала и не пригодна. Вопрос открыт.

-----
vx

| Сообщение посчитали полезным:

Найдено следующее решение в общем виде:



-----
vx

| Сообщение посчитали полезным: neshta