5

Are there any tools, libraries, or frameworks to get the control flow graph of a C program, and find the worst possible path a program can take?

When I read the other questions related to control flow graphs, I came across a few tools which can generate the control flow graph. Is there any way to use them to find the worst possible path?

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
Hari Krishna
  • 551
  • 6
  • 21
  • as i hav already accepted an answer, let me add a note, Understand 2 by [link](http://scitools.com) and its c, perl , python api's help getting a cgf very easy, – Hari Krishna Jan 26 '12 at 17:31

2 Answers2

1

If the graph will ever have loops in it, then no -- there isn't a foolproof way to figure this, as the question is equivalent to the halting problem. Short version: it's impossible for a program, given an arbitrary other program, to even determine whether it will ever return. You could possibly determine potential infinite loops, but the only way to be anywhere near certain is to actually run the program with an exhaustive set of inputs.

cHao
  • 84,970
  • 20
  • 145
  • 172
0

You will probably be in interested in Worst Case Execution Time which, if succesful, in some sense must have found your worst control flow path.

Regarding libaries for computing C control flow graphs, see our flow analysis support for DMS for C and other languages,

Ira Baxter
  • 93,541
  • 22
  • 172
  • 341