Java反编译器剖析(下)

更多细节

目前为止,我们的分析仅限于一个单独的代码序列——以一个简单指令列表开始,经过一系列转换产生更高级别的指令。如果你认为这些都太过简化,你的看法是对的。因为Java是一种高度结构化的编程语言,包含的概念比如范围(scope)、块(block),以及更加复杂的控制流。为了处理一些更加复杂的指令,比如 if/else 块和循环(loop),我们需要对代码进行更加深入的分析,关注各种可能被选取的代码路径。这就是所谓的控制流分析

我们首先将代码分解成连续的块,确保这些代码块会从头至尾依次执行。这些分解后的代码称作基本块(basic block)。通过在指令跳转的地方将指令列表进行分割,由此划分这些基本块。指令跳转可以是跳转到别的块,也可以是跳转到块本身。

通过在块之间连上边,就可以得到一个代表所有可能分支的控制流图(CFG,control flow graph)。应该注意的是,这些边界可能并不十分明确,如果块中包含的指令抛出异常,那么控制流就会转到对应的异常处理程序。虽然我们不会在这里详细讨论如何构建CFG,但是为了帮助理解如何利用这些图解析类似循环这种代码结构,需要理解一些比较高层的概念。

控制流图实例

我们对控制流图最感兴趣的角度是支配关系(domination relationship):

  • 若所有通向节点N的路径都经过D,那么称节点D支配了节点N。所有节点都支配自身;如果D和N是不同的节点,那么D被称为严格支配了节点N。
  • 如果D严格支配了N,但严格支配节点N的其它节点受D的严格支配,那么D可以称作直接支配N。
  • 支配树(dominator tree)上的节点有这样的特性,所有子节点都是受该树节点直接支配。
  • D的支配边界(dominance frontier)是一组类型N的节点集合。D直接支配类型N的前一节点,但不是完全支配N。换言之,到该集合为止节点D的支配关系结束。

译注:关于此处的概念,可以参考Wikipedia: Dominator (graph theory)

基本的循环和控制流

考虑如下Java方法:

public static void fn(int n) {
    for (int i = 0; i < n; ++i) {
        System.out.println(i);
    }
}

反汇编结果如下:

 0:  iconst_0
 1:  istore_1
 2:  iload_1
 3:  iload_0
 4:  if_icmpge 20
 7:  getstatic #2      // System.out:PrintStream
10:  iload_1
11:  invokevirtual #3  // PrintStream.println:(I)V
14:  iinc 1, 1
17:  goto 2
20:  return

接下来,我们应用先前讨论的内容将其转为更加可读的形式。首先引入栈变量,然后执行复制传播。

字节码 栈变量 复制传播后
 0
1
2
3
4
7
10
11
14
17
20
iconst_0
istore_1
iload_1
iload_0
if_icmpge 20
getstatic #2
iload_1
invokevirtual #3
iinc 1, 1
goto 2
return
s0 = 0
v1 = s0
s2 = v1
s3 = v0
if (s2 >= s3) goto 20
s4 = System.out
s5 = v1
s4.println(s5)
v1 = v1 + 1
goto 2
return

v1 = 0

if (v1 >= v0) goto 20

System.out.println(v1)


v1 = v1 + 1
goto 4
return

我们注意到 #4 的条件分支和 #17goto 创建了一个逻辑循环。从控制流图上可以更容易发现这个循环:

在上图中,从 goto 语句跳转回条件判断形成了一个循环。在这个例子中,条件分支作为循环入口(loop header),可定义为循环边的支配者。循环入口支配了循环体内所有节点。

通过寻找形成循环的边,我们可以确定一个条件分支是不是循环入口。但是要如何才能做到这一点?一个简单的办法是,判断测试条件是否在其自身的控制边界内。一旦确定了循环入口,我们需要找出哪些节点应当放在循环体内。通过找出入口支配的所有节点可以达到这个目的。算法的伪代码如下:

findDominatedNodes(header)
        q := new Queue()
        r := new Set()

        q.enqueue(header)

        while (not q.empty())
            n := q.dequeue()

            if (header.dominates(n))
                r.add(n)

                for (s in n.successors())
                    q.enqueue(n)

        return r

一旦确定了循环体,就可以将代码转换成循环了。请记住,循环入口也许是一个判断跳出循环条件语句。这种情况下需要对这个条件取反。

v1 = 0
while (v1 < v0) {
    System.out.println(v1)
    v1 = v1 + 1
}
return

瞧,现在我们得到了一个前置条件循环!包括whilefor 以及for-each 的大部分循环,编译后都遵循一种基本模式,这里我们都将其作为简单的 while 循环。一般来讲,我们很难完全确定原来的程序到底写的是哪一种循环。但是,for 循环和 foreach 循环都遵循着一种非常特殊的模式。这里我们不对细节进行追究。但如果对比一下上面的 while 循环,就可以发现原来的 for 循环是如何在循环开始之前对循环条件进行初始化的 (v1 = 0) ,也可以了解迭代器 (v1 = v1 + 1) 如何被加到循环体的结尾。这个就当做把 while 转换为 forforeach 的一个练习吧。还有一个很有意思的问题,如果要把循环改为后置条件循环 (do / while) 又该怎么做呢?

我们可以使用类似的技术对 if/else 语句进行反编译。if/else 的字节码非常直观:

begin:
    iftrue(!condition) goto #else
    // `if` block begins here
    ...
    goto #end

else:
    // `else` block begins here
    ...

end:
    // end of `if/else`

上面的代码中,我们使用 iftrue 伪指令取代条件分支:测试条件,如果通过则进入分支;否则,继续测试。我们知道, if 后面紧跟着条件,else 开始跳转。找出 ‘if/else’ 块的内容与找出起始点的支配节点一样简单,执行之前的算法即可达成。

现在完成了基本的流控制机制介绍,当然还有些其他内容(比如错误处理和子程序等等),这些已经超出了本文的讨论范围。

总结

写一个反编译器不是一件简单的工作,涉及内容足以写一本甚至是一个系列的书!很明显,在一篇博客中不能覆盖所有的内容。而且即使我们这么做,也许你都不愿意读。我们希望,通过一些最普通的构造——逻辑运算、条件判断以及基本的流控制,能让你对反编译器的开发有一点有趣的了解。

  • Lee Benfield:Java反编译器CFR的作者。
  • Mike Strobel:Java反编译器和元编程框架Procyon的作者。

现在,不如开始动手写一个自己的Java反编译器吧 :)

原文链接: javacodegeeks 翻译: ImportNew.com - 邬柏
译文链接: http://www.importnew.com/9248.html
[ 转载请保留原文出处、译者和译文链接。]

关于作者: 邬柏

(新浪微博:@Alex_Aisin-Gioro

查看邬柏的更多文章 >>



相关文章

发表评论

Comment form

(*) 表示必填项

还没有评论。

跳到底部
返回顶部