基于代码迷惑的软件保护

摘要：代码迷惑是软件防盗版、篡改和逆向工程的有效方法，但以前的代码迷惑技术多数缺乏理论依据，使得其保护效果不是十分明确。该文给出插入死代码和改变控制流两种迷惑技术，提出了新的代码迷惑模型，并利用NP-complete问题从理论上证明其可行性。最后，通过实例分析表明该模型具有很好的保护效果。

关键词：代码迷惑；NP-complete问题；软件保护

中文分类号：TP309文献标识码：A 文章编号：1009-3044(2011)01-0118-03

近年来随着计算机网络技术的发展，更多的软件运行在不确定的环境下，可以被任意地分析、跟踪、篡改等。再加上各种静态分析、逆向工程技术的不断进步，使得对软件攻击变得更加容易。针对软件面临的安全问题， 学者们提出了许多软件保护技术 ，主要包括: 软件篡改抵制、软件加密、软件水印、代码迷惑等。其中代码迷惑技术作为一个与加密技术互补的, 针对逆向工程的安全分支, 正受到越来越多的关注。

代码迷惑是一种保持语义的程序变换技术。它通过加大程序复杂度并降低程序的可读性来提高软件的安全性。加大程序的复杂度使得攻击者很难利用工具破解并分析软件；降低程序的可读性则可以使攻击者即便获得软件源代码也无法理解程序的功能。尽管Barak等人[2]在理论上证明了没有硬件支持的代码迷惑技术不能为软件提供彻底的保护。但在实际应用中，代码迷惑的目的并不是为软件提供绝对的保护，只要能保证程序在有效期内不被攻击者攻破，就达到了保护的目的。

目前代码迷惑技术有许多种，这些技术多数只在某个方面增大了攻击者理解程序的难度。例如“Linn等人[4]的插人花指令方法增加了对程序进行正确反汇编的难度，Li等人[5]的基于函数指针迷惑算法增加了分析函数调用的难度，而Wang等人[6]的压平算法则增加了理解控制流转换关系的难度。所以仅仅依赖其中的一种迷惑技术并不一定能有效增强程序安全，因为攻击方法灵活多变，攻击者可以综合运用各种技巧避开这些复杂性，从其他薄弱环节来进行攻击，窜改代码以达到预期目的。

本文将阐述两种代码迷惑技术：插入死代码或无关代码的迷惑和改变控制流迷惑；综合利用这些技术给出一个代码迷惑模型的实现方案。

1 插入死代码或无关代码的迷惑

死代码是指在程序运行时不会执行到的代码，无关代码是执行不会影响程序功能的代码。插入死代码或无关代码即所谓的添加冗余指令，是代码迷惑变换策略中的一种有效方法。死代码或无关代码也叫做伪指令、垃圾指令，该技术的主要特点是通过在程序体中插入无效指令或不影响原始代码功能的无用指令来破坏反汇编的结果和增加代码分析的难度，以达到加密保护的目的。

Linn在他的文章[4]中分析了传统静态反汇编算法，并给出利用垃圾指令阻止反汇编的方法。本文在其研究成果的基础上提出了一种简单有效的代码迷惑方法，具体分两步实现。

第一步，将符合一定规则的冗余指令集中在一起，如表1；左边一列是规则，右边一列给出相应的含义。第一行功能是把0值加到一个寄存器中，第二行功能是将寄存器的值放入本寄存器中，第三行把一个寄存器的值与0进行逻辑或，第四行把一个寄存器的值与-1进行逻辑与。

第二步，随机抽取若干个无用指令组成一定数量的死代码块。并把他们插入程序的执行体中，图1给出常用的死代码块。

根据上面的方法进行代码迷惑可以增加攻击者分析理解程序的难度，对软件能产生很好的保护效果。

2 改变控制流的迷惑

改变控制流迷惑的原理是对程序执行流扰乱，是程序执行流中各个基本块的前驱或后继基本块发生改变，以达到迷惑。这种方法在实际应用中使用广泛且效果好，目前已经有许多这方面比较成熟的技术，如Wang等人使用的压平技术，Li等人使用的函数指针的思想。本文主要针对程序顺序结构提出一种新的执行流迷惑的方法，该方法的主要思路是：重新安排线性执行的语句模块在程序中的物理位置，而在逻辑上执行顺序与原程序执行顺序相同，即在保持程序的功能不变的情况下利用条件跳转或无条件跳转对程序的执行顺序进行改变。图2给出了改变控制流的迷惑示意图。

图2通过插入无条件分支指令来给出一个修改控制流的实例；一段原本顺序执行的程序被两段带有复杂分支的程序段替代，但这两段程序的功能和原始程序段是一样。

3 构造代码迷惑模型

本节首先从理论上讨论构建迷惑器的可能性，为此将给出相关的定义和命题并加以证明；然后提出一个可行的设计方案。

3.1 基本概念和命题

定义 代码变换。假设程序 P 是由n个指令序列I1I2…In组成，将P分成K个代码块P1P2…Pk其中任意一块Pi包含一定数量非空操作的随机指令序列且以一顺序指令结束。现在集合[1,k]中有一个序列σ，对于其中的每一个代码块Pi，都对应一个新的代码块P'σ(i)且满足每一个代码块P'σ(i)包含与代码块Pi相同的指令和转向两个其它代码块P'j , P'1的条件分支指令结束。 称这种由 P 到P'的转换叫代码变换。表示为P'=T(p)。

进一步，可以定义一组迷惑器（K-obfuscators） 记为Ok。如果i ∈ [1, k]且在程序执行期代码块P'σ(i)最终跳转到P'σ(i+1)，这样一个代码变换T就包含一组迷惑器；表示为T∈Ok。根据最后输出，可以确定代码块P'σ(i)内条件分支跳转目标。

需要注意的是，如果T∈Ok且P=T(p)，那么变换T就只包含一个迷惑器。

命题 假设程序中每一条分支路径都可能执行，对于任何一对程序段P 和P'确定是否存在T∈Ok使得P'=T(p)是一个NP-complete问题。

证明 依据Wang 、Ogiso等人在文献[6-7]中的结论，每一对符合上述定义的程序段P 和P'都存在一个不确定算法来检测在多项式时间里是否存在一个变换T使得P'=T(p)；同时这个算法也能够验证在多项式时间里是否每个代码块P'σ(i)都有一个输出，使得T∈Ok。因此命题是一个NP问题。

假设S是NP-complete的第一个问题3-SAT中一个实例，P是满足定义的一段程序。下面来证明命题可归约为一个3-SAT问题。

由于S是3-SAT问题的一个实例，则S可表示为：并有

其中v1,v2……vm是一组布尔型变量。

根据以上描述可在集合(1,2,3,……,n-1,n)上建立满足如下条件的3-SAT问题的实例S，其中(ui)i∈[1,k]是集合上一组顺序子集。

现假设有一个满足定义的变换T，使得P'是P经过T变换后的程序段，其中每一块代码(Pi')i∈[1,k]是由(Pi)i∈[1,k]代码块使用一个迷惑器得到的。具体过程如图3。

1）P'0代码块实现对程序段P'的初始化，其伪代码如图4。首先是每一个布尔型变量Vi和Vi被声明为函数指针的指针，使每一个这种变量可能指向第二行的true或false 。这样每一个Vi和Vi对应公式S中一个布尔变量和它的否定变量，因此在S中设置vi和在程序段P'中设置*vi= true是一致的。代码块的其余部分完成对变量Vi和Vi初始化。就如同在方程式S中修改布尔变量vi一样。共有两种情况可选：一种是vi满足S，另一种vi不满足S。

2）代码块Pi，i∈[1,k-1]变换为P?i的过程如图5，首先指针false被初始化为代码块P'i+1的地址。接着，将代码块Pi插入使得P'i和Pi具有相同的功能。其次，代码根据代码块P'0中初始化变量Vi和Vi的值修改指针false的值。最后false函数被调用。另外，为了终止程序段P'代码块P'k和其他的代码块稍微不同。下面分两步证明上述的程序变换问题和S实例等价。

第一步 当S满足；那么对i ∈ [1, k] si一定满足条件，相应地在伪代码级别上j ∈[min(ui),max(ui)]，lj,1或lj,2或lj,3指向true变量，因此至少有一个文字lj,t,t∈[1, 3]指向true变量，这样在图5中的false变量不会被重新赋值。在这种情况下，代码块P'i执行后跳转到P'i+1，所以有T∈Ok；即如果S满足则T∈Ok。

第二步 当T∈Ok满足，那么对于每一个i，P'i执行结果将转向P'i+1。由图5可知在代码块P'i中变量false指向P'i+1，因此至少有一个文字lj,t,t∈[1, 3],指向true变量，这表明Si是满足的，进一步可得出S，所以有如果T∈Ok则S满足。上述两步的证明可知程序变换问题和S实例是等价的。

3.2 设计代码迷惑模型

根据3.1中命题的证明过程，代码迷惑模型构建步骤为：

1）分割程序段，将包含n条指令(Ij)j∈ [1, n]程序段P划分成K个随机大小且非空的代码块(Pi)l∈ [1, k]，并要求每个代码块中不能以goto或ret 语句结束。图6给出一个分割程序段的实例。

2）构建死代码块，依据1节中介绍的代码迷惑技术建立指令序列块(Gi)l∈ [1, P]来提高程序反静态分析的难度，每一个序列块都是随机非空。

3）生成代码迷惑程序段P'，首先在开始代码块P'0中初始化一个布尔型变量K作为代码块P'i执行后的跳转判定条件并保证最终P'=P；然后，对于i ∈ [1, k+p]中的代码块P'i生成需要考虑两种情况；一种是当P'i为功能代码块时，也就是P'i中包含Ps且!s∈ [1, k]。代码块P'i结尾的条件跳转分支中必须有一个执向P'i+1，一个随机指向任意代码块；另一种是当P'i为死代码块时，也就是P'i中包含Gt且!t∈ [1, p]。代码块P'i结尾的条件跳转分支可以指向任意其它的代码块。

4 性能分析

本节针对上节提出的代码迷惑模型设计出一个实例，并给出代码迷惑变换后的程序段示意图。通过对其进行分析可以看出迷惑后的程序具有很强的保护能力。

1）实例设计，首先将原程序段划分成图6中所示：P1、P2、P3、P4、P55个功能代码块，并使其满足3.1中的定义要求。然后构建出两个死代码块G1、G2。最后将5个功能代码块和2个死代码块依据代码迷惑模型进行图7所示的代码变换。

2）实例分析，代码块P'0初始化布尔变量(xi)i∈[1,6]的值用来确定每一个代码块的跳转目标。例如，当x1=1时，代码块P1跳转到P2执行而不是跳转到G2去。为了保证代码迷惑后程序的执行顺序不变，则程序的实际执行过程如图5所示，因此必须满足i ∈[1,4] ,xi=1，而在代码迷惑模型中提到K值不确定的情况下，程序段P'可能的执行路径为2k+p-1条。

布尔变量x5、x6作为死代码块G1、G2跳转条件，在保证P'P条件下，这两块代码是不能得到执行的。因此，在假设x5、x6的值为NULL情况下，代码迷惑后程序段P'可能执行路径如表1。表中给出程序段P'四种执行结果分别为：

当K= 1，4，5，6，7，9，13时，程序执行死循环。

当K= 0，2，3，8，10，11时，程序执行发生错误。

当K= 12，14时，程序可以得到执行，但其执行的顺序和原程序不一致。

当且仅当K= 15时，程序和代码迷惑前一致。

从上述的分析可知原程序经过代码迷惑后，原本只有一条执行路径的程序变为有16条可执行路径，这就非常明显的提高程序的复杂性，增加了程序的分析理解难度。

5 结束语

本文给出了一种基于控制流转换方法来构造迷惑模型的实现方案。从性能分析角度来看，插入死代码和改变控制流迷惑都会使得程序的复杂度有所提高，并降低程序的可读性，如果再结合防篡改技术，对软件会有更好的保护效果。

参考文献：

[1] Collberg C,Thomborson C,Low D.Breaking abstractions and unstructuring data structures[C].In Proc IEEE InternationalConference on Computer Languages,1998:28-38.

[2] Barak B.On the(Im)possibility of Obfuscating Programs[C].Proc of 21 Ann.Int'1 Cryptology Conf,2001:1-18.

[3] Collberg C S,Thomhomon C.Watermarking，Tamper-proofing and Obfuscation-Tools for Software Protection[J].IEEE Transactions on Software Engineering,2002,8(8).

[4] LINN C,DEBRAY S.Obfuscation of executable code to improve resistance to static disassembly[C]//Proc of the 10th ACM CCS'03.New York:ACM Press,2003:290-299.

[5] LI Yong-xia,CHEN Yi-yun.Technique of code obfuscation based on function tointer array[J].Chinese Journal of Computers,2004,27(12):1706-1711.

[6] WANG Chen-xi.A security architecture for survivability me-chanisms[D].Charlottes:Department of Computer Science，University of Virginia,2000.

[7] Ogiso T,Sakabe Y,Soshi M,Miyaji A.Softwate tamper resitance based on the difficulty of interprocdeural analysis[C]//The Third International Workshop on Information Security Applications,2002:437-452.