基于同余方程和改進(jìn)的壓扁控制流的混淆算法

王 巖，黃章進(jìn)，顧乃杰

(1.中國科學(xué)技術(shù)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230027； 2.中國科學(xué)技術(shù)大學(xué) 安徽省計算與通信重點(diǎn)實(shí)驗(yàn)室，合肥 230027； 3.中國科學(xué)技術(shù)大學(xué) 先進(jìn)技術(shù)研究院，合肥 230027)

基于同余方程和改進(jìn)的壓扁控制流的混淆算法

王 巖1,2,3，黃章進(jìn)1,2,3*，顧乃杰1,2,3

(1.中國科學(xué)技術(shù)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230027； 2.中國科學(xué)技術(shù)大學(xué) 安徽省計算與通信重點(diǎn)實(shí)驗(yàn)室，合肥 230027； 3.中國科學(xué)技術(shù)大學(xué) 先進(jìn)技術(shù)研究院，合肥 230027)

(*通信作者電子郵箱zhuang@ustc.edu.cn)

針對現(xiàn)有控制流混淆算法的混淆結(jié)果單一的問題，提出了一種基于同余方程和改進(jìn)的壓扁控制流混淆算法。首先，使用密鑰和一組同余方程來生成源代碼的基本塊中需要使用的不透明謂詞；其次，基于Logistic混沌映射提出了一種新的N態(tài)不透明謂詞構(gòu)造算法，并將其應(yīng)用到現(xiàn)有的壓扁控制流算法中，對現(xiàn)有的壓扁控制流算法進(jìn)行改進(jìn)；最后，將上述兩個對源碼進(jìn)行混淆的算法結(jié)合，以此來增加源代碼中控制流的復(fù)雜度，使其更難被破解。與現(xiàn)有的基于混沌不透明謂詞的壓扁控制流算法相比，所提混淆算法使混淆后代碼的防篡改攻擊時間平均提高了22%以上，總?cè)?fù)雜度平均提高了34%以上。實(shí)驗(yàn)結(jié)果表明，所提算法能夠保證混淆后程序執(zhí)行結(jié)果的正確性并且具有很高的圈復(fù)雜度，能夠有效地抵抗靜態(tài)攻擊和動態(tài)攻擊。

代碼混淆；N態(tài)不透明謂詞；同余方程；壓扁控制流算法

0 引言

近年來隨著軟件技術(shù)的飛速發(fā)展，軟件代碼的安全保護(hù)越來越引起人們的重視。為了提高軟件的可靠性，代碼混淆作為一種抵抗軟件逆向分析的方法被提出[1]。代碼混淆[2]是指對擬發(fā)布的應(yīng)用程序進(jìn)行保持語義轉(zhuǎn)換，使得變換后的程序與原來的程序在功能上相同或相近，但更難被理解和反編譯。Collberg等[2-5]將代碼混淆分為外形混淆、數(shù)據(jù)混淆、預(yù)防性混淆和控制混淆四類?？刂苹煜鄬τ谄渌N混淆具有更好的安全性，是當(dāng)下代碼混淆領(lǐng)域主要的研究熱點(diǎn)?？刂苹煜饕蕾囉诓煌该髦^詞[3]。Arboit[6]表明可以將謂詞進(jìn)行參數(shù)化來構(gòu)造更加復(fù)雜的謂詞，并提出了一種使用二次剩余構(gòu)造不透明謂詞的方法。但是，Myles等[7]在其實(shí)驗(yàn)中證明了使用二次剩余構(gòu)造出的不透明謂詞在安全性方面表現(xiàn)得很差。袁征等[8]提出了一種基于初等數(shù)論里面的同余方程來生成不透明謂詞的方法。這種不透明謂詞存在形式過于簡單、安全性差的缺點(diǎn)，在逆向分析過程中較容易被過濾[1]。蘇慶等[1]通過改進(jìn)Logistic混沌映射，提出了一種新的混沌映射，使用該映射構(gòu)造出了一種混沌不透明謂詞，但是這種混沌不透明謂詞只有在結(jié)果為真時才具有相對較高的密碼安全性。

Wang[9]第一次提出了基于switch-case的控制流壓扁算法。這個算法將源代碼劃分成基本塊，將基本塊打亂后放入switch-case結(jié)構(gòu)中；由case中的條件變量來控制基本塊的執(zhí)行順序，將其按照源碼中基本塊原來的執(zhí)行順序來執(zhí)行；最后將switch封裝到死循環(huán)中，當(dāng)執(zhí)行完最后一個基本塊時，退出死循環(huán)。吳偉民等[10]在此基礎(chǔ)上提出了N態(tài)二維混沌不透明謂詞，將二態(tài)不透明謂詞擴(kuò)展成N態(tài)；然后將其應(yīng)用于控制流壓扁算法中的switch-case語句中的case常量表達(dá)式中。這在一定程度上提高了逆向分析的難度。但是，給case中控制下一步switch走向的變量賦的是常量值，使其暴露在攻擊者的視野中，在一定程度上降低了破解的難度。

本文利用密鑰和若干同余方程組解的狀態(tài)來生成不透明謂詞，并將其應(yīng)用于源代碼的基本塊中，這種構(gòu)造方法與陳代梅等[11]提出的使用同余方程和中國剩余定理來構(gòu)造不透明謂詞的方法相比，省去了對生成的多項(xiàng)式進(jìn)行兩兩互素的計算，減少了計算時間，且產(chǎn)生的不透明謂詞為True或False的幾率基本相同。本文基于分段Logistic混沌映射[12]提出了一種新的N態(tài)混沌不透明謂詞的構(gòu)造算法，并將其與吳偉民等[10]改進(jìn)的壓扁控制流算法相結(jié)合，隱藏對case語句中控制變量的賦值。依此對源代碼進(jìn)行控制流混淆，混淆后的代碼不僅具有很高的安全性，并且具有很高的圈復(fù)雜度，能夠有效地抵抗逆向工程的攻擊。

1 基本概念

1.1 不透明謂詞

定義1 不透明謂詞[1]。對于一個謂詞P，如果程序中點(diǎn)p的輸出在嵌入程序之前就已知，則該謂詞P是不透明的。如果謂詞P的輸出永遠(yuǎn)為真，則記為PT；如果謂詞P的輸出永遠(yuǎn)為假，則記為PF；如果謂詞的輸出有時為真有時為假，則記為P?。

定義2 陷門不透明謂詞[1]。令Kj為謂詞P的密鑰，若Kj已知，則混淆前很容易確定謂詞P在程序中點(diǎn)p上的輸出;否則若Kj未知，則混淆前難以確定謂詞P在程序中點(diǎn)p上的輸出，則稱謂詞為陷門不透明謂詞。

定義3N態(tài)不透明謂詞[10]。對于某一確定的實(shí)現(xiàn)機(jī)制，不透明謂詞表達(dá)式P=E(O)的可能取值為1,2,…,N，其中O為謂詞定義域，通過表達(dá)式映射E所對應(yīng)的P構(gòu)成了N態(tài)不透明謂詞。

1.2 不透明謂詞的插入

在程序中插入的不透明謂詞主要有永真不透明謂詞、永假不透明謂詞、可真可假的不透明謂詞。在程序中插入不透明謂詞的方法如圖1～3所示[11]，圖中：Bi(i=1,2,3)表示程序中的基本塊，f(Bi)表示基本塊Bi的語義，實(shí)線表示可能的執(zhí)行路徑，虛線表示永遠(yuǎn)不會執(zhí)行的路徑，PT表示不透明謂詞的輸出為True，PF表示不透明謂詞的輸出為False，P?表示不透明謂詞的輸出為True或False，B2bug表示垃圾代碼。不透明謂詞的插入方式就是在基本塊之間添加一個條件判斷語句，根據(jù)不透明謂詞輸出的結(jié)果判斷執(zhí)行哪個基本塊。

圖1 永真不透明謂詞

圖2 永假不透明謂詞(f(B2)≠f(B2bug))

圖3 可真可假不透明謂詞

2 代碼混淆算法

本章首先描述不透明謂詞的構(gòu)造算法，然后提出基于分段Logistic映射的N態(tài)不透明謂詞的構(gòu)造算法，最后給出改進(jìn)后的壓扁控制流算法。

2.1 構(gòu)造不透明謂詞

記模素數(shù)p的Legendre符號為(d/p)。

同余方程[13]如下：

1)同余方程1：

x2=-1(modp)

(1)

當(dāng)-1/p=1，即p=4k+1(k∈Z)時有解，設(shè)最小整數(shù)解為x1。

2)同余方程2：

x2=2(modp)

(2)

當(dāng)2/p=1，即p=8k+1或p=8k+7(k∈Z)時有解，設(shè)最小整數(shù)解為x2。

3)同余方程3：

x2=-2(modp)

(3)

當(dāng)-2/p=1，即p=8k+1或p=8k+3(k∈Z)時有解，設(shè)最小整數(shù)解為x3。

4)同余方程4：

x2=3(modp)

(4)

當(dāng)3/p=1，即p=12k+1或p=12k+11(k∈Z)時有解，設(shè)最小整數(shù)解為x4。

5)同余方程5：

x2=-3(modp)

(5)

當(dāng)-3/p=1，即p=6k+1(k∈Z)時有解，設(shè)最小整數(shù)解為x5。

本文構(gòu)造不透明謂詞的過程如下：

1)設(shè)Nj∈Z+(j=1,2,…,n)，隨機(jī)生成Nj個整數(shù)(k1,k2,…,kNj)為謂詞Pj的密鑰，對于每個整數(shù)ki，根據(jù)式(1)～(5)中判定是否有解的等式(如p=4k+1)，將ki代入其中，至少有一個解p是素數(shù)。

3)對于每個Nj產(chǎn)生的五元組解，將每一組解中互相對應(yīng)每一位進(jìn)行異或操作，最后得到一個五元組解記為(r1,r2,…,r5)。

4)根據(jù)其中1的個數(shù)來判斷不透明謂詞的輸出，當(dāng)1的個數(shù)為奇數(shù)時不透明謂詞輸出為True，當(dāng)1的個數(shù)為偶數(shù)時不透明謂詞輸出為False。

表1～2給出了本文提出的算法與陳代梅等[11]提出的算法在產(chǎn)生結(jié)果為True的不透明謂詞的個數(shù)和產(chǎn)生不透明謂詞的時間上的實(shí)驗(yàn)結(jié)果對比。

表1 結(jié)果為True的不透明謂詞的個數(shù)對比

根據(jù)表1中的數(shù)據(jù)，本文提出的算法產(chǎn)生的不透明謂詞結(jié)果為True或False的個數(shù)基本相同，產(chǎn)生10～10 000個不透明謂詞時，結(jié)果為True的混沌不透明謂詞分別占40%、47%、43.8%、45.1%，生成不透明謂詞的個數(shù)越多，其百分比越接近50%，結(jié)果為True或False的混沌不透明謂詞的個數(shù)越接近。本文提出的算法在生成不透明謂詞的均衡性方面優(yōu)于陳代梅等[11]提出的算法。

表2 產(chǎn)生不透明謂詞的時間對比 ms

由表2的數(shù)據(jù)可知，在產(chǎn)生10個～10 000個不透明謂詞時，使用本文提出的算法所消耗的時間相對于陳代梅等[11]提出的算法所消耗的時間分別降低了63.38%、68.79%、65.96%、64.06%，其開銷小于使用陳代梅等[11]的算法產(chǎn)生的開銷。

2.2 基于分段Logistic映射的N態(tài)不透明謂詞構(gòu)造算法

分段Logistic混沌映射[12]具有非線性性質(zhì)，采用此映射生成混沌序列時不需要進(jìn)行擾動運(yùn)算，能夠保證生成的算法具有更好的效率和安全性。定義如下：

(6)

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

以下所述N態(tài)不透明謂詞構(gòu)造算法就是定義3中的實(shí)現(xiàn)機(jī)制E，而密鑰(a0,u,fun)就是其中的謂詞。本文構(gòu)造N態(tài)不透明謂詞的算法描述如下：

步驟1 根據(jù)式(6)對參數(shù)的要求，使用隨機(jī)生成的二元組密鑰(a0,u)進(jìn)入混沌系統(tǒng)產(chǎn)生隨機(jī)實(shí)數(shù)序列A={a1,a2,…,aN}。

步驟2 通過映射函數(shù)fun將實(shí)數(shù)序列A={a1,a2,…,aN}映射成整數(shù)序列F={F1,F2,…,FN}，此時添加映射函數(shù)后，密鑰變成三元組：(a0,u,fun)。

步驟3 統(tǒng)計F中出現(xiàn)的不重復(fù)元素的個數(shù)t(t∈[1,N])，并將其對應(yīng)的密鑰存放在數(shù)組R中。

步驟4 不斷重復(fù)步驟1～步驟3，訓(xùn)練出與不同t值對應(yīng)的N個密鑰。存放密鑰的數(shù)組R={result1,result2,…,resultN}，其中resulti為步驟3中不重復(fù)元素個數(shù)t等于i時所對應(yīng)的密鑰(a0i,ui,fun)，以此類推。

假設(shè)Fi的取值范圍為[0,m]，步驟2中使用的映射函數(shù)fun為：

Fi=Round{ai×m}

(7)

其中Round是取整函數(shù)。

2.3 改進(jìn)的壓扁控制流算法

在吳偉民等[10]提出的控制流壓扁算法中，對控制變量的賦值為暴露在外的常量值，如算法1所示。針對這種情況，本文使用基于分段Logistic混沌映射產(chǎn)生的N態(tài)不透明謂詞替換這些常量值，并將2.1節(jié)中生成不透明謂詞的算法應(yīng)用到程序中的基本塊上。改進(jìn)后的算法如算法2所示。

算法1 文獻(xiàn)[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中，函數(shù)ChaoOpp是吳偉民等[10]提出的N態(tài)不透明謂詞的生成方法，ValuesOne和ValuesTwo是其生成不透明謂詞所需的密鑰，blockA、blockB、blockC是程序中的基本塊，在第1)、6)、10)行中，對next變量賦予的常量值直接暴露在外。

算法2 本文提出的改進(jìn)的控制流壓扁算法。

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中，函數(shù)logistic是本文基于分段Logistic映射產(chǎn)生N態(tài)不透明謂詞的方法，參數(shù)R1～R3是使用2.2節(jié)中提出的算法生成的密鑰，函數(shù)cPredic是2.1節(jié)中提出的生成不透明謂詞的算法，其參數(shù)PTrue和PFalse分別是與其對應(yīng)的生成永真和永假謂詞的密鑰，blockBug為插入的垃圾代碼的基本塊。使用這種算法讓程序的控制流程更加難以被分析，安全性更高。

3 實(shí)驗(yàn)結(jié)果與分析

本文提出的算法均使用Python語言實(shí)現(xiàn)，并針對幾個開源的Python程序進(jìn)行性能測試。

3.1 正確性

對源碼進(jìn)行控制流混淆，首先必須保證其正確性，即混淆后的源碼在功能上與混淆前的源碼一致，并且擁有相同的輸出結(jié)果。為了對本文提出的混淆算法進(jìn)行測試，選了3個開源的Python工具進(jìn)行測試，結(jié)果如表3所示。

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

從表3中可以看出，混淆前后的輸出結(jié)果相同。理論上分析，使用N態(tài)不透明謂詞隱藏程序的控制流，并沒有真正改變其基本塊的執(zhí)行順序，因此并不會影響程序的功能和輸出結(jié)果。

3.2 安全性

本文使用同余方程生成的不透明謂詞以及生成的N態(tài)不透明謂詞，其結(jié)果只有在執(zhí)行的過程中才能確定，即本文生成的不透明謂詞是陷門不透明謂詞，靜態(tài)分析并不能確定其輸出結(jié)果，因此本文提出的生成不透明謂詞的算法可以有效地抵抗靜態(tài)攻擊。

由于動態(tài)攻擊的難點(diǎn)是確定不透明謂詞的輸出[11]。本文對于基本塊中使用的謂詞是通過密鑰和同余方程的解產(chǎn)生，而N態(tài)不透明謂詞的生成也是根據(jù)三元組或四元組密鑰產(chǎn)生，且密鑰是隨機(jī)生成的，同余方程解的狀態(tài)也是隨機(jī)的，因此可以有效地抵抗動態(tài)攻擊。

為了對本文提出的混淆算法進(jìn)行測試，選了3個開源的Python程序進(jìn)行防篡改攻擊測試，具體統(tǒng)計結(jié)果如表4所示。

由表4中的數(shù)據(jù)可知， 相比使用文獻(xiàn)[10]算法，使用本文算法Pycrypto-master混淆后產(chǎn)生的攻擊時間增加了28.57%，Docutils增加了29.26%，Jieba-master增加了22.85%?；煜蟠a的攻擊時間相比于混淆前大大增加，并且使用本文算法比使用文獻(xiàn)[10]算法產(chǎn)生的攻擊時間平均高了22%以上，使代碼變得更加難被篡改。

表4 代碼的防篡改攻擊能力對比 h

3.3 開銷

開銷主要表現(xiàn)在時間和空間上。時間方面的開銷主要是判斷不透明謂詞的輸出，空間方面的開銷主要是插入更改控制流的代碼。下面分別對表3中的開源測試案例進(jìn)行混淆，并對比其混淆前后在時間和空間方面的開銷。

3.3.1 時間開銷

通過對表3中的開源測試用例進(jìn)行混淆，混淆前后的時間開銷如圖4所示。從圖4中可以看出，混淆后程序的執(zhí)行時間比混淆前要長。其中：Docutils混淆后較混淆前運(yùn)行時間增加了8.08%；Pycrypto-master增加了4.04%；Jieba-master增加了3.09%。但隨著程序的不斷增大，增加的時間開銷會不斷變小，卻給程序的破解增加了非常大的難度，因此，這種算法是可取的。

圖4 混淆前后測試用例的時間對比

3.3.2 空間開銷

在空間開銷方面，從圖5中可以看出，混淆后的程序比混淆前的程序占用的空間增加了。其中：Pycrypto-master混淆后較混淆前運(yùn)行空間增加了10.33%；Docutils增加了9.30%；Jieba-master增加了0.13%。但隨著程序的不斷增大，空間開銷會越來越小，不會對程序造成很大的負(fù)擔(dān)。

3.4 圈復(fù)雜度

現(xiàn)階段并沒有對混淆后程序的復(fù)雜度進(jìn)行評價的統(tǒng)一標(biāo)準(zhǔn)。圈復(fù)雜度是衡量一個衡量程序復(fù)雜度的度量指標(biāo)[14]。Radon[15]可以統(tǒng)計Python代碼的總?cè)?fù)雜度。通過多次實(shí)驗(yàn)，具體統(tǒng)計結(jié)果如表5所示。

圖5 混淆前后測試用例的空間對比

程序混淆前文獻(xiàn)[10]算法混淆后Pycrypto?master208328173935Docutils569771459616Jieba?master196248337

由表5中的數(shù)據(jù)可知：Pycrypto-master混淆后較混淆前的總?cè)?fù)雜度增加了88.91%；Docutils增加了68.79%；Jieba-master增加了71.94%。與使用文獻(xiàn)[10]算法相比，Pycrypto-master混淆后產(chǎn)生的總?cè)?fù)雜度增加了39.69%；Docutils增加了34.58%；Jieba-master增加了35.89%?；煜蟠a的總?cè)?fù)雜度相比混淆前大大增加，并且比使用文獻(xiàn)[10]算法產(chǎn)生的總?cè)?fù)雜度平均提高了34%以上，代碼變得更加復(fù)雜。因此，混淆后的代碼更難被破解。

4 結(jié)語

本文提出了一種簡單的基于密鑰和同余方程解的狀態(tài)的不透明謂詞生成算法，可大量應(yīng)用于基本塊中。針對當(dāng)前壓扁控制流算法存在的弊端，提出了一種新的N態(tài)不透明謂詞生成算法，并對原有的壓扁控制流算法進(jìn)行改進(jìn)。最后在正確性、安全性、開銷、圈復(fù)雜度等方面對本文提出的算法進(jìn)行了評估。實(shí)驗(yàn)結(jié)果和分析表明本文提出的算法在正確性和安全性方面表現(xiàn)得很好，具備非常高的圈復(fù)雜度，能夠有效地抵抗靜態(tài)攻擊和動態(tài)攻擊。然而，提高代碼的混淆度的同時，也增加了時間和空間開銷。因此，對于如何在兩者之間取得平衡，還需要進(jìn)一步的研究。

)

[1] 蘇慶,吳偉民,李忠良，等.混沌不透明謂詞在代碼混淆中的研究與應(yīng)用[J].計算機(jī)科學(xué),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] 袁征,馮雁,溫巧燕,等.構(gòu)造一種新的混淆Java程序的不透明謂詞[J].北京郵電大學(xué)學(xué)報,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].計算機(jī)科學(xué),2015,42(5):178-182.(WUWM,LINSM,LINZY.Chaotic-basedopaquepredicatecontrolflowflattenalgorithm[J].ComputerScience, 2015, 42(5): 178-182.)

[11] 陳代梅,范希輝,朱靜,等.基于同余方程和中國剩余定理的混淆算法[J].計算機(jī)應(yīng)用研究,2015,32(2):485-488.(CHENDM,FANXH,ZHUJ,etal.ObfuscationalgorithmsbasedoncongruenceequationandChineseremaindertheorem[J].ApplicationResearchofComputers, 2015, 32(2): 485-488.)

[12] 王興元,朱偉勇.二維Logistic映射中混沌與分形的研究[J].中國圖象圖形學(xué)報,1999,4(4):340-344.(WANGXY,ZHUWY.ResearchesonchaosandfractalofthecoupledLogisticmap[J].JournalofImageandGraphics,1999, 4(4): 340-344.)

[13] 潘承洞,潘承彪.簡明數(shù)論[M].北京:北京大學(xué)出版社,1998:150-162.(PANCD,PANCB.SimplifiedNumberTheory[M].Beijing:PekingUniversityPress, 1998: 150-162.)

[14] 趙玉潔,湯戰(zhàn)勇,王妮,等.代碼混淆算法有效性評估[J].軟件學(xué)報,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。

安徽省自然科學(xué)基金資助項(xiàng)目(1408085MKL06)；高等學(xué)校學(xué)科創(chuàng)新引智計劃項(xiàng)目(B07033)。

王巖(1991—)，男，山東濟(jì)南人，碩士研究生，CCF會員，主要研究方向：軟件技術(shù)、程序優(yōu)化； 黃章進(jìn)(1980—)，男，湖北天門人，副教授，博士，CCF會員，主要研究方向：計算機(jī)圖形學(xué)、圖形處理器計算； 顧乃杰(1961—)，男，江蘇南通人，教授，碩士，CCF會員，主要研究方向：并行算法、并行處理、并行體系機(jī)構(gòu)。

1001- 9081(2017)06- 1803- 05

10.11772/j.issn.1001- 9081.2017.06.1803

TP311.56

A