[Soot-list] ExceptionalUnitGraph and nested traps
Michael Faes
rolve at trick17.ch
Wed Jan 2 08:12:24 EST 2013
Hi John (and Patrick),
Thank you so much for your detailed answer. It seems like this exception
business is considerably more complicated than I thought.
As you suggested, I copied the UnitThrowAnalysis and removed some of the
exceptions that are not relevant for my analysis. And in case this
proves to be not enough to resolve the issue, I'm just going to make the
analysis assume that all objects are unlocked when a method returns.
I encountered one more issue though. What is the correct way to set my
custom analysis as the default throw analysis? I tried the following in
my main method:
Options.v().set_via_shimple(true);
Options.v().set_omit_excepting_unit_edges(true);
Scene.v().setDefaultThrowAnalysis(new NoVmErrorsThrowAnalysis());
PackManager.v().getPack("stp").add(
new Transform("stp.deadlock", new MethodSummarizer()));
Main.main(args);
but I get this exception:
java.lang.IllegalStateException: RefType
java.lang.RuntimeException not loaded. If you tried to get the RefType
of a library class, did you call loadNecessaryClasses()? Otherwise
please check Soot's classpath.
at soot.Scene.getRefType(Scene.java:467)
at soot.toolkits.exceptions.ThrowableSet$Manager.<init>
at soot.Singletons.soot_toolkits_exceptions_ThrowableSet_Manager
at soot.toolkits.exceptions.ThrowableSet$Manager.v
at soot.toolkits.exceptions.NoVmErrorsThrowAnalysis.<init>
at deadlockfinder.DeadlockFinder.main
And when adding Scene.v().loadNecessaryClasses(); before creating the
analysis, I get another exception:
java.lang.RuntimeException: This operation requires resolving level
SIGNATURES but deadlockfinder.test.TestClass is at resolving level HIERARCHY
If you are extending Soot, try to add the following call before calling
soot.Main.main(..):
Scene.v().addBasicClass(deadlockfinder.test.TestClass,SIGNATURES);
Otherwise, try whole-program mode (-w).
at soot.SootClass.checkLevel(SootClass.java:125)
at soot.SootClass.addMethod(SootClass.java:574)
at soot.coffi.Util.resolveFromClassFile(Util.java:255)
at soot.CoffiClassSource.resolve(CoffiClassSource.java:39)
at soot.SootResolver.bringToHierarchy(SootResolver.java:215)
at soot.SootResolver.bringToSignatures(SootResolver.java:239)
at soot.SootResolver.processResolveWorklist(SootResolver.java:154)
at soot.SootResolver.resolveClass(SootResolver.java:124)
at soot.Scene.loadClass(Scene.java:448)
at soot.Scene.loadClassAndSupport(Scene.java:433)
at soot.Scene.loadNecessaryClass(Scene.java:1053)
at soot.Scene.loadNecessaryClasses(Scene.java:1067)
at soot.Main.run(Main.java:167)
at soot.Main.main(Main.java:141)
at deadlockfinder.DeadlockFinder.main(DeadlockFinder.java:22)
It get the feeling that I'm doing something very basic wrong.
Thanks for your time.
Michael
-------- Original-Nachricht --------
Betreff: Re: [Soot-list] ExceptionalUnitGraph and nested traps
Von: John Jorgensen <jorgensen.john at gmail.com>
An: Patrick Lam <plam at sable.mcgill.ca>, Michael Faes <rolve at trick17.ch>
Datum: 01.01.2013 21:44
> 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
> <mailto: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 <mailto: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 <mailto:Soot-list at sable.mcgill.ca>
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>
>
More information about the Soot-list
mailing list