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

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

 

эт я похоже погорячился, всё намного проще

в рекурентном цикле вместо "джампа назад", будет "call на вход" + команды захламления\очистки стека, а так всё тоже самое
Хотя по прежнему не понимаю: общие черты конструкций это хорошо, но ведь конкретные условия продолжения\завершения цикла должны сильно влиять на результат, или ты ограничиваешься только грубой прикидкой?

 

1.

Isn`t it ? Есть кнешно теоремы, доказательства, но ... рекурсия бывает разная, и неявная в т.ч.
2. если программу рассматривать не как цельный кусок кода, а как независимые "потоки" control&data flow`а, то можно рассматривать их отдельно, что упрощает обработку и понимание процесса.

Код (Text):

1. char a[20];
2. for (int i=0;i<20;i++)
3.   a[i]=0;

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

Такой пример на первый взгляд непроходим:

Код (Text):

1. char a[20];
2. for (int i=0;i<a[i];i++)
3.   a[i]=0;

Но это только первый взгляд ...

Еще, по поводу реверс автомата: если немного подумать над сабжем, то можно увидеть много конструкций которые невозможно пройти прямым проходом, вот тут, обратный и появляется в виде побочного продукта...

PS: слабо придумать язык (метод) описания прохода подобных "идиом" ?

 

Подумал над рекурсией повнимательнее...
Рекурсия это не один, а два связанных цикла (хотя тело одного из них может быть и пустым)
1. Цикл "закрутки": состоит из блока комманд от точки входа, до call и завершается по условию.
2. Цикл "раскрутки": сотоит из блока комманд после call до ret и выполняется столько же раз, сколько и первый.
В обычной рекурсии оба цикла не могут иметь досрочного выхода типа ".BREAK .IF ...", однако в код предназначенный для обмана твоего анализатора его можно и встроить
Джимп из первого блока команд во второй является командой завершения первого цикла и перехода к выполнению второго. А джимп назад через call означает возврат из середины второго цикла опять к выполнению первого.

Код (Text):

1. iter PROC
2.   ... (тело первого цикла)
3.   cmp ...
4.   j.. @F
5.   call iter
6.   @@:
7.   ... (тело второго цикла)
8.  ret
9. iter ENDP

можно рассматривать как:

Код (Text):

1. iter_1:
2.    ...
3.    inc [iter_count]
4.    cmp ...
5. jn.. iter_1
6. iter_2:
7.    ...
8.    dec [iter_count]
9. jnz iter_2

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

 

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

 

Читал я с полгодика назад работу, описывающую попытки получения такого результа.
Если интересно:
G. Balakrishnan and T. Reps, Analyzing Memory Accesses in X86 Executables, in 13th International Conference on Compiler Construction, 2004

 

Что то у меня не получается файл выложить

 

alkor
Здорово. Я про то что не прикрепилось. Это к лучшему, когда я искал, наткнулся на хучу интересных доков. Странно, что до этого я их не встречал, хоть сабжем активно интересуюсь Сенкс.

ЗЫ: большие файлы (50К) не прикрепляются.

 

_Serega_

Есть такая задача, называется 3N+1:

Код (Text):

1. while(a>1ULL) //а - 64х-битное беззнаковое целое ;)
2. {
3.   if(a&1)
4.     a=a*3+1;
5.   a=a>>1;
6. }

Твой код сможет сказать при каких A этот цикл завершится?