基于小波变换的关系数据库水印算法

基于小波变换的关系数据库水印算法1陈明刚,孙星明,肖湘蓉（湖南大学计算机与通信学院，湖南长沙，410082）摘要：针对关系数据库的特性，提出一种基于小波变换的鲁棒盲水印算法。嵌入时先构造主键的最小非负剩余系对数据分组，通过设置各组数据小波变换后“高/低频数据对”奇偶性的异同以嵌入信息。提取时统计相应位置的数据对奇偶性异同频度，依据阀值判断而获取嵌入的水印。试验结果表明水印提取的准确度较高，算法具有较好的隐蔽性、鲁棒性，在数据丢失60％的情况下，仍能较完整的提取出水印信息。关键词：关系数据库水印;小波变换;鲁棒;阀值中图分类号：PT309.2文献标识码：A文章编号：ARelationalDatabaseWatermarkingAlgorithmBasedonWaveletTransformationCHENMing-Gang,SUNXing-Ming,XIAOXiang-Rong（SchoolofComputer&CommunicationHunanUniversity,ChangshaHunan,410082,China.Contact:ChenMing-Gang,E-mail:[e-mail]）Abstract:Aimedatthecharacteristicsofrelationaldatabase,anovelandrobustwatermarkingalgorithmbasedonwavelettransformationisproposedinthispaper.Thealgorithmfirstlygroupsthedatabyconstructingacompleteresidualsystemwhichisbasedonthehashvaluesoftheprimarykeys,andthenapplieswavelettransformationtothedataofeachgroupandembedsonebitineachgroupbysettingparitysimilarityordifferenceinapairofhighandlowfrequencydata.Whenthewatermarkisextracted,themarkisretrievedfromgroupsbycountingthefrequenciesofsimilaritiesanddifferencesofparitypairsatcorrespondingpositions,andcomparingwiththethresholds.Experimentshaveshownthatthealgorithmhasarelativelyhighaccuracy,apreferableimperceptibilityandagoodrobustness,whichallowsupto60%lossofdatawhilealmostintegralmarkscanstillbeextracted.Keywords:Relationaldatabasewatermarking,Wavelettransformation,Robust,Threshold1引言数字水印技术是20世纪90年代出现的一门崭新的技术，通过在数字产品中嵌入可感知或不可感知的信息来证明数字产品的所有权或检验数字内容的原始性[1]。数字水印是用于解决知识产权保护问题、最具有潜力的多学科交叉技术，自93年提出以来发展十分迅速，已经受到国际学术界和企业界的高度关注。水印按所负载的载体数据，可以划分为图像水印、音频水印、视频水印、文本水印、软件水印、数据库水印、协议水印以及用于三维网格模型的网格水印等。目前，图像、音频、视频和文本等多媒体信息数字水印技术的研究较多，取得了很好的成果[2]。由于关系数据的特殊性，对关系数据库嵌入水收稿日期：2007年5月30日；作者简介：陈明刚(1980-)，男，湖南湘西人，硕士生；孙星明(1963-)，男，湖南益阳人，博士，教授，博导；肖湘蓉(1971-)，女，博士生，讲师；基金项目：国家973项目(2006CB303000)，国家自然科学基金(编号：60573045)，高校博士点基金（编号：20050532007）。印有一定难度[3]，研究者较少，但同时关系数据库水印有许多具有较高理论意义和应用价值的问题值得深入地研究。现有国外的研究成果中，R.Agrawal[4][5]的方法以主键的HASH值作为定位标志，对数值型属性的LSB位嵌入，按一定规则将特定位置的数值置为1或0。算法基于数据的概率特性，嵌入到关系数据中的编码没有特定含义，仅与数值本身有关，很难直接通过水印内容证明版权的所有者。R.Sion[6][7][8][9]等提出针对数值型属性操作的方法，在可用性规则限定下修改数据的分布特性，成组嵌入水印信息。对数值的改变虽然在允许误差范围内，但改变了数据的分布特性，隐蔽性能不够好，嵌入过程的计算量较大；文献[8]在提取水印时还需要使用嵌入图（Embeddingmap），没有实现“全盲”提取。文献[9]利用主键定位对任意类型属性实现嵌入，由水印码元计算某个属性的取值，对原始值进行替换以嵌入，虽没有改变数据的分布特性，但属性本身的值发生了变化，可能影响数据正常使用。Y.Li提出利用索引嵌入水印的方法[10][11]，通过改变关系数据各“索引对”之间的顺序嵌入水印。水印的嵌入不改变数据的物理位置，也没有改变关系数据本身的值，数据没有失真，几乎不影响数据的使用。但由于索引是关系数据内容之外的附加信息，若对关系表作重新索引或删除索引，则水印信息完全丢失，鲁棒性不够好。国内对数据库水印研究比较少，主要有：牛夏牧教授在文献[4-9]的算法上作了改进[14]，通过主键对数据分组，嵌入了有实际意义的信息。张勇博士，采用李德毅教授的云模型思想，将图像信息转换成水印云滴嵌入到关系数据中[12][13]，提取时将原始版权图像与云滴进行相似性比较，属于非盲水印。张勇博士提出的可逆关系数据水印方法[15]，取关系数据末尾部分的差值，再利用小波变换方法展开，嵌入水印信息。本文提出一种基于小波变换的关系数据库水印，分别对水印信息和分组关系数据进行小波变换，再依据各组“高/低频数据对”的奇偶性异同嵌入水印信息，水印的隐蔽性、鲁棒性较好。提取时不需要原始数据，通过统计嵌入位置数据对的奇偶性异同数，即可获得嵌入的水印信息。2算法与实现基于小波变换的关系数据库水印算法的基本思想是：先通过构造主键哈希值的最小非负完全剩余系对关系数据分组，每组将用于嵌入一位水印信息；再对组内数值型数据按设定的规则排序后作小波变换，通过改变“高/低频数据对”LSB位的奇偶性嵌入水印码，将信息分散到多个数据中。提取也是分两步进行，先重新分组找到水印的嵌入位置，再逐组统计各数据对奇偶性异同的频度，由阈值判断获取嵌入的水印信息。2.1符号定义水印信息码W长度为|W|，各码元依次是w1,w2,…,wm(wi∈{0,1}，ｍ=|W|)；在待嵌关系表R(P,D1,D2,…,Ds)中，P为主关键字，Dj(j=1,…,s)为R中可用于水印嵌入的数值型属性。R中共包含n个元组：r1,r2,…,rn，各元组的主键为ri.P(i=1,…,n)，元组中的数值属性为ri.D1,ri.D2,…,ri.Ds。e是一个正整数，对任意整数a，令Ca={c|c∈Z,a≡cmode}，Ca叫做模e的a的剩余类；剩余类中的数据叫做该类的剩余。0,1,…,e-1是模e的一个完全剩余系，叫做模e的最小非负完全剩余系。小波变换是一种多层分解数据的工具，可以用较小的空间表示对象在多层次上的特征。实验中为增强水印的鲁棒性，且使水印信息更分散，对关系数据和待嵌水印图像分别进行小波分解。（1）关系数据：对每个剩余类组进行一维小波分解，每组都分为高频和低频两部分，令高频数据为H，低频数据为L，组内数据数目为t。则在各组中的高频数据可依次表示为high1,…,hight/2，低频数据为low1,…,lowt/2。水印信息表示规则（i=1…t/2）：水印码’1’：高/低频LSB位奇偶性相同（即(highi.LSb-lowi.LSB)%2=0）；水印码’0’：高/低频LSB位奇偶性不同（即(highi.LSB-lowi.LSB)%20）；（2）水印图像：对原始水印图像进行二维小波分解后，因为低频部分集中了数据的大部分能量，将低频部分嵌入到关系数据中，可降低嵌入的信息量。2.2数据分组通过构造主键哈希值模e（调整因子）的最小非负完全剩余系，将全部数据分为e组，每个剩余类Ci（i=0,…,e-1）是一组。其中前|W|个剩余类C0,C1,…C|w|-1中的剩余，所在元组都满足条件“主键哈希值模e等于水印序号z”，即Hash(ri.P,K1)mode＝z（i=1,…,n；z=0,…,|W|-1；e≥z）。构造剩余类组实现对数据分组（每一个分组中嵌入一位水印信息），先根据元组主键Hash值判断，再将相关信息保存二维数组key[u,v]和value[u,v]中，分别记录各组数据所在元组的主键和属性值；number[u]记录组中元素个数；下标u=1,…,|W|表示水印组编号；v=1,…,t表示数据编号。分组过程见算法1。调整因子e决定最大分组数，也就是可嵌入的水印容量，e的取值可根据具体嵌入的水印信息和关系数据量进行设置。按照数据分布特性，各剩余类组中剩余的数目t大致相当，但不完全相等，即对不同的剩余类组t值不固定，当有e个剩余类时，ent/。由分组算法知，在分组过程中位置z是不断变化的（0≤z≤|W|-1），对不同的水印码元，各剩余类中的剩余数并不相同，数目也不固定。因此在算法公开的情况下，如果不知道密钥及调整因子e，攻击者很难获取到分组数据，对水印数据定位，从而增强了水印的安全性能。2.3水印嵌入由于图像具有经历少量干扰（误码/破坏）时总体可识别的特性，因此嵌入时以图像作为水印信息。为方便操作和降低时间复杂度，在不影响视觉效果的前提下先对水印信息先作预处理，即对图像作二值化处理。将原始的水印灰度图像变为黑白图像，处理时定义灰度值大于125的像素为’1’，其余为白色像素’0’。预处理后的图像经过二维小波分解，低频部分表现了主要轮廓，高频部分的细节可以忽略，因此嵌入低频部分即可包含图像大部分能量，从而达到版权标记的目的。为使水印信息更分散，增强算法的鲁棒性和隐蔽性，把各分组数据进行小波变换再作嵌入。嵌入时通过对高频数据的LSB位作“加/减1”操作，使各数据对满足水印信息表示规则而嵌入编码’0’或’1’。具体实现过程见算法2。由于嵌入是在小波变换后实现，数据的修改在频域中，水印信息很分散，所以嵌入水印对数据的算法1：GroupingInput：关系数据表R，待嵌信息E，调整因子e，密钥K1Output：属性值value，元组的主键key，组中元素数目number1）foreachtupleri∈R//逐个处理表中的记录2）u=Hash(ri.P,K1)%e//元组主键哈希值对p取模3）ifu|E|step4//|E|是待嵌信息的长度elsestep7//只保存前|E|个剩余类组4）key[u][number[u]]=ri.P//保存元组的主键值5）value[u][number[u]]=ri.D//记录属性值6）number[u]=number[u]+17）step1:nexttuple//直到处理完全部数据算法2：EmbeddingInput：关系数据表R，水印信息W，调整因子e，密钥K1Output：嵌入了水印W的关系数据表R’1）E=E(W)//对水印信息进行预处理2）Grouping(R,E,e,K1)//数据分组，见算法13）for(i=0;i|E|;i++)//|E|是待嵌信息E的长度4）s=number[i]/2//s是低、高频的分界5）sort（key[i],value[i]）//根据主键对分组