[Soot-list] Question on the DEF/USE analysis

[CREGUT Pierre RD-MAPS-LAN]

First thank you for your very detailed answer.

To give a bit of context, I am writing a translator from Android 
bytecode to Jimple.
Doing this I discover oddities of the Dalvik VM with respect to regular 
Java VMs.

John Jorgensen a écrit :
>     cregut> To avoid this, I have added a version of the
>     cregut> ExceptionalUnitGraph class where
>     cregut> "allvaysAddSelfEdges" is false (mightHaveSideEffect
>     cregut> is static and cannot be overridden).
>
> It's been a few years since I was familiar with this code, but if
> you are using soot from the command line, I think you can just
> use the "-omit-excepting-unit-edges" command line option (or more
> likely "-trim-cfgs", which implies "-omit-excepting-unit-edges")
> to turn off alwaysAddSelfEdges, without having to replace
> the ExceptionalUnitGraph implementation.
>   
In fact, no, in the code of ExceptionalUnitGraph, you have :      
 boolean alwaysAddSelfEdges = ((! omitExceptingUnitEdges) ||
                      mightHaveSideEffects(thrower));
So you have to have both omitExceptingUnitEdges to true and 
mightHaveSideEffects
to false to get rid of the behavior.
> The command line option effectively changes
> the default value of one of the ExceptionalUnitGraph's
> constructor; the Soot.Options class probably provides
> programmatic methods to change the default value without
> specifying the command line option, but I haven't looked into
> that.
>
>     cregut> This is true as long as the definition effect 
>     cregut> occurs after any potential exception has been raised for all the 
>     cregut> statements of the intermediate language. I think this is true in Jimple.
>
>     cregut> Am I wrong, or is this something that could be modified to make the 
>     cregut> def/use analysis more precise ?
>
> I think you're right (that's the reason "-trim-cfgs" and
> "-omit-excepting-unit-edges" exist).  But there are at least two
> caveats:
>   
I think you have raised a different but related issue. We have 
exceptions caused by the instruction itself and
we have exceptions caused by the code called by the instruction.
If we have a jimple instruction
     x = m(...)
we have at least two JVM instructions.
- One for the invoke that may fail because of m (the side effect)
- One that modifies x that can only fail if it has its own problems (in 
fact it may be just the result being there on the stack).

The question of omit-excepting-unit-edges is related to the second case 
(and there is a second question which is when (after or before the 
assignment)). Still we have the first case that has no sense for the 
def/use analysis. if an exception is raised in m, the assignment is not 
done. From the point of view of the def/use analysis the jimple 
instruction occurs after the exception.
> - I've never seen a definitive specification of when asynchronous
>   exceptions may be delivered (ThreadDeath and InternalError are
>   asynchronous, meaning them may be delivered to a thread at
>   arbitrary points unrelated to the particular instructions the
>   thread is executing).  So it's conceivable that if your
>   assignment were the last instruction within a try block whose
>   catch catches Throwable (i.e., it catches the asynchronous
>   exceptions) and that an asynchronous exception happens to be
>   raised just as the assignment completes, then some JVMs might
>   deliver the asynchronous exception to the catch block even after
>   completing the assignment to the LHS of the statement being
>   executed when the exception occurred (I agree that this is an
>   unlikely interpretation, but I'm not sure the JVM specification
>   disallows it).
>
> - When I checked seven years ago, the bytecode verifiers in JVMs
>   performed their verifications on the assumption that all
>   instructions within a try block had the potential to throw an
>   exception to the catch.  As a consequence, basing optimizations
>   on CFGs which eliminated edges corresponding to unrealizable
>   exceptions could result in unverifiable code (see sections 2.6
>   and 3.4 of
>   http://www.sable.mcgill.ca/publications/techreports/#report2003-3
>   for details).  
>   
This is very interesting. I will read your report.
Clearly this kind of assumptions has been changed for the Android VM. 
The Dalvik VM does not throw an exception if there is no explicit 
runtime exception mentioned for the corresponding bytecode in the JVM 
spec. Even more, the Dalvik VM assumes that a return cannot raise an 
exception (even if the JVM return does when there is an unbalanced 
monitor enter).  Otherwise most bytecode programs could not be typed.
>   Soot includes a hack (the "Trap Tightener" in the jb.tt pass)
>   to reduce the likelihood of such unverifiable code, but the
>   hack does not eliminate the possibility.
>
>   So it's conceivable that making the Def/Use analysis more
>   accurate might increase the possibility of generating
>   unverifiable code. I haven't thought through the details of
>   that, though.
>
>   
Ok, that probably means that it is only useful for my specific case not 
as a generic improvement for the bytecode.

There is a last question, the JVM and the Dalvik VM distinguishes 
"Throwable" and "<any>".
There can be a handler for both even if according to the VM 
specification, I do not see what
can be between any and Throwable which is the ancestor of both Errors 
and Exceptions.
Soot does not make any difference and convert to Throwable the handlers 
for any. As a result those
handlers are often dead code (and the splitter does not like this but 
this is another topic).
It may be the case that some implicit exceptions (internal errors) are 
considered as belonging to
(any \ Throwable) in  Dalvik.

-- 

*Pierre Cregut*
FT/RD/MAPS/DVC/JAVA
tél. +33 (0)2 96 05 19 76
pierre.cregut at orange-ftgroup.com <mailto:pierre.cregut at orange-ftgroup.com>


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20101007/af8a08ea/attachment-0001.html