2013 Distinguished Speaker Series
Adam Porter - iTree:
Efficiently Discovering High-Coverage Configurations Using Interaction Trees
Friday, November 22, 2013 - 11:15am - Trabant Theater
Refreshments in 102A Smith Hall at 10:30am
Modern software systems are increasingly configurable. While this has many benefits, it also makes some software engineering tasks, such as software testing, much harder. This is because, in theory, unique errors could be hiding in any configuration, and, therefore, every configuration may need to undergo expensive testing. As this is generally infeasible, developers need cost-effective techniques for selecting which specific configurations they will test. One popular selection approach is combinatorial interaction testing (CIT), where the developer selects a strength t and then computes a covering array (a set of configurations) in which all t-way combinations of configuration option settings appear at least once.
In prior work, we demonstrated several limitations of the CIT approach. In particular, we found that a given system’s effective configuration space—the minimal set of configurations needed to achieve a specific goal— may comprise only a tiny subset of the system’s full configuration space. We also found that this effective configuration space may not be well approximated by t-way covering arrays. Based on these insights we have developed an algorithm called interaction tree discovery (iTree).
iTree is an iterative learning algorithm that efficiently searches for a small set of configurations that closely approximates a system’s effective configuration space. On each iteration iTree tests the system on a small sample of carefully chosen configurations, monitors the system’s behaviors, and then applies machine learning techniques to discover which combinations of option settings are potentially responsible for any newly observed behaviors. This information is used in the next iteration to pick a new sample of configurations that are likely to reveal further new behaviors.
We have evaluated the iTree algorithm by comparing the coverage it achieves versus that of covering arrays and randomly generated configuration sets. We have also evaluated its scalability by using it to test MySQL, at 1M+ LOC database system. Our results strongly suggest that the iTree algorithm is highly scalable and can identify a high-coverage test set of configurations more effectively than existing methods.
(Joint work with Charles Song and Jeffrey S. Foster)
Adam Porter is a professor in the Deptartment of Computer Science,University of Maryland and at University of Maryland Institute for Advanced Computing Studies (UMIACS). He specializes in software development with interests in programmer productivity, quality assurance, and mobile application design (particularly mobile learning tools). He has been honored as Mobile Learning Fellow, 2010, UMD OIT/Center for Teaching Excellence and is an IEEE and ACM Senior Member. His PhD is from the University of California, Irvine, 1991.