More Web Proxy on the site http://driver.im/

research-article

Partial replay of long-running applications

Authors:

Armando Solar-Lezama,

Samuel MaddenAuthors Info & Claims

ESEC/FSE '11: Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering

Pages 135 - 145

https://doi.org/10.1145/2025113.2025135

Published: 09 September 2011 Publication History

Abstract

Bugs in deployed software can be extremely difficult to track down. Invasive logging techniques, such as logging all non-deterministic inputs, can incur substantial runtime overheads. This paper shows how symbolic analysis can be used to re-create path equivalent executions for very long running programs such as databases and web servers. The goal is to help developers debug such long-running programs by allowing them to walk through an execution of the last few requests or transactions leading up to an error. The challenge is to provide this functionality without the high runtime overheads associated with traditional replay techniques based on input logging or memory snapshots. Our approach achieves this by recording a small amount of information about program execution, such as the direction of branches taken, and then using symbolic analysis to reconstruct the execution of the last few inputs processed by the application, as well as the state of memory before these inputs were executed.

We implemented our technique in a new tool called bbr. In this paper, we show that it can be used to replay bugs in long-running single-threaded programs starting from the middle of an execution. We show that bbr incurs low recording overhead (avg. of 10%) during program execution, which is much less than existing replay schemes. We also show that it can reproduce real bugs from web servers, database systems, and other common utilities.

References

[1]

http://code.google.com/p/memcached/issues/detail?id=21.

[2]

http://www.uclibc.org.

[3]

http://research.microsoft.com/en-us/um/redmond/projects/z3/.

[4]

http://www.tpcc.org.

[5]

http://www.sqlite.org/src/info/eb5548a849.

[6]

http://www.sqlite.org/src/info/b73fb0bd64.

[7]

http://www.sqlite.org/src/info/360c6073e197.

[8]

http://code.google.com/p/memcached/issues/detail?id=15.

[9]

CVE-2005-1279.

[10]

CVE-2005-1278.

[11]

CVE-2005-1280.

[12]

CVE-2003-0899.

[13]

CVE-2001-0820.

[14]

CVE-2002-1904.

[15]

G. Altekar and I. Stoica. Odr: output-deterministic replay for multicore debugging. In SOSP, pages 193--206, 2009.

Digital Library

[16]

T. Ball, R. Majumdar, T. D. Millstein, and S. K. Rajamani. Automatic predicate abstraction of c programs. In PLDI, pages 203--213, 2001.

Digital Library

[17]

S. Bhansali, W.-K. Chen, S. de Jong, A. Edwards, R. Murray, M. Drinić, D. Mihočka, and J. Chau. Framework for instruction-level tracing and analysis of program executions. In Proceedings of the 2nd international conference on Virtual execution environments, VEE '06, pages 154--163, 2006.

Digital Library

[18]

C. Cadar, D. Dunbar, and D. R. Engler. Klee: Unassisted and automatic generation of high-coverage tests for complex systems programs. In OSDI, pages 209--224, 2008.

Digital Library

[19]

M. Castro, M. Costa, and J.-P. Martin. Better bug reporting with better privacy. In ASPLOS, pages 319--328, 2008.

Digital Library

[20]

B. Elkarablieh, P. Godefroid, and M. Y. Levin. Precise pointer reasoning for dynamic test generation. In ISSTA, pages 129--140, 2009.

Digital Library

[21]

D. R. Engler and K. Ashcraft. Racerx: effective, static detection of race conditions and deadlocks. In SOSP, pages 237--252, 2003.

Digital Library

[22]

D. Geels, G. Altekar, S. Shenker, and I. Stoica. Replay debugging for distributed applications. In USENIX Annual Technical Conference, pages 289--300, 2006.

Digital Library

[23]

P. Godefroid, M. Y. Levin, and D. A. Molnar. Automated whitebox fuzz testing. In NDSS, 2008.

[24]

Z. Guo, X. Wang, J. Tang, X. Liu, Z. Xu, M. Wu, M. F. Kaashoek, and Z. Zhang. R2: An application-level kernel for record and replay. In OSDI, pages 193--208, 2008.

Digital Library

[25]

J. Huang, P. Liu, and C. Zhang. Leap: lightweight deterministic multi-processor replay of concurrent java programs. In SIGSOFT FSE, pages 207--216, 2010.

Digital Library

[26]

S. Khurshid, C. S. Pasareanu, and W. Visser. Generalized symbolic execution for model checking and testing. In TACAS, pages 553--568, 2003.

Digital Library

[27]

S. T. King, G. W. Dunlap, and P. M. Chen. Debugging operating systems with time-traveling virtual machines. In USENIX Annual Technical Conference, pages 1--15, 2005.

Digital Library

[28]

V. Kiriansky, D. Bruening, and S. P. Amarasinghe. Secure execution via program shepherding. In USENIX Security Symposium, pages 191--206, 2002.

Digital Library

[29]

R. Manevich, M. Sridharan, S. Adams, M. Das, and Z. Yang. Pse: explaining program failures via postmortem static analysis. In SIGSOFT FSE, pages 63--72, 2004.

Digital Library

[30]

R. H. B. Netzer and M. H. Weaver. Optimal tracing and incremental reexecution for debugging long-running programs. In PLDI, pages 313--325, 1994.

Digital Library

[31]

S. Park, Y. Zhou, W. Xiong, Z. Yin, R. Kaushik, K. H. Lee, and S. Lu. Pres: probabilistic replay with execution sketching on multiprocessors. In SOSP, pages 177--192, 2009.

Digital Library

[32]

K. Sen, D. Marinov, and G. Agha. Cute: a concolic unit testing engine for c. In ESEC/SIGSOFT FSE, pages 263--272, 2005.

Digital Library

[33]

S. M. Srinivasan, S. Kandula, C. R. Andrews, and Y. Zhou. Flashback: A lightweight extension for rollback and deterministic replay for software debugging. In USENIX Annual Technical Conference, pages 29--44, 2004.

Digital Library

[34]

N. Tillmann and J. de Halleux. Pex-white box test generation for .net. In TAP, pages 134--153, 2008.

Digital Library

[35]

D. Vanoverberghe, N. Tillmann, and F. Piessens. Test input generation for programs with pointers. In TACAS, pages 277--291, 2009.

Digital Library

[36]

W. Visser, C. S. Pasareanu, and S. Khurshid. Test input generation with java pathfinder. In ISSTA, pages 97--107, 2004.

Digital Library

[37]

M. Wu, F. Long, X. Wang, Z. Xu, H. Lin, X. Liu, Z. Guo, H. Guo, L. Zhou, and Z. Zhang. Language-based replay via data flow cut. In FSE-18, 2010.

Digital Library

[38]

J. Yang, T. Chen, M. Wu, Z. Xu, X. Liu, H. Lin, M. Yang, F. Long, L. Zhang, and L. Zhou. Modist: Transparent model checking of unmodified distributed systems. In NSDI, pages 213--228, 2009.

Digital Library

[39]

J. Yang, C. Sar, P. Twohey, C. Cadar, and D. R. Engler. Automatically generating malicious disks using symbolic execution. In IEEE Symposium on Security and Privacy, pages 243--257, 2006.

Digital Library

[40]

C. Zamfir and G. Candea. Execution synthesis: a technique for automated software debugging. In EuroSys, pages 321--334, 2010.

Digital Library

Cited By

Pobee EChan WDumas MPfahl DApel SRusso A(2019)AggrePlay: efficient record and replay of multi-threaded programsProceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3338906.3338959(567-577)Online publication date: 12-Aug-2019
https://dl.acm.org/doi/10.1145/3338906.3338959
Pobee EMei XChan WZimmermann TLawall JMarinov D(2019)Efficient transaction-based deterministic replay for multi-threaded programsProceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2019.00076(760-771)Online publication date: 10-Nov-2019
https://dl.acm.org/doi/10.1109/ASE.2019.00076
Wang CCheung ABodik R(2018)Speeding up symbolic reasoning for relational queriesProceedings of the ACM on Programming Languages10.1145/32765272:OOPSLA(1-25)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276527
Show More Cited By

Index Terms

Partial replay of long-running applications
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

On the existence of probe effect in multi-threaded embedded programs
EMSOFT '14: Proceedings of the 14th International Conference on Embedded Software

Software instrumentation has been a convenient and portable approach for dynamic analysis, debugging, or profiling of program execution. Unfortunately, instrumentation may change the temporal behavior of multi-threaded program execution and result in ...
Running symbolic execution forever
ISSTA 2020: Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis

When symbolic execution is used to analyse real-world applications, it often consumes all available memory in a relatively short amount of time, sometimes making it impossible to analyse an application for an extended period. In this paper, we present a ...
Runtime exception detection in Java programs using symbolic execution

Most of the runtime failures of a software system can be revealed during test execution only, which has a very high cost. In Java programs, runtime failures are manifested as unhandled runtime exceptions.

In this paper we present an approach and tool ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ESEC/FSE '11: Proceedings of the 19th ACM SIGSOFT symposium and the 13th European conference on Foundations of software engineering

September 2011

548 pages

ISBN:9781450304436

DOI:10.1145/2025113

General Chair:
Tibor Gyimóthy
University of Szeged, Hungary
,
Program Chair:
Andreas Zeller
Saarland University, Germany

Copyright © 2011 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

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 September 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ESEC/FSE'11

Sponsor:

SIGSOFT

ESEC/FSE'11: Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering

September 5 - 9, 2011

Szeged, Hungary

Acceptance Rates

Overall Acceptance Rate 17 of 128 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
339
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)3

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pobee EChan WDumas MPfahl DApel SRusso A(2019)AggrePlay: efficient record and replay of multi-threaded programsProceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3338906.3338959(567-577)Online publication date: 12-Aug-2019
https://dl.acm.org/doi/10.1145/3338906.3338959
Pobee EMei XChan WZimmermann TLawall JMarinov D(2019)Efficient transaction-based deterministic replay for multi-threaded programsProceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE.2019.00076(760-771)Online publication date: 10-Nov-2019
https://dl.acm.org/doi/10.1109/ASE.2019.00076
Wang CCheung ABodik R(2018)Speeding up symbolic reasoning for relational queriesProceedings of the ACM on Programming Languages10.1145/32765272:OOPSLA(1-25)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276527
Singh RSolar-Lezama APiskac RTalupur M(2016)SwapperProceedings of the 16th Conference on Formal Methods in Computer-Aided Design10.5555/3077629.3077661(185-192)Online publication date: 3-Oct-2016
https://dl.acm.org/doi/10.5555/3077629.3077661
Sambasivan RShafer IMace JSigelman BFonseca RGanger G(2016)Principled workflow-centric tracing of distributed systemsProceedings of the Seventh ACM Symposium on Cloud Computing10.1145/2987550.2987568(401-414)Online publication date: 5-Oct-2016
https://dl.acm.org/doi/10.1145/2987550.2987568
Wang PNguyen HGu XLu S(2016)RDE: Replay DEbugging for Diagnosing Production Site Failures2016 IEEE 35th Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS.2016.050(327-336)Online publication date: Sep-2016
https://doi.org/10.1109/SRDS.2016.050
Singh RSolar-Lezama A(2016)SWAPPER: A framework for automatic generation of formula simplifiers based on conditional rewrite rules2016 Formal Methods in Computer-Aided Design (FMCAD)10.1109/FMCAD.2016.7886678(185-192)Online publication date: Oct-2016
https://doi.org/10.1109/FMCAD.2016.7886678
Inala JSingh RSolar-Lezama A(2016)Synthesis of Domain Specific CNF Encoders for Bit-Vector SolversTheory and Applications of Satisfiability Testing – SAT 201610.1007/978-3-319-40970-2_19(302-320)Online publication date: 11-Jun-2016
https://doi.org/10.1007/978-3-319-40970-2_19
Raman RVenkatasubramanian SAchuthan KNedungadi P(2015)Computer Science (CS) Education in Indian SchoolsACM Transactions on Computing Education10.1145/271632515:2(1-36)Online publication date: 5-May-2015
https://dl.acm.org/doi/10.1145/2716325
Wang ZZhou KZhao G(2015)Lightweight Order-Based Deterministic Replay of Java Multithread Program2015 2nd International Symposium on Dependable Computing and Internet of Things (DCIT)10.1109/DCIT.2015.7(50-58)Online publication date: Nov-2015
https://doi.org/10.1109/DCIT.2015.7
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.

Media

Figures

Other

Tables

View Table of Contents