No fucking chance... to AV!

I wish to talk again on topic which I already posted in russian. Wintermute once wrote the influential article ("Polymorphism and grammars") where he expressed his unbelief in polymorphic techniques. No fucking chance, - he said, yeah. From onward many VXers repeated with a mulish obstinacy that polymorphism is dead, though the original Wintermute's conclusion is at least an exaggeration. There are many extremely simple examples of languages which cannot be recognized by FSM (for example L=aⁿbⁿ). There are other chalenges to AV engines based on regular expressions. Suppose that we have a simple grammar:

MOV x, y :=   MOV     tmp, y
              MOV     x, tmp |
              PUSH    y
              POP     x

And the following code:

MOV     EAX, 1
MOV     EBX, 2

We apply the rule and get the following:

MOV     ECX, 1
MOV     EAX, ECX
PUSH    2
POP     EBX

We could even apply it recursively (one time) and get:

PUSH    1
POP     ECX
MOV     EAX, ECX
PUSH    2
POP     EBX

Yet it still be detected after the reverse transformations will be applied in the loop until no changes could be made. But combine it with a permutation:

PUSH    2
PUSH    1
POP     ECX
POP     EBX
MOV     EAX, ECX

After single optimization the same rules cannot be applied anymore. Further optimization would require a far more complex and costly analysis. One possible solution is to build data dependency graph and slice the code into domains of dependent expressions which could be optimized separately. Data dependency could be broken by packing different variables into single one (using different bits or XORing them like in XOR-lists) or introduce Fortran's COMMON-blocks and scatter the assigments all along the CFG.

We could save the anti-virus vendors from unemployment till the end of time.