Вопрос. Оба потока команд должны укладываться в требуемую модель в точности? Или возможно: первый поток call xxxx, второй поток call yyyy? По адресам xxxx, yyyy выполняются независимые процедуры
тут уже излагали мысль, повторюсь. пусть оба потока есть псевдокод, который исполняет виртуальная машина. в таком случае задача решается. в противном общего решения не видно. Главное вобще то не это, как спросил КК - кого это обманет? Т.е. непонятна цель. как академическое упражнение это хорошая задача. Надо давать ее хорошим студентам, чтоб показать что они не сильно хорошие студенты))))
Просто. 1. Создаем последовательность байт используя PRNG. 2. Проверяем, обладают ли полученные ветки требуемым побочным эффектом 3. Если нет, переходим к пункту 1 изменив seed PRNG. Правильный вопрос "можно ли это сделать за полиномиальное время?"
Я согласен с J0E, по крайней мере для начала сойдет. Ведь сначала нужно набрать данные а потом думать. Думаю если снабдить брутфорс предварительной проверкой на явные UD-операции (т.е. проходится каждая ветка и по длинам инструкций быстро чекается всякая херь типа gs:/группы call/jump [ofs32]/etc), а затем выполняем каждую ветку под SEH/либо мулятором. Если после прогона все ветки выжили без исключений - в лог, далее смотреть что там и анализировать. Полагаю, байтов 8-10 можно посмотреть в "полиноминальное" время (и заодно на машине без аналитики получить сложность таких вычислений).
генерируем 2 длинные случайные последовательности. проверяем входит ли одна в другую. если не входит - повторяем генерацию. вероятность успеха на коротких цепочках и oo времени таки да, ненулевая.
