Endless loop in soot.jimple.toolkits.typing.fast.TypeResolver.typePromotion()

[jpstotz]

Please examine each of the following points so that we can help you as soon and best as possible.

Describe the bug

When trying to load the body of a certain method Soot ends up in an endless loop soot.jimple.toolkits.typing.fast.TypeResolver.typePromotion()

VisualVM shows where soot is stuck:

Input file
The affected APK, stripped down to the relevant classes.dex file (the original has 21 dex files)
tt dex only.apk.zip

To reproduce

Load the APK into soot (latest develop branch) and try to load the body of method u in class X.Da5.
I have used this test code:

String classToLoad = "X.Da5";
String methodToLoad = "u";
File apkFile = new File("tt dex only.apk");

Options o = Options.v();
o.set_exclude(Collections.emptyList());
o.set_verbose(true);
o.set_process_multiple_dex(true);
o.set_no_bodies_for_excluded(true);
o.set_allow_phantom_refs(true);
o.set_whole_program(true);
o.set_process_dir(List.of(apkFile.getAbsolutePath()));
o.set_prepend_classpath(false);
o.set_process_multiple_dex(true);

o.set_android_jars(ANDROID_JARS_DIR);
o.set_src_prec(Options.src_prec_apk);

Main.v().autoSetOptions();
Scene.v().loadNecessaryClasses();
System.out.println("loadNecessaryClasses finished");

SootClass sootClass = Scene.v().getSootClass(classToLoad);
List<SootMethod> allMethods = sootClass.getMethods();
List<SootMethod> selectedMethods = allMethods.stream().filter(m -> methodToLoad.equals(m.getName())).toList();
if (selectedMethods.isEmpty()) {
	throw new RuntimeException("No method named " + methodToLoad+" in class " + classToLoad); 
}
if (selectedMethods.size()>1) {
	throw new RuntimeException("Multiple methods named " + methodToLoad+" in class " + classToLoad); 
}
SootMethod sm = selectedMethods.get(0);
Body b = sm.retrieveActiveBody();
System.out.println("finished"); // never reached

Expected behavior
Typing finishes at least after a few minutes

[jpstotz]

This is the Jimple code of the method before TypeResolver starts working on it. The local that prevents TypeResolver from finishing is local:$u1#15#5.

    public final boolean u(com.ss.android.ugc.aweme.sticker.data.InteractStickerStruct)
    {
        com.ss.android.ugc.aweme.sticker.data.InteractStickerStruct $u9;
        com.ss.android.ugc.aweme.feed.model.Aweme $u3;
        boolean $u-1#21;
        com.ss.android.ugc.aweme.addyours.model.AddYoursAvatar[] $u0#13, $r0;
        java.io.Serializable $u1#15#5, $r1, $r3, $r5;
        java.util.List $u-1#12;
        X.EH3 $u6;
        android.content.Context $u1#1;
        java.lang.Object[] $u-1#14;
        X.Da5 this;
        bottom_type $u5#3, $u1_5#5, $u4#6, $u1_1#10, $u1#15, $u1_4#19;
        android.os.Parcelable[] $r2, $r4;
        int $u-1#9, $u1_1#10#4;
        com.ss.android.ugc.aweme.profile.model.User $u-1#8, $u-1#22;
        java.lang.String $u-1#23, $u5#3#1, $u1_5#5#2, $u4#6#3, $u1_4#19#6;
        X.6yB $u0#18;
        com.ss.android.ugc.aweme.addyours.model.AddYoursTopic $u-1#17;
        X.E9D $u0#4, $u0#20;
        com.ss.android.ugc.aweme.addyours.model.AddYoursStickerStruct $u-1#11, $u-1#16;
        com.bytedance.router.SmartRoute $u-1#2;
        this := @this: X.Da5;
        $u9 := @parameter0: com.ss.android.ugc.aweme.sticker.data.InteractStickerStruct;
        staticinvoke <kotlin.jvm.internal.Intrinsics: void checkNotNullParameter(java.lang.Object,java.lang.String)>($u9, "sticker");
        $u1#1 = this.<X.Da5: android.content.Context LJJLJ>;
        $u6 = this.<X.Da5: X.EH3 LJJLJLI>;
        $u3 = this.<X.Da5: com.ss.android.ugc.aweme.feed.model.Aweme LJJLL>;
        $u-1#2 = staticinvoke <com.bytedance.router.SmartRouter: com.bytedance.router.SmartRoute buildRoute(android.content.Context,java.lang.String)>($u1#1, "//addyours/topic_detail");
        $u5#3#1 = null;
        if $u6 == null goto label13;
        $u0#4 = $u6.<X.EH3: X.E9D LJIILLIIL>;
        if $u0#4 == null goto label13;
        $u1_5#5#2 = $u0#4.<X.E9D: java.lang.String LIZ>;
     label01:
        $u4#6#3 = "";
        if $u1_5#5#2 != null goto label02;
        $u1_5#5#2 = "";
     label02:
        virtualinvoke $u-1#2.<com.bytedance.router.SmartRoute: com.bytedance.router.SmartRoute withParam(java.lang.String,java.lang.String)>("enter_from", $u1_5#5#2);
        if $u3 == null goto label12;
        $u-1#8 = virtualinvoke $u3.<com.ss.android.ugc.aweme.feed.model.Aweme: com.ss.android.ugc.aweme.profile.model.User getAuthor()>();
        if $u-1#8 == null goto label12;
        $u-1#9 = virtualinvoke $u-1#8.<com.ss.android.ugc.aweme.profile.model.User: int getFollowStatus()>();
        $u1_1#10#4 = $u-1#9;
     label03:
        virtualinvoke $u-1#2.<com.bytedance.router.SmartRoute: com.bytedance.router.SmartRoute withParam(java.lang.String,int)>("follow_status", $u1_1#10#4);
        $u-1#11 = virtualinvoke $u9.<com.ss.android.ugc.aweme.sticker.data.InteractStickerStruct: com.ss.android.ugc.aweme.addyours.model.AddYoursStickerStruct getAddYoursStickerStruct()>();
        if $u-1#11 == null goto label11;
        $u-1#12 = virtualinvoke $u-1#11.<com.ss.android.ugc.aweme.addyours.model.AddYoursStickerStruct: java.util.List getUserAvatars()>();
        if $u-1#12 == null goto label11;

# relevant code part start
        $u0#13 = newarray (com.ss.android.ugc.aweme.addyours.model.AddYoursAvatar)[0];
        $u-1#14 = interfaceinvoke $u-1#12.<java.util.List: java.lang.Object[] toArray(java.lang.Object[])>($u0#13);
        $r0 = (com.ss.android.ugc.aweme.addyours.model.AddYoursAvatar[]) $u-1#14;
        $r1 = (java.io.Serializable) $r0;
        $u1#15#5 = $r1;
        if $u1#15#5 == null goto label11;
     label04:
        $r2 = (android.os.Parcelable[]) $u1#15#5;
        virtualinvoke $u-1#2.<com.bytedance.router.SmartRoute: com.bytedance.router.SmartRoute withParam(java.lang.String,android.os.Parcelable[])>("user_avatars", $r2);
# relevant code part end

        $u-1#16 = virtualinvoke $u9.<com.ss.android.ugc.aweme.sticker.data.InteractStickerStruct: com.ss.android.ugc.aweme.addyours.model.AddYoursStickerStruct getAddYoursStickerStruct()>();
        staticinvoke <kotlin.jvm.internal.Intrinsics: void checkNotNullExpressionValue(java.lang.Object,java.lang.String)>($u-1#16, "stickerStruct.addYoursStickerStruct");
        $u-1#17 = staticinvoke <X.Dbk: com.ss.android.ugc.aweme.addyours.model.AddYoursTopic LIZ(com.ss.android.ugc.aweme.addyours.model.AddYoursStickerStruct)>($u-1#16);
        virtualinvoke $u-1#2.<com.bytedance.router.SmartRoute: com.bytedance.router.SmartRoute withParam(java.lang.String,java.io.Serializable)>("topic", $u-1#17);
        if $u6 == null goto label10;
        $u0#18 = $u6.<X.EH3: X.6yB LJIJJ>;
        if $u0#18 == null goto label10;
        $u1_4#19#6 = $u0#18.<X.6yB: java.lang.String LIZ>;
     label05:
        virtualinvoke $u-1#2.<com.bytedance.router.SmartRoute: com.bytedance.router.SmartRoute withParam(java.lang.String,java.lang.String)>("add_yours_enter_from_before_detail_page", $u1_4#19#6);
        if $u6 == null goto label06;
        $u0#20 = $u6.<X.EH3: X.E9D LJIILLIIL>;
        if $u0#20 == null goto label06;
        $u5#3#1 = $u0#20.<X.E9D: java.lang.String LIZ>;
     label06:
        $u-1#21 = staticinvoke <kotlin.jvm.internal.Intrinsics: boolean LJ(java.lang.Object,java.lang.Object)>($u5#3#1, "others_homepage");
        if $u-1#21 == 0 goto label08;
        if $u3 == null goto label07;
        $u-1#22 = virtualinvoke $u3.<com.ss.android.ugc.aweme.feed.model.Aweme: com.ss.android.ugc.aweme.profile.model.User getAuthor()>();
        if $u-1#22 == null goto label07;
        $u-1#23 = virtualinvoke $u-1#22.<com.ss.android.ugc.aweme.profile.model.User: java.lang.String getUid()>();
        if $u-1#23 == null goto label07;
        $u4#6#3 = $u-1#23;
     label07:
        virtualinvoke $u-1#2.<com.bytedance.router.SmartRoute: com.bytedance.router.SmartRoute withParam(java.lang.String,java.lang.String)>("viewed_user_id", $u4#6#3);
     label08:
        if $u3 == null goto label09;
        $r3 = (java.io.Serializable) $u3;
        virtualinvoke $u-1#2.<com.bytedance.router.SmartRoute: com.bytedance.router.SmartRoute withParam(java.lang.String,java.io.Serializable)>("from_aweme", $r3);
     label09:
        virtualinvoke $u-1#2.<com.bytedance.router.SmartRoute: void open()>();
        return 1;
     label10:
        $u1_4#19#6 = null;
        goto label05;
     label11:
        $r4 = newarray (android.os.Parcelable)[0];
        $r5 = (java.io.Serializable) $r4;
        $u1#15#5 = $r5;
        goto label04;
     label12:
        $u1_1#10#4 = 0;
        goto label03;
     label13:
        $u1_5#5#2 = null;
        goto label01;
    }

Relevant code part:

        $u0#13 = newarray (com.ss.android.ugc.aweme.addyours.model.AddYoursAvatar)[0];
        $u-1#14 = interfaceinvoke $u-1#12.<java.util.List: java.lang.Object[] toArray(java.lang.Object[])>($u0#13);
        $r0 = (com.ss.android.ugc.aweme.addyours.model.AddYoursAvatar[]) $u-1#14;
        $r1 = (java.io.Serializable) $r0;
        $u1#15#5 = $r1;
        if $u1#15#5 == null goto label11;
     label04:
        $r2 = (android.os.Parcelable[]) $u1#15#5;
        virtualinvoke $u-1#2.<com.bytedance.router.SmartRoute: com.bytedance.router.SmartRoute withParam(java.lang.String,android.os.Parcelable[])>("user_avatars", $r2);

Smali:

new-array v0, v7, [Lcom/ss/android/ugc/aweme/addyours/model/AddYoursAvatar;
invoke-interface {v1, v0}, Ljava/util/List;->toArray([Ljava/lang/Object;)[Ljava/lang/Object;
move-result-object v1
check-cast v1, [Lcom/ss/android/ugc/aweme/addyours/model/AddYoursAvatar;
if-eqz v1, :cond_a2
:goto_4c
const-string v0, "user_avatars"
invoke-virtual {v2, v0, v1}, Lcom/bytedance/router/SmartRoute;->withParam(Ljava/lang/String;[Landroid/os/Parcelable;)Lcom/bytedance/router/SmartRoute;

Effectively this is:

    android.os.Parcelable[] parcelableArr = (com.ss.android.ugc.aweme.addyours.model.AddYoursAvatar[]) userAvatars.toArray(new com.ss.android.ugc.aweme.addyours.model.AddYoursAvatar[0]);
    if (parcelableArr == null) goto L141;
L117:
    buildRoute.withParam("user_avatars", parcelableArr);

[jpstotz]

As a first counter measure I would suggest changing the outer loop in typePromotion so that if throws an error if the number if typings to be changed does not reduce.
In my opinion an Exception is better than an endless loop. To do so we count in each loop run the number of conversionsPending and compare them with the loop run before. If it has not changed in my understanding this means the algorithm is stuck in an endless loop.

  private ITyping typePromotion(ITyping tg) {
    int conversionsPending = Integer.MAX_VALUE;
    int lastConversionsPending;
    do {
      lastConversionsPending = conversionsPending;
      AugEvalFunction ef = createAugEvalFunction(this.jb);
      AugHierarchy h = new AugHierarchy();
      UseChecker uc = createUseChecker(this.jb);
      TypePromotionUseVisitor uv = createTypePromotionUseVisitor(jb, tg);
      do {
        Collection<ITyping> sigma = this.applyAssignmentConstraints(tg, ef, h);
        if (sigma.isEmpty()) {
          return null;
        }
        tg = sigma.iterator().next();
        uv.typingChanged = false;
        uc.check(tg, uv, this.jb.getUnits().snapshotIterator());
        if (uv.fail) {
          return null;
        }

      } while (uv.typingChanged);

      conversionsPending = 0;
      for (Local v : this.jb.getLocals()) {
        Type t = tg.get(v);
        Type r = convert(t);
        if (r != null) {
          tg.set(v, r);
          conversionsPending++;
        }
      }
      if (lastConversionsPending <= conversionsPending) {
        throw new RuntimeException("typingPromotion failed: conversionsPending was not reduced " + jb.getMethod());
      }
    } while (conversionsPending > 0);

    return tg;
  }

After testing the proposed code I have made it a PR: #2187

This PR does not fix this issue, just reduce the impact...