基于组合测试的硬件木马黑盒定位：从原理到高效算法实践

1. 项目概述

在集成电路（IC）设计制造的全球化链条中，硬件安全正成为一个日益严峻的挑战。想象一下，你设计了一款用于金融加密或关键基础设施的芯片，经过层层验证，功能完美。然而，在某个你无法完全掌控的海外代工厂生产环节，一个微小的、恶意的电路模块被悄然植入。这个模块平时静默无声，只有当接收到一组特定的、极其罕见的输入信号组合时才会被激活，可能窃取密钥、篡改数据甚至直接瘫痪系统。这就是硬件木马的威胁。传统的功能测试或随机测试，面对海量的输入组合（例如一个128位AES加密模块的输入空间高达2^128），犹如大海捞针，几乎不可能命中那个精心设计的、罕见的“触发密码”。我们的核心任务，就是从这近乎无限的可能性中，高效、精确地找出这个致命的“密码组合”。

我从事硬件安全测试多年，见过太多因为检测手段不足而导致的潜在风险。硬件木马的检测难，定位更难。很多方法要么需要完整的网表（这在黑盒测试场景中无法获得），要么依赖侧信道分析，对环境敏感且成本高昂。今天要分享的，是一种基于组合测试理论的纯逻辑测试方法。它不关心芯片内部的具体结构，只关注输入与输出的逻辑关系，通过精心设计的、具有特定数学性质的测试向量集，不仅能发现木马的存在，更能像侦探一样，从测试结果中逆向推理，唯一确定是哪些输入位、在什么取值下触发了木马。这种方法将组合测试中的故障定位概念与硬件木马检测相结合，为黑盒环境下的硬件安全验证提供了一种全新的、强有力的工具。

2. 核心原理：从组合测试到硬件木马定位

2.1 组合测试与覆盖阵列：系统性的“组合拳”

要理解我们的方法，首先要明白组合测试在做什么。它不是盲目地测试所有可能的输入（那是指数爆炸的），而是系统性地覆盖所有参数间的交互。举个例子，假设一个系统有3个布尔输入A、B、C，完全测试需要2^3=8个用例。但组合测试认为，很多缺陷是由少数几个参数（比如2个）的特定组合引发的。一个强度为2的覆盖阵列（Covering Array, CA）会生成一组测试用例，确保任意两个参数（如A和B， A和C， B和C）的所有4种取值组合（00, 01, 10, 11）都至少出现一次。对于3个布尔参数，一个最小化的强度为2的覆盖阵列可能只需要4个测试用例，而不是8个。

在数学上，一个覆盖阵列 CA(N; t, k, v) 是一个 N x k 的矩阵，其中 k 是参数个数，v 是每个参数取值的个数（我们通常处理v=2的布尔情况），t 是测试强度。这个矩阵满足：任意挑选 t 列，所有可能的 v^t 种组合都在这些列对应的行中出现过至少一次。对于硬件木马检测，我们可以将芯片的128位输入（明文或密钥）看作128个布尔参数。一个由 ℓ 个特定输入位及其特定取值构成的触发模式，正好对应一个ℓ-way交互。如果我们使用一个强度 t ≥ ℓ 的覆盖阵列作为测试集，那么任何长度不超过 ℓ 的触发模式，都必然会被至少一个测试向量所“覆盖”（即激活）。这就保证了检测的完备性。

注意：这里存在一个关键权衡。测试强度 t 的选择决定了我们能检测的木马触发模式的最大长度 ℓ。t 越大，能覆盖的触发模式长度越长，但所需的测试用例数量 N 也会增长。实践中，基于“小触发”假设（攻击者倾向于使用少量输入位以保持隐蔽），通常选择 t=6 或 8 就能有效覆盖绝大多数可能的木马。

2.2 从检测到定位：检测阵列的“指纹”能力

覆盖阵列能确保触发木马，但它只能告诉我们“测试失败了”，却无法告诉我们“是哪个模式导致失败”。如果多个测试都失败，我们无法直接区分是同一个木马被多次触发，还是存在多个木马。这就需要更强大的数学工具：检测阵列。

检测阵列是覆盖阵列的增强版，它具备“故障隔离”能力。一个 (d, t)-检测阵列 不仅能覆盖所有 t-way 交互，还具有这样的性质：对于任意不超过 d 个的故障交互集合，都能通过测试结果的“指纹”（即哪些测试通过、哪些失败）将其唯一地识别出来。在我们的场景中，d=1（通常假设一次只定位一个木马），t 是我们关心的最大交互强度。

其核心原理在于测试向量的差异性设计。对于任何一个非触发模式，检测阵列都保证至少存在一个通过的测试用例覆盖了它；而对于触发模式，所有覆盖它的测试用例都会失败。更重要的是，对于触发模式所涉及的那些特定输入位，在所有失败的测试用例中，这些位的值是完全一致的；而对于其他非触发位，至少能在某些失败的测试用例中找到值不一致的情况。这就为我们快速定位提供了可能。

2.3 方法映射：将硬件问题转化为组合问题

现在，我们将硬件木马定位问题形式化地映射到组合测试框架中：

1. 系统参数：待测电路（如AES模块）的128位主输入，映射为128个布尔参数（k=128, v=2）。
2. 故障模型：硬件木马的触发模式，即一个由 ℓ 个特定输入位及其特定取值（0或1）构成的集合，映射为一个ℓ-way 故障交互。
3. 测试集：一个预先计算好的、满足 (1, t)-检测阵列性质的二进制矩阵，其中每一行是一个128位的测试向量（明文或密钥）。
4. 测试预言：一个“黄金模型”（Golden Model），可以是可信的软件实现或已知良好的硬件。对每个测试向量，比较待测电路与黄金模型的输出。一致则标记为“通过”，不一致则标记为“失败”。
5. 定位目标：根据这个标记了“通过/失败”的测试集，运用检测阵列的数学性质，逆向推导出唯一的故障交互，即木马的触发模式（哪些位？什么值？）。

这种方法的核心优势在于其黑盒性和完备性保证。我们不需要知道芯片内部的网表或布局，只需要能施加输入和观察输出。只要木马的触发模式长度不超过我们预设的强度 t，并且测试集满足检测阵列的性质，我们的算法就保证能将其精确定位出来。

3. 定位算法详解：从暴力枚举到高效求解

拿到带有通过/失败标记的测试集后，如何从中提取出触发模式？我们探讨三种算法，其效率和适用场景截然不同。

3.1 算法一：基于全枚举的慢速定位

这是最直观的思路。既然所有“通过”的测试用例都不包含触发模式，那么触发模式必然不在这些测试用例所覆盖的所有 ℓ 位模式之中。

算法步骤：

1. 初始化一个集合 T，包含所有可能的 ℓ 位触发模式（共有 C(128, ℓ) * 2^ℓ 个，这是一个天文数字）。
2. 遍历每一个“通过”的测试向量 p。
3. 对于 p 所覆盖的每一个 ℓ 位模式 τ（即从128位中任选ℓ位，取其在该测试向量中的值），将 τ 从集合 T 中移除。
4. 遍历结束后，集合 T 中剩余的模式就是潜在的触发模式。

原理与局限： 这个算法逻辑正确。如果测试集是一个 (1, ℓ)-检测阵列，那么算法结束时 T 中将恰好剩下一个模式，即真正的触发模式。因为检测阵列的性质保证了每一个非触发模式都至少被一个“通过”的测试覆盖过，从而被剔除。 然而，其计算复杂度是灾难性的。它需要枚举所有可能的 ℓ 位模式，对于 ℓ=8，模式数量超过 10^12 量级。同时，对于每个“通过”的测试，还要检查它覆盖了哪些模式。这使得该算法仅适用于理论分析或极小的 ℓ，不具备实际可操作性。

3.2 算法二：基于半枚举的改进定位

算法一做了大量无用功，因为它从全部模式空间开始剔除。算法二进行了优化：既然触发模式必然被所有“失败”的测试覆盖，那么我们可以从一个“失败”的测试向量入手。

算法步骤：

1. 随机选取一个“失败”的测试向量 f。
2. 生成该向量 f 所覆盖的所有 ℓ 位模式，构成初始候选集 T_f。这个集合的大小是 C(128, ℓ)，虽然仍很大，但比全空间小得多（因为不需要考虑2^ℓ的取值组合，取值已由 f 确定）。
3. 遍历候选集 T_f 中的每一个模式 τ。
4. 检查 τ 是否被任何一个“通过”的测试向量 p 所覆盖。如果是，则 τ 不可能是触发模式，将其从 T_f 中移除。
5. 遍历结束后，T_f 中剩余的模式即为定位结果。

效率分析： 算法二的初始候选集远小于算法一。在理想情况下（检测阵列），它最终也能定位到唯一的模式。其平均时间复杂度取决于“通过”测试的数量和候选集大小。虽然比算法一有提升，但当 ℓ 较大时，C(128, ℓ) 依然巨大，计算仍然非常耗时。

3.3 算法三：基于共享模式的高效定位（核心算法）

这是本文提出的高效算法，也是工程实践中推荐使用的方法。它完全避免了枚举 ℓ 位模式，复杂度与 ℓ 几乎无关。

算法核心洞察：

1. 一致性：触发模式必须被所有“失败”的测试向量覆盖。因此，对于触发模式所涉及的每一个输入位，在所有“失败”的测试向量中，该位的值必须完全相同。
2. 差异性：对于任何不参与触发模式的输入位，由于检测阵列的构造性质，我们可以在“失败”的测试向量集合中，找到至少两个在该位上取值不同的向量。否则，该位就会被错误地纳入触发模式。

算法步骤：

1. 收集所有“失败”的测试向量，构成集合 F。
2. 初始化一个空的触发模式 τ。
3. 遍历128个输入位的位置 i (从1到128)：
   • 检查集合 F 中所有测试向量在第 i 位上的值是否一致。
   • 如果完全一致，则将(i, 该一致的值)加入到触发模式 τ 中。
4. 遍历结束后，τ 即为定位到的触发模式（包含位置信息和取值）。

复杂度与优势： 算法的时间复杂度仅为 O(|F| * k)，其中 |F| 是失败测试的数量，k 是输入位数（128）。这比前两种算法指数级的复杂度有了质的飞跃。例如，定位一个 ℓ=8 的木马，算法三平均仅需约0.2秒，而算法一在 ℓ=4 时就需要数秒，ℓ=5 以上就不可行了。

实操心得：算法三的成功完全依赖于测试集是 (1, t)-检测阵列且 t ≥ ℓ。如果使用随机生成的测试集，失败测试向量在所有位上值都一致的情况可能不止出现在触发位，还会出现在许多无关的位上，导致算法返回一个过长的、错误的模式。因此，测试集的组合性质是该方法有效的基石，不能随意用随机向量替代。

4. 实验验证与对比分析

我们以128位密钥的AES-ECB加密模块为实验对象，在其Verilog代码中植入了不同长度（ℓ 从1到8）、不同位置、不同取值模式的组合型硬件木马。木马的触发电路由AND和NOT门构成，有效载荷是翻转加密/解密模式控制信号。

4.1 测试集构建

我们生成了系列组合测试集 CT_ℓ，它们实际上是 (1, ℓ)-检测阵列（同时也是强度为 ℓ+1 的覆盖阵列）。作为对比，我们生成了两组随机测试集：

• rand(CT_ℓ)：与 CT_ℓ 测试集行数相同的随机二进制矩阵。
• randN(CT_ℓ)：行数与当前已知最优的 (1, ℓ)-检测阵列相同的随机二进制矩阵（通常比 CT_ℓ 更小）。

4.2 定位能力对比

我们使用算法三进行定位，结果清晰展示了组合测试方法的优势：

1. 完备性保证：对于任何长度 ℓ ≤ 8 的木马，使用 CT_ℓ 测试集都能100%成功触发并精确定位。无论木马触发位是分散在地址空间的哪些位置，也无论触发值是全1、全0还是混合模式，CT_ℓ 测试集配合算法三都能无误地返回正确的位和值。
2. 随机测试的不可靠性：使用 rand(CT_ℓ) 或 randN(CT_ℓ) 测试集，定位成功率无法保证。实验表明，对于 ℓ=4 的情况，rand(CT_ℓ) 可能会漏掉超过10%的触发模式；而更小的 randN(CT_ℓ) 漏报率更高。随机测试集有时也能定位成功，但这依赖于运气，而非数学保证。在实际安全攸关的场景中，这种不确定性是不可接受的。
3. 对更长木马的探测能力：一个有趣的发现是，CT_5 测试集（为定位长度≤5设计）有时也能成功定位 ℓ=8 的木马。这是因为 CT_5 作为一个强度为6的覆盖阵列，其结构可能偶然满足了定位更长模式所需的部分条件。但这并非保证。只有使用 CT_8 测试集，才对所有 ℓ≤8 的木马提供完备的定位保证。

4.3 性能与资源消耗

测试集类型	设计目标 ℓ	测试向量数量 (N)	定位算法	平均定位时间 (ℓ=8)	是否提供完备性保证
CT_ℓ (组合测试)	1-8	几十到几百量级	算法三	~0.23 秒	是
rand(CT_ℓ) (随机)	无	同 CT_ℓ	算法三	相近，但结果可能错误	否
穷举测试	任意	2^128 (不可行)	直接比对	不可计算	是（理论上）

从上表可以看出，组合测试方法在测试集大小（测试时间）和定位可靠性之间取得了极佳的平衡。虽然 CT_ℓ 的测试向量数量比仅用于检测的覆盖阵列要多（为了获得定位能力需要额外的结构），但它相比穷举法仍然是微不足道的，并且提供了随机测试无法比拟的确定性。

注意事项：测试向量的数量 N 随着参数 k 和强度 t 的增长而近似对数增长，这使得该方法能够扩展到具有大量输入的系统。生成最优的检测阵列本身是一个组合优化问题，可以使用如模拟退火、贪心算法或数学构造法等工具离线完成。一旦生成，测试集可以重复用于测试同一型号的所有芯片。

5. 方案局限性与未来扩展

5.1 当前方法的假设与局限

我们的方法建立在几个关键假设之上，理解这些局限对于正确应用至关重要：

1. 组合型触发：木马触发条件必须是主输入位上纯组合逻辑（AND/OR/NOT）的函数，不涉及内部状态或时序逻辑（如计数器）。这是方法的核心前提。
2. 黑盒与黄金模型：需要能够控制所有待测输入，并有一个可信的“黄金模型”来判定输出是否正确。对于某些无法获得黄金模型的场景（例如，完全未知的第三方IP核），此方法不适用。
3. 触发模式长度上限 t：测试者需要预先估计一个可能的最大触发长度 ℓ_max，并据此选择测试强度 t ≥ ℓ_max。如果实际木马的触发长度超过了 t，则无法保证定位。这要求测试者基于对攻击者动机和能力的风险评估来做出选择。
4. 单木马定位：算法三主要针对定位单个木马设计。虽然理论上 (d, t)-检测阵列可以定位最多 d 个木马，但生成此类阵列和设计对应的定位算法更为复杂。

5.2 与其他检测技术的融合

本方法并非要取代其他硬件安全技术，而是与之互补，形成更强大的防御体系：

• 与侧信道分析结合：组合测试向量可以作为一种最优的激励生成器，用于驱动功耗分析或电磁辐射分析。传统的侧信道分析需要大量随机或特定向量来凸显木马活动与正常活动的差异。而我们的测试集能系统性地遍历输入组合，确保任何小规模组合触发的木马都能被激活，从而可能产生更显著的侧信道信号差异，再结合定位算法，实现“激励-采集-定位”的闭环。
• 与网表分析结合：对于有网表的白盒或灰盒场景，可以先使用概率分析、可控性/可观性分析或电路结构分析（如[37]中的方法）筛选出可疑节点集合。这些节点可能具有稀有信号特性或布局上的便利性。然后，我们的方法可以不再针对全部128个主输入，而是针对这个缩小后的可疑节点集合（可能只有几十个）构建检测阵列。这能大幅降低测试强度 t 的要求或显著减少测试向量数量，实现更精准的定位。
• 与片上传感器结合：在芯片内部布置环形振荡器等传感器来监测局部电路活动。将组合测试向量施加到电路上，通过传感器读取活动指纹。当木马被激活时，其附近的传感器会检测到异常。通过分析哪些测试向量导致了哪些传感器的异常，可以辅助定位木马所在的物理区域。

5.3 未来研究方向

基于当前工作，有几个有前景的扩展方向：

1. 定位更复杂的触发逻辑：当前方法针对由AND/NOT门构成的“与-非”形式触发电路。一个自然的扩展是处理包含OR门的触发逻辑。例如，一个触发条件为(A and not B) or (C and D)的木马，其触发模式对应两个故障交互的并集。这可以映射为定位多个故障交互的问题，需要使用 (d, t)-检测阵列（d>1）。虽然理论可行，但生成能高效定位多个交互的检测阵列是一个开放的算法挑战。
2. 处理时序型硬件木马：许多硬件木马是时序的，例如由计数器或有限状态机触发。这需要将组合测试扩展到序列覆盖阵列。测试向量不再是一个静态的输入组合，而是一个输入序列。我们需要生成能覆盖特定长度内所有事件序列组合的测试集，以触发基于状态的木马。
3. 构建自动化测试框架：将测试集生成、测试执行（通过JTAG或功能接口）、结果收集、黄金模型比对以及定位算法集成到一个自动化工具链中。这将极大降低该方法的使用门槛，使其能够被集成电路测试工程师直接应用。
4. 研究最优检测阵列构造：寻找行数更少（即测试用例更少）的 (1, t)-检测阵列和 (d, t)-检测阵列。这直接关系到测试成本。利用群论、编码理论或搜索优化算法（如SAT求解器）来寻找更优的构造，是一个具有理论和实践价值的数学问题。

6. 总结与工程实践建议

回顾整个流程，基于组合测试的硬件木马定位方法提供了一条清晰的技术路径：首先，根据对潜在威胁的分析（例如，假设攻击者最多能操控8个输入位），确定测试强度 t（例如 t=8）。接着，离线生成或从库中选取一个针对128位二进制参数的 (1, t)-检测阵列作为测试集。然后，在测试平台上，将测试集中的每一个向量作为输入，同时施加给待测芯片和黄金模型，比较输出结果，标记通过/失败。最后，运行高效的算法三，直接分析失败测试向量在各个位上的取值一致性，在毫秒级时间内输出触发模式的具体位置和数值。

在实际项目中应用该方法，我总结出以下几点心得：

1. 强度选择是门艺术：不要盲目追求高 t 值。t=6 能覆盖绝大多数学术论文和基准测试中的木马模型。t=8 则提供了很高的安全余量。t 每增加1，测试集大小可能会显著增长。需要结合项目安全等级、测试时间预算和风险评估来权衡。
2. 黄金模型的可靠性是关键：任何输出比对错误都会导致定位失败。确保你的黄金模型（无论是软件仿真、FPGA参考设计还是已知良品芯片）是绝对可信的。在测试开始前，用大量随机向量对黄金模型和待测模型进行一致性校验是个好习惯。
3. 理解“定位”的含义：我们定位的是逻辑触发条件，即“哪些输入位在什么值时会导致木马激活”。这并不意味着我们知道了木马在物理版图上的确切位置或它的具体电路结构。但它提供了至关重要的信息：我们可以通过避免使用这些触发模式来安全地使用芯片（尽管功能受限），或者为后续的物理失效分析（如FIB）提供精确的切入点。
4. 方法适用于更广泛的“参数”：虽然本文以AES的128位主输入为例，但方法的本质是通用的。这里的“参数”可以是任何可独立控制且可能被木马利用的信号线，例如配置寄存器、控制引脚、甚至某些经过筛选的内部节点（如果可观测）。这大大扩展了方法的适用场景。

最后，我想强调的是，硬件安全没有银弹。基于组合测试的定位方法为我们提供了一种系统化、可证明、高效率的黑盒检测与定位工具。它特别适合在流片后、封装前的芯片验收测试，或在无法获得设计细节的第三方IP核集成验证阶段使用。将它与白盒分析、侧信道检测等技术结合，形成多层次、跨阶段的硬件安全验证策略，才能构筑起真正坚固的硬件安全防线。