ПРЕОБРАЗОВАНИЕ КОДА И КОНЕЧНЫЕ АВТОМАТЫ --------------------------------------- (проектируем очень хуево дизассемблируемый код) Существует такой интересный объект, как конечный автомат (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 выход 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 #include #include #include #include #include #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=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