[Soot-list] Reachability in CFGs

[John Jorgensen]

I'm going to change Irem's example a bit, to emphasize Chris
Pickett's point that you need to decide what you mean by "call"
when you say that m3() can't be executed without m2() being
called:

  m1();
  try {
    m2();
  } catch (Throwable t) {
    m3();
  }

I changed the caught type from Exception to Throwable so that the
catcher will catch the Error types that signal problems in the
virtual machine. Now in addition to the possibility that the
invoke{interface,special,static,virtual} instruction might throw
an exception, there's the possibility that an asynchronous
InternalError (generated by something going wrong in the VM that
might have nothing to do with the currently executing code), or a
ThreadDeath (originating in another thread executing completely
different code) might be thrown to m3() at the moment of the
invocation of m2(), before any code within m2() executes.

I don't know how likely it is that real VMs would actually do
such a thing, but the specification allows it.  Of course, the
issue might not matter in whatever use you're making of the CFG.

    irem> Anyway, right now, what I do is to construct the 
    irem> ExceptionalUnitGraph, and check 
    irem> for each node in the graph:
    irem>  	for each of its exceptional successors in the graph:
    irem> 		whether the successor is a handler unit for one of the 
    irem> 		ExceptionalDests of the node
    irem> 		if this is so, 
    irem> 			I keep the edge between the node and successor 
    irem> 		else
    irem> 			I delete the edge

If you take this approach, be sure that the
omitExceptingUnitEdges parameter to ExceptionalUnitGraph's
constructor is false (i.e., don't specify
--omit-excepting-unit-edges if you're using Soot's command line,
nor --trim-cfgs, which is shorthand for 
"--throw-analysis unit --omit-excepting-unit-edges -p jb.tt enabled:true")

To illustrate why, let me change your example again, replacing
the invocations of m1() and m2() with assignments and changing
the catch parameter, to reduce the number of paths to the catch
block:

  b = 0;          // point A
  try {
    b = a[i];     // point B
  } catch (IndexOutOfBoundsException e) {
    m3();         // point C
  }

If you specify "--throw-analysis unit" and
"--omit-excepting-unit-edges", the resulting ExceptionalUnitGraph
will have an edge from A to C, but none from B to C.  That's what
you want if you're using the CFG for dataflow analysis, since it
allows the analysis to deduce that if m3() is invoked, b must
still have the value 0.

Then, as you've described your algorithm, I think it would leave you
with no edges leading to C at all.

(For the sake of strict accuracy, I should mention that if you
actually ran the example through soot, the single Java statement
at B would be turned into multiple Jimple instructions, so the
edge to the handler would likely not originate from the
instruction corresponding to point A in the example, but instead
from an assignment to some stack temporary. But you get the idea:
there would still be only one edge if you used
--omit-excepting-unit-edges.)

    irem> I think this was not the case for certain earlier versions, and I
    irem> inherited a code that worked fine with them. But now I have to
    irem> manipulate the CFGs given by soot to reflect reachability better.

This surprises me, since I don't think there have been many
changes to the exceptional control flow analysis since it was
integrated into Soot's trunk (release 2.2 in Dec 2004).  Could it
be that the changed behaviour has to do with using a different
set of arguments to graph constructors? Did you perhaps recently
start using --trim-cfgs or --omit-excepting-unit-edges?