More Graphing

While developing the attribute prorogation/calculation and predicates, it has been helpful to have a visual representation of the finite state automata that represents the parser's state transitions. Below is the state diagram of the LR(0) automata for the traditional Dragon Book expression grammar. I'll post a graph of the minimal x86 transformation grammar that I've been working on after I refactor it a little.

Prototype: Parse Tree Generation Nearly Done

As you can see from the ordered tree at the right, the parser can now generate parse trees. You may also note that bottom-up propagation of attributes is working as well. Howerver, the only semantic operation that's currently implemented is last-occurrence assignment. This will probably be one of the first things to be fixed before the next tag.

Note that this particular parse tree has been pruned (merge-upwards/delete) of intermediary non-terminal nodes that do not have attributes because they do not convey any information about the input assembly.

You can already begin to see that terminals are being reduced into non-terminals. For example, the terminals "pushl_v0(v0=0x0c), popl_r0(r0=edx)" have been merged into the single non-terminal "put_v0_in_r0(v0=0x0c, r0=edx)." This is essential for metamorphism. In fact, it's half of what metamorphism calls for. The second half is to expand non-terminals into different (but semantically equivalent) terminals during generation.

Up Next:

1. Bottom-up attribute propagation (synthesis) with semantic operations (e.g. simple addition, subtraction, etc.)
2. Metamorphic generation (i.e. the inverse of parsing.) This will include top-down attribute propagation (inheritance.)
   

The grammar for the table is as shown parse tee is:

		Terminals			Tokens
		movl_r0_r1(r0, r1)			movl %r0, %r1
		movl_v0_r0(v0, r0)			movl $v0, %r0
		pushl_v0(v0)			pushl $v0
		int_v0(v0)			int $v0
		popl_r0(r0)			popl %r0
		addl_v0_r0(v0)			addl $v0, %r0
		incl_r0			incl %r0
		xor_r0_r1			xor %r0, %r1
		line(line_content)			unmatched

instr_list'()
: instr_list()
;


instr_list()
: instr() instr_list()
| instr()
;

instr()
: macroinstr()
| x86instr()
;

x86instr()
: line(line_content)
| movl_r0_r1(r0, r1)
| movl_v0_r0(v0, r0)
| pushl_v0(v0)
| int_v0(v0)
| popl_r0(r0)
| addl_v0_r0(v0, r0)
| incl_r0(r0)
| xor_r0_r1(r0, r1)
;

macroinstr()
: put_v0_in_r0(v0, r0)
| add_v0_to_r0(v0, r0)
;

put_v0_in_r0(v0, r0)
: movl_v0_r0(v0, r0)
| pushl_v0(v0) popl_r0(r0)
;

add_v0_to_r0()
| incl_r0(r0) add_v0_to_r0(v0 - 1, r0)
| addl_v0_r0(v0, r0)
;

The input to the parser that generated the tree was:

.section .text
.globl _start
_start:
      pushl $0x0
      pushl $0xa646c72
      pushl $0x6f77206f
      pushl $0x6c6c6548
      movl %esp, %esi
      pushl $0x0c
      popl %edx
      movl %esi, %ecx
      movl $0x1, %ebx
      movl $0x4, %eax
      int $0x80
      xor %ebx, %ebx
      addl $0x05, %ebx
      movl $0x1, %eax
      int $0x80

Prototype: SLR(1) Parser Complete

With just over a week having passed since this sub-project's inception, it is now complete. We now have a fully functional retargetable SLR(1) parser.

• Given an input grammar G and a string w ∈ L(G), our SLR(1) parser recognizes w.

So, with that, a significant portion of the prototype is complete. Some code clean-up still needs be done (mainly that SymbolReferences need to be resolved before parse table construction, not during, and most certainly not uncached.) It would also be nice to make a lot of the break and continue statements into labeled break statements. There's probably plenty of area for optimization as well. Anyway, none of this needs to be done now.

Just as an experiential note, the most difficult part of this project was probably the construction of the First and Follow sets, particularly Follow. Translating these simple mathematical ideas into actual code was, at first, quite daunting. After cross-referencing several different English and mathematical descriptions, it finally became apparent what actually needed to be coded. After that, every other component of the parser seemed exceedingly trivial to implement in comparison.

Note that the requirement from a previous post that the parser would be augmented to not have an Accept state was unnecessary and this augmentation requirement has been dropped. The original problems can be solved by constructing some sort of annotated and attributed parse tree, or equivalent.

The next sub-projects to be completed are,

1. Enabling the parser to handle attributed grammars;
2. Given Parser(G, w ∈ L(G)) = t, implement Generate(G, t) = w' where w' ≠ w;
   
3. Given D = Description(G₁) construct a grammar G₂ that parses D and can generate D', where D' ≠ D.

Prototype: SLR(1) Parser Progress

[EDIT]: It may not be obvious, from the discussion below, that the parser we're constructing is intended to be retargetable (i.e. when "compution of" is written, "computation of .. for an arbitrary grammar input" is meant.)

Well, progress on the SLR(1) parser is moving forward rather rapidly. This weekend, I've managed to implement computation of the set of all nullable non-terminals, all First sets, all Follow sets and Follow sets for strings of arbitrary grammar symbols. I also managed to implement computation of closures for LR(0) item sets and the Goto(I, X) function to computer transitions between LR(0) item sets, allowing for the computation of canonical LR(0) item sets. This basically gives us the entire foundation that we need to populate the ACTION and GOTO tables. After that, it's just a matter of writing the code for the actual parser.

Everything so far is tested against the examples grammars from "Compileers: Pricipiles, Techniques & Tools" (Purple Dragon Book), James Brunskill's "An Easy Explanation of First and Follow Sets", the Wikipedia article on LR Parsers, and Daniel Scharstein's Notes on LR(1) Parsin. I would have conducted even more testing but it's still quite cumbersome to write grammars into the prototype because, ironically, I have no grammar metasyntax (e.g. BNF) parser.

I've also been thinking. With all of this work being done already, why not just extend the SLR(1) parser to be an LALR parser. Anyway, maybe not, but it doesn't seem like a giant leap and it may eventually be worth it if we want to have more freedom in the construction of our grammars.

That's all for now. Expect more on the ACTION and GOTO tables soon.

Prototype: A Change of Languages and a SLR(1) Parser

Well, vacation time in Sweden is over and it's back to work (paid and hobby) for me.

A Change of Languages

So, first of all, the reason I haven't blogged much lately is that I committed myself to rewriting the prototype in Java (from Ruby).
There's really not much to say about that other than to explain why. Mainly, I will be able to structure the program more similarly to what I will have to do in C or assembly. Java also provides an environment more similar to C but still allows the use of the higher level features (useful for prototyping). Ruby is simply too high-level to do any realistic work. Another important point is that more people can read Java than Ruby and one of the central goals of this project is to educate. Anyhow, expect to see the code in SVN fairly soon.
The old Ruby code will be "deleted" but available in the SVN history.

SLR(1) Parser

Instead of using the simplified shift/reduce parser I had been working on, I've decided to move to an SLR(1) (a simple LR parser with 1 lookahead).

Justification

The main reasons for moving away from the simplified shift/reduce parser are:

1. SLR(1) parsers have a formal basis
2. SLR(1) parsers are well-studied and well-understood
3. SLR(1) parsers can handle LR(k) grammars where k > 0
4. SLR(1) parsers are easily retargetable which is essential for our purpose
   

Project Breakdown

Since one of our goals is to be able to retarget our parser, we in fact need an SLR(1) parser generator. This will be what I will be focusing on for now. The following is a breakdown of the tasks required by our parser generator.

1. Construct the set of item sets for all production rules
2. Construct the set of nullable non-terminals
3. Construct the set of First(X) mappings
4. Construct the set of Follow(X) mappings
5. Construct the Goto table which facilitiates the Goto(I, X) function
6. Construct the Action table which facilitates the Action(I, a) function
   

It should also be noted that in the case of parsing x86 assembly, the disassembler is the lexical analyzer.

Augmentations

Our SLR(1) parsers will differ in two ways from that of a true SLR(1) parser.

The first is that the SLR(1) parser will support synthesized attributes because we are using attribute grammars for all of our mutation (be it mutation of a grammar or mutation of x86 assembly instructions).

The second is that it will not require reduction to the start symbol. That means that we will redefine the ACCEPT action in the Action table.

This is done because we really only need to parse terminals into higher-level non-terminals, not necessarily the start symbol. The second reason for making this augmentation is that, if we did reduce to the start symbol, the start symbol would have to carry a great deal of semantic information (attributes). It would even require modifications to the grammar (such as the examples given in previous posts) to even function properly. This is all unnecessary work, only slightly affects our formalisms and gives us a bit more freedom when writing grammars. If it turns out that this affects our formalisms more than I thought the grammars and parser can easily be updated anyway.

References

If you'd like to follow along, I'm basing the work I'm doing now on the Compileers: Pricipiles, Techniques & Tools (second edition) by Aho, Lam, Sethi and Ullman (The Purple Dragon Book).


For a brief overview or cheatsheet, check out Notes on LR(1) Parsing written by Daniel Scharstein for his "Compiler Design" course at Middlebury College.

Prototype: First Demonstration of the Metamorphic Engine

Well, it seems that I now have a rather good framework for implementing metamorphism with an attribute grammar. As you can see from the video, a grammar with just a few terminals and only 2 non-terminals (each of which have only two constituents) produces fairly good variation.

It may seem like development is going a little slower than it has recently but that's just because I've been trying to mathematically formalize some of the ideas. A post of that should be coming in the near future.

I've also been spending a little bit of time coming up with instruction subsets that satisfy the constraints of the Tzeitzen system. More on that shortly too.

The only thing to do before really moving on to Requirements 2, 3 and 4 is to add some more production rules and semantic rules. So, the next thing you'll see in SVN (besides more rules) is a) production rule extraction; and b) a way of representing production rules so that they can be mutated.

Prototype: Trivial metamorphism works

News from prototype-land: Trivial metamorphism works. That means Requirement 1 has been fulfilled.

In this case, the grammar contains only a single non-terminal, namely:

put_v_in_r(v1,r1)
: pushl_v(v1) popl_r(r1)
| movl_v_r(v1,r1)
;

Plenty more to do. For one thing I'm not sure that up-propagation of attributes from terminals is done correctly. Specifically, I think I have to do α-conversion during up-propagation because there will be rules like the following:

ntop1_v(v1,v2)
: top1_v(v1) top2_v(v1)
;

After I'm convinced that works properly, I'm going to come up with and embed one of the undecidable grammars from Filiol's paper. And then it's on to convince this ruby script to mutate it's own grammar :) (i.e. The Hard Part).

Anyway, here's a screenshot of some trivial mutations:

Prototype Work

So, I began the prototype a few days ago. After a few false starts, I've come up with a shift/reduce parser that uses an attribute grammar. x86 instructions are parsed out of their AT&T syntax format into terminal symbols. Using the shift/reduce algorithm, the terminal symbols are reduce to non-terminal symbols. Furthermore, using the attribute grammar paradigm allows passing of information (in the form of attributes) from terminals, upward, to non-terminals. This is also what allows agreement to be satisfied at parse-time between all terms of a non-terminal's constituent.

In short, my implementation of shift/reduce parsing isn't the most efficient but it works well enough for this prototype. I have not yet implemented generation, but as soon as that done. It will be a fully functional metamorphic engine based on an attribute grammar, as I set out to do.

I haven't put a whole lot of thought into mutating the attribute grammar using only itself, but I think all signs so far point to this not being too difficult.

As a side note, I decided on Ruby as the language of choice. The code publically is availible for review in the Bukowski SVN under the prototype directory.

So, for proof of life, I'll leave you with the following input for and output of the prototype.

Input assembly:

.section .text
.globl _start
_start:
   pushl   $0x0
   pushl   $0xa646c72
   pushl   $0x6f77206f
   pushl   $0x6c6c6548
   movl    %esp, %esi
   pushl   $0x0c
   popl    %edx
   movl    %esi, %ecx
   movl    $0x1, %ebx
   movl    $0x4, %eax
   int     $0x80
   movl    $0x2, %ebx
   movl    $0x1, %eax
   int     $0x80

Output parse stack:

# 0[ Token:0x7f30510f11e8 @type=0, @content=".section .text" ]
# 1[ Token:0x7f30510ebef0 @type=0, @content=".globl _start" ]
# 2[ Token:0x7f30510e72d8 @type=0, @content="_start:" ]
# 3[ Token:0x7f30510cd568 @id="pushl_v", @attributes={nil: nil, "v1": "0x0"}, @type=1 ]
# 4[ Token:0x7f30510ca750 @id="pushl_v", @attributes={nil: nil, "v1": "0xa646c72"}, @type=1 ]
# 5[ Token:0x7f30510b9ae0 @id="pushl_v", @attributes={nil: nil, "v1": "0x6f77206f"}, @type=1 ]
# 6[ Token:0x7f30510a86c8 @id="pushl_v", @attributes={nil: nil, "v1": "0x6c6c6548"}, @type=1 ]
# 7[ Token:0x7f30510a0b58 @id="movl_r_r", @attributes={"r2": "esi", nil: nil, "r1": "esp"}, @type=1 ]
# 8[ Token:0x7f30510761f0 @id="put_v_in_r", @attributes={nil: nil, "v1": "0x0c", "r1": "edx"}, @type=2 ]
# 9[ Token:0x7f30510719e8 @id="movl_r_r", @attributes={"r2": "ecx", nil: nil, "r1": "esi"}, @type=1 ]
#10[ Token:0x7f3051069040 @id="put_v_in_r", @attributes={"r2": "ebx", nil: nil, "v1": "0x1"}, @type=2 ]
#11[ Token:0x7f30510655d0 @id="put_v_in_r", @attributes={"r2": "eax", nil: nil, "v1": "0x4"}, @type=2 ]
#12[ Token:0x7f3051058f38 @id="int_v", @attributes={nil: nil, "v1": "0x80"}, @type=1 ]
#13[ Token:0x7f305104bc20 @id="put_v_in_r", @attributes={"r2": "ebx", nil: nil, "v1": "0x2"}, @type=2 ]
#14[ Token:0x7f30510432c8 @id="put_v_in_r", @attributes={"r2": "eax", nil: nil, "v1": "0x1"}, @type=2 ]
#15[ Token:0x7f30510367d0 @id="int_v", @attributes={nil: nil, "v1": "0x80"}, @type=1 ]

Description:
The main thing to notice here is on fames #8, 10, 11, 13 and 14. At frame #8, the assembly went from [ "pushl $0x0c", "popl %edx" ] to [ pushl_v(0xc), popl_r(eax) ] to [ put_v_in_r(0xc,eax) ]. At frame #10 (and similarly on 11, 13, 14) the assembly went from ["movl $0x01, %ebx" ] to [ movl_v_r(0x01,ebx) ] to [ put_v_in_r(0x01,ebx) ]. This allows for the bidirectional translation of ("pushl $v; popl %r", "movl $v, %r").

The Path to a Fully Functional Grammar-Based Meta-Metamorphic Engine

Now that NOP-cavity infection is fully functional it's time to move on to bigger, better and newer things.

Instead of starting directly in on implementing the entire meta-metamorphic engine in C, I'm going to do a quick prototype it in a higher level language (probably python). After the prototype is complete I will begin simultaneously implementing the real version and writing a formal paper on the topic.

Prototype Requirements and Artificial Limitations

• Artificial Limitation 1: The grammar will be written in the language of choice directly (instead of an external document)
• Artificial Limitation 2: The grammar words will be written in plain text AT&T syntax instead of opcode (e.g. "push %eax" instead of "\x50".
• Artificial Limitation 3: The plain text AT&T syntax will be parsed via regular expressions instead of a proper AT&T syntax lexer and parser.
• Artificial Limitation 4: The grammar words (x86 instructions) considered will be relatively small; and, respectively, the grammar itself will be relatively small.
  
• Requirement 1: The prototype engine must use an attribute grammar to mutate an ordered set of x86 instructions written in plain-text AT&T syntax, output the mutation in AT&T plain-text syntax, the output must be semantically equivalent.
• Requirement 2: The prototype engine must be able to mutate the attribute grammar using only the grammar itself.
• Requirement 3: The prototype engine must be able to use resultant grammars of Requirement 2 to further fulfil all requirements listed herein to produce more mutations (further generations, respective to iterations per run)
• Requirement 4: The engine must be able to produce a sufficient (to be defined later) number of unique output mutations and unique output grammars.

Note that any limitations may be waived if they hinder progress.

NOP-Cavity Infection Fully Functional (Bukowski 0.0.9 Released)

The title says it all. NOP-cavity infection is now fully functional. The cavity infecter is able to inject any piece of position-independent code into any executable that has enough space in it's NOP-cavities. See the screenshot below:


As you can see, there's one unnecessary jump inserted into the last cavity. That'll be fixed in the next release.

Bukowski 0.0.9

• libx86: x86_note_t: a new way of affixing notes (metadata) to instructions
• libx86: x86_instr_list_t: new functionality for lookup based on notes; new functionality to calculate the distance between two instructions
• libx86: x86_branch_analyzer_t: new functionality to update the actual branch displacements that will be emitted
• libcavity: uses branch analyser to link individual NOP-cavity injections. Fully functional.

View Bukowski 0.0.9 SVN Repository

NOP-Cavity Infection Almost Complete: Next?

I thought that I'd lay out what I need to do, in order, for readers.

In the next few days, I'll be updating the assembler to prefer branch annotations over static data. I will be writing a new test case that re-assembles a disassembly of arch(1) that has been annotated by the branch analyser. Although the previously posted graph was pretty, this test case will further help contribute to proving that the branch analyser works properly. Mundanely, the expected output is the exact input :)

After this boring bureaucratic work is done, I'll be completing the NOP injection code (libcavity). It's currently possible to inject code into an executable's NOP areas but it is not possible to actually execute that code because it is not linked by jumps. The branch analyser and respective update to the assembler solves exactly this problem. The only task left is to actually use that new code in libcavity. Practically that will mean just running a branch analysis on the injectable payload.

So, then NOP-Cavity infection will be complete. Next?

Now that we're done with our apetizers (short term goals I and II), we can move on to our main course: instruction-level metamorphism.

Much of the code we've written so far has been necessary for the metamorphic engine to work. The first use of this code will be to add two new types of rules to the mutation grammar:

1. M -> N where ninstrs(M) != ninstrs(N)
2. M -> N where nbytes(M) != nbytes(N)
3. and of course M -> N where ninstrs(M) != ninstrs(N) and nbytes(M) != nbytes(N)

This basic ground work allows us to move on to more interesting things. First, let's state the goal:

• Write a metamorphic engine based on a formal grammar that can mutate x86 code using the rules of the grammar; and mutate the grammar itself using the rules of the grammar. The grammar should conform to the constraints outlined in "Metamorphism, Formal Grammars and Undecidable Code Mutation" (Filiol, 2008)
  

What we have, after the some more examples of the aforementioned three types of rules are added to the grammar, is a formal grammar that can mutate x86 code. The grammar cannot yet be used to mutate itself; nor does it conform to the constraints mention in Filiol's paper.

It is not currently possible to implement rules that would make the grammar conform to Filiol's constraints (to ensure undecidability) because the grammar engine does not support non-terminal symbols.

So it seems we have two tasks to do before actually getting to Filiol's constraints:

1. Enable the grammar to manipulate non-terminal symbols
2. Enable the engine to mutate the grammar using the grammar itself

I'm not going to describe the details of what needs to be done in this post, because I haven't even described, in this blog, how the grammar works. For now I'll just say that, because we're using an attribute grammar, we will be required to do α-conversion on the attributes to preserve semantic information.

Branch Annotation

So, as you may be able to see from the image on the left, branch annotation seems to work fairly well. The directed graph on the left represents the static-branch and forward control flow information for the instructions extracted from arch(1)'s ".text" section. Records with a red border are branch instructions. All branch destinations are represented by records with a bold black border. Potential control transfer from a branch instruction to its potential destination are represented by a red directed edge. Notice that both forward and backward branches are present in this graph.

A couple of limitations of the library can be noticed in this graph. The first can be seen by looking for branch instructions (records with a red border) that do not have a directed edge extending from them. The reason for this is that the branch destination is outside of the section of instructions that was analysed. The destinations of these branches reside before or after the section that was analysed. In the future this will be remedied by assigning one of a few reserved branch IDs to the branch instruction and storing it's offset (outward) from the beginning or end of the analysed section. That will be necessary if the sizes of instructions within a section will be modified.

Another limitation can be seen from the graph is that branch instructions (labelled only with their mnemonic, such as "JMP" or "CALL") are not highlighted in red, nor do they have a directed edge originating from them. This is because these particular branch instructions do not use relative offsets but their destination is determined by static-addressing and/or register contents. I have no plans to fix this any time soon as it would require far more static analysis than actually necessary to accomplish the goals laid out so far.

Something that cannot be seen from this graph is the libraries ability to handle branches whos' destination is the middle of some instruction. This information isn't currently used in any way, but it will be used in the future to ensure that mutations aren't done on these branch destinations and that the branches themselves get updated correctly.

Although the graph looks rather good, I have no way of proving with any certainty that it is correct. The next step to verify this code is working correctly is to write a test case that re-assembles the code using the branch annotations instead of the original relative offsets encoded in the branch instructions. This means updating the assembler to prefer branch annotations over encoded information. After that, we should know with a great deal more certainty whether this code is correct or not and can move on to more interesting things.

I've quoted the original disassembly of arch(1)'s ".text" section for those who are curious.

P.S. The graph was generated from dumping an instruction list to XML and using XSLT to translate the graph into GraphViz ".dot" format and converting that into a PNG.

arch.textonly:     file format elf32-i386


Disassembly of section .text:

08048330 <.text>:
 8048330: 31 ed                 xor    %ebp,%ebp
 8048332: 5e                    pop    %esi
 8048333: 89 e1                 mov    %esp,%ecx
 8048335: 83 e4 f0              and    $0xfffffff0,%esp
 8048338: 50                    push   %eax
 8048339: 54                    push   %esp
 804833a: 52                    push   %edx
 804833b: 68 b0 84 04 08        push   $0x80484b0
 8048340: 68 50 84 04 08        push   $0x8048450
 8048345: 51                    push   %ecx
 8048346: 56                    push   %esi
 8048347: 68 00 84 04 08        push   $0x8048400
 804834c: e8 c7 ff ff ff        call   0x8048318
 8048351: f4                    hlt    
 8048352: 90                    nop    
 8048353: 90                    nop    
 8048354: 55                    push   %ebp
 8048355: 89 e5                 mov    %esp,%ebp
 8048357: 53                    push   %ebx
 8048358: e8 00 00 00 00        call   0x804835d
 804835d: 5b                    pop    %ebx
 804835e: 81 c3 f3 12 00 00     add    $0x12f3,%ebx
 8048364: 50                    push   %eax
 8048365: 8b 83 fc ff ff ff     mov    -0x4(%ebx),%eax
 804836b: 85 c0                 test   %eax,%eax
 804836d: 74 02                 je     0x8048371
 804836f: ff d0                 call   *%eax
 8048371: 8b 5d fc              mov    -0x4(%ebp),%ebx
 8048374: c9                    leave  
 8048375: c3                    ret    
 8048376: 90                    nop    
 8048377: 90                    nop    
 8048378: 90                    nop    
 8048379: 90                    nop    
 804837a: 90                    nop    
 804837b: 90                    nop    
 804837c: 90                    nop    
 804837d: 90                    nop    
 804837e: 90                    nop    
 804837f: 90                    nop    
 8048380: 55                    push   %ebp
 8048381: 89 e5                 mov    %esp,%ebp
 8048383: 83 ec 08              sub    $0x8,%esp
 8048386: 80 3d 78 96 04 08 00  cmpb   $0x0,0x8049678
 804838d: 75 2d                 jne    0x80483bc
 804838f: a1 74 96 04 08        mov    0x8049674,%eax
 8048394: 8b 10                 mov    (%eax),%edx
 8048396: 85 d2                 test   %edx,%edx
 8048398: 74 1b                 je     0x80483b5
 804839a: 8d b6 00 00 00 00     lea    0x0(%esi),%esi
 80483a0: 83 c0 04              add    $0x4,%eax
 80483a3: a3 74 96 04 08        mov    %eax,0x8049674
 80483a8: ff d2                 call   *%edx
 80483aa: a1 74 96 04 08        mov    0x8049674,%eax
 80483af: 8b 10                 mov    (%eax),%edx
 80483b1: 85 d2                 test   %edx,%edx
 80483b3: 75 eb                 jne    0x80483a0
 80483b5: c6 05 78 96 04 08 01  movb   $0x1,0x8049678
 80483bc: c9                    leave  
 80483bd: c3                    ret    
 80483be: 89 f6                 mov    %esi,%esi
 80483c0: 55                    push   %ebp
 80483c1: 89 e5                 mov    %esp,%ebp
 80483c3: 83 ec 08              sub    $0x8,%esp
 80483c6: a1 80 95 04 08        mov    0x8049580,%eax
 80483cb: 85 c0                 test   %eax,%eax
 80483cd: 74 21                 je     0x80483f0
 80483cf: b8 00 00 00 00        mov    $0x0,%eax
 80483d4: 85 c0                 test   %eax,%eax
 80483d6: 74 18                 je     0x80483f0
 80483d8: 83 ec 0c              sub    $0xc,%esp
 80483db: 68 80 95 04 08        push   $0x8049580
 80483e0: e8 1b 7c fb f7        call   0x0
 80483e5: 83 c4 10              add    $0x10,%esp
 80483e8: 90                    nop    
 80483e9: 8d b4 26 00 00 00 00  lea    0x0(%esi,%eiz,1),%esi
 80483f0: 89 ec                 mov    %ebp,%esp
 80483f2: 5d                    pop    %ebp
 80483f3: c3                    ret    
 80483f4: 90                    nop    
 80483f5: 90                    nop    
 80483f6: 90                    nop    
 80483f7: 90                    nop    
 80483f8: 90                    nop    
 80483f9: 90                    nop    
 80483fa: 90                    nop    
 80483fb: 90                    nop    
 80483fc: 90                    nop    
 80483fd: 90                    nop    
 80483fe: 90                    nop    
 80483ff: 90                    nop    
 8048400: 55                    push   %ebp
 8048401: 89 e5                 mov    %esp,%ebp
 8048403: 81 ec a8 01 00 00     sub    $0x1a8,%esp
 8048409: 83 e4 f0              and    $0xfffffff0,%esp
 804840c: 8d 85 68 fe ff ff     lea    -0x198(%ebp),%eax
 8048412: 89 04 24              mov    %eax,(%esp)
 8048415: e8 ee fe ff ff        call   0x8048308
 804841a: 85 c0                 test   %eax,%eax
 804841c: 74 15                 je     0x8048433
 804841e: c7 04 24 64 85 04 08  movl   $0x8048564,(%esp)
 8048425: e8 be fe ff ff        call   0x80482e8
 804842a: b8 01 00 00 00        mov    $0x1,%eax
 804842f: 89 ec                 mov    %ebp,%esp
 8048431: 5d                    pop    %ebp
 8048432: c3                    ret    
 8048433: 8d 85 6c ff ff ff     lea    -0x94(%ebp),%eax
 8048439: 89 04 24              mov    %eax,(%esp)
 804843c: e8 b7 fe ff ff        call   0x80482f8
 8048441: 31 c0                 xor    %eax,%eax
 8048443: eb ea                 jmp    0x804842f
 8048445: 90                    nop    
 8048446: 90                    nop    
 8048447: 90                    nop    
 8048448: 90                    nop    
 8048449: 90                    nop    
 804844a: 90                    nop    
 804844b: 90                    nop    
 804844c: 90                    nop    
 804844d: 90                    nop    
 804844e: 90                    nop    
 804844f: 90                    nop    
 8048450: 55                    push   %ebp
 8048451: 89 e5                 mov    %esp,%ebp
 8048453: 57                    push   %edi
 8048454: 56                    push   %esi
 8048455: 31 f6                 xor    %esi,%esi
 8048457: 53                    push   %ebx
 8048458: 83 ec 0c              sub    $0xc,%esp
 804845b: e8 a0 00 00 00        call   0x8048500
 8048460: 81 c3 f0 11 00 00     add    $0x11f0,%ebx
 8048466: e8 55 fe ff ff        call   0x80482c0
 804846b: 8d 93 20 ff ff ff     lea    -0xe0(%ebx),%edx
 8048471: 8d 8b 20 ff ff ff     lea    -0xe0(%ebx),%ecx
 8048477: 29 ca                 sub    %ecx,%edx
 8048479: c1 fa 02              sar    $0x2,%edx
 804847c: 39 d6                 cmp    %edx,%esi
 804847e: 73 1c                 jae    0x804849c
 8048480: 89 d7                 mov    %edx,%edi
 8048482: 8d b4 26 00 00 00 00  lea    0x0(%esi,%eiz,1),%esi
 8048489: 8d bc 27 00 00 00 00  lea    0x0(%edi,%eiz,1),%edi
 8048490: ff 94 b3 20 ff ff ff  call   *-0xe0(%ebx,%esi,4)
 8048497: 46                    inc    %esi
 8048498: 39 fe                 cmp    %edi,%esi
 804849a: 72 f4                 jb     0x8048490
 804849c: 83 c4 0c              add    $0xc,%esp
 804849f: 5b                    pop    %ebx
 80484a0: 5e                    pop    %esi
 80484a1: 5f                    pop    %edi
 80484a2: 5d                    pop    %ebp
 80484a3: c3                    ret    
 80484a4: 8d b6 00 00 00 00     lea    0x0(%esi),%esi
 80484aa: 8d bf 00 00 00 00     lea    0x0(%edi),%edi
 80484b0: 55                    push   %ebp
 80484b1: 89 e5                 mov    %esp,%ebp
 80484b3: 83 ec 08              sub    $0x8,%esp
 80484b6: 89 1c 24              mov    %ebx,(%esp)
 80484b9: e8 42 00 00 00        call   0x8048500
 80484be: 81 c3 92 11 00 00     add    $0x1192,%ebx
 80484c4: 89 74 24 04           mov    %esi,0x4(%esp)
 80484c8: 8d 8b 20 ff ff ff     lea    -0xe0(%ebx),%ecx
 80484ce: 8d 83 20 ff ff ff     lea    -0xe0(%ebx),%eax
 80484d4: 29 c1                 sub    %eax,%ecx
 80484d6: c1 f9 02              sar    $0x2,%ecx
 80484d9: 85 c9                 test   %ecx,%ecx
 80484db: 8d 71 ff              lea    -0x1(%ecx),%esi
 80484de: 75 10                 jne    0x80484f0
 80484e0: e8 5b 00 00 00        call   0x8048540
 80484e5: 8b 1c 24              mov    (%esp),%ebx
 80484e8: 8b 74 24 04           mov    0x4(%esp),%esi
 80484ec: 89 ec                 mov    %ebp,%esp
 80484ee: 5d                    pop    %ebp
 80484ef: c3                    ret    
 80484f0: ff 94 b3 20 ff ff ff  call   *-0xe0(%ebx,%esi,4)
 80484f7: 89 f2                 mov    %esi,%edx
 80484f9: 4e                    dec    %esi
 80484fa: 85 d2                 test   %edx,%edx
 80484fc: 75 f2                 jne    0x80484f0
 80484fe: eb e0                 jmp    0x80484e0
 8048500: 8b 1c 24              mov    (%esp),%ebx
 8048503: c3                    ret    
 8048504: 90                    nop    
 8048505: 90                    nop    
 8048506: 90                    nop    
 8048507: 90                    nop    
 8048508: 90                    nop    
 8048509: 90                    nop    
 804850a: 90                    nop    
 804850b: 90                    nop    
 804850c: 90                    nop    
 804850d: 90                    nop    
 804850e: 90                    nop    
 804850f: 90                    nop    
 8048510: 55                    push   %ebp
 8048511: 89 e5                 mov    %esp,%ebp
 8048513: 53                    push   %ebx
 8048514: 52                    push   %edx
 8048515: a1 70 95 04 08        mov    0x8049570,%eax
 804851a: 83 f8 ff              cmp    $0xffffffff,%eax
 804851d: bb 70 95 04 08        mov    $0x8049570,%ebx
 8048522: 74 18                 je     0x804853c
 8048524: 8d b6 00 00 00 00     lea    0x0(%esi),%esi
 804852a: 8d bf 00 00 00 00     lea    0x0(%edi),%edi
 8048530: 83 eb 04              sub    $0x4,%ebx
 8048533: ff d0                 call   *%eax
 8048535: 8b 03                 mov    (%ebx),%eax
 8048537: 83 f8 ff              cmp    $0xffffffff,%eax
 804853a: 75 f4                 jne    0x8048530
 804853c: 58                    pop    %eax
 804853d: 5b                    pop    %ebx
 804853e: 5d                    pop    %ebp
 804853f: c3                    ret    

Bukowski Project 0.0.8 Released

I'm very proud to announce the first version of the Bukowski Project that does something useful!

• libx86: x86_instr_list_t is now much more featureful, multi-purpose and const-correct
  
• libcavity: it's now possible to do basic NOP-area infection
  

View Bukowski 0.0.8 SVN Repository

NOP-Cavity Infection Works

Like I said in the last post, it turned out to be fairly trivial to complete basic NOP-cavity infection. I''ve posted a screenshot here of what that looks like:



You might already be able to tell that the code injected was the following:

xor %eax, %eax
add $0x1, %eax
sub $0x1, %eax
addl $0x01, %eax
int3

So, why NOP infection anyway?

Because it's so awesome. No, really, I'm actually using this as a test case for the rest of the framework. If this framework isn't capable of doing NOP-infection, there's no way it's going to be able to do metamorphism.

Besides, NOP-infection is a useful way to hide code inside an executable without changing the executable size. Yes, there's known heuristics for detecting this hidden code, but it may turn out to be useful anyhow.

Anyway, I'll be tagging the code in a moment. You can try it out for yourself.


Next?

Well, if you looked carefully at the screenshot, you'll notice that it's not possible for our injected code to be executed properly because it does not include jump instructions. The next thing to do is to mark-up instruction lists possibly in the way description the "Growing and Shrinking Instructions" series. After doing that it should be fairly easy to link the portions of code togehter so that they can execute.

x86_instr_list_t

A bit of work was done to today drop the inflexible x86_disassembly_t structure (a dynamically reisizing array) and replace it with a new x86_instr_list_t (a doubly-linked list of instructions). The point of this was to be able to delete, insert and, therefore, replace any number N of instructions at any offset A in an instruction list with any number M of instructions at any offset B from a second instruction list.

Extensive test cases have been written to verify that as many silly combinations that I could think of work properly. The code for x86_instr_list_t is still a bit messy and unoptimized but that will be attended to the next time I do refactoring. All of libx86's previous test cases still work. And the previous output from the generator is still correct.

libcavity should now be fairly simple to finish. It will also be fairly simple to update libmutate to replace some N instructions with some M instructions where N!=M now. I haven't actually updated the libraries to do this yet, but it should be there in the next few days.

So what's after that? Well, as one may have picked up, there's two things that can change the size of a chunk of x86 opcode. The first is that the number of instructions in a collection of instructions can change due to mutation or cavity infection. The second is that the size of any instruction can become smaller or larger. Because of this the operands of "jump" instructions will have to be updated. Thus it will be time to implement something such as that descript in the "Growing and Shrinking Instructions" series. I have come up with an algorithm which will only necessitate one iteration of "jump" instruction operand updates per generation of mutations (i.e. it will not be necessary to update them after each mutation or each cavity injection.)

Video of Old Presentations

Recently an acquaintance of mine asked me about my old presentations. I haven't put up the slides yet but I did happen to find the videos. I'll see what I can do about the slides later.

RECON 2008 - Anthony de Almeida Lopes - Bypassing Security Protections by Backdooring libc

RECON 2006 - Anthony de Almeida Lopes and Jack Louis - Multi-cavity NOP-infection OS-Independent x86 Virus.

Bukowski 0.0.7 Released: Disassembly to XML

Ali wanted the disassembler to output XML descriptions of instructions, so I just added that. I'm not sure if it's the best way represent that data, but it should suffice for now. As requirements for other projects that use this output are further defined, it will be updated accordingly.

Anyway, having this will allow us to write some fairly accurate regression tests for the disassembler itself as well as other components. It's probably also going to be pretty useful for debugging.

I've uploaded (6.4MB) an example disassembly of ls(1)'s ".text" section.

View Bukowski 0.0.7 SVN Repository

IRC and CIA

I just started an IRC channel on EFNet: #bukowski. I really wanted to see what using the cia.vc commit bot is like. Seems to work quite well. I'm not sure if the channel will be permanant or not, but if we get enough interest, maybe it will be.

Re: Growing and Shrinking Instructions

This is mostly a note to myself, but I wanted to point out that when marking a control-flow instructions as referring to a destination node we cannot just set the destination index to be the position of the destination instruction within the disassembly. This is because the distance positions of instructions within a disassembly will likely change. This is certainly true for metamorphism as well as NOP-infection.

The solution is to mark each destination instruction with a different set of indexes. That is to say that our metadata for a control-flow instruction should express something along the lines of "this is a jump instruction and jumps to destination index M" not "this is a jump instruction and jumps to instruction N." The metadata of an instruction that is the destination of a jump should express something along the lines of "this instruction is jumped to and has a destination index of M."

The algorithm can basically be broken into two parts:

1. Iterate through all instructions. When a jump instruction is found, mark it's destination instruction as being a destination instruction with an destination index of n. Increment n so that the next one we mark as a destination instruction has a different destination index. If we encounter a destination instruction that is already marked, do nothing.
2. Iterate through all instructions. When a jump instruction is found, mark it as referring to the destination index of the destination instruction.

This requires two iterations through all instructions but I believe its simplicity is worth its inefficiency.

There is one issue left to be considered. That is, what happens when we encounter a control flow instruction that references an instruction outside of our disassembly. For exmaple, we may have disassembled a .text section but an instruction we encounter may reference an instruction in the .plt section of the same executable.

First and second short term goals closer than ever

As you can see from recent blog posts and SVN commmits, the first and second points in my "Short term plans" are quite near completion; however, there's a bit more supporting code that needs to be written.

To recap, the first goal (I) is to translate every instance of one instruction in ls(1); and the second goal (II) is to resurrect the NOP-cavity infecter with the new libraries. I'd like to break down, more specially. the code that needs to be written to accomplish these two goals.

I. Translate every instance of one instruction in ls(1)

Recent work allows us to translate every instances of an instruction in an arbitrary .text section of an ELF file. We are able to extract a .text section, disassemble it, mutate all instances of an instruction (i.e. addb $val, %reg) and reassemble the .text section. We are not yet able to reconstruct the ELF file so that it is executable. There are two main areas of work the need to be done to accomplish this, both of which related to changes in size of the .text section.

The first thing that needs to be done is re-adjusting the displacements of control flow instructions (i.e. jumps, calls, loops, etc.) This is because the instruction that we rewrite in a different form may be a different size.

The second thing to do is necessary for the same reason. We need to recalculate the size and offsets of program headers, section headers and many other pieces of the ELF so that it still works.

The last thing to do, which is similar to something the needs to do for goal II, is that our disassembly object (x86_disassembly_t) needs to facilitate the replacing of some number of instructions with a different number of instructions. This isn't an issue for the one instruction that I've chosen to mutate but it should not be forgotten as we move forward.

II. Resurrect the NOP-cavity infecter with the new libraries

The algorithm for the NOP-cavity infecter has not changed much since its original version; however, there are some considerations need to be made when rewriting it using the new libraries. Although the algorithm does need to be updated to fit the new API's, it is mainly the underlying libraries that we need to update to make this work correctly.

The first and easiest thing to fix is that we need to be able to calculate the size of a disassembled or constructed instruction before it is actually assembled. This is so that we can determine whether our group of instruction fit into the area currently consumed by a certain number of NOPs.

The second thing that needs to be done is that our disassembly object (x86_disassembly_t) needs to facilitate the replacing of a series of instructions with a single instruction. Unlike the last requirement for goal I, this is actually required for the cavity infecter to function at all.

Issues Common to I and II

To get any of the above to work correctly, it will be necessary to control-flow annotation post-disassembly and pre-reassembly routines. I described this briefly in the post entitled "Growing and Shrinking Instructions"

Growing and Shrinking Instructions

So, I've been thinking (... "thinking" ...) about how some instruction mutations are going to change the size of code blocks (Some getting smaller, others getting larger). This means that, at some point, the mutator is going to need to update control-flow instructions offsets. After a bit of thinking, I figured that the best way to do it is probably the following. Upon initial disassembly of some code to be mutated, we mark all "jump" destinations by index. For example, the first jump destination is marked as 0, the second ad 1 and so on. Then we go and edit all jump instructions so that their displacement is the corresponding index instead of an actual offset. When instructions are mutated, their destination marker would be updated. Then, right before reassembly, we can resolve all of the faked-displacements to correspond to the correct destination. This allows for any number of mutations to occur between post-disassembly and reassembly.

Simple idea, I know, but just wanted to get that off my chest so I can stop over-thinking it :)

Test cases and coverage

So, I committed myself to making sure that I could translate all instances of at least one instruction in GNU's ls(1) program. Thinking it through a bit, I realized that whatever program I choose as my test target, it will need to have a large amount of test cases. It turns out that ls(1) does have a good amount of test cases. As you can see here
http://git.savannah.gnu.org/cgit/coreutils.git/tree/tests/ls?id=v6.12.
I haven't profile the test cases, but I doubt that by combining them I'll get 100% coverage.
So, now I'm wondering, does anyone know of any open-source C program that comes with test cases that will add up to 100% coverage? I know that wget(1) has a significant amount of test cases, but I'll have to do some actual profiling with these.

0.0.6 Screenshot

I thought it might be useful to add a screenshot of what I've accomplished so far. It's just one operation but it's a start!




Notice that this is not a simple swap. The first highlighted instruction adds 1 to EAX but the second instruction adds 2 to eax (in both cases). The result, by the itme you reach the INT3 instruciton, in both cases, is the number 4 in eax. The following screenshot proves that.

Bukowski Project 0.0.6 Released

I've just tagged 0.0.6 of the Bukowski.

The major change here is that it's now possible to do basic instruction substitution. The example in grammar.xml is not fully functional because I've only added a "negate" operation so far. However, there's plenty of rules that can be written for x86-32 using basic instruction substitution.

As soon as more operations (including constraints) are added, significantly more will be possible. On the other hand, there's plenty of more work to do. For one thing, a lot of this needs some serious refactoring. I'm considering this version of the engine to be a rather rough prototype. Also, rule composition isn't possible yet either (for making rules out of non-terminals).

So, althogh this is very "prototypy", we're well on our way to having a fully-functional grammar-based instruction mutation engine.

View Bukowski 0.0.6 SVN Repository

Short term plans

You may have seen the trickle of SVN commits that started up recently and I figured that I should state what, exactly, it is that I'm working on right now.

Now that the disassembler is complete, I have begun to work on the mutation engine based on the "pattern system" that I've spoken about. I have several stages of goals for this library, the first stage is this:

1. Disassemble an x86-32 version of /bin/ls
2. Translate all occurrences of at least one instruction
3. Reassemble it
4. Verify that the mutated /bin/ls is still functioning as originally intended

The second thing that I'll be doing is resurrecting my old NOP-chaining virus so that it uses the new x86 library.

The third thing to do before getting really complex is to resurrect the old execve-backdooring trojan using the new library. This probably includes making the ELF library ptrace-capable.

After that, the next thing to do is to make the x86 disassembler useful from within virus context (i.e. it should be grafted onto the actual virus and usable by it.) This allows each generation to be able to mutate itself into the next generation. This will mean doing some work on the ELF library. This also means creating binary representations of the disassembler. What that means exactly, I have not decided. The two obvious routes are to a) just serialize the x86_instr_t instructions and carry them with the virus generations; or b) create a traditional disassembler from the x86_instr_t:s. Option a has one big downside: it's easily detectable by data pattern recognition and option b's biggest downside is that it should be very easy to detect it by behaviour-based pattern recognition. Now, I'll be getting far ahead of myself here, but I do have a potential resolution to option a: It should be possible to apply metamorphism to the instruction data itself. And by this, I don't mean simply re-ordering the data, I also mean structure-access mutation (so that each generation's x86_instr_t is not layed out in the same way). I assume that even this has issues, but it's something to consider anyhow.

Note that all of the above will be done with very few mutation rules in the mutation engine. So, after all of that is complete, I will be spending a lot of time (hopefully with help from other people) writing tons of mutation rules.

So, that's all of it for the short term. That's not to say that I won't get inspired and/or distracted and add some more things to this short term list but at least all of this needs to be done before moving on to longer term issues.

Now you may be asking, what are the longer term issues?
Well, the first major one is to take all of the mutation rules that we've collected and apply some of Eric Filiol's ideas from "Metamorphism, Formal Grammars and Undecidable Code Mutation.". This probably means adding some layers of abstraction to the mutation library so that the rules we've can be suitably used to form a formal grammar. Then on top of this, it will may be necessary to make the grammar be able to mutate itself. Yes, this is complicated and I'm not even going to begin discussing implementing it, but this will get bukowski out of it's "just another metamoprhic engine" into something practically more undetectable.

One of the last things to do, in the distant future, is to make a system call abstraction library so that not only can the virus work on Windows, Mac OS (and other BSDs) but it should not even care what platform it runs on. By the way, in case you're sceptical, this is possible and I've done it before with the the old NOP-virus. The only part that I have to learn how to actually implement is some form of "execve-backdoor" for Windows.

The very very last thing that I'll do is update the x86 library to work for x86-64. This really is not a concern of mine right now since I'm still just proving theories but it will be necessary to increase the practical threat of the virus as x86-64 becomes the de facto ISA for PCs and servers. And at the same time I'll optimize everything for efficiency and size and fix any other practical detectability issues.

Re: CVE-2009-1175

Regarding CVE-2009-1175. I've already said this elsewhere but the bug is in the URL parameter to the HTTP GET method, not in the non-existent CGI that was listed. Sorry for the confusion, that was just the example I happened to post in the GNOME bugzilla.

Bukowski Project 0.0.5 Released

I've just tagged version 0.0.5 of the Bukowski framework.

libx86

It's now possible to disassemble and re-assemble most userland binaries

libelf

Added some basic functionality here. There's plenty more to do though

libmutate

rules.xml has been posted, which should give a general idea of what I have planned

generator

Started on a virus-generator. Not very useful yet. Basically just useful for a test harness for the rest of the libraries.

View Bukowski 0.0.5 SVN Repository

p.s. I also switched everything to SVN. Really tired of CVS's b.s.

Compression with neural networks (2)

Regarding my last post, "Compression with neural networks", I have come to a few conclusions on the details of the implementation.

Review

We want to map the integers x_i to y_i, where x_i = i for i from 0 to 255 and the members of y consisting of randomly chosen integers between 0 and 255.

A Potential implementation

The basic setup is that we have 8 neurons. Each neuron outputs a 0 or 1. Each neuron has m input channels. For each x_i, it must be split into m components. For example, if we assume x_i is 8-bits, we can break x_i into x_i0 and x_i1, where x_ij is 4-bits. Each neuron can be fed the same data vector, but gives a different bit of the output. So, mathematically, this boils down to each neuron being represented by a vector of functions, {f_i(x) | 0 < i < m }, and y_i = {f₀(x_i), ..., f_{m - 1}(x_i)}. y_i, as a vector, is the binary representation of y_i as a non-negative integer.

Notes

• Each input to the a function in {f_i(x) | 0 < i < m } can be considered as a vector or integer, choosing one over the other should be a matter of convenience.


• Each function {f_i(x) | 0 < i < m }, as a neuron, must be able to distinguish data that is not linearly separable. This is because componentizing it's input, x, cannot render a data set that is linearly separable, according to the expected bit of each neuron. Thus, it will be necessary to use another type of neuronal node such as a multi-layered perceptron.

Compression with neural networks

For many years, I've wondered - how is it possible to construct a function, f(x), given a sequence of numbers (i.e. sequential positive integers) such that it generates a different sequence of numbers, y, where y is chosen before f(x) is constructed. In many cases this is trivial, but for a randomly chosen output vector, y, it can become quite difficult.

One solution to the problem, which I've discovered lately, is to use a neural network. A neural network can be trained with the pair { x_i, y_i }, such that when x_i is given to the networks input channels, the target value y_i is given on it's output channels.

My experiment will be this: I will generated n random bytes to form y and train the neural network to map every k ∈ { i | 0 < i < n } to y_k.

Note that the width of the input channel directly limits the upper bound of n and that to output one byte for each input value, we require eight output channels, each being binary. Again, to point out the obvious, y_i ∈ {0,1}⁸.

This will require something like a multilayer-perceptron for most data sets, as there is no guarantee that all {i, y_i} pairs are linearly separable.

Why do I care? Well, I've been thinking recently how to carry on some sets of data throughout generations in a non-static form. I've investigated Huffman coding and a few other methods. But I have found flaws in all of those methods varying from bad compression rates to things that weaken the virus' resistance to detection in various forms. I don't have a proof yet, but I tend to believe that this solution, combined with some other techniques, mitigates many (if not all) of the issues I've encountered so far.

Using a neural network as part of a fitness function in a genetic algorithm

Recently I've become interested in neural networks and to a lesser extent, genetic algorithms.
And as usual, with any new technology, I immediately begin thinking about how this can be applied to offensive technology. So, the following is a synopsis of my first application idea.

First of all, you may be wondering, what do genetic algorithms have to do with viruses at all? I mean, verbally, it sounds legitimate when you say "virus" and "genetic" in the same sentence, but what use is it, technically?

The basic idea that I've come up with is that each generation of a metamorphic virus would generate several candidates and choose the "best" candidate out of the set. That's the extend of my usage of the phrase "genetic algorithm" and I realize this may not fit the formal definition; however, the basic principles relate.

Information, typically in the form of statistics, is extracted from each candidate. These are our characteristics and each candidate generates a vector of these n characteristics, represented as real numbers. For clarity, if we have m candidates, we have m vectors, each consisting of n elements. Now we use a neural net, that accepts an input vector x consisting of n elements. In other words, each input node of the network has n input channels. The neural network is trained to recognize all m vectors. Now we use the metamorphic engine to generate another k s.t. k < m candidates. Now, if we've designed our metamorphic engine and neural network correctly, we should be able to select the candidate which is most different from all the others. In other words, there should be a non-empty set of vectors that the neural net does not recognize. We can randomly select one of these as our potential candidate. Another, interesting way to do it is, instead of randomly selecting from the pool of rejected candidates, we can find a candidate which generated a correction error rate for the neural network which is in a specific rang. Note that I say, within a range here, because it may be intuitive to select the candidate with the highest error rate, but it may be desirable for slow-mutation, thus a lower and upper bound of error will need to be specified.

This is all very interesting; however there are many fundamental problems in it that I have not yet thought through. One of them is what I'll call the "flip-flop" problem. This is what happens when, in each generation, the most different candidate is chosen and ends up being fairly similar to the previous generation (which we know nothing about in the current generation). G₂ generates, for example, C₁, C₂, and C₃. Out of those 3, it selects C₂ which is in fact, most similar to G₁. So, it essentially flips between two very similar forms, which, in effect, neutralizes the power of a metamorphic engine. It may be intuitive to say that G_n should know something about G_n-1, but this is not a good solution, since anything that G_n knows about G_n-1, an anti-virus solution also knows. This reduces the power of metamorphism to something not as significantly better than simple polymorphism. I should mention, just to cover mistakes I've already made, what "know something about" means. It could be a pre-trained neural net, the set of characteristics from the previous generation, etc. This is not to say that we should disallow any carrying on of information throughout generations, it's just that we should carry as little as possible.

This is the summary of what I've come up with so far. As I said, there's plenty of room for improvement and as I read more about the subjects, I am confident that a solution will become apparent. Keep tuned for updates on this subject.