[Soot-list] ExceptionalUnitGraph and nested traps
John Jorgensen
jorgensen.john at gmail.com
Tue Jan 1 15:44:35 EST 2013
Hello Michael,
As the person who re-implemented exception analysis back in 2003, I can
provide some background for the conservative reporting that Pat describes
(though, of course, I may be misremembering some of the details, so you
should check what I'm about to say against your own explorations).
If you use a pessimistic, legalistic interpretation of the JVM
specification (at least as it stood in 2003) all the successor edges in
your example could happen, and it is, in principle, possible that a thread
could leave the metnod without unlocking "this".
For more detail about this issue than you probably want, see the Sable
technical report
2003-3<http://www.sable.mcgill.ca/publications/techreports/sable-tr-2003-3.pdf>,
especially sections 2.3 and 2.4. The main issues are
- that InternalError exceptions (and perhaps other subtypes of
VirtualMachineError) can be thrown "asynchronously", as a result of the VM
encountering problems that have nothing to do with the code being executed
in the current thread.
- when an instruction A may throw an exception to handler H, then the CFG
needs to include edges from all the predecessors of A to H, so that
dataflow analyses using the CFG reflect the fact that the flow of control
can reach H without performing all of the state changes implied by
instruction A (because A was interrupted before its completion).
- when an instruction A may thrown an exception to handler H, and A may
have side-effects, then there needs to be an edge from A itself to H, in
addition to the edges from A's predecessors, so that dataflow analyses
using the CFG reflect the fact that some state changes implied by
instruction A may have occurred when control reaches H, even if A is
interrupted before its completion. (This applies to the invocation of
currentTimeMillis() in your example, since the exception analysis is not
interprocedural, so it has to assume currentTimeMillis() may have
side-effects)
So, with that background, let's look at your example. say
currentTimeMillis() throws some exception, which is caught by the handler
starting with
label3: $r5 := @caughtexception;
but then in the midst of the assignment to $r5, the JVM throws an
InternalError (I don't know... maybe the JVM's in a phone whose battery is
about to drain completely, and the JVM throws an InternalError as the
lights go out...) so the assignment to $r5 doesn't happen, and the
InternalError is thrown to
label8: $r6 := @caughtexception;
before the execution of
label4: exitmonitor r3;
and "this" is never unlocked.
I concede that this story is clearly not what is intended to happen (if it
were, section 3.14 "Synchronization" would not supply the example
implementation of synchronized blocks that it does), but I don't see how
the JVM specification (at least as of 2003) would rule it out.
I suspect that, in practice, JVM implementations somehow delay the delivery
of asynchronous exceptions to unproblematic points. And even if they
didn't, an asynchronous exception probably signals a condition so dire that
the executing program is about to terminate abruptly anyway. So you might
sensibly choose to ignore them even if you accept this pessimistic
interpretation of the specification.
The cleanest way to do that is probably to implement your own
ThrowAnalysis, likely as a minor variant on UnitThrowAnalysis which does
not assume that all instructions can throw any of the exceptions designated
as VM_ERRORS in soot.toolkits.exceptions.ThrowableSet and
soot.toolkits.exceptions.UnitThrowAnalysis.
(Throughout this response, I've been assuming that you're using soot's
--trim-cfgs option, since otherwise you'll be using PedanticThrowAnalysis,
which assumes every instruction can throw every exception all the time. If
you decide to add a new ThrowAnalysis, I recommend using soot's
"--dump-cfgs" option to generate dot graphs to help you visualize the
results. And if you do that, be warned that the jb.uce phase always uses
PedanticThrowAnalysis, to ensure that the unreachable code eliminator won't
delete any unreachable handlers. That's something that I forgot myself,
until looking a a CFG dumped by the jb.uce phase reminded me.)
Note that in the jimple representation of your particular example, at least
some of the problematic edges would go away if one simply said that
exceptions are never thrown by Jimple's IdentityStmt instructions (which
you could justify on the basis that they simply record the assignment of
parameters to a register standing for a stack location, and do not
represent any actual bytecode in the analyzed program). But that's not a
general solution to the underlying issue (the Baf representation of your
example, includes a pop instruction that corresponds to real bytecode
within the catch block, but before the exitmonitor, so that instruction
could theoretically be executing when an asynchonous exception happens).
On Mon, Dec 31, 2012 at 9:30 AM, Patrick Lam <plam at sable.mcgill.ca> wrote:
> Hi Michael,
>
> It looks to me like the ExceptionalUnitGraph is conservatively reporting
> possible successor edges that never actually happen. That's not wrong,
> but it would be better if it were more precise. I suspect that there's
> no easy way to fix it short of fixing the ExceptionalUnitGraph creation
> code or running a subsequent pass to clean it.
>
> pat
>
> On 12/31/12 09:29, Michael Faes wrote:
> > Hi everyone,
> >
> > I'm going to use Soot (2.5.0) for a deadlock analysis as part of my
> > Master's thesis and I'm currently experimenting with the data flow
> > analysis framework and the ExceptionalUnitGraph.
> >
> > Here is my problem: I found that if there are any nested traps around a
> > statement, the ExceptionalUnitGraph has edges from that statement to
> > both trap handlers instead of only to the inner one.
> >
> > Here is an example. This method:
> >
> > public void foo() {
> > synchronized(TestClass.class) {
> > synchronized(this) {
> > System.currentTimeMillis();
> > }
> > }
> > }
> >
> > is converted to Jimple like this:
> >
> > public void foo()
> > {
> > deadlockfinder.test.TestClass r0, r3;
> > java.lang.Class $r1, r2;
> > java.lang.Throwable $r5, $r6;
> >
> > r0 := @this: deadlockfinder.test.TestClass;
> > $r1 = class "deadlockfinder/test/TestClass";
> > r2 = $r1;
> > entermonitor $r1;
> > label0:
> > r3 = r0;
> > entermonitor r0;
> > label1:
> > staticinvoke<java.lang.System: long currentTimeMillis()>();
> > exitmonitor r3;
> > label2:
> > goto label6;
> > label3:
> > $r5 := @caughtexception;
> > label4:
> > exitmonitor r3;
> > label5:
> > throw $r5;
> > label6:
> > exitmonitor r2;
> > label7:
> > goto label11;
> > label8:
> > $r6 := @caughtexception;
> > label9:
> > exitmonitor r2;
> > label10:
> > throw $r6;
> > label11:
> > return;
> >
> > catch java.lang.Throwable from label1 to label2 with label3;
> > catch java.lang.Throwable from label4 to label5 with label3;
> > catch java.lang.Throwable from label0 to label7 with label8;
> > catch java.lang.Throwable from label9 to label10 with label8;
> > }
> >
> > Note the trap that spans from label1 to 2 and the one that spans from
> > label0 to 7.
> >
> > When printing the predecessors of each statement, I get the following
> > for the statement "$r6 := @caughtexception;" after label8:
> >
> > exitmonitor r3
> > goto [?= exitmonitor r2]
> > $r6 := @caughtexception
> > exitmonitor r2
> > r3 = r0
> > entermonitor r0
> > exitmonitor r3
> > throw $r5
> > $r5 := @caughtexception
> > exitmonitor r2
> > entermonitor $r1
> > staticinvoke<java.lang.System: long currentTimeMillis()>()
> > ^^^
> >
> > As you can see, the graph adds the possibility to go from
> > currentTimeMillis() directly to the outer trap handler. Because of this,
> > my deadlock analysis concludes that it is possible for a thread to leave
> > this method without unlocking "this".
> >
> > Now, my questions: Am I right that this is undesired behavior? Is there
> > a way to fix this?
> >
> > Thank you so much in advance.
> >
> > Best regards,
> > Michael
> > _______________________________________________
> > Soot-list mailing list
> > Soot-list at sable.mcgill.ca
> > http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20130101/7753ec46/attachment.html
More information about the Soot-list
mailing list