Entropy-Based Test Generation for Improved Fault Localization

J. Campos and R. Abreu and G. Fraser and M. d’Amorim
ACM/IEEE International Conference on Automated Software Engineering (ASE), 2013


Spectrum-based Bayesian reasoning can effectively rank candidate fault locations based on passing/failing test cases, but the diagnostic quality highly depends on the size and diversity of the underlying test suite. As test suites in practice often do not exhibit the necessary properties, we present a technique to extend existing test suites with new test cases that optimize the diagnostic quality. We apply probability theory concepts to guide test case generation using entropy, such that the amount of uncertainty in the diagnostic ranking is minimized. Our EntBug prototype extends the search-based test generation tool EvoSuite to use entropy in the fitness function of its underlying genetic algorithm, and we applied it to seven real faults. Empirical results show that our approach reduces the entropy of the diagnostic ranking by 49% on average (compared to using the original test suite), leading to a 91% average reduction of diagnosis candidates needed to inspect to find the true faulty one.


  author = {Campos, Jos{\'e} and Abreu, Rui and Fraser, Gordon and d'Amorim, Marcelo},
  title = {Entropy-Based Test Generation for Improved Fault Localization},
  booktitle = {Proceedings of the 28th IEEE/ACM International Conference on
  Automated Software Engineering},
  series = {ASE 2013},
  year = {2013},
  isbn = {978-1-4799-0215-6},
  location = {Palo Alto, USA},
  pages = {257--267},
  numpages = {10},
  url = {},
  doi = {},
  acmid = {},
  publisher = {ACM},
  address = {New York, NY, USA},
  keywords = {Fault localization, test case generation},