Andreas Zeller, Saarland University, Germany

Search-Based Program Analysis

Abstract: Traditionally, program analysis has been divided into two camps: Static techniques analyze code and safely determining what cannot happen; while dynamic techniques analyze executions to determine what actually has happened. While static analysis suffers from overapproximation, erring on whatever could happen, dynamic analysis suffers from underapproximation, ignoring what else could happen. In this talk, I suggest to systematically generate executions to enhance dynamic analysis, exploring and searching the space of software behavior. First results in fault localization and specification mining demonstrate the benefits of search-based analysis.

Speaker biography: Andreas Zeller is a full professor at Saarland University in Saarbrücken, Germany. His broad research area concerns the construction and evolution of large, complex software systems at reasonable cost and high reliability. His research in this area concerns the analysis of these systems, especially the analysis of why these systems fail to work as they should. In 2009, Zeller got the ACM SIGSOFT Impact Paper Award for his work on delta debugging as the most influential software engineering paper of 1999. His book "Why programs fail" got the 2005 Software Productivity Award as one of the three most productivity-boosting books of the year.

Andreas Zeller is the program chair of ESEC/FSE 2011, with which SSBSE is co-located.

Darrell Whitley, Colorado State University, USA

Promoting Shared Subsolutions for Better Recombination

Abstract: On certain classes of problems, recombination is more effective if the parents that are being recombined share common subsolutions. This is certainly the case for elementary landscapes, where the common subsolutions can be used to partition the recombination space into linearly independent subproblems. These independent subproblems can be recombined in a greedy fashion so that that a very concrete kind of exponential filtering happens: if the problem can be decomposed into k subproblems, a single greedy recombination can select the best of 2^k possible offspring. In some cases (when the recombination subspace is small enough), recombination can be replaced by a form of dynamic programming that return the optimal solution in the corresponding subspace. These ideas have been applied with excellent results for TSP, easily beating Chained-LK and sometimes beating LKH.

For Search Based Software Engineering, these ideas might - for example - be useful when applying Genetic programming to fix software bugs in large programs. Some form of mutation or local search may first be needed to create solutions with common subsolutions, and only after this may the potential benefits for recombination be revealed.

If this is the case, we should ask how we can more actively promote shared common subsolutions, and to what degree can we exploit common subsolutions if the subsolutions are not linearly independent.

Speaker biography: Darrell Whitley is Chair of the Department of Computer Science at Colorado State University. From 1993 to 1997 Prof. Whitley served as Chair of the Governing Board of the International Society for Genetic Algorithms. In 1999 ISGA merged with the Genetic Programming community to form the International Society for Genetic and Evolutionary Computation. From 1997 to 2002 Whitley served as Editor-in-Chief for the journal Evolutionary Computation published by MIT Press. In 2005 ISGEC became a Special Interest Group (SIGEVO) of ACM. In 2007 Whitley was elected Chair of SIGEVO.

Darrell Whitley helped establish the SBSE track at GECCO, which began in 2002 and is celebrating its 10th year at GECCO 2011.