随着现代半导体制造工艺和集成电路设计水平的不断提升，集成电路广泛应用于金融、航天和国防等领域.集成电路行业的激烈竞争促使集成电路设计与制造实现全球化，这导致集成电路的设计与制造过程不能实现自主可控，进而无法确保生产出的集成电路的安全可信性.攻击者可以针对集成电路设计与制造过程中的多个环节植入硬件木马^[1-2]，修改原始电路的工作状态来实现物理摧毁、逻辑破坏和信息泄露等目的^[3-5]. 理论上无法将硬件木马从被感染的集成电路中去除，其危害比软件木马更大，对集成电路的安全构成了极其严重的威胁.

硬件木马包括触发逻辑和有效载荷两部分.攻击者为了保证硬件木马的隐蔽性，通常会选择电路中的多个少态节点作为植入节点，以其稀有逻辑作为触发逻辑^[6]的激励信号.当多个少态节点的稀有逻辑值同时出现时，触发逻辑结构被激活，有效载荷开始工作.传统的功能检测难以覆盖电路所有功能，难以使少态节点达到其稀有值，所以通过传统的功能检测较难识别出硬件木马.须以少态节点为导向生成能够提高其翻转率的测试向量.

Chakraborty等^[7]提出多次激活少态事件(multiple excitation of rare occurrence, MERO)算法，以1个比特为单位筛选能快速激活少态节点的测试向量. Wang等^[8]提出针对组合型硬件木马的测试向量生成方法，利用自动测试向量生成方法(automatic test pattern generation, ATPG)产生使少态节点处于稀有逻辑值的测试向量，但该测试向量难以激活时序型硬件木马. Xue等^[9]提出基于活性驱动的测试向量生成算法，以汉明距离最大的原则重新排序测试向量，重排后得到的测试向量提升了电路的整体翻转率，但难以提升少态节点的相对翻转率，导致硬件木马显化效果不佳.

本研究提出基于遗传算法的少态节点活性提升方法，利用遗传算法的全局搜索能力，在整个向量空间内寻找能有效提升少态节点相对翻转率的测试向量.

节点翻转率包括静态翻转率和动态翻转率.静态翻转率表征节点逻辑状态的变化情况，假设在m个时钟周期内节点出现逻辑0的概率为P₀，逻辑1的概率为P₁，那么此节点的静态翻转率P_S=P₀P₁，静态翻转率的最大值为1/4.动态翻转率表征节点的翻转情况，假设在m个时钟周期内节点的翻转次数为n，则其动态翻转率为n/m.静态翻转率与动态翻转率均可表征电路节点活性，节点翻转率越高，节点的活性越高，反之，节点的活性越低，难以翻转或者达到稀有状态值.在通常情况下，当节点的翻转率低于某个阈值（例如，Ye等^[10]定义为0.02），则认定其为少态节点.

以一个例子简单介绍节点翻转率与少态节点判定标准,如图1所示. 图中，L为节点A的逻辑值，T为节点A的时钟周期，该图表示节点A在6个时钟周期内的逻辑状态转移. 由图可知，节点A出现逻辑值1和0的概率均为1/2，所以静态翻转率为1/4；节点A在6个时钟周期内仅翻转1次，所以动态翻转率为1/6. 静态翻转率是基于逻辑值的活性判断方法，只适用于判定组合电路的节点活性；动态翻转率是基于状态跳变的活性判断方法，不仅适用于判定组合电路的节点活性，也适用于判定时序电路的节点活性.

为了规避传统的功能测试和结构测试，少态节点是硬件木马的理想植入位置，其难以翻转或者达到稀有状态值的特点，能够保证硬件木马难以被激活并被发现.组合型硬件木马以电路内部节点的逻辑值作为硬件木马的激活条件；时序型硬件木马监测电路内部节点的状态跳变. 当内部节点的逻辑组合值和状态跳变满足激活条件时，硬件木马被触发.因此，本研究利用动态翻转率作为电路节点的衡量标准，寻找并定位电路中所有少态节点，利用遗传算法筛选能快速提升少态节点活性的测试向量集.

Xue等^[9]提出的节点活性提升方法在提高少态节点翻转率的同时，也提升了电路的整体翻转率.少态节点的翻转引起的影响很容易被整体电路的翻转所淹没，不能凸显少态节点的活性提升效率.因此，引入相对翻转率表征少态节点在电路中的相对活性，表达式为

(1) ${P_{\rm x}} = {{{S_{\rm c}}} / {{S_{\rm z}}}}.$

式中：P_x为相对翻转率；S_c为少态节点的翻转次数之和；S_z为电路所有非少态节点翻转次数之和.少态节点的相对翻转率增大，表明少态节点在电路中的翻转次数所占比重增加.

遗传算法是模拟自然选择和遗传进化的计算模型^[11]，以随机个体为出发点，无需任何先验知识，利用适应度函数评估个体的优劣，通过选择、交叉和变异3个算子在整个搜索空间内寻找最优个体.适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定.这一特点使得遗传算法的应用范围大大扩展.在搜索空间上寻找能快速使少态节点翻转的测试向量，该过程类似于在解空间中搜索最优解，而遗传算法具有收敛速度快和全局搜索能力强的特点，所以本研究使用遗传算法在向量空间内搜索能有效提升少态节点相对翻转率的测试向量.遗传算法有5个构成要素，分别为染色体的编码、适应度函数、选择算子、交叉算子和变异算子.

编码就是将问题的解空间转换成遗传算法所能处理的搜索空间，对问题的解空间进行编码，使其能够被遗传算法的算子操作^[12]. 测试向量均为二值符号串，所以采用二进制编码方法进行遗传算法的编码操作. 二进制编码是遗传算法中常用的编码算法. 编码符号集是二值符号集{0,1}，其个体基因是二值符号串.

在遗传算法中个体适应度反映每个个体相对于整个群体的相对适应性，其大小决定了其是否能继续繁衍，适应度高的个体被复制到下一代的可能性高于适应度低的个体^[13]. 本研究须生成可提高少态节点相对翻转率的测试向量，所以用所有少态节点的翻转次数之和表示每个个体的适应度，将遗传算法的搜索方向设为寻找能提高少态节点翻转率的个体. 个体适应度的表达式为

(2) $ f = \mathop \sum \nolimits_{k = 1}^N {R_{\rm{count}}}\left( k \right). $

式中：R_count为少态节点的翻转次数；k为相应的少态节点；N为少态节点总数.

选择算子模拟自然选择过程，依据适应度选择个体生存或淘汰. 若使用轮盘赌选择方法进行选择操作，每个个体被选择的概率与其适应度成正比，种群中适应度过高的个体会被迅速选择、复制遗传，导致算法提前收敛于局部最优解. 因此，对个体使用排序选择法进行选择操作. 具体操作方法如下：在计算每个个体的适应度后，根据其适应度大小对种群中的个体排序，再将事先设计好的概率表分配给各个个体，所有个体按适应度大小排序，选择概率P_s (i)与适应度的取值无关，仅与序号相关. 个体被选择的概率的表达式^[14]为

(3) $ P_{\rm{s}}\left( i \right) = a{(1 - a)^{i - 1}}. $

式中：a为选择参数，a∈(0，1.0)，根据文献[14]，取a=0.236；i为个体适应度由大到小的排序序号.

交叉算子模仿基因重组过程，依据交叉概率决定两个体是否进行交叉操作，其作用在于将父代的优良基因遗传给下一代，并生成包含更复杂结构的新个体. 对于符号串较长的个体，单点交叉不能保证种群的多样性，所以本研究使用多点交叉. 多点交叉是指在一对父代个体中随机选择多个交叉点，在交叉点间进行基因交换得到子代个体. 如图2所示，交叉点在第4、7、10位，将交叉点之间的符号串相互交换，最终得到2个新的个体.交叉概率越高，探索新的解空间的能力越强，但优良基因的丢失概率也相应提高；交叉概率过低则可能导致搜索阻滞^[15]. 一般交叉概率P_c∈(0.6，1.0)，本研究须保留种群中的优良个体，而搜索阻滞会影响算法效率，所以取P_c=0.6.

利用变异算子模拟基因突变现象，如图3所示. 以变异概率选择基因符号串中的第2、7、11位，并改变该基因值. 变异概率太小会造成种群多样性差，易出现早熟问题；若变异概率过高，算法就会变成随机搜索. 一般变异概率P_m的取值范围为0.005~0.050，早熟问题会导致算法收敛于局部最优解^[16]，而随机搜索虽然会降低算法效率，但是仍可以找到最优测试向量，所以取P_m=0.05.

使用遗传算法对测试向量进行迭代. 以随机生成的测试向量组作为初始化种群，以少态节点的翻转次数作为适应度，具体步骤如下：1）搭建测试平台，产生随机测试向量，并使其激励电路. 围绕原始电路搭建测试平台，使用模拟器编译器(verilog compiler simulator, VCS)仿真工具对原始电路进行仿真测试并保存仿真过程文件（saif文件）. 2）统计电路节点的翻转率. 根据电路的仿真过程saif文件，使用shell编程脚本统计电路节点的翻转次数，进而确定各个节点的翻转概率. 3）设定临界概率阈值P_th，并确定电路中的少态节点. 设定P_th，将翻转概率小于P_th的节点认定为少态节点，同时去除重复节点和不活动节点. 4）初始化测试向量组. 生成随机测试向量组作为初始种群，并设定交叉概率、变异概率和最大迭代次数等参数. 5）计算每个个体的适应度. 根据少态节点的翻转次数计算每个个体的适应度.当所有个体适应度之和大于设定阈值时停止算法，并输出这一代测试向量组；否则继续算法. 6）对种群中的个体进行选择、交叉和变异操作. 根据每个个体的适应度对种群中的个体进行选择操作，舍弃适应度较低的个体，对适应度较高的个体进行交叉和变异操作，产生下一代个体. 7）判断种群适应度是否提升，若种群适应度减小，则保留父代个体，并返回步骤6）；否则保留子代个体. 8）判断迭代终止条件是否满足. 判断当前迭代次数是否大于最大迭代次数，如果大于则输出这一代测试向量组；否则返回步骤5）继续进行迭代操作.

本研究以与Chakraborty等^[7]的研究中相同的ISCAS'85基准电路中的c3540为研究对象. 将100 000个随机向量输入到电路中，根据Ye等^[10]的研究设定P_th=0.02，以此为标准寻找少态节点. 筛选出的8个节点如表1所示. 表中，P为翻转概率. 在随机生成的100 000个测试向量中，8个少态节点共翻转了11 656次，平均每1 000个向量使少态节点翻转了117次.

本研究以100个向量为一个体，10个个体为一种群进行遗传算法运算. 设最大迭代次数为500，种群的适应度随每代的变化如图4所示. 图中，K为种群代数，F为种群适应度之和. 可以看出，种群在第310代时开始收敛. 最终生成的10组测试向量的适应度之和为678，而算法运行前10组向量适应度为117，平均每组向量适应度为原有向量的5.79倍. 适应度最大的向量组的适应度为97，原有向量组的适应度为12，遗传算法得到的最优解将少态节点的翻转次数提高了8.08倍.

本研究共用遗传算法对10个种群进行迭代，在从这10个不同种群中找出适应度最大的10个个体向量输入到c3540电路后，8个少态节点的翻转概率如表2所示. 对比表1、2，表2中少态节点的翻转率平均增大了7.53倍，其中n651节点的翻转率提高了12.18倍.

如图5所示为算法运行前后电路节点翻转率的分布情况. 图中，N'为节点个数. 可以看出，在算法运行后，电路中原有的少态节点的翻转率提高，这些节点已经属于非少态节点；电路中翻转率大于0.4的节点个数减小；翻转率为0.1~0.4的节点数量增加. 电路整体翻转率没有明显提高，具体的定量分析如下：在算法运行前，当以每1 000个向量为输入时，电路中所有非少态节点的翻转次数之和为155 158，少态节点翻转次数之和为117；在算法运行后，当以每1 000个向量为输入时，电路所有非少态节点的翻转次数之和为157 146，少态节点翻转次数之和为882. 少态节点的翻转次数提高了7.54倍，电路整体翻转率仅提高了1.02倍，少态节点的相对翻转率提升了7.44倍.

本研究搭建FPGA测试平台，验证向量对少态节点的活性的提升效果. 将优化向量存储在FPGA内部的ROM中，逐次读取ROM内数据作为c3540电路的激励向量. 为了有效计算少态节点的翻转次数，将电路中的少态节点与计数器相连，利用在线逻辑分析仪ChipScope统计计数器的计数值，该计数值代表少态节点的翻转次数. 实验结果表明，当以每1 000个向量为输入时，电路少态节点翻转次数之和为882，与仿真结果一致，证明了优化向量的有效性.

针对电路中易被攻击者利用而植入硬件木马的少态节点，提出基于遗传算法的少态节点活性提升方法，利用遗传算法的全局寻优能力，将电路中所有少态节点的翻转次数之和作为适应度，并对测试向量进行选择、交叉和变异操作生成能有效提升少态节点活性的测试向量. 仿真结果表明，该方法能将电路中的少态节点活性提高到原来的7.54倍，同时少态节点的相对翻转率提升了7.44倍. 本研究仅以ISCAS'85基准电路中的c3540为研究对象进行仿真验证，须在今后的研究中增加待测电路的多样性，对一些更加复杂的电路进行仿真验证，如AES电路等.