Endless Loop in TypeResolver

[jpstotz]

Describe the bug When loading the body of a certain method Soot ends up in an endless loop (the algorithm does not terminate even after multiple hours).

Input file mobi.mmdt.ottplus_4.8.19 (480199)_min.apk.zip

To reproduce

Logger log = LoggerFactory.getLogger("SootTest");

String classToLoad = "org.mmessenger.ui.ChatActivity";
File apkFile = new File("mobi.mmdt.ottplus_4.8.19 (480199)_min.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_coffi(false);

File androidJarsDir = new File("./androidJars");
o.set_android_jars(androidJarsDir.getAbsolutePath());
o.set_src_prec(Options.src_prec_apk);

Main.v().autoSetOptions();
Scene.v().loadNecessaryClasses();
log.info("loadNecessaryClasses finished");

SootClass sootClass = Scene.v().getSootClass(classToLoad);
SootMethod sm = sootClass.getMethodByName("getThemeDescriptions");
Body b = sm.retrieveActiveBody();
log.info("finished"); // never reached

Expected behavior After some minutes the body should be loaded.

Additional context Soot seems to be stuck in the method soot.jimple.toolkits.typing.fast.TypeResolver.applyAssignmentConstraints(Typing, IEvalFunction, IHierarchy). In detail the loop while (!sigma.isEmpty()) {..} seems to be effectively an endless loop or it's complexity is so high that it does not end in reasonable time.

[StevenArzt]

There are corner cases in which the type assigner is absurdly slow. Can you give some insights about the structure of the method? We have seen such effects on (obfuscated) methods with hundreds / thousands of locals to be typed. You essentially get a full typing for each local for each candidate. If there are two possible typings for each local, you get n^2 typings in total where n is the number of locals. This can escalate quickly. We have already implemented some shortcuts to drop typings early, but you can still construct cases in which the algorithm is infeasible.

[jpstotz]

@arzt The problematic method public ArrayList<ThemeDescription> getThemeDescriptions() is a pretty long method which mainly creates a few hundred object instances of a class called ThemeDescription that are added to an ArrayList and returned:

   @Override // org.mmessenger.ui.ActionBar.BaseFragment
    public ArrayList<ThemeDescription> getThemeDescriptions() {
        TrendingStickersAlert trendingStickersAlert;
        ThemeDescription.ThemeDescriptionDelegate themeDescriptionDelegate = new ThemeDescription.ThemeDescriptionDelegate() { // from class: org.mmessenger.ui.-$$Lambda$ChatActivity$SdDIVARTmFmRSBuB7h2us7NWc70
            @Override // org.mmessenger.ui.ActionBar.ThemeDescription.ThemeDescriptionDelegate
            public final void didSetColor() {
                ChatActivity.this.lambda$getThemeDescriptions$128$ChatActivity();
            }
        };
        ArrayList<ThemeDescription> arrayList = new ArrayList<>();
        arrayList.add(new ThemeDescription(this.fragmentView, 0, null, null, null, null, "chat_wallpaper"));
        arrayList.add(new ThemeDescription(this.fragmentView, 0, null, null, null, null, "chat_wallpaper_gradient_to"));
        arrayList.add(new ThemeDescription(this.messagesSearchListView, ThemeDescription.FLAG_BACKGROUND, null, null, null, null, "windowBackgroundWhite"));
    // ... another 500 lines 
}

The full code is a bit long to include it so I attached the Jadx decompiled class ChatActivity.java.txt. The method starts in line 14790.

Considering that each line requires on dex level may be 3-5 assignments the method may end up with about 2500 locals. With n^2 that will generate a lot of typings...

What do you think of a configurable option to abort the whole typing process after a certain amount of iterations? In my opinion a an exception may be preferred than an next-to-endless loop...

[StevenArzt]

We need to look into this in detail. Simply aborting typing would lead to (partially) untyped code, which breaks many things in Soot. That's not really a solution. I'd suggest to drop the code into Soot, set a breakpoint right before the type assigner starts, and have a look at the pre-typing Jimple code.