Memory Graphs
Description and Extraction

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 "[3]" means that v2 is the fourth element of v1. For structs or unions the label "->membername" is used. For dereferencing the label "[0]" 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"+"[42]"="array[42]".

Extraction

foreach visible variable var do
     fetch_value(var)
od

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.

def fetch_value(var):
     insert_in_Graph(var)
     if isArray(var) then
         unfold_array(var)
     else if isStruct(var) then
         unfold_struct(var)
     else if isPointer(var) then
         unfold_pointer(var)

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.

def unfold_array(var):
     for i=1 to length(var) do
         fetch_value(var[i])
     od

def unfold_struct(var):
     foreach member mem do
         fetch_value(var+"."+mem)
     od

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.

def unfold_pointer(var):
     if pointsToStack(var) then
         fetch_value(var+"[0]")
     else if pointsToHeap(var) then
         foreach offset to elements allocated together with var off do
             fetch_value(var+"["+off+"]")
         do

Back

Impressum ● Datenschutzerklärung