[core] Problem recognizing loops

[oriori1703]

When using the latest build of jadx from the master branch, jadx fails to decomplie this function.
I came across this function or something very similar a couple of times, but the example here is from an old ctf I did.

Class: opensecurity.sendsecret.ValidateAccess
Method : private static String ˊ(int i, int i2, int i3) (private static String m0(int i, int i2, int i3) when using deobfuscation)
Error and warnings:

    /* JADX WARN: Removed duplicated region for block: B:10:0x002a  */
    /* JADX WARN: Removed duplicated region for block: B:8:0x0025  */

The apk: SENDSECRET.zip
The source code: SendSecret_source.zip

This function was not in the original source code of the project. It was create as a part of the DexGuard's string obfuscation feature.
This means that it may have been "written" in smali, and was never a "real java function" to begin with.
Despite of that I think jadx should still support such use cases and should be able to decomplie this method.

Here is the CFG for this method:

From a short (not really that short) look at the code it seems that the problem stems from BlockProcessor.markLoops.
The way it's currently checks for a loop is the following:

• for each block:
  • getting all of it's successors
  • for each successor:
    • getting all of it's dominators
    • if the block dominate its predecessor mark it as loop

This is fine for the most part, but it is only guaranteed to be correct when the control flow graph is a structured graph (a graph where gotos aren't necessary).
Unfortunately, in this case there is another edge leading to the second block (block 6) of the loop, causing the "head" of the loop (block 5) to not be a dominator of the second, therefore causing the whole thing to not be recognized as a loop.
This results in Jadx going into an infinite loop when trying to create the regions, as can be seen from the CFG with regions having a couple of edges connecting each node in the loop (though I'm not sure why it eventually stops):

One way to fix this could be to duplicate block 5 to appear before the loop, and in it's end. It would look something like this:

In my opinion, a better fix would be keep using the same way of detecting loops, but apply s transformation to the CFG to make it a structured graph.
A good explanation can be found in the paper No More Gotos, specifically at section 5-a for the problem described above (though the rest of the paper could also help with other structuring problems).

In short it would mean to create a "structuring variable" that is given a different value for each entry to into a cyclic region with more than one entry.
The value would be equal to the "index" of the entry in the loop. For the first entry the value would be 1, for the second entry it would be 2, and so on.
Afterwards create a new condition block surrounding each entered node in the loop to check the value of the structuring variable.
finally redirect each entry to the first constructed condition block.
It would look something like this (taken from the paper):

I'm sorry I do not have time to implement a fix myself, so I hope this explanation was enough.
Let me know if I could help with anything else :)

BTW, I think there is also a problem with ternary expressions being incorrectly generated in this function, but I'm not sure if the root cause is the issue above, so I didn't really look into it yet.

[skylot]

@oriori1703 thanks for the sample and nice article!
I know about that 'multi-entry loop' issue and that it is possible to fix CFG to resolve it, but as soon as these cases are quite rare I just give it low-priority and postponed for the later 😞
Anyway, I will try to fix it this time 👍

[skylot]

@oriori1703 I commit a fix for this exact case, it is very specific, but now jadx will add a warning if found another case 😃