Реверсинг и конечные автоматы

Такое вот дело:

Есть функция на вход которой передается структура с описанием х86 кода.

В качестве результата : 1.) описатель конечного автомата (ну можно так назвать), характеризующего этот код для всех возможных входных вариантов данных, 2.) либо некий реверс-автомат, который указывает что должно быть на входе, что-б на выходе получилось исходное значение , такая вот ерунда, понимаю, что объяснил - не очень, поэтому в аттаче обобщенный рисунок-пример результата для функции СтрЛен (без описателя среды, т.е. атрибутов страниц памяти, расположения стека, расположения данных и др.).

Вопрос состоит в следующем, придумать такой х86 код, который функция будет ооочень долго жевать (исключая самомодифицирующийся код - там другие методики), а если не пережует, то вообще - СУПЕР!

Либо можете высказать своё ИМХО, например, что такое невозможно; я, по крайней мере, для случая 1. придумать не могу

 

Ни фига непонятно!

 

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

 

так... значит берём StrLen.... на выходе 4, значит строка должна быть длиной 4 символа.... если на выходе 1024, значит на входе.... мда... без реверса "конечного автомата" никак, т.к. очень долго жевать... 1024 это не 4, это ж больше....

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

я правильно понял?

 

_Serega_
Давай перефразирую (грубо): есть машина Тьюринга (алгоритм), выполняющий некоторую последовательность инструкций. Вопрос, существует ли такая последовательность инструкций, которую она не сможет выполнить. Ответ известен - да, существует. Даже есть конструктивная теорема на этот счет.
А твой вопрос требует уточнения - что за декомпайлер.

 

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

Нет, это излишне. Только листинг на асме.

 

crypto

У меня на столе лежит книженция по автоматам к-ю я почти не читал , А что за теорема? В смысле название ее какое?

 

_Serega_
А рекурсию(конечную и бесконечную), как переваривает?

 

_Serega_
А название книженции какое? Лучше книгу прочти, сам все и узнаешь

 

Pavia
Спасибо за участие.

К сожалению пока никак, циклы конечные и бесконечные в общем случае проскакивают на ура.
С Call`ми алгоритм пока еще не выработан, отдельно анализируется то, что до, и после Call`а. Сложные блоки разбиваются на более простые (как в случае Call`а).

 

crypto

Уточню, потому что перефразировка получалась вкорне неправильна. Анализируются граничные значения (BOUND`ы), регистров и переменных в блоке кода, и для каждой ветви ControlFlow`а, эти граничные величины выводятся как отдельные состояния автомата.

 

_Serega_
Можно уточнить? Твоя функция анализирует структуру ассемблерного кода (конструкции if, if-else, for, while, switch)? И тебя интересует, есть ли такая конструкция, которую твоя функция не проглотит?

 

Рисунок абсолютно чёрный только у меня?

А, это опера его не отображает..

 

IceStudent
У меня нормальный.

 

А что будешь делать с ассиметричными алгоритмами, хешами? Там по результату ведь нельзя получить входные данные.

 

crypto

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

Нет, такие структуры есть, интересен случай когда проанализировать код будет очень долго.
Приведу простейший пример:

Исходные данные:
EAX = [0..5] (лежит в пределах от 0..5)
EBX = [6..12]

КОД:
ADD EAX,EBX

Результат:
EAX = [6..17]
EBX = [6..12]

Естественно КОД может быть с циклами и ветвлениями. Но суть является не приведение мегабайтного листинга, а 10-15 команд которые даже человек загнется таким образом анализировать.

 

IceStudent

Абсолютно верно, реверс алгоритмы, например ситуация с модулем деления очень туго, но это к счастью, второстепенный 2.) вопрос.
Также целевой код это - не RSA алгоритмы, а большей частью похожий на стандартные сишные функции работы со строками. Еще туда-же указатели на все и вся. То есть код сепарируется не только по ветвям ControlFlow`a а и еще по ветвям DataFlow`a.

 

_Serega_
Есть такие функции - однонаправленнные, вот их наверное твой автомат не прожует в обратную сторону.

 

_Serega_
А можно популярно обьяснить зачем оно такое может быть полезно?

 

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