Automatically fixing bugs in C programs with Genetic Algorithms

http://epr.adaptive.cs.unm.edu/

by peterhunt • 15 years ago

140 43 15 years ago

epr.adaptive.cs.unm.edu

rcfox3• 15 years ago

John Regehr has comments on when this should or shouldn't be used: http://blog.regehr.org/archives/383

peterhunt3• 15 years ago

That's a great point. Specifically, it initially seems like it would be a bad idea to have an automated system repair code that humans will need to maintain. However, I've looked at some of the examples of fixes this project has created and many of them are relatively small, and perhaps handing them to humans for code review, cleanup and "humanizing" might be a valid way to go.

jfruh2• 15 years ago

I've often thought about evolutionary engineering like this, comparing it to biological systems. The human body (and really all biological life) is a remarkable machine -- it runs for decades, much longer than just about anything people build, and under most circumstances can repair itself quite impressively. But if it needs repair beyond what it can do itself, you run into a harrowing mess, with difficulty swapping in new parts, some parts doing double duty, difficulty separating various systems, etc.

It's also not extensible at all, which is a big problem for software engineering. An evolutionarily derived codebase might do really well at the problem that provided the parameters for its initial evolution, but trying to get it to do something else might be difficult or impossible. I suppose you could use more evolutionary iterations to get it to do something else, but maybe it'd be easier to start from scratch at that point?

sehugg• 15 years ago

Yep, an evolutionary algorithm will take advantage of any shortcut and any loophope in your fitness function. They're best for optimization, not for ensuring correctness :)

eru2• 15 years ago

If you care to read the output, that seems like a good way to find errors in your fitness function.

5hoom• 15 years ago

This just looks so cool. I'm sure this would be very useful on giant legacy codebases where the author is long gone but the bugs remain, and I just like the idea of using ai techniques to refactor code. Seems all futuristic and stuff ;)

ForrestN• 15 years ago

I agree. Fun to imagine the software bugfixing future versions of itself.

jpadkins• 15 years ago

To some, self improving software is a frightening.

zb• 15 years ago

Fortunately giant legacy codebases are well known for their excellent automated test coverage, otherwise this comment would sound ridiculous.

tansey• 15 years ago

Their research is certainly cool and novel. On the surface, this is a straight-forward application of genetic programming (evolving abstract syntax trees):

1. Take function which fails some test case(s)

2. Parse AST

3. Find a bunch of other lines of code in the program and use those as possible mutations

4. Evolve until test performance is improved

The trick is #3. They are going on the hypothesis that the solution to bugs are often found in other parts of a program. For instance, you pass in a variable and forget to check for it being null. It's likely that you have a check for that somewhere else in the program, and if so, then you can add that (templated) line of code into your buggy function and it will now pass that test case.

It's certainly not a panacea, but it does work remarkably well for many bug cases.

peterhunt3• 15 years ago

Actually, I tried to implement something like this as an undergrad and I found that the search space was simply intractable and the fitness function too coarse grained (I.e binary). What I really like about this approach is that they do a trace of the program execution as a heuristic to guide the evolutionary strategy. That's awesome.

As a side note, a few months ago I reached out to this team to ask them a few questions. They are super nice.

rat• 15 years ago

How readable/maintainable is the resulting code?

Volpe• 15 years ago

That's the next genetic algorithms problem :P

munin2• 15 years ago

it's funny, this is exactly how lots of lower-division undergrads at my school approach writing code! i've heard professors refer to it as "debugging via brownian motion"

Someone• 15 years ago

You have very persisting undergrads. Most would skip the "check whether the tests that passed previously still pass" step.

munin2• 15 years ago

their grade is (sometimes) largely based on how well they pass unit tests.

aninteger• 15 years ago

One of the problems with machine generated code is that it's rarely readable by human beings so you'd still have to take a lot of time to see what the algorithm changed. The other huge problem is false positives (although OpenBSD made lint work for them so maybe it's not that bad)

amikula• 15 years ago

Fascinating concept. What if humans wrote the tests, and a genetic system like this used a specialized language (machine code or JVM bytecode, for example) to write a solution? What level of sophistication could a system like this attain?

rcfox3• 15 years ago

I assume it would be like finding the interpolating polynomial of a bunch of points in a row. (Like this: . . . . . .) The resulting polynomial would go through all of the points, but have very large peaks/valleys in between.

Essentially, you'd get a system that passed all of your tests, but produced garbage for anything not covered by the tests.

peterhunt3• 15 years ago

That's true, but I think this problem will eventually be tractable. We have tools like QuickCheck that can generate randomized test cases and ensure certain properties are maintained. While this probably isn't enough today, I could imagine this becoming a good starting point to improve this technology.

eric-hu2• 15 years ago

Your post got me excited because it sounds like you're describing Runge's Phenomenon ( http://en.wikipedia.org/wiki/Runge%27s_phenomenon ).

The wikipedia article doesn't have the best illustration, but I think the inherent idea is really wise: in trying too hard to meet your initial constraints, you can come up with a solution that's only useful at those constraint points.

_delirium4• 15 years ago

That's been an idea since the 60s in various forms, but tractability tends to be a big problem. The classic approach is to randomly generate Lisp code trees, guided by various heuristics or randomized-optimization algorithms (e.g. genetic programming). There have been some successes, but typically smallish algorithms for well-defined problems, rather than "normal" full-sized programs.

Some other attempts include: inductive logic programming (automatically infer logic programs from desired example output), partial programming (use statistical machine learning to fill in incompletely specified behavior in a program), and renewed attempts to use exhaustive or heuristic search where the search space is constrained by strong modern type systems (e.g. MagicHaskeller).

brindle• 15 years ago

1. The search space is all possible abstract syntax trees. That is a large search space.

2. The correct solution must also satisfy all test unit tests. Basically the bug fixing is driven by the fitness function that determines if the bug is fixed and the program still satisfies the specification, i.e. the unit tests.

If you have a complex program the challenge will be coming up with a complete specification of the program's behavior.

Havoc• 15 years ago

Is it just me or is this a horrible idea? Surely the GA will evolve in ways that fix the problem but introduce some new problems that you haven't even considered/tested for?

breckinloggins• 15 years ago

Sure, if you intend to just run the algorithm and check in the changes proudly proclaiming "it's fixed!"

A better use for it would be as an assistant to help you track down the root cause of stubborn bugs.

It's kind of like git-bisect in reverse.

dkubb• 15 years ago

I've used a similar technique to this called Mutation Testing to find code that wasn't tested by a unit test.

It doesn't use a GA, but it's still pretty neat. It parses the code into an AST and then mutates each node in the AST, rerunning the tests to see if they pass or fail. They are supposed to fail; if they continue to pass, it means a state isn't being tested.

The computer acts as my assistant tracking down cases I forgot to test, so that I can write the test to catch the mutation. Sometimes it even finds sections of code that are impossible to reach normally, allowing me to remove the dead code paths that I might otherwise have missed.

aidenn0• 15 years ago

On the other-hand a sizable percentage of developers already use this technique, informally, for bugfixing. My intuition is that replacing those developers with this algorithm would only improve code quality.

cpeterso• 15 years ago

A more tractable problem is genetic Acovea (Analysis of Compiler Options via Evolutionary Algorithm), a genetic algorithm to find the "best" optimization CFLAGS for compiling programs with gcc. Unfortunately, the Acovea project is no longer maintained.

http://web.archive.org/web/20101223023921/http://www.coyoteg...

I've been told that Intel's compiler performance team has investigated similar genetic algorithms.

InclinedPlane• 15 years ago

Such a hugely promising area of research. Also consider something even finer grained, adjusting optimization options on individual blocks of code at run-time or through instrumented binaries using genetic algorithms. It could revolutionize optimization.

zwieback• 15 years ago

I think if you took this technique plus input from compiler warnings and static code analysis and rolled them all together into a real-time IDE advisor you would have a nice product.

I don't think fixing programs in post processing is such a great idea but if the feedback can be used to make me a better programmer I'm all for it.

Scanning neighboring code is a really good idea, when I'm working on someone else's code I'll try to follow the exisiting practices instead of inserting bits and pieces in my own style.

braindead_in• 15 years ago

Reminds me of I Robot. Someday these C programs will group together and develop the ability to think independently.

erikb• 15 years ago

I enjoy the idea a lot, that one day people won't need to program their machines anymore but can discuss with them what they actually want. Yes, there will still be the need for the good old coding (maybe even more, because someone needs to write these eloquent programs, right?). And yes, the resulting programs of these discussions will be a lot more unclear (and thus prone to all kinds of bugs). But for what does your grandfather need a 100% correct program? He needs some food (no matter if carrots or beans), some clean clothes (no matter if the red or the blue shirt) and someone who reminds him to take his pills and tell him how the weather tomorrow maybe could be.

I wonder why we don't read more about these topics. Not just because of the opportunities for less educated people and the chance to automate repeatable tasks we can't repeat just yet. There are so many things where we are actually a lot more flexible then we think. For example when I prototype my new android game, I don't really care what way finding routines the game characters use. In the beginning I just want to put together something really fast to see if my game idea is worth anything. I would really like an IDE to just fill in the empty spots itself with anything that might work. And after time, using my more concrete programming input and the data from the test runs that every coder does while developing the IDE could improve the code itself.

I imagine an IDE that I can tell "I want to code a computergame. It should be rougelike. Very rougelike computergames are rouge, nethack, ADOM. A little rougelike computergames are Diablo, Dungean Siege, Baldurs Gate, Oblivion, World of Warcraft. Not rougelike computergames are Counter Strike, Doom, Sim City. Not computergames are VIM, Firefox, Word. Make prototype!"

eru2• 15 years ago

Vi is actually quite nethack-like in its interface.

caustic• 15 years ago

That's an interesting concept, but it seems like they are not alone in this field. Just recently I stumbled upon a web page by Moshe Sipper, who seems to work on a very similar topic "Darwinian Software Engineering":

    http://www.moshesipper.com/finch/

He makes a rather grandiose claim -- “We believe that in about fifty years' time it will be possible to program computers by means of evolution. Not merely possible but indeed prevalent.”

michaelochurch• 15 years ago

Watch out with this. If you auto-fix a Java program, the result is that none of the original code survives; it's rewritten from scratch in Scala!

Automatically fixing bugs in C programs with Genetic Algorithms

Related Stories