工业工程  2017, Vol. 20Issue (6): 77-83.  DOI: 10.3969/j.issn.1007-7375.e17-4137.
0

引用本文 

苏庆, 何凡, 伍乃骐. 基于带抑止弧的Petri网的软件保护技术应用序列构建方法[J]. 工业工程, 2017, 20(6): 77-83. DOI: 10.3969/j.issn.1007-7375.e17-4137.
SU Qing, HE Fan, WU Naiqi. A Method of Constructing Sequence of Software Protection Technologies Based on Petri Net with Inhibitor Arcs[J]. Industrial Engineering Journal, 2017, 20(6): 77-83. DOI: 10.3969/j.issn.1007-7375.e17-4137.

基金项目:

广东省科技计划资助项目(2017A040405050);广州市科技计划资助项目(201604016041)

作者简介:

苏庆(1979–),男,广东省人,副教授,博士研究生,主要研究方向为软件安全与保护。

文章历史

收稿日期:2017-05-29
基于带抑止弧的Petri网的软件保护技术应用序列构建方法
苏庆1, 何凡1, 伍乃骐2     
广东工业大学 1.计算机学院;
2. 机电工程学院,广东 广州 510006
摘要: 基于软件保护领域中多种软件保护技术之间存在不同依赖关系的情况,针对求解有效的软件保护技术应用序列问题,提出了一种基于带抑止弧的Petri网建模分析的求解方法。首先分类并建立4种基本的软件保护技术依赖关系的Petri网模型,包括前向/后向必须依赖关系和前向/后向禁止依赖关系;根据实际应用场景建立相应的复合依赖关系Petri网模型,并绘制其可达标识图;在可达标识图中定位满足需求的标识,求解得从初始标识到此标识的一条变迁序列所对应的软件保护技术应用序列即为所求序列。最后,通过实验证明了此方法的有效性。
关键词: 软件保护技术    带抑止弧的Petri网    代码混淆技术    软件水印技术    
A Method of Constructing Sequence of Software Protection Technologies Based on Petri Net with Inhibitor Arcs
SU Qing1, HE Fan1, WU Naiqi2     
1. College of Computer Science, Guangdong University of Technology, Guangzhou 510006, China;
2. College of Electromechanical Engineering, Guangdong University of Technology, Guangzhou 510006, China
Abstract: A method is proposed to find a suitable sequence of software protection technologies with various dependency relationships existing among each other in software protection domain by Petri net with inhibitor arcs. Firstly, all dependency relationships are divided into four categories-pre/post-requirements and pre/post-prohibitions and Petri net model constructed for each relationship. Secondly, a composite model is built according to the specific software protection techniques to be used and the reachable marking map drawn. Thirdly, the required marking in reachable marking map is found and the sequence of transitions, which makes Petri net change from initial marking to the required marking, is the suitable sequence of software protection technologies. At last, the effectiveness of this method is demonstrated by experiments.
Key words: software protection technology    petri net with inhibitor arcs    code obfuscation technology    software watermarking technology    

计算机安全很大程度上是软件安全问题。当前软件安全面临三大威胁:逆向分析、盗版和篡改,使软件处于危险的“白盒攻击环境[1]”中。为了对抗这些威胁,当前软件保护手段主要有:代码混淆、软件水印和防篡改技术。代码混淆技术主要用于防御对程序的逆向分析,本质上是对代码进行保留语义的等价变换,但转换后的程序更难被理解。软件水印技术是指将某些标识信息(即水印)通过某种方式嵌入在软件中,并在必要的时候进行提取,并据此作软件版权归属证明和完整性验证等。软件防篡改技术是指通过基于硬件和软件的措施阻止被非法修改后的程序正常运行。由于单一的代码混淆技术已经被证明不能提供绝对的安全性[2],而软件水印和防篡改技术都只能作为软件被攻破后降低损失的一种手段,因此主流的软件保护系统一般都会同时使用以上三大类技术。然而,当这些技术之间具有依赖关系时,则需要确定它们之间合适的应用顺序,方能同时保证代码保护效果以及与原程序的等价性,否则可能起到保护效果被抵消甚至被保护软件受到破坏的反作用。

针对在同一段代码上应用多种软件保护技术的问题,Collberg等人[3]第一次提出将软件保护技术序列相对独立地放在软件保护系统的最外层循环中,但是并没有对软件保护技术依赖关系做详细的研究;Worblewski[4]在对x86机器码的保护中使用了硬编码的软件保护技术序列;Lacey等[5]研究了两种代码变换技术不能同时作用于同一段代码的情况,并提出一种根据被作用代码的特点选择应用技术的算法。但当要使用的软件保护技术数量较多,并且有着复杂的相互依赖关系时,这些方法均不适用。针对复杂依赖关系的情况,Heffner等[6]总结了软件保护技术之间的3类共6种依赖关系,并使用有穷自动机对这些关系建模,被自动机接受的句子即是可行的软件保护方法使用序列[7]。在实际应用中,要求用户了解各种软件保护技术之间的依赖关系,并手工对各种技术进行排序。这样就会增加用户的使用负担。因此,应当研究自动化的软件保护技术应用序列求解方法。

软件保护技术应用序列的求解本质上是一个针对实际应用需求的软件保护技术组合问题。而Petri网作为一种建立在严格数学基础上的工具,适用于解决软件保护技术的应用序列问题的求解。本文提出一种运用带抑止弧的Petri网对软件保护技术之间的依赖关系进行建模求解的方法,根据不同的应用场合,求解满足其特点需求的保护技术应用序列。

1 带抑止弧的Petri网

带抑止弧的Petri网(Petri net with inhibitor arcs)是在原型Petri网的基础上增加一种连接库所和变迁的弧形成的。这种弧称为抑止弧,只对在原型Petri网意义下具备发生条件的变迁是否允许发生起控制作用。变迁一旦发生,抑止弧对由此引起的标识变化不再产生影响。

定义 1  带抑止弧的Petri网是一个五元组[8]

Σ = ( S , T ; F , I , M ) 其中,S,T;F)是一个基本网系统,S代表库所集,T代表变迁集, F = ( S × T ) ( T × S ) 表示弧集,M是网的一个标识, I S × T 称为抑止弧集, I F = (即 s S t T : ( s , t ) F ( s , t ) I )。

1)对 t T ,如果

a) s S : ( s , t ) F M ( s ) 1

b) s S : ( s , t ) I M ( s ) = 0

t在标识M有发生权(仍记为M[t>)。

2)若M[t>,则变迁tM可以发生。tM发生产生新的标识 M

M ( s ) = { M ( s ) 1 , ( s , t ) F ( t , s ) F ; M ( s ) + 1 , ( t , s ) F ( s , t ) F ; M ( s ) ,

用图形表示带抑止弧的Petri网时,一条抑止弧相当于把一条有向边的箭头换成一个小圆圈。对于任意一个库所s和任意一个变迁tst的有向边和st的抑止弧不能同时存在。

2 软件保护技术依赖关系及其建模

综合前人成果,本文给出基于Petri网角度描述的软件保护技术依赖关系定义及模型。

2.1 必须依赖关系

若保护技术A必须依赖于保护技术B,则必须同时应用A和B两种保护技术,否则会使得应用保护技术A后的程序过于脆弱或存在明显漏洞,很容易被攻击者攻击成功。

2.1.1 前向必须依赖关系

若保护技术A前向必须依赖于保护技术B,则B必须在A之前应用,记为 A r B 。例如在插入假分支之前必须先使用不透明谓词生成技术生成不透明谓词,依靠不透明谓词来增强假分支的混淆强度[9]。对应的Petri网模型如图1所示,初始网标识 M 0 = [ 1 , 0 , 0 , n , m ] ,其中s1表示程序初始状态,t1表示应用保护技术A,t2表示应用保护技术B,s4控制应用保护A最多n次,s5控制应用B最多m次。t1的发生需要s2中具有标志,而s2中的标志由t2产生,t1发生后会退回给s2一个标志;此后t1的发生便不依赖于t2,即第一次应用保护技术A之前,必须先应用保护技术B。

图 1 前向必须依赖关系Petri网 Fig. 1 Pre-requirements Petri nets
2.1.2 后向必须依赖关系

若保护技术A后向必须依赖于保护技术B,则在应用A之后必须应用B,记为 A r B 。例如应用序列号保护技术后,必须应用加密技术防止动态调试攻击获取内存中的序列号。对应的Petri网模型如图2所示,初始网标识 M 0 = [ 1 , 0 , 0 , n , m 1 , 1 ] ,其中s1表示程序初始状态,t1表示应用保护技术A,t2表示应用保护技术B,s4控制应用A最多n次,s5控制应用B最多m–1次。当s4中还存在标志时,抑止弧(s4t3)发生作用禁止了t3的发生;只有当A应用完n次之后,即t1发生n次之后,s4中不再含有标志,t3才可以发生,使得s5中产生一个标志,最终使得B应用m次。

图 2 后向必须依赖关系Petri网 Fig. 2 Post-requirements Petri nets
2.2 禁止依赖关系

若保护技术A禁止依赖于保护技术B,则A和B不能同时应用,否则会使得保护技术A的应用无效或者保护强度大大降低。

2.2.1 前向禁止依赖关系

若保护技术A前向禁止依赖于保护技术B,则在应用A之前禁止应用B,记为 A p B 。例如很多代码混淆技术都需要运用一种别名分析技术[10]以定位程序中可以被合并的部分,因此在此之前禁止应用会导致别名分析困难的技术,比如不透明谓词[11]。对应的Petri网模型如图3所示,初始网标识 M 0 = [ 1 , 0 , 0 , n , m ] ,其中s1表示程序初始状态,t1表示应用保护技术A,t2表示应用保护技术B,s4控制应用A最多n次,s5控制应用B最多次。当s4中有标志时,抑止弧(s4,,t2)使得t2不能发生,即只有当A应用n次之后,B才能应用,从而保证了B不会出现在A之前被应用。

图 3 前向禁止依赖关系Petri网 Fig. 3 Pre-prohibitions Petri nets
2.2.2 后向禁止依赖关系

若保护技术A后向禁止依赖于保护技术B,则在应用A之后禁止应用B,记为 A p B 。例如在使用了程序执行路径水印技术[12]后,应禁止使用执行路径多样性混淆技术[13]。对应的Petri网模型如图4所示,初始网标识 M 0 = [ 1 , 0 , 0 , n , m ] ,其中s1表示程序初始状态,t1表示应用A,t2表示应用B,s4控制应用A最多n次,s5控制应用B最多m次。一旦t1发生将导致s2中含有标识,则抑止弧(s2,,t2)会使得t2不能发生,即应用A之后禁止应用B。

图 4 后向禁止依赖关系Petri网 Fig. 4 Post-prohibitions Petri nets
2.3 复合依赖关系

当3种或3种以上的保护技术互相之间有依赖关系时,需要将上述子网组合应用。上述4种基本依赖关系子网中,每一次某个代表应用保护技术的变迁发生后,总会从代表初始状态的库所中消耗一个标志,然后在变迁发生后返还。因此这种结构具有良好的可扩展性,当需要组合多种依赖关系的子网时,只需要将各自的代表初始状态的库所共用。

例如,假设软件保护技术A、B、C的依赖关系为: A r B , B p C ,则对应的Petri网如图5所示,初始网标识 M 0 = [ 1 , 0 , 0 , n , m , 0 , k ] ,其中s1表示程序初始状态,t1表示应用A,t2表示应用B,t3表示应用C,s4控制应用A最多n次,s5控制应用B最多m次,s7表示应用C最多k次。

图 5 复合依赖关系Petri网 Fig. 5 Complex dependency Petri nets
3 问题求解及分析过程

对于应用最多的复合依赖关系应用场景,其求解过程如下。

Step1 对要使用的保护技术编号,并列出每种保护技术之间的依赖关系。

Step2 对每一个依赖关系建立独立Petri网模型。

Step3 将Step2得到的每个独立依赖关系Petri网模型进行组合,组合方法如下:

1) 选定一个独立依赖关系Petri网作为基本初始子网;

2) 依次将其他独立依赖关系Petri网以共用始状态的库所为基础进行组合,直到所有独立依赖关系Petri网全部组合完毕;

3) 重新对库所进行编号,得到完整的Petri网模型Σ1

Step4 求出Σ1的可达标识图Σ2,其基本思路如下[14]

1) 令可达标识集为 CR ( M 0 ) 。对每个变迁构造输入向量和输出向量;

2) 令 CR ( M 0 ) = { M 0 } ,并标记M0标识为“new”;

3) 当 CR ( M 0 ) 中含有带“new”的标识时,不断选择“new”标识并触发激活状态的变迁,若得到新标识则继续标记为“new”并加入 CR ( M 0 ) ,并在可达标识图上增加一条由被选择的“new”标识到达新标识的有向弧,弧上标记发生的变迁,然后将被选择的“new”标识标记为“old”。

Step5 根据具体需求在Σ2中找到满足需求的标识M

Step6 从Σ2的初始标识M0M直接的一条路径上经过的所有变迁按序形成一个变迁序列S0S0中的每个变迁对应于一种软件保护技术,即S0就是所求的软件保护技术应用序列。

3.1 应用举例

假定现在需要应用7种软件保护技术(A,B,C,D,E,F,G),对应的应用次数向量为(2,3,2,2,4,3,2),其相互依赖关系如下:

a) A r B

b) B p C

c) D r A

d) E p F

e) G跟其他保护技术无依赖关系。

对应的Petri网如图6所示,其中s0表示程序初始状态,t1t7依次表示应用保护技术A至G,s1表示A应用的最大次数,s2t8s3组成的子网控制B应用的最大次数,s4s8依次表示C至G应用的最大次数。

图 6 软件保护技术依赖关系模型1 Fig. 6 Software protection technology dependency model 1
3.2 分析求解

图6中可以看出,由于次数控制库所(s1s8)的存在, M R ( M 0 ) : M ( s i ) 4 ; 0 i 15 ,因此Σ7是一个有界网,所以可以画出图6的可达图[8],部分可达标示图如图7所示。再根据可达标示图和不同的需求求出合适的保护技术应用序列。

图 7 部分可达标识图 Fig. 7 Partiallyreachable marking map of model 1

基于实际应用目的,提出3种序列求解方案。

3.2.1 令软件保护技术被应用的总次数最多

应用保护技术次数最多,即变迁t1t7发生次数最多。由于每一次表示应用保护技术的变迁发生后,都会使得对应变迁的后继库所增加一个标志(如t1发生会使得s9增加一个标志)。因此在可达图7中找出 P = M ( i ) , 9 i 15 最大的标识 M ,任何一条由初始标识M0到标识 M 的变迁发生序列为所求序列,图7中令P最大的标识为 M 19 = [ 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 2 , 3 , 2 , 2 , 4 , 3 , 2 ] ,对应的一条变迁发生序列为(t6t6t7t7t1t2t1t6t5t4t8t2t5t4t5t5t2t3t3)即保护技术应用序列为(FFGGABAFEDBEDEEBCC)。

3.2.2 令被应用的软件保护技术的种类最多

应用保护技术种类最多即变迁t1t7中发生的变迁种类数最多。同样由于每一次应用保护技术的变迁发生,使得对应后继库所增加一个标志。因此在可达图7中找出标识M″,使如下函数f(M″)值最大。

f ( M ) = 15 9 g ( M ( i ) ) ; g ( x ) = { 0 , x = 0 1 , x 0

任何一条由初始标识M0到达M″的变迁发生序列为所求序列。图7中使得f(M)最大的标识为 M 18 = [ 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 2 , 3 , 1 , 2 , 4 , 3 , 2 ] ,对应的一条变迁发生序列为(t7t7t6t6t6t5t5t5t5t2t2t1t4t4t1t8t2t3),即保护技术应用序列为(GGFFFEEEEBBADDABC)。

3.2.3 令指定软件保护技术被应用的次数最多

指定保护技术应用次数最多,即变迁t1t7中某一个发生次数最多,只需在可达图7中找出标识M′″,使得 M R ( M 0 ) : M ( s i ) M ( s i ) ,其中i是指定保护技术对应的变迁的后继库所下标。例如图7中使得t5发生次数最多的标识为 M 119 = [ 1 , 0 , 2 , 1 , 2 , 1 , 0 , 0 , 0 , 2 , 0 , 0 , 1 , 4 , 3 , 2 ] ,对应的一条变迁发生序列为(t7t7t6t6t6t5t5t5t5t1t1t4),即保护技术应用序列为(GGFFFEEEEAD)。

4 实验

为了说明正确的保护算法应用顺序对最终结果的影响,本文使用一个运用网络单纯性算法求解网络最小费用流的Java程序作为测试用例,并对比Sandmark[15]平台上的7种保护技术在使用不同序列时,最终输出程序的正确性以及各项复杂度指标。这7种保护技术描述及依赖关系描述如下。

A:Merge local integers,将两个32位整数合并成一个64位的整数;

B:Add initialization,将水印信息嵌入到一个类的构造方法中,并用一个整形变量保存;

C:Opaque branch insertion,在一个方法中随机地插入不透明分支;

D:Branch inverter,在指令中寻找if声明,并更改指令使执行流程中if部分和else部分交换;

E:Collberg-Thomborson Watermarking,将水印编码为图并嵌入到程序中,图结构在运行时动态生成;

F:Overload names,修改程序的函数名;

G:Random dead code,随机插入垃圾代码。

依赖关系描述如下。

A p B C r D E r F ,G与其他算法无依赖关系。

假设使用次数为(1,2,1,1,1,2,2),若忽略以上依赖关系,可随机生成一个应用上述软件保护技术的序列,如 L 1 = ( FBACDEBGFG )

另外,求出上述依赖关系的Petri网和可达标识图,分别如图8图9所示。在图9所示的可达标识图中,找到令 x = M ( 2 ) + M ( 3 ) + M ( 6 ) + M ( 8 ) + M ( 10 ) + M ( 11 ) 最大的标识为 M 9 = [ 1 , 1 , 2 , 0 , 0 , 2 , 0 , 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0 ] ,从初始标识M0M9的一条路径即是应用保护技术次数最多的序列为 L 2 = ( GADCBEFBGF )

分别对实验用例程序测试以上两种序列,得到的三次水印信息提取情况见表1,最终程序复杂度情况见表2L1L2得到的最终程序控制流图分别如图10(a)10(b)所示。

图 8 软件保护技术依赖关系模型2 Fig. 8 Software protection technology dependency model 2
图 9 模型2的可达标识图 Fig. 9 Reachable marking map of Model 2

分析序列L1L2,可以发现L1中D只出现在C之后,没有满足依赖关系 C r D ,A前面出现一次B,没有满足依赖关 A p B ,而L2正确地满足了所有依赖关系。从表1中可以看出,使用序列L1应用保护技术得到的程序中,嵌入的3个水印信息只剩下了两个,原因是L1中第一次使用B嵌入的水印被后面A的应用摧毁;而L2则全部保留。

表 1 水印提取结果 Tab. 1 Results of watermark extraction using sequence L1 and L2 protection technology

表2中可以看出,使用序列L1应用保护技术得到的程序各项复杂度相比原程序并没有很大的提升,而使用序列L2应用保护技术得到的程序相比原程序各项复杂度均有大幅度提升。

表 2 各项软件复杂度对比 Tab. 2 The original program and the complexity of the program after the application of sequence L1 and L2
图 10 程序控制流图 Fig. 10 Program control flow graph

Halstead程序复杂度度量方法统计程序中出现的操作符和操作数,以此来计算程序容量和工作量[16]L1L2都往程序中插入水印、不透明分支和垃圾代码,都会增加程序的Halstead复杂度,但L1违背依赖关系 C r D 导致可插入的点大大减少,最终导致L1的Halstead复杂度远小于L2。在程序中插入不透明分支会增加程序的McCabe Cyclomatic圈复杂度[16],但L1在执行C后圈复杂度没有增加,也说明忽略依赖关系 C r D 导致执行C基本无效。最后从二者的控制流图也可以看出L2的结果比L1更加复杂(在图10(a)中基本块数目为50,分支数目为6,而图10(b)中基本块数目为56,分支数目为8。其余两个复杂度的变化原因与上述相同。

5 结论

本文提出一种使用带抑止弧的Petri网对软件保护技术间存在的依赖关系建模的方法,对4种基本的软件保护技术依赖关系进行了分类和建模,并在基于实际应用场景的Petri网模型上,求解满足不同的需求的软件保护方法应用序列。在下一步,将继续进行对求解软件保护技术应用序列最大效果问题上的研究,解决在满足依赖关系的基础上,获得最大保护效果的应用序列问题。

参考文献
[1]
GU Y X. Software security patterns: white-box attack analysis andsoftware protection technology[C]. Proceedings of the 1st Inter-national ACM Summer School on Information Security and Protection Theme on Software Security and Protection. New York: ACM, 2010: 7.
[2]
BARAK B, GOLDREICH O, IMPAGLIAZZO R. On the (im)possibility of obfuscating programs[J]. Journal of the ACM, 2001, 59(2): 1-18.
[3]
COLLBERG C, THOMBORSON C, LOW D. A taxonomy of obfuscating transformations[R]. New Zealand: Department of Computer Science the University of Auckland, 1997: 148.
[4]
WROBLEWSKI G. General method of program code obfuscation[C]. International Conference on Software Engineering Research and Practice. 2002.
[5]
LACEY D, MOOR O D. Detecting disabling interference between program transformations[J]. 2001.
[6]
HEFFNER K, COLLBERG C S. The obfuscation executive[C]. Information Security, International Conference, ISC 2004, Palo Alto, CA, USA, September 27-29, 2004, Proceedings. DBLP, 2004: 428-440.
[7]
王怀军. 白盒环境中防动态攻击的软件保护方法研究[D]. 西安: 西北大学, 2014.
WANG Huaijun. Research on software protection method against dynamic attack in white box environment[D]. Xi’an: Northwestern University, 2014.
[8]
吴哲辉. Petri网导论[M]. 北京: 机械工业出版社, 2006.
[9]
苏庆, 吴伟民, 李忠良, 等. 混沌不透明谓词在代码混淆中的研究与应用[J]. 计算机科学, 2013, 40(6): 155-159.
SU Qing, WU Weimin, LI Zhongliang et. Research and application of chaos opaque predicate in code obfuscation[J]. Computer Science, 2013, 40(6): 155-159.
[10]
刘鹏, 赵荣彩, 李朋远. 一种面向向量化的动态指针别名分析框架[J]. 计算机科学, 2015, 42(3): 26-30.
LIU Peng, ZHAO Rongcai, LI Pengyuan. Dynamic pointer alias analysis framework for vectorization[J]. Computer Science, 2015, 42(3): 26-30. DOI: 10.11896/j.issn.1002-137X.2015.03.005.
[11]
杨宇波. 代码混淆模型研究[D]. 北京: 北京邮电大学, 2015.
YANG Yubo. Research on code obfuscation model[D]. Beijing: Beijing University of Posts and Telecommunications, 2015.
[12]
朱正平, 钟诚, 陈东用. 一种基于执行路径隐藏的软件水印算法[J]. 计算机应用研究, 2006, 23(12): 118-120.
ZHU Zhengping, ZHONG Cheng, CHEN Dongyong. Software watermarking algorithm based on hiding execution path of watermark-functions[J]. Application Research of Computers, 2006, 23(12): 118-120. DOI: 10.3969/j.issn.1001-3695.2006.12.038.
[13]
许广莲, 房鼎益, 王怀军, 等. 一种白盒环境中抗动态攻击的软件保护方法[J]. 小型微型计算机系统, 2015, 36(9): 2062-2066.
XU Guanglian, FANG Dingyi, WANG Huaijun. Software protection method defending dynamic attack in white-box environment[J]. Journal of Chinese Computer Systems, 2015, 36(9): 2062-2066.
[14]
ZHANG Jinquan, NI Lina, JIANG Changjun. An algorithm to construct concurrent reachability graph of petri nets[J]. Journal of Donghua University(English Edition), 2004, 21(3): 180-184.
[15]
COLBERG C. Sandmark’s home page[EB/OL]. http://sandmark.cs.arizona.edu.
[16]
王磊, 侯整风, 向润昭, 等. 基于嵌套复杂度的控制流混淆算法[J]. 计算机工程, 2016, 42(11): 177-181.
WANG Lei, HOU Zhengfeng, XIANG Runzhao. A control flow obfuscation algorithm based on nested complexity[J]. Computer Engineering, 2016, 42(11): 177-181. DOI: 10.3969/j.issn.1000-3428.2016.11.029.