Distributable defect localization using markov models
William M. Portnoy, David S. Notkin · 2005
Using deployed software instances to localize defects enables better results with higher efficiency while enabling new analysis scenarios. We show that Markov chains can serve as profiles of software behavior with high fidelity, and these profile Markov chains can be used to localize software defects. Markov chains offer three advantages for defect localization. First, we illustrate how to iteratively search for defects while learning a profile Markov chain. This process enables a server to-direct fielded instances of the software to effectively place instrumentation, and the results of this analysis are available to the development team after the collection and analysis of the data received from every execution in the field. Developers can use these constantly improving location suggestions to investigate the defect. We validate our iterative approach empirically with examples. Second, we show that this Markov chain defect localization technique works at multiple levels of abstraction, from basic blocks in a control flow graph to lines in a source code file to functions in a call graph. This natural scalability provides a path toward applying this algorithm to larger, more complicated programs. Third, we show that Markov chains naturally handle multiple versions of the software. Software behavior profiles can be updated over time in the style of longitudinal analysis [Not02]. Markov chains naturally allow the Bayesian approach of providing a prior distribution that can be incrementally updated incorporating new evidence collected from experiments run in the field. The data collected from multiple versions of the software can be elegantly aggregated into a Markov chain. While other defect localization techniques are available, they have disadvantages solvable by using a probabilistic model such a Markov chains, and we argue that defect localization based on control flow is complementary to techniques based on data predicates. Compared to related work, this technique provides good tradeoffs between implementation simplicity, analysis execution cost, and the maintenance of user privacy. With this technique, we successfully localize defects in real world programs such as GNU BC and the Python interpreter, and we experimentally evaluate our approach with the Siemens programs and test suite.