基于同余方程和改进的压扁控制流的混淆算法

王 岩，黄章进，顾乃杰

(1.中国科学技术大学 计算机科学与技术学院，合肥 230027； 2.中国科学技术大学 安徽省计算与通信重点实验室，合肥 230027； 3.中国科学技术大学 先进技术研究院，合肥 230027)

基于同余方程和改进的压扁控制流的混淆算法

王 岩1,2,3，黄章进1,2,3*，顾乃杰1,2,3

(1.中国科学技术大学 计算机科学与技术学院，合肥 230027； 2.中国科学技术大学 安徽省计算与通信重点实验室，合肥 230027； 3.中国科学技术大学 先进技术研究院，合肥 230027)

(*通信作者电子邮箱zhuang@ustc.edu.cn)

针对现有控制流混淆算法的混淆结果单一的问题，提出了一种基于同余方程和改进的压扁控制流混淆算法。首先，使用密钥和一组同余方程来生成源代码的基本块中需要使用的不透明谓词；其次，基于Logistic混沌映射提出了一种新的N态不透明谓词构造算法，并将其应用到现有的压扁控制流算法中，对现有的压扁控制流算法进行改进；最后，将上述两个对源码进行混淆的算法结合，以此来增加源代码中控制流的复杂度，使其更难被破解。与现有的基于混沌不透明谓词的压扁控制流算法相比，所提混淆算法使混淆后代码的防篡改攻击时间平均提高了22%以上，总圈复杂度平均提高了34%以上。实验结果表明，所提算法能够保证混淆后程序执行结果的正确性并且具有很高的圈复杂度，能够有效地抵抗静态攻击和动态攻击。

代码混淆；N态不透明谓词；同余方程；压扁控制流算法

0 引言

近年来随着软件技术的飞速发展，软件代码的安全保护越来越引起人们的重视。为了提高软件的可靠性，代码混淆作为一种抵抗软件逆向分析的方法被提出[1]。代码混淆[2]是指对拟发布的应用程序进行保持语义转换，使得变换后的程序与原来的程序在功能上相同或相近，但更难被理解和反编译。Collberg等[2-5]将代码混淆分为外形混淆、数据混淆、预防性混淆和控制混淆四类。控制混淆相对于其他三种混淆具有更好的安全性，是当下代码混淆领域主要的研究热点。控制混淆主要依赖于不透明谓词[3]。Arboit[6]表明可以将谓词进行参数化来构造更加复杂的谓词，并提出了一种使用二次剩余构造不透明谓词的方法。但是，Myles等[7]在其实验中证明了使用二次剩余构造出的不透明谓词在安全性方面表现得很差。袁征等[8]提出了一种基于初等数论里面的同余方程来生成不透明谓词的方法。这种不透明谓词存在形式过于简单、安全性差的缺点，在逆向分析过程中较容易被过滤[1]。苏庆等[1]通过改进Logistic混沌映射，提出了一种新的混沌映射，使用该映射构造出了一种混沌不透明谓词，但是这种混沌不透明谓词只有在结果为真时才具有相对较高的密码安全性。

Wang[9]第一次提出了基于switch-case的控制流压扁算法。这个算法将源代码划分成基本块，将基本块打乱后放入switch-case结构中；由case中的条件变量来控制基本块的执行顺序，将其按照源码中基本块原来的执行顺序来执行；最后将switch封装到死循环中，当执行完最后一个基本块时，退出死循环。吴伟民等[10]在此基础上提出了N态二维混沌不透明谓词，将二态不透明谓词扩展成N态；然后将其应用于控制流压扁算法中的switch-case语句中的case常量表达式中。这在一定程度上提高了逆向分析的难度。但是，给case中控制下一步switch走向的变量赋的是常量值，使其暴露在攻击者的视野中，在一定程度上降低了破解的难度。

本文利用密钥和若干同余方程组解的状态来生成不透明谓词，并将其应用于源代码的基本块中，这种构造方法与陈代梅等[11]提出的使用同余方程和中国剩余定理来构造不透明谓词的方法相比，省去了对生成的多项式进行两两互素的计算，减少了计算时间，且产生的不透明谓词为True或False的几率基本相同。本文基于分段Logistic混沌映射[12]提出了一种新的N态混沌不透明谓词的构造算法，并将其与吴伟民等[10]改进的压扁控制流算法相结合，隐藏对case语句中控制变量的赋值。依此对源代码进行控制流混淆，混淆后的代码不仅具有很高的安全性，并且具有很高的圈复杂度，能够有效地抵抗逆向工程的攻击。

1 基本概念

1.1 不透明谓词

定义1 不透明谓词[1]。对于一个谓词P，如果程序中点p的输出在嵌入程序之前就已知，则该谓词P是不透明的。如果谓词P的输出永远为真，则记为PT；如果谓词P的输出永远为假，则记为PF；如果谓词的输出有时为真有时为假，则记为P?。

定义2 陷门不透明谓词[1]。令Kj为谓词P的密钥，若Kj已知，则混淆前很容易确定谓词P在程序中点p上的输出;否则若Kj未知，则混淆前难以确定谓词P在程序中点p上的输出，则称谓词为陷门不透明谓词。

定义3N态不透明谓词[10]。对于某一确定的实现机制，不透明谓词表达式P=E(O)的可能取值为1,2,…,N，其中O为谓词定义域，通过表达式映射E所对应的P构成了N态不透明谓词。

1.2 不透明谓词的插入

在程序中插入的不透明谓词主要有永真不透明谓词、永假不透明谓词、可真可假的不透明谓词。在程序中插入不透明谓词的方法如图1～3所示[11]，图中：Bi(i=1,2,3)表示程序中的基本块，f(Bi)表示基本块Bi的语义，实线表示可能的执行路径，虚线表示永远不会执行的路径，PT表示不透明谓词的输出为True，PF表示不透明谓词的输出为False，P?表示不透明谓词的输出为True或False，B2bug表示垃圾代码。不透明谓词的插入方式就是在基本块之间添加一个条件判断语句，根据不透明谓词输出的结果判断执行哪个基本块。

图1 永真不透明谓词

图2 永假不透明谓词(f(B2)≠f(B2bug))

图3 可真可假不透明谓词

2 代码混淆算法

本章首先描述不透明谓词的构造算法，然后提出基于分段Logistic映射的N态不透明谓词的构造算法，最后给出改进后的压扁控制流算法。

2.1 构造不透明谓词

记模素数p的Legendre符号为(d/p)。

同余方程[13]如下：

1)同余方程1：

x2=-1(modp)

(1)

当-1/p=1，即p=4k+1(k∈Z)时有解，设最小整数解为x1。

2)同余方程2：

x2=2(modp)

(2)

当2/p=1，即p=8k+1或p=8k+7(k∈Z)时有解，设最小整数解为x2。

3)同余方程3：

x2=-2(modp)

(3)

当-2/p=1，即p=8k+1或p=8k+3(k∈Z)时有解，设最小整数解为x3。

4)同余方程4：

x2=3(modp)

(4)

当3/p=1，即p=12k+1或p=12k+11(k∈Z)时有解，设最小整数解为x4。

5)同余方程5：

x2=-3(modp)

(5)

当-3/p=1，即p=6k+1(k∈Z)时有解，设最小整数解为x5。

本文构造不透明谓词的过程如下：

1)设Nj∈Z+(j=1,2,…,n)，随机生成Nj个整数(k1,k2,…,kNj)为谓词Pj的密钥，对于每个整数ki，根据式(1)～(5)中判定是否有解的等式(如p=4k+1)，将ki代入其中，至少有一个解p是素数。

3)对于每个Nj产生的五元组解，将每一组解中互相对应每一位进行异或操作，最后得到一个五元组解记为(r1,r2,…,r5)。

4)根据其中1的个数来判断不透明谓词的输出，当1的个数为奇数时不透明谓词输出为True，当1的个数为偶数时不透明谓词输出为False。

表1～2给出了本文提出的算法与陈代梅等[11]提出的算法在产生结果为True的不透明谓词的个数和产生不透明谓词的时间上的实验结果对比。

表1 结果为True的不透明谓词的个数对比

根据表1中的数据，本文提出的算法产生的不透明谓词结果为True或False的个数基本相同，产生10～10 000个不透明谓词时，结果为True的混沌不透明谓词分别占40%、47%、43.8%、45.1%，生成不透明谓词的个数越多，其百分比越接近50%，结果为True或False的混沌不透明谓词的个数越接近。本文提出的算法在生成不透明谓词的均衡性方面优于陈代梅等[11]提出的算法。

表2 产生不透明谓词的时间对比 ms

由表2的数据可知，在产生10个～10 000个不透明谓词时，使用本文提出的算法所消耗的时间相对于陈代梅等[11]提出的算法所消耗的时间分别降低了63.38%、68.79%、65.96%、64.06%，其开销小于使用陈代梅等[11]的算法产生的开销。

2.2 基于分段Logistic映射的N态不透明谓词构造算法

分段Logistic混沌映射[12]具有非线性性质，采用此映射生成混沌序列时不需要进行扰动运算，能够保证生成的算法具有更好的效率和安全性。定义如下：

(6)

其中，3.569 946…≤u≤4，a0∈(0,1)。

以下所述N态不透明谓词构造算法就是定义3中的实现机制E，而密钥(a0,u,fun)就是其中的谓词。本文构造N态不透明谓词的算法描述如下：

步骤1 根据式(6)对参数的要求，使用随机生成的二元组密钥(a0,u)进入混沌系统产生随机实数序列A={a1,a2,…,aN}。

步骤2 通过映射函数fun将实数序列A={a1,a2,…,aN}映射成整数序列F={F1,F2,…,FN}，此时添加映射函数后，密钥变成三元组：(a0,u,fun)。

步骤3 统计F中出现的不重复元素的个数t(t∈[1,N])，并将其对应的密钥存放在数组R中。

步骤4 不断重复步骤1～步骤3，训练出与不同t值对应的N个密钥。存放密钥的数组R={result1,result2,…,resultN}，其中resulti为步骤3中不重复元素个数t等于i时所对应的密钥(a0i,ui,fun)，以此类推。

假设Fi的取值范围为[0,m]，步骤2中使用的映射函数fun为：

Fi=Round{ai×m}

(7)

其中Round是取整函数。

2.3 改进的压扁控制流算法

在吴伟民等[10]提出的控制流压扁算法中，对控制变量的赋值为暴露在外的常量值，如算法1所示。针对这种情况，本文使用基于分段Logistic混沌映射产生的N态不透明谓词替换这些常量值，并将2.1节中生成不透明谓词的算法应用到程序中的基本块上。改进后的算法如算法2所示。

算法1 文献[10]提出的控制流压扁算法。

1)

next=2;

2)

while(next!= 1) {

3)

switch(next) {

4)

caseChaoOpp(ValuesOne):

5)

blockA;

6)

next=3;

7)

break;

8)

caseChaoOpp(ValuesTwo):

9)

blockB;

10)

next=1;

11)

break;

12)

}

13)

}

在算法1中，函数ChaoOpp是吴伟民等[10]提出的N态不透明谓词的生成方法，ValuesOne和ValuesTwo是其生成不透明谓词所需的密钥，blockA、blockB、blockC是程序中的基本块，在第1)、6)、10)行中，对next变量赋予的常量值直接暴露在外。

算法2 本文提出的改进的控制流压扁算法。

1)

next=logistic(R1);

2)

while(next!= 1) {

3)

switch(next){

4)

caseChaoOpp(ValuesOne):

5)

if(cPredic(PTrue))

6)

blockA;

7)

next=logistic(R2);

8)

break;

9)

caseChaoOpp(ValuesTwo):

10)

if(cPredic(PFalse)) {

11)

blockBug;}

12)

else{

13)

blockB;

14)

next=logistic(R3);

15)

break;

16)

}

17)

}

18)

}

在算法2中，函数logistic是本文基于分段Logistic映射产生N态不透明谓词的方法，参数R1～R3是使用2.2节中提出的算法生成的密钥，函数cPredic是2.1节中提出的生成不透明谓词的算法，其参数PTrue和PFalse分别是与其对应的生成永真和永假谓词的密钥，blockBug为插入的垃圾代码的基本块。使用这种算法让程序的控制流程更加难以被分析，安全性更高。

3 实验结果与分析

本文提出的算法均使用Python语言实现，并针对几个开源的Python程序进行性能测试。

3.1 正确性

对源码进行控制流混淆，首先必须保证其正确性，即混淆后的源码在功能上与混淆前的源码一致，并且拥有相同的输出结果。为了对本文提出的混淆算法进行测试，选了3个开源的Python工具进行测试，结果如表3所示。

表3 混淆前后程序功能对比

从表3中可以看出，混淆前后的输出结果相同。理论上分析，使用N态不透明谓词隐藏程序的控制流，并没有真正改变其基本块的执行顺序，因此并不会影响程序的功能和输出结果。

3.2 安全性

本文使用同余方程生成的不透明谓词以及生成的N态不透明谓词，其结果只有在执行的过程中才能确定，即本文生成的不透明谓词是陷门不透明谓词，静态分析并不能确定其输出结果，因此本文提出的生成不透明谓词的算法可以有效地抵抗静态攻击。

由于动态攻击的难点是确定不透明谓词的输出[11]。本文对于基本块中使用的谓词是通过密钥和同余方程的解产生，而N态不透明谓词的生成也是根据三元组或四元组密钥产生，且密钥是随机生成的，同余方程解的状态也是随机的，因此可以有效地抵抗动态攻击。

为了对本文提出的混淆算法进行测试，选了3个开源的Python程序进行防篡改攻击测试，具体统计结果如表4所示。

由表4中的数据可知， 相比使用文献[10]算法，使用本文算法Pycrypto-master混淆后产生的攻击时间增加了28.57%，Docutils增加了29.26%，Jieba-master增加了22.85%。混淆后代码的攻击时间相比于混淆前大大增加，并且使用本文算法比使用文献[10]算法产生的攻击时间平均高了22%以上，使代码变得更加难被篡改。

表4 代码的防篡改攻击能力对比 h

3.3 开销

开销主要表现在时间和空间上。时间方面的开销主要是判断不透明谓词的输出，空间方面的开销主要是插入更改控制流的代码。下面分别对表3中的开源测试案例进行混淆，并对比其混淆前后在时间和空间方面的开销。

3.3.1 时间开销

通过对表3中的开源测试用例进行混淆，混淆前后的时间开销如图4所示。从图4中可以看出，混淆后程序的执行时间比混淆前要长。其中：Docutils混淆后较混淆前运行时间增加了8.08%；Pycrypto-master增加了4.04%；Jieba-master增加了3.09%。但随着程序的不断增大，增加的时间开销会不断变小，却给程序的破解增加了非常大的难度，因此，这种算法是可取的。

图4 混淆前后测试用例的时间对比

3.3.2 空间开销

在空间开销方面，从图5中可以看出，混淆后的程序比混淆前的程序占用的空间增加了。其中：Pycrypto-master混淆后较混淆前运行空间增加了10.33%；Docutils增加了9.30%；Jieba-master增加了0.13%。但随着程序的不断增大，空间开销会越来越小，不会对程序造成很大的负担。

3.4 圈复杂度

现阶段并没有对混淆后程序的复杂度进行评价的统一标准。圈复杂度是衡量一个衡量程序复杂度的度量指标[14]。Radon[15]可以统计Python代码的总圈复杂度。通过多次实验，具体统计结果如表5所示。

图5 混淆前后测试用例的空间对比

程序混淆前文献[10]算法混淆后Pycrypto⁃master208328173935Docutils569771459616Jieba⁃master196248337

由表5中的数据可知：Pycrypto-master混淆后较混淆前的总圈复杂度增加了88.91%；Docutils增加了68.79%；Jieba-master增加了71.94%。与使用文献[10]算法相比，Pycrypto-master混淆后产生的总圈复杂度增加了39.69%；Docutils增加了34.58%；Jieba-master增加了35.89%。混淆后代码的总圈复杂度相比混淆前大大增加，并且比使用文献[10]算法产生的总圈复杂度平均提高了34%以上，代码变得更加复杂。因此，混淆后的代码更难被破解。

4 结语

本文提出了一种简单的基于密钥和同余方程解的状态的不透明谓词生成算法，可大量应用于基本块中。针对当前压扁控制流算法存在的弊端，提出了一种新的N态不透明谓词生成算法，并对原有的压扁控制流算法进行改进。最后在正确性、安全性、开销、圈复杂度等方面对本文提出的算法进行了评估。实验结果和分析表明本文提出的算法在正确性和安全性方面表现得很好，具备非常高的圈复杂度，能够有效地抵抗静态攻击和动态攻击。然而，提高代码的混淆度的同时，也增加了时间和空间开销。因此，对于如何在两者之间取得平衡，还需要进一步的研究。

)

[1] 苏庆,吴伟民,李忠良，等.混沌不透明谓词在代码混淆中的研究与应用[J].计算机科学,2013,40(6):155-159.(SUQ,WUWM,LIZL,etal.Researchandapplicationofchaosopaquepredicateincodeobfuscation[J].ComputerScience, 2013, 40(6): 155-159.)

[2]COLLBERGC,THOMBORSONC,LOWD.Ataxonomyofobfuscatingtransformations,TR#148[R].Auckland,NewZealand:UniversityofAuckland,1997.

[3]COLLBERGC,THOMBORSONC,LOWD.Manufacturingcheap,resilient,andstealthyopaqueconstructs[C] //Proceedingsofthe25thACMSIGLAN-SIGACTSymposiumonPrinciplesofProgrammingLanguages.NewYork:ACM, 1998: 184-196.

[4]COLLBERGC,THOMBORSONC,LOWD.Breakingabstractionsandun-structuringdatastructures[C] //ICCL’98:Proceedingsof1998InternationalConferenceonComputerLanguages.Piscataway,NJ:IEEE, 1998: 28-38.

[5]COLLBERGCS,THOMBORSONCD,LOWDWK.Obfuscationtechniquesforenhancingsoftwaresecurity:US, 6668325 [P]. 2003- 12- 23.

[6]ARBOITG.AmethodforwatermarkingJavaprogramsviaopaquepredicates[C/OL] //Proceedingsofthe2002InternationalConferenceonElectronicCommerceResearch. [2016- 10- 16].http://profs.scienze.univr.it/～giaco/download/Watermarking-Obfuscation/sp-paper.pdf.

[7]MYLESG,COLLBERGC.Softwarewatermarkingviaopaquepredicates:implementation,analysis,andattacks[J].ElectronicCommerceResearch, 2006, 6(2): 155-171.

[8] 袁征,冯雁,温巧燕,等.构造一种新的混淆Java程序的不透明谓词[J].北京邮电大学学报,2007,30(6):103-106.(YUANZ,FENGY,WENQY,etal.ManufactureofanewopaquepredicateforJavaprograms[J].JournalofBeijingUniversityofPostsandTelecommunications, 2007, 30(6): 103-106.)

[9]WANGCX.Asecurityarchitectureforsurvivabilitymechanisms[D].Charlottesville,VA:UniversityofVirginia, 2001: 65-68.

[10] 吴伟民,林水明,林志毅.一种基于混沌不透明谓词的压扁控制流算法[J].计算机科学,2015,42(5):178-182.(WUWM,LINSM,LINZY.Chaotic-basedopaquepredicatecontrolflowflattenalgorithm[J].ComputerScience, 2015, 42(5): 178-182.)

[11] 陈代梅,范希辉,朱静,等.基于同余方程和中国剩余定理的混淆算法[J].计算机应用研究,2015,32(2):485-488.(CHENDM,FANXH,ZHUJ,etal.ObfuscationalgorithmsbasedoncongruenceequationandChineseremaindertheorem[J].ApplicationResearchofComputers, 2015, 32(2): 485-488.)

[12] 王兴元,朱伟勇.二维Logistic映射中混沌与分形的研究[J].中国图象图形学报,1999,4(4):340-344.(WANGXY,ZHUWY.ResearchesonchaosandfractalofthecoupledLogisticmap[J].JournalofImageandGraphics,1999, 4(4): 340-344.)

[13] 潘承洞,潘承彪.简明数论[M].北京:北京大学出版社,1998:150-162.(PANCD,PANCB.SimplifiedNumberTheory[M].Beijing:PekingUniversityPress, 1998: 150-162.)

[14] 赵玉洁,汤战勇,王妮,等.代码混淆算法有效性评估[J].软件学报,2012,23(3):700-711.(ZHAOYJ,TANGZY,WANGN,etal.Evaluationofcodeobfuscatingtransformation[J].JournalofSoftware, 2012, 23(3): 700-711.)

[15]LACCHIAM.Radon:acodemetricstoolinPython[EB/OL]. [2016- 10- 16].https://pypi.python.org/pypi/radon.

ThisworkispartiallysupportedbytheAnhuiProvincialNaturalScienceFoundation(1408085MKL06),theProgramforInnovationoftheDisciplineHigherEducation(B07033).

WANG Yan, born in 1991, M.S. candidate. His research interests include software technology, program optimization.

HUANG Zhangjin, born in 1980, Ph. D., associate professor. His research interests include computer graphics, graphic processing unit computation.

GU Naijie, born in 1961, M. S., professor. His research interests include parallel algorithm, parallel processing, parallel architecture.

Obfuscating algorithm based on congruence equation and improved flat control flow

WANG Yan1,2,3, HUANG Zhangjin1,2,3*, GU Naijie1,2,3

(1.SchoolofComputerScienceandTechnology,UniversityofScienceandTechnologyofChina,HefeiAnhui230027,China; 2.AnhuiProvinceKeyLaboratoryofComputingandCommunicationSoftware,UniversityofScienceandTechnologyofChina,HefeiAnhui230027,China; 3.InstituteofAdvancedTechnology,UniversityofScienceandTechnologyofChina,HefeiAnhui230027,China)

Aiming at the simple obfuscating result of the existing control flow obfuscating algorithm, an obfuscating algorithm based on congruence equation and improved flat control flow was presented. First of all, a kind of opaque predicate used in the basic block of the source code was created by using secret keys and a group of congruence equation. Then, a new algorithm for creatingN-state opaque predicate was presented based on Logistic chaotic mapping. The proposed algorithm was applied to the existing flat control flow algorithm for improving it. Finally, according to the combination of the above two proposed algorithms for obfuscating the source code, the complexity of the flat control flow in the code was increased and make it more difficult to be cracked. Compared with the flat control flow algorithm based on chaotic opaque predicate, the code’s tamper-proof attack time of the obfuscated code was increased by above 22% on average and its code’s total cyclomatic complexity was improved by above 34% on average by using the proposed obfuscating algorithm. The experimental results show that, the proposed algorithm can guarantee the correctness of execution result of the obfuscated program and has a high cyclomatic complexity, so it can effectively resist static and dynamic attacks.

code obfuscation;N-State opaque predicate; congruence equation; flat control flow algorithm

2016- 11- 15;

2016- 12- 21。

安徽省自然科学基金资助项目(1408085MKL06)；高等学校学科创新引智计划项目(B07033)。

王岩(1991—)，男，山东济南人，硕士研究生，CCF会员，主要研究方向：软件技术、程序优化； 黄章进(1980—)，男，湖北天门人，副教授，博士，CCF会员，主要研究方向：计算机图形学、图形处理器计算； 顾乃杰(1961—)，男，江苏南通人，教授，硕士，CCF会员，主要研究方向：并行算法、并行处理、并行体系机构。

1001- 9081(2017)06- 1803- 05

10.11772/j.issn.1001- 9081.2017.06.1803

TP311.56

A