Prev Up Next

I guess it has something to do with the object sp, but I am lost in the source code. Let us locate where the object sp is used. What is the exact sequence of operations that are executed on it? I'll call Bauhaus for help.

Through a static data flow analysis, Bauhaus locates all possible operations on the object sp in the code. Then Bauhaus traces the order of these operations based on interprocedural and intraprocedural control flow. Because it is also important to understand under which circumstances an operation is executed, all predicates that have a control influence are kept, too. All other nodes in the original control flow graph not relevant to the object under consideration are ignored, which reduces the nodes to be inspected by several orders of magnitude for large programs. The result is representated as a static object trace graph.

Here is the static object trace for sp.

This graph looks very much like a standard control flow graph. So what is new? Well, it is true that this graph is a projection of the original interprocedural and intraprocedural control flow graph where only the relevant nodes for one particular object are kept. The difficulty to obtain this graph is to locate the relevant nodes in the first place. Bauhaus locates these nodes by a global static data flow analysis that captures hidden accesses through pointers.

Now, let's analyze the static object trace for sp.

First, the object is created through the constructor new_stack on the heap using malloc and then initialized. After that, read_stack pushes several elements onto sp. Upon return of read_stack, an element is popped from sp.

Hm, now I see the problem: if the predicate in read_stack is wrong the first time it is evaluated, the push is not executed. The pop immediately following the prediate must fail.

Oh, there is another problem I just realize: sp is never deallocated from the heap. Oh boy, I found a memory leak.

Tests, like all dynamic analyses, give you a dynamic trace that is valid with respect to a certain input. The static traces in Bauhaus, on the other hand, give you all potential traces independent of the input.

Last modified: Thu Aug 28 16:30:29 MET DST 2003