一种增强型动态图的软件水印算法

王 巍, 何 颖, 谭永坤, 刘衍珩,3

(1. 长春财经学院 信息工程学院, 长春 130122；2. 中国电子科技集团公司第五十四研究所, 石家庄 050081；3. 吉林大学 计算机科学与技术学院, 长春 130012)

软件水印是一种软件版权保护技术, 其将承载版权保护信息和身份认证信息的数据直接或间接嵌入数字载体. 目前实现方式主要有静态软件水印和动态软件水印两大类. 由于动态软件水印技术在隐蔽性、 抗攻击、 防篡改等方面明显优于静态软件水印, 因此已逐渐成为软件水印技术的主要实现方法, 其典型代表是基于动态图的软件水印.

基于动态图的软件水印[1]是指将水印信息编码到某种图结构中, 然后在程序运行过程中动态构建图结构并生成水印信息. Collberg等[2]首次提出了动态图水印CT(Collberg-Thomborson)算法, 在程序运行时动态生成的数据结构图拓扑中嵌入水印信息, 探讨了PPCT(planted plane cubic tree)编码、 基数k链表水印数的可行性； Palsberg等[3]采用PPCT编码结构实现了CT算法, 进一步证明了基于动态图的软件水印算法具有较强抗攻击性、 防篡改和鲁棒性; 刘嘉怡等[4]提出了一种基于PPCT和排序图的混合编码方法, 增强了水印的隐蔽性, 但在两种编码方案所需叶节点不同时, 会导致叶节点的冗余； 苏庆等[5]将水印信息编码至Petri网运行时状态序列中, 该方案具有较高的水印数据率和一定的检错恢复能力, 但攻击者易发现程序中的水印片段, 防篡改相对减弱； 郑秋梅等[6]利用颜色直方图差值法从视频序列中提取关键帧, 对关键帧和水印图像分别进行非下采样Contourlet变换、 离散余弦变换以及离散平稳小波变换, 提高了水印的嵌入容量, 对抵抗常见时、 空域攻击具有较好的鲁棒性.

目前, 对动态图软件水印技术的研究已有许多成果[7-8]. 但研究将水印信息保存在数据结构数据域中的相关报道较少. 基于此, 本文提出一种基于动态图的软件水印算法----增强型动态图水印(enhanced dynamic graph watermarking, EDGW)算法, 并对数据嵌入率、 隐蔽性及抗攻击性3个参数的性能进行取舍, 设计适应实际应用场景的软件水印算法, 研究其可行性与性能的优劣.

1 算法核心思想

本文提出一种新的动态图水印算法, 水印数不再由图结构的拓扑本身编码, 而是向水印图结构的每个节点中增加一个数据域用以存储水印信息, 使水印保护不受水印图结构编码的影响.

增强型动态图水印算法是对动态图软件水印算法的一种改进算法, 其采用增强型动态图数据结构, 通过将水印信息存储在动态生成数据结构的数据域中的方式向程序中嵌入水印信息, 其水印嵌入和提取过程如下：

步骤1) 根据水印分解算法将水印数W拆分为包含k个水印分存值的集合Wi(0≤i

步骤2) 根据k的大小从候选数据结构中选择一个包含k个节点的水印图G, 用其节点的数据域嵌入水印分存值Wi；

步骤3) 分裂水印图G, 得到子水印图集合Gi(0≤i

步骤4) 将子水印图Gi转换为中间代码段Mi(0≤i

步骤5) 将中间代码段Mi转换为创建水印子图的目标代码段Ci；

步骤6) 将目标代码段Ci嵌入到一个特定输入序列li(0≤i

步骤7) 在嵌入水印程序中输入步骤6)中选取的输入序列li(0≤i

步骤8) 选取特定的遍历算法遍历水印图G, 从G中提取Wi；

步骤9) 选取特定的合并算法将水印分存值集合Wi还原为水印数W.

与通常的动态图水印算法相比, 增强型动态图水印算法提高了动态图水印的性能.首先, 动态图数据结构以通过增加数据域保存水印信息的方式明显提高了数据嵌入率； 其次, 动态图的数据结构仍在程序运行过程中动态构建生成, 动态特性仍保持不变, 仍保留其隐蔽性、 抗攻击性和防篡改等动态图结构的优点.

2 增强型动态图数据结构

本文提出的增强型动态图数据结构针对链表结构和二叉树结构的水印图结构进行改进.

定义1动态图数据结构以通过增加数据域保存水印信息得到的数据结构称为增强型动态图数据结构； 由基数k链表改进后的数据结构称为增强型基数k链表结构, 由PPCT结构改进的数据结构称为增强型PPCT结构.

2.1 增强型基数k链表结构

链表结构包含n个节点, 每个节点由左指针域、 右指针域和数据域构成. 其中： 右指针实现节点链接; 左指针用于防篡改, 可被设计成置换链表形式或基数k链表编码形式； 数据域用于存储采用大数分解算法得到的水印分存值. 图1为增强型链表结构示意图.

图1 增强型链表结构示意图Fig.1 Schematic diagram of enhanced linked list structure

图2 增强型PPCT结构示意图Fig.2 Schematic diagram of enhanced PPCT structure

2.2 增强型PPCT结构

增强型PPCT结构中, 每个节点增加一个数据域, 用于存储水印数. 由于水印分存值个数即PPCT的叶节点数确定, 因此可从构建的水印库中随机选择具有相同叶节点数的增强型PPCT的任意一种拓扑结构表示同一水印数, 以降低模式匹配攻击的威胁. 图2为增强型PPCT结构示意图.

3 实现过程

本文借助已有的实验平台Sandmark[9]实现包含嵌入水印和提取水印两个过程.

3.1 嵌入水印

嵌入水印的流程主要有以下步骤：

2) 生成图结构.从候选数据结构中随机选择一个节点与水印分存值个数相等的图结构, 即包含k个节点的水印图G； 然后按照一定的算法将水印分存值Wi依次存入水印图G的数据域内.

3) 分裂图结构.将水印图G分裂为若干水印子图Gi(0≤i

4) 生成中间代码.图3为某子水印图及其中间代码.由图3可见, 从水印图的根节点进行深度优先遍历搜索, 生成过程如下： 以一个相反的拓扑顺序在每个节点处都生成CreateNode( )指令； 生成m=CreateNode( )和n=CreateNode( )两个节点后, AddEdge(n,m)添加链接指针连接节点m和n； 用SaveNode指令将子图的根节点保存在一个全局的数据结构中, 以保证子图的所有节点在任何时刻均可全局访问.

5) 生成目标代码并插入. 根据中间代码生成目标代码, 图4为某水印图对应的目标代码(以Java语言为例). 生成目标代码后, 先将被选中的可用标记点替换成Watermark.create( ), 然后用一个覆盖整个程序的混淆算法对该成员函数进行内嵌化或者重命名该类名字等操作. 混淆和优化防止攻击者对水印代码进行模式匹配攻击.

图3 某子水印图(A)及其中间代码(B)Fig.3 Sub watermark image (A)and its intermediate code (B)

图4 水印图对应的目标代码Fig.4 Object code corresponding to watermark image

3.2 提取水印

首先输入跟踪过程中输入过的密钥序列, 水印图G会在内存的堆中构建； 其次选取特定的遍历算法从G中提取Wi； 最后通过特定的合并算法将水印分存值集合Wi合并得到原始水印数W.

4 结果分析

4.1 实验环境

本文借助实验平台Sandmark进行实验, 实验硬件及软件配置要求如下： 内存为1 GB以上, 剩余磁盘空间为2 GB以上, 操作系统为Windows7 64 bit或Windows10 64 bit, 软件为JDK,Eclipse,Sandmark.

4.2 实验样本

实验选择两个软件作为实验的样本程序： 计算器(Calculator)和tic-tac-toe(TTT). 样本程序的特征参数列于表1.

表1 样本程序的特征参数

图5 不同数据结构动态嵌入率对比结果Fig.5 Comparison results of dynamic embedding rate of different data structures

两个样本程序的大小成倍递增, 计算器的规模较小, 而TTT则具有适中的规模. 因此, 该样本程序具有代表性.

4.3 实验结果分析

下面从数据嵌入率、 隐蔽性和抗攻击性三方面分析增强型动态图水印算法的性能.

4.3.1 数据嵌入率分析

不同数据结构动态嵌入率对比结果如图5所示. 由图5可见： PPCT嵌入率最低, 极限小于0.5； IPPCT(intensify planted plane cubic tree)嵌入率约为基数k链表的1/2； 置换链表与基数k链表动态嵌入率的渐近趋势一致, 在给定的根节点上置换链表的嵌入率小于基数k链表的嵌入率； 而EDGW结构的嵌入率在任何节点情况下均约为10.6. 因为每个节点增加了一个数据域, 在通常的32位处理机中, 一个整型变量所占的空间是一个双字, 其数据嵌入率约为10.6位/双字, 与基数k链表编码当n=255时嵌入率约为1 bit/节点相比约为其30倍.基数k链表数据嵌入率随节点数的增加呈对数形式增长, 而EDGW数据嵌入率则不再增长. 因此, 增强型水印算法的动态嵌入率有极大提升.

4.3.2 隐蔽性分析

定义2(水印算法隐蔽性)[10]假设Java程序中所有类型的字节码指令集合S1={I0,I1,…,Im}, 嵌入水印后样本程序为Pw,Pw中各种字节码指令相对S1占比为R1={x0,x1,…,xm}, 一般Java程序中各种字节码指令占比为R2={y0,y1,…,ym}.则Pw和程序之间的特征距离值定义为

(1)

其中x0,x1,…,xm分别为字节码I0,I1,…,Im在嵌入水印后样本程序Pw相对S1占比,y0,y1,…,ym分别为字节码I0,I1,…,Im在未嵌入水印程序中占比.

本文使用Sandmark平台上的字节码查看工具, 根据Collberg等[11]统计的1 000多个Java程序中各种类型字节码占比频率, 得到嵌入水印后的水印程序Pw的字节码指令的分布情况. 不同动态图水印的隐蔽性数据列于表2.

表2 不同动态图水印的隐蔽性

由表2可见, 增强型动态图水印的隐蔽性与一般动态图水印的隐蔽性类似. 在一般程序中生成一种数据结构时都含有数据域, 而一般动态图水印节点中只有指针, 易引起攻击者的兴趣. 增强型动态图水印在保持动态图水印原有优点的前提下避免了该缺欠, 在增强型算法中生成的数据结构不仅具有指针域而且还有数据域, 使生成这种结构的代码更像一段“正常”的程序.

4.3.3 抗攻击性分析

软件水印攻击方法主要有加法攻击(additive attack)、 减法攻击(subtractive attack)及扭曲攻击(distortive attack)[12]. 加法攻击和减法攻击较难实施, 前者可通过在嵌入水印时添加时间戳避免, 后者进行攻击需要大量的静态程序代码分析； 扭曲攻击中的保持语意变换攻击是目前最常用、 最有效的攻击方法. 因此, 为验证变换后能否正确提取出水印数, 实验中对样本程序进行混淆变换攻击. 实验数据列于表3, 其中“+”表示抗攻击性良好, “-”表示识别过程失效. 由表3可见, 在多种混淆攻击下, 除Split Classes识别过程失效, 其他动态图水印抗攻击型都表现良好. 增强型软件水印结构有助于建立一个更大的水印库, 增加攻击者获得嵌入软件中的软件水印具体结构的难度, 使攻击者破解水印的代价变高. 在总体上, 增强型动态图水印算法保持着较高的抗攻击性.

表3 不同动态图的抗攻击性结果

续表3

综上所述, 本文提出的增强型动态图水印算法较通常的动态图水印算法具有优势. 首先, 算法改进了动态图数据结构, 增加数据域保存水印信息, 明显提高了动态软件水印的数据嵌入率； 其次, 增强型动态图的数据结构仍在程序运行过程中动态构建生成, 动态特性仍保持不变， 仍保留了动态图结构的隐蔽性、 抗攻击性和防篡改等优点； 最后, 引入中间代码生成技术增加了程序的可重定位性及复用性. 因此, 本文算法提高了动态图水印的性能且复用性较好.