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

Article

Lightweight control-flow instrumentation and postmortem analysis in support of debugging

Authors:

Ben LiblitAuthors Info & Claims

ASE '13: Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering

Pages 378 - 388

https://doi.org/10.1109/ASE.2013.6693096

Published: 11 November 2013 Publication History

Publisher Site Get Access

Abstract

Debugging is difficult and costly. As a human programmer looks for a bug, it would be helpful to see a complete trace of events leading to the point of failure. Unfortunately, full tracing is simply too slow to use in deployment, and may even be impractical during testing.

We aid post-deployment debugging by giving programmers additional information about program activity shortly before failure. We use latent information in post-failure memory dumps, augmented by low-overhead, tunable run-time tracing. Our results with a realistically-tuned tracing scheme show low enough overhead (0-5%) to be used in production runs. We demonstrate several potential uses of this enhanced information, including a novel postmortem static slice restriction technique and a reduced view of potentially-executed code. Experimental evaluation shows our approach to be very effective, such as shrinking stack-sensitive interprocedural static slices by 49-78% in larger applications.

References

[1]

H. Agrawal and J. R. Horgan, "Dynamic program slicing," in Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, ser. PLDI '90. New York, NY, USA: ACM, 1990, pp. 246-256.

Digital Library

[2]

H. Agrawal, R. A. DeMillo, and E. H. Spafford, "Dynamic slicing in the presence of unconstrained pointers," in Proceedings of the symposium on Testing, analysis, and verification, ser. TAV4. New York, NY, USA: ACM, 1991, pp. 60-73.

Digital Library

[3]

G. Ammons, T. Ball, and J. R. Larus, "Exploiting hardware performance counters with flow and context sensitive profiling," in Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, ser. PLDI '97. New York, NY, USA: ACM, 1997, pp. 85-96.

Digital Library

[4]

P. Anderson, T. Reps, and T. Teitelbaum, "Design and implementation of a fine-grained software inspection tool," IEEE Trans. Softw. Eng., vol. 29, no. 8, pp. 721-733, Aug. 2003.

Digital Library

[5]

T. Apiwattanapong and M. J. Harrold, "Selective path profiling," in Proceedings of the 2002 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, ser. PASTE '02. New York, NY, USA: ACM, 2002, pp. 35-42.

Digital Library

[6]

P. Arumuga Nainar and B. Liblit, "Adaptive bug isolation," in ICSE (1), J. Kramer, J. Bishop, P. T. Devanbu, and S. Uchitel, Eds. ACM, 2010, pp. 255-264.

Digital Library

[7]

T. Ball and J. R. Larus, "Efficient path profiling," in Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, ser. MICRO 29. Washington, DC, USA: IEEE Computer Society, 1996, pp. 46-57.

Digital Library

[8]

D. Binkley, S. Danicic, T. Gyimóthy, M. Harman, A. Kiss, and B. Korel, "A formalisation of the relationship between forms of program slicing," Sci. Comput. Program., vol. 62, no. 3, pp. 228-252, Oct. 2006.

Digital Library

[9]

D. Binkley, N. Gold, and M. Harman, "An empirical study of static program slice size," ACM Trans. Softw. Eng. Methodol., vol. 16, no. 2, Apr. 2007.

Digital Library

[10]

M. D. Bond and K. S. McKinley, "Probabilistic calling context," in Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems and applications, ser. OOPSLA '07. New York, NY, USA: ACM, 2007, pp. 97-112.

Digital Library

[11]

J. Bowring, A. Orso, and M. J. Harrold, "Monitoring deployed software using software tomography," in Proceedings of the 2002 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, ser. PASTE '02. New York, NY, USA: ACM, 2002, pp. 2-9.

Digital Library

[12]

J. Clause and A. Orso, "A technique for enabling and supporting debugging of field failures," in Proceedings of the 29th international conference on Software Engineering, ser. ICSE '07. Washington, DC, USA: IEEE Computer Society, 2007, pp. 261-270.

Digital Library

[13]

O. Crameri, R. Bianchini, and W. Zwaenepoel, "Striking a new balance between program instrumentation and debugging time," in Proceedings of the sixth conference on Computer systems, ser. EuroSys '11. New York, NY, USA: ACM, 2011, pp. 199-214.

Digital Library

[14]

B. Gauf and E. Dustin, "The case for automated software testing," Journal of Software Technology, vol. 10, no. 3, pp. 29-34, Oct. 2007.

[15]

R. Gupta, M. L. Soffa, and J. Howard, "Hybrid slicing: integrating dynamic information with static analysis," ACM Trans. Softw. Eng. Methodol., vol. 6, no. 4, pp. 370-397, Oct. 1997.

Digital Library

[16]

B. Hailpern and P. Santhanam, "Software debugging, testing, and verification," IBM Syst. J., vol. 41, no. 1, pp. 4-12, Jan. 2002.

Digital Library

[17]

S. Horwitz, T. Reps, and D. Binkley, "Interprocedural slicing using dependence graphs," in Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, ser. PLDI '88. New York, NY, USA: ACM, 1988, pp. 35-46.

Digital Library

[18]

S. Horwitz, B. Liblit, and M. Polishchuk, "Better debugging via output tracing and callstack-sensitive slicing," IEEE Trans. Softw. Eng., vol. 36, no. 1, pp. 7-19, Jan. 2010.

Digital Library

[19]

C. Jaramillo, R. Gupta, and M. L. Soffa, "FULLDOC: A full reporting debugger for optimized code," in Proceedings of the 7th International Symposium on Static Analysis, ser. SAS '00. London, UK, UK: Springer-Verlag, 2000, pp. 240-259.

Digital Library

[20]

W. Jin and A. Orso, "Bugredux: reproducing field failures for in-house debugging," in Proceedings of the 2012 International Conference on Software Engineering, ser. ICSE 2012. Piscataway, NJ, USA: IEEE Press, 2012, pp. 474-484.

Digital Library

[21]

M. Kamkar, P. Fritzson, and N. Shahmehri, "Three approaches to interprocedural dynamic slicing," Microprocessing and Microprogramming, vol. 38, no. 1-5, pp. 625-636, 1993.

Digital Library

[22]

B. Korel and J. Laski, "Dynamic program slicing," Inf. Process. Lett., vol. 29, no. 3, pp. 155-163, Oct. 1988.

Digital Library

[23]

B. Korel and J. Laski, "Dynamic slicing of computer programs," J. Syst. Softw., vol. 13, no. 3, pp. 187-195, Dec. 1990.

Digital Library

[24]

J. Krinke, "Context-sensitivity matters, but context does not," in Proceedings of the Source Code Analysis and Manipulation, Fourth IEEE International Workshop, ser. SCAM '04. Washington, DC, USA: IEEE Computer Society, 2004, pp. 29-35.

Digital Library

[25]

C. Lattner and V. Adve, "LLVM: A compilation framework for lifelong program analysis & transformation," in Proceedings of the 2004 International Symposium on Code Generation and Optimization (CGO'04), Palo Alto, California, Mar. 2004.

Digital Library

[26]

Y. Lei, X. Mao, Z. Dai, and C. Wang, "Effective statistical fault localization using program slices," in Proceedings of the 2012 IEEE 36th Annual Computer Software and Applications Conference, ser. COMPSAC '12. Washington, DC, USA: IEEE Computer Society, 2012, pp. 1-10.

Digital Library

[27]

D. Melski and T. W. Reps, "Interprocedural path profiling," in Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, ser. CC '99. London, UK, UK: Springer-Verlag, 1999, pp. 47-62.

Digital Library

[28]

A. Mulhern and B. Liblit, "Effective slicing: A generalization of full and relevant slicing," University of Wisconsin-Madison, Tech. Rep. 1639, Jun. 2008.

[29]

A. Nishimatsu, M. Jihira, S. Kusumoto, and K. Inoue, "Call-mark slicing: an efficient and economical way of reducing slice," in Proceedings of the 21st international conference on Software engineering, ser. ICSE '99. New York, NY, USA: ACM, 1999, pp. 422-431.

Digital Library

[30]

A. Orso, D. Liang, M. J. Harrold, and R. Lipton, "Gamma system: continuous evolution of software after deployment," in Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, ser. ISSTA '02. New York, NY, USA: ACM, 2002, pp. 65-69.

Digital Library

[31]

K. J. Ottenstein and L. M. Ottenstein, "The program dependence graph in a software development environment," in Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, ser. SDE 1. New York, NY, USA: ACM, 1984, pp. 177-184.

Digital Library

[32]

J. Rößler, A. Zeller, G. Fraser, C. Zamfir, and G. Candea, "Reconstructing core dumps," in ICST '13: Proceedings of the Sixth IEEE International Conference on Software Testing, Verification and Validation, Mar. 2013.

Digital Library

[33]

G. Rothermel, S. Elbaum, A. Kinneer, and H. Do. (2006, Sep.) Software-artifact infrastructure repository. [Online]. Available: http://sir.unl.edu/portal/

[34]

W. N. Sumner, Y. Zheng, D. Weeratunge, and X. Zhang, "Precise calling context encoding," in Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering - Volume 1, ser. ICSE '10. New York, NY, USA: ACM, 2010, pp. 525-534.

Digital Library

[35]

T. Takada, F. Ohata, and K. Inoue, "Dependence-cache slicing: A program slicing method using lightweight dynamic information," in Proceedings of the 10th International Workshop on Program Comprehension, ser. IWPC '02. Washington, DC, USA: IEEE Computer Society, 2002, pp. 169.

Digital Library

[36]

G. Tassey, "The economic impacts of inadequate infrastructure for software testing," National Institute of Standards and Technology, RTI Project, vol. 7007, no. 011, 2002.

[37]

C. M. Tice, "Non-transparent debugging of optimized code," Ph.D. dissertation, EECS Department, University of California, Berkeley, Nov 1999. [Online]. Available: http://www.eecs.berkeley.edu/Pubs/TechRpts/1999/6232.html

Digital Library

[38]

K. Vaswani, A. V. Nori, and T. M. Chilimbi, "Preferential path profiling: compactly numbering interesting paths," in Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, ser. POPL '07. New York, NY, USA: ACM, 2007, pp. 351-362.

Digital Library

[39]

G. A. Venkatesh, "The semantic approach to program slicing," in Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, ser. PLDI '91. New York, NY, USA: ACM, 1991, pp. 107-119.

Digital Library

[40]

D. Weeratunge, X. Zhang, and S. Jagannathan, "Analyzing multicore dumps to facilitate concurrency bug reproduction," in Proceedings of the fifteenth edition of ASPLOS on Architectural support for programming languages and operating systems, ser. ASPLOS XV. New York, NY, USA: ACM, 2010, pp. 155-166.

Digital Library

[41]

M. Weiser, "Program slicing," IEEE Trans. Softw. Eng., vol. 10, no. 4, pp. 352-357, Jul. 1984.

Digital Library

[42]

D. Yuan, H. Mai, W. Xiong, L. Tan, Y. Zhou, and S. Pasupathy, "Sherlog: error diagnosis by connecting clues from run-time logs," in Proceedings of the fifteenth edition of ASPLOS on Architectural support for programming languages and operating systems, ser. ASPLOS XV. New York, NY, USA: ACM, 2010, pp. 143-154.

Digital Library

[43]

D. Yuan, J. Zheng, S. Park, Y. Zhou, and S. Savage, "Improving software diagnosability via log enhancement," in Proceedings of the sixteenth international conference on Architectural support for programming languages and operating systems, ser. ASPLOS XVI. New York, NY, USA: ACM, 2011, pp. 3-14.

Digital Library

[44]

C. Zamfir and G. Candea, "Execution synthesis: a technique for automated software debugging," in Proceedings of the 5th European conference on Computer systems, ser. EuroSys '10. New York, NY, USA: ACM, 2010, pp. 321-334.

Digital Library

[45]

X. Zhang and R. Gupta, "Cost effective dynamic program slicing," in Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, ser. PLDI '04. New York, NY, USA: ACM, 2004, pp. 94-106.

Digital Library

Cited By

Kim TKim COzen AFei FTu ZZhang XDeng XTian DXu DCapkun SRoesner F(2020)From control model to programProceedings of the 29th USENIX Conference on Security Symposium10.5555/3489212.3489264(913-930)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.5555/3489212.3489264
Guo WMu DXing XDu MSong DHeninger NTraynor P(2019)DEEPVSAProceedings of the 28th USENIX Conference on Security Symposium10.5555/3361338.3361462(1787-1804)Online publication date: 14-Aug-2019
https://dl.acm.org/doi/10.5555/3361338.3361462
Ohmann PBrooks AD'Antoni LLiblit B(2017)Control-flow recovery from partial failure reportsACM SIGPLAN Notices10.1145/3140587.306236852:6(390-405)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062368
Show More Cited By

Recommendations

Lightweight control-flow instrumentation and postmortem analysis in support of debugging

Debugging is difficult and costly. As a programmer looks for a bug, it would be helpful to see a complete trace of events leading to the point of failure. Unfortunately, full tracing is simply too slow to use after deployment, and may even be ...
Debugging with control-flow breakpoints
AOSD '07: Proceedings of the 6th international conference on Aspect-oriented software development

Modern source-level debuggers support dynamic breakpoints that are guarded by conditions based on program state. Such breakpoints address situations where a static breakpoint is not sufficiently precise to characterise a point of interest in program ...
Efficient statistical debugging via hierarchical instrumentation
ISSTA 2014: Proceedings of the 2014 International Symposium on Software Testing and Analysis

Debugging is known to be a notoriously painstaking and time-consuming task. As one major family of automated debugging, statistical debugging approaches have been well investigated over the past decade to assist in debugging. All these approaches ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASE '13: Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering

November 2013

765 pages

ISBN:9781479902156

General Chair:
Ewen Denney
SGT, NASA, Ames Research Center, Moffett Field
,
Program Chairs:
Tevfik Bultan
University of California, Santa Barbara
,
Andreas Zeller
Saarland University, Saarbrücken, Germany

Sponsors

NASA: National Aeronatics and Space Administration
SIGAI: ACM Special Interest Group on Artificial Intelligence
IEEE: IEEE Computer Society Technical Committee on Design Automation
SIGSOFT: ACM Special Interest Group on Software Engineering
Microsoft: Microsoft

Publisher

IEEE Press

Publication History

Published: 11 November 2013

Check for updates

Qualifiers

Article

Conference

ASE '13

Sponsor:

NASA
SIGAI
IEEE
SIGSOFT
Microsoft

ASE '13: Automated Software Engineering

November 11 - 15, 2013

CA, Silicon Valley, USA

Acceptance Rates

Overall Acceptance Rate 82 of 337 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
34
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kim TKim COzen AFei FTu ZZhang XDeng XTian DXu DCapkun SRoesner F(2020)From control model to programProceedings of the 29th USENIX Conference on Security Symposium10.5555/3489212.3489264(913-930)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.5555/3489212.3489264
Guo WMu DXing XDu MSong DHeninger NTraynor P(2019)DEEPVSAProceedings of the 28th USENIX Conference on Security Symposium10.5555/3361338.3361462(1787-1804)Online publication date: 14-Aug-2019
https://dl.acm.org/doi/10.5555/3361338.3361462
Ohmann PBrooks AD'Antoni LLiblit B(2017)Control-flow recovery from partial failure reportsACM SIGPLAN Notices10.1145/3140587.306236852:6(390-405)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062368
Bianchi FPezzè MTerragni VBodden ESchäfer WDeursen AZisman A(2017)Reproducing concurrency failures from crash stacksProceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering10.1145/3106237.3106292(705-716)Online publication date: 21-Aug-2017
https://dl.acm.org/doi/10.1145/3106237.3106292
Ohmann PBrooks AD'Antoni LLiblit BCohen AVechev M(2017)Control-flow recovery from partial failure reportsProceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3062341.3062368(390-405)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3062341.3062368
Ohmann PBrown DNeelakandan NLinderoth JLiblit BLo DApel SKhurshid S(2016)Optimizing customized program coverageProceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering10.1145/2970276.2970351(27-38)Online publication date: 25-Aug-2016
https://dl.acm.org/doi/10.1145/2970276.2970351
Yang CWu SChan W(2016)Hierarchical Program PathsACM Transactions on Software Engineering and Methodology10.1145/296309425:3(1-44)Online publication date: 22-Aug-2016
https://dl.acm.org/doi/10.1145/2963094
Wu RXiao XCheung SZhang HZhang C(2016)Casper: an efficient approach to call trace collectionACM SIGPLAN Notices10.1145/2914770.283761951:1(678-690)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2914770.2837619
Wu RXiao XCheung SZhang HZhang CBodik RMajumdar R(2016)Casper: an efficient approach to call trace collectionProceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages10.1145/2837614.2837619(678-690)Online publication date: 11-Jan-2016
https://dl.acm.org/doi/10.1145/2837614.2837619
Zhu JHe PFu QZhang HLyu MZhang DBertolino ACanfora GElbaum S(2015)Learning to logProceedings of the 37th International Conference on Software Engineering - Volume 110.5555/2818754.2818807(415-425)Online publication date: 16-May-2015
https://dl.acm.org/doi/10.5555/2818754.2818807
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