（计算机科学与技术专业论文）基于net组件依赖图的软件胎记研究.pdf

硕j ：学位论文 摘要 软件具有高附加值、易复制的特点，导致软件盗版猖獗、软件厂商损失严 重。保障软件产业健康、可持续发展已成为当今世界的迫切课题。 软件胎记是近年出现的防盗版技术，它通过提取、比较软件固有特征的相似 度来辨别盗版。该技术能有效证明版权且不限制程序执行，符合软件厂商既保护 知识产权又占领市场的策略，受到厂商和学术界双方的高度重视。目前国内外学 者已提出了几种胎记算法，对软件胎记技术进行了有益的探索，但还存在不少问 题需要深入研究。 软件系统的组件依赖关系可抽象为图，不同软件的组件依赖图相似度小、 难以修改，是构成胎记的理想对象。本文针对n e t 软件，设计了一种基于组件 依赖图的软件胎记方案。通过提取、比对正版软件与可疑软件之间静态和动态 组件依赖图集合的相似程度，识别盗版。为了提高组件依赖图集合相似度匹配 效率，本文为静态、动态组件依赖图分别设计了近似匹配算法。静态组件依赖 图匹配算法基于求最大公共子图的思想，保证最大公共子图同构的同时，各组 件的名称也正确映射。动态组件依赖图先被转化成无序标签树，然后借鉴图的 宽度优先遍历方法，设计了一种线性时间复杂度的匹配算法。在组件名称必须 匹配的约束下，这两种近似图匹配算法能有效减小大规模图集的匹配计算量。 为了验证胎记技术抵御混淆攻击的可靠性与可信性，本文与t a n a m m 和w p p 进行了实验对比。结果表明，对于具有大量用户组件的软件系统，本文提出的胎 记技术效果好，适合对大型软件系统提供版权保护。 关键词：软件保护；软件胎记；组件依赖图；图匹配 i i 基于n e t 组件依赖图的软件胎记研究 a b s t r a c t i nr e c e n ty e a r s ，s o f t w a r ep i r a c yh a ss e r i o u s l yi m p a i r e dt h ed e v e l o p m e n to f s o f t w a r ei n d u s t r y , a st h es o f t w a r ei sh i g hv a l u e a d d e da n de a s yt ob ec o p i e dw i t h l o wc o s t 。t om a i n t a i nt h eh e a l t h ya n ds u s t a i n a b l ed e v e l o p m e n to ft h es o f t w a r e i n d u s t r yi sc u r r e n t l yap r e s s i n gt o p i cn e e d i n gt ob ea d d r e s s e d 。 a sa ni m p o r t a n tb r a n c ho fs o f t w a r ep r o t e c t i o n ，s o f t w a r eb i r t h m a r kc a nb eu s e d t op r o v ec o d et h e f tb yi d e n t i l y i n gt h ei n t r i n s i cp r o p e r t i e so fap r o g r a m o w i n gt o s o f t w a r eb i r t h m a r kc o u l di d e n t i f yt h ec o p y r i g h tb yi t s e l fw i t h o u ti n t e r r u p t i n gt h e p r o g r a m ，i th a sr e c e i v e dc l o s ea t t e n t i o nf r o mb o t hs o f t w a r em a n u f a c t u r e ra n d a c a d e m i cc i r c l e s a l t h o u g hs o m ec o n t r i b u t i o n sh a v eb e e nm a d eo nt h es o f t w a r e b i r t h m a r k ，t h e r ea r es t i l lm a n yq u e s t i o n sn e e d i n gt ob ei n v e s t i g a t e df u r t h e r t h ec o m p o n e n td e p e n d e n c yi nas o f t w a r es y s t e mc a nb ed e e m e da sag r a p h ， a n dt h ec o m p o n e n td e p e n d e n c eg r a p h s ( c d g s ) e x t r a c t e df r o md i f f e r e n ts o f t w a r e a r eo fl o ws i m i l a r i t ya n dd i f f i c u l tt ob em o d i f i e d t h i sm e a n st h a tc d gi sa ni d e a l o b j e c tf o rb i r t h m a r k t h i sp a p e rd e s i g n sac d g b a s e ds o f t w a r eb i r t h m a r ks c h e m e f o r n e ts o f t w a r e ，w h i c hu n i q u e l yi d e n t i f i e sap r o g r a mb a s e do ni t ss t a t i ca n d d y n a m i cc d g s t oi m p r o v et h em a t c h i n ge f f i c i e n c yo ft h ec d gs e t ，t h i sp a p e r p r o p o s e st w om a t c h i n ga l g o r i t h m sf o rs t a t i ca n dd y n a m i cc d g s t h es t a t i cc d g m a t c h i n ga l g o r i t h mi sb a s e do nt h ei d e ao fs e e k i n gt h el a r g e s tc o m m o ns u b - g r a p h 。 t h i sm e t h o dn o to n l ye n s u r e st h el a r g e s tc o m m o ns u b g r a p hi si s o m o r p h i c ，b u ta l s o g u a r a n t e e s t h ec o m p o n e n tn a m ei s c o r r e c t l ym a p p e d f o rt h ed y n a m i cc d g m a t c h i n g ，w ef i r s tt r a n s f o r mt h ec d gi n t ot h ed i s o r d e r e dl a b e lt r e e s ，a n dt h e n d e s i g nam a t c h i n ga l g o r i t h mw i t hl i n e a rt i m ec o m p l e x i t yf o rt h el a b e lt r e eb a s e do n t h ei d e ao fb r e a d t hf i r s ts e a r c hg r a p ha l g o r i t h m 。u n d e rt h ec o n s t r a i n tt h a tt h e n a m e so ft h ec o m p o n e n t sm u s tm a t c h ，t h ep r o p o s e dm e t h o d sa r ea b l et oe f f i c i e n t l y r e d u c et h em a t c h i n gc o m p l e x i t yf o rt h el a r g e s c a l eg r a p hs e t t od e m o n s t r a t et h ec r e d i b i l i t ya n dr e l i a b i l i t ya g a i n s ts e m a n t i c s p r e s e r v i n g t r a n s f o r m a t i o n s ，t h ep e r f o r m a n c eo ft h ep r o p o s ea p p r o a c h e si se v a l u a t e da n d c o m p a r e dw i t ht a n a m ma n dw p pb i r t h m a r k s e x p e r i m e n t a lr e s u l t ss h o wt h a to u r t e c h n i q u ei sa m o n gt h eb e s tm e t h o d sf o rt h es o f t w a r es y s t e mw i t hal a r g en u m b e r o fu s e rc o m p o n e n t s ，t h u ss u i t a b l ef o rl a r g e - s c a l es o f t w a r es y s t e m st op r o v i d e c o p y r i g h tp r o t e c t i o n i i i 硕士学位论文 k e y w o r d s ：s o f t w a r ep r o t e c t i o n ；s o f t w a r eb i r t h m a r k ；c o m p o n e n td e p e n d e n c eg r a p h ； g r a p hm a t c h i n g i v 基于n e t 组件依赖图的软件胎记研究 图1 1 图1 2 图1 3 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图2 1 1 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图4 1 图4 2 图4 3 图4 4 插图索引 全球主要区域软件盗版率1 全球主要区域软件盗版损失金额2 论文组织结构图4 软件胎记技术一般性框架9 保持语义转换攻击模型图。1 1 删减攻击模型图12 添加攻击模型图一1 2 j a v a 平台基层类的继承结构1 3 j a v a 平台基层类的继承结构1 4 j a v a 程序的一个s m c 调用序列1 4 取k = - 3 时，从一个简单方法中提取k - g r a m s 胎记示例1 5 一段程序代码中提取w p p 胎记的过程1 6 一段程序代码中提取w p p 胎记的过程17 k = - 2 时，d a p i 胎记序列集合图18 软件组件间的控制依赖示意图2 2 软件组件问的数据依赖示意图2 3 软件系统的一个局部动态依赖图示意图2 4 软件系统的全局静态依赖示意图2 5 组件依赖图转换成无序树的示意过程2 8 将一个动态组件依赖图转换成一棵简化的无序树2 9 基于n e t 平台的软件执行过程示意图3 2 基于n e t 组件依赖图的软件胎记系统框架图3 3 全局静态组件依赖图提取工具r e f l e c t o r 3 4 通过c l rp r o f i l i n g a p i 获取n e t 软件的调用树3 5 v i i 硕 ：学位论文 附表索引 表1 12 0 0 6 2 0 0 7 年全球软件业损失最高的1 5 个国家2 表4 1 软件胎记性能评估框架3 7 表4 2 基于n e t 组件依赖图软件胎记的独立性测试结果3 7 表4 3 基于n e t 组件依赖图软件胎记的误判性测试结果3 8 表4 4 基于n e t 组件依赖图软件胎记的可靠性测试结果3 8 表4 5t a n a m m 与w p p 胎记的独立性测试结果3 9 表4 6t a n a m m 与w p p 胎记的误判性测试结果一3 9 表4 7t a n a m m 与w p p 胎记的可靠性测试结果4 0 v u l 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的 个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后 果由本人承担。 作者签名：同tj 、碉 日期：炒多年月27 e l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名： 同t 卜职 导师签名：z 犷1 一八 疹 ? 日期：矽矿夕年 日期：加夕年 钐月习日 如其z q i e l 硕j ：学位论文 1 1 课题的来源与意义 第1 章绪论 本课题来源于国家自然科学基金项目“基于混淆编译理论的动态软件水印研 究( 6 0 5 7 3 0 4 5 ) 和教育部博士点基金项目“软件数字水印技术( 2 0 0 5 0 5 3 2 0 0 7 ) 的 部分研究内容。 i n t e r n e t 和p 2 p ( p e e r o t o p e e r ) 的快速发展给人们的学习和工作带来极大方便，人 们可以通过网络进行信息交互和资源共享。但随之而来的副作用不容忽视，通过 网络传输的数字产品很容易被恶意的个人或团体在未经许可的情况下非法使用。 软件作为一种典型的数字产品，在开发过程中需要投入巨大的人力物力，是开发 人员智慧和劳动的结晶，大量盗版软件通过网络肆意传播正使软件业蒙受巨大的 经济损失。 根据美国商用软件联盟( b s a ，t h eb u s i n e s ss o f t w a r e a l l i a n c e ) 和国际数据公司 ( i d c ，i n t e m a f i o n a ld a t ac o r p o r a t i o n ) 2 0 0 8 年联合公布的调查报告显示，2 0 0 7 年全 球软件盗版率为3 8 ，损失将近4 8 0 亿美元，l b 2 0 0 6 年增长了3 个百分点【lj 。图1 1 显示了全球各主要区域软件盗版率，图1 2 显示了各相应区域软件盗版损失金额。 中欧 中东 亚太 盗版率( ) 图1 1全球主要区域软件盗版率 基于n e t 组件依赖圈的软件胎记研究 中欧 中东 亚太 损失金额( s m ) 图1 2 全球主要区域软件盗版损失金额 另外，联合调查报告还指出，软件业发达的国家遭受更大的损失，2 0 0 7 年与 2 0 0 6 年基本持平( 如表1 1 所示) 。在全球软件损失最大的前1 5 个国家中，中国 居第二位，并且盗版率居第一位。软件盗版已严重影响全球软件业的健康发展。 表1 12 0 0 6 2 0 0 7 年全球软件业损失最高的1 5 个国家 软件厂商对待软件盗版的立场是矛盾的。一方面，软件厂商希望通过打击盗 硕上学位论文 版避免蒙受巨大的经济损失；另一方面，又担心过于严厉的保护会导致大量用户 流失而失去占领市场的机会。如何在提供版权认证信息或盗版检测的同时，不限 制用户对软件的使用是目前软件厂商理想的软件保护技术，并已经成为一个研 究热点。 现有软件保护技术主要以增加硬件设施、限制使用期限、满足分布式需求、 定期升级更新为主，在保护软件的同时也限制了软件执行，无法完全满足软件厂 商抢占市场的需求。同时，随着盗版手段的提高，软件盗版形式发生了显著变化。 特别是基于中间码的j a v a 和n e t 程序，能被轻易地反编译成易被程序员理解的 中间代码，从而可进行简单的代码复制、代码等价替换、仿造他人的软件设计模 式、方案、商业逻辑，或以相同或不同的计算机语言编码来另外实现。因此，在 不严格限制程序运行的情况下，对改变软件表现形式的盗版行为进行研究，有着 重要的现实意义。 软件胎记是从软件中提取的能惟一标识软件版权的固有特征集合。它是近几 年才兴起的一种软件保护技术，是复制检测技术的一个新分支，通过对比两个软 件的胎记相似度来判别软件版权归属。软件胎记技术不限制软件运行，并且在保 持语义变换后仍有很强的辨别力，所以该技术得到学术界与软件厂商的大力支持， 已成为国际学术界的一个前沿研究方向，处于迅速发展阶段。 1 2 研究内容与目标 本文主要研究基于n e t 软件静态与动态组件依赖图的胎记提取方法，并分析 采用此方法保护软件版权的效果，主要工作包括以下几个方面： 1 分析软件系统中动态与静态组件依赖图顶点之间的映射关系，借鉴现有图 匹配算法，为静态和动态组件依赖图分别提出一种近似匹配算法。 2 提出一种静态与动态组件依赖图结合的软件胎记方案。分析n e t 软件的 内部结构和运行原理，提取n e t 软件系统的静态和动态组件依赖图集合作为胎 记，并使用静态和动态组件依赖图匹配算法计算不同软件的胎记相似度。 3 测试基于n e t 静态与动态组件依赖图软件胎记技术的性能。通过对提取 的胎记进行相似度计算检测本文胎记技术的可信性和可靠性，并与现有的软件胎 记技术进行比较、分析优缺点。 软件胎记技术作为软件保护技术的一个新分支，实用领域对软件胎记技术提 出三个基本要求： ( 1 ) 可信性( c r e d i b i l i t y ) ：主要考察软件胎记算法误判率的高低。一个好的软件 胎记算法应能提取出软件中的各种细节，并以此准准确区分完成类似功能的不同 软件。 ( 2 ) 可靠性( r e s i l i e n c e ) ：主要是考察软件胎记算法抵抗等价变换攻击的能力。 基于n e t 组件依赖图的软件胎记研究 对于原始程序p 和对它进行等价转换而得到的程序p ，一个理想的软件胎记算法 从p 与p 中提取出的胎记应该具有高度的相似性，由此来判断程序p 是从程序p 盗版或演化而来。 ( 3 ) 高效性( e f f i c i e n c y ) ：主要考察软件胎记算法从软件提取胎记、比较胎记形 似度的效率。一个实用的胎记算法应该能快速的从软件系统中提取出惟一标识自 己的特征集合，并准确快速的计算两个软件中提取的胎记的相似度。 本课题的研究目标正是设计一种实用的软件胎记算法，使之满足如上的三个 基本要求，用于软件版权保护。 1 3 论文的结构 第1 章阐述了项目的来源和意义、课题的研究目标及本论文所做的主要工作。 第2 章综述了软件保护与软件胎记研究现状，详细介绍了软件胎记的相关知识， 包括软件胎记的定义、分类、软件胎记系统的一般模型、攻击模型和当前主要的软件 胎记算法。 第3 章详述了图和图匹配的基本思想，提出一种带约束的静态组件依赖图近似 匹配算法和一种基于无序标签树匹配的动态组件依赖图匹配算法。 第4 章分析n e t 组件依赖图的特点，给出一种基于，n e t 组件依赖图的软件胎 记方案。并通过介绍n e t 平台的架构和运行原理，给出静态组件依赖图和动态组 件依赖图的提取方法。 第5 章对本文提出的胎记方案进行实验评估，并与两个经典胎记技术进行对比。 最后总结了本文的主要工作，指出本文的主要贡献和不足，以及需进一步研究的 工作。 本文的论文结构图如图1 3 所示： i 第1 章绪论 上 i 第2 章软件保护技术概述 l第3 章组件依赖图与缉件依赖图匹配算法设计 l第4 章一种基于n e t 组件依赖图的软件胎记方案 i第5 章基丁n e t 组件依簿图的软件胎记性能评估 0 i总结 i 图1 3 论文组织结构图 硕十学位论文 第2 章软件胎记技术综述 2 1 软件保护技术概述 在针对软件保护的研究中，根据保护对象的不同，常常把软件分为两大类， 一类是软件宿主，又称软件主机或软件平台，主要指操作系统等能够承载其他软 件运行的软件；另一类是软件组件，就是通常意义上的软件，或称为软件模块。 针对软件宿主安全的研究，主要是如何防止合法用户和其数据被恶意客户端程序 所攻击，以及如何设计和管理计算机系统来实现一个严密的安全系统；针对软件 组件保护的研究，即如何防止合法软件在未经版权所有者同意的情况下被第三方 蓄意复制并分发以获得经济利益，或者把软件部分或全部代码归为已有。 由于软件宿主是软件组件的运行环境，通常是由某个商业组织独立开发的系 统平台，考虑到商业利益，开发者一般不会公布其所有的底层a p i ，故其安全性主 要由开发者自己维护。现今流行的杀毒软件也是保护软件宿主安全的重要手段， 它们根据软件宿主的漏洞或升级来更新保护措施，通常具有滞后性，没有某种既 定的研究方法。软件组件的安全问题与软件宿主的安全问题不同，原因在于软件 组件对于其运行环境的预期和假设有限，不能完全控制和了解自身将要运行的环 境，这决定了软件组件的安全问题要更为复杂和难以解决。引起全社会普遍关注 的软件盗版问题，就属于这个范畴，是软件保护的核心。根据是否包含硬件，软 件防盗版技术分为基于硬件的方法与基于软件的方法两类。 基于硬件的方法包括软件狗【2 训、特殊介质【2 ，5 】智能卡【6 引，这类方法的原理是 给系统加上一个软件执行开关，没有它程序不可执行。硬件方式的保护方法一般 具有较好的安全性，适用于安全性要求较高的独立系统，但是普遍成本较高、缺 乏灵活性，不适应分布式软件的部署，而且需要个体用户掌握相应知识，易用性 不强。由于目前软件产业的蓬勃发展，单独使用硬件方法来保护软件版权归属已 经远远不能满足现实的需要。比如加密狗是一种智能性加密产品，又被称为加密 锁，它是一个可以安装在并口、串口或u s b 接口上的硬件电路。但是对最终用户而 言，就必须在自己的机器上安装相应的保护硬件和驱动程序，存在易用性不强的 问题，价格也比较高。 基于软件的方法主要包括加掣3 1 、加壳【3 ，4 1 、混淆技术1 1 、防篡改【1 2 - 15 1 、软件 水印【1 6 - 19 1 、软件更新【2 0 1 、复制检测技术【2 m 4 1 和软件胎记【2 5 - 3 u 等。这类方法对软件的 保护程度完全取决于采用算法的好坏，主要特点是成本低、适合在线发布，普遍增加 了软件本身的运行代价。由于软件方式的保护方法成本一般较低，灵活性强，能提 基于n e t 组件依赖图的软件胎记研究 供适当的保护力度，适合大部分软件保护的需要，现有的软件保护技术研究主要集 中在第二类，下面分别对这些技术进行介绍： 1 ) 加密技术( e n c r y p t i o n ) 加密是通过隐藏软件的内容实施保护，它利用加密算法对代码和数据进行加 密，防止软件被静态分析。常用加密算法包括单向散列算法m d 5 、s h a 、c r c ， 公开密钥算法r s a 、d s a 等【3 】。它是伴随着软件解密技术的发展而发展的，理论 上讲，加密前的软件和加密后的软件在功能上应当完全相同，所以必然存在某种 方法可以在保证功能不变的前提下，把加密的部分从软件本身移除，所需要的仅 仅是时间而己。同时，加密的程序运行时在内存中需要解密才能执行，这会影响软 件的执行效率，对一些流程复杂的软件不太实用。 2 ) 加壳技术( p a c k e r c r y p t e r t e c n o l o g y ) 加壳( s h e l l ) 是防止攻击者对程序文件的非法修改和反编译而采用的一种方法p ，4 】， 它给编译好并加密的程序加上一个附加程序，附加程序通过w i n d o w s j 1 载器载入内存 后，先于原始程序取得控制权，然后对原始程序进行解密，还原完成后再把控制权交 还给原始程序执行。加外壳能有效地防止对程序的非法修改，还可以防止程序被静态 反编译，但加壳技术显著增加了程序额外开销，需要占用大量的系统资源。加壳的软 件保护方法虽然在一定程度上增加了软件破解的难度，但是随着硬件技术的迅速发展 及计算机技术的普及，特别是基于虚拟机的j a v a 和n e t 程序非常容易被反编译成容 易理解的中间码，只要有足够的时间，一个熟练的软件逆向工程工作者总是能破解。 3 ) 混淆技术( o b f u s c a t i o n ) 代码混淆的目的是隐藏软件的功能与方法，在保留程序功能的同时让程序的 可读性尽量降低，使混淆后的程序很难被动态或静态反编译。它是一种转换技术， 程序被转换后具有与原程序相同的行为和难以理解的语义。其原理是通过变换代 码，混淆原程序的数据结构和控制流，转换一个程序p 到另一个程序p ，使得p 对 逆向工程师来说更为困难。混淆技术作为一个与加密技术互补，针对逆向工程的安 全分支，正受到越来越多的关注，它也经常与其他软件保护技术一起使用来增强保护 效果( 1 6 1 。混淆技术能有效防止攻击者对程序的动、静态分析，但增加了软件维护者维 护和修改软件本身的难度。 4 ) 防篡改技术( t a m p e rp r o o v m g ) 软件防篡改技术是一种防止软件被非法篡改的技术，主要是通过对软件进行完整 性校验来判断软件是否被篡改。它的目标是检测程序的完整性是否被破坏，使软件具 备在恶意主机环境下抵抗被篡改的能力 1 2 - 1 5 】。a u c s m i t h 提出了一个基于i v k ( i n t e g r i t y v e r i f i c a t i o nk e r n e l ) 的防篡改模型，让程序自动检测自身关键代码的完整性 1 2 , 1 3 】。h o m e c ta 1 d 2 】提出了一种类似的设计方案，在软件中嵌入多个用于检测的方法，每个方法 负责检测一小部分代码的完整性。这种嵌入多个检测方法的设计增大了系统的信息 硕l ：学位论文 熵，使得攻击者很难找到并去除整个检测功能。另外，c h a n g 和a t a l l a h t l 5 j 提出一种 在软件中嵌入多个守护程序的方案。在软件中嵌入多个守护程序，每个守护程序负责 不同的安全工作，最简单的情况是嵌入两个守护程序，第一个负责关键代码的完整性 检测，另一个负责当完整性被破坏时对程序进行自动修复。防篡改的显著缺点是需要 额外开销，增加了程序时间和空间花费。 5 ) 软件更新技术( s o f t w a r ea g i n g ) 软件更新是使用非对称加密技术【2 0 1 ，更新后的软件仍然支持旧版本的所有功 能，但无法对其实施逆向工程攻击。文献 2 0 】详细介绍了利用软件更新技术防止 软件盗版。软件更新存在如下缺点：使用范围小，通常应用在文档级的应用软件， 如微软的w o r d ，这些软件在处理数据时基于特定的格式，另外频繁的更新增加了 软件额外的花费。 6 ) 软件水印技术( s o f t w a r ew a t e r m a r k i n g ) 软件水印是近年来出现的软件产品版权保护技术。它通过在程序发行前嵌入 秘密消息，在将来的盗版检测过程中尝试提取此秘密消息，以证明软件的所有权。 该技术可提供所有者鉴别、所有权验证、操作跟踪、拷贝控制等服务，是密码学、 软件工程、算法设计、图论等学科的交叉研究领域【i 们。通常意义上的软件水印技 术包含两个方面，即水( w a t e r m a r k i n g ) 和指纹( f i n g e r p r i n t i n g ) ，两者统称软件水 印。前者嵌入的是软件版权拥有者的信息，而后者嵌入的是软件使用者的信息， 具有惟一性。 根据嵌入与提取水印时机，软件水印分为静态与动态两种【1 6 】。静态软件水印， 如静态数据水印、静态代码水印，它们的存在不依赖于软件的运行状态，可以在 存放、分发以及运行时被验证。静态水印很容易被定位和破坏，鲁棒性较差；而 动态水印的存在依赖于软件的运行状态，通常是在一类特殊的输入下才会产生， 其验证也必须在这类特定输入下才能完成。根据产生时机和位置可分为：e a s t e r e g g 水印、动态数据结构水印 1 7 , t s 、动态执行序列水印【2 们。但是不论静态水印还 是动态水印都很难在保证程序功能的情况下保证嵌入的秘密消息不能或难以去 除，实用的软件水印目前还是一个空白。 刀复制检测技术( c o p yd e t e c t i o n ) 复制检测技术主要集中在文档复制检测上，用于判断一个文件的内容是否抄袭于 另外一个或多个文件。在软件保护的应用上，主要是针对源代码相似性的检测。如对 于一个程序源代码文件p ，使用少量代码等价变换、同义词替换等方法后得到源代码 文件p ，则可以通过复制检测技术得出p 是从尸抄袭得来。文本复制检测有两类基本 的检测方法，一类是基于字符串比较的方法- k o l m o g o r o v 复杂度【2 4 1 ，另一类是基于 词频统计的方法属性计数法( a t t r i b u t ec o u n t i n g ) 2 1 】。复制检测还可以借鉴信息检索 中的很多方法，b i , ! z i v s m ，i i s 和基于结构的结构度量( s t r u c t u r em e t r i c s ) 2 2 等等。此外 基于n e t 组件依赖图的软件胎记研究 还有人提出用神经网络来检测程序复制【2 3 】，b a k e r 和m a n b e r l 2 4 】采用三种应用于源代码 和文本的相似性度量工具s i f t , d u p 和d i f t , 对i a v a 字节码进行相似性鉴别。 该技术使用方便，不需对源程序做任何预处理，还可应用于图像、音频、视频的 复制检测。但作为一种软件保护措施，还存在两大缺点：一是软件相似度的计算基于 源代码的相似度，它主要应用在遵守某种协议的开源软件，而软件厂商通常以二进制 的形式发布自己的产品，在保护二进制软件版权上显得无能为力；二是当对程序进行 保持语义转换或流程混淆之后，该技术对转换前后的两个程序视为不同的程序，抗混 淆攻击的能力较差。 8 ) 代码克隆检测技术( c o d ec l o n ed e t e c t i o n ) 代码克隆是对一个程序片断不做大量修改而直接拷贝片段的代码复制技术，该技 术主要应用在代码的复用中。针对该种复制技术，很多检测技术被应用在程序克隆鉴 别中，例如匹配的抽象语法树【明以及代码段的比对【2 8 】。但是，类似于文本复制检测技 术的不足，该技术也只能应用在源代码级别。 9 ) 软件胎记技术( s o f t w a r eb i r t h m a r k i n g ) 软件胎记是程序所特有的能标识其本身的特性或特性集合。胎记技术通过对两个 软件中提取的胎记进行相似度的计算，来判定软件的盗版行为。通常，如果两个程序 p 和q 拥有相似的胎记，则证明它们之间具有相似性，即可能存在盗版的关系。 同软件水印技术一样，软件胎记常用来检测软件盗版。但两者又有所不同。首先， 软件水印必须在程序中添加额外的代码，而软件胎记通过检测程序本身固有特性的相 似性来判断是否存在盗版。另外，不同于软件水印可提供软件版权信息验证并能追踪 软件的非法散播来源，软件胎记只能确认一个程序是否为另一个程序的拷贝。对于一 个理想化的胎记系统而言，即使程序经过保持语义等价转化，仍能够提供准确的软件 相似性鉴别。 2 2 软件胎记技术 2 2 1 软件胎记的定义和分类 软件胎记是程序所拥有的，能惟一标识程序本身的固有属性或特征集合【2 5 1 。它是 复制检测技术的一个新分支，通过比对两个软件的胎记相似度检测盗版【3 2 1 。其一般性 框架模型如图2 1 所示，对于完成类似功能的软件彳和曰，首先通过胎记提取算法提取 出各自的胎记，然后使用胎记比较算法计算其相似度，若相似度大于设定的阈值0 【则 认为可能发生盗版，否则认定未发生盗版。 与软件水印技术类似，软件胎记根据是否在运行过程中提取软件的特征集合，分 为静态胎记与动态动态两种。静态胎记提取静态的程序变量信息集合，比如域的类型 和初始值；动态胎记收集程序执行时的特征信息集合作为软件的胎记。一个动态的胎 硕十学位论文 记算法立足于整个程序层次，而静态胎记算法立足于整个程序或程序的单个模块。它 们之间有联系也有区别，现将它们定义如下： 7 ( 警卢赙 图2 1软件胎记技术一般性框架 定义1 1 静态软件胎记( s t a t i cs o f t w a r eb i r t h m a r k ) 假设p 是程序模块集合，e x t r a c t 是一种从程序模块p 中提取特征集合的方法，则胎记b 是根据方法e x t r a c t 而获取的一系 列特征集合：e x t r a c t ( p ) 专b 。 定义1 2 动态软件胎记( d y n a m i cs o f t w a r eb i r t h m a r k ) 对于程序p 和输入序列， e x t r a c t 是在给定输入序列的程序执行过程中所提取的特征集合的一种方法，则胎记b 是根据该方法所提取的一系列程序特征集合：e x t r a c t ( p ，j ) - - b 。 软件胎记系统主要包括两个部分，胎记提取和胎记相似度比较。胎记提取依赖于 e x t r a c t 算法，静态与动态胎记的提取区别在于是否在程序运行时进行。检测一个 软件是否盗用于另一软件，最终依赖于使用同一e x t r a c t 算法提取的两个胎记的相 似度比较。文献【2 5 】给出一个较好的评判标准，已为广大软件厂商和学者认同，现描 述如下： 定义1 3 软件相似性( s o f t w a r ed e r i v a t i v e ) 勘，g 是程序模块集合，占 l ，若满足 下列条件，则称p ，q 具有相似性： ( 1 ) 满足程序外部行为属性 ( 2 ) 卜s i m i l a r i t y ( b p ，6 口) s ，则称厂具有可信性。 属性1 3 可靠性( r e s i l i e n c e ) 设p 是p 经过等价转换r 而来，为一个胎记提 取算法，若厂( p ) = f ( p ) 或f ( p ，) = 厂( p ，) ，则称算法厂对f 具有高可靠性，若对 于设定的阈值g ，函数厂满足卜s i m i l a r i t y ( b p ，b ) - 一p ，( 与p 等价程序) 提取胎记提取胎记 初始胎记bl 8 b 、一变换后胎记曰 图2 2 保持语义转换攻击模型图 由上图中可以看到，此种攻击的结果试图得到一个程序p ，它的功能与原 程序尸等价但特征相异。目前，特别是针对基于虚拟机的j a v a 和n e t 程序，已 存在许多代码与流程混淆工具，它们都是保持语义的转换工具。软件开发者使用 它们把源代码转换成难以阅读的等价代码，以此防止代码非法拷贝。这种工具同 时也为软件胎记攻击者提供了攻击手段，因此，一种实用胎记技术应该能抵御各 种混淆工具的攻击。 ( 2 ) 删减攻击( c r o p p i n ga t t a c k ) 在基于组件的软件系统中，系统的各种功能由某个组件独立完成，或由几个 基于n e t 组件依赖罔的软件胎记研究 组件协同完成。软件系统删减某些组件通常对其他组件并无影响，而删除部分功 能后的软件系统仍有很大的价值，且删除前后所提取出的胎记不相同，故删除攻 击是攻击者常用的攻击手段。图2 3 为删减攻击模型图。 图2 3 删减攻击模型图 攻击者通过分析软件系统各组件的功能，删除部分次要功能，然后发布出去 以达到软件盗用的目的。因为软件组件是一整套完整定义接口的代码模块，是一 个比对象更抽象的实体，是可管理的、独立的逻辑程序块，是可以进行独立分离、 易于重复使用的软件部分。这种情况下，删去攻击的成功率相对较高。 ( 3 ) 添加攻击( a d d i t i v ea t t a c k ) 与删减攻击相反，攻击者为软件系统增加部分功能组件或模块，使得增加前 后提取的胎记相异，以达到添加攻击的目的。通过对核心代码进行包装，以另一 种崭新的界面展现给用户，这种添加攻击是软件盗用者的常用方法。图2 4 为添加攻击模型图。 图2 4 添加攻击模型图 对于软件胎记攻击者而言，他们通常同时使用几种攻击方法，使得通过提取 软件胎记来检测盗版显得更加困难。设计一种同时抵御三种攻击的胎记技术是本 文研究的重点。 2 2 3 软件胎记技术应用 目前，软件胎记已经得到了一定的应用。美国加州大学b e r k e l e y 分校的a a i k e n 等人开发的m o s s 系统( m e a s u r eo f s o f t w a r es i m i l a r i t y ) ，悉尼大学的m i c h a e l 硕一l 二学位论文 j w i