自动检测与清除集成电路设计中功能性木马的方法和装置

摘要

本文提出一种检测，定位和掩蔽算术电路中的硬件木马(HT)以提高电路安全性的方法。该方法使用逆向工程从标准电路和待检测电路中分别提取2输入XOR子电路，XOR树，1位加法器，1位加法器图形和算术宏模块。方法对标准电路与待检测电路以及提取出的算术宏模块进行比较，通过ECO引擎来检测HT。本方法通过ECO引擎生成补丁电路来屏蔽HT。

说明书

关于使用在先申请的受益声明

本申请要求受益于美国临时专利申请62/281,738，题为“检测，定位，并修正数字电路中的硬件木马”，临时专利申请时间为2016年1月22日，该申请的内容通过引用以其整体并入本文。

技术领域

本发明涉及一般电路设计，尤其涉及提高电路安全性的方法和装置。

背景技术

现代电路(诸如集成电路(IC))是非常复杂的。例如，平均台式计算机芯片可以具有超过10亿个晶体管。由于复杂性和高成本，IC设计经常外包给第三方来完成电路设计。这种外包方式为攻击者提供了通过引入恶意更改或硬件木马(HT)来损坏设计的IC的机会，这导致严重的安全问题，特别是对于诸如军事应用方面的关键应用。HT可能对嵌入HT的电路造成故障或破坏，降低电路可靠性和泄漏机密信息。

目前亟需用于验证与提高电路安全性的新方法和装置。

发明内容

本文提出了一个示例性实施例，其提供了一种在算术电路中检测，定位和屏蔽功能性硬件木马(HT)以提高电路安全性的方法。该方法通过比较标准算术电路(称为第一网表)与被HT侵害电路(称为第二网表)从而检测与消除第二网表中的HT。

本文分别从第一网表和第二网表中提取算术宏模块，然后对于提取的算术宏模块进行比较。利用算术宏模块来定位第二网表中HT的位置，并且在第二网表中加入补丁电路来屏蔽HT以提高电路安全性。

本来同时讨论了其他示例性实施例。

附图说明

图1示出了根据示例性实施例的在电路设计过程期间硬件木马(HT)植入的情况的图。

图2A示出了根据示例性实施例的门级(GTL)电路图。

图2B示出了根据示例性实施例的GTL电路中的HT注入后的电路图。

图2C示出了根据示例性实施例的修正后的GTL电路图。

图2D示出了根据示例性实施例的HT诊断报告。

图3示出了根据示例性实施例的示例方法的流程图。

图4A示出了根据示例性实施例的乘法器的组成图。

图4B示出了根据示例性实施例的乘法器的组成图。

图5示出了根据示例性实施例的XOR森林的示意图。

图6示出了根据示例性实施例的示例逆向工程技术的流程图。

图7A示出了根据示例性实施例的检查网表的示意图。

图7B示出了根据示例性实施例的目标网表的示意图。

图7C示出了根据示例性实施例的剪枝后的网表示意图。

图8A示出了根据示例性实施例的在添加补丁电路之前的示意图。

图8B示出了根据示例性实施例的在添加补丁电路之后的示意图。

图9A示出了根据示例性实施例的在添加保守类补丁之前的示意图。

图9B示出了根据示例性实施例的在添加保守类补丁之后的示意图。

图10A示出了根据示例性实施例的在添加激进类补丁之前的示意图。

图10B示出了根据示例性实施例的在添加激进类补丁之后的示意图。

图11A示出了根据示例性实施例的在使用Add-First重新布线变换优化补丁电路之前的电路图。

图11B示出了根据示例性实施例的在使用Add-First重新布线变换优化补丁电路之后的电路图。

图12A示出了根据示例性实施例的在使用Cut-First重新布线变换优化补丁电路之前的电路图。

图12B示出了根据示例性实施例的在使用Cut-First重新布线变换优化补丁电路之后的电路图。

图13示出了根据示例性实施例的测试用例信息表格。

图14示出了根据示例方法的实验结果表格。

图15示出了根据示例性实施例得到的计算机系统

具体实施方式

示例性实施例涉及提高电路安全性的方法和装置。

电路(例如集成电路(IC))或芯片设计和制造是非常复杂的。现代IC通常包括数百万个微型电子部件，例如门，晶体管和二极管(例如，现在平均台式计算机芯片可以具有超过10亿个晶体管)，这使得人们不可能利用纸笔或手动地设计这样的电路或芯片。通常采用诸如安装对应软件(诸如电子设计自动化(EDA)或计算机辅助设计(CAD)工具)的计算机设备或系统的硬件来完成这些任务。

由于IC设计和制造的复杂性显着增加，设计通常通过使用来自供应商的第三方知识产权(3PIP)进行外包设计。由于攻击者(例如不信任的人或不诚实的工程师或间谍)将硬件木马(HT)或错误(例如，非预期或未经授权的功能硬件插入，恶意硬件插入或未经授权的设计修改)注入到电路中的可能性大幅增加。此外，不可靠的制作厂商还可以在硬件制作阶段将意外的功能安装到电路或芯片。

HT或者错误在许多方面会伤害电路或者芯片。例如，HT通过添加，删除或修改电路的一个或多个组件(例如逻辑门，晶体管，二极管等)来恶意地改变或修改电路的功能。作为另一示例，HT通过修改要发送到电路中的一个或多个参数来间接地改变电路功能。HT可以中断电路(例如IC)或删改正常电路的功能。作为示例，HT使IC发生故障和/或执行构成安全攻击的一个或多个功能。HT还可以由间谍设计或植入以检索敏感数据或信息，或者被设计为改变主机电路规范，例如延迟，功率消耗和可靠性。例如，如果HT被植入或嵌入在电路中，被指定为正常工作十年的电路或芯片可能缩短为仅一年可靠。

因此，在诸如IC设计，验证和制造，消费产品和军事应用等行业中，检测电路(例如算术电路，例如IC)中的HT或缺陷的存在以及掩蔽或杀死这样的HT是非常重要的。并且检测和去除这样的HT或者错误以提高电路安全性在这些行业中具有重要意义。诸如IC之类的电路中的未检测到的HT可以使得该电路在诸如敏感信息泄漏的多个方面处于极大的危险中。现有检测算法在检测和移除HT中效率低下(例如高运行时或时间复杂性)，大大延长了产品设计周期，并且增加了上市时间并且危及利润率。此外，现有算法不令人满意的效率或运行时的复杂性要求计算机设备提供更多资源(诸如存储器使用)与高性能(诸如高处理能力和速度)，并且还在数据通过网络传输到远程服务器时增加网络消耗。因此，用于HT检测和捕获的不令人满意的方法或方案不仅在技术和经济上危及许多行业(例如IC工业和与IC行业相关或依赖于IC行业的其他行业)，而且还需要昂贵的计算机硬件，需要大量的资源消耗，例如内存使用和高处理速度。

现有或常规方法在检测和杀死电路中的HT方面有困难与缺陷。一方面，这是因为HT的存在不容易检测。HT可以驻留在芯片的测试电路内，以避免在正常操作期间被检测到并且偶尔被激活以执行恶意操作。此外，现代IC或芯片中的逻辑门的数量太大，以至于穷举测试是不可行的。另一方面，现有方法在一个或多个方面本质上具有缺陷。

例如，许多现有方法只能从门级(GTL)网表中提取简单的逻辑模式，例如门，但不能处理复杂但基本的算术模块，例如加法器和乘法器。一些现有方法使用模拟工具来识别具有低激活概率的逻辑门，然而，该激活概率是不准确的。一些现有方法采用基于可满足性(SAT)的功能形式验证技术来检测电路中的HT，然而，其不能验证以不同样式设计的某些算术逻辑(例如非布斯乘法器与布斯乘法器)。现有的基于SAT的功能形式验证技术不能很好地工作的主要原因是现有的SAT算法高度依赖于成功定位比较逻辑的内部等效点。当发现少量内部等效点时，即使对于相当小的电路，求解时间在最坏的情况下(例如以不同样式(例如，非布斯与布斯)设计的乘法器之间执行比较时)成指数地增长。现有的SAT算法在电路(例如算术电路)的等效检查方面也显示出无法工作，例如不能证明两个算术电路之间的相等性。此外，现有方法不能检测和定位HT的主体和边界在哪里，也就无法让芯片所有者或设计者分析HT的预期损坏的电路。

因此，现有的方法或方案在检测和掩蔽或去除电路或算术电路(例如IC，专用集成电路(ASIC)和现场可编程门阵列(FPGA)，数字信号处理器(DSP)等)中表现低效。从计算机技术的角度看，现有也是不利的：因为检测和掩蔽HT的较不高效的过程会消耗海量时间(例如，几十小时或几天，或甚至不收敛(经过海量运行时间后仍然留下主题问题未解决))；需要大的资源使用(如内存使用和网络消耗)；昂贵的计算机设备(如高处理能力)。

示例性实施例通过在以非常规方式起作用以使电路工业和计算机工业受益的新方法和装置中提供技术解决方案来解决上述问题。示例性实施例对防止(例如检测，定位和掩蔽或去除)HT具有显着改进或增强的效率，通过减少或防止由HT引起的电路故障和故障，增加电路生产(例如产量)和寿命。另一方面，通过避免敏感数据泄漏或通过避免电路或包含这种电路的装置或机器来提高电路安全性以防止电路被攻击者或间谍接管。示例性实施例通过减少资源消耗(例如，存储器使用和网络消耗)而进一步有益于计算机技术。示例方法可以由具有较低硬件要求的计算机设备或系统执行，并且因此减少具有昂贵的芯片，存储器和其他内部电子部件的昂贵计算机的需求。

示例性实施例通过在新的方法和装置中提供技术解决方案来解决上述问题。所述新方法和装置可以检测出由一个或多个HT或错误导致的问题电路与正确电路之间的一个或多个功能差异，可以定位或显示差异以校正HT或调查篡改意图或目的，并通过将功能恢复到原始规范(例如，正确规范)来杀死，掩蔽或移除HT。作为示例，示例实施例以最小电路改变将电路或芯片的功能恢复回原始规范，以避免显着地影响电路或芯片的性能(诸如时钟和定时等)。示例性实施例通过在早期阶段阻止对电路的故意或绘制的损坏来改善电路安全性，并通过揭示HT意图来找出间谍源。

作为示例，示例性实施例通过提供具有逆向工程、形式验证、功能工程变更(ECO)、逻辑重新布线算法的组合技术解决方案来解决上述问题。作为示例，示例性实施例可以自动处理多个HT，保证百分百的在电路中捕获存在的HT。

作为示例，示例性实施例通过结合逆向工程和形式验证(称为互补耦合(CC)形式验证方案)以克服SAT算法在算术验证中无法使用的问题。示例逆向工程在验证等同性证明中表现良好，而示例SAT求解器在验证不等同性证明中表现良好。逆向工程和SAT技术的耦合可以同时利用逆向工程和SAT的优点，并且获得了组合优点，其改善了HT检测，降低了运行时间复杂性，提高了验证电路正确性的能力。作为示例，示例性实施例可以将正确或标准设计的网表与可能嵌入或植入HT电路的网表进行比较。

在示例实施例中，当检测到实际产生电路与标准电路存在功能差别时，会使用ECO技术来定位HT，并且插入或添加补丁电路以掩盖或消除HT。在另一示例实施例中，应用逻辑重新布线技术来优化补丁电路，使得电路的尺寸最小化。这一技术使得改正后的电路性能与改正前的性能差别可以最小化。

作为示例，用于检测，定位和掩蔽具有数百万逻辑门的IC中的多个HT(对HT的数量没有限制)的示例性实施例的运行时间仅需数分钟，而现有方法则需要数小时甚至数天。

示例性实施例包括具有特定软件的计算机系统，以及嵌入在网络中的这样的计算机系统。示例计算机系统通过执行本文的示例方法来解决诸如IC工业的电路工业中引起的技术问题。当执行示例方法时，示例计算机系统通过减少诸如存储器使用和网络消耗的资源使用来提高硬件性能。

图1示出了根据示例性实施例的在电路设计过程期间的HT注入的情形的图。图形100包括客户方110，设计工厂120，芯片制造工厂130和间谍或攻击者140。

作为示例，客户110计划设计新电路或芯片(例如，IC，ASIC，FPGA，DSP等)。作为示例，使用寄存器传送级(RTL)规范语言(诸如Verilog或VHDL)来规定设计功能或规范。然后，设计工厂120根据客户110提供的规定设计功能，经历慢长的设计过程，其中设计团队使用包含软件(如EDA或CAD工具)的硬件(如计算机)进行电路设计。客户110相当于将具体电路设计外包给设计工厂120。

作为示例，在设计工厂120中执行的设计过程包括逻辑综合和物理布局与布线(P&R)。例如，如图1所示，RTL级电路122被转换为门级(GTL)电路124，然后将其转换为电路级电路126。最终完成的电路设计交由制造芯片厂商130进行生产。

如图1所示，在设计工厂120的设计阶段期间，间谍140(例如不信任的人或不诚实的工程师)恶意地将HT或错误插入或嵌入电路或芯片中。作为示例，HT可以在设计工厂120中的任一中间阶段被引入到电路，诸如RTL级电路122，门级电路124和电路级电路126的设计过程。

客户110必须能够有效和高效地检测和去除HT(例如在实际时间限制内百分百的检测HT，例如在多项式时间甚至线性时间内)。否则，具有注入的HT的间谍140可能导致电路或芯片故障，破坏芯片的系统或窃取机密信息。客户110也可能倾向于不昂贵的HT捕获过程(例如，对诸如计算机设备的硬件的较低要求)。

图2A-2D示出了根据示例性实施例的在门级(GTL)电路中的HT注入的示意图。仅为了说明的目的，图2A示出了原始GTL电路210，其包括具有输入向量212的8-AND门214，212具有8个输入表示为in[7:0]，AND门216具有一个输出218(为out)和两个输入：一个是8-AND门214的输出，另一个是输入213(为s)。

作为示例，图2A中的GTL电路210是电路的原始网表。作为示例，输入213接收冗余内部信号s，其在正常工作模式或正常操作期间是固定逻辑1。

图2B示出了根据示例实施例的包括恶意逻辑或HT 225的网表220。结果，图2A中的AND门216被替换或改变为多路选择器(MUX)226。所添加的恶意逻辑225不在正常工作模式下被触发，因此不能通过使用常规方法如正常输入测试向量来进行检测。

图2C示出了根据示例性实施例的修补网表230。如图所示，打补丁网表230包括掩蔽或杀死恶意逻辑或HT 225的补丁或补丁逻辑235.在一个示例实施例中，补丁235的大小被最小化以减少目标电路或芯片的性能损耗。作为示例，目标电路或芯片是去除或屏蔽了HT的最终产品。

图2D示出了根据示例性实施例的HT诊断报告240。HT诊断报告240包括示出补丁235的网表的第一部分242和在用补丁235校正之后示出MUX 236的第二部分244。

图2A-2D表示了通过在电路中检测，定位和掩蔽或杀死插入或植入的HT或缺陷的示例性方法来改进电路安全性的流程。插入的HT通过引入补丁被掩蔽，使得电路可以根据原始或正确的规范被恢复回正确电路。

图3示出了根据示例性实施例的流程图。流程图300表示由安装有相关软件的计算机或并入有该计算机的设备执行的示例方法。计算机包括诸如计算机系统或电子系统，可穿戴电子设备，服务器，便携式电子设备，手持式便携式电子设备和硬件(例如，处理器，处理单元，数字信号处理器，控制器，存储器等)的电子设备。

该示例方法在由计算机执行时通过提高电路设计的有效性和效率(例如降低运行时间复杂性)来解决如上所述的电路工业中的一个或多个现有技术问题。示例方法还通过消耗更少的资源(例如存储器，处理器和诸如带宽的网络使用)来提高执行示例性方法的计算机的性能。

框302描述了示例方法用到的算术电路的第一网表。

例如，第一网表是符合客户或个人的计划或建议的规范的原始指定(标准或正确)网表。作为示例，第一网表是从标准寄存器传送级(RTL)电路转换得到的门级(GTL)网表。

框304描述了示例方法用到的算术电路的第二网表。

例如，第二网表是被检查的网表。作为示例，第二网表由间谍或攻击者产生的HT所修改。为了提高电路安全性，需要检查第二网表是否功能与第一网表相同。

框306指出从第一网表中提取算术宏单元以获得第一或多个算术宏。框308描述从第二网表中提取算术宏以获得一个或多个算术宏。

作为示例，宏或算术宏被定义为逻辑块，其是电路(例如IC)中的构建组件，例如加法器，乘法器，多路选择器(MUX)或诸如(A+B)×C均可视为宏.

在示例性实施例中，应用示例逆向工程(RE)技术来提取和比较所有算术宏，例如加法器和乘法器。算术宏通常由许多基本组件“1位加法器”构成，其包括1位半加法器(HA)和/或1位全加器(FA)。逆向工程技术(RE)首先从整个电路中识别所有这些基本组件。然后，RE构建1位加法器图，图中一个加法器的输出是另一个加法器的输入。不同算术宏的功能可以从构建的加法器图的不同组成样式获得。

作为示例，以由1位加法器构成的诸如CLA加法器，Ripple加法器，Booth乘法器和Non-Booth乘法器的多种样式来实现算术组件(诸如加法器和乘法器)。例如，图4A-4B表示了两种不同样式的乘法器410与420。其中FA表示1位全加器，HA表示1位半加法器。如图所示，乘法器410和乘法器420均包含一些公共结构单元(例如1位加法器)。

在示例性实施例中，首先提取所有1位加法器。1位全加器(FA)具有3个输入信号(例如a，b和c)和2个输出信号(例如sum和carry(也称为co))。1位全加器的功能如下：

FAco＝a&b+b&c+a&c(1)

其中也称为“异或”操作表示布尔“异或”函数，“+”表示布尔“或”函数，“&”表示布尔“和”函数。

1位半加器(HA)具有两个输入信号(例如a和b)和2个输出信号(例如和和进位(也称为co))。1位半加法器的功能如下：

HAco＝a&b

举例来说，加法器和乘法器都由一个或多个1位加法器组成。例如，Non-Booth类型的4位乘法器的第三个输出表示为：

作为示例，非布斯4位乘法器的第四位输出表示为：

其中FAco和HAco是其他1位加法器的输出信号

在示例性实施例中，为了计算1位加法器图，首先识别所有1位加法器。为了计算1位加法器，首先识别所有功能为异或(XOR)的2输入单输出子电路。然后，识别一个或多个XOR树。XOR树包含一个或多个2-输入XOR子电路并且每个2-输入XOR子电路的输出均为另一个XOR子电路的输入信号。一个或多个XOR树的输入是加法器和乘法器的初始输入或内部1位加法器的进位信号。基于一个或多个XOR树，可以推导正确的进位信号，从而讲一个或多个XOR树连接在一起以形成XOR森林。作为示例，XOR森林也被认为是1位加法器图。根据示例性实施例的1位加法器图的构造在图5中示出。

图6示出了根据示例实施例的逆向工程技术的流程图。表600中所示的示例方法包括：识别或确定多个2输入XOR子电路；建立一个或多个XOR树；确定进位信号；连接多个XOR树以形成诸如1位加法器图的XOR森林；根据1位加法器图确定算术宏的逻辑功能和算术宏的电路边界。在示例实施例中，在形成或构建1位加法器图(也称为XOR森林)之后，使用XOR森林来确定诸如加法，减法和乘法的算术逻辑功能，以及更加复杂的算术逻辑(例如加法器和乘法器(例如(a+b)×c，a×b+c×d等)的组合)。

返回到图3，块310通过将第一算术宏与第二算术宏进行比较来检测HT。

在示例实施例中，如块310中所述的过程被认为是全局HT定位，因为其全局地确定HT位于哪个或哪些区域中。在另一示例性实施例中，为了提高全局地定位一个或多个HT的效率，应用剪枝技术进行处理。

例如，利用剪枝技术，等效子电路对可以被识别并从电路剥离，所有HT仅存在于非等效子电路区域内部。作为示例，如果第一电路的第一部分和第二电路的第二部分是等效子电路对，则第一部分和第二部分具有相同的功能，或者它们在功能上等效。如果第一部分和第二部分具有不同的功能，则它们在功能上是非等效的，而不是等效的子电路对。作为另一示例，第一算术宏由部分A1和部分B1组成，并且第二算术宏由部分A2和部分B2组成。部分A1和部分A2在功能上等效，并且部分B1和部分B2在功能上是非等效的。作为示例，从第二算术宏中去除A2，使得HT被确定为位于第二算术宏的B2中。

作为示例，图7A-7C示出了根据示例实施例的剪枝过程的图。图7A示出了包含HT的检查网表710(或第二网表)。被检查的网表710包括具有6-XOR子电路(即，实现6输入XOR功能)的部分714和指示被检查网表710的其他部分的部分712.图7B示出了标准或正确网表720(或第一网表)。标准网表720包括具有6-XOR子电路的部分724和指示标准网表720的其他部分722。部分714和部分724具有相同的功能或功能上等效，但具有不同的实现样式。

如图7C所示，将等效对(部分714和部分724)从相应的网表中修整或剥离以获得修剪的网表730.在示例性实施例中，重复执行剪枝或剥离处理以最小化非等效电路部分。在另一示例性实施例中，迭代地执行剪枝或剥离处理，直到在检查网表710和标准网表720之间没有找到等效子电路对或等效对。

返回到图3，块312用功能工程变更(ECO)引擎来定位第二网表中的HT。

作为示例，ECO引擎或技术被应用于定位和掩蔽HT。

框314使用ECO引擎通过在第二网表中添加补丁来掩蔽HT，从而提高了算术电路的安全性。

作为示例，ECO引擎将电路中的一组输入(PI)表示为一组布尔变量X＝{x1，...，xn}。F(X)＝{f1(X)，f2(X)，...，fm(X)}表示第二网表中的逻辑功能；G(X)＝{g1(X)，g2(X)，...，gm(X)}表示第一网表中的逻辑功能。

对于检查网表与标准网表中的逻辑功能函数对fi和gi，diff-set表示某一组电路输入，在此电路输入的情况下函数fi和gi具有相反的值，并且定义如下：

diffi(X)＝fi(X)⊕gi(X)(4)

ECO引擎通过增量式地添加补丁逻辑或电路来最小化每个函数对的diff-set，直到所有diff-set都为空，这表示被检查的函数和标准函数逻辑功能相同，也就是HT已经被彻底清除。在示例性实施例中，补丁逻辑被不断插入到电路中以最小化diff-set。

例如，对于要插入补丁逻辑的电路内的内部信号r，假设r的函数是t(X)，PO对应的函数为fi并且函数值受r信号影响，则r的care-set定义如下：

Care-set表示某一组电路输入，在此电路输入的情况下，可以在输出函数fi处观察到信号r处的任何变化。在示例实施例中，根据diff-set与care-set的包含关系所有电路输入被划分为两个分区：

(i)care-out-diff：某一组电路输入，在此电路输入的情况下，care-set的值为1且此电路输入不被diff-set所包含。和：

(ii)care-in-diff：某一组电路输入，此电路输入同时被care-set和diff-set包含。

作为示例，若改变care-out-diff中函数fi的值，则diff-set会被放大，从而使得HT的危害增加，因此试图消去HT的补丁函数p(X)必须满足以下约束：

另一方面，为了最小化diff-set，需要改变在care-in-diff中的t的值：

因此，如果p(X)和diff-set满足以下条件，

这意味着

那么p(X)可以完全清空diffi(X)也即是消除HT

图8A-8B示出了根据示例性实施例的补丁函数创建图。图8A示出了在修补之前的图810。图形810包括具有重叠816(即，care-in-diff)的care-set 812和diff-set 814。不包括care-in-diff 816的care-set 812是care-out-diff。图8B示出了在加入补丁函数之后的图820。图形820中diff-set的面积减小，表示HT造成的影响与危害也相对减小。

作为示例，在创建补丁或补丁函数时考虑约束等式(6-8)。如果信号r仅驱动单个输出，则相应的补丁函数必须满足方程(6)和方程(7)。在示例实施例中，为了增强创建有效补丁的可能性，同时避免穷举搜索，本方法提出了生成两种类型的补丁方案：保守类补丁和激进类补丁。

图9A-9B示出了根据示例性实施例生成的保守类补丁。图9A示出了创建补丁前的care-set与diff-set面积图910。图9B示出了创建补丁后的面积图920。

在生成保守类补丁策略中，信号r处生成的补丁会保证不使任何PO对应的diff-set面积增加。因此，保守类补丁对所有PO均满足约束等式(6)。举例来说，从PO集合{PO1，PO2，...，POm}中选择PO的子集。子集{POi1，POi2，...，POil}被称为改进的PO集。在r处创建的补丁函数会满足约束等式(7)。

如图9A-9B所示，9B生成的补丁可以最大程度的减少diff-set的面积。

图10A-10B为根据示例性实施例生成激进类补丁的示意图。图10A示出了生成激进类补丁前的care-set与diff-set面积图1010。图10B示出了生成激进类补丁后的面积图1020。

作为示例，输出信号o1端的diff-set被完全消除(或改善)，而o2端的diff-set面积被扩大(变差)。在一个示例中，PO集合被划分为三个子集：

(i)忽略集合：在生成补丁函数过程期间不考虑集合中PO的diff-set，并且在示例性实施例中，这样的PO的diff-set在生成补丁函数之后会变得更差。

(ii)没有更改集：该集合中的PO的diff-set不会改变。在示例性实施例中，该集合中的PO的差异集合也不改善。对于该集合中的每个PO，其均满足等式(6)。

(iii)改进集：通过创建的补丁改进该集合中的PO的diff-set。其满足约束等式(6)和等式(7)。此外，对于该集合中的至少一个PO，满足约束等式(8)，这意味着所创建的补丁函数能够完全消除至少一个HT。

如图10A-10B所示，可以完全消除o1的HT，同时扩大o2的diff-set。

在示例性实施例中，示例方法包括使用功能工程变更(ECO)引擎来提高在网表中定位HT的效率。示例方法会首先生成保守类补丁候选者和激进类候选者，然后选择其中具有较小尺寸的候选者作为实际补丁电路。

在一些示例性实施例中，通过利用逻辑重新布线技术来优化补丁电路以最小化补丁电路从而提高电路性能。作为示例，补丁优化过程包括Add-First重新布线变换和Cut-First重新布线变换。

图11A-11B为根据示例性实施例的Add-first重新布线变换的示意图。图11A中的电路图1110表示了在Add-First重新布线变换之前的补丁电路；图11B中的电路图1120示出了在Add-First重新布线变换之后的补丁电路。

如图所示，对于Add-First重新布线变换，首先将冗余连线1112添加到补丁电路中(例如，从图中的g5到g9的连接线)。然后，若干连接线和逻辑门(例如g4，g6和g7)会因此变成冗余逻辑可以被移除，移除后的电路如图11B所示。可见优化后的补丁电路尺寸大幅减少。在由L.A.Entrena和K.-T Cheng所写的“Combinational and Sequential LogicOptimization by Redundancy Addition and Removal”(发布于1995年IEEE transactionon Computer-Aided Design会议)的论文中描述了此种重新布线变换的详细实现。

图12A-12B为根据示例性实施例的Cut-First重新布线转换的示意图。图12A中的电路图1210为重新布线转换之前的补丁电路；图12B为重新布线转换之后的补丁电路图。

如图12A所示，在Cut-First重新布线转换方法中，从b到g6的导线首先被去除，然后通过在g8和g9处添加额外的逻辑，可以使得转换后的逻辑功能保持不变，而转换后的补丁电路只需要较少的逻辑门与连接线，转换后的电路如图12B所示。Cut-First重新布线变换的实现在由Xiao Qing Yang，Tak-Kei Lam和Yu-Liang Wu撰写的论文“ECR：a lowcomplexity generalized error cancellation rewiring scheme”中详细描述，其发表在2010年的Proceedings of the 47th Design Automation Conference会议。

图13显示了根据示例性实施例可以得到的算数宏模块表格。在表1300中，“样式”栏中B表示布斯乘法器，NB表示非布斯乘法器。如图所示，除了基本乘法器之外，一些更复杂的算术宏模块(参见表1300中的“函数”列)也存在于基准中。

在表格1300中，第一列是案例套件的名称。每个套件包括13个测试电路，它们实现类似的算术功能，但具有不同的操作数的位宽。示例提取的算术逻辑及其设计样式和操作数的位宽显示在第3-5列。示例方法可以成功提取绝大多数(97％)的算术宏模块，只有套件ut36和hid10失败。在成功地提取算术逻辑的情况下，可以采用示例性形式验证技术与ECO引擎检测电路中是否存在一个或多个HT。

图14显示了根据示例方法的结果比较表格。

在表1400中，前三列示出了测试用例基本信息。每个用例具有两个电路g1和g2，它们具有逻辑差异。作为示例，g1是HT篡改过的电路，g2是标准或正确的电路。接下来的4列显示了使用两个示例方法分别生成的补丁电路大小以及生成补丁电路使用的时间。如图所示，示例方法产生的补丁电路可以减小40％，运行时间减少86％。

图15显示了根据示例性实施例得到的计算机系统或电子系统。计算机系统1500包括一个或多个计算机或电子设备(例如一个或多个服务器)1510，其包括处理器或处理单元1512(诸如一个或多个处理器，微处理器和/或微控制器)，一个或多个组件计算机可读介质(CRM)或存储器1514，以及电路安全增强器1518。

存储器1514存储在被执行时使处理器1512执行本文所讨论的方法和/或本文所讨论的一个或多个框的指令。电路安全增强器1518是有助于改进计算机的性能和/或执行本文所讨论的方法和/或本文所讨论的一个或多个框的专用硬件和/或软件的示例。结合图3讨论电路安全增强器的示例功能。

在示例实施例中，计算机系统1500包括存储器或存储器1530，通过一个或多个网络1520通信的便携式电子设备或PED 1540。

存储器1530可以包括存储图像文件，音频文件，视频文件，软件应用和本文所讨论的其他信息中的一个或多个的一个或多个存储器或数据库。作为示例，存储器1530存储由服务器1510通过网络1520检索的图像，指令或软件应用，使得执行本文讨论的方法和/或本文所讨论的一个或多个框。

PED 1540包括处理器或处理单元1542(诸如一个或多个处理器，微处理器和/或微控制器)，计算机可读介质(CRM)或存储器1544的一个或多个组件，一个或多个显示器1546，以及电路安全增强器1548。

PED 1540可以执行本文讨论的方法和/或本文所讨论的一个或多个框，并显示图像或文件(例如网表)以供查看。或者或另外，PED1540可以通过网络1520从存储器1530检索诸如图像和文件以及软件指令的文件，并且执行本文所讨论的方法和/或本文所讨论的一个或多个块。

在示例实施例中，计算机系统1500包括PED 1550，其包括处理器或处理单元1552(诸如一个或多个处理器，微处理器和/或微控制器)，计算机可读介质(CRM)或存储器的一个或多个组件1554，以及一个或多个显示器1556。

作为示例，PED 1550通过网络1520与服务器1510和/或存储器1530通信，使得本文讨论的方法和/或本文所讨论的一个或多个框由服务器1510执行，并且结果被发回到PED1550的输出，存储和审查。

网络1520可以包括蜂窝网络，公共交换电话网络，因特网，局域网(LAN)，广域网(WAN)，城域网(MAN)，个域网(PAN)，家域网(HAM)和其他公共和/或专用网络。另外，电子设备不需要通过网络彼此通信。作为一个示例，电子设备可以经由一个或多个线(例如直接有线连接)耦合在一起。作为另一示例，电子设备可以通过诸如蓝牙，近场通信(NFC)或其它无线通信协议的无线协议直接通信。

在一些示例性实施例中，本文所示的方法和与其相关联的数据和指令存储在相应的存储设备中，所述存储设备被实现为非暂时性计算机可读和/或机器可读存储介质，物理或有形介质，和/暂时存储介质。这些存储介质包括不同形式的存储器，包括诸如DRAM或SRAM，可擦除和可编程只读存储器(EPROM)，电可擦除和可编程只读存储器(EEPROM)和闪存的半导体存储器设备；磁盘如固定和可移动磁盘；其他磁介质包括磁带；光学介质，诸如紧凑盘(CD)或数字通用盘(DVD)。注意，上述软件的指令可以在计算机可读或机器可读存储介质上提供，或者可以在分布在具有可能多个节点的大型系统中的多个计算机可读或机器可读存储介质上提供。这样的计算机可读或机器可读介质被认为是物品(或制造物品)的一部分。制品或制品可以指制造的单个组件或多个组件。

在此讨论的框和/或方法可以在本文讨论的处理器，控制器和其他硬件上执行。此外，本文所讨论的框和/或方法可以在有或者没有用户的指令的情况下自动执行。

提供根据示例实施例的方法作为示例，并且来自一种方法的示例不应被解释为限制来自另一种方法的示例。图和其他信息显示示例数据和示例结构；其他数据和其他数据库结构可以用示例实施例来实现。此外，在不同附图中讨论的方法可以添加到其他图中的方法或与其交换。此外，具体的数值数据值(例如具体数量，数量，类别等)或其他具体信息应当被解释为用于讨论示例实施例的说明。没有提供这样的具体信息来限制示例实施例。

如本文所使用的，术语“硬件木马”(HT)是指对电路的未授权或非预期的改变，修改，插入，植入。HT可能引起电路故障，降低可靠性，导致机密信息泄漏等。

如本文所使用的，术语“算术电路”是指电路中的一个或多个部分用于完成诸如加法，减法，乘法和任何其它算术运算的电路。

如本文所使用的，术语“网表”表示电路中的逻辑门以及其之间的连接关系。

如本文所使用的，术语“宏”或“算术宏”是指构成电路(例如IC)中某一特定组件的多个逻辑单元或标准单元的集合。特定组件包括但不限于加法器，乘法器，多路选择器(MUX)等

如本文所使用的，术语“子电路”是指术语“宏”，并且这两个术语可以互换使用。

如本文所使用的，术语“2-输入异或(XOR)子电路”是指具有2个输入信号和1个输出信号的子电路。输出信号的功能是两个输入信号的排他或函数。

如本文所使用的，术语“XOR树”是指由一个或多个2输入XOR子电路及其连接关系组成的子电路。

如本文所使用的，术语“1位加法器”是指1位半加法器和/或1位全加器。

如本文所使用的，术语“1位半加器”是指具有2个输入(例如a和b)和2个输出(例如sum和co)的算术宏。“co”也可以称为“carry”。sum的功能是a和b的“异或”函数；co的功能是a和b的“和”函数。

如本文所使用的，术语“1位全加器”是指具有3个输入(例如a，b和c)和2个输出(例如sum和co)的算术宏。“co”也可以称为“carry”。sum的功能是a，b和c的“排他或”函数；co的功能是a，b和c的“多数表决”函数。

如本文所使用的，术语“1位加法器图”是指由一个或多个1位加法器及其连接关系组成的子电路。

如本文所使用的，术语“XOR森林”是指术语“1位加法器图”，并且这两个术语可以互换使用。

如本文所使用的，术语“逆向工程(RE)”是指从电路提取算术宏的过程。RE过程包括识别2输入异或(XOR)子电路，XOR树，1位加法器，1位加法器图和算术宏。

如本文所使用的，术语“指数时间”是指用于算法的运行时间以2ⁿ为上限，其中n是算法的输入信号数量。

如本文所使用的，术语“多项式时间”是指用于算法的运行时间以多项式表达式为上限。

如本文所使用的，术语“线性时间”是指算法的运行时间随着算法的输入信号数量线性增加。