大规模用户环境下数字指纹的快速检测方法

摘要

大规模用户环境下数字指纹的快速检测方法，具体为：构建数字指纹哈希表，在数字指纹哈希表中对从作品中提取的指纹进行匹配，匹配得到与提取指纹相似的指纹近邻集，指纹近邻集中与提取指纹相差最小的数字指纹对应的用户为非法用户。本发明所采用的基于LSH的快速近邻搜索方法，能快速响应数字指纹系统查询请求，能满足系统实时查询的要求。尤其在用户量巨大时，本算法在时间效率上相比现有的检测算法有巨大的优势。

权利要求

1.大规模用户环境下数字指纹的快速检测方法，具体为：

在数字作品分发阶段，根据用户信息及购买过程的描述信息生成数字指纹，对数字指纹进行哈希，将生成的哈希码存入数字指纹哈希表中；

在跟踪体制中，从作品中提取数字指纹，按照所述数字作品分发阶段中的哈希方法为其生成哈希码，并与数字指纹哈希表中的哈希码进行匹配，得到与提取数字指纹相似的指纹近邻集，指纹近邻集中与提取数字指纹相差最小的数字指纹对应的用户为非法用户。

2.根据权利要求1所述的大规模用户环境下数字指纹的快速检测方法，其特征在于，所述数字指纹哈希表包含一个以上的哈希桶，哈希桶内使用一个以上相互独立的哈希函数，任意两个哈希桶的哈希函数不全相同。

3.根据权利要求1或2所述的大规模用户环境下数字指纹的快速检测方法，其特征在于，对数字指纹进行归一化处理后再构建数字指纹哈希表，对提取的指纹按相同方式归一化处理后再进行匹配。

说明书

大规模用户环境下数字指纹的快速检测方法

技术领域

[0001] 本发明属于信息安全技术领域，具体涉及一种大规模用户环境下数字指纹的快速检测方法。

背景技术

[0002] 随着计算机网络和多媒体技术的飞速发展，互联网上的数字媒体应用正在呈爆炸式增加。越来越多的多媒体作品(图像、文本、音频、视频等)以电子的形式传播，使得这些作品的存储、复制与传播变得非常方便快捷。数字产品逐步融入消费者的生活，这给广大创作者和发行商带来了新机遇，但同时也非常容易造成数字作品的非法拷贝和非法传播。

[0003] 同时随着我国数字电视的推广和普及，数字化的音视频播放录制设备走进千家万户，数字电视网上的非法复制和侵权行为将更加严重。因此，如何通过对非法分发者的身份进行确认，并对其进行控告和惩戒，进而形成一种打击非法侵权的威慑力量，已经成为版权保护亟待解决的问题。数字产品版权保护问题，已成为数字世界的一个非常重要和紧迫的议题，是阻碍信息数字化发展的主要障碍。如何防止数字产品被非法复制与传播，保护版权所有者的合法权益，已经成为进入信息化社会急需解决的问题。

[0004] 这些问题的解决要求在版权保护中实施跟踪机制，也就是能够对数字作品拷贝的销售、使用、流通和存储行为予以监督和控制。许多加密技术和数字版权管理(DRM)框架采用端到端的加密来保护数字媒体的版权。但一旦加密媒体数据被解密后，这种保护机制就不再有效了。数字水印方法则可用于对解密后的多媒体内容提供进一步的保护。作为数字水印的一个分支，数字指纹就是解决这类问题的一种版权跟踪技术，是一种有效且最具潜力的方法，已成为研究的热点。数字指纹是将不同的标志性识别代码——指纹，利用数字水印技术嵌入到数字媒体中，然后将嵌有指纹的数字媒体分发给用户。发行商发现盗版行为后，就能通过提取盗版产品中的指纹，确定非法复制的来源，对盗版者进行起诉，从而起到版权保护和威慑的作用。目前，数字指纹领域的研究主要集中在设计抗共谋攻击的数字指纹编码方案，而忽视了数字指纹的检测问题，特别是当用户量急剧增大时数字指纹的快速检测问题。目前国内外还未出现关于数字指纹的快速检测文章，但是信息检索领域和数据挖掘领域关于快速相似性检索(fast similarity search)和最近邻搜索(nearest-neighbor retrieve)的研究非常火热。如何把这些相关技术应用于解决数字指纹的快速检测问题，国内外也少有专家、学者论及这个问题。

[0005] 现阶段数字指纹的检测方法还是采用数字水印的检测方法，主要有两种：一种是线性相关的方法，这种方法类似于通信中的匹配滤波；一种归一化相关性检测方法，即计算两个向量之间夹角的余弦值。虽然熟悉的线性相关的方法虽然很有用并且计算简单，但也有明显的缺点。它最大的问题在于检测值很大程度上依赖于从作品中提取的向量幅度。这表明该检测方法对于一些简单的处理，如图像的亮度或降低音乐的音量，不具备鲁棒性。这一点不能满足数字指纹实际应用要求，已经被归一化相关性方法所取代。归一化相关的计算方法如下：

[0006]

[0007] 其中z表示提取出的指纹序列，ui表示第i条原始的指纹序列，L表示所有的数字指纹的数目，在阀值范围内具有最大相关值的TN(i)对应的用户即非法使用过作品的用户(非法使用指对作品进行信息处理、几何攻击或共谋攻击等处理后非法传播)：

[0008]

[0009] 从式(1)可以看出，归一化相关性算法的时间复杂度与用户量L和指纹码的维度呈线性关系。随着网络的蓬勃发展，网络用户量急剧增多和网络用户对数字媒体的需求量增大，数据指纹的规模也必然随之增大。实际上，随着用户量的增加，及抗共谋性能的要求的提高，数字指纹的码长不可避免地会随之增长，这在很大程度上降低数字指纹的追踪效率。同时进行归一化相关性时，需将大量的原始数字指纹读入内存中，这对计算机的性能也是一个极大的挑战。

[0010] 现有的数字指纹系统中，绝大部分的数字指纹的码长都达到了几百位甚至几千位的实数。归一化相关性检测的方法与系统中数字指纹的总数及数字指纹的维度呈线性关系。数字指纹的维度越长，用户量越大，归一化相关性检测的效率就会越低下。虽然归一化相关性检测的准确非常高，但是追踪出正确非法用户的时间远远超出了用户能忍受的程度，所以必须在尽量不降低准确率的情况，找出一种快速的匹配算法。

发明内容

[0011] 本发明的目的在于提供一种基于局部敏感性哈希(简称LSH，下同)的大规模用户环境下数字指纹快速检测方法，检测速度快，并具有较高的准确率。

[0012] 大规模用户环境下数字指纹的快速检测方法，具体为：构建数字指纹哈希表，将从作品中提取的指纹在数字指纹哈希表中进行匹配，得到与提取指纹相似的指纹近邻集，指纹近邻集中与提取指纹相差最小的数字指纹对应的用户为非法用户。

[0013] 作为优选方式，所述数字指纹哈希表包含一个以上的哈希桶，哈希桶内使用一个以上相互独立的哈希函数，任意两个哈希桶的哈希函数不全相同。

[0014] 作为优选方式，对数字指纹进行归一化处理后再构建数字指纹哈希表，对提取的指纹按相同方式归一化处理后再进行匹配。

[0015] 本发明的技术效果体现在：根据指纹编码产生的数字指纹之间的相似性，将利用哈希进行快速近邻搜索的思想引入数字指纹的检测中。本发明所采用的基于LSH的快速近邻搜索方法，能快速响应数字指纹系统查询请求，能满足系统实时查询的要求。尤其在用户量巨大时，本算法在时间效率上相比现有的检测算法有巨大的优势。该方法对高维数据进行哈希，把原始数据转化到低维的空间，对高维数据进行降维。新转化的码字是高压缩的，因此可以很容易地载入到内存中，并且新的码字长度较短，可以进行快速的计算。

附图说明

[0016] 图1为本发明数字指纹检测原理图。

[0017] 图2为数字指纹哈希表的建立流程图。

[0018] 图3为数字指纹检测具体流程图。

[0019] 图4为测试图像，其中4(a)图为“莉娜”图像；4(b)图为“辣椒”图像；4(c)图为“渔船”图像；4(d)图为“猩猩”图像；4(e)为“桥”；4(f)为“飞机”；4(g)为“夫妻”；4(h)为“手表”。

[0020] 图5为本发明基于LSH检测方法与归一化相关检测方法的运行时间对比图，其中图5(a)为原始的归一化相关性检测公式与本发明基于LSH检测方法运行时间的对比；图5(b)为对相关性检测公式优化后与本发明基于LSH检测方法的运行时间的对比。

[0021] 图6为本发明基于LSH检测方法抗信号处理攻击的能力，6(a)为嵌入指纹的图像加噪声(NOISE)后提取出的指纹集的检测效果图；6(b)为嵌入指纹的图像JPEG压缩(JPEG)后图片提取出的指纹集检测效果图；6(c)为对原始指纹上加高斯噪声生成的指纹集的检测效果图。

[0022] 图7为本发明基于LSH检测方法抗几何攻击的能力示意图，7(a)为缩放(RESC)攻击检测效果图；7(b)为旋转(ROT)攻击检测效果图；7(c)为旋转加裁剪(ROTCROP)攻击检测效果图；7(d)为旋转加拉伸(ROTSCALE)攻击检测效果图。

[0023] 图8为本发明基于LSH方法抗共谋攻击的能力示意图。

具体实施方式

[0024] 下面结合附图和具体实施方式对本发明做进一步详细说明。

[0025] 本发明中的数字指纹是指通过指纹编码生成的一些标志性的识别码，而不是被动监管技术中所采用的媒体指纹，它与用户和该用户购买的媒体作品对应，应用于主动追踪非法用户。

[0026] 如图1所示，本发明所采用的数字指纹体制与通用的数字指纹体一样，包括两部分：一是用于向拷贝中嵌入指纹并对带指纹拷贝进行分发的拷贝分发体制；另一部分是实现对非法分发者进行跟踪并审判的跟踪体制。其中用户j的信息由用户提供或由其与发行商(或信任的第三方)通过一系列交互后生成。它通常包括用户的身份信息及该次购买过程的描述信息。有关用户j的信息将被按照一定规则进行编码并嵌入到发行商要出售的原拷贝中。用户直接得到带有其指纹的拷贝或由发行商将带有指纹的拷贝发放给用户，同时发行商和用户得到有关交易记录。不诚实的用户可能会直接分发他所得到的拷贝或者对拷贝进行处理后再行分发，也可能与其他用户联合进行共谋攻击后获得新的拷贝伪本后分发。无论是哪种情况，非法分发的拷贝中都会留下参与非法活动用户的指纹信息。一旦发行商发现了非法拷贝，他将运用相应的指纹提取及指纹解码技术，并运用跟踪算法跟踪非法分发者。

[0027] 而本发明所采用的数字指纹体制在通用的数字指纹体制上进行了修改。对数字指纹进行哈希，存储哈希后的码字。所采用的哈希方法可以有很多种选择，如学习哈希、光谱哈希、语义哈希等。本发明中采用了经典的局部敏感性哈希(LSH)方法。使用哈希的方法，虽然增加了存储哈希表的空间，并且可能带来检测的正确率的降低，但是极大的提升了我们的检测速度，减少了作品发行商查询自己所拥有的作品是否被非法使用时的等待时间。

[0028] 本发明中所采用的LSH方法来自于Mayur Datar等于2004年9月在纽约 举 办 的SoGG 会 议 上 提 出 的“Locality-Sensitive Hashing Scheme Based on p-StableDistributions”方法。作者在文章中提出，LSH的方法对于满足确定边界条件的数据可以在O(logn)时间内找到精确的近邻，其中n为数据集的大小。该算法的核心思想是用一些哈希函数来映射数据集中的数据点，以确保相似点之间发生冲突的概率远远高于非相似的点发生冲突的概率，具体说明如下：

[0029] 算法中标记定义如下：

[0030] 1. 代表lp范数下的d维空间

[0031] 2.对 于 任 意 空 间 内 的 点 v，‖v‖p代 表 向 量 v的 lp范 数。

[0032] 数据集Q是 空间中的一个有限子集，它的长度|Q|为n。

[0033] 3.B(v，r)代表以数据点v为中心，r为半径的球。如果v∈B(q，R)，则称v为q的R-近邻，即v与q相似。

[0034] LSH 家 族 系 对 于 任 意 q， 函 数是关于t的严格递减函数。这就是说随机q和
v的距离的增大，它们发生冲突的可能性随之减小，即相似的q和v发生冲突的概率远远大于非相似q和v发生冲突的概率。

[0035] 任意的三个点q，v，u，并且满足v∈B(q，R)， 因此有p(‖q-v‖)＞p(‖q-u‖)。直观上我们可以把Q中的点哈希到低维空间U中。然后查询q时，只需要计算q的哈希，并且只需考虑q的近邻点，即与q发生冲突的点。

[0036] 为了达到需求的运行时间，我们扩大[0，R]和(R，+∞)范围内发生冲突的概率的差距。为了达到这个目的，我们联合使用几个函数 尤其在指定K以后，定义一个函数家族G＝{g：S→UK)，使g(v)＝(h1(v)，...，hK(v))，其中hi∈H，i＝1，2，...，K。对于一个整数L，我们独立地或等概率地从G中选择L个函数g1，...，gL。在预处理阶段，算法把Q中的点v都存入桶gj(v)，(j＝1，...，L)。

[0037] 下面具体说明建立数字指纹集的哈希表和指纹检测的具体实施步骤。

[0038] (1)指纹初始化

[0039] 如图2所示，在初始化阶段，首先对整体的数字指纹集进行归一化处理，并初始化参数。进行归一化处理的好处，一是可保证参与计算的量数值相差不大，避免或减小计算过程中的截断误差，二是可以保证哈希后的码字之间的距离与原始指纹之间的距离相当。

[0040] (2)构建数字指纹哈希表

[0041] 归一化处理后接着建立数字指纹哈希表。哈希表内构建了L(L大于等于1)个哈希桶，一个哈希桶存储K个哈希函数，即将数字指纹降维到K(K大于等于1)维。K影响查询准确率，L影响查询时间，具体大小根据实际应用情况调整。单个哈希桶内存储的各哈希函数相互独立，哈希桶之间的哈希函数不全相同。发行商(或信任的第三方)按照上述哈希表形式将所有原始指纹的哈希值存入哈希表相应位置，并记录原始指纹的哈希值与原始指纹的索引间的链接关系。

[0042] (3)指纹检测

[0043] 指纹的检测过程如图3所示：在指纹的检测的初始阶段也需要对查询指纹进行归一化处理，使其与建立数字指纹集的哈希表的过程相适应。在实际应用中，提取出的数字指纹集可能是受过攻击的，并且在字作品的传输的过程中或者图像、视频编解码的过程中也会受到噪声污染，使得提取出的指纹与原始的指纹之间存在着很大的差距。通过归一化处理，可以使原始数字指纹集和提取的指纹都均匀地分布在(-1，+1)之间，缩小两者之间的差距，提高检测的精度。

[0044] 按照上面对建立指纹集的哈希表算法的描述，定义经过归一化处理后的查询指纹为q。为了查询q，算法从所有的桶g1(q)，...，gL(q)中搜索。首先使用每个桶中存储的哈希函数计算q的哈希值，再在哈希表搜索到该哈希值，通过其与指纹索引的链接关系找到该哈希值对应的指纹v，指纹v即为与q发生冲突的点。对于桶中发现的每个指纹v，计算q和v之间的距离，如果‖q-v‖≤R，则称q是v的R-近邻，R为经验值可通过多次测试确定，最简单的方式是将R设为无穷大，则所有发生冲突的指纹都为查询点q对应的近邻集。对所有的‖q-v‖进行排序，最小距离对应的指纹即为q的精确近邻指纹，其对应的用户即为非法用户。

[0045] 实验结果

[0046] 本实验采用的实验环境配置如下：

[0047]

[0048] 本发明中测试实验采用如图4所示的八幅测试图像：“莉娜”、“辣椒”、“渔船”、“猩猩”、“桥”、“飞机”、“夫妻”和“手表”。在我们实验中，所采用的数字指纹是用Wu Min、He Shan等在文献“Collusion-resistant video fingerprintingfor large user group”中提出的算法生成的4544维的实数。后面几组实验中所使用的指纹集都是对该指纹集中的部分指纹进行处理得到的。实验中，首先对图4所示的8幅图像中的每幅图像分别嵌入不同的指纹得到大量嵌有指纹的图像，接着用数字指纹攻击软件StirMark Benchmark 4对这些嵌有的指纹的图像做信号处理处理攻击或几何攻击得到攻击后的伪本，然后从这些伪本中提取出指纹，即得到实验中使用的遭受过信号处理攻击和几何攻击的查询指纹集。

[0049] 测试实验对指纹检测的时间效率和准确率两方面进行实验和结果分析，如图5、图6和图7所示。实验中的检测效果在很大程度上依赖于数字指纹嵌入算法的鲁棒性和指纹检测算法提取出的指纹与原始指纹之间的保真性。

[0050] 图5说明了归一化相关性方法与基于LSH的检测方法的时间效率的对比。实验中，因为matlab软件内存限制和数字指纹集维度太大，本发明测试了用户量从2000个用户到20000个用户时归一化相关性检测方法和基于LSH的检测方法的时间效率的对比。本发明基于LSH的方法中使用了10个哈希桶，每个哈希桶内面使用了32个不同的哈希函数，即将原始指纹集降为32维。图5(a)是显示了原始的归一化相关性检测方法与本发明的基于LSH方法的检测时间的对比。图5(b)显示了对归一化相关性检测公式(1)进行了优化后与本发明中采用的基于LSH的检测方法的时间效率的对比。对归一化相关性检测方法的优化过程如下：首先对原始数字指纹ui，i＝1，2，…，L和查询指纹集z进行了归一化，公式T(1)可变为TN(i)＝zui，i＝1，2，...，L，优化后可以带来检测速度的提升。图5(a)和图
5(b)显示了本发明相比于归一化相关性检测方法，在时间效率上有巨大的优势。

[0051] 图6的实验中，首先对图4中所示的每幅图像分别嵌入不同指纹得到大量的嵌入指纹的图像，然后用StirMark Benchmark 4软件对嵌入指纹的图像进行高斯滤波、加高斯白噪声、JPEG压缩后提取出的数字指纹进行检测以及用matlab软件直接对原始指纹加高斯白噪声模拟各种受到加噪声攻击后的指纹集进行检测。高斯滤波的实验只采用了一个滤波模板，检测的平均正确率为0.885。图6(a)展示了使用基于LSH方法检测JPEG攻击的正确率。如图所示，实验中所实验的各种程度JPEG压缩攻击对检测结果基本没有影响，保持了很高的正确率。图6(b)展示了检测加高斯噪声攻击的正确率。图6(c)所展示的实验结果，是使用matlab软件直接在原始指纹上加高斯白噪声后，用基于LSH方法检测的效果图。如图所示，本发明所采用基于LSH的算法，对JPEG压缩、加高斯声都有很好的检测效果，尤其是对于JPEG压缩，基本上都能正常的检测出。对于直接在原始指纹上加高斯噪声，也有很好的检测效果，随着加高斯噪声的信噪比的减小，检测的效果会随之变好。

[0052] 图7显示了用Stirmark软件对嵌入指纹的图像进行4种几何攻击后提取出的指纹集进行实验的效果图。几何攻击一直是数字水印领域和数字指纹领域的难题，各种嵌入算法对几何攻击的鲁棒性都不理想，所以对于几何攻击检测的准确率都不高。如图所示，虽然本发明所使用的基于LSH的检测方法，对于4种几何攻击的检测效率略低，但是检测的准确率在可以接受的范围内。

[0053] 图8说明了2-50人的平均攻击、最大攻击、最小攻击、中值攻击、交叉、改进负攻击、随机负攻击这8种共谋攻击情况下的检测效果。如图所示，本发明基于LSH的检测方法对于共谋攻击仍达到0.93以上，对于大部分的攻击方法都可以正确的检测出非法用户。