Разорвать граф.

Вопрос. Оба потока команд должны укладываться в требуемую модель в точности?
Или возможно: первый поток call xxxx, второй поток call yyyy? По адресам xxxx, yyyy выполняются независимые процедуры

 

medstrax1
В один блок.

 

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

 

Просто.
1. Создаем последовательность байт используя PRNG.
2. Проверяем, обладают ли полученные ветки требуемым побочным эффектом
3. Если нет, переходим к пункту 1 изменив seed PRNG.

Правильный вопрос "можно ли это сделать за полиномиальное время?"

 

Я согласен с J0E, по крайней мере для начала сойдет. Ведь сначала нужно набрать данные а потом думать. Думаю если снабдить брутфорс предварительной проверкой на явные UD-операции (т.е. проходится каждая ветка и по длинам инструкций быстро чекается всякая херь типа gs:/группы call/jump [ofs32]/etc), а затем выполняем каждую ветку под SEH/либо мулятором. Если после прогона все ветки выжили без исключений - в лог, далее смотреть что там и анализировать.

Полагаю, байтов 8-10 можно посмотреть в "полиноминальное" время (и заодно на машине без аналитики получить сложность таких вычислений).

 

генерируем 2 длинные случайные последовательности. проверяем входит ли одна в другую. если не входит - повторяем генерацию.
вероятность успеха на коротких цепочках и oo времени таки да, ненулевая.

 

Improvements on Hiding x86-64 Instructions by Interleaving

 

Можно на этом построить дизасм назад.

Проход дизом длин назад от -15, маркировка инструкций ветви как сходящейся/расходящейся(оптимизация), и новый проход назад.

Код (Text):

1. IsCross(I, P):
2.    push(0)
3.    Do
4.       D = I - P   ; Смещение от инструкции.
5.       if -D: > Fail:fi   ; Инструкция I внутри P-1.
6.       if !D: > Good: fi   ; I = P схождение ветви на I.
7.       if Flow{D}: > Good: fi   ; Схождение далее по ветви.
8.       if Cros{D}: > Fail: fi   ; Расхождение далее.
9.       push(D)
10.       P + LDE(P)   ; Следующая инструкция.
11.    Loop
12.  
13. Good:   ; Все инструкции ветви сходятся.
14.    !Result
15.    Do
16.       pop(D)
17.       Flow{D}
18.       if !D: end: fi
19.    Loop
20.  
21.  
22. Fail:   ; Все расходятся.
23.    Result
24.    Do
25.       pop(D)
26.       Cros{D}
27.       if !D: end: fi
28.    Loop

Проход пока все ветви не сойдутся:

Код (Text):

1.    P = I
2. Back:
3.    E = P
4.    P - 14   ; Макс длина -1.
5.    X = IsCross(I, P)
6.  
7.    rep
8.       P+
9.       Y = IsCross(I, P)
10.       if X <> Y: > Back: fi
11.    until P = E

Должно быть схождение только одной ветви.