基于QR码模块边界偏移的信息植入与提取方法

(1. 福建工程学院 信息科学与工程学院，福建 福州 350118；2. 福建师范大学 数学与信息学院，福建 福州 350007)

随着移动智能终端和互联网技术的迅猛发展，二维条码以空前的速度占领了信息时代的至高点。作为二维条码技术的典型代表，快速响应(quick response，QR)码被广泛应用于各行各业，从移动支付[1]到身份认证[2-3]。人们在享受QR码带来的便捷服务时，对敏感信息的安全问题却感到不安，因为任何人都可以通过遵循开放标准的解码软件轻松获取标准QR码的编码信息。因此，如何实现QR码编码信息的篡改检测，是一个值得研究的问题，具有重要的社会和经济价值。

与直接加密编码信息或将认证信息与编码信息一同编码的传统方法不同，在基于QR码模块边界多方向偏移的信息植入与提取方法中，编码信息的数字签名将通过所提出的植入方法与QR码一同分发，并在解码的同时被提取出来用于编码信息的篡改检测。

1 国内外相关工作

1.1 QR码

QR码是目前应用最为广泛的二维条码技术之一，具有较高的编码容量、较小的打印尺寸、丰富的编码字符集、强大的自纠错能力、任意角度可读等特点。尽管QR码具有诸多优点，但其遵循开放设计原则因而没有对编码信息的安全性做出明确规定，加之制作和传播成本极为低廉，使其常常成为不法分子的攻击目标。文献[4]深入分析了与QR码有关的信息安全问题。

1.2 现状分析

针对QR码的信息安全问题，国内外学者纷纷给出了不同的解决方案。其中，传统方法包括利用各种加密技术对编码信息进行加、解密[5-8]以确保编码信息的安全性，该方法虽有效，但需要对终端用户(即执行解码操作的用户)进行身份认证。让编码信息不可见虽可以实现其认证功能，却有悖认证信息公开的原则。另外有一类问题的关注点是实现与QR码所关联对象的认证[9]，而非研究涉及的QR码自身编码信息的认证研究。在不改变编码信息的情况下，Yao等人[10]提出利用第三方知识库实现编码信息的认证。显然，该方法对第三方知识库的依赖性是其主要的局限所在。

另一种思路是使用额外的认证信息(例如消息认证码、数字签名)来实现编码信息的防伪，其关键在于设计切实有效的认证信息分发策略。现有方法虽未对编码信息进行修改，但大多将认证信息同样编码到QR码中[11-12]，而编码信息的增加往往意味着编码容量需求的增加，以及解码效率的降低。与之相比，空间域[13-14]以及频率域[15]数字水印技术可以在不改变给定QR码编码内容的条件下实现认证信息的植入。前者的缺点是不能用于印刷媒体传播的QR码，因为数字水印信息无法在经历打印、扫描操作之后正确还原；后者的计算开销对于计算资源和电力储备有限的移动设备非常不利。

除使用传统的数字水印技术进行数据植入外，Barmawi等人[14]以牺牲QR码自身纠错能力为代价提出了一种基于模块操作的数据植入方法，其植入容量为纠错码字容量的1/2。在文献[14]方法的基础上，Lin等人[16]提出了一种植入容量更优的私密信息分发方法。文献[17]通过对Lin等人的方法进行分析研究得出结论，其信息植入容量取决于所采用QR码纠错码的长度。文献[18]认为，由于采用LSB方法进行数据植入，Lin等人所提出的方法确实较之前的方法具有更高的植入容量。但同时，文献[19]也指出，由于使用标准QR码中的部分模块进行信息植入，该信息植入方法是以牺牲标准QR码的纠错能力为代价的。

受上述方法的启发，提出一种基于模块边界多方向偏移的信息植入及提取方法，并将其应用于QR码编码信息的认证。本方法具有植入信息容量高、抗干扰能力强等优点，适用于通过数字媒体、印刷媒体传播的QR码场景。

2 提出方法

2.1 问题描述及解决思路

给定原始信息E1，遵照开放标准(如ISO/IEC 18004:2006[20]等)对E1进行编码得QR码，令其为Q1。Q1通过印刷、互联网等媒体进行分发以后被终端用户获取，令用户获得的QR码为Q2，解码所得信息为E2。“QR码编码信息认证”问题可以理解为：如何有效实现QR码编码信息的认证，即确认E2是否与E1一致。以此为动机，提出一种基于数字签名植入的QR码编码信息认证框架，核心方法为基于模块边界多方向偏移的信息植入及提取，以实现认证信息和QR码的关联，主要针对的问题包括(1)信息植入阶段的容量设计方法，以保证大容量的植入需求；(2)信息提取阶段的纠错机制设计，以保证方法的鲁棒性。

本方法基于以下观察：标准QR码是由一系列随机排列的黑、白模块构成的矩形区域，不同色块之间存在一条明显的分界线。如赋予某些分界线以“偏移”能力，则可通过其偏移或非偏移来表达二进制0或者1。这些分界线称作可偏移边界，并定义如下：

定义1可偏移边界

对于QR码Q中任意两相邻模块M1和M2之间的边界b来说，当且仅当M1、M2代表Q中不同的二进制信息(或者说具有不同的颜色)时b为可偏移边界。

假设图1(a)中的黑、白矩形区域为某QR码中两相邻模块，则箭头所指位置即为满足定义1的一个可偏移边界，其“偏移”行为定义如下：

定义2边界偏移

定义2所述的R(M2)选取问题，在实际操作中可以有多种设计方案。其共同的步骤为对每个模块进一步作3×3等分，如图1(a)中B0-B8和W0-W8所示。差别在于：对只存在一个方向偏移的情况来说，将R(M2)设计为如图1中区域W1、W8和W7的合集(此时W0-W8为M2)。

定义3二进制0/1数据植入或提取

对于可偏移边界b来说，在某个方向上植入(或提取)二进制信息1被定义为在该方向上对b执行边界偏移(或检测到存在边界偏移)；在某个方向上植入(或提取)二进制信息0被定义为在该方向上不执行边界偏移(或检测到不存在边界偏移)。

在上述定义的基础上，提出信息植入和提取方法：根据定义1找到给定标准QR码的可偏移边界集合B；根据定义3将给定二进制信息应用于B中特定的可偏移边界以实现信息植入，或者通过检测B中特定可偏移边界的偏移状态以实现信息提取。例如，在图1(b)中，可以通过置W1、W8和W7为黑色来植入1；通过保留W1、W8和W7为白色来植入数值0。

图1 可偏移边界及其信息植入方法展示Fig.1 Boundary offset and information embedding method

值得指出的是，本方法的可行性是建立在以下几点假设的基础上：(1)QR码模块所对应的区域通常大于1个像素大小；(2)在保证模块中心位置像素不变的情况下对其他区域进行修改，通常不会影响QR码编码信息的正常读取[21]；(3)可偏移边界的数量是稳定的。其中，假设(1)用于保证模块能够进一步细分。鉴于过小的模块将导致识别效率偏低的问题，假设(1)在实际应用中是普遍存在性。假设(2)用于保证模块边界偏移不会影响原始QR码的正常读取，其论证可参考文献[21]；假设(3)用于为植入数据的容量提供保证，其有效性可由QR标准所定义的掩码(Mask)操作予以证实[20]，该操作确保标准QR码中不同色块在数量和空间分布上较为平均，而可偏移边界即与之相关。

2.2 信息植入方法

2.2.1 容量设计

植入容量是信息植入方法设计中的一个重要问题，为获得更多的植入容量，可以将图1(b)所示单方向偏移情况扩展至多方向。这是由于矩形模块存在4条边，所以模块边界偏移可以同时出现在上下左右4个方向上。显然，多方向偏移比单方向偏移能够表达更多的二进制数，即提供更大的植入容量。

为应对可偏移边界在两个相反方向上同时存在可偏移性的情况，将使用如图2所示的方案来替代图1方案。即使用W1和B5分别表示定义2中所述向右和向左方向上的“局部区域”，其颜色是否改变依植入信息的不同而异。

图2 多方向信息植入方法展示Fig.2 Multidirectional information embedding method

在有多个可偏移方向可选的情况下采用哪几个方向进行偏移是实际应用中遇到的另一个问题。显然，这是一个排列组合问题，一共有N(N满足公式1)种可能性。

(1)

受QR码中版本和纠错等级设计的启发，按照上述多方向偏移可能性以及等级越高、容量越大的原则将植入容量划分为15个等级，供用户以选择的权力。

2.2.2 方法流程

如图3所示，给定QR码Q1，二进制植入信息S1，首先按照定义1识别Q1中所有的可偏移边界B，然后采取相关措施防止植入数据溢出。具体来说，令CB为可偏移边界的个数，LS1为S1的长度，那么只要CB不小于LS1，就可以继续执行下一步骤；否则，需要通过提升QR码版本等方式获得更大的植入容量。接下来，从头到尾依次遍历S1中的每一个二进制数，并依照定义3所述的规则在对应的可偏移边界位置逐个进行植入，直至S1中的所有数都遍历完为止。为保证后续植入信息提取的顺利进行，在信息植入环节将引入纠错编码环节。任意一种块码(block code)技术都可用作纠错编码，RS编码即其中的典型代表。图4展示了该方法的效果，其中左侧是给定的标准QR码，中间是在向右和向下两个方向上植入信息后的结果，右侧对两者的差异进行了标记。

图3 基于多方向偏移的信息植入方法流程图Fig.3 Workflow of the multidirectional offset based information embedding method

图4 植入效果展示Fig.4 Embedding result

2.3 信息提取方法

2.3.1 纠错机制设计

对上述多级偏移方式所植入的信息进行提取并非简单的逆向操作，因为即使在未遭受恶意攻击的情况下，噪声、遮挡、污损等干扰也会导致终端用户获取的QR码遭到破坏。标准QR码中采用RS纠错机制来保障数据的正确性，本方法同样将利用纠错码技术，但面临的问题比标准QR码多。

本方法面临的挑战在于：既要考虑ERA(Erasure，即将0识别为1或者将1识别为0)错误，又要应对ERR(Error，即数据位丢失，例如由于遮挡等原因错将图5中左侧实心箭头所示的4位数据识别为右侧实心箭头所示的2位数据)错误。标准QR码只需要考虑ERA错误，因为一旦确定其版本和尺寸，就可以获得其模块大小，亦即编码数据的长度不会丢失。植入信息提取的关键是识别可偏移边界及其偏移情况。一旦有一个偏移边界没有被正确识别到，就会产生一个ERR。例如，图5左为标准QR码中5个黑白相间、左右相邻的模块，假设由于遮挡干扰的发生，所识别到的对应模块如图5右侧所示，此时QR码编码信息的总位数并没有变，仅产生1个ERA(右侧空心箭头标识)。相比之下，由于部分可偏移边界的消失，原本嵌入的4位二进制数(左侧箭头标识，从左向右单向偏移)最终只识别到2位(右侧实心箭头标识)，即产生2个ERR。与此同时，记t为RS纠错码的长度，就可纠错的数量来说，ERA与ERR的上限分别为t和⎣t/2」。也就是说，在RS码长度确定的情况下，ERR对纠错能力的消耗更大。因此单纯依靠RS码来实现纠错很难达到理想的效果。

为增强方法的纠错能力，提出一种准确识别携带植入信息QR码中所有可偏移边界的方法，以消除所有的ERR，具体流程如下：

2.3.2 方法流程

如图6所示，令Q2表示终端用户获取到的携带植入信息的QR码，从中解码得到E2，本方法的纠错策略是：重新对E2进行编码，得到标准QR码Q1'，从Q1'中(而非Q2中)获取所有的可偏移边界B'，然后结合B'以及Q2来提取植入信息S2，最后采用植入信息环节相同的纠错码技术对S2进行纠错，实现植入信息的准确提取。

值得说明的是，上述流程中借助了标准QR的纠错机制，从而保证B'与2.2.2节所述的B一致。因此，方法以标准QR码的正常解码为前提，这也正好切合本研究实现编码信息认证的出发点，因为在编码信息无法正常获取的情况下谈其认证是毫无意义的。另外，S2中虽然消去了所有的ERR，但可能存在ERA，因此最后仍然需要对其进行纠错处理。

图5 同一遮挡攻击下标准QR码的消除错误与本方法的数据位丢失错误比较Fig.5 Comparison between the erasure error for standard QR code and the missing digits error for this method under the same occlusion attack

图6 多方向偏移植入信息提取流程图Fig.6 Workflow of the extraction of message embedded by the proposed multidirectional offset

2.4 编码信息认证框架

基于上述多级偏移的信息植入及提取方法来实现QR码编码信息的认证功能，其主要流程如图7所示。给定QR码Q1，其编码信息为E1，为实现编码信息的认证，在生成环节将对E1进行签名操作(包括生成摘要及其加密)，并将得到的签名信息通过所提出的方法植入Q1中。然后该带签名信息的QR码将进入传播环节直至其被终端用户获取到。

由于传播环节的未知性，令获取到的QR码为Q2，通过常规解码方法将得到编码信息E2。在认证环节，将E2与E1的一致性问题转化为摘要D1和D2的一致性问题予以解决，其中D1、D2分别是对E2进行哈希和对Q2中的签名信息解密所得到的。一方面，数字签名技术确保了该认证方法的有效性，另一方面，所提出的多级偏移信息植入方法为植入高容量的认证信息及其准确提取提供了可靠的解决方案。

图7 基于多级偏移植入数字签名的QR码编码信息认证方法框架Fig.7 Authentication framework of encoded message of QR code based on hierarchical offset digital signature embedding

3 实验

为验证所提出方法的可行性和有效性，进行了各种类型的实验，主要对其中的植入数据容量评估和裁剪攻击测试结果进行阐述和讨论。

3.1 实验数据及环境

实验是在一台具有Intel Core i5(3.3 Hz)CPU、8G内存的普通台式电脑上进行的，编程环境为MATLAB。实验采用ZXing库的标准QR码编码和解码，其编码信息、植入信息均为随机生成，QR码的个数、编码/植入信息的长度、纠错等级等设置因实验目的不同。

3.2 植入数据容量评估

植入容量的大小是衡量数据植入算法的核心指标之一。该方法的植入容量与给定的QR码模块分布及所使用的方向数有关。为保证评估的客观性，随机生成4 000个标准QR码作为输入信息(其编码信息由包含于ASCII码中的字符组成，长度在9～2 900之间的，覆盖所有4个纠错等级以及40个版本号)，分别测试使用1、2、3、4个方向进行信息植入情况下的植入容量(分别记为“本方法-1、2、3、4”)。以给定QR码的编码信息容量(单位为比特)为基准，将该方法与Barmawi等人[14]的方法及Lin等人[16]的方法进行比较，其结果绘制于图8中。可见，以植入容量作为衡量标准，该方法明显优于另外两种方法。如果使用2个方向进行信息植入，该方法将具备与QR码编码信息相当的容量；如果采用4个方向进行植入，该方法的平均植入容量是QR码编码容量的2.2倍、Lin等人方法的6.4倍、Barmawi等人方法的6.7倍。

3.3 裁剪攻击实验

为测试方法的鲁棒性，进行了两组裁剪攻击实验。鉴于所提出的纠错方法是建立在QR码自身纠错机制的基础上，因此实验对象选取为纠错等级H(即最高等级)、版本号4的1 000个标准QR码。为模拟QR码在实际应用中可能遭遇的各种遮挡情况，在第一组实验中，使用以图9所示为代表的裁剪攻击进行测试，实验结果表明本方法具有良好的植入信息提取能力。

图9 裁剪攻击示例Fig.9 Demonstration of different kinds of occlusion attacks

为进一步量化方法的纠错性能，在第二组实验中，将352比特的信息(其中128比特为有效信息，其余为纠错码)植入给定的1 000个QR码中。然后将遮挡区域定义为不同尺寸(占QR码图片面积从5%至30%不等)的矩形区域，同时将其以滑动窗口的形式依次遮盖QR码的不同区域，然后执行提取操作，并通过公式2计算得到植入信息提取的成功率R。

(2)

其中Ncor是植入信息被成功提取的次数，Ntot是窗口滑动的次数。最终的平均成功率Ravg是对1 000个QR码进行测试所得结果的平均值。

表1展示了在不同方向上进行植入的提取成功率结果，该结果是在对应QR码能够成功解码的前提下得到的。此外，表中还记录了相同实验情况下，对应QR码自身编码信息解码的成功率，用以作为本方法成功率的参照基准。从表1可知，遮挡面积越小，植入信息提取的成功率越高。另外，由于使用1个方向进行植入较4个方向的植入数据分布更为分散，因此提取的成功率也更高。

4 结语

提出一种基于多级模块边界偏移的信息植入和提取方法，将其与数字签名技术相结合，可以在不改变给定QR码编码信息的情况下，实现QR码编码信息的篡改检测功能，从而保证用户的财产信息安全。该方法的创新点在于：1)提出了一种多级模块边界偏移的QR码信息植入方法；2)实现了一种有效应对数据位丢失错误的纠错策略；3)将信息植入和提取方法与数字签名技术相结合，构建出一套QR码编码信息认证框架。通过实验验证了方法的可行性和有效性。但受限于QR码自身纠错性能，该方法中植入信息的提取成功率仍有待进一步提升，需要更加深入研究。

表1 不同摘挡尺寸情况下的植入信息平均提取成功率