2. 机电工程学院,广东 广州 510006
2. College of Electromechanical Engineering, Guangdong University of Technology, Guangzhou 510006, China
计算机安全很大程度上是软件安全问题。当前软件安全面临三大威胁:逆向分析、盗版和篡改,使软件处于危险的“白盒攻击环境[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]
1)对
a)
b)
则t在标识M有发生权(仍记为M[t>)。
2)若M[t>,则变迁t在M可以发生。t在M发生产生新的标识
用图形表示带抑止弧的Petri网时,一条抑止弧相当于把一条有向边的箭头换成一个小圆圈。对于任意一个库所s和任意一个变迁t,s到t的有向边和s到t的抑止弧不能同时存在。
2 软件保护技术依赖关系及其建模综合前人成果,本文给出基于Petri网角度描述的软件保护技术依赖关系定义及模型。
2.1 必须依赖关系若保护技术A必须依赖于保护技术B,则必须同时应用A和B两种保护技术,否则会使得应用保护技术A后的程序过于脆弱或存在明显漏洞,很容易被攻击者攻击成功。
2.1.1 前向必须依赖关系若保护技术A前向必须依赖于保护技术B,则B必须在A之前应用,记为
|
图 1 前向必须依赖关系Petri网 Fig. 1 Pre-requirements Petri nets |
若保护技术A后向必须依赖于保护技术B,则在应用A之后必须应用B,记为
|
图 2 后向必须依赖关系Petri网 Fig. 2 Post-requirements Petri nets |
若保护技术A禁止依赖于保护技术B,则A和B不能同时应用,否则会使得保护技术A的应用无效或者保护强度大大降低。
2.2.1 前向禁止依赖关系若保护技术A前向禁止依赖于保护技术B,则在应用A之前禁止应用B,记为
|
图 3 前向禁止依赖关系Petri网 Fig. 3 Pre-prohibitions Petri nets |
若保护技术A后向禁止依赖于保护技术B,则在应用A之后禁止应用B,记为
|
图 4 后向禁止依赖关系Petri网 Fig. 4 Post-prohibitions Petri nets |
当3种或3种以上的保护技术互相之间有依赖关系时,需要将上述子网组合应用。上述4种基本依赖关系子网中,每一次某个代表应用保护技术的变迁发生后,总会从代表初始状态的库所中消耗一个标志,然后在变迁发生后返还。因此这种结构具有良好的可扩展性,当需要组合多种依赖关系的子网时,只需要将各自的代表初始状态的库所共用。
例如,假设软件保护技术A、B、C的依赖关系为:
|
图 5 复合依赖关系Petri网 Fig. 5 Complex dependency Petri nets |
对于应用最多的复合依赖关系应用场景,其求解过程如下。
Step1 对要使用的保护技术编号,并列出每种保护技术之间的依赖关系。
Step2 对每一个依赖关系建立独立Petri网模型。
Step3 将Step2得到的每个独立依赖关系Petri网模型进行组合,组合方法如下:
1) 选定一个独立依赖关系Petri网作为基本初始子网;
2) 依次将其他独立依赖关系Petri网以共用始状态的库所为基础进行组合,直到所有独立依赖关系Petri网全部组合完毕;
3) 重新对库所进行编号,得到完整的Petri网模型Σ1。
Step4 求出Σ1的可达标识图Σ2,其基本思路如下[14]:
1) 令可达标识集为
2) 令
3) 当
Step5 根据具体需求在Σ2中找到满足需求的标识M。
Step6 从Σ2的初始标识M0到M直接的一条路径上经过的所有变迁按序形成一个变迁序列S0,S0中的每个变迁对应于一种软件保护技术,即S0就是所求的软件保护技术应用序列。
3.1 应用举例假定现在需要应用7种软件保护技术(A,B,C,D,E,F,G),对应的应用次数向量为(2,3,2,2,4,3,2),其相互依赖关系如下:
a)
b)
c)
d)
e) G跟其他保护技术无依赖关系。
对应的Petri网如图6所示,其中s0表示程序初始状态,t1至t7依次表示应用保护技术A至G,s1表示A应用的最大次数,s2、t8和s3组成的子网控制B应用的最大次数,s4至s8依次表示C至G应用的最大次数。
|
图 6 软件保护技术依赖关系模型1 Fig. 6 Software protection technology dependency model 1 |
从图6中可以看出,由于次数控制库所(s1至s8)的存在,
|
图 7 部分可达标识图 Fig. 7 Partiallyreachable marking map of model 1 |
基于实际应用目的,提出3种序列求解方案。
3.2.1 令软件保护技术被应用的总次数最多应用保护技术次数最多,即变迁t1至t7发生次数最多。由于每一次表示应用保护技术的变迁发生后,都会使得对应变迁的后继库所增加一个标志(如t1发生会使得s9增加一个标志)。因此在可达图7中找出
应用保护技术种类最多即变迁t1至t7中发生的变迁种类数最多。同样由于每一次应用保护技术的变迁发生,使得对应后继库所增加一个标志。因此在可达图7中找出标识M″,使如下函数f(M″)值最大。
任何一条由初始标识M0到达M″的变迁发生序列为所求序列。图7中使得f(M)最大的标识为
指定保护技术应用次数最多,即变迁t1至t7中某一个发生次数最多,只需在可达图7中找出标识M′″,使得
为了说明正确的保护算法应用顺序对最终结果的影响,本文使用一个运用网络单纯性算法求解网络最小费用流的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,随机插入垃圾代码。
依赖关系描述如下。
假设使用次数为(1,2,1,1,1,2,2),若忽略以上依赖关系,可随机生成一个应用上述软件保护技术的序列,如
另外,求出上述依赖关系的Petri网和可达标识图,分别如图8和图9所示。在图9所示的可达标识图中,找到令
分别对实验用例程序测试以上两种序列,得到的三次水印信息提取情况见表1,最终程序复杂度情况见表2,L1和L2得到的最终程序控制流图分别如图10(a)和10(b)所示。
|
图 8 软件保护技术依赖关系模型2 Fig. 8 Software protection technology dependency model 2 |
|
图 9 模型2的可达标识图 Fig. 9 Reachable marking map of Model 2 |
分析序列L1和L2,可以发现L1中D只出现在C之后,没有满足依赖关系
| 表 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]。L1和L2都往程序中插入水印、不透明分支和垃圾代码,都会增加程序的Halstead复杂度,但L1违背依赖关系
本文提出一种使用带抑止弧的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. |
2017, Vol. 20