现代集成电路的设计和制造依赖于涉及多个方的全球化供应链。虽然这种合作加速了产品开发周期，但也引入了潜在的安全风险。例如，工程师经常直接集成第三方网表IP，这可能导致安全威胁，如篡改攻击[1]、IP侵权[2]和硬件木马[3]。网表逆向工程（Netlist Reverse Engineering, RE）有助于用户理解未知门级网表的功能，是恢复供应商之间信任的常用方法[[4], [5], [6]]。网表RE分为组合逻辑RE和顺序逻辑RE。组合逻辑RE的任务包括边界检测和算术模块的功能识别[7]，而顺序逻辑RE则专注于识别未知电路的控制逻辑。鉴于许多攻击和防御策略都围绕电路的控制路径展开，本文重点讨论顺序逻辑RE。
电路中的控制路径通常由有限状态机（Finite State Machines, FSMs）实现，这些 FSMs由形成状态寄存器的D触发器（Data Flip-Flops, DFFs）组成。因此，高效准确地检测状态寄存器有助于理解未知门级网表的功能[8]。然而，从包含数百万逻辑门的网表中提取状态寄存器并非易事，通常面临四个挑战：1）负责控制逻辑的状态DFF与用于数据存储的数据DFF混在一起；2）网表中逻辑门的规模限制了检测方法的准确性和运行效率；3）网表中可能存在结构类似于状态寄存器的算术逻辑模块；4）与可以使用模板匹配[9]或行为匹配[10]等技术检测的算术模块不同，状态寄存器通常用于控制不同的电路功能，使得这些方法不适用。
已经提出了许多检测网表中状态寄存器的方法，这些方法可以分为两类：基于图论的方法和基于GNN的方法。RELIC系列[[11], [12], [13]]作为典型的基于图论的方法，通过比较寄存器的输入电路（fan-in circuits）的相似性来区分状态寄存器和数据寄存器。然而，这种方法需要为每个单独的网表探索不同的配置参数，计算成本较高，仅适用于小规模网表。其他基于图论的研究[[14], [15], [16], [17], [18], [19]]根据反馈路径的存在来确定状态寄存器。在反馈路径存在的基础上，开发了各种技术来提高检测准确性，例如进一步根据寄存器的输出是否连接到控制信号来进行过滤。然而，这些方法的准确性仍然不足。尽管与RELIC系列相比，它们在执行速度和网表大小方面有所改进，但仍然无法处理大规模网表。
在过去五年中，GNN已被广泛应用于与网表相关的任务[[20], [21], [22], [23]]，使得使用GNN检测状态寄存器成为可能。ReIGNN [24]将状态寄存器的检测表述为一个二分类问题，即在状态DFF和数据DFF之间进行分类，并首次将GNN应用于此任务，实现了更短的推理时间和处理大规模网表的能力。然而，ReIGNN的真正阳性率仍然不足，大量数据DFF被错误地分类为状态DFF，导致较高的假阳性率。因此，ReIGNN需要后处理来纠正这些错误分类。此外，所有上述状态寄存器检测方法——无论是基于图论的还是基于GNN的——除了RELIC-FUN——都没有考虑网表的功能特征。即使在RELIC-FUN中，也只考虑了输入电路中4个可行片内的布尔函数匹配。我们在第III.A节中概述了现有的状态寄存器检测方法。
限制GNN性能的主要问题是过度平滑（over-smoothing）[25]和过度压缩（over-squashing）[26]。在网表的背景下，这意味着GNN只能提取子电路级别的特征，无法捕捉逻辑门之间的长距离依赖关系。图变换器（Graph Transformers, GTs）[27]利用变换器的注意力机制，能够有效捕捉这种长距离依赖关系。然而，注意力的计算复杂度与图中节点的数量成二次方关系，使得GTs不适合处理大规模图。我们尝试将GTs [28,29]应用于网表，发现当逻辑门数量超过6K时，在具有64 GB RAM的系统上会发生内存错误——这远远低于实际网表的规模。为了使GTs能够应用于大规模图，一些研究专注于简化注意力计算以降低计算复杂度[[30], [31], [32], [33], [34], [35], [36], [37], [38]]，而其他研究则旨在通过基于拓扑的采样策略[39], [40], [41], [42]降低硬件要求。我们在第III.D节中进行了详细讨论。然而，迄今为止，还没有公开的研究将GTs应用于识别状态DFF。此外，无论是基于自适应的方法还是基于采样的方法，都忽略了顺序网表作为有向循环图的固有特性，从而无法完全捕捉它们的结构和功能特征。
在本文中，我们提出了一种基于GT的方法FSMformer，它结合了局部模块和全局模块，同时提取顺序网表的结构和功能特征，从而实现对大规模网表中状态DFF的高效准确检测。具体来说，我们的贡献有三个方面。
- 1)
数据集：目前没有公开可用的用于寄存器检测任务的网表数据集。我们收集了10个常用功能块的RTL实现，并通过逻辑综合生成了专门的网表数据集。每个网表在保持其功能的同时进行了全局结构修改。此外，我们开发了一个名为PyNetlist2的网表处理工具，以促进顺序网表转换为图表示。数据集和PyNetlist2都将在指定的网站上开源[43]。
- 2)
局部模块：FSMformer使用定制的GNN作为局部模块来生成逻辑门的局部表示。考虑到顺序网表本质上是有向循环图而非无向图，因此定制的GNN是一个双向消息传递神经网络，可以同时提取网表的功能和结构特征。双向消息传递利用与电路中信号传播方向一致的前向消息传递来增强对网表功能的理解，以及反向消息传递来补充对网表结构的理解。
- 3)
全局模块：FSMformer使用基于变换器的架构作为全局模块来生成逻辑门的全局表示。全局模块不仅捕捉网表中的长距离依赖关系，还减轻了局部模块中存在的过度平滑和过度压缩问题。为了克服传统注意力机制在网表可扩展性方面的限制，全局模块采用了线性注意力机制，显著降低了计算复杂度。为了捕捉信号从主输入（Primary Inputs, PIs）到主输出（Primary Outputs, POs）的传播特性，我们采用了多量子位磁位置嵌入（Multiple-Q Magnetic Positional Embedding, PE）来增强全局模块对信号传输方向的感知，从而提高其对网表功能的理解。
实验结果：与现有的基于图论的最先进方法FSMX-ultra相比，我们提出的FSMformer在状态DFF检测的准确性上提高了14%。与现有的基于GNN的最先进方法ReIGNN相比，FSMformer在状态DFF检测的准确性上提高了3.13%。此外，几种先进的GNN和GTs首次被应用于状态寄存器检测作为基线模型。实验结果表明，FSMformer是唯一在状态DFF和数据DFF上都取得高准确性的模型。此外，我们进行了消融研究以验证双向消息传递、全局线性注意力和多量子位磁位置嵌入的有效性。
本文的其余部分组织如下。第II节介绍了本研究涉及的基本概念。第III节讨论了现有的状态寄存器检测方法及其局限性、网表表示方法及其相应约束、有向GNN的当前研究现状以及大规模图挑战下的GTs最新进展。第IV节详细介绍了我们提出的方法。第V节描述了验证我们方法优越性的实验结果。最后，第VI节总结了本文。
