I want to generate a Program Dependence Graph (PDG) from C source code. I found papers that explain how do it, but all used the commercial CodeSurfer tool.
Are there any free tools or open source projects that can do this job?
In mathematics, computer science and digital electronics, a dependency graph is a directed graph representing dependencies of several objects towards each other. It is possible to derive an evaluation order or the absence of an evaluation order that respects the given dependencies from the dependency graph.
Frama-C is an Open Source static analysis platform with a slicer for C programs based on the computation of a Program Dependence Graph.
Note that slicing actual programs written in a real programming language such as C involves many special cases and concepts that are skimmed over in scientific publications. Still, I am confident that you won't find anything simpler than Frama-C's PDG computation, first because it is the only Open Source one available (that I know of), and second because any other PDG computation that handled C programs would have to solve the same problems and introduce the same concepts.
Here is one example:
int a, b, d, *p;
int f (int x) {
return a + x;
}
int main (int c, char **v) {
p = &b;
a = 1;
*p = 2;
d = 3;
c = f(b);
}
The command frama-c -pdg -pdg-dot graph -pdg-print t.c
generates dot files graph.main.dot
and graph.f.dot
containing the PDG of main()
and f()
respectively.
You can use the dot
program to pretty-print one of them thus: dot -Tpdf graph.main.dot > graph.pdf
The result is below:
Note the edge from the node c = f(b);
to the node *p = 2;
. A PDG computation claiming to be useful for C programs must handle aliasing.
On the other hand, a slicer using this PDG to slice on the criterion “inputs of statement c = f(b);
” would be able to remove d = 3;
, which cannot influence the function call, even through the pointer access *p
.
Frama-C's slicer uses the dependencies indicated by the PDG to keep only the statements that are useful for the user-specified slicing criterion. For instance, the command frama-c -slice-wr c t.c -then-on 'Slicing export' -print
produces the reduced program below, where the assignment to d
has been removed:
/* Generated by Frama-C */
int a;
int b;
int *p;
int f_slice_1(int x)
{
int __retres;
__retres = a + x;
return (__retres);
}
void main(int c)
{
p = & b;
a = 1;
*p = 2;
c = f_slice_1(b);
return;
}
If you like to visualize the dependencies of methods calling each other and are using gcc
then gcc
's option -fdump-rtl-expand
might be of interest to you.
For each source file you compile using the option -fdump-rtl-expand
gcc
will output a *.expand
file.
Those files fed to the tool egypt produce graph(s) showing the method's dependencies.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With