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.

SearchMe: Visual, Clustering search

Posted in Apple,Google,Interface,Search,Web 2.0 by Elliott Back on April 27th, 2008.

The more I look at visual search engine SearchMe, the more I like it. In a way that text-based search engine Google has never done, SearchMe brings thumbnails to search results without losing any of the textual indicators we need to process relevance. SearchMe is also innovating in clustering search results into categories or topics, something Google has experimented with their sets demo but never implemented into the larger search engine. Perhaps the best way to show you how much more relevant SearchMe can be is through a short example, searching for “Obama.”

searchme-obama-1.png

The first thing I get, as I type “Obama,” is a list of categories that SearchMe finds relevant. I click on “Politicians” and it takes me to the next screen, the main area for exploring search results:

searchme-obama-2.png

There are a few features you should note that set the SearchMe results apart from their competition. First, they keep the list of categories you’re interested in just one click away from instant filtering at the top of the results. Second, all of the available space of the page is filled with a gigantic preview of the search results. The title of the website is shown at the bottom, along with the site URL when you mouseover the results. Essentially, their search results are a better version of Apple’s coverflow, applied to websites. Clicking on a preview will take you directly to the page of interest, in the same tab, just like most search engines do today.

searchme-scientology.png

Their dynamic snippets code is nice, as well, highlighting the search terms you used in multiple colours. It appears to have been implemented directly in the coverflow-like flash engine, or behind the scenes is coming back as a new layer of image, as it loads only after the high resolution preview has loaded. An unfortunate side-effect of their highlighting algorithm is that when searching for multiple words, like “Calderon de la Barca,” the words will be highlighted separately, even if found next to each other.

searchme-china.png

Not all their results work well; for example, searching for “China” leads me into irrelevance, regardless of the category I choose, and also brings up this half-rendered view of NBA China, that my own browser renders properly. Other search terms also return odd categories and funny previews, but I imagine that this is something that will improve over time. The big problems for a search engine, responsiveness and interface, are already solved as SearchMe is both lightning fast and beautiful.

If you’re interested, you can go check out their blog or signup to the private beta. Apparently, the venture is Sequoia backed, according to Techcrunch, which probably means it’s serious about being a big web search contender in the future. According to Louis Grey, the searchme spider is aggressively hitting his blog, too. It will be interesting to come back and a year and see how SearchMe has evolved. The most likely outcome for this is being acquired by one of the big four–Facebook, Google, Yahoo, or Microsoft–since it’s hard to imagine unseating any of them in the popular mindset.

Next Page »