2. 中国科学技术大学 安徽省计算与通信重点实验室, 合肥 230027;
3. 中国科学技术大学 先进技术研究院, 合肥 230027
2. Anhui Province Key Laboratory of Computing and Communication Software, University of Science and Technology of China, Hefei Anhui 230027, China;
3. Institute of Advanced Technology, University of Science and Technology of China, Hefei Anhui 230027, China
近年来随着软件技术的飞速发展,软件代码的安全保护越来越引起人们的重视。为了提高软件的可靠性,代码混淆作为一种抵抗软件逆向分析的方法被提出[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上的输出,则称谓词为陷门不透明谓词。
定义3 N态不透明谓词[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表示垃圾代码。不透明谓词的插入方式就是在基本块之间添加一个条件判断语句,根据不透明谓词输出的结果判断执行哪个基本块。
本章首先描述不透明谓词的构造算法,然后提出基于分段Logistic映射的N态不透明谓词的构造算法,最后给出改进后的压扁控制流算法。
2.1 构造不透明谓词使用Pj表示构造出的不透明谓词,本文使用密钥并基于若干组同余方程[13]的解的状态来对不透明谓词{Pj}j=1j=n(j=1, 2, …, n)进行参数化。
记模素数p的Legendre符号为(d/p)。
同余方程[13]如下:
1) 同余方程1:
$ {x^2} = - 1({\rm mod} p) $ | (1) |
当-1/p=1,即p=4k+1(k∈Z)时有解,设最小整数解为x1。
2) 同余方程2:
$ {x^2} = 2({\rm mod} p) $ | (2) |
当2/p=1,即p=8k+1或p=8k+7(k∈Z)时有解,设最小整数解为x2。
3) 同余方程3:
$ {x^2} = - 2({\rm mod} p) $ | (3) |
当-2/p=1,即p=8k+1或p=8k+3(k∈Z)时有解,设最小整数解为x3。
4) 同余方程4:
$ {x^2} = 3({\rm mod} p) $ | (4) |
当3/p=1,即p=12k+1或p=12k+11(k∈Z)时有解,设最小整数解为x4。
5) 同余方程5:
$ {x^2} = - 3({\rm mod} p) $ | (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是素数。
2) 确定p后,根据式(1)~(5) 解出(xi)i=1i=5。当xi有解时记为1,无解时记为0,最后将(xi)i=1i=5放入数组中,形成一个五元组(x1, x2, …, x5)。
3) 对于每个Nj产生的五元组解,将每一组解中互相对应每一位进行异或操作,最后得到一个五元组解记为(r1, r2, …, r5)。
4) 根据其中1的个数来判断不透明谓词的输出,当1的个数为奇数时不透明谓词输出为True,当1的个数为偶数时不透明谓词输出为False。
表 1~2给出了本文提出的算法与陈代梅等[11]提出的算法在产生结果为True的不透明谓词的个数和产生不透明谓词的时间上的实验结果对比。
根据表 1中的数据,本文提出的算法产生的不透明谓词结果为True或False的个数基本相同,产生10~10 000个不透明谓词时,结果为True的混沌不透明谓词分别占40%、47%、43.8%、45.1%,生成不透明谓词的个数越多,其百分比越接近50%,结果为True或False的混沌不透明谓词的个数越接近。本文提出的算法在生成不透明谓词的均衡性方面优于陈代梅等[11]提出的算法。
由表 2的数据可知,在产生10个~10 000个不透明谓词时,使用本文提出的算法所消耗的时间相对于陈代梅等[11]提出的算法所消耗的时间分别降低了63.38%、68.79%、65.96%、64.06%,其开销小于使用陈代梅等[11]的算法产生的开销。
2.2 基于分段Logistic映射的N态不透明谓词构造算法分段Logistic混沌映射[12]具有非线性性质,采用此映射生成混沌序列时不需要进行扰动运算,能够保证生成的算法具有更好的效率和安全性。定义如下:
$ \begin{array}{l} \;\;\;\;\;\;{a_{n + 1}} = \\ \left\{ \begin{array}{l} 4 \times u \times {a_n} \times (0.5 - {a_n}), \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;0 \le {a_n} < 0.5\\ 1 - 4 \times u \times {a_n} \times (0.5 - {a_n}) \times (1 - {a_n}), 0.5 \le {a_n} \le 1 \end{array} \right. \end{array} $ | (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为:
$ {F_i} = Round\left\{ {{a_i} \times m} \right\} $ | (7) |
其中Round是取整函数。
2.3 改进的压扁控制流算法在吴伟民等[10]提出的控制流压扁算法中,对控制变量的赋值为暴露在外的常量值,如算法1所示。针对这种情况,本文使用基于分段Logistic混沌映射产生的N态不透明谓词替换这些常量值,并将2.1节中生成不透明谓词的算法应用到程序中的基本块上。改进后的算法如算法2所示。
算法1 文献[10]提出的控制流压扁算法。
1) next=2;
2) while (next!= 1) {
3) switch (next) {
4) case ChaoOpp(ValuesOne):
5) blockA;
6) next=3;
7) break;
8) case ChaoOpp(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) case ChaoOpp(ValuesOne):
5) if (cPredic(PTrue))
6) blockA;
7) next=logistic(R2);
8) break;
9) case ChaoOpp(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中可以看出,混淆前后的输出结果相同。理论上分析,使用N态不透明谓词隐藏程序的控制流,并没有真正改变其基本块的执行顺序,因此并不会影响程序的功能和输出结果。
3.2 安全性本文使用同余方程生成的不透明谓词以及生成的N态不透明谓词,其结果只有在执行的过程中才能确定,即本文生成的不透明谓词是陷门不透明谓词,静态分析并不能确定其输出结果,因此本文提出的生成不透明谓词的算法可以有效地抵抗静态攻击。
由于动态攻击的难点是确定不透明谓词的输出[11]。本文对于基本块中使用的谓词是通过密钥和同余方程的解产生,而N态不透明谓词的生成也是根据三元组或四元组密钥产生,且密钥是随机生成的,同余方程解的状态也是随机的,因此可以有效地抵抗动态攻击。
为了对本文提出的混淆算法进行测试,选了3个开源的Python程序进行防篡改攻击测试,具体统计结果如表 4所示。
由表 4中的数据可知,相比使用文献[10]算法,使用本文算法Pycrypto-master混淆后产生的攻击时间增加了28.57%,Docutils增加了29.26%,Jieba-master增加了22.85%。混淆后代码的攻击时间相比于混淆前大大增加,并且使用本文算法比使用文献[10]算法产生的攻击时间平均高了22%以上,使代码变得更加难被篡改。
3.3 开销开销主要表现在时间和空间上。时间方面的开销主要是判断不透明谓词的输出,空间方面的开销主要是插入更改控制流的代码。下面分别对表 3中的开源测试案例进行混淆,并对比其混淆前后在时间和空间方面的开销。
3.3.1 时间开销通过对表 3中的开源测试用例进行混淆,混淆前后的时间开销如图 4所示。从图 4中可以看出,混淆后程序的执行时间比混淆前要长。其中:Docutils混淆后较混淆前运行时间增加了8.08%;Pycrypto-master增加了4.04%;Jieba-master增加了3.09%。但随着程序的不断增大,增加的时间开销会不断变小,却给程序的破解增加了非常大的难度,因此,这种算法是可取的。
在空间开销方面,从图 5中可以看出,混淆后的程序比混淆前的程序占用的空间增加了。其中:Pycrypto-master混淆后较混淆前运行空间增加了10.33%;Docutils增加了9.30%;Jieba-master增加了0.13%。但随着程序的不断增大,空间开销会越来越小,不会对程序造成很大的负担。
现阶段并没有对混淆后程序的复杂度进行评价的统一标准。圈复杂度是衡量一个衡量程序复杂度的度量指标[14]。Radon[15]可以统计Python代码的总圈复杂度。通过多次实验,具体统计结果如表 5所示。
由表 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. ( SU Q, WU W M, LI Z L, et al. Research and application of chaos opaque predicate in code obfuscation[J]. Computer Science, 2013, 40(6): 155-159. ) |
[2] | COLLBERG C, THOMBORSON C, LOW D. A taxonomy of obfuscating transformations, TR #148[R]. Auckland, New Zealand:University of Auckland, 1997. https://www.researchgate.net/publication/37987523_A_Taxonomy_of_Obfuscating_Transformations |
[3] | COLLBERG C, THOMBORSON C, LOW D. Manufacturing cheap, resilient, and stealthy opaque constructs[C]//Proceedings of the 25th ACM SIGLAN-SIGACT Symposium on Principles of Programming Languages. New York:ACM, 1998:184-196. |
[4] | COLLBERG C, THOMBORSON C, LOW D. Breaking abstractions and un-structuring data structures[C]//ICCL'98:Proceedings of 1998 International Conference on Computer Languages. Piscataway, NJ:IEEE, 1998:28-38. |
[5] | COLLBERG C S, THOMBORSON C D, LOW D W K. Obfuscation techniques for enhancing software security:US, 6668325[P]. 2003-12-23. https://link.springer.com/chapter/10.1007/978-3-319-08509-8_1 |
[6] | ARBOIT G. A method for watermarking Java programs via opaque predicates[C/OL]//Proceedings of the 2002 International Conference on Electronic Commerce Research.[2016-10-16]. http://profs.scienze.univr.it/~giaco/download/Watermarking-Obfuscation/sp-paper.pdf. |
[7] | MYLES G, COLLBERG C. Software watermarking via opaque predicates:implementation, analysis, and attacks[J]. Electronic Commerce Research, 2006, 6(2): 155-171. doi: 10.1007/s10660-006-6955-z |
[8] | 袁征, 冯雁, 温巧燕, 等. 构造一种新的混淆Java程序的不透明谓词[J]. 北京邮电大学学报, 2007, 30(6): 103-106. ( YUAN Z, FENG Y, WEN Q Y, et al. Manufacture of a new opaque predicate for Java programs[J]. Journal of Beijing University of Posts and Telecommunications, 2007, 30(6): 103-106. ) |
[9] | WANG C X. A security architecture for survivability mechanisms[D]. Charlottesville, VA:University of Virginia, 2001:65-68. https://link.springer.com/chapter/10.1007/978-3-642-10467-1_65 |
[10] | 吴伟民, 林水明, 林志毅. 一种基于混沌不透明谓词的压扁控制流算法[J]. 计算机科学, 2015, 42(5): 178-182. ( WU W M, LIN S M, LIN Z Y. Chaotic-based opaque predicate control flow flatten algorithm[J]. Computer Science, 2015, 42(5): 178-182. doi: 10.11896/j.issn.1002-137X.2015.05.036 ) |
[11] | 陈代梅, 范希辉, 朱静, 等. 基于同余方程和中国剩余定理的混淆算法[J]. 计算机应用研究, 2015, 32(2): 485-488. ( CHEN D M, FAN X H, ZHU J, et al. Obfuscation algorithms based on congruence equation and Chinese remainder theorem[J]. Application Research of Computers, 2015, 32(2): 485-488. ) |
[12] | 王兴元, 朱伟勇. 二维Logistic映射中混沌与分形的研究[J]. 中国图象图形学报, 1999, 4(4): 340-344. ( WANG X Y, ZHU W Y. Researches on chaos and fractal of the coupled Logistic map[J]. Journal of Image and Graphics, 1999, 4(4): 340-344. doi: 10.11834/jig.19990481 ) |
[13] | 潘承洞, 潘承彪. 简明数论[M]. 北京: 北京大学出版社, 1998 : 150 -162. ( PAN C D, PAN C B. Simplified Number Theory[M]. Beijing: Peking University Press, 1998 : 150 -162. ) |
[14] | 赵玉洁, 汤战勇, 王妮, 等. 代码混淆算法有效性评估[J]. 软件学报, 2012, 23(3): 700-711. ( ZHAO Y J, TANG Z Y, WANG N, et al. Evaluation of code obfuscating transformation[J]. Journal of Software, 2012, 23(3): 700-711. ) |
[15] | LACCHIA M. Radon:a code metrics tool in Python[EB/OL].[2016-10-16]. https://pypi.python.org/pypi/radon. |