Dies ist ein Archiv des alten Softwaretechnik Lehrstuhls der Universität des Saarlandes. Es ist nicht länger aktuell.

  

Memory Graphs
Description and Extraction

Lehrstuhl für Softwaretechnik (Prof. Zeller)
Universität des Saarlandes – Informatik
Informatik Campus des Saarlandes
Campus E9 1 (CISPA)
66123 Saarbrücken
E-mail: zeller @ cs.uni-saarland.de
Telefon: +49 681 302-70970

Deutschsprachige Startseite Page d'acceuil en franÁais English home page
  

Description

The 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 "[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]".

Memory Graph of an array

Extraction

For each visible variable the accessible data is unfolded using the procedure fetch_value. This is typically implemented as a call to a debugger such as GDB which queries the value from a running program.

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

<webmaster@st.cs.uni-saarland.de> · http://www.st.cs.uni-saarland.de//memgraphs/extraction.php3 · Stand: 2018-04-05 13:41