基于词性标记串统计特性的文本数字水印算法.doc

第4期戴祖旭等：基于词性标记串统计特性的文本数字水印算法113基于词性标记串统计特性的文本数字水印算法戴祖旭1, 2, 洪帆1, 崔国华1, 付敏2(1. 华中科技大学 计算机科学与技术学院, 湖北 武汉 430074；2. 武汉工程大学 理学院, 湖北 武汉 430074)摘 要：提出了一个将n元熵方程化为至多(n-1)个一元非线性方程求解的算法，证明了算法的正确性，给出了误差估计。利用词性标记串的统计特性设计了一种基于熵的文本数字水印方案，该方案通过改变词性标记串的概率分布使其熵与嵌入的水印一致。由于水印函数是一类实值函数，其值域仅受计算精度限制，可以大幅度提高水印容量。关键词：信息科学与系统科学；文本数字水印；熵；熵方程数值解；词性标记中图分类号：TP391 文献标识码：B 文章编号：1000-436X(2007)04-0108-08Watermarking text document based on statisticproperty of part of speech stringDAI Zu-xu1, 2, HONG Fan1, CUI Guo-hua1, FU Min2 (1. College of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China;2. College of Science, Wuhan Institute of Technology, Wuhan 430074, China)Abstract: An algorithm resolving nonlinear entropy equation with multivariable was described and proved firstly, then a new scheme where a text document is marked by accommodating probability distribution of certain Part of Speech strings to entropy constitutes the watermark was designed. Watermark function in the scheme values in a real number set dominated by computing precision, it is helpful to advances watermark capacity significantly.Key words: information & systems science; text digit watermarking; entropy; approximate root of entropy equation; part of speech tagging1 引言收稿日期：2006-09-30；修回日期：2007-01-15文本是一种广泛使用的数字媒体，利用数字水印技术保护文本文档知识产权及数据完整性的研究工作方兴未艾17。文献810将文本文档解释成一副黑白二值图像，通过上下移动文本行、左右移动文本行内的单词、改变字符高（宽）度等嵌入秘密消息，接收方将原始文档和水印文档进行对比即可检测出行距、字间距、字符特征的变化，从而读出隐藏消息。文献1113针对二值纯文本图像，在分析文本文档图像结构特点的基础上，将文本图像依内容进行分块，使每一图像子块只包含一个英文单词或一个字，然后提取该块的可嵌入水印的像素点，最后从中随机选一部分点嵌入水印信息。上述方案可以概括为基于文本格式的数字水印算法。由于文本文档缺乏图像、音频和视频等媒体所具有的人类视觉或听觉冗余特性，学者们越来越关注文本语法与语义层面的冗余特性研究，在此基础上提出了相应的文本水印算法。文献1421介绍了基于同义词、同音词、同形词替换等的文本水印算法，借助于同义词词典及词语习惯搭配词典的支持，这类算法将水印定义为词的函数，词是携带水印比特的实体，每个词携带水印的容量是其同义词的个数的对数；文献2225介绍了基于句子语法分析树的文本水印算法，充分利用句法分析器、句法树库等自然语言处理研究成果，这类算法将水印定义为句子语法分析树的函数，句子是携带水印比特的实体，每个句子携带水印的容量和与其语义等价的句型数量成正相关。上述水印算法可以概括为基于文本内容的数字水印算法。总的说来，基于文本格式和文本内容的水印技术共同缺点是水印函数是一种对有限状态的编码算法，函数值域为有限集，水印容量难以提高，另外，基于文本格式的水印算法易受文本再生攻击，基于文本内容的水印算法易受同义词替换、句子、段落移位攻击。自然语言语句是词的序列，处于序列中的词具有特定的词性，而词性通常是有限的，比如，汉语的词性有31种26，借助于计算语言学关于自然语言词法分析（比如分词与词性标注）研究成果27，自然语言语句可以变换为词性标记串，而且，由于受到语法的限制，句子的结构也具有稳定性，虽然一篇文档中句子重复出现的现象较少，但词性标记串重复出现的现象却较普遍，而词性标记串本质上就是句型，是句子语法结构的抽象。基于此，本文将词性标记串的统计特性与水印关联，提出了一种基于词性标记串统计特性的文本水印算法，基本思路是对文本做词性标记处理，统计词性标记串的频数，选择部分标记串连同其频数构造一个完备概率空间，通过修改文本改变标记串的概率分布使其信息熵与水印一致。本算法能抵抗同义词替换、句子移位等攻击，而且水印函数是一类实值函数，其值域仅受计算精度限制，可以大幅度提高水印容量，理论上可以无限。本文余下部分组织如下：第2节在介绍信息熵的定义及性质的基础上给出了信息熵方程求解算法、算法收敛性证明以及误差估计；第3节介绍了水印嵌入与提取算法；第4节对算法安全性进行了讨论；第5节给出了一个实验结果；第6节是结束语。2 信息熵方程求解算法2.1 信息熵定义及性质定义28 设离散有限随机变量 ，X的概率向量为，其中，。则X的信息熵定义为=(1)性质128 0，=0当且仅当存在i使pi=1，=ln(n)当且仅当对所有i有pi=。性质228 设P=(, , , , , , ) 是概率向量，pn=，则 =+(2)2.2 信息熵方程求解算法本水印算法实现过程中要解决信息熵方程的求解问题，即通过n元非线性不确定方程组(3)求出它的一组解p1, p2, pn，其中常数c是与水印相关的一个实数。对于式(3)，当=0时，解p1,p2,pn中有一个为1，其余都为0；当=ln(n)时，有惟一解；而当时，方程组可能有无数多解，我们利用2.1节的性质2将这个n元非线性不确定方程组转变为至多（n1）个一元非线性方程来求解。引理 设，则方程在区间上有惟一解。证明 函数在(0,1)上连续，而且令0，可得。又因为对有，对有，因此在处有极大值。再由可知 。另一方面，由我们可以补充定义，因此函数在区间上单调增加且在端点处函数值不同号，方程有惟一解。算法一：信息熵方程求解算法。输入：概率向量维数，信息熵c，且满足。输出：概率向量为，且满足=c。1. ；2. If c=0 Then output = ；Else if c=ln(n) output =；Return.3. For i=1 to (n2) do1) ；2) ；3) 解方程求pi；4. 解方程求；5. For i=1 to (n1) do；6. .7. Output 定理1 设，是算法一的输出，则H(P)=c。证明 先证明方程（）有解。因为，所以，所以,所以。一般的，由数学归纳法我们有且，。从而，由引理可知，方程（）有解。另外，由可知方程 亦有解。设算法求得的一组解为，记为，反复使用信息熵性质2可得=+而 因此有。证毕。由于 仍然是非线性方程，因此只能求得近似解，信息熵方程求解算法误差的主要来源是对（1）个方程求根时的误差累积。定理2 设pi是方程的近似解，且（）， 是算法一的输出，则= 。证明 同定理1的推导，我们有 .所以= 3 水印嵌入与提取3.1 水印嵌入算法1) 设水印w是一个定长的二进制串，将其映射为，且（）；2) 利用算法一求解熵式（3），其中c=设解向量为p=；3) 随机选择词性标记串集合S= ，设mi表示si在原文档中出现的频数。4) 如果概率向量仅有一个分量为1，则密钥S=退化为S=，此时可以随机修改的频数以嵌入水印；否则，令 ，其中是正整数，且的最大公约数为。5) 利用除法定理求di和ri，其中di和ri满足(4)和(5)这里表示向上取整，下同。式(4)主要用于控制对文本句子的修改数量。6) 修改原文档29使si的频数为ri ；S=和D=是密钥。3.2 水印提取算法1) 根据密钥S=分别统计标记串si在原始文档和水印文档中的频数mi与ri， ；2) 若S=s1，则g(w)=0，由逆变换求得水印；否则，利用mi、ri与密钥di由式(4)计算，3) 令，计算g(w)=，再由逆变换求得水印4 水印安全性本文提出的非盲水印方案是基于文本统计特性的，因此能抵抗同义词替换、句子移位等攻击，下面重点讨论敌手去除水印操作的计算复杂度。如果敌手要完成去除水印操作，他必须知道密钥S=和在原文档中相应的频数mi ()。设K=| 是侯选词性标记串集合，则S=,(n1)是K的非空子集，共有(1) 种不同的选择。 对每个子集S=, 敌手能从水印文档中统计出频数（），从而根据（4）式推断出2 ， (6)因此修改,频数的方案有种。令m=，由加法原理可知敌手去除水印的计算复杂度约为5 实验结果我们以杜鹏程的长篇小说保卫延安为载体文本，该文本约有37 031个自然语言语句，使用了北京大学计算语言学研究所开发的汉语词语切分与词性标记软件进行标记，得到词性标记串的统计特性如表1所示。表1词性标记串频数统计频数分段151050100累积频数16 3975372294621选择，其频数分别为m1=31，m2=31，m3=22。假设水印为“WIT”，所对应的ASCII码值为119、105、116，转换为二进制小数，就是0.01110111 01101001 01110100，再转换为十进制小数，得g(w)=0.466452836990356。解熵方程得p1=0.8539310713856974, p2=0.1299972763380719, p3=0.0160716522762308,8539310713856974, 1299972763380719, 160716522762308,275461635930869, 41934605270345,7305296489195,35, 24, 18。6 结束语本文提出的求解n元非线性熵方程的算法可以通过调整参数取值求出方程不同的解。基于词性标记串统计特性的文本水印方案对于同义词替换、句子移位等文本操作具有较强的鲁棒性，而且水印容量主要由计算精度确定，理论上可以无限。参考文献：1尹浩,林闯,邱锋.数字水印技术综述J.计算机研究与发展,2005,42(7):1093-1099.YIN H, LIN C, QIU F. A survey of digital watermarkingJ. Journal of Computer Research and Development, 2005,42(7):1093-1099.2钮心忻,杨义先,吴志军.信息隐藏理论与关键技术研究J.电信科学,2004,20(12):28-30.NIU X X, YANG Y X, WU Z J. Study on the basic theory and technology of information hidingJ. Journal of Telecommunications Science,2004,20(12):28-30.3周继军,杨著,钮心忻等. 文本信息隐藏检测算法研究J.通信学报,2004,25(12):97-101.ZHOU J J, YANG Z, NIU X X, et al. Research on the detecting algorithm of text document information hidingJ. Journal of Communications, 2004,25(12):97-101.4李庆诚,李瑷珲.网络出版中版权保护技术-文本数字水印的研究J.计算机工程与应用,2004, (18):163-211.LI Q C, LI A H. Study on textual digital watermarking for copyright protection in e-publishJ.Computer Engineering and Applications, 2004, (18):163-211.5吴树峰,黄刘生等.信息隐藏技术及其攻击方法J.计算机科学,2003.30(2):92-96.WU S F, HUANG L S, et al. Information hiding and countermeasuresJ. Computer Science, 2003,30(2):92-96.6钮心忻,杨义先.文本伪装算法研究J.电子学报,2003,31(3):402-405.NIU X X, YANG Y X. Research on text steganographyJ. Acta Electronic Sinic, 2003,31(3):402-405.7陈明奇,钮心忻,杨义先.数字水印的研究进展和应用J.通信学报.2001,22(5):71-79.CHEN M Q, NIU X X, YANG Y X. The research developments and applications of digital watermarkingJ. Journal of Communications, 2001,22(5):71-79.8BRASSIL J T, LOW S, MAXEMCHUN F K. Copyright protection for the electronic distribution of text documentsJ. Proceedings of the IEEE, 1999,87(7):1181-1196.9LOW S H, MAXEMCHUK N F, LAPONE A M. Document identification for copyright protection using centroid detectionJ. IEEE Trans on Communications, 1998,46(3):372-383.10黄华, 齐春, 李俊.一种新的文本数字水印标记策略和检测方法J.西安交通大学学报,2002, 36(2):165-181.HUANG H, QI C, LI J. New watermarking scheme and centroid detecting method for text documentsJ.Journal of XiAn Jiao Tong University, 2002,36(2):165-181.11张小华,刘芳,焦李成.一种有效的文档水印技术J.通信学报,2003,24(5):21-28.ZHANG X H, LIU F, JIAO L C. An effective document watermarking techniqueJ. Journal of Communications, 2003,24(5):21-28.12朱从旭,陈志刚.一种灵敏的文本图像认证混沌脆弱水印技术J.小型微型计算机系统,2006, 27(1):151-154.ZHU C X, CHEN Z G. Sensitive chaotic fragile watermarking technique for binary images verificationJ. Mini-Micro Systems, 2006, 27(1):151-154.13张小华,刘芳,焦李成.一种基于外边缘的文档水印技术J.系统工程与电子技术,2003,25(5):612-616.ZHANG X H, LIU F, JIAO L C. A new effective document watermarking technique based on outside edgesJ. Systems Engineering and Electronics, 2003,25(5):612-616.14肖湘蓉,孙星明.基于内容的英文文本数字水印算法设计与实现J.计算机工程,2005,31(22):29-118.XIAO X R, SUN X M. Design and implementation of content-based english text watermarking algorithmJ.Computer Engineering, 2005, 31(22):29-118.15刘东,周明天.一种文本数字水印系统解决方案J.计算机应用,2006,26(1):84-86.LIU D, ZHOU M T. Solution for text digital watermarking systemJ.Computer Applications, 2006,26(1):84-86.16杨榆,徐迎晖,钮心忻等.基于语义的文本隐藏方法J.计算机系统应用,2006,(3):91-94.YANG Y, XU Y H, NIU X X et al. Text steganography based on semanticsJ. Computer System Applications, 2006,(3):91-94.17赵敏之,孙星明,向华政.基于虚词变化的自然语言信息隐藏算法研究J.计算机工程与应用,2006(3): 158-160.ZHAO M Z, SUN X M, XIANG H Z. Research on the chinese text steganography based on the modification of the empty wordJ. Computer Engineering and Applications, 2006,(3): 158-160.18眭新光,罗慧.一种安全的基于文本的信息隐藏技术J.计算机工程,2004,30(19):104-191.SUI X G, LUO H. A secure steganography method based on textJ. Computer Engineering, 2004,30(19):104-191.19CHIANG Y L, CHANG L P, HSIEH W T. Natural language watermarking using semantic substitution for chinese textA. IWDW 2003C. Berlin: Springer,2004. 129-140.20KANKANHALLI M S, HAU K F. Watermarking of electronic text documentsJElectronic Commerce Research,2002,(2):169-187.21BOLSHAKOV I AA method of linguistic steganography based on collocationlly-verified synonymyA. Information Hiding:6th International WorkshopC. Toronto: Springer,2004.180-191.22SUN X M, ASIIMWE A J. Noun-Verb based technique of text watermarking using recursive decent semantic Net parsersA. ICNC 2005C. Berlin:Springer, 2005. 968-971.23LIU Y L, SUN X M, WU Y. A natural language watermarking based on chinese syntaxA. ICNC 2005C. Berlin: Springer,2005.958-961.24ATALLAH M J, RASKIN V, CROGAN M, et al. Natural language watermarking: design, analysis, and a proof-of -concept implementationA. Information HidingC. Berlin:Springer, 2001.185-199.25ATALLAH M J, RASKIN V, HEMPELEMANN C F, et al. N