InternalTypingException for Integer1Type

[mbenz89]

When jimplifying com.reddit.frontpage-214190.apk(Reddit v. 2.26.2), the following exception is thrown:

Exception in thread "main" Unexpected type null
	at soot.jimple.toolkits.typing.integer.ClassHierarchy.typeNode(ClassHierarchy.java:152)
	at soot.jimple.toolkits.typing.integer.TypeResolver.typeVariable(TypeResolver.java:121)
	at soot.jimple.toolkits.typing.integer.ConstraintCollector.caseAssignStmt(ConstraintCollector.java:406)
	at soot.jimple.internal.JAssignStmt.apply(JAssignStmt.java:242)
	at soot.jimple.toolkits.typing.integer.ConstraintCollector.collect(ConstraintCollector.java:104)
	at soot.jimple.toolkits.typing.integer.TypeResolver.collect_constraints_1(TypeResolver.java:209)
	at soot.jimple.toolkits.typing.integer.TypeResolver.resolve_step_1(TypeResolver.java:178)
	at soot.jimple.toolkits.typing.integer.TypeResolver.resolve(TypeResolver.java:147)
	at soot.jimple.toolkits.typing.fast.TypeResolver.inferTypes(TypeResolver.java:174)
	at soot.jimple.toolkits.typing.TypeAssigner.internalTransform(TypeAssigner.java:121)
	at soot.BodyTransformer.transform(BodyTransformer.java:55)
	at soot.BodyTransformer.transform(BodyTransformer.java:59)
	at soot.dexpler.DexBody.jimplify(DexBody.java:630)
	at soot.dexpler.DexMethod$1.getBody(DexMethod.java:119)
	at soot.SootMethod.retrieveActiveBody(SootMethod.java:401)
	at soot.PackManager$3.run(PackManager.java:1295)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1142)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:617)
	at java.lang.Thread.run(Thread.java:745)

This seems to occure because the soot.jimple.toolkits.typing.integer.ClassHierarchy does not have an entry for the Integer1Type in its typeNodeMap. The Integer1Type origins from the cast expression tmp$91006191 = ([0..1]) tmp$1547686471; in the following body:

   private void a(long, long)
   {
       com.danikula.videocache.ProxyCache $u7;
       long $u8, $u10;
       int $u1#2, $u0#3, $u0#4, $u0#5, $u3#6, $u3#7, $u4#8, tmp$91006191;
       java.lang.Object $u0#9, tmp$1547686471, tmp$1329378571, tmp$426070274, tmp$1096974924;
       float $u0#10, $u3#11, $u0#12, $u0#14;
       java.lang.Throwable $u0#15;

       $u7 := @this: com.danikula.videocache.ProxyCache;

       $u8 := @parameter0: long;

       $u10 := @parameter1: long;

       $u1#2 = 1;

       $u0#3 = $u10 cmp 0L;

       if $u0#3 != 0 goto label07;

       $u0#4 = 1;

    label01:
       if $u0#4 == 0 goto label08;

       $u0#5 = 100;

    label02:
       $u3#6 = $u7.<com.danikula.videocache.ProxyCache: int c>;

       if $u0#5 == $u3#6 goto label09;

       $u3#7 = 1;

    label03:
       $u4#8 = $u10 cmp 0L;

       if $u4#8 < 0 goto label10;

    label04:
       if $u1#2 == null goto label05;

       if $u3#7 == 0 goto label05;

       virtualinvoke $u7.<com.danikula.videocache.ProxyCache: void a(int)>($u0#5);

    label05:
       $u7.<com.danikula.videocache.ProxyCache: int c> = $u0#5;

       tmp$1547686471 = $u7.<com.danikula.videocache.ProxyCache: java.lang.Object a>;

       tmp$91006191 = ([0..1]) tmp$1547686471;

       $u1#2 = tmp$91006191;

       tmp$1329378571 = (java.lang.Object) $u1#2;

       entermonitor tmp$1329378571;

    label06:
       $u0#9 = $u7.<com.danikula.videocache.ProxyCache: java.lang.Object a>;

       virtualinvoke $u0#9.<java.lang.Object: void notifyAll()>();

       tmp$426070274 = (java.lang.Object) $u1#2;

       exitmonitor tmp$426070274;

       return;

    label07:
       $u0#4 = 0;

       goto label01;

    label08:
       $u0#10 = (float) $u8;

       $u3#11 = (float) $u10;

       $u0#12 = $u0#10 / $u3#11;

       $u0#14 = $u0#12 * 100.0F;

       $u0#5 = (int) $u0#14;

       goto label02;

    label09:
       $u3#7 = 0;

       goto label03;

    label10:
       $u1#2 = null;

       goto label04;

    label11:
       $u0#15 := @caughtexception;

       tmp$1096974924 = (java.lang.Object) $u1#2;

       exitmonitor tmp$1096974924;

    label12:
       throw $u0#15;

       catch java.lang.Throwable from label06 to label12 with label11;
   }

I think the cast should rather be to int since the left side of the assignment is an int and Integer1Type is not a real type but seems to be some helper type.

I'm not sure if the correct fix would be to adapt the ClassHierarchy to handle such special types as Integer1Type or if the problem is rather that the cast should not have such a special type in the first place.

@StevenArzt Have you seen this before? Any ideas?

[jpstotz]

@mbenz: I disagree with you that it should be an ´int`. In general the generated code is really looking strange:

tmp$1547686471 = $u7.<com.danikula.videocache.ProxyCache: java.lang.Object a>;
tmp$91006191 = ([0..1]) tmp$1547686471;
$u1#2 = tmp$91006191;
tmp$1329378571 = (java.lang.Object) $u1#2;

We have an java.lang.Object instance which is first casted to the Integer1Type [0..1] and two lines after it is casted back to an Object. I would guess that the generated code is just completely wrong, I would assume that the following shortened version would be correct:

tmp$1547686471 = $u7.<com.danikula.videocache.ProxyCache: java.lang.Object a>;
entermonitor tmp$1547686471;

However I wasn't able to get the app version you mentioned, therefore I don't know how the smali code looks.

I also encountered this bug in a different app: com.google.android.youtube V14.06.56 in method <jlj: void a(akqi,java.lang.Object)>. Instead ob Object in my case the problem arises when assigning Class variables. However in the end the type cast is also unnecessary.

BTW: Does anybody know what the Integer1Type is designed for? Unfortunately it's author Ben Bellamy was that sort of programmer who seem to prefer comment-free code, which makes it now hard to understand what the idea behind the Integer1Type is. Looking at the history in a branch before the Maven refactoring we again end up in the paper "Efficient Local Type Inference' at OOPSLA '08" - well known from #1053...

[jpstotz]

@mbenz During a short talk with Steven I got enlighted about the reason of this problem:

The problem "source" is $u1#2 . In the beginning of that method this variable is used as integer: $u1#2 = 1; Later this variable is however used as Object variable. Reusing a register isn't a big problem in dex, however Soot has to detect and split those multiple usages - and in this case it failed to split it up correctly. Therefore two variables with different types end up in one which can only fail.

Therefore the bug is located in the LocalSplitter or in the DexNullTransformer (tries to identify if an assignment by zero means $u1#2 =0 or $u1#2 = null).

[mbenz89]

@jpstotz you're completely right. Seems that I was a bit hasty on proposing a reason for this issue :).

As it turns out, we now know the underlying reason...always a good thing to have Steven around!

[jpstotz]

Looking at the code you posted I would assume that in your case the problem may be that DexNullTransformer is not aware of the commands entermonitor and exitmonitor which are clear indicators that the used variable has to be an Object instead of an int.
Edit: I checked my assumption, however the DexNullTransformer correctly handles entermonitor and exitmonitor staments.

Unfortunately in my case the problem is more complicated as I have code like this:

var1 = null;
var2 = null;
while (var1 == var2) {
    var1 = ...
    ...
    var2 = var1;
}

The problem is that var2 is never used in a way that clearly indicates that it is an object. The assignment and the comparison both work for int and Object. Only the fact that var1 has to be an Object makes it clear that var2 also have to be an Object, too. Therefore my problem is not located in the DexNullTransformer as it does not handle variable to variable assignments.

[jpstotz]

@mbenz OK, another try to solve this issue. I found a similar version com.reddit.frontpage at apkmirror.com that triggers this problem. The big advantage of your sample is that it happens in the class ProxyCache, a class where we can get the source code.

It turns out that the method triggering this issue consists of two methods on source code level, one seems to be inlined by the compiler:

    private void notifyNewCacheDataAvailable(long cacheAvailable, long sourceAvailable) {
        onCacheAvailable(cacheAvailable, sourceAvailable);

        synchronized (wc) {
            wc.notifyAll();
        }
    }

    protected void onCacheAvailable(long cacheAvailable, long sourceLength) {
        boolean zeroLengthSource = sourceLength == 0;
        int percents = zeroLengthSource ? 100 : (int) ((float) cacheAvailable / sourceLength * 100);
        boolean percentsChanged = percents != percentsAvailable;
        boolean sourceLengthKnown = sourceLength >= 0;
        if (sourceLengthKnown && percentsChanged) {
            onCachePercentsAvailableChanged(percents);
        }
        percentsAvailable = percents;
    }

The source of the problem is the assignment just at the beginning of the method: $u1#2 = 1;
Later $u1#2 is used as Object, therefore the my current assumption is that the LocalSplitter causes this issue. Looking at the smali code of this method I got to the conclusion that the statement $u1#2 = 1; has to be interpreted as boolean tmp = true. It is used for the line

boolean zeroLengthSource = sourceLength == 0; in this way

boolean localTrue = true;
if (sourceLength == 0) {  zeroLengthSource = localTrue; }

I just started to dig into LocalSplitter and it's dependencies. From my current understanding I would say that there is a problem in the SimpleLocalDefs when the variable is accessed in the catch part of a try-catch section. It returns two possible definition statements where only one should be returned. Thats all for today - I will continue tomorrow.

[jpstotz]

I think I now understand why soot is totally confused by this method. For understanding it is best to use the Jimple code before it has been processed by the LocalSplitter (the interesting part starts at label06):

private void a(long, long)
{
    unknown $u7, $u8, $u9, $u10, $u11, $u0, $u1, $u2, $u3, $u4, $u5, $u6, $u-1;
    $u7 := @this: com.danikula.videocache.ProxyCache;
    $u8 := @parameter0: long;
    $u10 := @parameter1: long;
    $u4 = 0L;
    $u1 = 1;
    $u2 = 0;
    $u0 = $u10 cmp $u4;
    if $u0 != 0 goto label07;
    $u0 = $u1;
 label01:
    if $u0 == 0 goto label08;
    $u0 = 100;
 label02:
    $u3 = $u7.<com.danikula.videocache.ProxyCache: int c>;
    if $u0 == $u3 goto label09;
    $u3 = $u1;
 label03:
    $u4 = $u10 cmp $u4;
    if $u4 < 0 goto label10;
 label04:
    if $u1 == 0 goto label05;
    if $u3 == 0 goto label05;
    virtualinvoke $u7.<com.danikula.videocache.ProxyCache: void a(int)>($u0);
 label05:
    $u7.<com.danikula.videocache.ProxyCache: int c> = $u0;
    $u1 = $u7.<com.danikula.videocache.ProxyCache: java.lang.Object a>;
    entermonitor $u1;
 label06: // try_start (start of synchronized)
    $u0 = $u7.<com.danikula.videocache.ProxyCache: java.lang.Object a>;
    virtualinvoke $u0.<java.lang.Object: void notifyAll()>();
    exitmonitor $u1;
    return; // end of synchronized section
 label07:
    $u0 = $u2;
    goto label01;
 label08:
    $u0 = (float) $u8;
    $u3 = (float) $u10;
    $u0 = $u0 / $u3;
    $u3 = 1120403456;
    $u0 = $u0 * $u3;
    $u0 = (int) $u0;
    goto label02;
 label09:
    $u3 = $u2;
    goto label03;
 label10:
    $u1 = $u2;
    goto label04;
 label11: // catch handler -> inside the try-catch section WTF!!!
    $u0 := @caughtexception;
    exitmonitor $u1;
 label12: // try end
    throw $u0;
    catch java.lang.Throwable from label06 to label12 with label11;
}

The important line is the last one: catch java.lang.Throwable from label06 to label12 with label11;. In my understanding this is bad code:

1. The try-catch region includes the catch block that handles the Exception. If the catch block would throw an Exception this should lead to an endless creation of Exceptions.

2. The try-catch section is to make sure that if inside the synchronized block en Exception occurs the `exitmonitor´ is always called - a bit like this code:

    try {
        entermonitor X;
        // do something
        exitmonitor X;
    } catch (Throwable t) {
        exitmonitor X;
    }       

However the try-catch section in this case also includes the blocks from label07 to label11 which is wired because this code belongs to code that is executed outside of the synchronized block and therefore should not be covered by the try-catch exception handler.

This confuses the LocalSplitter when processing exitmonitor $u1;in the label11 block. Inside the try-catch section $u1; is used as Object (label06 block) and as well as int/boolean (label07 to label11).

Therefore splitting of $u1 totally fails and in the end causes this error. At the moment I am not sure how we could proceed to resolve such code in a way that in the end correctly working Jimple code is created.

[jpstotz]

A short talk with Steven again explained a lot:

The reason for this strange try-catch structure is the Android code verifier. Whenever a synchronized respectively enetermonitor/exitmonitor block is contained within a method it requires such a structure. This is because the code verifier's implementation is plain dead simple that it can not handle multiple blocks within a method and in the end verify that exitmonitor is always be called on all code paths. Therefore the folks at Google had decided that calling exitmonitor on something else (whatever is at the moment stored in the used register) and such a try-catch block has to be present and cover everything starting after entermonitor to the end of the method.

Soot has at the moment two classes that deal with such situations: TrapTightener and TrapMinimizer. However they are both executed long after the LocalSplitter. Furthermore I tested what happens if I move them before the LocalSplitter and the output wasn't what I expected.

Therefore from my perspective a final solution would be a new TrapTransformer to handle such cases:

1. identify the try-catch system in the method as a special one generated from a synchronized block (entermonitor and exitmonitor is used within the method and the catch handler effectively only contains the code exitmonitorand throws) .
2. Change the region covered by the catch handler to only the statements after entermonitor and before exitmonitor (in our example this would be the code section from label06 to one statement before label07. The other sections don't have to be included in the try-catch block. Of course this totally changes the way the code might be executed but as we know that this is a try-catch block with the only purpose of ensuring the call of exitmonitor I think we can perform such a modification.

After transforming the method the proposed way the LocalSplitter could successfully do it's work and split $u1 correctly.

[mbenz89]

Wow! Thanks for the in-depth investigation, Jan!
Your problem description and solution proposal seem on point and makes sense to me.
Are you planning to implement the fix yourself?

[jpstotz]

Originally I thought analyzing your issue case would help me on my issue, too (the com.google.android.youtube app) . And saving my thoughts to the issue tracker is a necessity for me to track the "current state" as I often get interrupted by other tasks.
Unfortunately I had to realize that both cases have the same error message but besides that not much in common :(
However I learned a lot on the Soot internals...

I tried to create a fix, but it is not that simple (especially when multiple synchronization blocks are contained in one method). At the moment my schedule does not leave much time to work on soot therefore I can't promise anything - sorry.

[mbenz89]

I completely understand that and, unfortunately, have the same issues here...
Thanks for your input anyway!

[pavanupb]

@jpstotz How can we handle for the below case:

public final void a(com.google.android.gms.common.api.ResultCallback)
{
    unknown $u5, $u6, $u0, $u1, $u2, $u3, $u4, $u-1;

    $u5 := @this: com.google.android.gms.common.api.internal.zzs;

    $u6 := @parameter0: com.google.android.gms.common.api.ResultCallback;

    $u0 = 1;

    $u1 = 0;

    $u3 = $u5.<com.google.android.gms.common.api.internal.zzs: java.lang.Object a>;

    entermonitor $u3;

    if $u6 != 0 goto label03;

    $u0 = 0;

 label01:
    $u5.<com.google.android.gms.common.api.internal.zzs: com.google.android.gms.common.api.ResultCallback g> = $u0;

    exitmonitor $u3;

 label02:
    return;

 label03:
    $u2 = $u5.<com.google.android.gms.common.api.internal.zzs: boolean l>;

    if $u2 != 0 goto label08;

    $u2 = $u0;

 label04:
    $u4 = "Result has already been consumed.";

    staticinvoke <com.google.android.gms.common.internal.zzbq: void a(boolean,java.lang.Object)>($u2, $u4);

    $u2 = $u5.<com.google.android.gms.common.api.internal.zzs: com.google.android.gms.common.api.internal.zzdi p>;

    if $u2 != 0 goto label09;

 label05:
    $u1 = "Cannot set callbacks if then() has been called.";

    staticinvoke <com.google.android.gms.common.internal.zzbq: void a(boolean,java.lang.Object)>($u0, $u1);

    $u-1 = virtualinvoke $u5.<com.google.android.gms.common.api.PendingResult: boolean d()>();

    $u0 = $u-1;

    if $u0 == 0 goto label10;

    exitmonitor $u3;

    goto label02;

 label06:
    $u0 := @caughtexception;

    exitmonitor $u3;

 label07:
    throw $u0;

 label08:
    $u2 = $u1;

    goto label04;

 label09:
    $u0 = $u1;

    goto label05;

 label10:
    $u-1 = virtualinvoke $u5.<com.google.android.gms.common.api.internal.zzs: boolean a()>();

    $u0 = $u-1;

    if $u0 == 0 goto label12;

    $u0 = $u5.<com.google.android.gms.common.api.internal.zzs: com.google.android.gms.common.api.internal.zzu b>;

    $u-1 = specialinvoke $u5.<com.google.android.gms.common.api.internal.zzs: com.google.android.gms.common.api.Result g()>();

    $u1 = $u-1;

    virtualinvoke $u0.<com.google.android.gms.common.api.internal.zzu: void a(com.google.android.gms.common.api.ResultCallback,com.google.android.gms.common.api.Result)>($u6, $u1);

 label11:
    exitmonitor $u3;

    goto label02;

 label12:
    $u5.<com.google.android.gms.common.api.internal.zzs: com.google.android.gms.common.api.ResultCallback g> = $u6;

 label13:
    goto label11;

    catch java.lang.Throwable from label01 to label07 with label06;
    catch java.lang.Throwable from label10 to label13 with label06;
}

Should the first catch handler include the statements from if "$u6 != 0 goto label03"(Since it is after the enter monitor statement); till exitmonitor $u3; in label 05 as that would be the last exit monitor statement.
For the second catch handler should we modify it to include statements only till exitmonitor $u3; in label 11 or should we just leave it unchanged.

[jpstotz]

@pavanupb Looks like the compiler optimized the code and therefore the different blocks are not ordered in a way that would make it simple for us.

For the second catch handler should we modify it to include statements only till exitmonitor $u3; in label 11 or should we just leave it unchanged.

But then the block of label12 would be not covered by a catch-handler. Therefore if you change the second catch handler as you propose you have to add a third one for label12 - label13.

One problem I can see is that the blocks of label08 and label09 are not covered by any catch handler, although they clearly are inside the synchronized block. Looks like the compiler knew that an simple assignment of locals/registers can not fail and excluded those sections from the catch blocks. I would assume that this may confuse soot a lot.
If it really makes problems we have to move the second catch-handler begin from label10 to label08 (extending the catch section upwards).

However I have to admit that I don't in detail what cases soot can or can not handle well.