Register colouring still producing invalid code

[brazdil]

Original code: http://pastebin.com/5Emb4Fci
Instrumented code: http://pastebin.com/x1u1cGYs
Compiled code: http://pastebin.com/kNbd2Zct
APK: same as issue #22

The problem is at the very beginning of the method. The call to Intent.getComponent returns a result which is immediately used as an argument of ComponentName.getClassName. Instrumentation seems to lack non-throwing semantics for taint assignment of the result, which I'll fix later today, but it should not pose a problem in this particular case. The problem is that in the compiled code, the register (v3) is overwritten between the MOVE_RESULT and INVOKE (line 89), properly resuling in a verification error.

[xurubin]

OK I think it is another exception handling thing.
Original ROP method: http://pastebin.com/B2bJ7zYb
SSA representation: http://pastebin.com/490r7Wg4

Checkout v14 in the rop code:
one definition of v14 is android/content/ComponentName, and it is living along this chain:
block 0030 -> 0039 -> 003b -> 01bd
Another definition of v14 is java/lang/string, following this:
block 0043 -> 004c -> 004e -> 01bd

0202 is a catchall block and the two conflicting live v14 both reaches this point, which makes the SSA put a phi instruction (v262 in the ssa code) here and they will be allocated the same register, leading to collision.

I've added a helper method DexCodeGeneration.dumpSSA which is what I used to create the SSA dump. Being able to display phi with the ssa form should be very useful in future debugging. By stepping into com.android.dx.ssa.Optimizer.optimize() you can access the internal SsaMethod object being operated on. Use Eclipse's Display view to evaluate command 'com.rx201.dx.translator.DexCodeGeneration.dumpSSA(ssaMeth)' in order to print out the dump.

[xurubin]

Having spent 4 hours on this, I think now I know a bit more about the bug. The spurious move is introduced when SSA is removing phi instructions. The way phi is removed is by introducing move instructions to the end of all predecessors, moving the real register of phi's source to the real register of the phi reg. Hence, if a spurious control flow path from a basic block to the phi's block is introduced, a spurious move will appear. In this particular example, the phi is on the taint register t1.

This particular control flow path is a unguarded clearVisited(), which got captured by the original code's catch (Exception e).

[brazdil]

Hmm, I still don't see how that would be a problem. Provided we talk about the same piece of code (the ones I sent you in the email, with the latest code the error occurs later and on t3), then the original code contained a call to getComponent inside the TRY block you mention. Hence there is an exception path to the catch handler at that point (i.e. just before the INVOKE). By inserting a call to clearVisited, that path is merely duplicated... I could wrap it in a TRY block with an empty handler, but how would that change anything?

I must be missing something, because the resulting code wraps the consecutive calls to clearVisited and Taint.get (which fall into the original TRY block) into two separate TRYs, where the handler for the one wrapping get does the PHI moving even though it must have been done before...

[xurubin]

OK I may have a temporary workaround for this. In SsaConverter.java:

    private static void edgeSplit(SsaMethod result) {
        edgeSplitPredecessors(result);   <--- 1
        edgeSplitMoveExceptionsAndResults(result); <--- 2
        edgeSplitSuccessors(result);
    }

Swap statement 1 and 2. This will split a catch block with multiple predecessors into multiple blocks. The downside is code bloat, but it seems to solve the spurious move issue, as well as another one which is move-exception becoming the target of a Goto.

BTW, the different treatment of clearVisited and Taint.get is due to SsaConverter.needsNewSuccessor(), although I have absolutely no idea what this function does and why it does it.

Now we can keep going, and the next issue I see is:

java.lang.ClassCastException: uk.ac.cam.db538.dexter.aux.struct.TaintImmutable$$1
E/AndroidRuntime(11569):    at android.support.v4.app.FragmentManagerImpl.attachActivity(SourceFile:173)

But that looks like some straightforward instrumentation bug. Line 173 of FragmentManagerImpl is check-cast v3, Luk/ac/cam/db538/dexter/aux/struct/TaintInternal$$1;

[brazdil]

DUDE! You're a true hero! How the heck did you figure that out? Still curious why it's doing that... :-/
I've fixed the bug you mention at the end and now have Google Keep running !!!

[arb33]

On 26/09/2013 12:02, David Brázdil wrote:

DUDE! You're a true hero! How the heck did you figure that out? Still
curious why it's doing that... :-/
I've fixed the bug you mention at the end and now have Google Keep
running !!!

That's fantastic news. I look forward to trying it with other
applications. :-)

Alastair.

[brazdil]

Still experiencing an exception in JSON reader when notes are synced, but apart from that runs perfectly - very encouraging... Was a bit worried that the different signature might prevent it from logging into Google account but it doesn't seem to bother.