Lehrstuhl für Softwaretechnik (Prof. Zeller)
Universität des Saarlandes – Informatik
Informatik Campus des Saarlandes
Campus E9 1 (CISPA)
E-mail: zeller @ cs.uni-saarland.de
Telefon: +49 681 302-70970
DescriptionThe vertices of a Memory Graph represent the memory content. A vertex contains the type, the value and the address of stored data. Vertices can be identified by their address combined with their type.
An edge connects two vertices v1 and v2, if vertex v2 can be accessed via v1, i.e. by dereferencing. Another example is array v1 with element v2. Edges are labeled. A label specifies how vertex v2 can be accessed via v1. For arrays the label "" means that v2 is the fourth element of v1. For structs or unions the label "->membername" is used. For dereferencing the label "" is used. For simple variables their name is used to label the edge.
Each memory graph has a special root vertex. Via this vertex each visible variable can be accessed. The root vertex has no type, no address and no value.
The picture below shows a memory graph for an array with two elements. The array itself can be accessed via the root vertex. Its elements can only be accessed via the array. To access the element 42 the labels of the edges have to be concatenated, so you can get 42 via the access path "array"+""="array".
foreach visible variable var do
The procedure fetch_value generates a vertex containing the value, address and type. This vertex is connected by an edge with the previously accessed vertex. The new vertex and the connecting edge are inserted into the graph. If the kind of the variable is an array, struct/union or a pointer the unfold process continues.
Arrays and structs are unfolded straighforward. For arrays the number of elements is determined and each element is unfolded. For structs the members are determined and unfolded.
Pointers can point to the stack or to the heap. In the first case the pointer's dereferenced value is unfolded. In the second case, the pointer points to data on the heap which might have been allocated together with other data. This additional data is unfolded, too (assuming that it has the same type as our pointer). Strings are not handled as pointers due to the huge overhead they cause.