1. 项目概述当硬件指纹遇上形式化学习在硬件安全领域物理不可克隆函数PUF一直被视为构建“无密钥”密码学的希望之星。它的魅力在于直接利用芯片制造过程中无法复制的微观工艺偏差为每一颗芯片生成独一无二的“指纹”。想象一下你无需在芯片里烧录一个固定的密钥芯片本身的结构就是密钥。这对于资源捉襟见肘的物联网终端、边缘设备来说无疑是构建硬件信任根的理想方案。然而理想与现实之间总有一道鸿沟。基于延迟的PUF尤其是其鼻祖——仲裁器PUFAPUF其安全模型建立在“线性可加延迟”这一假设之上。简单来说一个n位的挑战输入控制着信号在两条对称路径中的走向最终的响应输出0或1取决于哪条路径的信号先到达仲裁器。这个过程的数学模型是线性的而这恰恰成了它的阿喀琉斯之踵。过去十几年安全研究者和攻击者之间上演了一场精彩的“攻防拉锯战”设计者不断提出新的PUF组合结构比如XOR PUF、反馈PUF、交织PUF来增加非线性而攻击者则不断升级机器学习模型用更少的挑战-响应对CRP就能成功克隆PUF的行为。这场博弈催生了一个核心问题我们能否在芯片流片之前就从理论上严格证明某种PUF设计能抵抗多大强度的建模攻击这正是“可证明学习”理论要回答的。概率近似正确PAC学习框架为我们提供了一个强大的数学工具。在这个框架下我们可以问给定一个PUF设计视为一个“概念”一个攻击者“学习者”需要多少组随机的CRP样本才能以高概率1-δ学习到一个错误率不超过ε的近似模型先前的研究已经证明基础的APUF和XOR APUF在PAC框架下用线性阈值函数LTF或决策列表DL等表示类是“可学习”的。但我们的工作向前迈进了一大步我们首次系统性地证明任意基于APUF的组合结构无论其组合方式多么复杂输出组合、输入变换、层级结构在确定性有限自动机DFA这一表示类下都是多项式时间/空间可学习的。我们提出的框架名为PLAnCo它不仅是一个理论分析工具更是一套能自动为任意PUF组合生成多项式规模DFA模型并计算其PAC可学习性上界的算法。提示理解PUF安全性的一个关键视角是“建模攻击”与“可证明安全”的对抗。建模攻击是实践中的威胁而可证明学习是从计算复杂性理论角度给出的形式化安全边界。我们的工作属于后者旨在为设计提供事前pre-silicon的理论安全评估。2. 核心挑战从组合PUF到多项式规模DFA的鸿沟将单个APUF建模为DFA已有先例其结构类似一棵深度为n挑战位数的二叉树每个状态追踪信号在特定阶段的累积延迟差。但当我们面对由多个APUF通过复杂逻辑组合而成的“超级PUF”时直接套用单个DFA的思路会立刻撞上两堵高墙。2.1 状态爆炸组合DFA的天然障碍第一个挑战直观但致命。假设我们有两个APUF各自有一个DFA表示。当它们通过一个XOR门组合时最朴素的想法是将两个DFA“并联”起来构建一个非确定性有限自动机NFA。这个NFA的每个状态是原来两个DFA状态的组合。问题在于经典的NFA转DFA算法子集构造法会导致状态数指数级增长。对于k个APUF的组合最坏情况下DFA的状态数可能达到O(2^k)量级这立刻就让“多项式规模”的梦想破灭了。为什么状态会爆炸根源在于不确定性。在组合NFA中读入一个输入符号挑战位后机器可能同时处于多个“候选状态”。为了消除不确定性子集构造法会将这组候选状态打包成一个新的DFA状态。当组合的组件很多时这些状态子集的数量是指数级的。2.2 输入分叉当每个PUF看到不同的挑战第二个挑战更为棘手。在很多高级PUF设计中比如交织PUFiPUF构成系统的多个APUF接收的挑战并不是相同的。上层PUF的响应会被插入Interpose到下层PUF的挑战位中。这意味着组合系统中不同DFA的“左语言”即到达该状态的所有前缀挑战序列完全不同。在经典的DFA组合理论中合并状态的前提是它们等价而等价的一个重要条件是具有相同的左语言。当左语言不同时状态不能简单合并。这似乎堵死了我们构建紧凑DFA的道路。2.3 我们的破局思路三大技术支柱面对这两大挑战我们提出了三个核心的技术创新它们共同构成了PLAnCo框架的基石基于“可合并状态”的精简我们观察到在APUF的DFA树状结构中许多状态在功能上是“可合并”的。即使它们来自不同的组件DFA只要它们对应相同的挑战前缀路径并且其累积延迟信息在后续计算中扮演的角色是“可互换”的那么这些状态就可以被合并而不改变自动机接受的语言。我们给出了严格的形式化引理Lemma 1来判定两个状态是否可合并其核心是检查合并后是否会产生新的、原本不被接受的语言路径。字母表编码应对输入分叉对于接收不同挑战的组件DFA我们不再强求在原始二进制字母表{0, 1}上合并它们。相反我们进行“字母表升维”。对于一个k元组合我们将每个输入符号重新定义为一个k位的向量。例如对于两个APUF的组合输入字母表从{0, 1}变为{(0,0), (0,1), (1,0), (1,1)}。这样组合DFA的每个转移就对应一个k位的挑战向量。虽然字母表大小从2变成了2^k但关键在于k是一个小的常数通常出于可靠性考虑k不会超过log(n)因此2^k仍然是n的多项式避免了根本性的指数爆炸。DFA插值处理输入变换这是处理像交织PUF这类结构的关键。当某个挑战位被另一个PUF的输出所替代时我们不是简单地将两个DFA串联。而是在主DFA对应这个挑战位的转移边上“插入”一个完整的子DFA。具体操作是移除原转移边用ε-转移空转移将原状态连接到子DFA的起始状态再将子DFA的所有最终状态和非最终状态分别用ε-转移连接到主DFA原本该挑战位为1或0时应到达的下一个状态。这个过程就像在程序的某个条件判断处插入了一个复杂的子函数调用。3. 构建多项式规模DFA从理论到实例理论需要实例来验证。我们以几种最具代表性的PUF组合结构为例展示PLAnCo框架如何一步步构建出紧凑的DFA模型。3.1 输出组合以k-XOR PUF为例k-XOR PUF是最经典的增强型PUF它将k个独立APUF的响应进行异或以增加非线性。步骤一构建ε-NFA我们为k个APUF分别构建其DFA记为DFA1, DFA2, ..., DFAk。创建一个新的起始状态S并用ε-转移连接到这k个DFA的起始状态。这形成了一个“并行”结构。接下来是关键我们需要定义最终状态。在最后一个层级第n层我们根据XOR函数的语义来标记最终状态。具体规则是如果一个状态组合中有奇数个DFA处于其自身的最终状态即响应为1那么这个组合状态就是整个k-XOR PUF的最终状态。步骤二NFA到DFA转换与状态合并这是避免指数爆炸的核心。由于所有APUF接收相同的挑战它们在各自DFA中走过的路径是完全同步的。当读入挑战位0时所有DFA都走“左分支”读入1时都走“右分支”。因此在每一层来自不同DFA但对应相同路径比如都是“左-左-右”的状态它们所携带的延迟信息虽然数值不同但在DFA的“语言接受”判定逻辑中它们所处的“相对位置”是等价的。根据我们的可合并状态引理这些状态可以被合并。合并后每个层级的状态数从k个独立状态缩减为1个组合状态该状态需要同时记录k个APUF的延迟对信息。步骤三延迟离散化实现多项式规模即使经过合并每个状态需要记录的延迟值对(α_i,1, α_i,2)仍然是连续值理论上仍有无限可能。这里我们引入一个关键的物理观察仲裁器有比较精度γ。只有当两条路径的延迟差绝对值大于γ时仲裁器才能稳定地输出0或1。因此我们可以将连续的延迟差离散化为有限的整数区间。假设延迟服从高斯分布N(μ, σ)那么n级后的累积延迟差绝大部分落在区间[nμ - 3√nσ, nμ 3√nσ]内。将其除以精度γ并取整延迟差就被离散化为[0, d]区间内的整数其中d ⌈6√nσ / γ⌉。对于一个k-XOR PUF每个状态需要存储2k个离散化后的延迟值。每个值有(d1)种可能因此每一层最多有(d1)^(2k)个可区分的状态。总共有n层所以整个DFA的状态总数上界为O(n(d1)^(2k))。由于d是n的多项式函数d ∝ √nk是常数因此整个DFA的规模是n的多项式。这就严格证明了k-XOR PUF存在多项式规模的DFA表示。3.2 输入变换组合以交织PUFiPUF为例交织PUF(ku, kl)-iPUF由上下两层XOR PUF组成上层ku-XOR PUF的响应会被插入到下层kl-XOR PUF的某个特定挑战位中。DFA插值操作假设下层的第i个挑战位被上层的输出替代。我们首先构建上层ku-XOR PUF的DFADFAu和下层kl-XOR PUF的DFADFAl。定位与切断在DFAl中找到所有在第i层对应被插入的挑战位的状态。移除这些状态原本基于输入0和1向第i1层状态的转移边。插入子DFA对于第i层的每一个状态q添加一条ε-转移指向DFAu的起始状态。这意味着当DFAl“读”到第i位时它实际上会“调用”整个DFAu来处理完整的原始挑战。结果路由DFAu处理完挑战后会到达其最后一层的某个状态。如果这个状态是DFAu的最终状态即上层响应为1则通过ε-转移跳转到DFAl中状态q在输入为1时应到达的下一个状态记为q(1)如果是非最终状态响应为0则跳转到q(0)。深度与规模分析经过插值DFA的深度增加了。DFAl先解析前i-1位然后DFAu解析全部n位最后DFAl解析剩下的n-i位。总深度变为 (i-1) (n1) (n-i) 2n1。在状态数方面由于我们应用了状态合并技术在任意一层可区分状态数由上层和下层中规模较大的那个决定即O((d1)^(2max(ku,kl)))。因此总状态数为O((2n1)(d1)^(2max(ku,kl)))仍然是多项式规模。3.3 通用构造算法我们将上述针对特定结构的构造方法抽象成一个通用算法Algorithm 1能够处理任意用PUF-G语言描述的APUF组合。PUF-G是一种形式化描述语言可以像搭积木一样定义PUF的串行、并行和条件组合。算法核心是递归下降的DFA构建过程解析将PUF-G描述解析成模块化结构树。递归构建对每个基本APUF模块生成其基础DFA模板。组合根据模块间的连接关系输出组合、输入变换调用相应的ComposeDFAOut或ComposeDFAInput函数利用前述的合并、编码、插值技术进行DFA组合。化简对组合产生的NFA应用子集构造法转换为DFA并持续检测和合并等价状态最终输出最小化的多项式规模DFA。这个算法可以无缝集成到现有的PARLE-G框架中实现从PUF设计描述到可学习性上界计算的自动化流程。4. PAC可学习性上界计算与实验验证有了多项式规模的DFA表示我们就可以将其代入PAC学习理论计算出攻击者成功建模所需CRP数量的理论上界。4.1 理论边界推导PAC学习的核心是样本复杂度。对于DFA表示类一个经典结论Angluin, 1987是如果一个目标概念可以用一个状态数为N的DFA表示那么存在一个学习算法最多需要O(N (1/ε)(N log(1/δ) N²))次查询成员查询就能以至少(1-δ/2)的概率学习到一个ε/2近似的假设。我们将之前推导出的各类PUF组合的DFA状态数N代入这个公式就得到了它们的PAC可学习性上界。下表总结了部分关键结果PUF 构造类型DFA 深度每个状态追踪的延迟参数数量DFA 总状态数上界 (N)PAC 样本复杂度上界 (大O表示)APUF(基准)n2O(n(d1)²)O(n(d1)² (1/ε)(n(d1)² log(1/δ) n²(d1)⁴))k-XOR PUF(输出组合)n2kO(n(d1)^(2k))O(n(d1)^(2k) (1/ε)(n(d1)^(2k) log(1/δ) n²(d1)^(4k)))(ku, kl)-iPUF(输入变换)2n12*max(ku,kl)O(n(d1)^(2*max(ku,kl)))与k-XOR类似但n替换为2n1反馈PUF (FF-APUF)nin2O((nin)(d1)²)与APUF类似深度增加循环PUF (Rec-APUF, θ次迭代)nθ(n1)2k (若核心为k-XOR)O((1θ)n(d1)^(2k))深度线性增加状态数多项式增加LPPUF (层级结构)O(n²)2m (m为第一层APUF数)O(n²(d1)^(2m))深度变为平方级状态数相应增加核心洞见输出组合的影响主要增加状态中追踪的参数数量从2到2k导致状态数上界中的指数基(d1)的指数变大但深度不变。这使得样本复杂度随k多项式增长但与使用的具体布尔组合函数XOR、Bent函数等无关。这是DFA表示区别于LTF表示的一个重要优势。输入变换的影响主要增加DFA的深度从n到2n1、nθ(n1)等导致样本复杂度随深度线性增加。闭合性一个关键结论是基于APUF的组合无论经过多少层上述操作其DFA表示规模始终是多项式级的因此其PAC可学习性上界也始终是多项式级的。这意味着仅通过组合APUF无法获得指数级的安全增益来抵抗基于DFA的PAC学习攻击。4.2 实验验证模拟与FPGA实测为了验证理论边界的现实可行性我们在PyPUF仿真框架和实际FPGA实现上进行了实验。仿真实验设置 我们修改并集成了Angluin的L算法实现用于学习模拟PUF实例的DFA。L算法通过向“教师”即PUF仿真器发起成员查询“这个挑战的响应是1吗”和等价查询“我当前学到的DFA对吗”来逐步逼近目标DFA。我们设定了学习参数ε0.01精度和δ0.1置信度。实验结果 我们对16位和32位挑战长度的多种PUF构造进行了建模攻击结果如下表所示PUF 类型参数无噪声噪声水平0.01噪声水平0.054-XOR APUFn1699.8%98.5%95.2%4-XOR APUFn3299.5%97.8%93.7%(1,4)-iPUFn1699.6%98.1%94.8%LPPUFn16, m498.9%96.3%91.5%注意噪声水是PyPUF中模拟环境扰动的参数0.01和0.05代表不同程度的响应不可靠性。实验表明即使在有噪声的现实条件下攻击仍然有效只是达到相同精度所需的查询次数会增加。FPGA实验 我们在FPGA上实现了64位挑战的4-XOR和8-XOR APUF并采集了真实的CRP数据。使用L算法进行学习在约10,000次等价查询内建模准确率分别达到了81%和81.2%。一个重要的观察是实际学习到的DFA大小远小于我们理论分析推导出的DFA表示上界。理论DFA证明了此类模型“存在”且规模可控而L算法在实践中找到了更紧凑的、功能近似的DFA。这解释了为何实际所需的CRP数量远低于理论样本复杂度上界但也同时意味着这些PUF在实际中可能比理论最坏情况更脆弱。5. 安全启示与设计反思我们的研究得出了一个或许令人沮丧但必须正视的结论在线性可加延迟模型的假设下任何基于APUF或类似延迟链的组合构造都无法在PAC学习框架下获得超越多项式级别的安全性。攻击者总能在多项式数量的CRP样本内以高概率学习到一个足够准确的模型。5.1 对现有PUF设计策略的重新评估根据可学习性上界我们可以将各类PUF组合划分到不同的复杂度类别中如图15所示Class 1基础APUF深度n追踪2个延迟参数。Class 2输出组合如XOR PUF深度n追踪2k个参数。Class 1a/2a在Class 1/2基础上引入输入变换如iPUF深度线性增加。Class 3交叉路径比较结构如DAPUF深度n但追踪k(k-1)/2个延迟对。这些类别之间的边代表了组合操作带来的复杂度变化。一个关键的发现是除了Class 1其他类别都有“自循环”这意味着在同一类别内的进一步组合例如将多个iPUF再组合不会改变其关于挑战长度n和组件数量k的渐进复杂度级别。这揭示了当前主流增强策略的局限性它们只能带来多项式级别的安全提升无法实现指数级的“安全跃迁”。5.2 未来安全PUF的设计方向既然基于线性延迟模型的组合之路似乎走到了尽头那么安全的下一代PUF应该朝向何处我们的分析指出了几个可能的方向打破线性可加延迟模型这是根本性的解决方案。需要引入本质的非线性物理效应使得延迟无法被建模为挑战位的线性加权和。例如利用电路中的振荡器频率、存储器单元的亚稳态等非线性特性。引入非二进制输出当前DFA建模依赖于二进制响应。如果PUF输出是多值或模拟量并且最终响应依赖于多个阈值比较那么简单的DFA模型可能不再适用需要更复杂的表示类。探索非基于延迟的熵源例如基于SRAM启动值、蝴蝶PUF、光学PUF等其物理机制与延迟链完全不同可能天生具有更高的建模复杂度。设计指数级膨胀的自动机有意识地将PUF设计成其最小DFA表示的大小随参数指数级增长。但这需要在增加安全性的同时权衡可靠性、面积和功耗等实际约束。5.3 PLAnCo框架的局限与边界必须指出我们的框架PLAnCo有其适用范围模型依赖它严格依赖于线性可加延迟模型。任何显著偏离此模型的PUF其DFA表示可能不存在或规模巨大我们的分析不再直接适用。二进制响应目前主要针对产生二进制响应的PUF。对于多值输出PUF需要扩展DFA到更一般的自动机模型。理论边界 vs. 实际攻击PAC上界是一个最坏情况下的理论保证。实际建模攻击如神经网络、逻辑回归可能更高效但也可能受限于局部最优。而我们的工作提供了在任何分布下都成立的、形式化的安全下限。这项工作的最终价值或许不在于宣告某一类PUF的“死刑”而在于为硬件安全社区提供了一个强大的形式化分析工具。在流片之前设计者就可以用PLAnCo框架评估新PUF架构对抗形式化学习攻击的潜在鲁棒性从而更早地识别安全弱点引导设计向更安全的方向演进。将安全评估从“事后实证”推向“事前证明”这正是迈向更可靠硬件安全根基的关键一步。
硬件安全新视角：基于DFA的PUF组合结构形式化可学习性分析
发布时间：2026/5/27 17:57:51
1. 项目概述当硬件指纹遇上形式化学习在硬件安全领域物理不可克隆函数PUF一直被视为构建“无密钥”密码学的希望之星。它的魅力在于直接利用芯片制造过程中无法复制的微观工艺偏差为每一颗芯片生成独一无二的“指纹”。想象一下你无需在芯片里烧录一个固定的密钥芯片本身的结构就是密钥。这对于资源捉襟见肘的物联网终端、边缘设备来说无疑是构建硬件信任根的理想方案。然而理想与现实之间总有一道鸿沟。基于延迟的PUF尤其是其鼻祖——仲裁器PUFAPUF其安全模型建立在“线性可加延迟”这一假设之上。简单来说一个n位的挑战输入控制着信号在两条对称路径中的走向最终的响应输出0或1取决于哪条路径的信号先到达仲裁器。这个过程的数学模型是线性的而这恰恰成了它的阿喀琉斯之踵。过去十几年安全研究者和攻击者之间上演了一场精彩的“攻防拉锯战”设计者不断提出新的PUF组合结构比如XOR PUF、反馈PUF、交织PUF来增加非线性而攻击者则不断升级机器学习模型用更少的挑战-响应对CRP就能成功克隆PUF的行为。这场博弈催生了一个核心问题我们能否在芯片流片之前就从理论上严格证明某种PUF设计能抵抗多大强度的建模攻击这正是“可证明学习”理论要回答的。概率近似正确PAC学习框架为我们提供了一个强大的数学工具。在这个框架下我们可以问给定一个PUF设计视为一个“概念”一个攻击者“学习者”需要多少组随机的CRP样本才能以高概率1-δ学习到一个错误率不超过ε的近似模型先前的研究已经证明基础的APUF和XOR APUF在PAC框架下用线性阈值函数LTF或决策列表DL等表示类是“可学习”的。但我们的工作向前迈进了一大步我们首次系统性地证明任意基于APUF的组合结构无论其组合方式多么复杂输出组合、输入变换、层级结构在确定性有限自动机DFA这一表示类下都是多项式时间/空间可学习的。我们提出的框架名为PLAnCo它不仅是一个理论分析工具更是一套能自动为任意PUF组合生成多项式规模DFA模型并计算其PAC可学习性上界的算法。提示理解PUF安全性的一个关键视角是“建模攻击”与“可证明安全”的对抗。建模攻击是实践中的威胁而可证明学习是从计算复杂性理论角度给出的形式化安全边界。我们的工作属于后者旨在为设计提供事前pre-silicon的理论安全评估。2. 核心挑战从组合PUF到多项式规模DFA的鸿沟将单个APUF建模为DFA已有先例其结构类似一棵深度为n挑战位数的二叉树每个状态追踪信号在特定阶段的累积延迟差。但当我们面对由多个APUF通过复杂逻辑组合而成的“超级PUF”时直接套用单个DFA的思路会立刻撞上两堵高墙。2.1 状态爆炸组合DFA的天然障碍第一个挑战直观但致命。假设我们有两个APUF各自有一个DFA表示。当它们通过一个XOR门组合时最朴素的想法是将两个DFA“并联”起来构建一个非确定性有限自动机NFA。这个NFA的每个状态是原来两个DFA状态的组合。问题在于经典的NFA转DFA算法子集构造法会导致状态数指数级增长。对于k个APUF的组合最坏情况下DFA的状态数可能达到O(2^k)量级这立刻就让“多项式规模”的梦想破灭了。为什么状态会爆炸根源在于不确定性。在组合NFA中读入一个输入符号挑战位后机器可能同时处于多个“候选状态”。为了消除不确定性子集构造法会将这组候选状态打包成一个新的DFA状态。当组合的组件很多时这些状态子集的数量是指数级的。2.2 输入分叉当每个PUF看到不同的挑战第二个挑战更为棘手。在很多高级PUF设计中比如交织PUFiPUF构成系统的多个APUF接收的挑战并不是相同的。上层PUF的响应会被插入Interpose到下层PUF的挑战位中。这意味着组合系统中不同DFA的“左语言”即到达该状态的所有前缀挑战序列完全不同。在经典的DFA组合理论中合并状态的前提是它们等价而等价的一个重要条件是具有相同的左语言。当左语言不同时状态不能简单合并。这似乎堵死了我们构建紧凑DFA的道路。2.3 我们的破局思路三大技术支柱面对这两大挑战我们提出了三个核心的技术创新它们共同构成了PLAnCo框架的基石基于“可合并状态”的精简我们观察到在APUF的DFA树状结构中许多状态在功能上是“可合并”的。即使它们来自不同的组件DFA只要它们对应相同的挑战前缀路径并且其累积延迟信息在后续计算中扮演的角色是“可互换”的那么这些状态就可以被合并而不改变自动机接受的语言。我们给出了严格的形式化引理Lemma 1来判定两个状态是否可合并其核心是检查合并后是否会产生新的、原本不被接受的语言路径。字母表编码应对输入分叉对于接收不同挑战的组件DFA我们不再强求在原始二进制字母表{0, 1}上合并它们。相反我们进行“字母表升维”。对于一个k元组合我们将每个输入符号重新定义为一个k位的向量。例如对于两个APUF的组合输入字母表从{0, 1}变为{(0,0), (0,1), (1,0), (1,1)}。这样组合DFA的每个转移就对应一个k位的挑战向量。虽然字母表大小从2变成了2^k但关键在于k是一个小的常数通常出于可靠性考虑k不会超过log(n)因此2^k仍然是n的多项式避免了根本性的指数爆炸。DFA插值处理输入变换这是处理像交织PUF这类结构的关键。当某个挑战位被另一个PUF的输出所替代时我们不是简单地将两个DFA串联。而是在主DFA对应这个挑战位的转移边上“插入”一个完整的子DFA。具体操作是移除原转移边用ε-转移空转移将原状态连接到子DFA的起始状态再将子DFA的所有最终状态和非最终状态分别用ε-转移连接到主DFA原本该挑战位为1或0时应到达的下一个状态。这个过程就像在程序的某个条件判断处插入了一个复杂的子函数调用。3. 构建多项式规模DFA从理论到实例理论需要实例来验证。我们以几种最具代表性的PUF组合结构为例展示PLAnCo框架如何一步步构建出紧凑的DFA模型。3.1 输出组合以k-XOR PUF为例k-XOR PUF是最经典的增强型PUF它将k个独立APUF的响应进行异或以增加非线性。步骤一构建ε-NFA我们为k个APUF分别构建其DFA记为DFA1, DFA2, ..., DFAk。创建一个新的起始状态S并用ε-转移连接到这k个DFA的起始状态。这形成了一个“并行”结构。接下来是关键我们需要定义最终状态。在最后一个层级第n层我们根据XOR函数的语义来标记最终状态。具体规则是如果一个状态组合中有奇数个DFA处于其自身的最终状态即响应为1那么这个组合状态就是整个k-XOR PUF的最终状态。步骤二NFA到DFA转换与状态合并这是避免指数爆炸的核心。由于所有APUF接收相同的挑战它们在各自DFA中走过的路径是完全同步的。当读入挑战位0时所有DFA都走“左分支”读入1时都走“右分支”。因此在每一层来自不同DFA但对应相同路径比如都是“左-左-右”的状态它们所携带的延迟信息虽然数值不同但在DFA的“语言接受”判定逻辑中它们所处的“相对位置”是等价的。根据我们的可合并状态引理这些状态可以被合并。合并后每个层级的状态数从k个独立状态缩减为1个组合状态该状态需要同时记录k个APUF的延迟对信息。步骤三延迟离散化实现多项式规模即使经过合并每个状态需要记录的延迟值对(α_i,1, α_i,2)仍然是连续值理论上仍有无限可能。这里我们引入一个关键的物理观察仲裁器有比较精度γ。只有当两条路径的延迟差绝对值大于γ时仲裁器才能稳定地输出0或1。因此我们可以将连续的延迟差离散化为有限的整数区间。假设延迟服从高斯分布N(μ, σ)那么n级后的累积延迟差绝大部分落在区间[nμ - 3√nσ, nμ 3√nσ]内。将其除以精度γ并取整延迟差就被离散化为[0, d]区间内的整数其中d ⌈6√nσ / γ⌉。对于一个k-XOR PUF每个状态需要存储2k个离散化后的延迟值。每个值有(d1)种可能因此每一层最多有(d1)^(2k)个可区分的状态。总共有n层所以整个DFA的状态总数上界为O(n(d1)^(2k))。由于d是n的多项式函数d ∝ √nk是常数因此整个DFA的规模是n的多项式。这就严格证明了k-XOR PUF存在多项式规模的DFA表示。3.2 输入变换组合以交织PUFiPUF为例交织PUF(ku, kl)-iPUF由上下两层XOR PUF组成上层ku-XOR PUF的响应会被插入到下层kl-XOR PUF的某个特定挑战位中。DFA插值操作假设下层的第i个挑战位被上层的输出替代。我们首先构建上层ku-XOR PUF的DFADFAu和下层kl-XOR PUF的DFADFAl。定位与切断在DFAl中找到所有在第i层对应被插入的挑战位的状态。移除这些状态原本基于输入0和1向第i1层状态的转移边。插入子DFA对于第i层的每一个状态q添加一条ε-转移指向DFAu的起始状态。这意味着当DFAl“读”到第i位时它实际上会“调用”整个DFAu来处理完整的原始挑战。结果路由DFAu处理完挑战后会到达其最后一层的某个状态。如果这个状态是DFAu的最终状态即上层响应为1则通过ε-转移跳转到DFAl中状态q在输入为1时应到达的下一个状态记为q(1)如果是非最终状态响应为0则跳转到q(0)。深度与规模分析经过插值DFA的深度增加了。DFAl先解析前i-1位然后DFAu解析全部n位最后DFAl解析剩下的n-i位。总深度变为 (i-1) (n1) (n-i) 2n1。在状态数方面由于我们应用了状态合并技术在任意一层可区分状态数由上层和下层中规模较大的那个决定即O((d1)^(2max(ku,kl)))。因此总状态数为O((2n1)(d1)^(2max(ku,kl)))仍然是多项式规模。3.3 通用构造算法我们将上述针对特定结构的构造方法抽象成一个通用算法Algorithm 1能够处理任意用PUF-G语言描述的APUF组合。PUF-G是一种形式化描述语言可以像搭积木一样定义PUF的串行、并行和条件组合。算法核心是递归下降的DFA构建过程解析将PUF-G描述解析成模块化结构树。递归构建对每个基本APUF模块生成其基础DFA模板。组合根据模块间的连接关系输出组合、输入变换调用相应的ComposeDFAOut或ComposeDFAInput函数利用前述的合并、编码、插值技术进行DFA组合。化简对组合产生的NFA应用子集构造法转换为DFA并持续检测和合并等价状态最终输出最小化的多项式规模DFA。这个算法可以无缝集成到现有的PARLE-G框架中实现从PUF设计描述到可学习性上界计算的自动化流程。4. PAC可学习性上界计算与实验验证有了多项式规模的DFA表示我们就可以将其代入PAC学习理论计算出攻击者成功建模所需CRP数量的理论上界。4.1 理论边界推导PAC学习的核心是样本复杂度。对于DFA表示类一个经典结论Angluin, 1987是如果一个目标概念可以用一个状态数为N的DFA表示那么存在一个学习算法最多需要O(N (1/ε)(N log(1/δ) N²))次查询成员查询就能以至少(1-δ/2)的概率学习到一个ε/2近似的假设。我们将之前推导出的各类PUF组合的DFA状态数N代入这个公式就得到了它们的PAC可学习性上界。下表总结了部分关键结果PUF 构造类型DFA 深度每个状态追踪的延迟参数数量DFA 总状态数上界 (N)PAC 样本复杂度上界 (大O表示)APUF(基准)n2O(n(d1)²)O(n(d1)² (1/ε)(n(d1)² log(1/δ) n²(d1)⁴))k-XOR PUF(输出组合)n2kO(n(d1)^(2k))O(n(d1)^(2k) (1/ε)(n(d1)^(2k) log(1/δ) n²(d1)^(4k)))(ku, kl)-iPUF(输入变换)2n12*max(ku,kl)O(n(d1)^(2*max(ku,kl)))与k-XOR类似但n替换为2n1反馈PUF (FF-APUF)nin2O((nin)(d1)²)与APUF类似深度增加循环PUF (Rec-APUF, θ次迭代)nθ(n1)2k (若核心为k-XOR)O((1θ)n(d1)^(2k))深度线性增加状态数多项式增加LPPUF (层级结构)O(n²)2m (m为第一层APUF数)O(n²(d1)^(2m))深度变为平方级状态数相应增加核心洞见输出组合的影响主要增加状态中追踪的参数数量从2到2k导致状态数上界中的指数基(d1)的指数变大但深度不变。这使得样本复杂度随k多项式增长但与使用的具体布尔组合函数XOR、Bent函数等无关。这是DFA表示区别于LTF表示的一个重要优势。输入变换的影响主要增加DFA的深度从n到2n1、nθ(n1)等导致样本复杂度随深度线性增加。闭合性一个关键结论是基于APUF的组合无论经过多少层上述操作其DFA表示规模始终是多项式级的因此其PAC可学习性上界也始终是多项式级的。这意味着仅通过组合APUF无法获得指数级的安全增益来抵抗基于DFA的PAC学习攻击。4.2 实验验证模拟与FPGA实测为了验证理论边界的现实可行性我们在PyPUF仿真框架和实际FPGA实现上进行了实验。仿真实验设置 我们修改并集成了Angluin的L算法实现用于学习模拟PUF实例的DFA。L算法通过向“教师”即PUF仿真器发起成员查询“这个挑战的响应是1吗”和等价查询“我当前学到的DFA对吗”来逐步逼近目标DFA。我们设定了学习参数ε0.01精度和δ0.1置信度。实验结果 我们对16位和32位挑战长度的多种PUF构造进行了建模攻击结果如下表所示PUF 类型参数无噪声噪声水平0.01噪声水平0.054-XOR APUFn1699.8%98.5%95.2%4-XOR APUFn3299.5%97.8%93.7%(1,4)-iPUFn1699.6%98.1%94.8%LPPUFn16, m498.9%96.3%91.5%注意噪声水是PyPUF中模拟环境扰动的参数0.01和0.05代表不同程度的响应不可靠性。实验表明即使在有噪声的现实条件下攻击仍然有效只是达到相同精度所需的查询次数会增加。FPGA实验 我们在FPGA上实现了64位挑战的4-XOR和8-XOR APUF并采集了真实的CRP数据。使用L算法进行学习在约10,000次等价查询内建模准确率分别达到了81%和81.2%。一个重要的观察是实际学习到的DFA大小远小于我们理论分析推导出的DFA表示上界。理论DFA证明了此类模型“存在”且规模可控而L算法在实践中找到了更紧凑的、功能近似的DFA。这解释了为何实际所需的CRP数量远低于理论样本复杂度上界但也同时意味着这些PUF在实际中可能比理论最坏情况更脆弱。5. 安全启示与设计反思我们的研究得出了一个或许令人沮丧但必须正视的结论在线性可加延迟模型的假设下任何基于APUF或类似延迟链的组合构造都无法在PAC学习框架下获得超越多项式级别的安全性。攻击者总能在多项式数量的CRP样本内以高概率学习到一个足够准确的模型。5.1 对现有PUF设计策略的重新评估根据可学习性上界我们可以将各类PUF组合划分到不同的复杂度类别中如图15所示Class 1基础APUF深度n追踪2个延迟参数。Class 2输出组合如XOR PUF深度n追踪2k个参数。Class 1a/2a在Class 1/2基础上引入输入变换如iPUF深度线性增加。Class 3交叉路径比较结构如DAPUF深度n但追踪k(k-1)/2个延迟对。这些类别之间的边代表了组合操作带来的复杂度变化。一个关键的发现是除了Class 1其他类别都有“自循环”这意味着在同一类别内的进一步组合例如将多个iPUF再组合不会改变其关于挑战长度n和组件数量k的渐进复杂度级别。这揭示了当前主流增强策略的局限性它们只能带来多项式级别的安全提升无法实现指数级的“安全跃迁”。5.2 未来安全PUF的设计方向既然基于线性延迟模型的组合之路似乎走到了尽头那么安全的下一代PUF应该朝向何处我们的分析指出了几个可能的方向打破线性可加延迟模型这是根本性的解决方案。需要引入本质的非线性物理效应使得延迟无法被建模为挑战位的线性加权和。例如利用电路中的振荡器频率、存储器单元的亚稳态等非线性特性。引入非二进制输出当前DFA建模依赖于二进制响应。如果PUF输出是多值或模拟量并且最终响应依赖于多个阈值比较那么简单的DFA模型可能不再适用需要更复杂的表示类。探索非基于延迟的熵源例如基于SRAM启动值、蝴蝶PUF、光学PUF等其物理机制与延迟链完全不同可能天生具有更高的建模复杂度。设计指数级膨胀的自动机有意识地将PUF设计成其最小DFA表示的大小随参数指数级增长。但这需要在增加安全性的同时权衡可靠性、面积和功耗等实际约束。5.3 PLAnCo框架的局限与边界必须指出我们的框架PLAnCo有其适用范围模型依赖它严格依赖于线性可加延迟模型。任何显著偏离此模型的PUF其DFA表示可能不存在或规模巨大我们的分析不再直接适用。二进制响应目前主要针对产生二进制响应的PUF。对于多值输出PUF需要扩展DFA到更一般的自动机模型。理论边界 vs. 实际攻击PAC上界是一个最坏情况下的理论保证。实际建模攻击如神经网络、逻辑回归可能更高效但也可能受限于局部最优。而我们的工作提供了在任何分布下都成立的、形式化的安全下限。这项工作的最终价值或许不在于宣告某一类PUF的“死刑”而在于为硬件安全社区提供了一个强大的形式化分析工具。在流片之前设计者就可以用PLAnCo框架评估新PUF架构对抗形式化学习攻击的潜在鲁棒性从而更早地识别安全弱点引导设计向更安全的方向演进。将安全评估从“事后实证”推向“事前证明”这正是迈向更可靠硬件安全根基的关键一步。
