Tracklet Generation Method by Submodular Optimization for Multi-Object Tracking

1.   引言

随着芯片克隆技术的发展，诸如只读存储器(Read Only Memory, ROM)中的特征信息很容易通过逆向工程、微检测技术等物理攻击手段被截取和复制，导致出现越来越多的克隆芯片。物理不可克隆函数(Physical Unclonable Function, PUF)电路通过提取芯片器件制造过程中的工艺偏差和布局布线差异来产生唯一身份认证，可以作为芯片指纹识别的合法身份认证^[1]。PUF电路在安全性和不可克隆性上具有很好的优势，能够有效抵抗物理攻击，不易被复制，因此PUF电路正逐渐应用于芯片指纹生成领域^[2,3]。

近年来，学术界和商业界出现了多种芯片指纹PUF电路。根据PUF电路构成单元类型的不同，主要包括基于仲裁器的PUF电路^{[4, 5]}、基于MUX单元的环形振荡器PUF电路^[6]等的基于延迟单元的PUF电路和另一种包括SRAM PUF电路^[7,8]、基于锁存器的PUF电路^[9,10]、蝶形PUF电路^[11]等^[12,13]的基于存储的PUF电路。根据以往研究可知，PUF电路的唯一性主要取决于PUF对工艺变化和布局布线差异的敏感性，而稳定性主要取决于PUF对温度、电源电压等环境条件变化的容忍性。美中不足的是，上述文献中的PUF电路均不能同时具有良好的唯一性和稳定性。与基于延迟类的PUF电路相比，基于存储的PUF电路的唯一性更好，由于如SRAM的存储单元对工艺变化更敏感。而且，基于SRAM的PUF电路对温度变化具有很高的容忍性。

在最为前沿的基于FPGA平台PUF研究，仅利用查找表(Look Up Table, LUT)的工艺差异作为PUF熵源，实现较为复杂^[14,15]。本文打破常规LUT设计方案，提出了使用MUX作为PUF熵的方案。针对PUF电路面积开销大、资源消耗形式多样化的问题，提出了一种基于MUX单元的新型轻量级M_SR PUF电路。通过在 Xilinx FPGA 中配置MUX单元构成延迟门单元，实现M_SR PUF。本文的主要贡献如下：

(1)高对称性的M_SR PUF单元是通过“硬宏”实现的，电路实现比较简单；

(2)M_SR PUF在Xilinx的Virtex-6，Virtex-7和Kintex-7多系列FPGA上实现，可以在广泛的环境变化(温度：0°C ～80°C；电压：0.8～1.2 V)中更稳定地工作；

(3) 在Xilinx的3个系列FPGA上实现M_SR PUF，在Virtex-6，Virtex-7和Kintex-7上分别获得50.423%, 49.902%和 50.051%的唯一性。此外，本文提出的M_SR PUF单元具有开销低的特点，仅消耗4个MUX和2个DFF，为轻量级芯片身份认证提供一种新的策略。

本文的其余部分安排如下：第2节介绍了一种传统的基于FPGA的延迟 PUF 设计。第3节介绍了基于MUX单元的M_SR PUF的设计。第4节是对实验结果的分析，分析了可靠性、唯一性和均匀性、位翻转率、随机性等性能指标。最后，在第5节得出结论。

2.   相关工作

基于FPGA的PUF电路，需要仔细设计以确保其能够很好地量化制造后的器件实际工艺变化。在基于FPGA的PUF中，通常首选RO-PUF^[16,17]和SR PUF^[8,18,19]。图1显示了一个传统的RO-PUF^[6]，它通过测量RO的自振荡回路的延迟来突出工艺制造变化。根据连接到两个不同环形振荡器的两个计数器值之间的差异，在输出端生成逻辑1或逻辑0。由于制造工艺的变化，不同环形振荡器间的频率会发生变化，可以通过比较环形振荡器的频率差来间接完成，以产生PUF响应。基于FPGA的RO PUF可以实现更好的唯一性和可靠性，但其对硬件资源的利用率较低，难以应用于轻量级物联网设备^[15]。

图  1  传统RO PUF

下载: 全尺寸图片 幻灯片

因此，具有轻量级特性的SR PUF受到青睐，即可以使用两个NOR或NAND门来实现通用SR锁存器。在多种类型的FPGA中，门是通过查找表(LUT)^{[14,17,20,21]}实现的。因此，使用NOR或NAND门实现电路没有区别，尽管它们的行为不同。图2 显示了一个基于NAND的SR锁存器^[8]，当输入信号EN为低电平“0”时，SR锁存器处于“强制”稳定状态，输出Q和Q*均为“1”。如果EN变高，SR锁存器将处于亚稳态。理论上，SR锁存器会在其亚稳态下无休止的振荡。但是，由于制造工艺的差异，两个与非门的延迟略有不同，导致其中一个具有更强的反馈(延迟1或延迟2)。因此，输出在未知时间后变得稳定。利用这一现象，学术界提出了多种类型的 SR PUF^[8,9,19]。

图  2  基于与非门的SR锁存器

下载: 全尺寸图片 幻灯片

为了实现无偏的SR锁存器，应该考虑以下几点细节。首先，有必要在输入端使用触发器来减少信号偏移，其次还必须在输出端使用触发器来平衡电容。此外，由于FPGA综合工具中的布线优化，互连信号存在不对称的布线。针对文献[18]，在可配置逻辑块中实现SR锁存器会导致PUF唯一性和可靠性较差。每个NAND门放置在单个SLICE中，SLICE放置在两个不同的CLB中，以保证文献中的对称实现^[22]。但是由于LUT端口的选择比较复杂，有些端口对外部环境的变化非常敏感，导致PUF的可靠性不高。

本文提出了一种基于MUX单元的M_SR PUF电路。根据Xilinx数据手册，两输入MUX单元的结构是相同的，位置也相对固定^[12,23]。考虑到MUX比LUT实现更简单，即MUX单元结构相同且位置固定，只需在相同数量的CLB中构建PUF单元即可保证PUF单元的对称性。

3.   基于MUX单元的M_SR PUF设计

3.1   基于MUX单元的延迟单元

根据Xilinx官方数据手册，作为Xilinx FPGA最丰富的可配置逻辑单元(Configurable Logic Block, CLB)，其由两个SLICE组成，包括SLICE_L和 SLICE_M两种类型。对于每个SLICE，包含3个多路选通器MUX，1个进位链Carry4和8个D触发器DFF等单元。通过利用CLB中的单元，可以实现许多组合电路。本文提出的PUF电路中的每个延迟单元都是在一个SLICE中实现的。根据Xilinx官方数据手册，双输入MUX单元结构一致，位置相对固定^{[24, 25]}。考虑到MUX比LUT有更简单的实现方式，即MUX单元结构相同及位置固定，能够保证延迟单元更好的公平性，进而得到输出质量较优的PUF响应。

本文使用MUX单元设计SR锁存器的延迟单元，如图3(a)所示M_NAND门设计，两个MUX单元的输入端口配置为“1”，“0”并级联，片选端口作为NAND的输入门模块和MUX单元。该输出作为与非门模块的输出，构成基于MUX单元的与非门电路。

图  3  基于 MUX 单元的延迟门 M_NAND 设计

下载: 全尺寸图片 幻灯片

3.2   M_SR PUF结构与实现

根据 3.1节所设计的基于MUX单元的延迟门电路，如图4 所示，构建了基于MUX单元的 PUF电路。对于提出的M_SR PUF，两个延迟门M_NAND放置在两个SLICE(相同的SLICE_L 或 SLICE_M)中。触发器(FF1)的输出连接到两个延迟门M_NAND1和M_NAND2的相同输入端in1作为锁存器的输入信号使能(ENE)，一个延迟门M_NAND1(或M_NAND2)的输出反馈连接到延迟门M_NAND2(或M_NAND1)的输入端in2，最后延迟门M_NAND1的输出(OUT)被触发器(FF2)锁存，得到PUF的0/1输出响应(RES)。

图  4  提出的M_SR PUF单元

下载: 全尺寸图片 幻灯片

本文采用一种响应机制，即通过提取SR锁存器的稳态来产生PUF。首先，通过输入信号ENE为“0”得到初始化的SR锁存器的输出OUT，然后通过激活ENE变为“1”，如图4所示，延迟门M_NAND1和M_NAND2作为SR锁存器实现。当锁存器进入稳定状态时，OUT被视为锁存器的响应，被FF2锁存为PUF的输出RES。其中获得高质量 PUF 响应的关键是图4 中的延时1和延时2 路径应严格对称。MUX单元在FPGA中对称分布，保证路径路由的对称性。

采用图5所示的延迟门布局策略，通过“硬宏”在FPGA中的同一系列SLICE上设计实现M_SR PUF电路(如图5，绿色或蓝色框为SR单元)， 进一步保证了PUF的高质量输出。根据上述所提出的基于MUX单元的M_SR PUF单元电路，如图6所示的实验评估平台。基于所提出的延迟门比较机制，通过“硬宏”实现一个128 bit的M_SR PUF阵列。实验系统实现中，通过数字时钟管理器(Digital Clock Manager, DCM)将开发板晶振的100 MHz时钟信号分成25 MHz触发采样时钟，然后将M_SR PUF输出位并行输出到先进先出存储器中(First In First Out, FIFO)，最后将128 bit M_SR PUF阵列输出流通过RS232串口传输到PC。

图  5  对称比较策略

下载: 全尺寸图片 幻灯片

图  6  提出的 M_SR PUF 评估系统

下载: 全尺寸图片 幻灯片

4.   实验结果与分析

本文基于硬件描述语言通过对所提出的M_SR PUF电路在Xilinx ML605, KC705和VC707 3种系列的FPGA上实现，每种系列的 FPGA 均实现 22个 128 bit PUF 输出。本节通过讨论 PUF 响应的灰度、空间特征、随机性和自相关性、唯一性、可靠性、位翻转率和资源开销来评估所提出 PUF输出响应的质量。

4.1   灰度

对于所提出的PUF电路生成的随机流，能够直观地了解输出序列的质量，本文通过采取灰度图像进行显示的方式。如图7所示，每幅图中水平方向为PUF响应输出的128 bit，垂直方向为22组PUF数量，其中图7(a)、图7(b)、图7(c)分别为实现于Xilinx Virtex-6，Virtex-7，Kintex-7的输出序列。可以看出，每组生成的128 bit序列质量不错，分布比较均匀。

图  7  22×128 bit PUF 输出序列的灰度图

下载: 全尺寸图片 幻灯片

4.2   位混叠和均匀性

比特混叠和均匀性揭示了随机序列的空间特征，其中位混叠是对相同长度的多个序列的比特偏差水平的评估，而均匀性是对序列整体偏差水平的评估。 均匀性可以理解为每个PUF输出序列中“0”和“1”的比例，位混叠可以理解为不同芯片上PUF同一比特中“0”和“1”的比例。理想下，如果位混叠和均匀性的数值为50%，表述其具有很好的空间特性。

本文将每个系列的22个PUF电路从1到22编号，从1到11的编号为均匀性组计算，其余编号组计算为位混叠。位混叠和均匀性结果如图8所示，可以看出在Virtex-6, Virtex-7 和 Kintex-7 开发板上得到的平均位混叠值为50.07%，48.58%和49.15%，平均均匀性值分别为51.14%，49.50%和48.08%。可以得出结论，所提出的 M_SR PUF 生成的序列具有出色的空间特性。

图  8  序列输出的空间特征

下载: 全尺寸图片 幻灯片

4.3   随机性和自相关

随机性是针对PUF 电路生成的随机序列的高熵、独立性和均匀分布的定义。也就是说，随机性越高，安全性越高，越难被攻击。对于随机性测试，通常使用美国国家标准与技术研究院(National Institute of Standards and Technology, NIST)提供的 NIST SP800-22 测试包进行统计测试^[26]。

本文使用的NIST测试软件版本为STS 2.1.2。对于NIST随机性测试，大多数子测试需要至少1M bit的输入序列，但一些诸如频率、块频率、累积和、傅里叶变换测试、序列、最长运行时间和近似熵测试子测试仅需要满足100 bit序列长度要求。NIST测试软件的输出是每个子测试的通过结果和评估p值(p值是NIST测试中随机性的一个很好的量化指标，其中p值越高，随机性越好)。对于本文提出的M_SR PUF，实现于Xilinx Virtex-6 FPGA开发板上的22×128 bit随机序列输出NIST测试结果如图9所示，测试结果的p值均大于指定显著性水平0.01(图9中红色横线为0.01阈值线)，输出序列具有好的随机性。

图  9  Xilinx Virtex-6开发板下PUF输出序列的NIST测试

下载: 全尺寸图片 幻灯片

自相关意味着随机误差项的期望值之间存在相关性。相关程度由相关系数表示，根据Karl Pearson设计的统计指标，如果两个变量分别为X和Y，则相关系数定义为

且相关系数的绝对值越大，相关性越强，即相关系数越接近1或–1，相关性越强，相关系数越接近0，相关性越弱。通常，当$\left|{\mathrm{\rho }}_{{X},{Y}}\right| < 0.3$时，表明两个变量之间的相关程度很弱，可以认为是不相关的。如图10所示，图10(a)，图10(b)，图10(c)分别为实现于Xilinx Virtex-6，Virtex-7，Kintex-7的输出序列自相关测试结果。从图中可以看出，相关系数$\left|{\rho }_{X,Y}\right|$得到的数据都在$6\times {10}^{-2}$以下，$\left|{\mathrm{\rho }}_{{X},{Y}}\right|\approx 0$，说明提出的M_SR PUF生成的随机序列不存在自相关。

图  10  22×128 bit PUF 输出序列的自相关测试

下载: 全尺寸图片 幻灯片

4.4   唯一性

唯一性是指针对多个PUF电路输入相同的激励后，输出响应之间的差异。工艺偏差作为PUF电路具有识别唯一身份能力的因素，理论上在相同的激励下，不同PUF电路的输出响应值分布是独立的，此时可以认为PUF的响应是唯一的。为了衡量PUF电路产生唯一响应的能力，可以使用片间汉明距离来计算不同PUF电路之间的响应差异，其中SLICE 之间的汉明距离表示两个具有相同位数的字符中包含多少个具有不同值的对应数字。因此，对于多个PUF电路实体的唯一性计算可以通过计算多个PUF电路的成对组合的芯片片间汉明距离，并计算其平均值来获得。具体计算公式为

其中，k是参与统计的芯片数量，${r}_{i}$是第$i$个芯片的响应，${r}_{j}$是第j个芯片的响应，n是生成序列的大小，HD是汉明距离。

为了更好地表明所提出的M_SR PUF可以适应不同系列的FPGA，依次评估了实现于3种Xilinx系列FPGA 的PUF输出响应的唯一性。如图11所示，在Xilinx Virtex-6, Virtex-7, Kintex-7分别获得64.541, 63.875, 64.064的平均汉明距离，即唯一性分别为50.423%, 49.902%, 50.051%。

图  11  3种系列 FPGA 实现的 PUF 芯片间汉明距离

下载: 全尺寸图片 幻灯片

4.5   可靠性

可靠性是指一个PUF电路在不同工作环境中，多次输入相同的激励会产生独特而稳定的响应。对于一个理想的PUF电路，无论外界环境如何变化，一个激励的输入都对应一个确定的输出响应。此时，可以认为PUF电路是可靠的。在实际工作中，外界环境温度的变化、芯片工作电压的波动以及其他一些环境噪声都会影响PUF电路的可靠性，而一些PUF(如仲裁器PUF)也会在仲裁结果中出现亚稳态，这会影响到PUF的可靠性。为了衡量一个PUF电路产生稳定响应的能力，需要将多个随机激励反复输入到PUF电路中，并计算稳定响应占总响应的比例。具体计算公式为

其中，N为参与测试的次数，${r}_{i}$为第$i$个芯片的响应，${r}_{i,{\rm{ief}}}$为第$i$个芯片在不同情况下的响应，n为输出响应序列的大小， HD代表汉明距离。

PUF序列是在多种电压环境(芯片工作电压步长0.05 V, 0.8～1.2 V)和宽温度波动(温度范围从0 °C～80 °C，步长20 °C)下进行的实验。如图12(a)所示，在电压变化下，本文提出的M_SR PUF输出序列在Virtex-6，Virtex-7和Kintex-7中的平均片上汉明距离分别为3.06, 3.11和2.5，即可靠性的量化值依次为94.879%, 94.010%, 91.884%。相对于电压下的可靠性结果，温度变化下的可靠性结果如图12(b)所示，Virtex-6, Virtex-7和Kintex-7开发板分别达到97.118%，96.806%和94.861%的可靠性数值。可以看出，所提出的M_SR PUF具有较强的耐温性。

图  12  3种系类FPGA的片间汉明距离

下载: 全尺寸图片 幻灯片

4.6   位翻转率

可靠性是通过在多种环境中对 PUF 电路的相同输入激励进行多次试验来测量的，反映了不同环境中的整体变化。本文还采用了针对每一位输出响应的位翻转率统计方法来量化各种环境条件下的波动。如图13 所示，所提出的 M_SR PUF 在0～80 °C的宽温度范围内在 Virtex-6，Virtex-7 和 Kintex-7 开发板上实现了平均位翻转率为 1.736%，1.910% 和 2.864%。同时，得到3.027%，3.809%和5.273%的电压变化下的平均位翻转率结果。进一步的实验表明，提出的 M_SR PUF 具有更高的温度耐受性。

图  13  PUF输出响应的位翻转率

下载: 全尺寸图片 幻灯片

4.7   相关性能对比

根据前面所述，从唯一性、可靠性和位翻转率的数据表明，本文提出的M_SR PUF具有一定的性能优势。如表1所示，针对实现平台、唯一性和可靠性以及硬件复杂度4个方面，与相关经典PUF研究进行对比。可以看出，本文提出的M_SR PUF可以在各种系列的Xilinx FPGA上实现。且由于FPGA上MUX单元的布局是对称的，不需要使用LUT带来的繁琐的手工布局和布线，因此可以实现更好的唯一性和可靠性，并且消耗更少的硬件资源。

表  1  相关PUF的性能比较

PUF 设计	FPGA平台	PUF 响应	唯一性(%)	可靠性(%)		资源消耗
				不同电压	不同温度
文献[8]	Spartan-3	128	49.200	80.000*		435×CLB
文献[16]	Artix	128	51.700	94.500*		–
文献[27]	Kintex-7	256	47.300	–	96.650	–
	Artix-7	256	40.100	94.000	96.000
文献[9]	Spartan-3	128	46.000	>87.000		2×128 SLICEs
文献[17]	Virtex-6	128	48.438	98.242	98.326	256×CLB
本文 M_SR PUF	Virtex-6	128	50.423	94.879	97.118	4×128 MUXs 2×128 DFF
	Virtex-7		49.902	94.010	96.806
	Kintex-7		50.051	91.884	94.861
注1：*表示文献没有说明获得可靠性结果的情况. 注2：1个CLB包含2 SLICEs, 1个SLICE包含4个LUTs和8个DFFs.

下载: 导出CSV 

| 显示表格

综上所述，本文提出的M_SR PUF单元具有开销低的特点，仅消耗4个MUXs和2个DFFs，在Xilinx一系列FPGA上具有良好的可移植性。而且，所提出的M_SR PUF具有很强的抗干扰性和可靠性。

5.   结论

本文针对PUF结构设计资源开销大以及实现技术较为复杂问题，提出了一种基于 MUX 单元的新颖M_SR PUF 结构方案。利用Xilinx FPGA开发套件中的MUX单元结构一致且位置固定特性，本文设计基于MUX的SR锁存器PUF单元结构，通过“硬宏”实现了128 bit M_SR PUF阵列。在多系列 Xilinx FPGAs上验证结果表明，所提出的M_SR PUF 获得了唯一性平均值为50.13%的输出响应质量指标，非常接近理想值50%。分析可得，所提出的M_SR PUF电路面积消耗低，每个M_SR PUF单元仅仅占用4个MUX和2个DFF，可以为轻量级物联网认证系统提供一种新的策略。