CODE TRANSFORMATION AND FINITE AUTOMATONS ----------------------------------------- There are such interesting object as finite automaton. This automaton has some internal states (just such variables), so when they changed, some action is performed. So, there is set of actions, and each action is performed when some automaton's state is changed to some specified value, and there are matrix(es), which defines state changes. Here is simple task: to convert string like "1,3-7,9-100,105" into binary form. Lets consider implementation, based on finite automaton. Lets introduce single internal state S, and its values will be: 0 - before first (before '-') number 1 - inside of first number 2 - before second (after '-') number 3 - inside of second number 4 - end of string (after last char) 5 - syntax error so, program will look as follows: c - pointer to current character *c - current character's value A - action # change char A action: situation: 0-->1 0..9 1 l=*c-'0'; new pair, got digit 0-->5 other new pair, got NOT a digit 1-->0 , 2 store(l,l); single number, ends with ',' 1-->1 0..9 3 l=l*10+*c-'0' adding new digit to first number 1-->2 - two numbers, 1st one ends with '-' 1-->4 eoln 2 store(l,l); single number, ends with eoln 1-->5 other unavailable char within first number 2-->3 0..9 4 h=*c-'0'; two numbers, got digit after '-' 2-->5 other two numbers, got NOT a digit after '-' 3-->0 , 5 store(l,h); two numbers, ends with ',' 3-->3 0..9 6 h=h*10+*c-'0'; adding new digit to second number 3-->4 eoln 5 store(l,h); two number, ends with eoln 3-->5 other unavailable char within first number 4--> 7 exit(); eoln, all ok 5--> 8 error(); syntax error so, matrix which describes state changes and corresponding actions, will look as follows: next state: c 0 1 2 3 4 5 u s action #: r t 0 - 1 - - - 2 r a 1 3 4 5 - 3 2 e t 2 - - - 6 - 2 n e 3 7 - - 8 7 2 t 4 - - - - - - 5 - - - - - - Simple source in C will look as follows: 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++; } Now, if we will make source listed above a bit more low-level, and remove state-variables, we will get the following: 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 Now, if somebody will try to reverse this code into classical C constructions, such as for, while, if-else, there will remain many redundand goto(jmp) commands, and if number of them will be big enough, it will be very hard to understand what this code does. Execution graph for such code will differ from execution graph for classical code by larger amount of crossed links. To reverse this code into its source form, you should select constant code blocks, enum them, then introduce states, and only after that it will be possible to continue understanding this code. But this looks as a hard task, because while optimization, original code blocks can be divided into parts, mixed and merged. Now, lets consider a bit more complicated source: 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; } } As you can see, this sample is written without comparison commands, and conditional jmps; everything is based on switch'es which is equivalent to tables. In such form our program is a cycle, consisting of three parts: in first part, external data is analyzed (here it is string of chars), and converted into some internal variables (here it is shown indirectly using matrix T[]), then state changes are calculated (here it is first switch), and at the same time action # is calculated (here it is once again first switch and variable A), and in third part, some action is performed (here it is 2nd switch). And here is interesting moment: now, instead of program, we have action #'s (indexes of code blocks), and sequence of these indexes is the core of our program. Now lets consider the following question: how next action # is generated. It is generated depending on current automaton state values and some other data. This means that we can use tables, which will tell us which state is next, and which action should be executed on such state change. Such tables can be converted into a function. Requirements for this function are simple: argument of this function is a number, which contains current state values, and probably some identifier, and result of this function is a number, which contains next state values, probably another identifier, and action index. As such, our program will just iterate the following cycle: 1. Call main function, passing state values as argument; then extract new state values and action index from the result. 2. Execute action by given index, which will probably change state values too. Lets consider the following sample: States are register values, from EAX to EDI, and action number is an instruction value, padded with NOP's or RETN. Then, ALL main part our program will be a ...function. Lets initially pass to function: EAX = 2, ECX = 3, other regs = 0, command is NOP. So, argument will be: 00000000...00000003000000020000C390 <--EDI->...<--ECX-><--EAX-><--cmd-> Lets function result then will be: 00000000...00000003000000020000C341 <--EDI->...<--ECX-><--EAX-><--cmd-> which means same state values, and command = inc ecx. So, we execute given command, and ecx state is changed, and then we pass into a function this argument: 00000000...00000004000000020000C341 <--EDI->...<--ECX-><--EAX-><--cmd-> and so on. For sure, argument and result values can also contain unique instruction id, in case when some opcodes are duplicated. Interesting fact is that our function can indirectly encode many instructions, such as jumps and arithmetic commands. The only commands can not be encoded are commands modifying memory, working with other external devices and api-calls. So, the question appears: how to build such function. There can be many variants, from simple tables up to neural networks. In the sample given above, it is impossible, for sure, because there are many registers, and they can have many values, so function will be so big so it will not fit into existing computers. So, lets consider simplified sample. Argument of function is just a current state number. Result is WORD. High result byte is first opcode byte. Low result byte is state number, and low state bit is value of ZF flag. As such, we can indirectly encode JZ/JNZ commands. Also, state number is equal to action index. Program will just encrypt/decrypt some asciiz text string. Source: ACTIONS: STATES/ACTIONS AND STATE CHANGES: NZ ZR xormsg: -1 --> 00 1ST BYTE: xor edx, edx 00 --> 02 01 --> 02 33 cycle1: lea esi, msg 02 --> 04 03 --> 04 BE mov ecx, msg_size 04 --> 06 05 --> 06 B9 cycle2: xor [esi], dh 06 --> 08 07 --> 08 30 sub dh, dl 08 --> 10 09 --> 10 2A inc esi 10 --> 12 11 --> 12 46 dec ecx 12 --> 06 13 --> 14 49 jnz cycle2 inc dl 14 --> 16 15 --> 16 FE cmp dl, 'Z' 16 --> 02 17 --> 18 80 jne cycle1 retn 18 Here is a function, defined by arguments and results: Argument Result 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 Now lets generate a function. Let it be polynomial. f(X) = SUMi( C[i]*X^i ), i=0..18 Here X is function argument, which, as we decided, is current state, and function result contains next state and its first opcode byte. Simple program to calculate coefficients is here: see (1). So, now we have everything to implement function: Here it is: float calc(float X) { float y = 0; for(int j=0; j #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