Elliott C. Back: Internet & Technology

Fixing Bugs with Genetic Algorithms

Posted in Code,Errors by Elliott Back on September 28th, 2009.

Wow, check out this preprint: A Genetic Programming Approach to Automated Software Repair. Essentially, the researchers used a suit of positive and negative unit tests as the distance scoring function for a genetic algorithm which operated on code to mutate branches. More interestingly, they did this on off-the-shelf legacy C programs.

Genetic programming is combined with program analysis methods to repair bugs in off-the-shelf legacy C programs. Fitness is defined using negative test cases that exercise the bug to be repaired and positive test cases that encode program requirements. Once a successful repair is discovered, structural differencing algorithms and delta debugging methods are used to minimize its size. Several modifications to the GP technique contribute to its success: (1) genetic operations are localized to the nodes along the execution path of the negative test case; (2) high-level statements are represented as single nodes in the program tree; (3) genetic operators use existing code in other parts of the program, so new code does not need to be invented. The paper describes the method, reviews earlier experiments that repaired 11 bugs in over 60,000 lines of code, reports results on new bug repairs, and describes experiments that analyze the performance and efficacy of the evolutionary components of the algorithm.

Literally, they wrote some small samples of code that said “here’s what I want this buggy program to do” and then their genetic algorithm actually went off and hacked away at the code (much like many of us flesh-and-blood programmers) and made it work. They have several nice examples, including one on automatically fixing the infamous Zune date bug.

The dream of automatic programming has eluded computer scientists for at least 50 years. Although the methods described in this paper do not evolve new programs from scratch, they do show how to evolve legacy software to repair existing faults.

This entry was posted on Monday, September 28th, 2009 at 8:27 pm and is tagged with . You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback.

2 Responses to “Fixing Bugs with Genetic Algorithms”

  1. Mr Ian Martin Ajzenszmidt says:

    Use this technology to program from a seed single 1 (one)line of code and automatically mutate until specification satisfied. When the specification changes just repeat the process with the new specification. Readability doesnt matter because the genetic programming does everything.

    • Mr Ian Martin Ajzenszmidt says:

      Initialise with a single line of code and let the
      genetic programming software automatically do all the programming / coding to the exact specification. As long as the specification is correct, this will generate bug free and correct software at virtually zero cost and, given current hardware such as GPGPU + CPU, minimal time. The only expense will be in getting the specification correct. There may be potential for an interactive specification elicitation interview and review software program. Net result and benefit. Reduce software development and maintenence upgrades from years and months to hours.

Leave a Reply