I decided to revisit the idea I described in “Recompiling Metamorphism” (Valhalla #2). Existing metamorphic viruses operate at the instruction and basic-block level, which severely limits the mutations they can perform. I believe we need to work with the program as a whole. I started with a simple language I called CBD — Crazy Bootstrapping Device — a B-like language, and given the complete absence of a specification, more of a UB-like one. It sort of worked, but problems surfaced in the most unexpected places, so the next language was a strict subset of C. The name CBD was too good to change, but the language is actually C now.
The fact that information is lost during compilation is well known. I decided to start by asking: what exactly do we need in order to recompile? Do we need types? Do we need to distinguish an array from a struct, and when can we, and when can’t we? This led to the first principle of the future language: bits don’t know their type. All structs and arrays are decayed into pointers, the signedness of numbers into the signedness of the operations that use them, and finally the access width (whether we load a byte or a word) into the load operations themselves.
The parser is written in full C: it reads source code, parses it, and produces an abstract syntax tree. The c1 compiler reads the AST and generates machine code directly. It turned out deceptively simple — just 700–800 lines of code — yet it can compile everything the language can express, including itself, so behind that simplicity lies rather complex behavior. I had to drop a few more features, such as the for statement and constructs like *out++ = x;. After that the decompiler started working too: it reads the binary and recovers the AST. The language has a single data type — the machine word — which makes decompilation tractable. The generated code is all-spill: every value lives on the stack, with rax as the result register and rcx as the second operand.
This alone is enough to experiment with mutations. The simple ones first: reorder operands of commutative operations; change evaluation order, (a + b) + c → a + (b + c); shuffle the order of functions and variables (both global and local); invert conditions, if (cond) { foo(); } else { bar(); } → if (!cond) { bar(); } else { foo(); }. It would be more natural to write something like this in Lisp, but Lisp compiles down to the same kind of spaghetti anyway; though in principle one could add a DSL. Among the non-trivial mutations: converting global variables to locals (the variable must be used in only one function that is not part of a cycle in the call graph) and vice versa.
Recompilation is also a proof of correctness for every transformation. The chain compile → decompile → recompile → run must produce the same result as the original. If a mutation breaks semantics, the round-trip test will catch it. A stronger check is the generational test: the mutating compiler compiles itself, the result compiles itself, and so on. If after several generations the binary is still functional and every generation differs from the previous one, the mutations are correct.
But the compiler doesn’t have to be dumb. Version c2 already has a register allocator and an intermediate representation, which opens up a whole range of additional possibilities: random register assignment, peephole optimizations and obfuscations, random instruction selection. Neither optimization nor instruction-level obfuscation interested me much, so the output code is still fairly naive — though it looks better and runs faster than c1’s. The main focus is on how unambiguously the program can be decompiled, and how radically its structure — not just its code — can be altered. But I've added a few optimizations and reordering of independent IR instructions within a basic block.
The practical implications of the technology are entirely obvious, fall outside the scope of this article, and therefore will not be discussed.
No comments:
Post a Comment