GenTree: Using Decision Trees to Learn Interactions for Configurable Software
This addresses challenges in developing, testing, and analyzing configurable software, but it is incremental as it builds on existing dynamic analysis and decision tree methods.
The paper tackles the problem of understanding how configuration options affect code coverage in configurable software by introducing GenTree, a dynamic analysis that learns logical interactions, and shows it efficiently finds precise interactions using a small fraction of the configuration space in experiments on 17 systems.
Modern software systems are increasingly designed to be highly configurable, which increases flexibility but can make programs harder to develop, test, and analyze, e.g., how configuration options are set to reach certain locations, what characterizes the configuration space of an interesting or buggy program behavior? We introduce GenTree, a new dynamic analysis that automatically learns a program's interactions - logical formulae that describe how configuration option settings map to code coverage. GenTree uses an iterative refinement approach that runs the program under a small sample of configurations to obtain coverage data; uses a custom classifying algorithm on these data to build decision trees representing interaction candidates; and then analyzes the trees to generate new configurations to further refine the trees and interactions in the next iteration. Our experiments on 17 configurable systems spanning 4 languages show that GenTree efficiently finds precise interactions using a tiny fraction of the configuration space.