借鉴群体智能优化算法，提出了一种基于粒子群优化的细菌觅食算法（PSO-BF）的关系数据库水印算法。运用混沌映射对水印序列加密生成水印信号，采用单向hash函数加密关系数据库中元组的次序，利用PSO-BF优化算法解决将水印信号的嵌入过程抽象为约束条件下的优化问题，阈值解码和择多表决法用于提取水印信号，并通过混沌映射解密为表征版权的水印序列。实验表明，该算法对元组删除、修改和添加等攻击具有较强的鲁棒性和良好的不可见性。
1486· 计算机应用研究 第31卷 主键为r.P,其编号Ⅰ按照式(9)计算得到。 式屮,b’;表示经过阈值解码获得的二进制水印信号比特。 I,=ll(K,, I P, Ai mod( m) 设P表示误码率,P表示b;等于0的概率,P1表示b等 式中,H(·)表示单向hash数。 丁1的概率,b。表示嵌入的水印比特,b表示解码的水印比 因此,分组M,可以表示成多维分组向量M(i,p,d),其中特f(x)表示概率密度函数,T表示判决阈值。P由式(l4)计 是分组编号,P是第i个分组屮将要嵌入水印的属性,d是第i算得到 个分组中的元组。每个分组中嵌入1位水印信号比特b,具休 P(b=0,b=1)+P(b1=1,b2=0)= 的嵌入璐用式(10)表示。 P(ba=01b=1)P1+P(b=11b=0)P0= M"(i,P,1::)=M(i,p,1:1)+8(i,P,1:1;) (10) P(X<1b。=1)P1+P(x>r|b。=0)Po= 式中:M(,P,1:T;)表示分组数据;M"(i,P,1:T)表示嵌人b P,f(xlb. =1)d,+Po rfx b=0)dx (14) 后的分组数据;(i,p,1:7)表示对第讠个分组中第p个属性的 通过对P求驻点(即求一阶偏导数为零的点)获得T 修改量,7表小第个分组第p个属性中数值型数据的总个其中P对T的一阶偏导数研P,/如式(15)所示。 数。8(i,p,1:T)受到数据使用范围U(i,P,1:T)的约束,U(i, o7=P1可∫f(x1b.=1)dx/ f(x|b。=0)dx/a p,1:T)表示数据库元组中的候选属性在不影响使用的前提下 Pf(T1b。=1)-Puf、T|b。=0) (15) 能够寳忍的变化范围。根据水印信号和数据库的统计特性来 根据jn和jn的统计特性,得出f(x|b。=0)~N(u,Oo),f(x 选择修改量δ的最优值,水印的嵌入过程抽象为约束条件下的b.=1)~N(u1,1)和P=1-P1,式(15)推导为式(16)的形式 优化问题。通过以下步骤来计算该优化问题的隐函数6 P a)通过式(11)计算第i个分组屮第p个属性的参考点R √2 (11) Po 0 其中:c∈[0,1]是一个实数并且隶属于由数据库拥有者确定 的秘密参数集合y;:和:分别表示M"(,P,1:T2)的均值和 令∂P。7=0可获得式(17)所示的二次方程式,该方程式 标准差。 的根T包含T”。 b)初始化,令sm=0 十 c)对于M"(i,n,j,=1:7。如果W“(i,P,j≥R2,则 sum sum P d)按照式(12)定义隐函数。 J, (M (12) 满足式(18)的即为最优判决阈值r。 使用PO-BF优化算法来解决该优化问题,适应度函数选 FP(T) (18) 为式(12)定义的隐数。细菌的初始化位置为随机放置在T 维解空间δ(,p,1:T;)中,根据式(I)和(12)算出第个分组中 c)择多表决法。由于在嵌入时,每一位水印比特b,被重 第P个属性的参考点和隐函数;类似地,再算出第i个分组中所复嵌入到不同的数据分组中,相当于重复纠错码,可有效地降 有候选属性的隐函数,最终算出所有分组的隐函数。b,决定隐低误妈率。采用文献[7]描述的择多表决法对b进行解码,得 函数是最大化还是最小化,当b:=0时,"S)-B优化算法使隐函到密文水印W,需要通过混沌吹射解密为明文水印r 数最小化;当b1=1时, PSO-BF优化算法使隐函数最大化。与b d)混沌映射。与水印信号的生成过程一样,根据混沌初 对应的隐函数最小值或最大值分别存入jm8中,这些值收植密钥k)和水印序列的长度l,生成混沌随机序列L。通过 在阈值解码中用于计算解码参数。在U(i,p,1:T)约束条件下 异或运算将W解密为水印序列=L⊕W。 使隐函数最优(最大或最小)的修改量8为全局最优修改量δ,3实验仿真及结果分析 从而不影响嵌入水印后的数据库数据的正常使用。 2.4水印序列的提取 仿真实验所用到的数据库是关于某地区的地球化学测量 提取是嵌入的逆过程,通过已嵌入水印的数据库DB和数据,包含地理位晋、样本特征、矿物水质等参数的测量信息。 秘密参数集合γ提取出水印序列。本文设计的是鲁棒性盲水 该关系数据库出77212个元组构成,每个元组有287个属性 印算法,即使DB被修改有失真(用DB′表示),不依赖于原实验环境为 MATLAR7.10 始数据库,依然能够从DB′中提取出表征版权的水印序列。3:1主要参数设置 水印序列的提取可以划分为以下四个主要过程 选取二进制水印序列Ⅰ的长度l=128,数据库分组数目 a)hsh函数分组。与嵌入过程样,采用单向ha函数m1=11,.参数c=0.75。150B优化算法中的参数已经根据 将DB′分成m个互不重叠的分组W。输入为:DB',K2秘实验调整为最佳值,=2,Nn=2,N=40,Pa=0.25,S=10 钥,分组属性和分组数目m;输出为分组数据M′={M 3.2鲁棒性分析 b)阈值解码。水印信号的比特解码基于使误码率最小的 本文所提水印算法是在数据使用范围约束条件下修改关 判决阙值r。误码率是指对已嵌入的水印比特进行错误系数据库中数值型属性值,因此对于修改最不重要位的攻击或 解码的概率。计算′的隐函数J(H')并与T”比较,按照式操作具有鲁棒性。为了抵抗属性重排序攻击,在水印的嵌入和 (13)进行阈值解码。 提取过程屮选取分组属性和密钥K2为秘密参数,并采用单向 ifJ1(M;}≤T (13)hah函数对元组的次序进行加密处理。 if J,(Mi)>7 模拟子集删除(删除随机取的σ个元组)、」集修改(随 第5期 毛力,等:基于PSO-BF优化算法的关系数据庠水印算法 1487 机选取τ个元组,将τ/2个元组乘以L.01,另外τ/2个元组乘性,理论分析和实验结果证明该算法能够有效地解决数据库的 以0.99)和子集增加(复制随机选取的τ个元纽)攻击,仿頁结版权保护问题。如何将优化算法应用于非数值型数据的水印 果分别如表1~3所示。由于采用重复嵌入水印的方式,水印嵌入和提取,将是今后继续研究的方向。 算法对于上述攻击具有较强的鲁棒性。 参考文献 表1子集删除攻击所产生的水印提取 [1 MAO Li, FAN Yang-yu, WANG Hui-qin, et al. Fractal and neural 元组选取比例/% ≤40506070808590 水印提取率/% L0010010010 95 networks based watermark identification J| Multimedia Tools and 表2子集修改攻击所产生的水印提取率 Applications,2011,52(1):201-219 元组进取比例/%≤405060708090100 水印提取率/% 100100100100100100100 [2]周飞,赵怀勋.基于混沌的DCT城关系数据库水印算法[J,计算 表3子集增加攻击所产生的水印提取率 机应用研究,2012,29(2):786-78 元组选取比例% 100 水印取率/% 100100100100100100100 [3 PASSINO K M. Biomimicry of bacterial foraging for distributed opti 3.3不可见性分析 mization and control [J]. IEEE Control Systems Magazine, 2002 嵌入水印对数据库数据各属性列的整休影响如表4所小 22(3):5267 可以看出由丁嵌入水印所引入的误差较小,水印算法具有良好 [4 KENNEDY J, EBERHART R C. Particle swarm optimization [C]// 的不可见性。 表4嵌入水印对数据均值和方差的影响 Proc of IEEE International Conference on Neural Networks. Piseat- 进制比特水印序列展性名 均值改变 away: IEEE Service Center, 1995: 1942-1948 比例/% 比例/% 0和1的 0.699 [5 DAS S, BISWAS A, DASGUPTA S. Bacterial foraging optimization 个数均等 0.279 1.368 algorithm: theoretical foundations, analysis, and applications [C]// 1的数目多 0.200 0.582 Foundations of Cornpululali 0.798 e.Berlin: Springer, 2009 的数目多 0.022 1.703 3-55. 全1序列 [6 SHEHAB M, BERTINO E, GHAFOOR A. Watermarking relational 1.159 全0序列 0.041 0.897 databases using optimization based techniques [ J. IEEE Trans on 4结束语 Knowledge and data Engineering 2008, 20(1): 116-129 [7. SION R, ATALLAH M, PRABHAKAR S. Rights protection for rela 木文设计了一种基于PSO-BF优化算法的关系数据库水 印算法,利用混沌映射、单向hsh函数和密钥等信息安全技术 tional data J]. IEEE Trans on Knowledge and Data Enginee 提高算法的鲁棒性,利用FSO-BF优化算法提高算法的不可见 ring,2004,16(12):150%-1525 (上接第1483页)性混沌映射用于算术编码,提出了基十混沌映6] ZHOU Jian-jiang,AUoC. Comments on a novel compression and en 射的同步算术编码与加密方案。本算法解决了现存方案中编 cryption scheme using variable model arithmetic coding and coupled 码和加密独立分开的问题,将加密的过程嵌入编码的过程中 chaotic system[ J. IEEE Trans on Circuits System, 2008, 55 实现了同步编码与加密。整个加密过程十分复杂,提高了密文 (10):33683369 [7 MI BO, LIAO Xiao-feng, CHEN Yong. A novel chaotic encryption 的不可预测性,可以抵徊短明文攻击和蛮力搜索攻击。仿真结 果表明,产生的密钥其有充分的随机性且密钥与密文具有很强 scherne hased on arithme ie coling[ J]. Chaos Solitons Fractals 2008,38(5):1523-1531 的敏感性。 [8 LI Heng-jian, ZHANG Jia-shu. A secure and efficient entropy coding 参考文献: based on arithmetic coding[J. Communications in Nonlinear Sci [1 WEN liang-tao, KIM H, VILLASENOR J. Binary arithmetic coding with key ence and Numerical Simulation, 2009, 14(12): 4304-4318 based interval splitting J. IEEE Signal Process, 2006, 13(2): 69-72 [9 LUCA M B, SERBANSCL A, AZOU S, et al. A new compression [2 KIM H, WEN Jiang-tao, VILLASENOR J. Secure arithmetic coding nethod using a chaotic sy mbol ic approach[C]//Pror: of IEF.F. Com [JJ. IEEE Trans on Signal Process, 2007, 55 (5): 2263-2272 munications Conference 2004: 3-5 「3 GRANGETTO M, MACLI E, OLMO C. Multimedia selective encryp-「101王飞,王海春,泥沌加密技木在WSN中实现的分析「冂.计算机科 tion by means of randomized arithmetic coding[ J]. IEEE Trans on 学,2010,37(7A):136-138 Multimedia,2006,8(5):905917 [11 WONG K W, LIN Qiu-zhen, CHEN Jian-yong. Simultaneous arith- [4 JAKIMOSKI G, SUBBALAKSHMI K Cryptanalysis of some multime- oding and encryption using chaotic maps J]. IEEE Trans on dia encryption schemes[ J. IEEE Trans on Multimedia, 2008, 10 its and Systems,2008,57(2):146-150 (3):330-33 [12 RUKHIN A, SOTO J, NECHVATAL J, et al. A statistical test suite [5 BOSE R, PATHAK S. A novel compression and encryption scheme u- for random and pseudorandom number generators for cryptographic ap sing variable model arithmetic coding and coupled chaotic systeml J] plicationsEb/oL].(2010-04-08).http://csrc.nistgov/groups, IEEE Trans on Circuits System, 2006, 53(4): 848-857 ST/toolkit/rng/ documentation software. html