what information we can get from a control flow graph?

Question

I have got a control flow graph of a trace of a C program(executed in a VM) which is highly complicated.I want to know what information can i extract if i have a CFG of a program trace apart from control dependencies ! Thank you

Answer 1

There a distinction to be made here:

• A control flow graph is an approximation to the program's control. A control flow graph can tell you, for any run of the program, where might control flow. It is entirely feasible that the program may never execute a certain edge of the graph:

  i := 23;
  x := some_complicated_function_returning_zero();
  if (x < i) {
     print "Hello, world!";
  }  else {
     print "Bad!";
  }
  

in that program, the else branch will never be executed, however program analysis tools will generally report that there is a control flow edge to both sides of the branch. This is because program analysis is approximate.

• A trace of the program is a traversal of edges in the program's control flow graph. A good set of tests will generally have tests which cover many of the possible control flow paths (or at least, those that are feasible, up to the imprecision in the control flow graph's construction), but beyond that, test cases which cover a wide range of the values that things like variables take within those execution paths.

A trace will let you see, how did the program execute for a single run, while a control flow graph will allow you to say "what are the possible ways that my program could execute."

Real programs are large, and therefore a control flow graph of an entire program will be extremely large, however, a trace will be considerably smaller, because of the fact that you don't have the exponential branching effect...