A Survey on Heap Analysis

PhD Qualifying Examination


Title: "A Survey on Heap Analysis"

by

Mr. Chengpeng WANG


Abstract:

Program heap is essentially a mathematical concept, i.e., a set of objects and
a connectivity relation on them. In real-world programs, developers define
various types of data structures and allocate the objects in the heap. Because
of dynamic allocation and flexible heap manipulations, the size of
heap-allocated objects is potentially unbounded and the connectivity relation
can be extremely complex, which increase the difficulty of assuring memory
safety and understanding heap-manipulating programs.

Static program analysis, a program analysis technique, achieves satisfactory
performance in many program analysis tasks. Based on abstract state
transformation, program states in actual execution can be approximated without
executing programs. However, the unboundedness of heap and complex connectivity
relation make heap-allocated objects difficult to be abstracted precisely, thus
the precision of clients in static analysis is degraded in the presence of
intensive use of heap. In order to support static analysis clients to analyze
program precisely, heap analysis provides linkage properties about the heap,
which reflects the connectivity relations of objects, such as reachability,
ownership, etc.

According to the way to organize heap-allocated objects, existing works can be
divided into two categories. The first category of works concentrate on the
structural heap connected by pointers, while the second category of works focus
on the structural heap organized by containers. Aiming to a particular
structural heap, abstract heap model is established and linkage properties are
inferred specifically by checking the satisfiability of constraints or solving
a CFL-reachability problem. To show the impact of heap analysis, applications
of heap analysis are introduced. The applications mainly include memory
corruption detection, typestate verification, memory safety verification in
multi-threaded programs, and heap-manipulating program understanding. We hope
our survey will shed light on our future work on heap analysis in certain
scenarios, including analyzing structural heap manipulated in a loop.


Date:                   Monday, 5 October 2020

Time:                   4:00pm - 6:00pm

Zoom meeting:           https://hkust.zoom.us/j/3611270672

Committee Members:      Dr. Charles Zhang (Supervisor)
                        Prof. Shing-Chi Cheung (Chairperson)
                        Dr. Wei Wang
                        Prof. Ke Yi


**** ALL are Welcome ****