abstract

Constraint-based event trace reduction

Author:

Jie WangAuthors Info & Claims

FSE 2016: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering

Pages 1106 - 1108

https://doi.org/10.1145/2950290.2983964

Published: 01 November 2016 Publication History

Abstract

Various record-replay techniques are developed to facilitate web application debugging. However, it is time-consuming to inspect all recorded events that reveal a failure. To reduce the cost of debugging, delta-debugging and program slicing are used to remove failure-irrelevant events. However, delta-debugging does not scale well for long traces, and program slicing fails to remove irrelevant events that the failure has program dependence on. In this paper, we propose an effective and efficient approach to remove failure-irrelevant events from the event trace. Our approach builds constraints among events and the failure (e.g., a variable can read any of its earlier type-compatible values), to search for a minimal event trace that satisfies these constraints. Our evaluation on 10 real-world web applications shows that our approach can further remove 70% of events in the reduced trace of dynamic slicing, and needs 80% less iterations and 86% less time than delta-debugging.

References

[1]

J. Mickens, J. Elson, and J. Howell, “Mugshot : Deterministic Capture and Replay for JavaScript Applications,” in Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation(NSDI), 2010, pp. 159– 174.

Digital Library

[2]

B. Burg, R. Bailey, A. J. Ko, and M. D. Ernst, “Interactive Record/Replay for Web Application Debugging,” in Preceedings of User Interface Software and Technology (UIST), 2013, pp. 473–484.

Digital Library

[3]

M. Hammoudi, B. Burg, G. Bae, and G. Rothermel, “On the Use of Delta Debugging to Reduce Recordings and Facilitate Debugging of Web Applications,” in Proceedings of the 10th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software (ESEC/FSE), 2015, pp. 333–344.

Digital Library

[4]

A. Zeller and R. Hildebrandt, “Simplifying and Isolating Failure-inducing Input,” IEEE Transactions on Software Engineering (TSE), vol. 28, no. 2, pp. 183–200, 2002.

Digital Library

[5]

J. Wang, W. Dou, C. Gao, and J. Wei, “Fast Reproducing Web Application Errors,” in Preceedings of the 26th International Symposium on Software Reliability Engineering (ISSRE), 2015, pp. 530–540.

Digital Library

[6]

M. Burger and A. Zeller, “Minimizing Reproduction of Software Failures,” in Proceedings of the International Symposium on Software Testing and Analysis(ISSTA), 2011, pp. 221–231.

Digital Library

[7]

J.-D. Choi and A. Zeller, “Isolating Failure-Inducing Thread Schedules,” in Proceedings of the ACM SIGSOFT international symposium on Software testing and analysis(ISSTA), 2002, pp. 210–220.

Digital Library

[8]

A. Zeller, “Isolating Cause-Effect Chains from Computer Programs,” ACM SIGSOFT Software Engineering Notes, vol. 27, no. 6, pp. 1–10, 2002.

Digital Library

[9]

Q. Zhang and B. Goncalves, “Minimizing GUI Event Traces,” in Preceedings of the 24th ACM SIGSOFT International Symposium on the Foundations of Software Engineering(FSE), 2016, to appear.

Digital Library

[10]

A. Zeller, “Yesterday, My Program Worked. Today, It Does Not. Why?,” in Proceedings of the 7th European Software Engineering Conference(ESEC), 1999, pp. 253–267.

Digital Library

[11]

J. Krinke, “Context-Sensitive Slicing of Concurrent Programs,” in Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering (ESEC/FSE), 2003, pp. 178–187.

Digital Library

[12]

D. Giffhorn and C. Hammer, “Precise Slicing of Concurrent Programs: An Evaluation of Static Slicing Algorithms for Concurrent Programs,” Automated Software Engineering(ASE), vol. 16, no. 2, pp. 197–234, 2009.

Digital Library

[13]

S. Zhang, “Practical Semantic Test Simplification,” in Proceedings of the International Conference on Software Engineering (ICSE), 2013, pp. 1173–1176.

Digital Library

[14]

S. Arlt, A. Podelski, and M. Wehrle, “Reducing GUI Test Suites via Program Slicing,” in Proceedings of the International Symposium on Software Testing and Analysis (ISSTA), 2014, pp. 270–281.

Digital Library

[15]

K. Sen, “Concolic Testing,” in Proceedings of the twentysecond IEEE/ACM international conference on Automated software engineering (ASE), 2007, pp. 571–572.

Digital Library

[16]

G. Li, E. Andreasen, and I. Ghosh, “SymJS: Automatic Symbolic Testing of JavaScript Web Applications,” in Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering(ICSE), 2014, pp. 449–459.

Digital Library

[17]

E. J. Schwartz, T. Avgerinos, and D. Brumley, “All You Ever Wanted to Know about Dynamic Taint Analysis and Forward Symbolic Execution,” in IEEE Symposium on Security & Privacy (S&P), 2010, pp. 317–331.

Digital Library

[18]

G. Li, E. Andreasen, and I. Ghosh, “SymJS: Automatic Symbolic Testing of JavaScript Web Applications,” in Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering(ICSE), 2014, pp. 449–459.

Digital Library

[19]

C. S. Jensen, M. R. Prasad, and A. Møller, “Automated Testing with Targeted Event Sequence Generation,” in Proceedings of the International Symposium on Software Testing and Analysis(ISSTA), 2013, pp. 67–77.

Digital Library

Cited By

Kiss A(2020)Generalizing the Split Factor of the Minimizing Delta Debugging AlgorithmIEEE Access10.1109/ACCESS.2020.30430278(219837-219846)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3043027
Kiss ÁHodován RGyimóthy TPrasetya WVos TGetir S(2018)HDDr: a recursive variant of the hierarchical Delta debugging algorithmProceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation10.1145/3278186.3278189(16-22)Online publication date: 5-Nov-2018
https://dl.acm.org/doi/10.1145/3278186.3278189
Wang JRosu GDi Penta MNguyen T(2017)Characterizing and taming non-deterministic bugs in JavaScript applicationsProceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering10.5555/3155562.3155696(1006-1009)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.5555/3155562.3155696
Show More Cited By

Index Terms

Constraint-based event trace reduction
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Event trace reduction for effective bug replay of Android apps via differential GUI state analysis
ESEC/FSE 2019: Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering

Existing Android testing tools, such as Monkey, generate a large quantity and a wide variety of user events to expose latent GUI bugs in Android apps. However, even if a bug is found, a majority of the events thus generated are often redundant and bug-...
Static analysis of event-driven Node.js JavaScript applications
OOPSLA '15

Many JavaScript programs are written in an event-driven style. In particular, in server-side Node.js applications, operations involving sockets, streams, and files are typically performed in an asynchronous manner, where the execution of listeners is ...
Scenario-based video event recognition by constraint flow
CVPR '11: Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition

We present a novel approach to representing and recognizing composite video events. A composite event is specified by a scenario, which is based on primitive events and their temporal-logical relations, to constrain the arrangements of the primitive ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FSE 2016: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering

November 2016

1156 pages

ISBN:9781450342186

DOI:10.1145/2950290

General Chair:
Thomas Zimmermann
Microsoft Research, USA
,
Program Chairs:
Jane Cleland-Huang
University of Notre Dame, USA
,
Zhendong Su
University of California at Davis, USA

Copyright © 2016 Owner/Author.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2016

Check for updates

Author Tags

Qualifiers

Abstract

Funding Sources

National Key Research and Development Plan
National Natural Science Foundation

Conference

FSE'16

Sponsor:

SIGSOFT

FSE'16: 24nd ACM SIGSOFT International Symposium on the Foundations of Software Engineering

November 13 - 18, 2016

WA, Seattle, USA

Acceptance Rates

Overall Acceptance Rate 17 of 128 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
192
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kiss A(2020)Generalizing the Split Factor of the Minimizing Delta Debugging AlgorithmIEEE Access10.1109/ACCESS.2020.30430278(219837-219846)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3043027
Kiss ÁHodován RGyimóthy TPrasetya WVos TGetir S(2018)HDDr: a recursive variant of the hierarchical Delta debugging algorithmProceedings of the 9th ACM SIGSOFT International Workshop on Automating TEST Case Design, Selection, and Evaluation10.1145/3278186.3278189(16-22)Online publication date: 5-Nov-2018
https://dl.acm.org/doi/10.1145/3278186.3278189
Wang JRosu GDi Penta MNguyen T(2017)Characterizing and taming non-deterministic bugs in JavaScript applicationsProceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering10.5555/3155562.3155696(1006-1009)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.5555/3155562.3155696
Wang J(2017)Characterizing and taming non-deterministic bugs in Javascript applications2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE)10.1109/ASE.2017.8115720(1006-1009)Online publication date: Oct-2017
https://doi.org/10.1109/ASE.2017.8115720

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