automaton.txt

                   ПРЕОБРАЗОВАНИЕ КОДА И КОНЕЧНЫЕ АВТОМАТЫ
                   ---------------------------------------
               (проектируем очень хуево дизассемблируемый код)


   Существует такой интересный объект, как конечный автомат (finite automaton).
   Этот автомат обладает внутренними состояниями (это просто такие переменные),
   при изменении которых происходят определенные действия.
   Таким образом, есть набор действий,
   каждое из которых определяется текущим состоянием автомата,
   и/или переходом из одного состояния в другое,
   и матрица, определяющяя переходы между состояниями.

   Рассмотрим простую задачку:
   есть строка вида "1,3-7,9-100,105" которую надо преобразовать
   в бинарный вид.
   Рассмотрим реализацию, основанную на технологии конечных автоматов (еще
   говорят switch-технология).
   Введем внутренние состояния автомата.

   0 - до первого (до '-') числа
   1 - внутри первого числа
   2 - до второго (после '-') числа
   3 - внутри второго числа
   4 - конец строки (после последнего символа)
   5 - ошибка синтаксиса

   тогда программа представляется в таком виде:

   c  - указатель на текущий символ
   *c - текущий символ разбираемой строки
   A  - номер действия

  переход  cимвол  A  действие:      ситуация:

   0-->1    0..9   1  l=*c-'0';      новая пара чисел, встречена цифра
   0-->5   другие                    новая пара чисел, встречена НЕ цифра
   1-->0     ,     2  store(l,l);    одно число, в конце ','
   1-->1    0..9   3  l=l*10+*c-'0'  добавить символ к первому числу
   1-->2     -                       два числа, первое закончилось на '-'
   1-->4    eoln   2  store(l,l);    одно число, после него - конец строки
   1-->5   другие                    недопустимый символ в первом числе
   2-->3    0..9   4  h=*c-'0';      два числа, после '-' цифра
   2-->5   другие                    два числа, после '-' НЕ цифра
   3-->0     ,     5  store(l,h);    два числа, в конце ','
   3-->3    0..9   6  h=h*10+*c-'0'; добавить символ к второму числу
   3-->4    eoln   5  store(l,h);    два числа, после них - конец строки
   3-->5   другие                    недопустимый символ во втором числе
   4-->            7  exit();        конец строки (после последнего символа)
   5-->            8  error();       ошибка синтаксиса

   тогда таблица действий при переходах между состояниями выглядит так:

           с      следующее состояние:
         т о       0  1  2  3  4  5
         е с        номер действия:
         к т   0   -  1  -  -  -  2
         у о   1   3  4  5  -  3  2
         щ я   2   -  -  -  6  -  2
         е н   3   7  -  -  8  7  2
         е и   4   -  -  -  -  -  -
           е   5   -  -  -  -  -  -

   Простой исходник на си будет выглядеть так:

    int S = 0;
    char*c = "1,3-7,9-100,105";

    for(;;)
    {
      switch(S)
      {
        case 0:
                if ( isdigit(*c)  ) { S=1; l=*c-'0';      } else
                                    { S=5;                };
                break;
        case 1:
                if ( *c == ','    ) { S=0; store(l,l);    } else
                if ( isdigit(*c)  ) { S=1; l=l*10+*c-'0'; } else
                if ( *c == '-'    ) { S=2;                } else
                if ( *c == 0      ) { S=4; store(l,l);    } else
                                    { S=5;                };
                break;
        case 2:
                if ( isdigit(*c)  ) { S=3; h=*c-'0';      } else
                                    { S=5;                };
                break;
        case 3:
                if ( *c == ','    ) { S=0; store(l,h);    } else
                if ( isdigit(*c)  ) { S=3; h=h*10+*c-'0'; } else
                if ( *c == 0      ) { S=4; store(l,h);    } else
                                    { S=5;                };
                break;
        case 4:
                exit();
                break;
        case 5:
                error();
                break;
      }
      c++;
    }

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

x:
  x0:
                if ( isdigit(*c)  ) { l=*c-'0';      c++; goto x1; } else
                                    {                c++; goto x5; };
  x1:
                if ( *c == ','    ) { store(l,l);    c++; goto x0; } else
                if ( isdigit(*c)  ) { l=l*10+*c-'0'; c++; goto x1; } else
                if ( *c == '-'    ) {                     goto x2; } else
                if ( *c == 0      ) { store(l,l);    c++; goto x4; } else
                                    {                     goto x5; };
  x2:
                if ( isdigit(*c)  ) { h=*c-'0';      c++; goto x3; } else
                                    {                     goto x5; };
  x3:
                if ( *c == ','    ) { store(l,h);    c++; goto x0; } else
                if ( isdigit(*c)  ) { h=h*10+*c-'0'; c++; goto x3; } else
                if ( *c == 0      ) { store(l,h);    c++; goto x4; } else
                                    {                     goto x5; };
  x4:           exit();
  x5:           error();
        goto x

   Полученный код, будучи скомпилированным с оптимизацией, крайне труден
   для дизассемблирования, и вот по какой причине:
   при попытке его восстановления в классические си-конструкции, типа
   for, while, if-else, останутся "лишние" goto, и если их будет много,
   то понять смысл будет исключительно сложно.
   Граф переходов между блоками для подобной программы будет отличаться
   от графа для классической программы бОльшим количеством
   перекрещивающихся связей.
   Для восстановления этого кода в исходный вид,
   придется выделить постоянные блоки кода, пронумеровать их, затем заново
   ввести переменные-состояния, и только тогда будет возможно пытаться
   что-то понять дальше. Но это представляется непростой задачей,
   потому что выделение тех же самых блоков кода что и были в исходном
   состоянии, после компиляции с оптимизацией становится в некоторых случаях
   весьма затруднительным, так как блоки могут делиться на части,
   объединяться и перемешиваться.

   Теперь рассмотрим более сложный исходник:

    int T[256] =
    {
      4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
      //                      , -      0 1 2 3 4 5 6 7 8 9
      0,0,0,0,0,0,0,0,0,0,0,0,2,3,0,0, 1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,
      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
      0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
    };

    for(;;)
    {
      int A;
      switch( S )
      {
        case 0:
                switch( T[*c] )
                {
                  case 1:  { S=1; A=1; }; break;
                  default: { S=5; A=2; }; break;
                }
                break;
        case 1:
                switch( T[*c] )
                {
                  case 2:  { S=0; A=2; }; break;
                  case 1:  { S=1; A=3; }; break;
                  case 3:  { S=2;      }; break;
                  case 4:  { S=4; A=2; }; break;
                  case 0:  { S=5;      }; break;
                }
                break;
        case 2:
                switch( T[*c] )
                {
                  case 1:  { S=3; A=4; }; break;
                  default: { S=5;      }; break;
                }
                break;
        case 3:
                switch( T[*c] )
                {
                  case 2:  { S=0; A=5; }; break;
                  case 1:  { S=3; A=6; }; break;
                  case 4:  { S=4; A=5; }; break;
                  default: { S=5;      }; break;
                }
                break;
        case 4:
                A = 7;
                break;
        case 5:
                A = 8;
                break;
      }
      switch( A )
      {
        case 1: { l=*c-'0';      c++; }; break;
        case 2: { store(l,l);    c++; }; break;
        case 3: { l=l*10+*c-'0'; c++; }; break;
        case 4: { h=*c-'0';      c++; }; break;
        case 5: { store(l,h);    c++; }; break;
        case 6: { h=h*10+*c-'0'; c++; }; break;
        case 7: { exit();             }; break;
        case 8: { error();            }; break;
      }
    }

    Как видим, последний пример написан без команд сравнения и условных
    переходов.

    В таком виде программа представляет собой цикл из трех частей:
    в первой части анализируются внешние данные (здесь это строка символов),
    и преобразуются в некоторые внутренние переменные (здесь это показано
    неявно через массив T[]), затем вычисляются переходы по таблицам между
    состояниями (здесь это первый switch), и одновременно на каждом таком
    переходе выбирается из таблиц номер действия (здесь это опять же первый
    switch и переменная A), и в третьей части цикла выполняется некоторое
    реальное действие (здесь это второй switch).

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

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

    Подобные таблицы могут быть преобразованы в функцию.

    Требования к такой функции просты: на вход ей подается
    число, в котором закодированы текущие состояния, а на выходе
    получается число, в котором закодированы следующие состояния и номер
    действия.
    Таким образом работа программы будет заключаться в итерации
    такого цикла:
    1. Вызвать функцию, передав в нее текущие состояния,
       затем из результата извлечь новые значения состояний и
       номер действия.
    2. Выполнить действие, определяемое полученным номером.

    Рассмотрим следующий вариант.
    Состояниями являются значения регистров EAX..EDI, а номером
    действия является численное значение байтов, определяющих
    некую инструкцию, дополненную либо NOP'ами либо командой RETN.

    Тогда ВСЯ наша программа будет являться... функцией.
    Изначально, на вход этой функции подается, к примеру,
    EAX = 2, ECX = 3, остальные = 0, команда NOP.
    Тогда число будет, например, таким:
              00000000...00000003000000020000C390
              <--EDI->...<--ECX-><--EAX-><--cmd->
    На выходе функция дает результат:
              00000000...00000003000000020000C341
              <--EDI->...<--ECX-><--EAX-><--cmd->
    что соответствует команде inc ecx,
    и тем же самым состояниям-значениям регистров.
    Тогда мы выполняем полученную команду, и меняется состояние ecx,
    и мы подаем в функцию такое число:
            00000000...00000004000000020000С341
            <--EDI->...<--ECX-><--EAX-><--cmd->
    и так далее.
    К числу, понятно, надо еще добавить уникальный номер
    каждой инструкции в программе, потому что сами опкоды
    могут повторяться.

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

    Возникает вопрос: как построить такую функцию.

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

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

    Поэтому рассмотрим упрощенный вариант.

    Аргументом функции будет номер состояния.
    Результатом будет число размером в WORD.
    Старшим байтом результата будет первый байт опкода.
    Младшим байтом будет номер состояния,
    а его младшим битом -- значение флага ZF.
    Поэтому появится возможность убрать из программы
    команды вида JZ/JNZ, и закодировать их
    посредством переходов между состояниями.
    Сама программа будет криптовать текстовую строчку.

    Исходный код программы:

           ДЕЙСТВИЯ:               СОСТОЯНИЯ И ПЕРЕХОДЫ:
                                      NZ          ZR
xormsg:                            -1 --> 00
         xor     edx, edx          00 --> 02   01 --> 02
cycle1:  lea     esi, msg          02 --> 04   03 --> 04
         mov     ecx, msg_size     04 --> 06   05 --> 06
cycle2:  xor     [esi], dh         06 --> 08   07 --> 08
         sub     dh, dl            08 --> 10   09 --> 10
         inc     esi               10 --> 12   11 --> 12
         dec     ecx               12 --> 06   13 --> 14
         jnz     cycle2
         inc     dl                14 --> 16   15 --> 16
         cmp     dl, 'Z'           16 --> 02   17 --> 18
         jne     cycle1
         retn                      18

    Функция, заданная таблицей:

       Аргумент   Значение

        f( -1 ) = 0x3300
        f(0x00) = 0xBE02
        f(0x01) = 0xBE02
        f(0x02) = 0xB904
        f(0x03) = 0xB904
        f(0x04) = 0x3006
        f(0x05) = 0x3006
        f(0x06) = 0x2A08
        f(0x07) = 0x2A08
        f(0x08) = 0x460A
        f(0x09) = 0x460A
        f(0x0A) = 0x490C
        f(0x0B) = 0x490C
        f(0x0C) = 0x3006
        f(0x0D) = 0xFE0E
        f(0x0E) = 0x8010
        f(0x0F) = 0x8010
        f(0x10) = 0xBE02
        f(0x11) = 0x0012

    Теперь сгенерируем функцию.
    Пусть это будет полином. Хоть и тривиально, но интересно.

      f(X) = SUMi( C[i]*X^i ), i=0..18

    Здесь X -- аргумент функции, который, как мы решили, есть текущее
    состояние, а в возвращаемом функцией числе будет закодировано
    следующее состояние и первый байт инструкции.

    Нахуячим простенькую програмку по подсчету коэффициентов полинома: см. (1)

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

  float calc(float X)
  {
    float y = 0;
    for(int j=0; j<N; j++)
      y += pow(X,j) * C[j];
    return y;
  }

   Или же, в более приятном виде:

N                       equ     19

go_next_state:          pushf  ; IN/OUT: EBX=current/next state
                        pusha
                        finit
                        fild    dword ptr [esp+4*4]     ; pusha.ebx
                        push    N
                        pop     ecx
                        lea     edx, C_table
                        fldz            ; st(1)
                        fld1            ; st(0)
__c1:                   fld     st(0)
                        fld     tbyte ptr [edx]
                        fmulp
                        faddp   st(2),st(0)
                        fmul    st(0),st(2)
                        add     edx, 10
                        loop    __c1
                        fistp   dword ptr [esp+4*4]     ; pusha.ebx
                        fistp   dword ptr [esp+4*4]     ; pusha.ebx
                        popa
                        popf
                        retn

C_table                 label   tbyte
  dt      4.864199999999999986e+04   ; C[ 0]
  dt      1.052028658321440037e+06   ; C[ 1]
  dt     -2.226893544084362929e+06   ; C[ 2]
  dt      1.054917653361728822e+06   ; C[ 3]
  dt      1.030581898921544049e+06   ; C[ 4]
  dt     -1.641889337850409245e+06   ; C[ 5]
  dt      1.056816179457771135e+06   ; C[ 6]
  dt     -4.226269487577827341e+05   ; C[ 7]
  dt      1.179126264336835917e+05   ; C[ 8]
  dt     -2.418954943314347526e+04   ; C[ 9]
  dt      3.749247680199179089e+03   ; C[10]
  dt     -4.446691826539333110e+02   ; C[11]
  dt      4.044639078866551414e+01   ; C[12]
  dt     -2.801020107772053989e+00   ; C[13]
  dt      1.450610807381378830e-01   ; C[14]
  dt     -5.436999378694686739e-03   ; C[15]
  dt      1.391774067561251339e-04   ; C[16]
  dt     -2.174850123595773034e-06   ; C[17]
  dt      1.563443629925163634e-08   ; C[18]

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

    Вот программа, полученная в результате всех этих извращений:

                        .data

msg                     db      'Бля, пошли все нахуй, мудаки!',0
msg_size                equ     $-msg

start:
                        call    xormsg

                        push    0
                        push    offset msg
                        push    offset msg
                        push    0
                        callW   MessageBoxA

                        call    xormsg

                        push    0
                        push    offset msg
                        push    offset msg
                        push    0
                        callW   MessageBoxA

                        push    -1
                        callW   ExitProcess

xormsg:
                        xor     ebx, ebx    ; начальное состояние = -1
                        dec     ebx

                        jmp     begin

cycle:                  pushf               ; копируем ZF в младший бит EBX
                        push    eax         ;
                        lahf                ;
                        shr     ah, 6 ; ZF  ;
                        and     ah, 1       ;
                        and     bl, 0FEh    ;
                        or      bl, ah      ;
                        pop     eax         ;
                        popf                ;
begin:
                        call    go_next_state ; вычисляем следующее состояние

                        cmp     bl, 18      ; последнее состояние --> выход
                        jae     quit

                        push    eax ecx     ; берем первый байт инструкции из
                        mov     cl, bh      ; результата функции, и патчим себя
                        mov     bh, 0
                        mov     eax, jtab[ebx*4]
                        mov     [eax], cl
                        pop     ecx eax

                        jmp     jtab[ebx*4] ; переходим на действие

quit:                   retn

jtab                    label   dword       ; таблица указателей на действия
                                            ; index = номер действия =
                        dd      s00,s01     ;       = номер состояния
                        dd      s02,s03
                        dd      s04,s05
                        dd      s06,s07
                        dd      s08,s09
                        dd      s10,s11
                        dd      s12,s13
                        dd      s14,s15
                        dd      s16,s17
s00:
s01:                  ; xor     edx, edx
                        db      ?,0D2h
                        jmp     cycle
s02:
s03:                  ; lea     esi, msg
                        db      ?
                        dd      offset msg
                        jmp     cycle
s04:
s05:                  ; mov     ecx, msg_size
                        db      ?
                        dd      msg_size
                        jmp     cycle
s06:
s07:                  ; xor     [esi], dh
                        db      ?,36h
                        jmp     cycle
s08:
s09:                  ; sub     dh, dl
                        db      ?,0F2h
                        jmp     cycle
s10:
s11:                  ; inc     esi
                        db      ?
                        jmp     cycle
s12:
s13:                  ; dec     ecx
                        db      ?
                        jmp     cycle
s14:
s15:                  ; inc     dl
                        db      ?,0C2h
                        jmp     cycle
s16:
s17:                  ; cmp     dl, 'Z'
                        db      ?,0FAh,'Z'
                        jmp     cycle

    Теперь, чтобы пронять логику работы программы, надо взять функцию,
    и получить все ее значения для всех возможных состояний,
    а затем составить таблицу переходов между состояниями,
    и заменить их на jz/jnz.
    После этого, если программа не была спроектирована как конечный автомат,
    так, как это показано в начале статьи, то можно будет реверсировать
    ее в классические си-конструкции типа if, for, while.

    На этом перейдем к теории.

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

    Предположим, что в качестве переменной части состояния автомата
    был бы использован не флаг ZF, а, скажем, значение регистра AL.
    Тогда для получения всей информации, закодированной в функции,
    на каждом шаге пришлось бы анализировать 256 вариантов.
    А если бы это был регистр AX, то при проверке первых
    двух байт файла на MZ, из текущего состояния было бы 65534 перехода
    на одну ветвь исполнения, и 2 перехода на другую ветвь.
    При еще больших размерах состояний, перебор всех состояний на
    каждом шаге стал бы еще более трудным, и тогда часть программы,
    отвечающая за изменение того же exe файла была бы пропущена,
    то есть не была бы экстрактирована из функции.

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


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

--------------------------------------------------------------------------------

  Приложение (1) - программа для подсчета коэффициентов полинома.
                   Для понимания рекомендуется знание си и
                   самую малость линейной алгебры.

  #include <windows.h>
  #include <stdio.h>
  #include <stdlib.h>
  #include <assert.h>
  #include <io.h>
  #include <math.h>
  #pragma hdrstop

  #define float    long double

  int N = 19;

  float X[100] = {-1,0,2,4,6, 8,10,12,14,16,1,3,5,7, 9,11,13,15,17 };
  float Y[100] = {
    0+0x3300,
    2+0xBE00,
    4+0xB900,
    6+0x3000,
    8+0x2A00,
   10+0x4600,
   12+0x4900,
    6+0x3000,
   16+0x8000,
    2+0xBE00,
    2+0xBE00,
    4+0xB900,
    6+0x3000,
    8+0x2A00,
   10+0x4600,
   12+0x4900,
   14+0xFE00,
   16+0x8000,
   18+0x0000 };

  float C[100];

  float calc(float X)
  {
    float y = 0;
    for(int j=0; j<N; j++)
      y += pow(X,j) * C[j];
    return y;
  }

  void init()
  {
    float* Z = new float[ N*(N+1) ];
    assert(Z);

  #define Zyx(y,x)       Z[y*(N+1)+x]

    for(int y=0; y<N; y++)
    {
      for(int x=0; x<N; x++)
        Zyx(y,x) = pow(X[y], x);
      Zyx(y,N) = Y[y];
    }
    for(int n=0; n<N-1; n++)
    for(int y=n+1; y<N; y++)
    {
      float t = Zyx(y,n) / Zyx(n,n);
      for(int x=0; x<=N; x++)
        Zyx(y,x) -= Zyx(n,x) * t;
    }
    for(int n=N-1; n>=0; n--)
    {
      float s = 0;
      for(int t=n+1; t<=N-1; t++)
        s += Zyx(n,t) * C[t];
      C[n] = (Zyx(n,N) - s) / Zyx(n,n);
    }

    delete Z;

    for(int i=0; i<N; i++)
      assert(abs(calc(X[i]) - Y[i]) < 0.0001);
  }

  void main()
  {
    init();

    for(int n=0; n<N; n++)
      printf("f(%5.2Lf) (%02X) = %5.2Lf (%04X)\n", X[n],
      (int)ceil(X[n]), Y[n], (int)ceil(Y[n]));
    printf("f(X) = SUMi( C[i]*X^i ), i=0..%i\n", N-1);
    for(int n=0; n<N; n++)
      printf("dt %30.19Le  ; C[%2i]\n", C[n], n);

  }

--------------------------------------------------------------------------------