9.1.1 控制流分析
几乎所有代码转换工具(不论它是编译器还是黑客工具)都必须以某种方式表示函数,而最常见的表示方式则莫过于控制流图(CFG)了。控制流图中的结点称为“基本块”(basic block)。基本块由一系列顺序执行的指令构成,它的结尾处通常是一个条件转移指令。控制流只能从基本块的第一条指令进入,从最后一条指令离开。如果控制流图中存在一条从基本块A尾部流向基本块B的头部的边,即A→B,就表示在程序运行时控制流可能从A流向B。控制流图是一种保守的表示方法,由于我们无法确定运行时控制流到底是怎么流动的,索性就把所有可能情况全部在控制流图中表示出来。因此我们说控制流图中表示的是代码所有可执行路径的超集。如图9.1(a)所示为模n的取幂函数的源代码。
图9.1 程序及其分块
在图9.1(b)中,我们已经把源码“编译”成了一个较为简单的中间表示形式了,源码中的结构化控制语句已经全部变成了条件转移指令(if...goto...)和无条件转移指令(goto...)了。而图9.2(a)给出的则是图9.1中的这个函数的控制流图。
图9.2 控制流图
注意,各个基本块的内部是没有分支指令的,它们只能在基本块的结尾处出现。基本块内部的语句则可以用多种方式表达。例如,在图9.2(b)中,我们把基本块B5转换成了一颗表达式树,这也是一种常见的表示方法。
下面给出构造控制流图的算法的基本方法(BuildCFG(F))。
(1)标记处所有的首指令(leader)。
①函数的第一条指令是首指令。
②任意一个转移指令的跳转目标都是首指令。
③紧跟在条件转移指令之后的指令都是首指令。
(2)各个基本块都是由某条首指令开始一直到下一个首指令为止(但不包括下一个首指令)之间的所有指令构成。
(3)如果基本块A结尾处转移指令的跳转目标是基本块B,或者B是紧跟在A后面的,则添加一条边A→B。
在图9.2中,语句(1)、(3)、(4)、(5)、(7)、(8)、(12)都是首指令。语句(1)是首指令,因为它是函数的第一条指令。语句(4)和(12)能成为首指令,因为一个是语句(3)的跳转目标,另一个则紧跟在语句(3)之后。同样,语句(7)和(5)是首指令,因为一个是语句(4)的跳转目标,另一个紧跟在语句(4)之后。语句(8)成为首指令的理由是它是语句(6)的跳转目标。最后语句(3)也是因为语句(11)直接跳转到它那里才成为首指令的。基本块B5是从首指令(8)开始的,由于接下来的一个首指令是(12),所以它所包含的指令就是语句(8)到(11)的指令。
1.表示异常
当然,生活并不总是一帆风顺的。你想想,在支持异常处理的语言中,任何一条指令都有可能在CPU时钟周期到点时抛出一个异常来,这在控制流图里怎么表示呢?在Java中,带除法运算的整型表达式,解除指针引用或者直接写上一条throw语句……一句话,源码中任何一个语句都可能抛出异常来!要按着前面给出的控制流图构造方法,每条指令都必须变成一个基本块再加上无数条边,我们应该把表示异常处理的边和一般的边区分开来。如图9.3所示为一个Java程序演示代码。
图9.3 演示Java代码
在Marmot编译器中,整个try语句块会被视为一个基本块,再加上“正常的”控制流边。此外,基本块也会被标上额外的边(浅灰色标出)表示异常处理。这些额外的边各自指向不同的异常处理块,如图9.4所示。
图9.4 Java控制流
2.用算法REAMB表示自修改代码
在一个“正常”程序中,代码段里的内容是不会被修改的,因为不管什么编译器生成代码总是为了去执行!
不论是破解者还是防御方都必须有能力处理自修改代码。所谓“自修改代码”就是指那些运行时会修改自身代码的程序。作为防御者,你往程序中加入的一些保护代码中就含有自修改代码。而作为破解者,你就更应该会分析自修改代码,因为只有这样才能破解这类软件!另外计算机病毒也经常使用自修改代码以逃避杀毒软件的查杀。这就意味着杀毒软件也必须能对付这类病毒的这类行为。
可问题是要表示自修改代码,传统的控制流图就不够用了,我们来看下面这段代码。
上述代码使用的指令集如图9.5所示。
图9.5 演示用处理器的指令集(所有的操作码和操作数都是1个字节)
在接下来讨论反汇编的内容中我们还会使用这个指令集。上面的代码中第一列中给出的是各条指令的偏移量,第二列给出的是各条指令的机器码(十进制数),第三、四列中则分别是各条指令的操作码和操作数。例如,第一条指令是loadi r0,12,它对应的机器码是[9,0,12],其中9表示的是loadi操作码,紧接着的0则表示寄存器r0,接下来的12则表示立即数12。这段代码的控制流图只含一个循环,如图9.6所示。
可我们发现这个控制流图(图9.6)竟然不是一个连通图!偏移+14上的无条件转移指令不但造成了这一情况,还使图中的循环成了一个死循环。我们再来仔细观察一下这段代码。你注意到了那条store指令了吗?这条指令把偏移+12上的那个字节变成了4,于是在偏移+12上的inc r4指令就变成了bra 4指令!换而言之,控制流图应该改成图9.7这个样子。
图9.6 代码的控制流图
图9.7 更改后的控制流图
从上例中,你是否得到这样的启示:如果运行时代码会被修改,那标准的控制流图就不够用了。算法REAMB对此进行了两方面的扩充:首先,在控制流图中增加了一个名为“代码字节”(codebyte)的结构体,以表示各条指令可能存在的不同状态。其次,它还给边加上了条件,只有当条件满足时,控制流才会沿着相应的边执行下去。下面我们将这个例子用算法REAMB重画其控制流图,如图9.8所示。
图9.8 用算法REAMB重画其控制流图
add指令由在偏移+9到+11上的
这三个字节组成。在图9.8中各个“代码字节”的地址已被添加了浅灰色底纹,而“代码字节”本身也已被添加了深灰色底纹。由于这三个字节在运行时不会改变,所以对于每个“代码字节”地址来说,只有一个可能的值。但是偏移+12处的情况就不同了,这里,这个值可能是3,也可能是4,分别表示指令inc和bra。而从add指令那个基本块出来的边就是条件边,它会根据偏移+12位置上究竟是3还是4而选择相应的边执行。
算法REAMB给出了一个非常漂亮的自修改代码表示法。不过在实践中,要画出一张由代码混淆算法生成的自修改代码对应的控制流图还是相当困难的!因为在上面这个例子中store指令使用的值还是很明显地直接存放在代码中的。我们可以想象,如果被修改代码的地址以及它将被改成什么值都是在程序运行时动态地算出来的话,相应的工作将会变得多么困难,甚至会变得不可判定!
3.识别循环
如果能从控制流图中把程序中所有循环都识别出来,无疑会是非常有用的。为了做到这一点,我们先来了解什么是必经结点。
如果控制流图中所有流向基本块B的路径都会经过基本块A,那么我们称A为B的必经结点(记为A dom B)。例如,在图9.9中,由于从B0(入口结点)出发流向B3、B4、B5的所有路径都要经过B2,所以B2就是B3、B4、B5的必经结点。
如图9.9(b)所示为控制流图9.9(a)所对应的必经结点树,它显示了控制流图中所有必经结点关系。如果在这棵树上有一条A→B的边,那么我们就称A是B的直接必经结点(记为A idom B)。
图9.9 必经节点控制流图范例
有了必经结点树,就能找出控制流图中的循环了。首先要在控制流图中找出回边(back edge)。所谓的“回边”是这样定义的:如果A是B的必经结点,且B有一条流向A的边,那这条边就被称为“回边”。在上例中,只有一条回边B5→B1。其中B1被称为循环的首结点。在必经结点树中,对于结点n,如果循环的首结点是它的必经结点,而且控制流能从n出发到达该首结点,循环中还恰巧只一条回边,那么n就一定是该循环中的一员。上例中,B1是结点B2、B3、B4、B5中任意一个的必经结点,而且控制流能从B2、B3、B4、B5中的任何一个流向B1,再加上那条回边B5→B1,所以B1、B2、B3、B4、B5就构成了控制流图中的一个循环。
4.过程间控制流分析
过程间分析代码一般是遵循这三个步骤进行的:局部分析——单独分析各个基本块;全局分析(又称过程内分析)——分析单个函数的整个控制流图;过程间分析——分析函数之间的调用关系。在传统的过程间分析中,函数间关系是用函数调用关系图表示的。函数调用关系图中的一个结点就表示程序中的一个函数,如果图中有一条边f→g,则表示函数f可能调用函数g。如果在这个图中出现了循环,则表示程序中有函数的递归调用,而如果不能从入口点到达某个结点的话,则说明在运行时该结点所代表的函数是不可达的。虽然从概念上来说,函数调用关系图中每个结点都可以展开成相应函数的控制流图,但在实践中,我们还是把函数调用关系图和控制流图视为各自独立的实体的。
由于在一个函数(f())中可能有多个地方调用了同一个函数(g()),所以函数调用关系图一般都是并联图(multi-graph)。
下面给出一个简单的程序及其函数调用关系图(图9.10)。
注意,图9.10中给出的函数调用关系图是错误的!因为根据函数调用关系图,我们判断函数k()不会被其他任何函数调用。可是分析下源码,main()函数会通过函数指针的形式调用k()!这个教训告诉你:函数调用关系图可不是这么好画出的,除非程序中不会以指针的形式调用函数。所以,在上例中,我们还得加上一条调用关系线,因为只有函数k()被取址,所以指针p中写入的一定是k()的地址,而main()函数通过p调用的就一定是k()。
图9.10 一个简单的程序及其函数调用关系图
在面向对象的语言中,由于方法都是通过指针调用的,所以你应该经常会遇到上述这类问题。幸而,有时简单的类型分析就能搞定这些讨厌的指针。我们来看下面这个Java程序。
如果只是单独考虑对象b,语句b.m()可能调用B:m方法,也可能调用C:m方法。因此,在函数调用关系图中我们必须要画上两条边——main→B:m和main→C:m。同样,如果不考虑程序中对a.m()的使用方式,语句a.m()可能调用A:m、B:m、C:m中的任意一个。若考虑了a.m()之前那条if-else语句,就能确定A:m是绝对不可能被调用的,只有B:m和C:m才可能会被调用!但是要让计算机对这一点也能明察秋毫,就必须使用下面要介绍的数据流分析技术。