Skip to main content
SpringerLink
Log in

Fast Model-Based Fault Localisation with Test Suites

  • Conference paper
  • First Online:
Tests and Proofs (TAP 2015)

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 9154))

Included in the following conference series:

Abstract

Fault localisation, i.e. the identification of program locations that cause errors, takes significant effort and cost. We describe a fast model-based fault localisation algorithm which, given a test suite, uses symbolic execution methods to fully automatically identify a small subset of program locations where genuine program repairs exist. Our algorithm iterates over failing test cases and collects locations where an assignment change can repair exhibited faulty behaviour. Our main contribution is an improved search through the test suite, reducing the effort for the symbolic execution of the models and leading to speed-ups of more than two orders of magnitude over the previously published implementation by Griesmayer et al.

We implemented our algorithm for C programs, using the KLEE symbolic execution engine, and demonstrate its effectiveness on the Siemens TCAS variants. Its performance is in line with recent alternative model-based fault localisation techniques, but narrows the location set further without rejecting any genuine repair locations where faults can be fixed by changing a single assignment.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Ahmadzadeh, M., Elliman, D., Higgins, C.: An analysis of patterns of debugging among novice computer science students. In: SIGCSE, pp. 84–88 (2005)

    Google Scholar 

  2. Bendersky, E.: Pycparser: C parser and AST generator written in Python (2012). https://github.com/eliben/pycparser

  3. Cadar, C., Ganesh, V., Pawlowski, P.M., Dill, D.L., Engler, D.R.: EXE: Automatically Generating Inputs of Death. ACM Trans. Inf. Syst. Secur. 12(2), 10A (2008)

    Article  Google Scholar 

  4. Chandra, S., Torlak, E., Barman, S., Bodik, R.: Angelic debugging. In: ICSE, pp. 121–130 (2011)

    Google Scholar 

  5. Cheeseman, P., Kanefsky, B., Taylor, W.M.: Where the really hard problems are. In: IJCAI, pp. 331–337 (1991)

    Google Scholar 

  6. Cleve, H., Zeller, A.: Locating causes of program failures. In: ICSE, pp. 342–351 (2005)

    Google Scholar 

  7. Console, L., Friedrich, G., Dupre, D.T.: Model-based diagnosis meets error diagnosis in logic programs. In: Fritzson, P.A. (ed.) AADEBUG 1993. LNCS, vol. 749, pp. 85–87. Springer, Heidelberg (1993)

    Google Scholar 

  8. Cook, S.A.: The complexity of theorem-proving procedures. In: Proc. ACM Symposium on Theory of Computing, pp. 151–158 (1971)

    Google Scholar 

  9. Cordeiro, L., Fischer, B., Marques-Silva, J.: SMT-Based Bounded Model Checking for Embedded ANSI-C Software. IEEE Trans. Softw. Engg. 38(4), 957–974 (2012)

    Article  Google Scholar 

  10. Do, H., Elbaum, S., Rothermel, G.: Supporting Controlled Experimentation with Testing Techniques. Empirical Softw. Engg., 405–435 (2005)

    Google Scholar 

  11. Griesmayer, A., Staber, S., Bloem, R.: Automated Fault Localization for C Programs. Electronic Notes in Theoretical Computer Science, 95–111 (2007)

    Google Scholar 

  12. Griesmayer, A., Staber, S., Bloem, R.: Fault localization using a model checker. Softw. Test. Verif. Reliab. 20(2), 149–173 (2010)

    Article  MATH  Google Scholar 

  13. Groce, A., Chaki, S., Kroening, D., Strichman, O.: Error explanation with distance metrics. Int. J. Softw. Tools Technol. Transf. 8(3), 229–247 (2006)

    Article  Google Scholar 

  14. Groce, A., Visser, W.: What Went Wrong: Explaining Counterexamples. In: Ball, T., Rajamani, S.K. (eds.) SPIN 2003. LNCS, vol. 2648, pp. 121–135. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  15. Hutchins, M., Foster, H., Goradia, T., Ostrand, T.: Experiments on the effectiveness of dataflow- and control-flow-based test adequacy criteria. In: ICSE, pp. 191–200 (1994)

    Google Scholar 

  16. Jones, J.A., Harrold, M.J.: Empirical Evaluation of the Tarantula Automatic Fault-localization Technique. In: ASE, pp. 273–282 (2005)

    Google Scholar 

  17. Jose, M., Majumdar, R.: Cause Clue Clauses: Error Localization Using Maximum Satisfiability. SIGPLAN Not 46(6), 437–446 (2011)

    Article  Google Scholar 

  18. de Kleer, J., Williams, B.: Diagnosing multiple faults. Artificial Intelligence 32(1), 97–130 (1987)

    Article  MATH  Google Scholar 

  19. Konighofer, R., Bloem, R.: Automated error localization and correction for imperative programs. In: FMCAD, pp. 91–100 (2011)

    Google Scholar 

  20. Könighofer, R., Bloem, R.: Repair with On-The-Fly Program Analysis. In: Biere, A., Nahir, A., Vos, T. (eds.) HVC. LNCS, vol. 7857, pp. 56–71. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  21. Könighofer, R., Toegl, R., Bloem, R.: Automatic Error Localization for Software Using Deductive Verification. In: Yahav, E. (ed.) HVC 2014. LNCS, vol. 8855, pp. 92–98. Springer, Heidelberg (2014)

    Google Scholar 

  22. Le, H.M., Grosse, D., Drechsler, R.: Automatic TLM Fault Localization for SystemC. Trans. Comp.-Aided Des. Integ. Cir. Sys. 31(8), 1249–1262 (2012)

    Google Scholar 

  23. de Moura, L., Bjørner, N.S.: Z3: An Efficient SMT Solver. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 337–340. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  24. Naish, L., Lee, H.J., Ramamohanarao, K.: A Model for Spectra-based Software Diagnosis. ACM Trans. Softw. Eng. Methodol. 20(3), 11A (2011)

    Article  Google Scholar 

  25. Nelson, G., Oppen, D.C.: Simplification by Cooperating Decision Procedures. ACM Trans. Program. Lang. Syst., 245–257 (1979)

    Google Scholar 

  26. Nguyen, H.D.T., Qi, D., Roychoudhury, A., Chandra, S.: SemFix: program repair via semantic analysis. In: ICSE, pp. 772–781 (2013)

    Google Scholar 

  27. Pham, H.: Software reliability. Springer (2000)

    Google Scholar 

  28. Reiter, R.: A theory of diagnosis from first principles. Artificial Intelligence 32(1), 57–95 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  29. Renieres, M., Reiss, S.P.: Fault localization with nearest neighbor queries. In: ASE, pp. 30–39 (2003)

    Google Scholar 

  30. Sahoo, S.K., Criswell, J., Geigle, C., Adve, V.: Using likely invariants for automated software fault localization. In: ASPLOS, pp. 139–152 (2013)

    Google Scholar 

  31. Santelices, R., Jones, J.A., Yu, Y., Harrold, M.J.: Lightweight fault-localization using multiple coverage types. In: ICSE, pp. 56–66 (2009)

    Google Scholar 

  32. Staber, S., Bloem, R.: Fault Localization and Correction with QBF. In: Marques-Silva, J., Sakallah, K.A. (eds.) SAT 2007. LNCS, vol. 4501, pp. 355–368. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  33. Sülflow, A., Fey, G., Bloem, R., Drechsler, R.: Debugging design errors by using unsatisfiable cores. In: MBMV, pp. 159–168 (2008)

    Google Scholar 

  34. Vessey, I.: Expertise in debugging computer programs: A process analysis. International Journal of Man-Machine Studies 23(5), 459–494 (1985)

    Article  Google Scholar 

  35. Wong, W.E., Debroy, V.: A survey of software fault localization. Tech. Rep. UTDCS-45-09, Uni. of Texas at Dallas (2009)

    Google Scholar 

  36. Xie, X., Chen, T.Y., Kuo, F.C., Xu, B.: A Theoretical Analysis of the Risk Evaluation Formulas for Spectrum-based Fault Localization. ACM Trans. Softw. Eng. Methodol. 22(4), 31A (2013)

    Article  Google Scholar 

  37. Zeller, A.: Yesterday, my program worked. Today, it does not. Why? SIGSOFT Softw. Eng. Notes 24(6), 253–267 (1999)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Southampton, Southampton, SO17 1BJ, UK

    Geoff Birch & Michael R. Poppleton

  2. Stellenbosch University, Stellenbosch, 7602, Matieland, South Africa

    Bernd Fischer

Authors
  1. Geoff Birch
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bernd Fischer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michael R. Poppleton
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Geoff Birch .

Editor information

Editors and Affiliations

  1. Inria Nancy & LORIA, Villers-lès-Nancy, France

    Jasmin Christian Blanchette

  2. CEA LIST Nano-Innov, Saclay, France

    Nikolai Kosmatov

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Birch, G., Fischer, B., Poppleton, M.R. (2015). Fast Model-Based Fault Localisation with Test Suites. In: Blanchette, J., Kosmatov, N. (eds) Tests and Proofs. TAP 2015. Lecture Notes in Computer Science(), vol 9154. Springer, Cham. https://doi.org/10.1007/978-3-319-21215-9_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-21215-9_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-21214-2

  • Online ISBN: 978-3-319-21215-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation