Wei Le
Mary Lou Soffa
ABSTRACT
Although a number of automatic tools have been developed to detect faults, much of the diagnosis is still being done manually. To help with the diagnostic tasks, we formally introduce fault correlation, a causal relationship between faults. We statically determine correlations based on the expected dynamic behavior of a fault. If the occurrence of one fault causes another fault to occur, we say they are correlated. With the identification of the correlated faults, we can better understand fault behaviors and the risks of faults. If one fault is uniquely correlated with another, we know fixing the first fault will fix the other. Correlated faults can be grouped, enabling prioritization of diagnoses of the fault groups. In this paper, we develop an interprocedural, path-sensitive, and scalable algorithm to automatically compute correlated faults in a program. In our approach, we first statically detect faults and determine their error states. By propagating the effects of the error state along a path, we detect the correlation of pairs of faults. We automatically construct a correlation graph which shows how correlations occur among multiple faults and along different paths. Guided by a correlation graph, we can reduce the number of faults required for diagnosis to find root causes. We implemented our correlation algorithm and found through experimentation that faults involved in the correlations can be of different types and located in different procedures. Using correlation information, we are able to automate diagnostic tasks that previously had to be done manually.
- Personal communication with Mingdong Shang, Code Reviewer at Microsoft, 2006.Google Scholar
- T. Ball, M. Naik, and S. K. Rajamani. From symptom to cause: localizing errors in counterexample traces. In Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2003. Google ScholarDigital Library
- R. Bodik, R. Gupta, and M. L. Soffa. Refining data flow information using infeasible paths. In Proceedings of the ACM SIGSOFT International Symposium on Foundations of Software Engineering, 1997. Google ScholarDigital Library
- D. Brumley, T. Chiueh, R. Johnson, H. Lin, and D. Song. RICH: Automatically protecting against integer-based vulnerabilities. In Symposium on Network and Distributed Systems Security, 2007.Google Scholar
- W. R. Bush, J. D. Pincus, and D. J. Sielaff. A static analyzer for finding dynamic programming errors. Software Practice and Experience, 2000. Google ScholarDigital Library
- S. Chen, Z. Kalbarczyk, J. Xu, and R. K. Iyer. A data-driven finite state machine model for analyzing security vulnerabilities. In International Conference on Dependable Systems and Networks, 2003.Google Scholar
- J. Clause and A. Orso. Penumbra: automatically identifying failure-relevant inputs using dynamic tainting. In Proceedings of the eighteenth international symposium on software testing and analysis, 2009. Google ScholarDigital Library
- CVE. http://cve.mitre.org/.Google Scholar
- M. Das, S. Lerner, and M. Seigle. ESP: path-sensitive program verification in polynomial time. In Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, 2002. Google ScholarDigital Library
- E. Duesterwald, R. Gupta, and M. L. Soffa. A practical framework for demand-driven interprocedural data flow analysis. ACM Transactions on Programming Languages and Systems, 1997. Google ScholarDigital Library
- D. Evans. Static detection of dynamic memory errors. In Proceedings of the ACM SIGPLAN 1996 Conference on Programming Language Design and Implementation, 1996. Google ScholarDigital Library
- FindBugs. http://findbugs.sourceforge.net/.Google Scholar
- A. K. Ghosh, T. O'Connor, and G. Mcgraw. An automated approach for identifying potential vulnerabilities in software. In 1998 IEEE Symposium on Security and Privacy, 1998.Google ScholarCross Ref
- T. Goradia. Dynamic impact analysis: a cost-effective technique to enforce error-propagation. SIGSOFT Software Engineering Notes, 1993. Google ScholarDigital Library
- B. Hackett, M. Das, D. Wang, and Z. Yang. Modular checking for buffer overflows in the large. In Proceeding of the 28th International Conference on Software Engineering, 2006. Google ScholarDigital Library
- Y. Hamadi. Disolver: A Distributed Constraint Solver. Technical Report MSR-TR-2003-91, Microsoft.Google Scholar
- L. Hatton. Testing the value of checklists in code inspections. IEEE Software, 2008. Google ScholarDigital Library
- S. Heckman and L. Williams. A model building process for identifying actionable static analysis alerts. In Proceedings of the 2009 International Conference on Software Testing Verification and Validation, 2009. Google ScholarDigital Library
- D. Jeffrey, N. Gupta, and R. Gupta. Fault localization using value replacement. In Proceedings of the 2008 international symposium on Software testing and analysis, 2008. Google ScholarDigital Library
- T. Kremenek, K. Ashcraft, J. Yang, and D. Engler. Correlation exploitation in error ranking. SIGSOFT Software Engineering Notes, 2004. Google ScholarDigital Library
- T. Kremenek and D. Engler. Z-ranking: Using statistical analysis to counter the impact of static analysis approximations. In Proceedings of the 10th International Static Analysis Symposium, 2002. Google ScholarDigital Library
- W. Le and M. L. Soffa. Marple: a demand-driven path-sensitive buffer overflow detector. In Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering, 2008. Google ScholarDigital Library
- W. Le and M. L. Soffa. General, scalable path-sensitive fault detection. Technical Report CS-2010-11 by Computer Science Department, University of Virginia, 2010.Google Scholar
- S. Lu, Z. Li, F. Qin, L. Tan, P. Zhou, and Y. Zhou. Bugbench: Benchmarks for evaluating bug detection tools. In Proceedings of Workshop on the Evaluation of Software Defect Detection Tools, 2005.Google Scholar
- F. Mueller and D. B. Whalley. Avoiding conditional branches by code replication. In Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, 1995. Google ScholarDigital Library
- Phoenix. http://research.microsoft.com/phoenix/.Google Scholar
- J. R. Ruthruff, J. Penix, J. D. Morgenthaler, S. Elbaum, and G. Rothermel. Predicting accurate and actionable static analysis warnings: an experimental approach. In Proceedings of the 30th international conference on Software engineering, 2008. Google ScholarDigital Library
- B. Schwarz, H. Chen, D. Wagner, J. Lin, W. Tu, G. Morrison, and J. West. Model checking an entire linux distribution for security violations. In Proceedings of the 21st Annual Computer Security Applications Conference, 2005. Google ScholarDigital Library
- G. Snelting. Combining slicing and constraint solving for validation of measurement software. In Proceedings of the Third International Symposium on Static Analysis, 1996. Google ScholarDigital Library
- K. Wu and Y. Malaiya. The effect of correlated faults on software reliability. In Proceedings of Software Reliability Engineering, 4th International Symposium on, 1993.Google ScholarCross Ref
- A. Zeller. Yesterday, my program worked. today, it does not. why? SIGSOFT Software Engineering Notes, 1999. Google ScholarDigital Library
- Z. Zhang, W. K. Chan, T. H. Tse, B. Jiang, and X. Wang. Capturing propagation of infected program states. In Proceedings of the 7th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium, 2009. Google ScholarDigital Library
- M. Zitser, R. Lippmann, and T. Leek. Testing static analysis tools using exploitable buffer overflows from open source code. In Proceedings of the 12th International Symposium on Foundations of Software Engineering, 2004. Google ScholarDigital Library
Index Terms
- Path-based fault correlations
Recommendations
Refining buffer overflow detection via demand-driven path-sensitive analysis
PASTE '07: Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineeringAlthough static analysis is an important technique for detecting buffer overflow before software deployment, current static tools rely on considerable human effort for annotating code to help analysis, or for diagnosing warnings, many of which are false ...
An Experimental Evaluation on Reliability Features of N-Version Programming
ISSRE '05: Proceedings of the 16th IEEE International Symposium on Software Reliability EngineeringAlthough N-version programming has been employed in some mission-critical applications, the reliability and fault correlation issues remain a debatable topic in the research community. In this paper, we perform a comprehensive evaluation on our recent ...
Stress-Based and Path-Based Fault Injection
The objective of fault injection is to mimic the existence of faults and to force the exercise of the fault tolerance mechanisms of the target system. To maximize the efficacy of each injection, the locations, timing, and conditions for faults being ...
Comments