MG++: Memory graphs for analyzing dynamic data structures

Vineet Singh, Rajiv Gupta, Iulian Neamtiu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Memory graphs are very useful in understanding the behavior of programs that use dynamically allocated data structures. We present a new memory graph representation, MG++, and a memory graph construction algorithm, that greatly enhance the utility of memory graphs. First, in addition to capturing the shapes of dynamically-constructed data structures, MG++ also captures how they evolve as the program executes and records the source code statements that play a role in their evolution to assist in debugging. Second, MG++ captures the history of actions performed by the memory allocator. This is useful in debugging programs that internally manage storage or in cases where understanding program behavior requires examining memory allocator actions. Our binary instrumentation-based algorithm for MG++ construction does not rely on the knowledge of memory allocator functions or on symbol table information. Our algorithm works for custom memory allocators as well as for in-program memory management. Experiments studying the time and space efficiency for real-world programs show that MG++ representation is space-efficient and the time overhead for MG++ construction algorithm is practical. We show that MG++ is effective for fault location and for analyzing binaries to detect heap buffer overflow attacks.

Original languageEnglish (US)
Title of host publication2015 IEEE 22nd International Conference on Software Analysis, Evolution, and Reengineering, SANER 2015 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages291-300
Number of pages10
ISBN (Electronic)9781479984695
DOIs
StatePublished - Apr 8 2015
Externally publishedYes
Event22nd IEEE International Conference on Software Analysis, Evolution, and Reengineering, SANER 2015 - Montreal, Canada
Duration: Mar 2 2015Mar 6 2015

Publication series

Name2015 IEEE 22nd International Conference on Software Analysis, Evolution, and Reengineering, SANER 2015 - Proceedings

Other

Other22nd IEEE International Conference on Software Analysis, Evolution, and Reengineering, SANER 2015
CountryCanada
CityMontreal
Period3/2/153/6/15

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Software

Keywords

  • buffer overflow attacks
  • evolution history
  • fault location
  • memory allocator history
  • memory graph

Fingerprint Dive into the research topics of 'MG++: Memory graphs for analyzing dynamic data structures'. Together they form a unique fingerprint.

Cite this