Swarup Kumar Sahoo
John Criswell
Vikram Adve
ABSTRACT
We propose an automatic diagnosis technique for isolating the root cause(s) of software failures. We use likely program invariants, automatically generated using correct inputs that are close to the fault-triggering input, to select a set of candidate program locations which are possible root causes. We then trim the set of candidate root causes using software-implemented dynamic backwards slicing, plus two new filtering heuristics: dependence filtering, and filtering via multiple failing inputs that are also close to the failing input. Experimental results on reported software bugs of three large open-source servers show that we are able to narrow down the number of candidate bug locations to between 5 and 17 program expressions, even in programs that are hundreds of thousands of lines long.
- Website. http://findbugs.sourceforge.net/.Google Scholar
- Website. http://www.hpenterprisesecurity.com/products/hp-fortifysoftware-security-center/hp-fortify-static-code-analyzer/.Google Scholar
- Website. http://www.coverity.com/products/coverity-save.html.Google Scholar
- NIST: National Institute of Standards and Technology. Software errors cost U.S. economy $59.5 billion annually: NIST assesses technical needs of industry to improve software-testing. June 2002.Google Scholar
- R. Abreu, P. Zoeteweij, and A. J. van Gemund. An evaluation of similarity coefficients for software fault localization. In 12th Pacific Rim International Symposium on Dependable Computing(PRDC), 2006. Google ScholarDigital Library
- V. Adve, C. Lattner, M. Brukman, A. Shukla, and B. Gaeke. LLVA: A low-level virtual instruction set architecture. In Proc. ACM/IEEE Int'l Symp. on Microarch. (MICRO), page 205,Washington, DC, USA, 2003. IEEE Computer Society. Google ScholarDigital Library
- S. Artzi, J. Dolby, F. Tip, and M. Pistoia. Directed test generation for effective fault localization. In Proceedings of the 19th international symposium on Software testing and analysis, ISSTA '10. Google ScholarDigital Library
- S. Artzi, J. Dolby, F. Tip, and M. Pistoia. Practical fault localization for dynamic web applications. In Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering, 2010. Google ScholarDigital Library
- D. L. Bird and C. U. Munoz. Automatic generation of random selfchecking test cases. IBM Systems Journal, 22(3):229--245, 1983.Google ScholarDigital Library
- M. Bond. Diagnosing and Tolerating Bugs in Deployed Systems. PhD thesis, University of Texas at Austin, 2008. Google ScholarDigital Library
- R. N. Charette. Why Software Fails. Spectrum, IEEE, 42(9):42--49, September 2005. Google ScholarDigital Library
- H. Cleve and A. Zeller. Locating causes of program failures. In ICSE, 2005. Google ScholarDigital Library
- R. Cytron, J. Ferrante, B. K. Rosen, M. N.Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. on Prog. Langs. and Systs. (TOPLAS), pages 13(4):451--490, October 1991. Google ScholarDigital Library
- D. Dhurjati, S. Kowshik, and V. Adve. SAFECode: Enforcing alias analysis for weakly typed languages. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2006. Google ScholarDigital Library
- W. Dietz, P. Li, J. Regehr, and V. Adve. Understanding Integer Overflow in C/C++. In International Conference on Software Engineering, June 2012. Google ScholarDigital Library
- M. Dimitrov and H. Zhou. Anomaly-based bug prediction, isolation, and validation: an automated approach for software debugging. In ASPLOS, 2009. Google ScholarDigital Library
- D. Engler, B. Chelf, A. Chou, and S. Hallem. Checking system rules using system-specific, programmer-written compiler extensions. In Proceedings of the 4th conference on Symposium on Operating System Design & Implementation - Volume 4, OSDI'00, 2000. Google ScholarDigital Library
- M. D. Ernst, J. Cockrell,W. G. Griswold, and D. Notkin. Dynamically discovering likely program invariants to support program evolution. IEEE Trans. Software Eng., 2001. Google ScholarDigital Library
- J. E. Forrester and B. P. Miller. An empirical study of the robustness of windows nt applications using random testing. In Proceedings of the 4th conference on USENIX Windows Systems Symposium, 2000. Google ScholarDigital Library
- K. Glerum, K. Kinshumann, S. Greenberg, G. Aul, V. Orgovan, G. Nichols, D. Grant, G. Loihle, and G. C. Hunt. Debugging in the (very) large: ten years of implementation and experience. In SOSP, 2009. Google ScholarDigital Library
- P. Godefroid, N. Klarlund, and K. Sen. Dart: directed automated random testing. In Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, PLDI '05, 2005. Google ScholarDigital Library
- P. Godefroid, M. Y. Levin, and D. A. Molnar. Automated whitebox fuzz testing. In Network Distributed Security Symposium (NDSS). Internet Society, 2008.Google Scholar
- N. Gupta, H. He, X. Zhang, and R. Gupta. Locating faulty code using failure-inducing chops. In ASE, 2005. Google ScholarDigital Library
- S. Hangal and M. S. Lam. Tracking down software bugs using automatic anomaly detection. In Proceedings of the International Conference on Software Engineering, 2002. Google ScholarDigital Library
- D. Jeffrey, N. Gupta, and R. Gupta. Effective and efficient localization of multiple faults using value replacement. In ICSM, 2009.Google ScholarCross Ref
- J. Jones, M. Harrold, and J. Stasko. Visualization of test information to assist fault localization. In Proceedings of the 24th international conference on Software engineering, 2002. Google ScholarDigital Library
- J. A. Jones and M. J. Harrold. Empirical evaluation of the tarantula automatic fault-localization technique. In ASE, 2005. Google ScholarDigital Library
- M. Jose and R. Majumdar. Cause clue clauses: error localization using maximum satisfiability. In PLDI, 2011. Google ScholarDigital Library
- C. Lattner and V. Adve. LLVM: A compilation framework for lifelong program analysis and transformation. In Proc. Conf. on Code Generation and Optimization, 2004. Google ScholarDigital Library
- B. Liblit, M. Naik, A. X. Zheng, A. Aiken, and M. I. Jordan. Scalable statistical bug isolation. In Proc. ACM SIGPLAN Conf. on Programming Language Design and Implementation (PLDI), 2005. Google ScholarDigital Library
- L. Mariani, F. Pastore, and M. Pezze. Dynamic analysis for diagnosing integration faults. IEEE Transactions on Software Engineering, 37:486--508, 2011. Google ScholarDigital Library
- A. Mockus, N. Nagappan, and T. T. Dinh-Trong. Test coverage and post-verification defects: A multiple case study. In International Symposium on Empirical Software Engineering and Measurement, 2009. Google ScholarDigital Library
- S. Nagarakatte, J. Zhao, M. M. Martin, and S. Zdancewic. Softbound: highly compatible and complete spatial memory safety for c. SIGPLAN Not., 44(6):245--258, 2009. Google ScholarDigital Library
- N. Nethercote and J. Seward. Valgrind: A program supervision framework. Electronic notes in theoretical computer science, 89(2), 2003.Google Scholar
- B. Pytlik, M. Renieris, S. Krishnamurthi, and S. P. Reiss. Automated fault localization using potential invariants. In Proceedings of the Workshop on Automated and Algorithmic Debugging, 2003.Google Scholar
- J. Regehr, Y. Chen, P. Cuoq, E. Eide, C. Ellision, and X. Yang. Testcase reduction for c compiler bugs. In Submission, 2012.Google Scholar
- S. K. Sahoo, J. Criswell, and V. Adve. An empirical study of reported bugs in server software with implications for automated bug diagnosis. In ICSE, 2010. Google ScholarDigital Library
- D. Scott. Making smart investments to reduce unplanned downtime. Tactical Guidelines TG-07-4033, Gartner Group, March 1999.Google Scholar
- W. N. Sumner and X. Zhang. Automatic failure inducing chain computation through aligned execution comparison. In Technical Report 08-023, Purdue University, 2008.Google Scholar
- W. N. Sumner and X. Zhang. Algorithms for automatically computing the causal paths of failures. In FASE, 2009. Google ScholarDigital Library
- W. N. Sumner and X. Zhang. Memory indexing: canonicalizing addresses across executions. In FSE, 2010. Google ScholarDigital Library
- J. Tucek, S. Lu, C. Huang, S. Xanthos, and Y. Zhou. Triage: diagnosing production run failures at the user's site. In SOSP, 2007. Google ScholarDigital Library
- B. Xin, W. N. Sumner, and X. Zhang. Efficient program execution indexing. In PLDI, 2008. Google ScholarDigital Library
- newblock A. Zeller. Isolating cause-effect chains from computer programs. In SIGSOFT '02: FSE, 2002. Google ScholarDigital Library
- A. Zeller and R. Hildebrandt. Simplifying and isolating failureinducing input. IEEE Transactions on Software Engineering, 2002. Google ScholarDigital Library
- X. Zhang, N. Gupta, and R. Gupta. Locating faults through automated predicate switching. In ICSE, 2006. Google ScholarDigital Library
- X. Zhang, N. Gupta, and R. Gupta. A study of effectiveness of dynamic slicing in locating real faults. Empirical Software Engineering, 2007. Google ScholarDigital Library
- X. Zhang, R. Gupta, and Y. Zhang. Precise dynamic slicing algorithms. In Proceedings of the 25th International Conference on Software Engineering, 2003. Google ScholarDigital Library
Index Terms
- Using likely invariants for automated software fault localization
Recommendations
A learning-to-rank based fault localization approach using likely invariants
ISSTA 2016: Proceedings of the 25th International Symposium on Software Testing and AnalysisDebugging is a costly process that consumes much of developer time and energy. To help reduce debugging effort, many studies have proposed various fault localization approaches. These approaches take as input a set of test cases (some failing, some ...
The inflection point hypothesis: a principled debugging approach for locating the root cause of a failure
SOSP '19: Proceedings of the 27th ACM Symposium on Operating Systems PrinciplesThe end goal of failure diagnosis is to locate the root cause. Prior root cause localization approaches almost all rely on statistical analysis. This paper proposes taking a different approach based on the observation that if we model an execution as a ...
Using likely invariants for automated software fault localization
ASPLOS '13We propose an automatic diagnosis technique for isolating the root cause(s) of software failures. We use likely program invariants, automatically generated using correct inputs that are close to the fault-triggering input, to select a set of candidate ...
Comments