research-article

Travioli: a dynamic analysis for detecting data-structure traversals

Authors:

Koushik SenAuthors Info & Claims

ICSE '17: Proceedings of the 39th International Conference on Software Engineering

Pages 473 - 483

https://doi.org/10.1109/ICSE.2017.50

Published: 20 May 2017 Publication History

Abstract

Traversal is one of the most fundamental operations on data structures, in which an algorithm systematically visits some or all of the data items of a data structure. We propose a dynamic analysis technique, called Travioli, for detecting data-structure traversals. We introduce the concept of acyclic execution contexts, which enables precise detection of traversals of arrays and linked data structures such as lists and trees in the presence of both loops and recursion. We describe how the information reported by Travioli can be used for visualizing data-structure traversals, manually generating performance regression tests, and for discovering performance bugs caused by redundant traversals. We evaluate Travioli on five real-world JavaScript programs. In our experiments, Travioli produced fewer than 4% false positives. We were able to construct performance tests for 93.75% of the reported true traversals. Travioli also found two asymptotic performance bugs in widely used JavaScript frameworks D3 and express.

References

[1]

Benchmark.js. https://benchmarkjs.com. Retrieved: August 2016.

[2]

Chrome performance dashboard. https://chromeperf.appspot.com. Retrieved: August 2016.

[3]

D3: a JavaScript library for visualizing data with HTML, SVG, and CSS. https://d3js.org. Retrieved: August 2016.

[4]

d3-collection: Handy data structures for elements keyed by string. https://github.com/d3/d3-collection. Retrieved: August 2016.

[5]

d3-hierarchy: 2d layout algorithms for visualizing hierarchical data. https://github.com/d3/d3-hierarchy. Retrieved: August 2016.

[6]

express.js: Fast, unopinionated, minimalist web framework for node. https://github.com/expressjs/express. Retrieved: August 2016.

[7]

immutable.js: Immutable persistent data collections for Javascript. https://github.com/facebook/immutable-js. Retrieved: August 2016.

[8]

Math.js: An extensive math library for JavaScript and Node.js. https://github.com/josdejong/mathjs. Retrieved: August 2016.

[9]

Node.js. https://nodejs.org. Retrieved: August 2016.

[10]

Edward E. Aftandilian, Sean Kelley, Connor Gramazio, Nathan Ricci, Sara L. Su, and Samuel Z. Guyer. Heapviz: Interactive heap visualization for program understanding and debugging. In Proceedings of the 5th International Symposium on Software Visualization, SOFTVIS '10, pages 53--62, New York, NY, USA, 2010. ACM.

Digital Library

[11]

Jacob Burnim, Sudeep Juvekar, and Koushik Sen. WISE: Automated test generation for worst-case complexity. In Proceedings of the 31st International Conference on Software Engineering, ICSE '09, pages 463--473, Washington, DC, USA, 2009. IEEE Computer Society.

Digital Library

[12]

Bihuan Chen, Yang Liu, and Wei Le. Generating performance distributions via probabilistic symbolic execution. In Proceedings of the 38th International Conference on Software Engineering, ICSE '16, pages 49--60, New York, NY, USA, 2016. ACM.

Digital Library

[13]

Anthony Cozzie, Frank Stratton, Hui Xue, and Samuel T. King. Digging for data structures. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, OSDI'08, pages 255--266, Berkeley, CA, USA, 2008. USENIX Association.

Digital Library

[14]

Luca Della Toffola, Michael Pradel, and Thomas R. Gross. Performance problems you can fix: A dynamic analysis of memoization opportunities. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA 2015, pages 607--622, New York, NY, USA, 2015. ACM.

Digital Library

[15]

John Ellson, Emden Gansner, Lefteris Koutsofios, Stephen C North, and Gordon Woodhull. Graphvizopen source graph drawing tools. In International Symposium on Graph Drawing, pages 483--484. Springer, 2001.

[16]

Rakesh Ghiya and Laurie J. Hendren. Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '96, pages 1--15, New York, NY, USA, 1996. ACM.

Digital Library

[17]

Guoliang Jin, Linhai Song, Xiaoming Shi, Joel Scherpelz, and Shan Lu. Understanding and detecting real-world performance bugs. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '12, pages 77--88, New York, NY, USA, 2012. ACM.

Digital Library

[18]

Uday P. Khedker, Amitabha Sanyal, and Amey Karkare. Heap reference analysis using access graphs. ACM Trans. Program. Lang. Syst., 30(1), November 2007.

Digital Library

[19]

Adrian Nistor, Linhai Song, Darko Marinov, and Shan Lu. Toddler: Detecting performance problems via similar memory-access patterns. In Proceedings of the 2013 International Conference on Software Engineering, ICSE '13, pages 562--571, Piscataway, NJ, USA, 2013. IEEE Press.

Digital Library

[20]

Oswaldo Olivo, Isil Dillig, and Calvin Lin. Static detection of asymptotic performance bugs in collection traversals. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2015, pages 369--378, New York, NY, USA, 2015. ACM.

Digital Library

[21]

Sokhom Pheng and Clark Verbrugge. Dynamic data structure analysis for Java programs. In Proceedings of the 14th IEEE International Conference on Program Comprehension, ICPC '06, pages 191--201, Washington, DC, USA, 2006. IEEE Computer Society.

Digital Library

[22]

Michael Pradel, Markus Huggler, and Thomas R. Gross. Performance regression testing of concurrent classes. In Proceedings of the 2014 International Symposium on Software Testing and Analysis, ISSTA 2014, pages 13--25, New York, NY, USA, 2014. ACM.

Digital Library

[23]

Easwaran Raman and David I. August. Recursive data structure profiling. In Proceedings of the 2005 Workshop on Memory System Performance, MSP '05, pages 5--14, New York, NY, USA, 2005. ACM.

Digital Library

[24]

Mooly Sagiv, Thomas Reps, and Reinhard Wilhelm. Parametric shape analysis via 3-valued logic. In Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL '99, pages 105--118, New York, NY, USA, 1999. ACM.

Digital Library

[25]

Koushik Sen, Swaroop Kalasapur, Tasneem Brutch, and Simon Gibbs. Jalangi: A selective record-replay and dynamic analysis framework for JavaScript. In Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2013, pages 488--498, New York, NY, USA, 2013. ACM.

Digital Library

[26]

Micha Sharir and Amir Pnueli. Two approaches to interprocedural data flow analysis. In Muchnick and Jones, editors, Program Flow Analysis: Theory and Applications. Prentice-Hall, Inc, 1981.

[27]

Olin Shivers. Control-Flow Analysis of Higher-Order Languages. PhD thesis, Carnegie Mellon University, May 1991.

Digital Library

[28]

V. Singh, R. Gupta, and I. Neamtiu. MG++: Memory graphs for analyzing dynamic data structures. In 2015 IEEE 22nd International Conference on Software Analysis, Evolution, and Reengineering (SANER), pages 291--300, March 2015.

[29]

Steven S. Skiena. The Algorithm Design Manual. Springer London, second edition, 2009.

Digital Library

[30]

John Whaley and Monica S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, PLDI '04, pages 131--144, New York, NY, USA, 2004. ACM.

Digital Library

[31]

David H. White, Thomas Rupprecht, and Gerald Lüttgen. DSI: An evidence-based approach to identify dynamic data structures in C programs. In Proceedings of the 25th International Symposium on Software Testing and Analysis, ISSTA 2016, pages 259--269, New York, NY, USA, 2016. ACM.

Digital Library

[32]

Bin Xin, William N. Sumner, and Xiangyu Zhang. Efficient program execution indexing. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '08, pages 238--248, New York, NY, USA, 2008. ACM.

Digital Library

Cited By

Li AHuang MLemieux CPadhye RBöhme MNoller YSzekeres L(2024)The Havoc Paradox in Generator-Based Fuzzing (Registered Report)Proceedings of the 3rd ACM International Fuzzing Workshop10.1145/3678722.3685529(3-12)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3678722.3685529
Liu YMeng WYin HStavrou ACremers CShi E(2022)AcquirerProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3559337(2071-2084)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3559337
Tan JJiao SChabbi MLiu XAyguadé EHwu WBadia RHofstee H(2020)What every scientific programmer should know about compiler optimizations?Proceedings of the 34th ACM International Conference on Supercomputing10.1145/3392717.3392754(1-12)Online publication date: 29-Jun-2020
https://dl.acm.org/doi/10.1145/3392717.3392754
Show More Cited By

Travioli: a dynamic analysis for detecting data-structure traversals
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis

Recommendations

Interprocedural pointer alias analysis

We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Side-effect analysis with fast escape filter
SOAP '12: Proceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program analysis

Side-effect analysis is a fundamental static analysis used to determine the memory locations modified or used by each program entity. For the programs with pointers, the analysis can be very imprecise. To improve the precision of side-effect analysis, ...
Practical pointer aliasing analysis

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICSE '17: Proceedings of the 39th International Conference on Software Engineering

May 2017

816 pages

ISBN:9781538638682

General Chair:
Sebastian Uchitel
University of Buenos Aires, Argentina and Imperial College London, UK
,
Program Chairs:
Alessandro Orso
Georgia Institute of Technology
,
Martin Robillard
McGill University, Canada

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering
IEEE-CS: Computer Society
SADIO: SADIO

Publisher

IEEE Press

Publication History

Published: 20 May 2017

Check for updates

Qualifiers

Research-article

Conference

ICSE '17

Sponsor:

SIGSOFT
IEEE-CS
SADIO

ICSE '17: 39th International Conference on Software Engineering

May 20 - 28, 2017

Buenos Aires, Argentina

Acceptance Rates

Overall Acceptance Rate 276 of 1,856 submissions, 15%

Upcoming Conference

ICSE 2025

2025 IEEE/ACM 46th International Conference on Software Engineering

April 26 - May 3, 2025

Ottawa , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
197
Total Downloads

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

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li AHuang MLemieux CPadhye RBöhme MNoller YSzekeres L(2024)The Havoc Paradox in Generator-Based Fuzzing (Registered Report)Proceedings of the 3rd ACM International Fuzzing Workshop10.1145/3678722.3685529(3-12)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3678722.3685529
Liu YMeng WYin HStavrou ACremers CShi E(2022)AcquirerProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3559337(2071-2084)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3548606.3559337
Tan JJiao SChabbi MLiu XAyguadé EHwu WBadia RHofstee H(2020)What every scientific programmer should know about compiler optimizations?Proceedings of the 34th ACM International Conference on Supercomputing10.1145/3392717.3392754(1-12)Online publication date: 29-Jun-2020
https://dl.acm.org/doi/10.1145/3392717.3392754
Su PWen SYang HChabbi MLiu XAtlee JBultan TWhittle J(2019)Redundant loadsProceedings of the 41st International Conference on Software Engineering10.1109/ICSE.2019.00103(982-993)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE.2019.00103
Fedorova AMustard CBeschastnikh IRubin JWong AMiucin SYe LLeavens GGarcia APăsăreanu C(2018)Performance comprehension at WiredTigerProceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3236024.3236081(83-94)Online publication date: 26-Oct-2018
https://dl.acm.org/doi/10.1145/3236024.3236081
Wei JChen JFeng YFerles KDillig ILeavens GGarcia APăsăreanu C(2018)Singularity: pattern fuzzing for worst case complexityProceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3236024.3236039(213-223)Online publication date: 26-Oct-2018
https://dl.acm.org/doi/10.1145/3236024.3236039
Lemieux CPadhye RSen KSong DTip FBodden E(2018)PerfFuzz: automatically generating pathological inputsProceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3213846.3213874(254-265)Online publication date: 12-Jul-2018
https://dl.acm.org/doi/10.1145/3213846.3213874
Mostafa SWang XXie TBultan TSen K(2017)PerfRanker: prioritization of performance regression tests for collection-intensive softwareProceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3092703.3092725(23-34)Online publication date: 10-Jul-2017
https://dl.acm.org/doi/10.1145/3092703.3092725

View Options

Get Access

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