research-article

Error propagation analysis for file systems

Authors:

Cindy Rubio-González,

Haryadi S. Gunawi,

Remzi H. Arpaci-Dusseau,

Andrea C. Arpaci-DusseauAuthors Info & Claims

PLDI '09: Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 270 - 280

https://doi.org/10.1145/1542476.1542506

Published: 15 June 2009 Publication History

Abstract

Unchecked errors are especially pernicious in operating system file management code. Transient or permanent hardware failures are inevitable, and error-management bugs at the file system layer can cause silent, unrecoverable data corruption. We propose an interprocedural static analysis that tracks errors as they propagate through file system code. Our implementation detects overwritten, out-of-scope, and unsaved unchecked errors. Analysis of four widely-used Linux file system implementations (CIFS, ext3, IBM JFS and ReiserFS), a relatively new file system implementation (ext4), and shared virtual file system (VFS) code uncovers 312 error propagation bugs. Our flow- and context-sensitive approach produces more precise results than related techniques while providing better diagnostic information, including possible execution paths that demonstrate each bug found.

References

[1]

M. W. Bigrigg and J. J. Vos. The set-check-use methodology for detecting error propagation failures in I/O routines. In Workshop on Dependability Benchmarking, Washington, DC, June 2002.

[2]

R. E. Bryant. Binary decision diagrams and beyond: enabling technologies for formal verification. In R. L. Rudell, editor, ICCAD, pages 236--243. IEEE Computer Society, 1995.

Digital Library

[3]

D. Callahan. The program summary graph and flow-sensitive interprocedural data flow analysis. In PLDI, pages 47--56, 1988.

Digital Library

[4]

G. Candea, M. Delgado, M. Chen, and A. Fox. Automatic failure-path inference: A generic introspection technique for Internet applications. In Proceedings of the The Third IEEE Workshop on Internet Applications (WIAPP '03), pages 132--141, San Jose, California, June 2003. IEEE.

Digital Library

[5]

A. Dilger. Error propagation bugs in ext4. Personal communication, Nov. 2008.

[6]

D. Evans. LCLint User's Guide. University of Virginia, May 2000.

[7]

C. A. Flanagan and M. Burrows. System and method for dynamically detecting unchecked error condition values in computer programs. United States Patent #6,378,081 B1, Apr. 2002.

[8]

J. B. Goodenough. Structured exception handling. In POPL, pages 204--224, 1975.

Digital Library

[9]

T. Goradia. Dynamic impact analysis: A cost-effective technique to enforce error-propagation. In ISSTA, pages 171--181, 1993.

Digital Library

[10]

A. D. Groce. Problem solved. Personal communication, Jan. 2009.

[11]

H. S. Gunawi, C. Rubio-González, A. C. Arpaci-Dusseau, R. H. Arpaci-Dusseau, and B. Liblit. EIO: Error handling is occasionally correct. In 6th USENIX Conference on File and Storage Technologies (FAST '08), San Jose, California, Feb. 2008.

Digital Library

[12]

P. J. Guo, J. H. Perkins, S. McCamant, and M. D. Ernst. Dynamic inference of abstract types. In L. L. Pollock and M. Pezzè, editors, ISSTA, pages 255--265. ACM, 2006.

Digital Library

[13]

M. Hiller, A. Jhumka, and N. Suri. An approach for analysing the propagation of data errors in software. In DSN, pages 161--172. IEEE Computer Society, 2001.

Digital Library

[14]

M. Hiller, A. Jhumka, and N. Suri. Propane: an environment for examining the propagation of errors in software. In ISSTA, pages 81--85, 2002.

Digital Library

[15]

M. Hiller, A. Jhumka, and N. Suri. Epic: Profiling the propagation and effect of data errors in software. IEEE Trans. Computers, 53(5): 512--530, 2004.

Digital Library

[16]

A. Jhumka, M. Hiller, and N. Suri. Assessing inter-modular error propagation in distributed software. In SRDS, pages 152--161. IEEE Computer Society, 2001.

[17]

A. Johansson and N. Suri. Error propagation profiling of operating systems. In DSN, pages 86--95. IEEE Computer Society, 2005.

Digital Library

[18]

N. Kidd, T. Reps, and A. Lal. WALi: A C++ library for weighted pushdown systems. http://www.cs.wisc.edu/wpis/wpds/download.php, 2008.

[19]

A. Lal, T.W. Reps, and G. Balakrishnan. Extended weighted pushdown systems. In K. Etessami and S. K. Rajamani, editors, CAV, volume 3576 of Lecture Notes in Computer Science, pages 434--448. Springer, 2005.

Digital Library

[20]

A. Lal, N. Kidd, T.W. Reps, and T. Touili. Abstract error projection. In H. R. Nielson and G. Filé, editors, SAS, volume 4634 of Lecture Notes in Computer Science, pages 200--217. Springer, 2007.

Digital Library

[21]

A. Lal, T. Touili, N. Kidd, and T. Reps. Interprocedural analysis of concurrent programs under a context bound. Technical Report 1598, University of Wisconsin--Madison, July 2007.

[22]

J. Lind-Nielsen. BuDDy -- A Binary Decision Diagram Package. http://sourceforge.net/projects/buddy, 2004.

[23]

B. Liskov. A history of CLU. In HOPL Preprints, pages 133--147, 1993.

Digital Library

[24]

G. C. Necula, S. McPeak, S. P. Rahul, and W. Weimer. CIL: Intermediate language and tools for analysis and transformation of C programs. In R. N. Horspool, editor, CC, volume 2304 of Lecture Notes in Computer Science, pages 213--228. Springer, 2002.

Digital Library

[25]

T. W. Reps, S. Schwoon, S. Jha, and D. Melski. Weighted pushdown systems and their application to interprocedural dataflow analysis. Sci.Comput. Program., 58(1--2):206--263, 2005.

Digital Library

[26]

P. Sacramento, B. Cabral, and P. Marques. Unchecked exceptions: Can the programmer be trusted to document exceptions? In Second International Conference on Innovative Views of .NET Technologies, Florianópolis, Brazil, Oct. 2006. Microsoft.

[27]

S. Schwoon. Model-Checking Pushdown Systems. PhD thesis, Technical Univ. of Munich, Munich, Germany, July 2002.

[28]

K. G. Shin and T.-H. Lin. Modeling and measurement of error propagation in a multimodule computing system. IEEE Trans. Computers, 37(9):1053--1066, 1988.

Digital Library

[29]

Sun Microsystems, Inc. Unchecked exceptions -- the controversy. http://java.sun.com/docs/books/tutorial/essential/exceptions/runtime.html, Aug. 2007.

[30]

M. van Dooren and E. Steegmans. Combining the robustness of checked exceptions with the flexibility of unchecked exceptions using anchored exception declarations. In R. Johnson and R. P. Gabriel, editors, OOPSLA, pages 455--471. ACM, 2005.

Digital Library

[31]

M. N. Wegman and F. K. Zadeck. Constant propagation with conditional branches. In POPL, pages 291--299, 1985.

Digital Library

[32]

J. Yang, P. Twohey, D. R. Engler, and M. Musuvathi. Using model checking to find serious file system errors. ACM Trans. Comput. Syst., 24(4):393--423, 2006.

Digital Library

Cited By

Dossche NCoppens BBalzarotti DXu W(2024)Inference of error specifications and bug detection using structural similaritiesProceedings of the 33rd USENIX Conference on Security Symposium10.5555/3698900.3699006(1885-1902)Online publication date: 14-Aug-2024
https://dl.acm.org/doi/10.5555/3698900.3699006
Liu YAdkar MHolzmann GKuenning GLiu PSmolka SSu WZadok EMa XWon Y(2024)MetisProceedings of the 22nd USENIX Conference on File and Storage Technologies10.5555/3650697.3650705(123-140)Online publication date: 27-Feb-2024
https://dl.acm.org/doi/10.5555/3650697.3650705
Stoica BSethi USu YZhou CLu SMace JMusuvathi MNath SWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)If At First You Don’t Succeed, Try, Try, Again...? Insights and LLM-informed Tooling for Detecting Retry Bugs in Software SystemsProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695971(63-78)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695971
Show More Cited By

Index Terms

Error propagation analysis for file systems
1. General and reference
  1. Cross-computing tools and techniques
    1. Reliability
    2. Validation
2. Software and its engineering
  1. Software creation and management
    1. Software development techniques
      1. Error handling and recovery
    2. Software verification and validation
  2. Software organization and properties
    1. Extra-functional properties
      1. Software reliability
    2. Software functional properties
      1. Formal methods

Recommendations

Error propagation analysis for file systems
PLDI '09

Unchecked errors are especially pernicious in operating system file management code. Transient or permanent hardware failures are inevitable, and error-management bugs at the file system layer can cause silent, unrecoverable data corruption. We propose ...
Defective error/pointer interactions in the Linux kernel
ISSTA '11: Proceedings of the 2011 International Symposium on Software Testing and Analysis

Linux run-time errors are represented by integer values referred to as error codes. These values propagate across long function-call chains before being handled. As these error codes propagate, they are often temporarily or permanently encoded into ...
Expect the unexpected: error code mismatches between documentation and the real world
PASTE '10: Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering

Inaccurate documentation can mislead programmers and cause software to fail in unexpected ways. We examine mismatches between documented and actual error codes returned by 42 Linux file-related system calls. We use static program analysis to identify ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '09: Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2009

492 pages

ISBN:9781605583921

DOI:10.1145/1542476

General Chair:
Michael Hind
IBM Research, USA
,
Program Chair:
Amer Diwan
University of Colorado at Boulder, USA

ACM SIGPLAN Notices Volume 44, Issue 6
PLDI '09
June 2009
478 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1543135
Issue’s Table of Contents

Copyright © 2009 ACM.

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: 15 June 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '09

Sponsor:

PLDI '09: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 15 - 21, 2009

Dublin, Ireland

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

89
Total Citations
View Citations
690
Total Downloads

Downloads (Last 12 months)23
Downloads (Last 6 weeks)5

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dossche NCoppens BBalzarotti DXu W(2024)Inference of error specifications and bug detection using structural similaritiesProceedings of the 33rd USENIX Conference on Security Symposium10.5555/3698900.3699006(1885-1902)Online publication date: 14-Aug-2024
https://dl.acm.org/doi/10.5555/3698900.3699006
Liu YAdkar MHolzmann GKuenning GLiu PSmolka SSu WZadok EMa XWon Y(2024)MetisProceedings of the 22nd USENIX Conference on File and Storage Technologies10.5555/3650697.3650705(123-140)Online publication date: 27-Feb-2024
https://dl.acm.org/doi/10.5555/3650697.3650705
Stoica BSethi USu YZhou CLu SMace JMusuvathi MNath SWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)If At First You Don’t Succeed, Try, Try, Again...? Insights and LLM-informed Tooling for Detecting Retry Bugs in Software SystemsProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695971(63-78)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695971
Liu DYan YFan HFeng Y(2024)Mining Fix Patterns for System Interaction BugsProceedings of the 15th Asia-Pacific Symposium on Internetware10.1145/3671016.3671398(367-376)Online publication date: 24-Jul-2024
https://dl.acm.org/doi/10.1145/3671016.3671398
Liu HJia ZLi SLei YYu YJiang YMao XLiao X(2024)Cut to the Chase: An Error-Oriented Approach to Detect Error-Handling BugsProceedings of the ACM on Software Engineering10.1145/36607871:FSE(1796-1818)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660787
Mehta MKrynski SGualandi HThakur MVitek J(2023)Reusing Just-in-Time Compiled CodeProceedings of the ACM on Programming Languages10.1145/36228397:OOPSLA2(1176-1197)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622839
Liu JZhu FHe F(2023)Automated Ambiguity Detection in Layout-Sensitive GrammarsProceedings of the ACM on Programming Languages10.1145/36228387:OOPSLA2(1150-1175)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622838
Porncharoenwase SPombrio JTorlak E(2023)A Pretty Expressive PrinterProceedings of the ACM on Programming Languages10.1145/36228377:OOPSLA2(1122-1149)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622837
Tang WHillerström DMcKinna JSteuwer MDardha OFu RLindley S(2023)Structural Subtyping as Parametric PolymorphismProceedings of the ACM on Programming Languages10.1145/36228367:OOPSLA2(1093-1121)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622836
Murali APeña LJhala RMadhusudan P(2023)Complete First-Order Reasoning for Properties of Functional ProgramsProceedings of the ACM on Programming Languages10.1145/36228357:OOPSLA2(1063-1092)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622835
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten