3

Is it possible to determine all the possible execution paths by reading the bytecode of a given method, or will that be equivalent to trying to solve the halting problem? If it can't be reduced to the halting problem, then how far can I go with static analysis without crossing the boundary of trying to solve the halting problem?

Related question: "Finding all the code in a given binary is equivalent to the Halting problem." Really?

Community
  • 1
  • 1
plaureano
  • 3,139
  • 6
  • 30
  • 29

1 Answers1

5

Yes, this is easily equivalent to solving the halting problem. Consider the following if statement:

if (TuringMachine(x)) then goto fred;

OK, is it really possible to goto fred? You can only answer this question if you can analyze a Turing machine. There's an equivalent set of bytecodes for this.

Now, if the only problem is to determine all plausible paths, and you don't care if you get some false positives, the answer is No. Consider the following program:

if (false) then x else y ;

The possbile paths: eval(false);do x and eval(false);do y is a complete enumeration.

You have to treat loops specially, as zero, one, two, or some maximum bounded number of iterations, it you want a computable answer. If a loop can repeat forever, some of your paths will be infinitely long and you can't report them with a algorithm and finite time :-{

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