llvm based code mutation for genetic programming?

Question

for a study on genetic programming, I would like to implement an evolutionary system on basis of llvm and apply code-mutations (possibly on IR level).

I found llvm-mutate which is quite useful executing point mutations. As far as I have understood, the instructions get count/numbered, one can then e.g. delete a numbered instruction.

However, introduction of new instructions seems to be possible as one of the availeable statements in the code. Real mutation however would allow to insert any of the allowed IR instructions, irrespective of it beeing used in the code to be mutated. In addition, it should be possible to insert library function calls of linked libraries (not used in the current code, but possibly available, because the lib has been linked in clang).

Did I overlook this in the llvm-mutate or is it really not possible so far?

Are there any projects trying to /already have implement(ed) such mutations for llvm?

llvm has lots of code analysis tools which should allow the implementation of the afore mentioned approach. llvm is huge, so I'm a bit disoriented. Any hints which tools could be helpful (e.g. getting a list of available library functions etc.)?

Thanks Alex

Answer 1

Very interesting question. I have been intrigued by the possibility of doing binary-level genetic programming for a while. With respect to what you ask:

It is apparent from their documentation that LLVM-mutate can't do what you are asking. However, I think it is wise for it not to. My reasoning is that any machine-language genetic program would inevitably face the "Halting Problem", e.g. it would be impossible to know if a randomly generated instruction would completely crash the whole computer (for example, by assigning a value to a OS-reserved pointer), or it might run forever and take all of your CPU cycles. Turing's theorem tells us that it is impossible to know in advance if a given program would do that. Mind you, LLVM-mutate can cause for a perfectly harmless program to still crash or run forever, but I think their approach makes it less likely by only taking existing instructions.

However, such a thing as "impossibility" only deters scientists, not engineers :-)...

What I have been thinking is this: In nature, real mutations work a lot more like LLVM-mutate that like what we do in normal Genetic Programming. In other words, they simply swap letters out of a very limited set (A,T,C,G) and every possible variation comes out of this. We could have a program or set of programs with an initial set of instructions, plus a set of "possible functions" either linked or defined in the program. Most of these functions would not be actually used, but they will be there to provide "raw DNA" for mutations, just like in our DNA. This set of functions would have the complete (or semi-complete) set of possible functions for a problem space. Then, we simply use basic operations like the ones in LLVM-mutate.

Some possible problems though:

• Given the amount of possible variability, the only way to have acceptable execution times would be to have massive amounts of computing power. Possibly achievable in the Cloud or with GPUs.

• You would still have to contend with Mr. Turing's Halting Problem. However I think this could be resolved by running the solutions in a "Sandbox" that doesn't take you down if the solution blows up: Something like a single-use virtual machine or a Docker-like container, with a time limitation (to get out of infinite loops). A solution that crashes or times out would get the worst possible fitness, so that the programs would tend to diverge away from those paths.

As to why do this at all, I can see a number of interesting applications: Self-healing programs, programs that self-optimize for an specific environment, program "vaccination" against vulnerabilities, mutating viruses, quality assurance, etc.

I think there's a potential open source project here. It would be insane, dangerous and a time-sucking vortex: Just my kind of project. Count me in if someone doing it.