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.

Why “Algorithms” are Good, or, Why Shelley WAS right, or, Another way that Bloglines sucks

Posted in Blogging,Computers & Technology,Search by Elliott Back on August 29th, 2005.

Take a look at today’s top-links page at Bloglines:

Ahhhh!

Do you see it? All of these links are talking about the same thing!! And, it’s bloody obvious from the confluence of the phrase “Google Talk” plastered as the page text! To you people at Bloglines, get with the game. Read this tutorial, pick your favorite clustering method, and then implement it so that we don’t get crappy results for “top links” that make us weep.

Yieldbuild Review / Casestudy

Posted in Adsense,Google,Optimization by Elliott Back on March 7th, 2008.

Since Techcrunch just mentioned Yieldbuild, a company I love, in YieldBuild Raises $6 Million Series B For Optimizing Ads, I figure that now is a good time to throw in my two bits. If you don’t know, Yieldbuild is the internet’s premier advertising optimization tool, boosting webmaster CPM and CTR. Crunch says it uses computer algorithms to automatically optimize your site’s ad spots with the most profitable combination of ad layout, style, and network. The system continually tests alternative configurations of layouts, networks, and color, looking for the highest performing ones.”

Does it really work? Check out this chart:

yieldbuild.png

The answer is simply yes–it improved CPM on my blog network by 21%. If you discount revenue from other blogs, this one went from 1.51 CPM to 2.51 CPM, an increase of 66% just due to using Yieldbuild. Now that I have a fulltime job, I don’t have time to bang out optimized advertising solutions. If you’re like this, why not let Yieldbuild do it for you?

Next Page »