research-article

Semantics-aware trace analysis

Authors:

Kevin J. Hoffman,

Patrick Eugster,

Suresh JagannathanAuthors Info & Claims

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

Pages 453 - 464

https://doi.org/10.1145/1542476.1542527

Published: 15 June 2009 Publication History

Abstract

As computer systems continue to become more powerful and complex, so do programs. High-level abstractions introduced to deal with complexity in large programs, while simplifying human reasoning, can often obfuscate salient program properties gleaned from automated source-level analysis through subtle (often non-local) interactions. Consequently, understanding the effects of program changes and whether these changes violate intended protocols become difficult to infer. Refactorings, and feature additions, modifications, or removals can introduce hard-to-catch bugs that often go undetected until many revisions later.

To address these issues, this paper presents a novel dynamic program analysis that builds a semantic view of program executions. These views reflect program abstractions and aspects; however, views are not simply projections of execution traces, but are linked to each other to capture semantic interactions among abstractions at different levels of granularity in a scalable manner.

We describe our approach in the context of Java and demonstrate its utility to improve regression analysis. We first formalize a subset of Java and a grammar for traces generated at program execution. We then introduce several types of views used to analyze regression bugs along with a novel, scalable technique for semantic differencing of traces from different versions of the same program. Benchmark results on large open-source Java programs demonstrate that semantic-aware trace differencing can identify precise and useful details about the underlying cause for a regression, even in programs that use reflection, multithreading, or dynamic code generation, features that typically confound other analysis techniques.

References

[1]

H. Agrawal and J.R. Horgan. Dynamic Program Slicing. In PLDI-90, pages 246--256, 1990.

Digital Library

[2]

T. Apiwattanapong, A. Orso, and M.J. Harrold. JDiff: A Differencing Technique and Tool for Object-Oriented Programs. ASE-07, 14(1):3--36, 2007.

Digital Library

[3]

L. Bergroth, H. Hakonen, and T. Raita. A Survey of Longest Common Subsequence Algorithms. In SPIRE-00, page 39, 2000.

Digital Library

[4]

C. Csallner and Y. Smaragdakis. DSD-Crasher: A Hybrid Analysis Tool for Bug Finding. In ISSTA-06, pages 245--254, 2006.

Digital Library

[5]

Valentin Dallmeier and Thomas Zimmermann. Extraction of Bug Localization Benchmarks from History. In ASE, pages 433--436, 2007.

Digital Library

[6]

M. Ernst, J. Cockrell, W. Griswold, and D. Notkin. Dynamically Discovering Likely Program Invariants to Support Program Evolution. TSE, 27(2):1--25, 2001.

Digital Library

[7]

Matthew Flatt, Shriram Krishnamurthi, and Matthias Felleisen. Classes and Mixins. In Proceedings of the 25th ACM SIGPLAN SIGACT symposium on Principles of Programming Languages, pages 171--183. ACM Press, 1998.

Digital Library

[8]

Liang Guo, Abhik Roychoudhury, and Tao Wang. Accurately Choosing Execution Runs for Software Fault Localization. In CC, pages 80--95, 2006.

Digital Library

[9]

D. S. Hirschberg. A Linear Space Algorithm for Computing Maximal Common Subsequences. CACM, 18(6):341--343, 1975.

Digital Library

[10]

Kevin Hoffman, Patrick Eugster, and Suresh Jagannathan. RPrism: Efficient Regression Analysis Using View-Based Trace Differencing. Technical Report dynt-200811-1, Purdue University, 2008.

[11]

Atsushi Igarashi, Benjamin C. Pierce, and Philip Wadler. Featherweight Java: A Minimal Core Calculus for Java and GJ. ACM TOPLAS, 23(3):396--450, May 2001.

Digital Library

[12]

G. Kiczales, J. Lamping, A. Menhdhekar, C. Maeda, C. Lopes, J.-M. Loingtier, and J. Irwin. Aspect-Oriented Programming. In ECOOP-97, pages 220--242, 1997.

[13]

Zhenmin Li, Lin Tan, Xuanhui Wang, Shan Lu, Yuanyuan Zhou, and Chengxiang Zhai. Have Things Changed Now?: An Empirical Study of Bug Characteristics in Modern Open Source Software. In ASID, pages 25--33, 2006.

Digital Library

[14]

Ben Liblit, Alex Aiken, Alice X. Zheng, and Michael I. Jordan. Bug Isolation via Remote Program Sampling. In PLDI--03, pages 141--154, 2003.

Digital Library

[15]

G. Pothier, E. Tanter, and J. Piquer. Scalable Omniscient Debugging. In OOPSLA-07, pages 535--552, 2007.

Digital Library

[16]

X. Ren, F. Shah, F. Tip, B. Ryder, and O. Chesley. Chianti: A Tool for Change Impact Analysis of Java Programs. In OOPSLA-04, pages 432--448, 2004.

Digital Library

[17]

M. Stoerzer, B. Ryder, X. Ren, and F. Tip. Finding Failure--Inducing Changes in Java Programs Using Change Classification. In ESECFSE--14, pages 57--68, 2006.

Digital Library

[18]

F. Tip. A Survey of Program Slicing Techniques. Journal of programming languages, 3:121--189, 1995.

[19]

G. A. Venkatesh. Experimental results from dynamic slicing of C programs. ACM Transactions on Programming Languages and Systems, 17(2):197--216, 1995.

Digital Library

[20]

Bin Xin, William N. Sumner, and Xiangyu Zhang. Efficient Program Execution Indexing. In PLDI-08, pages 238--248, 2008.

Digital Library

[21]

Andreas Zeller. Isolating Cause-Effect Chains from Computer Programs. In FSE-10, pages 1--10, 2002.

Digital Library

[22]

Andreas Zeller and Ralf Hildebrandt. Simplifying and Isolating Failure-Inducing Input. TSE, 28(2):183--200, 2002.

Digital Library

[23]

X. Zhang and R. Gupta. Cost Effective Dynamic Program Slicing. In PLDI-04, pages 94--106, 2004.

Digital Library

[24]

X. Zhang and R. Gupta. Matching Execution Histories of Program Versions. In ESEC/FSE--13, pages 197--206, 2005.

Digital Library

Cited By

Dai JZhang YXu HLyu HWu ZXing XYang MKim YKim JVigna GShi E(2021)Facilitating Vulnerability Assessment through PoC MigrationProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3484594(3300-3317)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3484594
Cai H(2018)Hybrid Program Dependence Approximation for Effective Dynamic Impact PredictionIEEE Transactions on Software Engineering10.1109/TSE.2017.269278344:4(334-364)Online publication date: 1-Apr-2018
https://doi.org/10.1109/TSE.2017.2692783
Pastore FMariani LBodden ESchäfer WDeursen AZisman A(2017)VART: a tool for the automatic detection of regression faultsProceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering10.1145/3106237.3122819(964-968)Online publication date: 21-Aug-2017
https://dl.acm.org/doi/10.1145/3106237.3122819
Show More Cited By

Index Terms

Semantics-aware trace analysis
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Process validation
        Traceability
      2. Software defect analysis
        Software testing and debugging

Recommendations

Semantics-aware trace analysis
PLDI '09

As computer systems continue to become more powerful and complex, so do programs. High-level abstractions introduced to deal with complexity in large programs, while simplifying human reasoning, can often obfuscate salient program properties gleaned ...
A trace simplification technique for effective debugging of concurrent programs
FSE '10: Proceedings of the eighteenth ACM SIGSOFT international symposium on Foundations of software engineering

Concurrent programs are notoriously difficult to debug. We see two main reasons for this: 1) concurrency bugs are often difficult to reproduce, 2) traces of buggy concurrent executions can be complicated by fine-grained thread interleavings. Recently, a ...
Trace-based teaching in early programming courses
SIGCSE '13: Proceeding of the 44th ACM technical symposium on Computer science education

Students in introductory programming courses struggle with building the mental models that correctly describe concepts such as variables, subroutine calls, and dynamic memory usage. This struggle leads to lowered student learning outcomes and, it has ...

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

41
Total Citations
View Citations
776
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)2

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dai JZhang YXu HLyu HWu ZXing XYang MKim YKim JVigna GShi E(2021)Facilitating Vulnerability Assessment through PoC MigrationProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security10.1145/3460120.3484594(3300-3317)Online publication date: 12-Nov-2021
https://dl.acm.org/doi/10.1145/3460120.3484594
Cai H(2018)Hybrid Program Dependence Approximation for Effective Dynamic Impact PredictionIEEE Transactions on Software Engineering10.1109/TSE.2017.269278344:4(334-364)Online publication date: 1-Apr-2018
https://doi.org/10.1109/TSE.2017.2692783
Pastore FMariani LBodden ESchäfer WDeursen AZisman A(2017)VART: a tool for the automatic detection of regression faultsProceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering10.1145/3106237.3122819(964-968)Online publication date: 21-Aug-2017
https://dl.acm.org/doi/10.1145/3106237.3122819
Luo LMing JWu DLiu PZhu S(2017)Semantics-Based Obfuscation-Resilient Binary Code Similarity Comparison with Applications to Software and Algorithm Plagiarism DetectionIEEE Transactions on Software Engineering10.1109/TSE.2017.265504643:12(1157-1177)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1109/TSE.2017.2655046
Al-Hajjaji MMeinicke JKrieter SSchröter RThüm TLeich TSaake G(2016)Tool demo: testing configurable systems with FeatureIDEACM SIGPLAN Notices10.1145/3093335.299325452:3(173-177)Online publication date: 20-Oct-2016
https://dl.acm.org/doi/10.1145/3093335.2993254
Kim DKwon YLiu PKim IPerry DZhang XRodriguez-Rivera G(2016)Apex: automatic programming assignment error explanationACM SIGPLAN Notices10.1145/3022671.298403151:10(311-327)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/3022671.2984031
Al-Hajjaji MMeinicke JKrieter SSchröter RThüm TLeich TSaake GFischer BSchaefer I(2016)Tool demo: testing configurable systems with FeatureIDEProceedings of the 2016 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences10.1145/2993236.2993254(173-177)Online publication date: 20-Oct-2016
https://dl.acm.org/doi/10.1145/2993236.2993254
Kim DKwon YLiu PKim IPerry DZhang XRodriguez-Rivera GVisser ESmaragdakis Y(2016)Apex: automatic programming assignment error explanationProceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2983990.2984031(311-327)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/2983990.2984031
Meinicke JWong CKästner CThüm TSaake GLo DApel SKhurshid S(2016)On essential configuration complexity: measuring interactions in highly-configurable systemsProceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering10.1145/2970276.2970322(483-494)Online publication date: 25-Aug-2016
https://dl.acm.org/doi/10.1145/2970276.2970322
Cai HSantelices RJiang S(2016)Prioritizing Change-Impact Analysis via Semantic Program-Dependence QuantificationIEEE Transactions on Reliability10.1109/TR.2015.248100065:3(1114-1132)Online publication date: Sep-2016
https://doi.org/10.1109/TR.2015.2481000
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