Cited By
View all- Boockmann JLuttgen G(2022)Heap Patterns for Memory Graph Visualization2022 Working Conference on Software Visualization (VISSOFT)10.1109/VISSOFT55257.2022.00025(162-166)Online publication date: Oct-2022
Shape-analysis driven memory graph visualization
Pages 298 - 308
Abstract
Analyzing heap dumps containing complex dynamic data structures is essential when debugging modern software systems. However, existing tools for visualizing memory graphs can neither deal with corrupt structures such as binary trees exhibiting cycles, nor do they offer adequate abstractions when being confronted with large heaps. This paper presents MGE (Memory Graph Explorer), a memory analyzer and visualizer that combines a novel memory graph abstraction with an interactive visualization. MGE borrows ideas from separation logic and shape analysis to reveal relationships between memory nodes, name recognized structures such as doubly-linked lists and binary trees, and summarize complex structures. This summarization works for corrupt data structures, too, and is particularly powerful for large, nested structures due to its support for interactive (un)folding. MGE's utility for aiding program comprehension is illustrated by real-world and textbook examples and contrasted with existing debuggers.
References
[1]
Omar Benomar, Houari A. Sahraoui, and Pierre Poulin. 2013. Visualizing software dynamicities with heat maps. In Working Conference on Software Visualization (VISSOFT'2013), Alexandru C. Telea, Andreas Kerren, and Andrian Marcus (Eds.). IEEE Computer Society, 1--10.
[2]
Alison Fernandez Blanco, Alexandre Bergel, and Juan Pablo Sandoval Alcocer. 2022. Software Visualizations to Analyze Memory Consumption: A Literature Review. ACM Comput. Surv. 55, 1, Article 18 (2022), 34 pages.
[3]
Jan H. Boockmann and Gerald Lüttgen. 2020. Learning Data Structure Shapes from Memory Graphs. In International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR'2020) (EPiC Series in Computing, Vol. 73), Elvira Albert and Laura Kovács (Eds.). EasyChair, 151--168. https://easychair.org/publications/paper/mkjl
[4]
Marc Brockschmidt, Yuxin Chen, Byron Cook, Pushmeet Kohli, Siddharth Krishna, Daniel Tarlow, and He Zhu. 2016. Learning to Verify the Heap. Technical Report. Microsoft Research. https://www.microsoft.com/en-us/research/publication/learning-to-verify-the-heap/
[5]
Michael Bruce-Lockhart, Theodore S. Norvell, and Yiannis Cotronis. 2007. Program and Algorithm Visualization in Engineering and Physics. Electron. Notes Theor. Comput. Sci. 178 (2007), 111--119.
[6]
Cristiano Calcagno, Dino Distefano, Jérémy Dubreil, Dominik Gabi, Pieter Hooimeijer, Martino Luca, Peter W. O'Hearn, Irene Papakonstantinou, Jim Purbrick, and Dulma Rodriguez. 2015. Moving Fast with Software Verification. In NASA Formal Methods Symposium (NFM'2015) (Lecture Notes in Computer Science, Vol. 9058), Klaus Havelund, Gerard J. Holzmann, and Rajeev Joshi (Eds.). Springer, 3--11.
[7]
Standard Performance Evaluation Corporation. 2001. SPECjbb2000 Documentation. https://www.spec.org/jbb2000/ (Accessed: 23rd March 2022).
[8]
Patrick Cousot and Radhia Cousot. 1979. Systematic Design of Program Analysis Frameworks. In Symposium on Principles of Programming Languages (POPL '1979), Alfred V. Aho, Stephen N. Zilles, and Barry K. Rosen (Eds.). ACM Press, 269--282.
[9]
Dino Distefano, Manuel Fähndrich, Francesco Logozzo, and Peter W. O'Hearn. 2019. Scaling static analyses at Facebook. Commun. ACM 62, 8 (2019), 62--70.
[10]
John Ellson, Emden R. Gansner, Eleftherios Koutsofios, Stephen C. North, and Gordon Woodhull. 2001. Graphviz - Open Source Graph Drawing Tools. In International Symposium on Graph Drawing (GD'2001) (Lecture Notes in Computer Science, Vol. 2265), Petra Mutzel, Michael Jünger, and Sebastian Leipert (Eds.). Springer, 483--484.
[11]
Eclipse Foundation. 2021. Memory Analyzer (MAT). https://www.eclipse.org/mat/ (Accessed: 23rd March 2022).
[12]
Martin Fowler. 2011. Domain-Specific Languages. Addison-Wesley.
[13]
Max Franz, Christian T. Lopes, Gerardo Huck, Yue Dong, Onur Sumer, and Gary D. Bader. 2015. Cytoscape.js: a graph theory library for visualisation and analysis. Bioinformatics 32, 2 (09 2015), 309--311.
[14]
Paul V. Gestwicki and Bharat Jayaraman. 2005. Methodology and architecture of JIVE. In Symposium on Software Visualization (SOFTVIS'2005), Thomas L. Naps and Wim De Pauw (Eds.). ACM, 95--104.
[15]
Rakesh Ghiya and Laurie J. Hendren. 1996. Is it a Tree, a DAG, or a Cyclic Graph? A Shape Analysis for Heap-Directed Pointers in C. In Symposium on Principles of Programming Languages (POPL'1996), Hans-Juergen Boehm and Guy L. Steele Jr. (Eds.). ACM Press, 1--15.
[16]
Jean-Yves Girard. 1987. Linear Logic. Theor. Comput. Sci. 50 (1987), 1--102.
[17]
Philip J. Guo. 2013. Online python tutor: embeddable web-based program visualization for CS education. In Technical Symposium on Computer Science Education (SIGCSE'2013), Tracy Camp, Paul T. Tymann, J. D. Dougherty, and Kris Nagel (Eds.). ACM, 579--584.
[18]
Sean Kelley, Edward Aftandilian, Connor Gramazio, Nathan P. Ricci, Sara L. Su, and Samuel Z. Guyer. 2013. Heapviz: Interactive heap visualization for program understanding and debugging. Inf. Vis. 12, 2 (2013), 163--177.
[19]
Ton Chanh Le, Guolong Zheng, and ThanhVu Nguyen. 2019. SLING: using dynamic analysis to infer program invariants in separation logic. In Conference on Programming Language Design and Implementation (PLDI'2019), Kathryn S. McKinley and Kathleen Fisher (Eds.). ACM, 788--801.
[20]
Mark Marron, César Sánchez, Zhendong Su, and Manuel Fähndrich. 2013. Abstracting Runtime Heaps for Program Understanding. IEEE Trans. Software Eng. 39, 6 (2013), 774--786.
[21]
Chris Miles. 2016. Visual Debugging with Xcode. https://developer.apple.com/videos/play/wwdc2016/410/ (Accessed: 23rd March 2022).
[22]
Oracle. 2021. HPROF: A Heap/CPU Profiling Tool. https://docs.oracle.com/javase/7/docs/technotes/samples/hprof.html (Accessed: 23rd March 2022).
[23]
Oracle. 2021. Java Platform, Version 11 API Specification for Object#hashCode(). https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Object.html#hashCode() (Accessed: 23rd March 2022).
[24]
Oracle. 2021. LinkedList (Java Platform SE 7). https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html (Accessed: 23rd March 2022).
[25]
Long H. Pham, Jun Sun, and Quang Loc Le. 2019. Compositional Verification of Heap-Manipulating Programs Through Property-Guided Learning. In Asian Symposium on Programming Languages and Systems (APLAS'2019) (Lecture Notes in Computer Science, Vol. 11893), Anthony Widjaja Lin (Ed.). Springer, 405--424.
[26]
Sokhom Pheng and Clark Verbrugge. 2006. Dynamic Data Structure Analysis for Java Programs. In International Conference on Program Comprehension (ICPC'2006). IEEE Computer Society, 191--201.
[27]
Alexey Ragozin. 2021. HeapLib. https://github.com/aragozin/heaplib (Accessed: 23rd March 2022).
[28]
Steven P. Reiss. 2014. The Challenge of Helping the Programmer during Debugging. In Working Conference on Software Visualization (VISSOFT'2014), Houari A. Sahraoui, Andy Zaidman, and Bonita Sharif (Eds.). IEEE Computer Society, 112--116.
[29]
John C. Reynolds. 2002. Separation Logic: A Logic for Shared Mutable Data Structures. In Symposium on Logic in Computer Science (LICS'2002). IEEE Computer Society, 55--74.
[30]
Shmuel Sagiv, Thomas W. Reps, and Reinhard Wilhelm. 2002. Parametric shape analysis via 3-valued logic. ACM Trans. Program. Lang. Syst. 24, 3 (2002), 217--298.
[31]
Sven Schneider, Leen Lambers, and Fernando Orejas. 2019. A Logic-Based Incremental Approach to Graph Repair. In International Conference on Fundamental Approaches to Software Engineering (FASE'2019) (Lecture Notes in Computer Science, Vol. 11424), Reiner Hähnle and Wil M. P. van der Aalst (Eds.). Springer, 151--167.
[32]
Gary Sevitsky, Wim De Pauw, and Ravi B. Konuru. 2001. An Information Exploration Tool for Performance Analysis of Java Programs. In International Conference on Technology of Object-Oriented Languages and Systems (TOOLS'2001). IEEE Computer Society, 85--101.
[33]
Chad Smith. 2021. gdbgui. https://github.com/cs01/gdbgui/ (Accessed: 23rd March 2022).
[34]
Richard M Stallman. 2002. GNU compiler collection internals. Free Software Foundation (2002).
[35]
Margaret-Anne D. Storey and Hausi A. Müller. 1995. Manipulating and documenting software structures using SHriMP views. In International Conference on Software Maintenance (ICSM'1995). IEEE Computer Society, 275.
[36]
Linus Torvalds. 2021. list.h - Linux Kernel List Headers. https://github.com/torvalds/linux/blob/master/include/linux/list.h (Accessed: 23rd March 2022).
[37]
Markus Triska. 2012. The Finite Domain Constraint Solver of SWI-Prolog. In International Symposium on Functional and Logic Programming (FLOPS'2012) (Lecture Notes in Computer Science, Vol. 7294), Tom Schrijvers and Peter Thiemann (Eds.). Springer, 307--316.
[38]
Frédéric Vogels, Bart Jacobs, and Frank Piessens. 2015. Featherweight VeriFast. Log. Methods Comput. Sci. 11, 3 (2015).
[39]
David H. White, Thomas Rupprecht, and Gerald Lüttgen. 2016. DSI: An evidence-based approach to identify dynamic data structures in C programs. In International Symposium on Software Testing and Analysis (ISSTA'2016), Andreas Zeller and Abhik Roychoudhury (Eds.). ACM, 259--269.
[40]
Jan Wielemaker, Tom Schrijvers, Markus Triska, and Torbjörn Lager. 2012. SWI-Prolog. Theory Pract. Log. Program. 12, 1--2 (2012), 67--96.
[41]
Reinhard Wilhelm, Shmuel Sagiv, and Thomas W. Reps. 2000. Shape Analysis. In International Conference on Compiler Construction (CC'2000) (Lecture Notes in Computer Science, Vol. 1781), David A. Watt (Ed.). Springer, 1--17.
[42]
Andreas Zeller and Dorothea Lütkehaus. 1996. DDD - A Free Graphical Front-End for UNIX Debuggers. ACM SIGPLAN Notices 31, 1 (1996), 22--27.
[43]
Thomas Zimmermann and Andreas Zeller. 2001. Visualizing Memory Graphs. In Software Visualization, International Seminar Dagstuhl Castle, Germany, May 20--25, 2001, Revised Lectures (Lecture Notes in Computer Science, Vol. 2269), Stephan Diehl (Ed.). Springer, 191--204.
Recommendations
Graph Visualization and Navigation in Information Visualization: A Survey
This is a survey on graph visualization and navigation techniques, as used in information visualization. Graphs appear in numerous applications such as web browsing, state-transition diagrams, and data structures. The ability to visualize and to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 2022
698 pages
ISBN:9781450392983
DOI:10.1145/3524610
- Conference Chairs:
- Ayushi Rastogi,
- Rosalia Tufano,
- General Chair:
- Gabriele Bavota,
- Program Chairs:
- Venera Arnaoudova,
- Sonia Haiduc
Copyright © 2022 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
In-Cooperation
- IEEE CS
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 20 October 2022
Check for updates
Qualifiers
- Research-article
Funding Sources
Conference
ICPC '22
Sponsor:
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 84Total Downloads
- Downloads (Last 12 months)26
- Downloads (Last 6 weeks)1
Reflects downloads up to 01 Jan 2025
Other Metrics
Citations
Cited By
View all- Boockmann JLuttgen G(2022)Heap Patterns for Memory Graph Visualization2022 Working Conference on Software Visualization (VISSOFT)10.1109/VISSOFT55257.2022.00025(162-166)Online publication date: Oct-2022
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in