http://z0mbie.host.sk/automaton_e.txt
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<N; j++)
y += pow(X,j) * C[j];
return y;
}
Or, in more nice form:
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]
Since first opcode byte is encoded within high byte of function result,
it will be defined in our program as ?:
.data
msg db 'Hello world!',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 ; initial state = -1
dec ebx
jmp begin
cycle: pushf ; copy ZF into bit 0 of 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 ; get next state
cmp bl, 18 ; exit if last state is reached
jae quit
push eax ecx ; take 1st opcode byte from
mov cl, bh ; function result, and patch code
mov bh, 0
mov eax, jtab[ebx*4]
mov [eax], cl
pop ecx eax
jmp jtab[ebx*4] ; go to action
quit: retn
jtab label dword ; table of actions
; index = action # = state #
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
Now, to understate logic of this compiled program, you should calculate
all function results for all state values, then build table of state
changes, and insert JZ/JNZ into corresponding program places.
After that, if program is NOT builded using method shown in the
1st part of this article, i.e. not based on finite automaton conception,
it will be possible to reverse it into classical C constructions, such as
if, for, while.
Now, a bit of theory.
All these code transformation can be applied to mostly all
blocks of existing code, i.e. any linear code can be converted
into finite automaton, and then state change table can be
converted into a function.
Lets assume, that variable state of automaton's state is not ZF flag,
as it show above, but AL register value.
This means, that to extract all information encoded in our
function, it is required to iterate 256 variants.
If this would be AX register, then, for example on checking
two first bytes of some file for MZ sign, current state will be
changed into one state in 65534 cases, and into another state
in 2 cases. The bigger argument size is, the more hardly
is to iterate it; and in some cases some state changes will be
lost, and part of code, which, for example, follows MZ-check
will not be extracted.
Ideally, such function is a black box, which has some value
on input, and outputs some other value, but extract all the
information is impossible.
Well, enough words has been said, and i'll go drink some beer,
while you will think about all that crap. I hope, it will help
you somewhere.
--------------------------------------------------------------------------------
Appendix (1) - program to calculate polynomial coefficients.
#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);
}
--------------------------------------------------------------------------------
