首页
论坛
专栏
课程

[原创]几款Android反编译器对循环结构的还原能力测试记录

2019-6-26 11:29 3074

[原创]几款Android反编译器对循环结构的还原能力测试记录

gjden
12
2019-6-26 11:29
3074


几款Android反编译器对循环结构的还原能力测试记录


0、motivation

   

      喜欢jadx的人会常常吐槽JEB反编译器:卖的这么贵,反编译效果还不怎么样。这里我想说的是,JEB毕竟是纯dalvik反编译器,从字节码解析到高级代码生成的整个过程都得从头来过,反编译差点也可以理解( 对于写一款全新的反编译的本人来说深有感触,经典算法和理论也常常有不奏效的时候,因此往往需要改进、优化和扩展,甚至需要提出极端情况下的解决方案,尤其是对抗结构化混淆时)。应该说 JEB 主要槽点是昂贵的费用,其采用的结构化分析技术的确属于比较落后的,但是JEB的功能比jadx更为丰富,更有利于做逆向分析。    

      我们知道,反编译器是编译器的逆过程,许多反编译器的理论和技术来源于编译理论,这里不细说。反编译器主要包含二进制程序解析、指令(字节码/机器码)解码(句法分析、语义分析)、中间代码生成、控制流图生成、数据流分析、控制流分析、高级代码生成等过程,其中各个阶段都有相关算法来处理。在反编译理论中,控制流分析中最核心的算法是结构化分析算法,结构化算法的优劣决定了反编译器的代码还原能力。而还原循环结构的结构化算法成为反编译实现的一个难点,即便目前的论文已经实现完全无goto的算法,但是这种算法面对复杂混淆后控制结构时还是会出现代码丢失甚至是拒绝工作的情况。

     因此,本文简单设计了几种循环类的控制结构来针对性的测试这几款反编译器的还原能力。同时也是为了检验GDA对循环结构的还原能力,发现不足并加以优化。对于反编译结果,我们遵循“语义不变性>代码可读性>代码还原度”的原则。为什么是这个原则,因为语义不变性保证了反编译的代码不会出现程序逻辑上的问题,也就是说,保留程序的等价性,任何输入都能得到同样的输出,出现语义错误在反编译技术领域被视为 不可接受的; 代码可读性需要建立在语义不变性的基础上,更易于人工的阅读和分析; 而代码还原度便是反编译代码与源代码相似程度。


1、Test1

      第一个测试中,我设计了循环头和锁节点都为二路条件循环结构,为了测试循环结构化分析能力,我多嵌套了几个if语句(代码标号为基本块号)。程序简单如下:

        int a = Math.getExponent(88);
	int y = 0;
1	while(y>0){
2	    if(a<=0){
3		 a=a+1;
		 y=y+1;
	     }else{ 
4		 if(a>10){
5		     if(a>100){
6		         a=a*5;
			 break;
		     }else{
7			 y=y/a;
		     }
		 }
             }
	}
8	this.attachBaseContext(this);

     

      后面两个图是我做的一张粗略的控制流图,通过android sdk将这段代码生成apk文件后,用Jeb、GDA、Jadx来反编译,并进行代码可读性和语义准确性上进行对比。如下图:

      通过对比可以看出,Jeb的还原能力是最差的,其代码可读性比较差,且发生了语义错误,甚至在面对此种循环结构时,还出现了块儿的丢失且多了3个continue。此外还可以看出,JEB反编译对于label的处理是在高级代码输出之后处理的,在做goto-label分析时将其去除,所以导致了空行的存在。

GDA看起来是最接近源代码的,且保持了语义的准确性,并且识别出了符号。

Jadx代码可读性更好,同时反编译后语义和源代码保持了一致,并且对级联的if-else语句做了优化,但已不再是源代码的样子。


2、Test2:

      该测试案例在Test1的基础上仅仅多一条语句,其结果是在循环内的第一个if-else结构之后加了一个后随节点,源代码如下:

        int a = Math.getExponent(88);
	int y = 0;
1	while(y>0){
2	    if(a<=0){
3		 a=a+1;
		 y=y+1;
	     }else{ 
4		 if(a>10){
5		     if(a>100){
6		         a = a*5;
			 break;
		     }else{
7			 y = y/a;
		     }
		 }
             }
8             y = y*y;
	}
9	this.attachBaseContext(this);

      编译成为apk后,我们使用JEB、GDA、Jadx来反编译看看效果。

      同样GDA几乎做了完美的复原;JEB将其识别为了for类型循环,同样丢失了退出循环的基本块儿(语句a=a*5),导致语义发生错误。Jadx同样也高度的还原了代码,且保持语义的正确性。

3、Test3

      接下来我们来看看他们对双层循环的结构化分析的能力。我设计一个双层循环,使内层循环break出外层循环,实际上基本块5不仅会是内存循环的锁节点,也会是外层循环的锁节点。并且该锁节点为二路条件节点,其一个分支路径回到内层循环,另外一个分支结构回到外层循环。一般对循环结构算法都是循环头-锁节点一一对应,因此处理过程中可能会复杂化该类结构。代码实现非常简单如下:

        int a=Math.getExponent(88);
        int y=0;
1	while(y>0){
2	    while(a>0){
3	        if(a<=0){
4	            a=a+1;
	            y=y+1;
	        }else{
5 	            if(a>10){
6	                 break;
	             }
	        }
            }
	}
7	this.attachBaseContext(this);

      编译成apk后,再反编译后可以看出GDA反编译的代码,外层循环并没识别出来,但是保持了语义的正确性;


        JEB虽然识别出来双层循环,内存循环识别成了do-while结构,另外我们还可以看出其糟糕的goto跳转严重的影响了还原代码的可读性,并且发送语义错误。Jadx基本上还原了原始代码,并保持了语义的正确性。


4、Test4

      这一段代码我在退出循环的”if(a>10)”语句中内嵌了另外一个if语句,这会导致内层循环的锁节点发生变化,并且给内层循环添加了一个跟随节点,另外代码做了稍稍的改动。当然代码也非常简单,如下图:

        int a=Math.getExponent(88);
        int y=0;
1	while(y>0){
2	    while(a>50){
3	        a=a+1;
	        y=y+1;
4 	        if(a>10){
5	            if(a>100){
6		        a=a*5;
		        break;
		    }else{
7			y=y/a;
	            }
	        }
            }
8           this.attachBaseContext(this);
	}

      同样我们将该段代码编译成apk后,再反编译:

      从反编译结果可以看出GDA保持了语义的不变性,并且几乎完全复原了源代码的结构。JEB虽然代码还原的语义没有发生错误,但是代码还原的质量并不是很好,与源代码相差较大。Jadx还原的代码和源代码几乎完全一样。


5、Test5


      我继续在上一个例子的基础上增加一些代码来看看反编译的效果。

        int a=Math.getExponent(88);
        int y=0;
1	while(y>0){
2           y++;
3	    while(a>50){
4	        a=a+1;
	        y=y+1;
5 	        if(a>10){
6	            if(a>100){
7		        a=a*5;
		        continue;
		    }else{
8			y=y/a;
	            }
	        }
9               y=a*y;
                break;
            }
10          this.attachBaseContext(this);
	}

      这次我在内层循环的第一个if-else结构上添加一个后随节点,并且最后break出内层循环到外层循环。并且将a=a*5语句后的break改成continue。同样编译成apk后再反编译。


      从反编译结果上来看,GDA还原代码时,虽然保持了与源码较高相似性,但是却因丢失了a=a*5语句后的continue语句导致语义错误。而JEB还原代码时,虽然保持语义的正确性,但是代码还原度比较低。Jdax和GDA一样都出现了语义错误,并且不仅丢失了continue语句而且还丢失了break语句。

6、Conclusion

      从三款反编译器对循环结构的简单测试中可以看出,Jadx反编译效果最好,利用asm生成class文件后再利用改进的java反编译技术进行反编译,体现了其优势;而对于直接对dalvik字节码进行反编译,另外实现一套反编译引擎的GDA和JEB都会差一点,但是从对循环结构及2路分支结构的恢复上,GDA明显强于JEB,并且对源代码的还原程度也非常高。JEB在测试案例中表现得比较糟糕,甚至在简单情况下就出现了语义错误,这是反编译中无法容忍的,当然本次测试的情况属于极端一点的测试,一般情况下,JEB的循环识别也非常不错。



[公告]安全服务和外包项目请将项目需求发到看雪企服平台:https://qifu.kanxue.com

最后于 2019-6-26 14:33 被gjden编辑 ,原因:
最新回复 (32)
krash 2019-6-26 13:46
2
0
我印象中jadx也是直接处理dalvik,不会先转成class.而反编译class的时候,会先转成dex再处理.
gjden 12 2019-6-26 14:15
3
0
krash 我印象中jadx也是直接处理dalvik,不会先转成class.而反编译class的时候,会先转成dex再处理.
对,jadx的作者的确是这么说的,这一点我纠正一下。
最后于 2019-6-26 14:31 被gjden编辑 ,原因:
葫芦娃 1 2019-6-26 16:51
4
0
roysue 3 2019-6-26 16:53
5
0
supperlitt 2019-6-26 17:10
6
0
但是jadx对内存的消耗也不敢恭维呀
我是土匪 4 2019-6-26 17:14
7
0
hackevil 2019-6-26 18:35
8
0
牛得飞上天,顶级水平!
ouyangtian 2019-6-26 21:31
9
0
之前也玩过,难的是finally的还原
hackevil 2019-6-26 21:59
10
0
ouyangtian 之前也玩过,难的是finally的还原
学界从未说过finally难吧,finally不就是个try-catch的后随么,难在哪儿了?反而解决非结构化问题才是难点,尤其是带循环的非结构化问题
goodgirls 2019-6-26 22:08
11
0
hackevil 学界从未说过finally难吧,finally不就是个try-catch的后随么,难在哪儿了?反而解决非结构化问题才是难点,尤其是带循环的非结构化问题
国人终于有拿得出手的反编译器了,@hackevil,之前被你莫名的鄙视了
hackevil 2019-6-26 22:26
12
0
goodgirls 国人终于有拿得出手的反编译器了,@hackevil[em_13],之前被你莫名的鄙视了[em_80]
不会吧,这么小心眼,还记得
goodgirls 2019-6-27 08:11
13
0
hackevil 不会吧,这么小心眼,还记得
当然,不要嘲笑菜鸟,尤其是女菜鸟
学编程 1 2019-6-27 10:58
14
0
GDA加载最新版本的华为应用市场,分析一会儿,做一些操作就容易卡死了。卡死的用户体验太差了。效果还是不错的
hackevil 2019-6-27 18:28
15
0
goodgirls 当然,不要嘲笑菜鸟,尤其是女菜鸟[em_51]
原来你是妹子啊,多有得罪
myhloli 1 2019-6-27 22:21
16
0
goodgirls 2019-6-28 13:03
17
0
hackevil 原来你是妹子啊[em_3],多有得罪[em_28]
这是啥表情
gotyou 2019-6-28 13:20
18
0
版主牛逼,文章没有什么花哨的东西,直击编译器的要害,学界泰斗啊,感谢付出与分享!
androidu 2019-7-2 13:52
19
0
666
goodgirls 2019-7-3 22:04
20
0


最后于 2019-7-3 22:19 被goodgirls编辑 ,原因:
gjden 12 2019-7-4 09:47
21
0
gotyou 版主牛逼,文章没有什么花哨的东西,直击编译器的要害,学界泰斗啊,感谢付出与分享![em_19]
学界泰斗,这个帽子有点重,扛不动的。
只是来打酱油 2019-7-4 10:28
22
0
有没有办法,完全还原?        理论上是可以还原的把
gjden 12 2019-7-4 17:16
23
0
只是来打酱油 有没有办法,完全还原? 理论上是可以还原的把
编译器的优化可能会导致某些基本块移动,或者一些表达式的消失,想要完全还原代码,理论上也是不可能的,但是部分函数是可以完全还原的。
monkeybar 2019-7-10 06:29
24
0
(Sorry, my Mandarin is not good enough for me to write an answer in chinese, so I'll type it in English. I hope you don't mind!)
I wanted to give my very different opinion about decompilation results. It seems the author did use an older version of JEB, because I have different results, and in my opinion, they are either as good as JADX or GDA.

Our company pays for JEB Pro, we always use the latest beta version, currently a 3.6 Beta July 2019.

- 1) JEB has discarded x*5 on purpose, since that variable is deemed useless after assignment. (In fact, JEB's deobfuscation capabilities are one of its great strength, as I'll show later)

- 2) OK

- 3) OK

- 4) OK

5) Here, we do have goto, but JEB provides semantically correct results, where the other two tools, eager to avoid gotos, generate wrong results! Something much worse when reversing is done professionally, with various clients expecting accurate information about the whats and hows of a piece of malware.

- (De)Obfuscation -
Now, let's go one step further and perform simple obfuscation of method test1 (Attaching the dex file)

jadx crashes; gda: not tested, unfortunately.



JEB cleans up and decompiles the code almost perfectly: see below (it looks like the obfuscator has inserted a large amount of trampoline and junk code)



It is unfortunate that the original poster seemed to be biased against JEB. I talked to lots of people at conferences and events and it seems almost all companies and research labs doing serious business on the Android security side, at least, use JEB.

All that being said, and in my experience, JEB outperforms all other static analysis tools (_except_ IDA when it comes to arm code analysis) in almost all domains: coverage (full APK support, including obfuscated resources, but also native processors and non-native processors), decompilation, debugging. Not to mention it supports refactioring and cross-references with virtuals and overrides, and has a full API to automate pretty much everything. IDA is really the only real competitor to JEB when it comes to x86 and arm, and HexRays decompiler in that regards still outperform JEB generally. We have examined complicated x86 malware where JEB was doing a better job at deobfuscating the code.

Sorry again for writing in English, I hope that's okay. I'm sometimes browsing pediy because it contains interesting articles, but I rarely post, my Chinese is not good enough for lengthy messages.

(Disclaimer: we use JEB everyday at our for-profit security company, and so we pay for it and to have the latest version at all times. We do Android malware reversing, Windows malware reversing, Ethereum contracts reversing. We love the tool and the support from the PNF Software guys, so obviously our opinion may be a little bit skewed!)
gjden 12 2019-7-11 13:39
25
0
monkeybar (Sorry, my Mandarin is not good enough for me to write an answer in chinese, so I'll type it in Engl ...
首先要明确的是本文并没有否定jeb也对其没有偏见,每个工具都有他的优缺点,就连优秀的苹果系统也很多人吐槽难用。本人也是非常喜欢JEB,只是本文内容限制在对循环结构的还原上,专门针对的是结构化算法的测试,并没有对比其他方面。文中也提及相应的观点,第一段:" 应该说 JEB 主要槽点是昂贵的费用,其采用的结构化分析技术的确属于比较落后的,但是JEB的功能比jadx更为丰富,更有利于做逆向分析 ", 并在文末也说了:“ 当然本次测试的情况属于极端一点的测试,一般情况下,JEB的循环识别也非常不错 ”  。看你也在论坛混了很长时间,应该是能看懂中文,我这里就不费劲儿翻译成英文了。


然后正式回复:

仔细看了你的回答,你可能使用的是最新版本,所以反编译效果有较大的改善,但是仍然有丢失基本块的bug.
对于test1,你的辩解完全不对:"JEB has discarded x*5 on purpose, since that variable is deemed useless after assignment",你认为是因为变量a(v1)分配值(a=Math.getExponent(88))之后后被jeb视为无效,这是不正确的,a(v1)的值是由method的返回值决定,jeb不会去做预判,jeb的问题仍然是结构化算法的问题,所以导致了(a=a*5)语句丢失,实际上是整个基本块的丢失。一个简单的测试就可以证明,我把a的值初始化为能够覆盖>100这个路径,并且给该基本块多加几条语句,jeb仍然将该基本块弄丢失了。test2中也一样,会出现丢失块的情况。
test1改后的源代码:
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
int a = 200;
int y = 0;
while(y<100){
    if(a<=0){
    a=a+1;
    y=y+1;
    }else{
        if(a>10){
            if(a>100){
                a=a*5;
                a=a&0xff;
                break;
            }else{
                y=y/a;
            }
        }
    }
}
this.attachBaseContext(this);

三款工具反编译结果:从结果来看,jeb依然丢失了这个块,这次是两条语句。



图中第二个图的篮筐里就是jeb丢失的块。
然后是你认为反编译ok的后几个test,本文目的不是测试反编译器是否能够反编译,而是测试反编译器的还原能力。
最后对于反混淆这一块儿,jeb的确做得很好,不过这完全是反编译器的兼容性和稳定性决定的,这靠的是完备的测试案例(如大量的采用不同反混淆手段的apk)以及使用者的错误反馈,最后做出相应改进,这一块儿商业的jeb本应具备的,不过最本质上和反编译器的核心算法关系不大。就你给出的例子,jeb只是考虑处理了这种垃圾指令或者那些控制流图上不可达的基本块,这种情况我也遇到过很多,也在GDA中加入了相应的处理。最后,也希望Jeb能改进优化。




mingxuan三千 2019-7-11 13:56
26
0
666
gotyou 2019-7-11 14:42
27
0
monkeybar (Sorry, my Mandarin is not good enough for me to write an answer in chinese, so I'll type it in Engl ...
你是老外吗,感觉此帖引来了pnf公司的人了
kanxue666 2019-7-11 20:17
28
0
楼主搞得真高端,完全达不到的高度,膜拜大神!
billery 2019-7-11 22:16
29
0
monkeybar (Sorry, my Mandarin is not good enough for me to write an answer in chinese, so I'll type it in Engl ...
逮到一名老外真能写,这么长篇幅。
monkeybar 2019-7-12 04:56
30
0
gjden 首先要明确的是本文并没有否定jeb也对其没有偏见,每个工具都有他的优缺点,就连优秀的苹果系统也很多人吐槽难用。本人也是非常喜欢JEB,只是本文内容限制在对循环结构的还原上,专门针对的是结构化算法的测试 ...
Hello. The variable `a` is simply discarded in the first case because the decompiler has determined that it is no longer "in use" (basic data flow analysis here). If you were to make it used, for example by returning it, then it would necessarily be kept.

See the example below, I used JEB 3.6, same as my last message.

hackevil 2019-7-12 05:40
31
0
monkeybar Hello. The variable `a` is simply discarded in the first case because the decompiler has determined ...
3.6都出来了啊,我等还在用2啊,能不能分享出来用用,看样子新版本的确有不少改进了,估摸着版主大大也没这么新的版本。
最后于 2019-7-12 05:40 被hackevil编辑 ,原因:
kwanhua 2019-7-15 18:40
32
0
确实的,最新版我也用过,无论是否最新版本,我发现jeb是会对没用的参数进行一些删减操作的... 还有就是@版主大大你文章里面的“语义不变性”,这个如果是针对整个函数的话,jeb丢失的块,对这个函数的输入输出,以及中间对输入处理的流程没影响的话,那么语义也算是不变吧...毕竟还是将,“什么东西”,“怎么做”,“达到什么效果” ,都表达清楚了。
ymlovel2019 2019-7-24 22:55
33
0
这个真牛,学到了,感谢
游客
登录 | 注册 方可回帖
返回