基于决策树的数据库脆弱水印算法研究＊

（1.空军后勤部指挥自动化站 北京 100720）（2.第二炮兵后勤部信息中心 北京 100820）

1 引言

关系型数据库是以二维表作为数据模型的数据库系统，自20世纪70年代发展至今，特别是互联网远程访问数据库操作普遍化，关系数据库水印技术成为一种有效版权保护技术逐步得到重视。关系数据库数字水印是指在不破坏关系数据库数据可用性的前提下，在关系数据库的冗余空间中嵌入水印信息，实现保护关系数据库版权或断定其是否遭到攻击和篡改的目的［1］。数字水印包括鲁棒水印和脆弱水印，脆弱水印主要用于数据的真伪辨别和完整性鉴定，能够敏感发现对数字作品任何形式的改变，从而确保能够检测对数字作品的篡改。

文章主要对关系数据库脆弱水印技术进行研究，在保护数据库数据准确性基础上，按照决策树算法分组，并对利用元组属性数据最低有效位采用汉明码编码等方法进行数据检测，并嵌入水印信息实现数据库脆弱水印的构建。

2 数字水印技术

目前数据库水印算法主要是利用一定失真范围内的数据变形来嵌入水印。IBM Almaden 研究中心R.Agrawal于2002年提出了对关系数据库中数值型属性值进行标记的策略，利用数值型元组存在的冗余空间，对某些数值属性的最低有效位（LSB）进行位操作，从而实现水印信息的嵌入［2］。R.Sion等人 进一步对关系数据库水印进行研究，采用给定数值型项目集合S＝｛s1，s2，s3，…，sn｝以及一个排序密钥K，根据标准化项目的最大意义比特位的加密键值哈希对其进行秘密排序，构建子集Si用于嵌入比特位水印标记［3］。牛夏牧等人对关系数据库数字水印进一步研究加入小量有实际意义水印的技术，清华大学张志浩等人2004年提出把一幅图像嵌入到关系数据库中的水印算法［4］。

Guo等人提出了数据库脆弱水印算法，将数据库元组划分到不同分组中，生成由属性水印和元组水印构成的分组水印矩阵，从而定位数据篡改位置［5］。Hsien-Chu Wu等人根据数据库关系数据之间存在相关性，运用支持向量回归（SVR）训练样本，得到属性的最佳关系模型，然后选取一个属性作为目标值，剩余属性作为SVR 训练特征值进行训练，生成Huffman编码，并利用私钥进行加密放在数据库后作为有效负载信息随着数据库一起传输，作为检测篡改的脆弱水印［6］。

3 改进型C4.5决策树

决策树是数据挖掘分类方法中的常用方法，能够以图形化的形式表现挖掘结果，从而方便使用者快速作出决策或预测。其中，ID3算法是J.R.Quinlan于1986年首先提出的一个经典决策树算法，该算法以信息论为基础，把信息增益度量属性选择，选择分裂后信息增益最大的属性进行划分［7］。该算法最大的不足是每次分裂倾向于选择取值较多的属性且不能处理连续型数据。

为了解决ID3算法不足，Quinlan在1993年在继承决策树基本构造思想基础上提出C4.5算法，该算法用信息增益率代替信息熵作为选择分裂属性的标准，对连续数值进行离散化，并递归生成一个判定树［8］。

C4.5算法策略如下：1）判定树以代表训练样本的单个节点开始；2）如果样本都在同一个类，则该节点成为树叶，并用该类标记；3）否则，使用称为信息增益率的基于熵的度量作为启发信息，选择最好将样本分类的属性作为该节点的“测试”或“判定”属性；4）对测试属性的每个已知的值，创建一个分枝，并以此为根据划分样本；5）使用同样的过程，递归地形成每个划分上的样本判定树。当出现下列情况时停止递归划分：给定节点的所有样本属于同一类：没有剩余属性可以用来进一步划分样本；没有剩余样本。

C4.5算法对于连续性数值进行基于增益率划分为不同区间，从而完成离散化操作。首先使用快速排序算法对属性值进行排序，然后计算信息增益，并确定最大信息增益为局部阈值，在用顺序查找的方法寻找最接近但不超过局部阈值的实际数值为该连续属性的分割阈值。

在树的每个节点使用信息增益率的度量选择测试属性，选择具有最高信息增益的属性作为当前节点的划分属性。假设S是s个数据样本的集合，类标号属性具有m个不同值（或连续属性分割为m个数值区间），定义m个不同的类Ci（i为正整数），si是类Ci中的样本数。那么对给定样本的期望信息为

其中Pi为任意样本属于Ci的概率，假设Pi估计为s1／s。

对于分类属性A，假设具有v个不同的值（a1，a2，…，av），那么数据样本总集合S可以划分为v个子集（s1，s2，…，sv），其中Sj是S中具有aj的样本，sij是子集Sj中Ci的样本数。那么，在属性A上划分子集的熵为

那么，针对属性A划分的信息增益为

属性A对类别集合C的信息增益率为

针对在关系数据库水印技术中的具体应用，对C4.5决策树算法进行优化改进，主要集中在两个方面：一是引入模糊数学方法改进连续数值分割方法；二是建立决策树子树剪割原则，优化决策树结构。

在采用常规方法根据最大增益求得分割的最大阈值，在此基础上引入模糊隶属函数方法的三角函数法［9］，既根据C4.5基本方法准确分割决策树又能减少计算量并有效提高后续数据库水印的鲁棒性。三角模糊数引入连续值分割先要对分割最大阈值进行模糊化处理，假设某属性C的分割最大阈值为VGmax，对于属性C中取值最小值Vmin和最大值Vmax，那么属性分为｛Vmin，VGmax｝和｛VGmax，Vmax｝两个部分，并针对性求得两个部分的最大分割阈值VGmax1和VGmax2。对于属性C的最大分割阈值VGmax分〈a1λ，VGmax1，β1λ〉和〈a2λ，VGmax2，β2λ〉两个部分，其中a1＝VGmax1-Vmin1，a2＝VGmax2-Vmin2，β1 ＝Vmax1-VGmax1，β2 ＝Vmax2-VGmin2，λ为三角模糊系数λ∈［0，1］。通过调整λ的大小控制阈值划分区间的大小，从而控制划分子树的大小。

在关系数据库的水印技术应用中，根据嵌入水印位数W的不同，以及数据库嵌入比例r的不同，对决策树子树大小有一定要求，从而提供一种子树剪割原则，即作为n层决策树的第i层叶子节点，符合该节点属性的元组数m应当满足公式：

即当符合某节点属性要求的元组数目小于上公式要求时，即可剪除该子树不再继续进行分割划分，从而有效提高决策树构建速度。

4 水印嵌入算法

对数据库数据进行水印信息嵌入，主要针对文本和数值两种类型数据进行嵌入，为了确保关系完整性和数据准确性，采用不同的嵌入方法和数据对象筛选原则。

4.1 文本型数据嵌入方法

对于文本型数据水印嵌入，为了确保水印信息的隐蔽性，采用在文本数据最后加入“空格”方法实现水印嵌入。当水印序列为“0”时，该元组属性文本数据结尾不加入空格；当水印序列为“1”时，该元组属性文本数据结尾加入空格。在水印检测时，通过比较文本长度和空格位置，当两者一致时则提取“0”，否则，当两者不一致时提取“1”。

4.2 数值型数据嵌入方法

对于数值型数据水印嵌入，主要利用数值型数据的最低有效位（LSB）进行嵌入，基本要求是数值型数据的字段长度低于最低有效位数，根据长度相差多少确定嵌入信息量的大小，可以填充信息的位数成为可填充位。这里主要嵌入三种信息，一是水印信息，二是奇偶校验信息，三是汉明纠错码信息，根据可嵌入最低有效位的位数来按照重要性依次嵌入三种不同信息：

1）水印信息嵌入

根据要嵌入属性Ai的各元组有效位，选择要嵌入水印最低有效位r，根据要嵌入水印序列信息，为“1”时嵌入1，为“0”时嵌入0，对于某元组该属性的最低有效位q（q＜r），将其中q～r位用0填充。

2）奇偶校验信息嵌入

在嵌入水印信息后，如果仍有可填充位，那么结合数据信息的奇偶数，对填充进行填充。如果校验的数据中有奇数个奇数，那么填充“1”，如果有偶数个奇数，那么填充“0”。

3）汉明码嵌入

汉明码是一种能自动检测并纠正一重错的线性纠错码［10］，设数据位数为m，校验位数为k，总编码数为n＝m＋k，那么根据汉明不等式：

采用（7，4）分组码最小码距d＝3，能够纠1个错或检2个错，假设A＝a1a2a3a4，那么添加校验位a5＝a1＋a2＋a3，a6＝a2＋a3＋a4，a7＝a1＋a3＋a4，其中“＋”表示位的“与”运算，最后构造含有纠错位的汉明码为A＝a1a2a3a4a5a6a7。根据汉明纠错编码要求，按照属性数值数据进行汉明编码添加在填充位中。

那么假设某元组属性数据为7.04，该属性所有元组最低有效位为0.001，定义长度为16，分析有效填充位为7位，水印信息为1，根据水印嵌入算法，那么按照步骤1，q＝2，r＝4，在第5位嵌入1，空余为嵌入0，得到7.0401。按照步骤2，数值数据7.0401中共有奇数个奇数，应该填充1，得到数据7.04011，最后对数据7.04011按照（7，4）汉明编码，对7.04011按照4位分组编码根据汉明编码，并转换为8进制数据，得到最后编码数据7.0401186。

5 基于决策树的数据库脆弱水印技术

5.1 一种新的数据库脆弱水印模型

关系数据库水印技术主要包括关系数据库水印嵌入系统和水印提取和检测系统。为了模型描述方便，假设对象关系数据库为R＝（P，A1，A2，…An），其中P为数据库中的主键，即为不变属性，也表示为最大意义属性MSA，Ai（0＜i＜n＋1，i为自然数）为其他属性［11］，这里可以是数值型也可以是文本型。W为构造的K位水印，β为从关系数据库中构造提取水印序列的算法。那么应当有：

这里重点对数据库水印模型的脆弱水印构造算法进行研究。脆弱水印构造算法基本思想是采用改进的C4.5决策树算法对关系数据库属性Ai进行分划，根据分划后的分组，分组中对元组属性P经引入密钥η，结合水印W的位数K，和进行排序变换的MSA 属性P，进行hash（η，K，P）函数变换［12］进行排序，然后按照水印W逐步嵌入到各个元组的属性Ai中。其基本步骤为

Step1：

对除MSA 属性P外的属性Ai进行C4.5算法决策树构建，形成Ai：｛（a1，a2），（a3，a4），…｝的子树划分结构，针对Ai的属性数据类型不同分为三种划分方法：

1）对于离散型数据，直接按照较多离散点进行划分；

2）对于连续性数值数据，采用第3节中改进型分割最大阈值方法进行划分；

3）对于文本数据，通过length（）等函数进行转变为连续的数值数据，按方法1或2进行。

Step2：

对Ai划分的n个分组，各个分组采用hash（η，K，P）函数进行变换，根据冲突情况定义“0”，“1”，根据按水印W序列进行元组排序，并记录MSA 属性P的序列。

Step3：

各个分组中对各个属性进行水印W的嵌入，其中文本型数据按照4.1节方法嵌入，数值型数据按照4.2节方法嵌入并根据可嵌入位多少选择性进行校验位的嵌入。

Step4：

对于关系数据库R中的其他属性，按照step2，step3的方法，进行多组的W水印的嵌入。

在数据库水印检测中，通过存储的决策树分组方法对数据库元组数据分组，然后属性P的序列按照hash（η，K，P）变换，生成根据元组提取的水印序列W0，并与水印W进行比较得到篡改的元组，随后对除去篡改元组的其余元组数据属性按照水印嵌入算法进行逆向提取，通过大数选举［13］和与标准水印W比较，得到篡改的属性，从而确定数据库中篡改的元组和属性。

5.2 算法分析

关系数据库的脆弱水印算法的评价标准主要是：隐蔽性、安全性、敏感性、较大的水印容量和较低复杂度［14］。本算法通过在C4.5算法中引入模糊三角函数并根据水印信息量制定剪切子树原则，提高决策树构建灵活度和速度。并利用改进型C4.5算法对关系数据库属性进行分割构建决策树，通过对属性分割子树的MSA 属性进行hash变换嵌入水印并进行检测确定篡改元组，并在各属性中的可嵌入位嵌入水印信息和相关校验位进行检测定位篡改属性，分析优点在于：

1）敏感性高：通过分组对篡改元组列进行定位，并通过属性数据中的水印信息、纠错码等进行属性检测和定位，能够有效进行篡改定位。

2）适用范围广：本算法适用于数值型、文本型等不同数据类型属性水印算法构建，具有更加广泛适用性。

3）对原数据影响小：通过对原始数据添加空格和在最低有效位嵌入方法，对原始数据影响有限。

4）具有较高的隐蔽性、安全性和较大的水印容量、较低复杂度。

6 结语

本文提出了一种新的关系数据库脆弱水印模型，该模型是基于改进型C4.5决策树算法进行关系数据库脆弱水印构建，重点研究了脆弱水印构建算法实现，并定性分析了该算法优点。通过研究分析发现，对比传统的关系数据库水印算法，本文提出新的关系数据库脆弱水印算法能够有效检测数据库篡改的位置，具备适用性强、较好的隐蔽性、安全性和敏感性。

［1］胡斌.关系数据库数字水印技术的研究与应用［D］.长沙：中南大学图书馆，2007：23-25.

［2］Agraw R，Kieman J.Watermarking relation database［C］／／Proceeding of the 28th VLDB Conference.Hong Kong：Hong Kong University of Science＆Technology，2002：155-166.

［3］Radu S，Mikhail A，Suni P.Rights protection for relational data［C］／／Proceeding of the 2003 ACM SIGMOD International Conference on Management of Data.San Diego，California：ACM SIGMOD，2003：98-109.

［4］牛夏牧，赵亮，黄文军，等.利用数字水印技术实现数据库的版权保护［J］.电子学报，2003，31（12A）：2050-2054.

［5］Huiping Guo，Yingjiu Li，Anyi Liu，et al.A fragile watermark-ing scheme for detecting malicious modifications of database relations［J］.Information Sciences，2006，176（10）：1350-1378.

［6］张立忠，蒋楠，张洋.基于关系数据库的脆弱性水印算法研究［J］.计算机工程与应用，2008，44（29）：157-160.

［7］Quinlan J R.Induction of decision tree［J］.Machine learning，1986（1）：81-86.

［8］Quinlan J R.C4.5：Programs for machine learning［M］.San Mateo：Morgan Kaufmann Publishers Inc，1993：17-42.

［9］杨纶标，高英仪.模糊数学原理及应用［M］.广州：华南理工大学出版社，2001：50-55.

［10］陈惠明.一种具有纠错能力的半脆弱水印算法［J］.计算机技术与发展，2012，22（4）：242-245.

［11］张浩，黄敏，曹加恒.数据库水印中的标记算法［J］.计算机应用研究，2005：42-44.

［12］黄子龙，张政保，文家福，等.一种基于Hash函数的脆弱水印算法［J］.计算机技术与发展，2011，21（2）：151-154.

［13］蒙应杰，吴超，张文，等.关系数据库零水印注册方案的研究［J］.计算机工程，2007，33（2）：133-136.

［14］武荣，曹加恒，黄敏，等.关系数据库的数字水印新技术［J］.武汉大学学报，2005，51（5）：589-593.

［15］王娟.数字图像脆弱水印现状研究［J］.计算机与数字工程，2009（10）.