[Soot-list] Reachability in CFGs

[irem]

VMerrors and the like: As you have guessed, I am not interested in
these. I am interested in the "correctness" (correctness w.r.t. a
property I define) of the program. The programmer can not totally avoid
VM errors therefore these do not concern me and for now I assume
single-threaded applications.

> 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")

This I actually plan to solve the other way round. I delete the
exceptional edges that are not to handlers contained in
ExceptionalDests. And I plan to add edges to handlers that are contained
in the handlers of ExceptionalDests if they are not already there. I
think this would solve the problem? Else, I end up with the pedantic
analysis which is not so informative for me.

So for this example:

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

I would add an edge from point B to C looking at the handlers available
for exceptions at point B. Hopefully, they include point C.


I meant the CompleteUnitGraph. I thought this was more in the shape I
wanted. But I am not sure about this. We weren't analyzing exceptional
behavior before in detail and I wasnt the one that wrote the code. Sorry
if I blurred any minds.

Thanks a lot, 

Irem  

On Sun, 2007-11-04 at 21:51 -0600, John Jorgensen wrote:
> 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?