序列检测和近似熵检测的快速实现研究

王 彤，朱敏玲

北京信息科技大学 计算机学院，北京 100101

1 引言

网络环境的日益复杂让信息安全逐渐成为人们关注的重点话题。随机序列在信息安全领域中有着广泛的应用，例如众多的密码算法、安全协议、数字水印、密码芯片中都利用随机序列来增强安全性[1]。因此，随机序列的质量直接影响信息安全问题。

随机序列的产生方式分为两种，一种是经过物理现象产生的真随机序列，另一种是经过计算机中的随机函数产生的伪随机序列[2]。著名的计算机学家冯·诺依曼曾经说过“任何想用数学的方法产生真随机数的人都是在痴心妄想”[3]。而伪随机数发生器和密码算法是通过一系列复杂的数学运算处理“种子值”得到伪随机序列，因为有“种子值”，伪随机序列在一定程度上是可控可测的，难以保证其质量。因此，在实际应用中需要对随机序列进行检测，保证随机序列的质量。

随机序列实质上是对一组均匀分布的随机变量进行抽样，产生的结果是不可控制、不可预测的，序列中的每个元素是相互独立，且服从均匀分布[4]。为保证随机序列在应用过程中的稳定性，随机性检测通过一些特定的特性，比如统计比特数量、m位非重叠子序列频数、两比特间异或操作等，分析待检测序列与真随机序列之间的差距，判断其是否通过检测。经过长时间的研究和发展，目前国内外研究学者已经提出了大量的随机性检测方法。国际上通用的检测方法是将多种随机性检测算法组成检测套件，以提供更复杂和全面的随机性分析，但是随机套件执行效率较低，当检测数据达到GB级时，在标准计算机上完成一次完整的随机性检测可能需要数小时[5]。

在随机性检测的应用价值下，国内外众多研究学者对随机性检测项目进行优化研究，例如，杨先伟等通过将不同参数情况进行整合，对扑克检测进行优化研究，提高算法效率9.5倍左右[6]；康红娟，杨先伟等通过将待检测序列分为初始序列和检测序列并按字节进行处理，减少数据流失，减少大量对数运算，提高Maurer通用统计检测效率[7]；Suciu等采用字节处理方式优化随机性统计检测包，检测包整体速度提升13.45倍[8]；Sýs等对NIST统计测试套件进行优化，并对线性复杂度检测和Berlekamp-Massey算法进行分析和优化[9]。

2001年美国NIST发布了16种随机性检测标准，其中将传统的序偶检测和扑克检测替换为序列检测，于亦舟等人将三种检测方法进行对比分析，证明序列检测效果要优于同时使用扑克检测和序偶检测的效果[10]。近似熵检测作为一项基础检测方法，不仅出现在我国的随机性检测标准中，也出现在众多国家的检测标准中。但是序列检测和近似熵检测的检测速度较慢，在NIST统计测试套件中检测速度位于各检测项的末端[11]。因此，本文对序列检测和近似熵检测进行优化分析，提高检测方法的运行效率。

2 两种检测算法简介

2.1 序列检测

序列检测的目的是判定待检测序列中2m个m位重叠子块的数目是否和随机情况下预期值一致。随机序列具有均匀性，故序列中每种m位重叠子序列出现的频数应该是一致的[12]。

计算两个相邻长度可重叠子块的频数时，设Yi(m)=(εi+1,εi+2,…,εi+m-1)，令：

式（1）中表示模式Yi(m)在待检测序列中出现的相对频数，πi表示模式l=(i1,i2,…,im)在待检测序列中出现的相对频率。待检测序列长度为n，m

序列检测的执行流程如下：

（1）将待检测序列ε构造成一个新的序列ε′，构造方法是将序列ε最开始的m-1位数据添加到序列ε的结尾得到新序列ε′，新序列ε′的长度为n′=n+m-1。

（2）计算ε′中所有的2m个m位子序列模式的出现频数，记m位模式i1i2…im出现的频数为vi1i2…im。对于所有的j(0≤j≤2m-1)，计算待检测序列中出现的相对频数。重复上述构造过程，分别计算不同参数下ε′中所有的m位、m-1位、m-2位子序列模式的出现频数。

（3）计算观察到的m比特模式的频数与预期模式频数的匹配程度，即统计值。

（4）计算p-value值，设显著性水平为α，如果p-value1≥α且p-value2≥α，则此序列通过序列检测；否则，不通过检测。

2.2 近似熵检测

近似熵检测与序列检测方法相似，目的是比较序列中相邻长度的重叠子序列出现的概率是否和正态分布的序列中出现的概率情况接近，以此来判断序列是否通过检测[13]。近似熵检测的执行流程如下：

（1）将长度为n的二元序列ε构造成一个新的序列ε′，构造方法与序列检测相同，得到新序列ε′，新序列ε′的长度为n′=n+m-1。

（2）计算ε′中所有的2m个m位子序列模式出现频数vi1i2…im，对所有的j(0≤j≤2m-1)，计算待检测序列出现的相对频数，计算相对频数方法与序列检测中一致。

（4）用m+1代替m，重复操作（1）至（3），计算得到。

（5）计算熵ApEn(m)和统计值V。

（6）计算p-value值，设显著性水平为α，如果p-value≥α，则认为待检序列通过近似熵检测；否则，不通过检测。

序列检测和近似熵检测方法相似，两种检测采用相同方法将待检测序列构造成新序列，并统计新序列中所有2m个m位子序列出现的频数，两种检测计算得到的统计值均服从χ2分布。

3 两种算法的效率分析与改进

传统随机性检测过程中将待检测序列存储和处理为数组，根据不同检测算法的描述对单个比特进行操作。例如在美国国家标准与技术研究院发布的随机性检测包sts2.1.2中采用一种通用的方法来计算扩张序列中所有可能出现的重叠mbit，首先定义具有2m+1-1个元素的数组变量p[]；将待检测序列划分成n m个非重叠子序列；定义局部变量k、i，再对每一个子序列，依次判断每个单比特的值，若值为1，则令X=X+1，若值为0，则令X=2X+1；每个子序列计算结束后统计，令p[X-1]=p[X-1]+1，同时令k=1。这种对待检测数据进行单比特处理的操作方式，不仅浪费CPU的字长，而且当检测数据达到GB级时，这将是一个非常耗时的转换过程。

通过分析两种算法的执行流程可知，序列检测和近似熵检测在计算过程中均统计了2m个m位子序列出现的频数，因此对该过程的时间复杂度进行分析。当两种检测的空间复杂度相同时，采用一种特殊的数据结构——二叉树，分析该步骤的时间复杂度。首先，查找m位重叠子序列出现的频数，就要构造深度为m+1的满二叉树，满二叉树共有2m+1-1个节点，其节点中存放的信息是该节点代表的m位子序列出现的频数。在统计序列中m位子序列出现的个数过程中，需要在有匹配信息时对应节点内容增加1，最后统计底层节点中存放的频数。在统计频数过程中每次向后移动1 bit，它的时间复杂度为O(mn)。因此，在空间复杂度相同的情况下，两种检测计算待检测序列中相邻长度重叠子序列频数的时间复杂度为O(n)。

序列检测和近似熵检测在统计2m个m位子序列出现的频数时，当参数m=2时，序列检测计算2位、1位重叠子序列出现的频数，近似熵检测计算2位、3位重叠子序列出现的频数；当参数m=5时，序列检测计算5位、4位、3位重叠子序列出现的频数，近似熵检测计算5位、6位重叠子序列出现的频数。在两种检测算法中存在大量重复的数据加载和计算过程，例如当m=2时，两种检测算法各执行一次（1）、（2）操作，如果将两种检测的部分数据进行复用，可以大大缩减检测时间，提高检测效率。

综上所述，采用序列检测和近似熵检测对大量数据进行检测时，需要通过若干轮的比特转换和逐比特的数值判断和数学运算才能得到统计值，因此对大量数据进行两种检测的运算量较大，执行效率较低，检测过程非常耗时。在实际应用中，多数国家的随机性检测标准中均包含序列检测和近似熵检测，因此需要加快两种检测的运行速度，以便快速筛查出不符合随机性特征的序列。针对以上问题，本文采取下列方法快速实现两种检测算法：

（1）优化字节处理方式，使用位级操作一次处理多个比特，提高CPU的利用率。

（2）根据检测算法自身特点，按字节对m位可重叠子序列模式出现的频数进行预处理，将字节处理与相对频数计算相结合。

（3）根据两种算法自身特点合并两种检测方法，减少数据重复加载过程，避免冗余的计算过程。

4 优化算法

4.1 两种检测算法优化

序列检测和近似熵检测在计算m位子序列模式出现的频数时，由于参数m无法确定，导致无法对字节中的重叠子序列进行预处理，因此本文根据随机性检测经验定义m=2,5。

本文中记ε=ε1||ε2||…||εL，1≤L≤n/8 为多个字节组成的待检测数据，其中εi，1≤i≤L。为区分两种参数下统计m位子块的相对频数情况，记为序列中m位子块出现的相对频数，其中1≤i≤2m。当参数为m时，计算相对频数的方式为：

优化方法中#i的值采用创建字节表的方式获取，当参数m=2 时，记B=(#i,t)表示计算ε=ε1||ε2||…||εL这新序列L个字节中m位子序列出现的频数，当t为1时，B=(#i,1)表示字节ε1中00、01、10、11子序列出现的次数。B=(#i,t)可以通过查表统计，得到所有重叠子序列出现的频数。在查询字节表的过程中，如果上一次是使用序列中第i～i+7位进行查表的，那本次将使用序列中第i+7～i+14位进行查表。以参数m=2为例，序列检测算法优化过程如下：

算法1优化实现序列检测算法

输入：待检测序列ε=ε1||ε2||…||εL，1≤L≤n/8，参数m=2

输出：序列是否通过序列检测

1.初始化数据：#i=vi1i2…im=0

2.将序列最开始的m-1位添加到序列末端，构成新序列ε′ ，即ε=ε1||ε2||…||εL→ε1||ε2||…||εL+m-1

3.L≤n/8时，查表计算B=(#i,t)，得到m位重叠子序列出现的频数

4.重复步骤1～3，分别计算m-1、m-2位重叠子序列出现的频数

6.计算p-value值，如果p-value≥0.01，序列通过检测

近似熵检测优化过程中，参数m=2时，计算m位重叠子序列的方法与序列检测相同，当参数转换为m+1=3时，查询字节表的过程中，如果上一次是使用序列中i～i+7位进行查表的，那本次将使用序列中第i+6～i+13位进行查表。以参数m=2为例，近似熵检测算法优化如下：

算法2优化实现近似熵检测算法

输入：待检测序列ε=ε1||ε2||…||εL，1≤L≤n/8，参数m=2

输出：序列是否通过近似熵检测

1.初始化数据：#i=vi1i2…im=0

2.将序列最开始的m-1位添加到序列末端，构成新序列ε′ ，即ε=ε1||ε2||…||εL→ε1||ε2||…||εL+m-1

3.L≤n/8时，查表计算B=(#i,t)，得到m位重叠子序列出现的频数

4.重复步骤1～3，计算m+1位重叠子序列出现的频数

5.计算近似熵ApEn(m)和统计值

6.计算p-value值，如果p-value≥0.01，序列通过检测

4.2 两种检测算法合并优化

将两种检测算法合并的过程中，字节统计结果可以在两种算法之间复用。当参数m=2时，两种检测同时需要统计2位子序列出现的次数；当参数m=5时，两种检测同时需要5位子序列出现的次数；当同时进行参数m=2，5时，近似熵检测可复用序列检测中2位、3位、5位子序列查表结果。极大地减少了两种算法的运算量，提高两种算法同时运行的效率。下面以参数m=2为例，提出两种检测合并后算法。

算法3优化实现两种合并算法

输入：待检测序列ε=ε1||ε2||…||εL，1≤L≤n/8，m=1

输出：检测结果

1.初始化数据：#i=vi1i2…im=0

2.将序列最开始的m-1位添加到序列末端，构成新序列ε′ ，即ε=ε1||ε2||…||εL→ε1||ε2||…||εL+m-1

3.L≤n/8时，查表计算B=(#i,t)，得到m位重叠子序列出现的频数

4.令m+=1，m<4 ，重复步骤1～3，分别计算出1位、2位、3位重叠子序列出现的频数

5.计算序列检测统计量∇Ψ2m、∇2Ψ2m

6.计算近似熵检测ApEn(m)和统计值

7.计算p-value1、p-value2、p-value3值，如果p-value≥0.01，序列通过检测

5 实验结果

在实际应用中产生随机序列的方式主要分为两类，一类是由伪随机数发生器和密码算法产生的伪随机序列，伪随机序列并不是真正意义上的随机序列，它是由确定事件的概率组合产生的，因此伪随机序列能够被预测和重复。另一类是通过物理方法产生的真随机序列，物理方法通过利用随机“噪音”信号产生序列，例如热力学噪声、电噪音中提取随机序列[14]。然而理论上经典的物理过程在考虑所有环境变量的基础上是可以模拟的，唯独量子物理过程产生的随机序列是完全真随机序列。在量子随机数发生器中，量子是无法继续分割的，量子组成了光子、原子、电子，它是构成物质的最小微粒。量子随机数具有随机性主要原因是量子事件中测量坍缩造成的不确定性和真空起伏导致的随机噪音，量子事件具有不确定性，量子随机数发生器利用这一特性产生随机序列[15]。因此，为保证实验数据可以通过两种检测，实验采用量子随机数发生器产生的真随机数。

本实验的测试平台情况如表1所示。

表1 测试平台信息

为更准确地说明本文提出的算法的效率，设计实验测试优化前后算法的执行效率。测试数据是利用量子随机数发生器生成的109bit的随机数据，将随机数据按106bit规格划分为1 000条样本数据。对比实验采用美国NIST官网发布的sts-2.1.2检测包，该检测包仅适用于Linux系统，为保证实验条件的一致性，本文按照该检测包代码思想，在Windows系统中实现两种检测算法。优化后实验是对待检测序列按照上述优化算法，分别实现参数m=2及m=5时的两种检测及合并后的检测，所有的算法均采用标准C实现，计时单位为ms。

参数m=2,5时选取实验中500条样本，原序列检测和近似熵检测以及优化后的算法1、算法2、算法3运行时间如图1～4所示。

图1 m=2时原算法耗时间

图2 m=2时优化算法耗时间

图3 m=5时原算法耗时间

图4 m=5时优化算法耗时间

实验结果如表2所示，参数m=2时，序列检测优化后速度提升了29.72倍，近似熵检测优化后速度提升了27.58倍；参数m=5时，序列检测优化后速度提升了30.02倍，近似熵检测优化后速度提升了24.14倍；参数m=2及m=5时两种检测合并后速度分别提升了40.12倍、45.23倍。

表2 算法性能对比

6 结束语

本文对NIST随机性检测标准中的序列检测和近似熵检测进行快速实现。通过对字节的预处理、字节统计与相对频数统计相结合、频数统计优化复用等方法，使得序列检测和近似熵检测速度最高分别提升30.02倍、27.58倍，两种检测合并后整体速度最高提升45.23倍。

本文提出的序列检测和近似熵检测优化方案，有利于两种检测方法的推广和应用。随机性检测标准中还有很多其他检测项可以做性能优化及算法合并，这将是以后研究工作的一个方向。