skip to main content
10.1145/1029894.1029907acmconferencesArticle/Chapter ViewAbstractPublication PagesfseConference Proceedingsconference-collections
Article

PSE: explaining program failures via postmortem static analysis

Published: 31 October 2004 Publication History

Abstract

In this paper, we describe PSE (Postmortem Symbolic Evaluation), a static analysis algorithm that can be used by programmers to diagnose software failures. The algorithm requires minimal information about a failure, namely its kind (e.g. NULL dereference), and its location in the program's source code. It produces a set of execution traces along which the program can be driven to the given failure.
PSE tracks the flow of a single value of interest from the point in the program where the failure occurred back to the points in the program where the value may have originated. The algorithm combines a novel dataflow analysis and memory alias analysis in a manner that allows for precise exploration of the program's behavior in polynomial time.
We have applied PSE to the problem of diagnosing potential NULL-dereference errors in a suite of C programs, including several SPEC benchmarks and a large commercial operating system. In most cases, the analysis is able to either validate a pointer dereference, or find precise error traces demonstrating a NULL value for the pointer, in less than a second.

References

[1]
Hiralal Agrawal and Joseph R. Horgan. Dynamic Program Slicing. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, June 1990.]]
[2]
Hiraral Agrawal, Joseph R. Horgan, Saul London, and W. Eric Wong. Fault Localization using Execution Slices and Dataflow Tests. In Proceedings of the IEEE International Symposium on Software Reliability Engineering, October 1995.]]
[3]
Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986.]]
[4]
Thomas Ball, Mayur Naik, and Sriram Rajamani. From Symptom to Cause: Localizing Errors in Counterexample Traces. In Conference Record of the Thirtieth ACM Symposium on Principles of Programming Languages, 2003.]]
[5]
Thomas Ball and Sriram K. Rajamani. Automatically Validating Temporal Safety Properties of Interfaces. In Proceedings of SPIN '01, 8th Annual SPIN Workshop on Model Checking of Software, May 2001.]]
[6]
Peter Bunus and Peter Fritzson. Semi-Automatic Fault Localization and Behavior Verification for Physical System Simulation Models. In Proceedings of the IEEE International Conference on Automated Software Engineering, October 2003.]]
[7]
William R. Bush, Jonathan D. Pincus, and David J. Sielaff. A Static Analyzer for Finding Dynamic Programming Errors. Software - Practice and Experience, 30(7):775--802, 2000.]]
[8]
J. Corbett, M. Dwyer, J. Hatcliff, C. Pasareanu, Robby, S. Laubach, and H. Zheng. Bandera: Extracting Finite-state Models from Java Source Code. In Proceedings of the 22nd International Conference on Software Engineering, 2000.]]
[9]
Microsoft Corporation. Microsoft Online Crash Analysis. http://oca.microsoft.com/en/dcp20.asp.]]
[10]
Manuvir Das. Unification-based pointer analysis with directional assignments. In ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, 2000.]]
[11]
Manuvir Das, Sorin Lerner, and Mark Seigle. ESP: Path-sensitive Program Verification in Polynomial Time. In ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, 2002.]]
[12]
Manuvir Das, Ben Liblit, Manuel Fähndrich, and Jakob Rehof. Estimating the Impact of Scalable Pointer Analysis on Optimization. In 8th International Symposium on Static Analysis, 2001.]]
[13]
Richard A. DeMillo, Hsin Pan, and Eugene H. Spafford. Critical Slicing for Software Fault Localization. In Proceedings of the International Symposium on Software Testing and Analysis, January 1996.]]
[14]
E. W. Dijkstra. A Discipline of programming. Prentice-Hall, 1976.]]
[15]
Nurit Dor, Stephen Adams, Manuvir Das, and Zhe Yang. Software Validation via Scalable Path-Sensitive Value Flow Analysis. In International Symposium on Software Testing and Analysis, 2004. Also available as Microsoft Research Technical Report MSR-TR-2003-58.]]
[16]
Margaret Francel and Spencer Rugaber. Fault Localization using Execution Traces. In Proceedings of the ACM Annual Southeast Regional Conference, 1992.]]
[17]
Seth Hallem, Benjamin Chelf, Yichen Xie, and Dawson Engler. A system and language for building system-specific, static analyses. In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, 2002.]]
[18]
Ben Liblit and Alex Aiken. Building a better backtrace: Techniques for postmortem program analysis. Technical Report UCB/CSD 02/1203, UC Berkeley Computer Science Division, October 2002.]]
[19]
Hsin Pan and Eugene H. Spafford. Toward Automatic Localization of Software Faults. In Proceedings of the Pacific Northwest Software Quality Conference, October 1992.]]
[20]
Brock Pytlik, Manos Renieris, Shriram Krishnamurthi, and Steven P. Reiss. Automated Fault Localization Using Potential Invariants. In Proceedings of the International Workshop on Automated and Algorithmic Debugging, September 2003.]]
[21]
Thomas Reps, Susan Horwitz, and Mooly Sagiv. Precise interprocedural dataflow analysis via graph reachability. In Proc. ACM Symp. on Principles of Programming Languages, pages 49--61. ACM Press, January 1995.]]
[22]
R. Strom and S. Yemini. Typestate: A Programming Language Concept for Enhancing Software Reliability. IEEE Transactions on Software Engineering, 12(1):157--171, 1986.]]
[23]
Robert E. Strom and Daniel M. Yellin. Extending Typestate Checking Using Conditional Liveness Analysis. IEEE Transactions on Software Engineering, May 1993.]]
[24]
Frank Tip. A survey of program slicing techniques. Journal of programming languages, 3:121--189, 1995.]]
[25]
Mark Weiser. Program slicing. In Proceedings of the 5th international conference on Software engineering, pages 439--449. IEEE Press, March 1981.]]

Cited By

View all
  • (2024)Boosting the Performance of Alias-Aware IFDS Analysis with CFL-Based Environment TransformersProceedings of the ACM on Programming Languages10.1145/36898048:OOPSLA2(2633-2661)Online publication date: 8-Oct-2024
  • (2024)Automatically Inspecting Thousands of Static Bug Warnings with Large Language Model: How Far Are We?ACM Transactions on Knowledge Discovery from Data10.1145/365371818:7(1-34)Online publication date: 26-Mar-2024
  • (2024)Boosting the Performance of Multi-Solver IFDS Algorithms with Flow-Sensitivity OptimizationsProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444884(296-307)Online publication date: 2-Mar-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGSOFT '04/FSE-12: Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering
October 2004
282 pages
ISBN:1581138555
DOI:10.1145/1029894
  • cover image ACM SIGSOFT Software Engineering Notes
    ACM SIGSOFT Software Engineering Notes  Volume 29, Issue 6
    November 2004
    275 pages
    ISSN:0163-5948
    DOI:10.1145/1041685
    Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 October 2004

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. alias analysis
  2. postmortem analysis
  3. typestate
  4. value flow

Qualifiers

  • Article

Conference

SIGSOFT04/FSE-12
Sponsor:

Acceptance Rates

Overall Acceptance Rate 17 of 128 submissions, 13%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)16
  • Downloads (Last 6 weeks)1
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Boosting the Performance of Alias-Aware IFDS Analysis with CFL-Based Environment TransformersProceedings of the ACM on Programming Languages10.1145/36898048:OOPSLA2(2633-2661)Online publication date: 8-Oct-2024
  • (2024)Automatically Inspecting Thousands of Static Bug Warnings with Large Language Model: How Far Are We?ACM Transactions on Knowledge Discovery from Data10.1145/365371818:7(1-34)Online publication date: 26-Mar-2024
  • (2024)Boosting the Performance of Multi-Solver IFDS Algorithms with Flow-Sensitivity OptimizationsProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444884(296-307)Online publication date: 2-Mar-2024
  • (2023) Anchor: Fast and Precise Value-flow Analysis for Containers via Memory OrientationACM Transactions on Software Engineering and Methodology10.1145/356580032:3(1-39)Online publication date: 26-Apr-2023
  • (2023)DStream: A Streaming-Based Highly Parallel IFDS FrameworkProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00208(2488-2500)Online publication date: 14-May-2023
  • (2022)BEACON: Directed Grey-Box Fuzzing with Provable Path Pruning2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833751(36-50)Online publication date: May-2022
  • (2021)Optimizing demand‐driven null dereference verification via merging branchesExpert Systems10.1111/exsy.1270739:6Online publication date: 27-May-2021
  • (2021)Scaling Up the IFDS Algorithm with Efficient Disk-Assisted Computing2021 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO51591.2021.9370311(236-247)Online publication date: 27-Feb-2021
  • (2020)Reverse debugging of kernel failures in deployed systemsProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489165(281-292)Online publication date: 15-Jul-2020
  • (2020)Generating Robust Parallel Programs via Model Driven Prediction of Compiler Optimizations for Non-determinismProceedings of the 49th International Conference on Parallel Processing10.1145/3404397.3404464(1-12)Online publication date: 17-Aug-2020
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media