一种针对非完备门级网表的高精度硬件后门检测方法

1.本发明涉及领域为硬件安全领域，针对当前芯片逆向工程技术得出的非完备门级网表，提出了一种高精度硬件后门检测方法，增强了硅后芯片硬件后门检测技术的通用性，为硅后硬件后门检测提供了新思路。


背景技术：

2.在过去二十年中，由于半导体供应链的全球化和计算设备无处不在的网络连接，硬件安全和信任已成为一个紧迫的问题。硬件后门由其隐蔽性的特点在传统芯片验证测试阶段难以被发现，加之硬件后门的负载可任意选取因此赋予了攻击者极大的攻击自由从而使得硬件后门造成的损失难以估量。
3.当前，硬件后门检测技术根据检测的执行阶段可分为硅前(pre-silicon)检测与硅后(post-silicon)检测。硅前检测主要针对流片生产前的硬件设计文件进行，如hdl文件、网表文件、gdsii文件等。硅前检测方法较为丰富，包括功能性验证、结构分析、代码和电路覆盖分析、形式化验证等。硅后检测主要针对流片生产后的成品集成电路芯片(ic)进行，可进一步分为非破坏性方法和破坏性方法。其中非破坏性方法包括功能测试和边信道分析。破坏性方法是对抗硬件后门的最高保障手段，通过逆向工程(re,reverse engineering)比对黄金ic或模型对ic进行可视验证，从最底层的物理结构排除硬件后门存在的可能。
4.2007年，dakshi agrawal等人在ieee symposium on security and privacy中首次提出“硬件后门”的概念，同时提出一种通过对芯片边信道设置“功耗指纹”的方式检测硬件后门的方法。2010年，美国伊利诺伊大学hicks等人提出了一种未使用的电路识别(uci)的检测方法。该方法在芯片设计时检测隐藏在电路中的恶意后门，其本质上是寻找在测试中未使用的电路部分，并将它们标记为潜在的恶意逻辑。2013年，美国哥伦比亚大学waksman等人提出基于电路真值表提取信号节点控制值特征(fanci)，进而标记木马信号节点的检测方法。2016年，美国哈佛大学hassan salmani等人将sandia可控性/可观测性分析程序(scoap)引入硬件后门检测中并结合机器学习算法提出了一种基于门级网表可控性和可观测性的无参考硬件后门检测与恢复技术(cotd)。2018年，vashistha等人提出木马扫描仪(trojan scanner)，它使用可信的gdsii布局(黄金布局)和扫描电子显微镜(sem)图像来识别在电路制造过程中对网表所做的恶意修改。2020年，stern等人使用非破坏性的后端激光探测方法检测木马。通过对两组不同的光电频率映射(eofm)图像进行比较，可以识别出木马时序器件，进而找到硬件木马时序器件(ffs)的位置。
5.ic逆向工程旨在从物理ic或掩膜数据提取出门级或功能级网表等高级抽象表示以理解或验证ic功能模型。其工艺流程包括芯片去封装、化学或等离子蚀刻、砂轮抛光、电子显微镜成相存储、图像缝合、图像识别及处理、软件自动化网表提取等步骤。随着集成电路工艺节点的突飞猛进，ic逆向工程正面临着巨大的挑战。lippmann等人提出，只要有足够的时间和资源，逆向工程可以恢复任何给定ic的构建模块，准确率高达99％，但从与硬件开
发和设计相关的商业实体角度来看，其目标不是让设计完全防止逆向工程，而是将这一过程推迟到足够长的时间，以引入完全新颖的设计和技术。因此，期望在合理的时间内，逆向工程能以100％精度完成逆向进而实现后门检测是不现实的。
6.综上所述，已知对ic的硬件后门检测方法都未从逆向工程的角度考虑非完备门级网表的问题，而本方法针对非完备门级网表实现高精度后门检测，为基于逆向工程的硅后硬件后门检测补齐了应用空白。


技术实现要素：

7.本发明提出了一种针对非完备门级网表的高精度硬件后门检测方法。该方法关注基于逆向工程的后门检测技术输入门级网表非完备的问题，无需黄金电路样本，该方法即能高精度地检测待测网表是否含有硬件后门，并给出可疑木马节点。解决了现有硬件后门检测方法无法对非完备门级网表进行检测的问题，并填补了基于逆向工程的后门检测技术应用空白。
8.本发明旨在逆向门级网表非完备(器件丢失或连线丢失)的情况下，结合ic逆向版图文件中断点的物理位置邻近关系以推理出断点间可能的逻辑连接关系，进而高精度地完成对ic的硬件后门检测。首先预处理并建模门级网表；其次识别并定位断点信号；然后针对断点信号迭代计算可测试性特征值以逼近原始完备网表中断点特征值；最后通过无监督聚类算法比较类间距离完成后门判断。本发明中，断点特征值会不断迭代以逼近原始值，因此需要从不同的初始条件开始计算可测试性特征值。本发明完整流程如图1所示。因而本发明技术方案为：一种针对非完备门级网表的高精度硬件后门检测方法，该方法包括：
9.步骤1、非完备门级网表预处理与建模；
10.首先，读取非完备门级网表文件,提取io及内部信号节点构成有向图顶点集合v＝{v1,v2,v3,,vm},集合中各顶点对象拥有信号名、驱动逻辑单元名、驱动逻辑单元类型；
11.其次，将逻辑器件输入输出信号节点对映射为有向图的边，构成边集e＝{e1,e2,e3,
…
,ei,
…ek
}；其中某边ei＝《ni,nj》表示顶点ni为某器件输入节点，且在有向图中指向同器件输出节点nj；每条边包括：边头节点名、边尾节点名、输入信号引脚名、所属逻辑器件名；
12.得到每个门级逻辑网表都映射为有向图g＝(v,e),g由顶点集v和边集e组成；
13.步骤2、断点信号识别与定位；
14.将gdsii文件导入eda(电子设计自动化)工具中，并使用eda工具对版图作设计规则检查(drc)以筛选出断线信号missnodes＝{n1,n2,
…
,nm}；其次，获取断线ni连接到器件的引脚名pins(ni)＝{p1,p2,
…
,pn}，并将ni断点类型type(ni)作式1所示分类：
[0015][0016]
其中，为空集，outpins＝{c1,so,co,s,q,qn,zn,y}，其中c1,so,co,s,q,qn,zn,y为元件库中不同器件输出引脚名；即若某断线信号未连接到任一器件引脚则记作isolate类断点信号，isolate类断点信号表示孤立类断点信号，否则若该断线信号未连接到任一器件输出引脚则记作mi类断点信号，mi类断点信号表示输入缺失类断点信号，连接到任一器
件输出引脚则记作mo类断点信号，mo类断点信号表示输出缺失类断点信号；
[0017]
最后，将非isolate类断点信号ni连接的任一逻辑器件相对于ic核心左下角的归一化坐标位置(location(ni)＝{xi,yi},xi∈[0,1],yi∈[0,1])填入断点信号的位置属性中，断点类型填入断点类型属性中；
[0018]
步骤3、迭代计算可测试性特征值；
[0019]
可测试性包括3个指标：cc0(v)、cc1(v)、co(v)即信号v的组合0可控制性、组合1可控制性、组合可观察性；
[0020]
步骤3.1：断点作io初始化；
[0021]
定义芯片输入端口集合为i,输出端口集合为o；则对各节点作式2至5的初始化操作；
[0022]
cc0(v)＝cc1(v)＝1,co(v)＝∞,v∈i∪mi
ꢀꢀꢀ
(2)
[0023]
cc0(v)＝cc1(v)＝∞,co(v)＝0,v∈o∪mo
ꢀꢀꢀ
(3)
[0024]
cc0(v)＝cc1(v)＝1,co(v)＝0,v∈isolate
ꢀꢀꢀ
(4)
[0025]
cc0(v)＝cc1(v)＝∞,co(v)＝∞,for others
ꢀꢀꢀ
(5)
[0026]
步骤3.2：计算可测试性特征值；
[0027]
首先统计信号节点的拓扑次序，使得线性时间复杂度下能有序完成信号节点特征值的计算；然后根据正向拓扑顺序即从输入到输出的顺序，计算信号节点的可控性特征；最后根据逆向拓扑顺序即从输出到输入顺序，计算信号节点的可观测性特征；
[0028]
采用kosaraju算法统计出信号节点的拓扑次序；
[0029]
逻辑门输出信号可控性指标等于将该信号置1或0所需控制的输入信号可控性指标之和的最小值加1；
[0030]
逻辑门输入信号可观测性指标等于输出信号可观测性指标加上将其他输入信号置为非控制值所需可控性指标之和的最小值再加1；
[0031]
步骤3.3：断点全局平均赋值；
[0032]
将mi类断点信号的可控性指标初始化为mo类断点信号的平均可控性，而将mo类断点信号的可观察性指标初始化为mi类断点信号的平均可观察性指标；另外，为了消除常量信号影响需对参与均值运算的信号作特征值范围检查；即对各信号作如下式6-10初始化操作；
[0033]
cc0(v)＝cc1(v)＝1,co(v)＝∞,v∈i
ꢀꢀꢀ
(6)
[0034]
cc0(v)＝cc1(v)＝∞,co(v)＝0,v∈o
ꢀꢀꢀ
(7)
[0035][0036][0037][0038]
其中，node表示单个断点信号；
[0039]
然后再计算一次可测试性指标为后续范围搜索赋值提供更为可靠的特征值；
[0040]
步骤3.4：断点范围搜索赋值；
[0041]
首先，从非孤立的断点信号出发构建一颗kd-tree；其次，对每一个mo类断点信号作一次范围搜索，将搜索得到的mi类断点信号的co特征值取平均赋给启动搜索的mo类断点信号，即式11所示；
[0042][0043]
其中,sni＝{node|node∈sn∩node∈mi∩co(node)＜∞}为搜索得到且co特征值有效的mi类断点信号集合，sn为kd-tree范围搜索返回节点集合；
[0044]
同理，对每一个mi类断点信号作一次范围搜索，将搜索得到的mo类断点信号的cc1、cc0特征值取平均赋给启动搜索的mi断点信号，如式12、13所示；
[0045][0046][0047]
其中，sno0＝{node|node∈sn∩node∈mo∩cc0(node)＜∞}为搜索得到且cc0特征值有效的mo类断点信号集合；sno1＝{node|node∈sn∩node∈mo∩cc1(node)＜∞}为搜索得到且cc1特征值有效的mo类断点信号集合；
[0048]
若未搜索到目标类断点信号则将目标类断点信号平均特征值赋给启动搜索的断点信号；
[0049]
步骤4：聚类判断；
[0050]
首先将每个信号节点的cc0与cc1特征值合并为一个特征值cc,如公式14所示：
[0051][0052]
其次，通过聚类算法将信号节点划分为3类；然后，通过类间距离判断各簇是否为木马信号节点簇；最后，报告检测结果。
[0053]
进一步的，所述步骤4的聚类方法为：
[0054]
聚类过程针对全体可控且可观察节点集n＝{n1,n2,
…
,nm}进行，首先输入各点ni∈n表示为二维特征向量的特征向量集d＝{(cc(ni),co(ni)),ni∈n}；其次，考虑到木马节点的分布特征，选择原点、最大可观测值点、最大可控制值点作为初始簇中心集合{μ1,μ2,μ3}，如式15所示：
[0055][0056]
最后，不断遍历集合d，计算ni节点对应特征向量di与各簇中心的欧氏距离d
ij
如式16，依据各点到最近簇中心距离划分簇如式17-18所示，其中λi为ni节点簇标记，为ni节点划入的节点簇；并更新簇中心位置如式19所示：
[0057]dij
＝||d
i-uj||2,di∈d,j∈{1,2,3}
ꢀꢀꢀ
(16)
[0058]
λi＝arg min
j∈{1,2,3}dij
ꢀꢀꢀꢀ
(17)
[0059][0060][0061]
直到收敛稳定到最终节点簇划分{c1,c2,c3}以及簇中心{μ1,μ2,μ3}。
[0062]
进一步的，所述步骤4中通过类间距离判断各簇是否为木马信号节点簇的方法为：
[0063]
分类判断通过设定与普通节点簇标准差相关的差异阈值，当簇间距离超过阈值则判断为木马簇；首先，依据簇中心到原点距离，从小到大将各簇标记为c1,c2,c3；其次，计算c1簇标准差σ1,如式20所示:
[0064][0065]
其中，k为c1簇节点数，μ为c1簇中心向量；设置阈值t1＝3σ1,计算c1,c2类间距离为i
12
，若i
12
》t1,则判定c2,c3都为木马节点簇；若i
12
≤t1,则判定c2为普通节点簇，并将c1,c2视作同一正常节点簇，计算c1,c2簇标准差σ2并设置新阈值t2＝3σ2以判断c3簇；计算c1,c2簇与c3簇类间距离为i
12,3
,若i
12,3
》t2则判定c3为木马节点簇,否则判定c3为普通节点簇；
[0066]
最后，将不可控或不可观察节点以及聚类判断后的木马节点簇视作木马节点报告给用户。
[0067]
本发明提出一种针对非完备门级网表的高精度硬件后门检测方法。该发明在ic逆向工程在有限资源条件下难以得到100％精确的逻辑网表的前提下，以高精度地完成硬件后门检测为目的。基于硬件后门节点的可测性特征值远大于正常节点的特征值，结合逆向工程得到的版图位置文件，通过io、全局平均、范围搜索的方式不断逼近原特征值，从而使得后续聚类判断可有效实施。实现了在网表非完备的条件下，高精度的硬件后门检测。
附图说明
[0068]
图1非完备门级网表硬件后门检测方法流程图；
[0069]
图2门级网表与有向图映射；
[0070]
图3迭代计算可测试性特征值子流程图；
[0071]
图4可测试性特征值计算流程图；
[0072]
图5基本逻辑器件可控性指标计算示意图；
[0073]
图6基本逻辑器件可观测性指标计算示意图；
[0074]
图7断点范围搜索赋值算法流程；
[0075]
图8mo类断点范围搜索赋值算法流程；
[0076]
图9mi类断点范围搜索赋值算法流程。
具体实施方式
[0077]
本发明对trust-hub样本集中的3个重点样本(rs232-t1300、s15850-t100、s35932-t100)进行实验，对每个样本随机丢失器件、线或器件线混合丢失，在不同的丢失规模(0.1％,0.5％,1％,5％)下，重复100次实验统计其中的检测正确率即平均检测率。另外，
对上述3个木马样本对应的无木马样本(rs232-tifree、s15850-tjfree、s35932-tjfree)再作100次实验以统计其中的检测错误率即平均虚警率。其中混合丢失是按指定规模同时丢失器件与线。实验结果如表中所示。
[0078]
一种针对非完备门级网表的高精度硬件后门检测方法，该方法包括：
[0079]
步骤1、非完备门级网表预处理与建模；
[0080]
网表预处理阶段目的是将抽象的逻辑网表转换为程序能使用的有向图数据模型；首先，读取非完备门级网表文件,提取io及内部信号节点构成有向图顶点集合v＝{v1,v2,v3,,vm},各顶点对象拥有信号名、驱动逻辑单元名、驱动逻辑单元类型等属性；
[0081]
其次，将逻辑器件输入输出信号节点对映射为有向图的边，构成边集e＝{e1,e2,e3,
…
,ek}；其中某边ei＝《ni,nj》表示顶点ni为某器件输入节点，且在有向图中指向同器件输出节点nj。每条边包括边头节点名、边尾节点名、输入信号引脚名、所属逻辑器件名等属性；
[0082]
因此，每个门级逻辑网表都可以映射为某一有向图g＝(v,e),g由顶点集v和边集e组成。门级网表与有向图的映射关系如图2所示。
[0083]
2、断点信号识别与定位
[0084]
该步骤通过对gdsii逆向版图文件作规则检查(drc)识别断点信号并标注出其在版图中的相对位置以应用后续的断点特征预测算法。首先，将gdsii文件导入eda工具中，并使用eda工具对版图作drc以筛选出断线信号missnodes＝{n1,n2,
…
,nm}。其次，获取断线ni连接到器件的引脚名pins(ni)＝{p1,p2,
…
,pn}，并将ni断点类型type(ni)作式1所示分类：
[0085][0086]
其中outpins＝{c1,so,co,s,q,qn,zn,y},为器件输出引脚名集合。即若某断线信号未连接到任一器件引脚则记作isolate类(孤立)断点信号，否则若该断线信号未连接到任一器件输出引脚则记作mi类(输入缺失)断点信号，连接到任一器件输出引脚则记作mo类(输出缺失)断点信号。
[0087]
最后，将非isolate类断点信号ni连接的任一逻辑器件相对于ic核心左下角的归一化坐标位置(location(ni)＝{xi,yi},xi∈[0,1],yi∈[0,1])填入断点信号的位置属性中，断点类型填入断点类型属性中以便后续范围搜索。
[0088]
3、迭代计算可测试性特征值
[0089]
可测试性(testablility)是针对测试逻辑电路的工作量或成本的相对度量指标。先前，已有研究表明木马触发电路信号节点的可测试性会远大于正常节点以达到在特定条件下触发的隐蔽性要求。本发明沿用scoap可测试性分析算法的框架，可测试性细分为可控性(controllability)与可观测性(observability)使用3个指标cc0(s)、cc1(s)、co(s)即信号s的组合0可控制性、组合1可控制性、组合可观察性。大体而言，三种组合可测试性指标(cc0、cc1和co)与为了从输入控制信号s或在输出观察信号s而必须操纵的信号数量有关，反映了从芯片io控制或观察内部信号s的难度。本步骤将在信息缺失情况下不断迭代计算可测试性特征值以估计原始可测试性特征值，具体子流程如图3所示，各子步骤与图中标号相同。
[0090]
3.1断点作io初始化
[0091]
该子步骤通过将断点信号视作io端口以启动可测试性特征计算，为后续迭代奠定基础。定义芯片输入端口集合为i,输出端口集合为o。则对各节点作式2至5的初始化操作。
[0092]
cc0(v)＝cc1(v)＝1,co(v)＝∞,v∈i∪mi
ꢀꢀꢀ
(22)
[0093]
cc0(v)＝cc1(v)＝∞,co(v)＝0,v∈o∪mo
ꢀꢀꢀ
(23)
[0094]
cc0(v)＝cc1(v)＝1,co(v)＝0,v∈isolate
ꢀꢀꢀ
(24)
[0095]
cc0(v)＝cc1(v)＝∞,co(v)＝∞,for others
ꢀꢀꢀ
(25)
[0096]
对于i与mi类断点信号置特征值cc0＝cc1＝1,co＝∞；对于o与mo类断点信号置特征值cc0＝cc1＝∞,co＝0；而对isolate类信号则置特征值cc0＝cc1＝1,co＝0对其他信号则置特征值cc0＝cc1＝co＝∞。
[0097]
3.2计算可测试性特征值
[0098]
在各初始化子步骤完成后即可计算可测试性特征值，计算流程如图4所示，首先统计信号节点的拓扑次序，使得线性时间复杂度下能有序完成信号节点特征值的计算；然后根据正向拓扑顺序(从输入到输出)，计算信号节点的可控性特征；最后根据逆向拓扑次序(从输出到输入)，计算信号节点的可观测性特征。
[0099]
由于逻辑电路中存在反馈回路，回路中的节点位于同一强连通分支中，因此本发明使用kosaraju
[8]
算法统计出信号节点的拓扑次序，再根据拓扑顺序计算可测性特征相比于根据信号通路递归计算的方式更高效。
[0100]
确定好拓扑顺序后即可开始从输入端口到输出端口按次序遍历各器件计算可控性指标。逻辑门的所有输入可控性都确定之后，输出可控性便可计算。基本思路是逻辑门输出信号可控性指标等于将该信号置1或0所需控制的输入信号可控性指标之和的最小值加1。基本逻辑器件的可控性计算如图5所示。
[0101]
所有信号可控性指标建立好后，从输出到输入逆向遍历每个器件以计算可观测性指标。逻辑门的输出信号可观测性指标确定后，输入信号可观测性便可计算。基本思路是逻辑门输入信号可观测性指标等于输出信号可观测性指标加上将其他输入信号置为非控制值所需可控性指标之和的最小值再加1。基本逻辑器件的可观测性指标计算如图6所示。
[0102]
3.3断点全局平均赋值
[0103]
此前，本发明在step3.1将断点信号视作io端口已经计算过一次可测性特征值，显然断点信号可测性特征值将大幅减小，进而间接拉低附近信号节点的可测性特征值。因此本步使用断点全局平均特征赋值的方式再次初始化可测试性特征值以驱动第二次可测性指标计算进一步逼近原始特征值。
[0104]
由于mo类断点信号输入并未缺失，从而经过第一次计算可测性指标后其可控性指标较为准确，同理mi类断点信号可观察性指标较为准确，因此将mi类断点信号的可控性指标初始化为mo类断点信号的平均可控性，而将mo类断点信号的可观察性指标初始化为mi类断点信号的平均可观察性指标。另外，为了消除常量信号影响需对参与均值运算的信号作特征值范围检查。即对各信号作如下式6-10初始化操作
[0105]
cc0(v)＝cc1(v)＝1,co(v)＝∞,v∈i
ꢀꢀꢀ
(26)
[0106]
cc0(v)＝cc1(v)＝∞,co(v)＝0,v∈o
ꢀꢀꢀ
(27)
[0107][0108][0109][0110]
对于木马断点，平均赋值显然提高了初始特征值，从而将抬高整体木马触发电路的特征值。而对于普通断点，平均赋值又不会使得初始特征值过大从而造成正常电路特征值过大而虚警。断点全局平均赋值初始化后再计算一次可测试性指标为后续范围搜索赋值提供更为可靠的特征值。
[0111]
3.4断点范围搜索赋值
[0112]
全局平均赋值后，断点特征值相比视作io更逼近原始特征值，但是当mi类和mo类的断点信号相互关联时，会导致后级断点信号计算的特征值偏低。而平均赋值又导致断点特征值趋于一致从而使得部分木马节点无法判断。因此，本发明提出结合版图位置信息针对断点信号作范围搜索以差异化断点特征值，更进一步逼近断点原特征值，使得木马节点得以暴露。断点范围搜索赋值算法流程如图7所示。
[0113]
本步骤在计算初始数据后，分别对mo类断点,mi类断点和剩余点初始化特征值。
[0114]
kd-tree
[9]
是计算几何中用于区域查找的数据结构，其性能优良兼顾了存储空间与查找时间，适用于非完备门级网表的断点范围搜索任务。首先，从非孤立的断点信号出发构建一颗kd-tree；其次，对mo类断点范围搜索赋值如图8所示，对每一个mo类断点信号作一次范围搜索，将搜索得到的mi类断点信号的co特征值取平均赋给启动搜索的mo类断点信号，即式11所示。
[0115][0116]
其中,sni＝{node|node∈sn∩node∈mi∩co(node)＜∞}为搜索得到且co特征值有效的mi类断点信号集合，sn为kd-tree范围搜索返回节点集合。
[0117]
同理，对mi类断点范围搜索赋值如图9所示，对每一个mi类断点信号作一次范围搜索，将搜索得到的mo类断点信号的cc1、cc0特征值取平均赋给启动搜索的mi断点信号，如式12、13所示。
[0118][0119][0120]
其中，sno0＝{node|node∈sn∩node∈mo∩cc0(node)＜∞}为搜索得到且cc0特征值有效的mo类断点信号集合。sno1＝{node|node∈sn∩node∈mo∩cc1(node)＜∞}为搜索得到且cc1特征值有效的mo类断点信号集合。
[0121]
若未搜索到目标类断点信号则将目标类断点信号平均特征值赋给启动搜索的断点信号。同步骤3.3，计算均值以及范围搜索时需要作特征值范围检查。由此步初始化可测性计算得出的可测性特征值更为逼近原特征值且具备差异化特点从而有效支撑了step4聚类判断的进行。
[0122]
4、聚类判断
[0123]
木马信号节点由于其隐蔽性的特点使得其cc1、cc0与co特征值相比正常节点大许多，表现在以cc、co为x、y轴的可测性特征值二维平面上，木马节点距离正常节点簇距离很远且木马信号节点簇分布在x-inf、y-inf处,正常信号节点簇分布在靠近原点处。
[0124]
因此，本步骤首先将每个信号节点的cc0与cc1特征值合并为一个特征值cc,如公式14所示:
[0125][0126]
其次，通过k-means
[10]
聚类算法将信号节点划分为3类；然后，通过类间距离判断各簇是否为木马信号节点簇。最后，报告检测结果。
[0127]
聚类过程针对全体可控且可观察节点集n＝{n1,n2,
…
,nm}进行，首先输入各点ni∈n表示为二维特征向量的特征向量集d＝{(cc(ni),co(ni)),ni∈n}。其次，考虑到木马节点的分布特征，选择原点，最大可观测值点，最大可控制值点作为初始簇中心集合{μ1,μ2,μ3}，如式15所示。
[0128][0129]
最后，不断遍历集合d，计算ni节点对应特征向量di与各簇中心的欧氏距离d
ij
如式16，依据各点到最近簇中心距离划分簇如式17-18所示，其中λi为ni节点簇标记，c
λi
为ni节点划入的节点簇。并更新簇中心位置如式19所示
[0130]dij
＝||d
i-uj||2,di∈d,j∈{1,2,3}
ꢀꢀꢀ
(36)
[0131]
λi＝arg min
j∈{1,2,3}dij
ꢀꢀꢀ
(37)
[0132][0133][0134]
直到收敛稳定到最终节点簇划分{c1,c2,c3}以及簇中心{μ1,μ2,μ3}。
[0135]
分类判断通过设定与普通节点簇标准差相关的差异阈值，当簇间距离超过阈值则判断为木马簇。首先，依据簇中心到原点距离，从小到大将各簇标记为c1,c2,c3。其次，计算c1簇标准差σ1,如式20所示:
[0136][0137]
其中，k为c1簇节点数，μ为c1簇中心向量。设置阈值t1＝3σ1,计算c1,c2类间距离为i
12
，若i
12
》t1,则判定c2,c3都为木马节点簇；若i
12
≤t1,则判定c2为普通节点簇，并将c1,c2视作同一正常节点簇，计算c1,c2簇标准差σ2并设置新阈值t2＝3σ2以判断c3簇；计算c1,c2簇与
c3簇类间距离为i
12,3
,若i
12,3
》t2则判定c3为木马节点簇,否则判定c3为普通节点簇。
[0138]
最后，将不可控或不可观察节点以及聚类判断后的木马节点簇视作木马节点报告给用户。
[0139]
由表中可知，本发明对所有丢失类型与丢失比例平均检测率高达98.3％，平均虚警率为0.64％能够对非完备门级网表完成高精度硬件后门检测。
[0140]
[0141]

技术特征：
1.一种针对非完备门级网表的高精度硬件后门检测方法，该方法包括：步骤1、非完备门级网表预处理与建模；首先，读取非完备门级网表文件,提取io及内部信号节点构成有向图顶点集合v＝{v1,v2,v3,,v
m
},集合中各顶点对象拥有信号名、驱动逻辑单元名、驱动逻辑单元类型；其次，将逻辑器件输入输出信号节点对映射为有向图的边，构成边集e＝{e1,e2,e3,
…
,e
i
,
…
e
k
}；其中某边e
i
＝<n
i
,n
j
>表示顶点n
i
为某器件输入节点，且在有向图中指向同器件输出节点n
j
；每条边包括：边头节点名、边尾节点名、输入信号引脚名、所属逻辑器件名；得到每个门级逻辑网表都映射为有向图g＝(v,e),g由顶点集v和边集e组成；步骤2、断点信号识别与定位；将gdsii文件导入eda(电子设计自动化)工具中，并使用eda工具对版图作设计规则检查(drc)以筛选出断线信号missnodes＝{n1,n2,
…
,n
m
}；其次，获取断线n
i
连接到器件的引脚名pins(n
i
)＝{p1,p2,
…
,p
n
}，并将n
i
断点类型type(n
i
)作式1所示分类：其中，为空集，outpins＝{c1,so,co,s,q,qn,zn,y}，其中c1,so,co,s,q,qn,zn,y为元件库中不同器件输出引脚名；即若某断线信号未连接到任一器件引脚则记作isolate类断点信号，isolate类断点信号表示孤立类断点信号，否则若该断线信号未连接到任一器件输出引脚则记作mi类断点信号，mi类断点信号表示输入缺失类断点信号，连接到任一器件输出引脚则记作mo类断点信号，mo类断点信号表示输出缺失类断点信号；最后，将非isolate类断点信号n
i
连接的任一逻辑器件相对于ic核心左下角的归一化坐标位置(location(n
i
)＝{x
i
,y
i
},x
i
∈[0,1],y
i
∈[0,1])填入断点信号的位置属性中，断点类型填入断点类型属性中；步骤3、迭代计算可测试性特征值；可测试性包括3个指标：cc0(v)、cc1(v)、co(v)即信号v的组合0可控制性、组合1可控制性、组合可观察性；步骤3.1：断点作io初始化；定义芯片输入端口集合为i,输出端口集合为o；则对各节点作式2至5的初始化操作；cc0(v)＝cc1(v)＝1,co(v)＝∞,v∈i∪mi (2)cc0(v)＝cc1(v)＝∞,co(v)＝0,v∈o∪mo (3)cc0(v)＝cc1(v)＝1,co(v)＝0,v∈isolate (4)cc0(v)＝cc1(v)＝∞,co(v)＝∞,for others (5)步骤3.2：计算可测试性特征值；首先统计信号节点的拓扑次序，使得线性时间复杂度下能有序完成信号节点特征值的计算；然后根据正向拓扑顺序即从输入到输出的顺序，计算信号节点的可控性特征；最后根据逆向拓扑顺序即从输出到输入顺序，计算信号节点的可观测性特征；采用kosaraju算法统计出信号节点的拓扑次序；逻辑门输出信号可控性指标等于将该信号置1或0所需控制的输入信号可控性指标之
和的最小值加1；逻辑门输入信号可观测性指标等于输出信号可观测性指标加上将其他输入信号置为非控制值所需可控性指标之和的最小值再加1；步骤3.3：断点全局平均赋值；将mi类断点信号的可控性指标初始化为mo类断点信号的平均可控性，而将mo类断点信号的可观察性指标初始化为mi类断点信号的平均可观察性指标；另外，为了消除常量信号影响需对参与均值运算的信号作特征值范围检查；即对各信号作如下式6-10初始化操作；cc0(v)＝cc1(v)＝1,co(v)＝∞,v∈i (6)cc0(v)＝cc1(v)＝∞,co(v)＝0,v∈o (7)(7)(7)其中，node表示单个断点信号；然后再计算一次可测试性指标为后续范围搜索赋值提供更为可靠的特征值；步骤3.4：断点范围搜索赋值；首先，从非孤立的断点信号出发构建一颗kd-tree；其次，对每一个mo类断点信号作一次范围搜索，将搜索得到的mi类断点信号的co特征值取平均赋给启动搜索的mo类断点信号，即式11所示；其中,sni＝{node|node∈sn∩node∈mi∩co(node)＜∞}为搜索得到且co特征值有效的mi类断点信号集合，sn为kd-tree范围搜索返回节点集合；同理，对每一个mi类断点信号作一次范围搜索，将搜索得到的mo类断点信号的cc1、cc0特征值取平均赋给启动搜索的mi断点信号，如式12、13所示；特征值取平均赋给启动搜索的mi断点信号，如式12、13所示；其中，sno0＝{node|node∈sn∩node∈mo∩c0c(nod)e＜∞}为搜索得到且cc0特征值有效的mo类断点信号集合；sno1＝{node|node∈sn∩node∈mo∩cc1(node)＜∞}为搜索得到且cc1特征值有效的mo类断点信号集合；若未搜索到目标类断点信号则将目标类断点信号平均特征值赋给启动搜索的断点信号；
步骤4：聚类判断；首先将每个信号节点的cc0与cc1特征值合并为一个特征值cc,如公式14所示：其次，通过聚类算法将信号节点划分为3类；然后，通过类间距离判断各簇是否为木马信号节点簇；最后，报告检测结果。2.如权利要求1所述的一种针对非完备门级网表的高精度硬件后门检测方法，其特征在于，所述步骤4的聚类方法为：聚类过程针对全体可控且可观察节点集n＝{n1,n2,
…
,n
m
}进行，首先输入各点n
i
∈n表示为二维特征向量的特征向量集d＝{(cc(n
i
),co(n
i
)),n
i
∈n}；其次，考虑到木马节点的分布特征，选择原点、最大可观测值点、最大可控制值点作为初始簇中心集合{μ1,μ2,μ3}，如式15所示：最后，不断遍历集合d，计算n
i
节点对应特征向量d
i
与各簇中心的欧氏距离d
ij
如式16，依据各点到最近簇中心距离划分簇如式17-18所示，其中λ
i
为n
i
节点簇标记，为n
i
节点划入的节点簇；并更新簇中心位置如式19所示：d
ij
＝||d
i-u
j
||2,d
i
∈d,j∈{1,2,3}
ꢀꢀꢀꢀꢀꢀ
(16)λ
i
＝argmin
j∈{1,2,3}
d
ij
ꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(17)(17)直到收敛稳定到最终节点簇划分{c1,c2,c3}以及簇中心{μ1,μ2,μ3}。3.如权利要求1所述的一种针对非完备门级网表的高精度硬件后门检测方法，其特征在于，所述步骤4中通过类间距离判断各簇是否为木马信号节点簇的方法为：分类判断通过设定与普通节点簇标准差相关的差异阈值，当簇间距离超过阈值则判断为木马簇；首先，依据簇中心到原点距离，从小到大将各簇标记为c1,c2,c3；其次，计算c1簇标准差σ1,如式20所示:其中，k为c1簇节点数，μ为c1簇中心向量；设置阈值t1＝3σ1,计算c1,c2类间距离为i
12
，若i
12
>t1,则判定c2,c3都为木马节点簇；若i
12
≤t1,则判定c2为普通节点簇，并将c1,c2视作同一正常节点簇，计算c1,c2簇标准差σ2并设置新阈值t2＝3σ2以判断c3簇；计算c1,c2簇与c3簇类间距离为i
12,3
,若i
12,3
>t2则判定c3为木马节点簇,否则判定c3为普通节点簇；最后，将不可控或不可观察节点以及聚类判断后的木马节点簇视作木马节点报告给用户。

技术总结
该发明公开了一种针对非完备门级网表的高精度硬件后门检测方法，涉及领域为硬件安全领域。该发明在IC逆向工程在有限资源条件下难以得到100％精确的逻辑网表的前提下，以高精度地完成硬件后门检测为目的。基于硬件后门节点的可测性特征值远大于正常节点的特征值，结合逆向工程得到的版图位置文件，通过IO、全局平均、范围搜索的方式不断逼近原特征值，从而使得后续聚类判断可有效实施。实现了在网表非完备的条件下，高精度的硬件后门检测。高精度的硬件后门检测。高精度的硬件后门检测。


技术研发人员：白智元 邹金成 陈哲 王坚 杨鍊
受保护的技术使用者：电子科技大学
技术研发日：2023.04.28
技术公布日：2023/8/13