一种基于电路划分的模拟电路IP核保护算法

谢 敏，杨 帆，曾 璇

（复旦大学 专用集成电路与系统国家重点实验室，上海 201203）

随着超大规模集成电路技术的发展以及片上系统（System on a Chip，SoC）的出现，基于IP（Intellectual Property）的SoC设计成为目前工业界最常用的芯片设计方法.使用IP 核不仅可以有效地控制设计费用、缩短设计周期，还可以提高产品质量，但是目前非法者盗取IP核的行为屡禁不止，损害了IC芯片设计者的版权和经济利益，也对使用者带来了一定的安全风险［1］.目前，非法者主要通过以下3种方式盗取IP核的内容：（1）通过窃取HDL（Hardware Description Language）文件或者网表文件制作非法IP核；（2）制造代工厂对版图文件或者版图进行非法拷贝，制作非法硬核；（3）利用解剖芯片和反向工程非法盗取IP核内容.这些方式说明了IC设计的每一步流程都容易被非法者用来盗取芯片信息，因此设计出IP核加密算法，对芯片设计流程进行保护，具有重要意义.理想的芯片加密过程必须不仅能对电路结构起到保护作用，同时还不能严重影响电路性能以及电路的前端和后端设计.

目前对数字电路进行加密的算法已经比较成熟，主要分为标签技术、数字水印技术和数字指纹技术.标签技术指的是将一块电子“标签”放在芯片内部，用来判别芯片的真伪.Majzoobi等［2］提出了一种基于电子标签的PUF（Physical Unclonable Functions）新技术，这种技术在芯片内部设置一个RFID（Radio Frequency Identification）标签，将芯片保护起来，防止其被克隆.标签技术的优点在于其较高的可信度和优越的跟踪性，但是由于“标签”具有一定的独立性，所以这种技术在一般情况下只能起到“威慑”作用，盗版者有可能将所放置的“标签”去除或破坏.

数字水印技术可以克服标签法的劣势嵌入到设计中.Liang等［3］提出了基于向量最小相关度的多扫描链算法，首先由伪随机测试向量产生器生成扫描输入的测试向量序列，然后测试向量序列与被测电路相结合构建出带有最小相关度向量的多扫描链水印结构，通过对该水印结构添加约束，水印可以被限制在特定的扫描单元里.数字水印技术具有不可见和抗攻击的能力，但是水印具有可被修改或移除的风险，并且不具有用户密钥唯一性.

数字指纹的主要优势在于对每个不同用户发放拥有独特指纹的IP设计，便于进行IP的侵权追踪，追究非法用户的责任.但是最大的难点是需要实现大量拥有相同功能和技术指标并具有独特性的IP设计，而且要有较高的抗合谋攻击能力.数字指纹技术目前具有代表性的算法是由Lach等［4－5］提出的一种基于解决方案的IP指纹保护技术.它以解决方案的划分为基础，首先将最初的解决方案划分成很多部分，然后为各个部分提供了不同的实现形式，通过对不同部分实现形式的不同组合完成功能相同且结构不同的IP设计.

模拟电路在飞速发展的集成电路技术中的地位和作用是不可替代的.然而模拟电路不仅对速度、精度以及功耗等多种性能有较高的要求，同时模拟电路对噪声、串扰等比数字电路要敏感得多，因此目前对模拟电路的IP保护相关的算法和实现并不多.Irby等［6］提出了针对模拟电路的版图进行保护的方法，首先根据电路中所有晶体管的类型和宽长比将晶体管进行排序，然后将加密水印嵌入到用于电路版图的晶体管叉指数（finger）中.这种方法相当于对模拟电路的参数进行加密，但并没有扰乱模拟电路的拓扑结构，因此加密性能并不高，同时它只在版图级别进行加密，并没有对电路网表起到保护作用.

本算法提出了一种基于电路划分的模拟电路IP核保护算法，首先将模拟电路建模成带权超图，然后通过对带权超图进行最大割划分，在划分割边处对线网进行扰动加密，对模拟电路的拓扑结构起到隐蔽作用.该算法可以有效保护模拟电路IP 核的内容，并不影响电路的实际功能，同时带来的面积开销和对电路性能的影响也在可接受的范围内.

1 背景回顾

本文涉及到一些基本的电路图划分的概念，如超图、带权超图、电路图划分等，下面进行简单的定义和介绍.

超图：超图是一种广义上的图，由节点集合和超边集合组成，超边可以连接两个或者多个节点.对于超图HG＝（V，Eh），其顶点集V＝｛vi｜1≤i≤n｝，超边集Eh＝

带权超图：节点或者超边含有权重的超图称为带权超图.用映射S：V——R 定义节点的权值，即S（vi）表示结点vi的权值；用映射W：Eh——R 定义边的权值，即的权值［7］.

模拟电路的超图模型：由于在模拟电路中，存在多个晶体管连接到同一个信号节点的结构，因此一般用超图模型来表示模拟电路［8］.如图1所示，用超图中的各个节点来表示电路中各个器件，用超图中的超边来表示器件间的连接关系，器件的大小（面积）用节点的点权重来表示，器件间连接关系的重要性用超边的权重来表示.

超图划分与割边：对于带权超图HG＝（V，Eh），给定的二分划分为P＝（V1，V2），其中V1和V2满足：V1∪V2＝V，V1∩V2＝Ø.该划分的割边为属于不同划分子集的超边权重之和，记为：cut（P）.如图2所示，超图的最大割划分问题就是找到一种划分方案P，使得割边cut（P）最大.

图1 （a）模拟电路图和（b）对应的超图模型Fig.1 （a）Analog circuit diagram and（b）corresponding hypergraph model

图2 超图划分示例Fig.2 Hypergraph partition diagram

2 基于电路划分的模拟电路IP核保护算法

为了实现模拟电路IP核保护，本算法主要通过修改电路网表，对电路中的线网加密，从而扰乱电路的拓扑结构实现IP核保护.首先通过分析电路网表将模拟电路建模成带权超图，然后对该带权超图进行最大割划分，在电路图的割边处进行线网加密，增强了IP 核内部模拟电路拓扑结构的隐蔽性，起到了保护模拟电路IP核的作用.同时，该加密网表并不影响后端仿真工作人员制作版图和仿真验证，对于根据加密网表制作出来的版图，使用正确开关序列密码开启电路后，即可获得正常的电路功能，并且加密处理对原电路带来的性能和面积开销也在可接受的范围之内.

2.1 电路的超图模型和最大割划分算法

本文提出的算法是基于对电路图拓扑结构的非关键路径进行线网加密，起到扰乱电路拓扑结构的作用.为了最大程度地实现对拓扑结构的扰动，我们选择对电路拓扑结构的划分最大割处进行线网扰动加密，以实现最高效地隐蔽到原电路拓扑结构中的作用.

由于模拟电路中通常包含有大量的对称结构（如差分电路等），在对称结构处进行划分一方面无法对网表进行加密；另一方面，在对称处进行划分还会破坏电路原有的对称关系，导致电路性能降低，甚至出现功能错误.因此，我们要避免在电路对称处进行划分.另外，模拟电路中还会存在一些关键结构，这些关键结构会决定电路性能，我们也希望在电路划分时，不要破坏这些结构.为此，我们提出了一种降低对称或关键结构处超边权重的方法来避免在对称处进行划分.该方法的主要思想是降低对称或关键结构部分的边权重，使得最大割不发生在对称或关键结构部分.我们将这些对称结构的超边的权重w′i，j降低为原权重wi，j的，其中n大于1，即

这里n是一个经验参数，一般可以取10～100之间的数值，电路构成超图的原始边权重取为1.对称结构可以通过用户指定或通过自动的对称结构检测算法来检测［9］，关键结构则由用户来指定.

电路的划分子集数对电路性能和加密强度有较大影响，通过实验验证，本文提出的算法对于晶体管数目少于50个的电路，设置划分子集数k为2；对于晶体管数目大于50个的电路系统，设置划分子集数k为［N／m］＋1，取m＝50.

构造完电路的带权重的超图模型后，我们需要求解超图的k－划分最大割问题，即将超图划分为k 个划分子集，并使得划分后电路的割边权重之和最大.超图的k－划分最大割问题是一个NP难问题，对于大规模问题，无法在有限时间内求得最优解.近年来，发展了很多超图的k－划分最大割问题的近似算法：Andersson和Engebretsen［10］为普通超图的最大割划分问题提出了一种基于最大集合分割和线性规划的算法；Ageev和Sviridenko［11］针对给定划分子集数目的小规模超图最大割划分问题，提出了一种基于管道舍入技术的随机算法；Zhu［12］提出了一种基于确定局部搜索计数的算法.

传统的FM 算法［13］被用于求解超图的k－划分最小割问题，该算法可以高效求解大规模问题，并可以获得较为优化的解.本文是基于FM 算法的多层次迭代二分划分方法［14］进行修改来求解超图的k－划分最大割问题，其主要思想是从电路的随机划分出发，对电路的划分进行迭代改进，使划分的割最大.本文的k划分最大割算法主要步骤如下：

（1）读取电路网表，建立带权超图模型，根据电路结构进行权重预处理并指定划分子集个数k；

（2）根据超边连接关系计算所有器件结点的增益，利用桶结构和双向链表存储所有结点的增益，并对超图模型进行初始二分划分，平衡系数根据k的大小确定；

（3）每次挑选增益最大的结点进行移动，每次移动尝试后设置该结点为“锁定”状态，并记录每一次移动后的割边权重，直到所有结点都为“锁定”状态；

（4）挑选取得割边权重最大的前n次操作，确定并记录本次二分划分的结果和割边权重；

（5）如果目标划分子集数k大于当前已有划分数目，更新带权超图模型，迭代执行步骤（2）、（3）、（4），直至算法结束.

2.2 线网加密方法

在对电路超图进行划分后，我们对划分结果的割边线网进行加密处理，主要通过添加混淆开关来实现.我们可以选择对所有割边线网进行加密，也可以从其中选择部分线网进行加密.对于n 条割边，存在种连接方式，这里表示全排列.如果对该连接关系加密，非授权者在没有拿到正确密码的情况下，找到正确的开关序列的概率是，具有较好的加密强度.为了对线网连接关系进行加密，我们需要添加n2个开关来控制线网的连接关系.

我们以图3为例来介绍线网加密方法，线网AC和线网BD 跨接在两个子集之间，为了对此线网进行加密，我们通过修改网表，添加新线网AD 和BC，同时在线网AC、AD、BC、BD 中间添加开关，4个开关依次为T1、T2、T3和T4.这样两个子集之间总共有2种连接方式，其中T1和T4闭合、T2和T3断开是正确的开关设置方式，开关序列密码为1001；T2和T3闭合、T1和T4断开是错误的开关设置方式，开关序列密码为0110.因此，对于此种情况，非授权者找到正确开关的概率是0.5.

图3 线网加密图示Fig.3 Net encryption diagram

线网加密的开关是由MOS管传输门来实现.如图4所示，T1为NMOS管，T2为PMOS管，NMOS管的衬底端接地，PMOS管的衬底接Vdd，两个栅极是控制信号，输入信号互补，源级和源级相接，作为输入端，漏极和漏极相接，作为输出端.通过C 和信号来控制传输门的通断，从而控制电路的连接关系［15］.

图4 传输门实现模拟开关图示Fig.4 Analog switch implemented by transmission gate diagram

3 实验结果及分析

为了验证本文提出的算法的可行性和有效性，我们选取了几类典型的模拟电路进行试验，包括缓冲器、比较器、负压电荷泵等.通过本文实现的网表加密软件对电路网表进行加密处理，该软件由C＋＋语言实现，由3267行代码组成，输入为模拟电路网表，输出为添加完加密开关的网表.对网表加密前后的电路都使用Cadence的SPECTRA 工具进行仿真.

（1）缓冲器

如图5（a）所示，缓冲器电路由一个接成闭环工作形式的两级放大器构成，用来对输入信号进行缓冲，提高其驱动能力.图5（b）为对该缓冲器电路的线网进行加密处理过的电路.

仿真时设置电源电压为4V，输入信号为2V.由于该电路测例共含有10个晶体管，因此设置划分子集数为2.

直流仿真结果如下：当不加线网加密开关时，缓冲器的输出为2.000 6V；当加入正确的控制信号（即开关序列码为1001）时，缓冲器的输出为2.000 6V，功能正常；当加入与正确控制信号完全相反的信号（即开关序列码为0110）时，缓冲器的输出为3.996V，功能错误；当输入开关序列为1111时，缓冲器输出电压为3.174V，功能错误.当不加线网加密开关时，缓冲器的面积为175μm2，添加开关后的面积为179μm2，面积增加了2.3%.

交流仿真结果如下：当不加线网加密开关时，缓冲器环路的频率响应曲线如图6（a）所示，交流小信号增益为100.1dB，单位增益带宽为10.25MHz，相位裕度为104.5°；当加入正确的控制信号（即开关序列码为1001）时，缓冲器环路的频率响应曲线如图6（b）所示，交流小信号增益为100.3dB，单位增益带宽为10.46MHz，相位裕度为104°；当加入与正确控制信号完全相反的信号（即开关序列码为0110）时，缓冲器环路的频率响应曲线如图6（c）所示，交流小信号增益为－153.1dB，功能错误；当输入开关序列为1111时，缓冲器环路的频率响应曲线如图6（d）所示，交流小信号增益为－87.02dB，功能错误.

图5 （a）缓冲器加密前电路和（b）缓冲器加密后电路Fig.5 （a）Buffer circuit beforeencryption and（b）buffer circuit after encryption

图6 缓冲器环路频率响应曲线Fig.6 Loop frequency response of buffer circuit

时域瞬态仿真结果如下：当不加线网加密开关时，缓冲器输入与输出的时域波形对比如图7（a）所示，输出信号与输入信号一致，实现了缓冲器的功能；当加入正确的控制信号（即开关序列码为1001）时，缓冲器输入与输出的时域波形对比如图7（b）所示，输出信号与输入信号一致，实现了缓冲器的功能；当加入与正确控制信号完全相反的信号（即开关序列码为0110）时，缓冲器输入与输出的时域波形对比如图7（c）所示，输出信号与输入信号不一致，功能错误；当输入开关序列为1111时，缓冲器输入与输出的时域波形对比如图7（d）所示，输出信号与输入信号不一致，功能错误.

图7 缓冲器时域波形曲线Fig.7 Time domain waveform of buffer circuit

（2）比较器电路

如图8（a）所示，比较器电路由一个开环工作的运算放大器构成，用来实现对两个输入信号大小关系的判断.当两个输入信号中正端比负端大时，输出高电平，反之则输出低电平.图8（b）为对该比较器电路的线网进行加密处理过的电路.

仿真时设置如下：电源电压3.5V，输入信号正端为1.01V，负端为1V.由于该电路测例共含有28个晶体管，因此设置划分子集数为2.

仿真结果表明：当不加线网加密开关时，比较器的输出为3.063V，输出为高电平；当加入正确的控制信号（即开关序列码为0110）时，比较器的输出为3.062V，功能正常；当加入与正确控制信号完全相反的信号（即开关序列码为1001）时，比较器的输出为0.333V，可以视为低电平，功能错误；当输入开关序列分别为0000和1111时，比较器输出电压分别为1.217V 和1.316V，可以视为不确定的逻辑电平，同样属于功能错误.当不加线网加密开关时，比较器的面积为1 982μm2，添加开关后的面积为2 022μm2，面积增加了2%.

图8 （a）比较器加密前电路和（b）比较器加密后电路Fig.8 （a）Comparator circuit before encryption and（b）comparator circuit after encryption

时域瞬态仿真结果如下：当不加线网加密开关时，比较器输入与输出的时域波形对比如图9（a）所示，输出信号反应了两个输入信号的大小关系，实现了比较器的功能；当加入正确的控制信号（即开关序列码为0110）时，比较器输入与输出的时域波形对比如图9（b）所示，输出信号反应了两个输入信号的大小关系，实现了比较器的功能；当加入与正确控制信号完全相反的信号（即开关序列码为1001）时，比较器输入与输出的时域波形对比如图9（c）所示，输出信号错误地反应了两个输入信号的大小关系；当输入开关序列为1111时，比较器输入与输出的时域波形对比如图9（d）所示，输出信号无法反应两个输入信号的大小关系，功能错误.

图9 比较器时域波形曲线Fig.9 Time domain waveform of comparator circuit

（3）负压电荷泵电路

如图10所示，图10（a）的负压电荷泵电路由时钟产生电路和电荷转移电路构成，用来把输入的正电压转换为相对应的负电压.图10（b）为对负压电荷泵电路的线网进行加密处理过的电路.

图10 （a）负压电荷泵加密前电路和（b）负压电荷泵加密后电路Fig.10 （a）Negative charge pump circuit before encryption and（b）negative charge pump circuit after encryption

仿真时设置输入电源电压3.5V.由于该电路测例共含有143个晶体管，因此我们设置划分子集为3个.仿真结果表明，当不加线网加密开关时，负压电荷泵的输出为－3.384V；当加入正确的控制信号（即开关序列码为100010001100010001）时，负压电荷泵的输出为－3.352V，与不加开关时的输出电压偏移1.4%，功能正常；当加入与正确控制信号完全相反的信号（即开关序列码为011101110011101110）时，负压电荷泵的输出为－2.41V，功能错误；当输入开关序列为000000000000000000时，负压电荷泵输出电压为2mV，功能错误；当输入开关序列为非正确的另一任意序列100111010110100101时，负压电荷泵输出电压为－1.323mV，功能错误.当不加线网加密开关时，负压电荷泵的面积为37 000μm2，添加开关后的面积为37 100μm2，面积增加了0.27%.

时域瞬态仿真结果如下：当不加线网加密开关时，负压电荷泵输出的时域波形如图11（a）所示，充放电周期为1.216μs，输出电压达到－3.384V；当加入正确的控制信号（即开关序列码为100010001100010001）时，负压电荷泵输出的时域波形如图11（b）所示，充放电周期为1.23μs，输出电压达到－3.352V；当加入与正确控制信号完全相反的信号（即开关序列码为011101110011101110）时，负压电荷泵输出的时域波形如图11（c）所示，输出电压只有－2.41V，功能错误.

从上述仿真结果可知，本文提出的基于电路划分的算法能对模拟电路的拓扑结构起到较好的保护作用.如果开关密码设置正确，就能得到正确的电路功能；否则，电路功能会出现错误或者电路性能会受到较大影响.同时由线网加密带来的面积开销也在可接受的范围之内.

图11 负压电荷泵时域波形曲线Fig.11 Time domain waveform of negative charge pump circuit

4 总结

本文提出了一种基于电路划分的模拟电路IP核保护算法，首先将模拟电路建模成带权超图，利用超图划分算法进行划分，然后对割边线网进行加密，从而扰乱模拟电路的拓扑结构.通过对典型的模拟电路进行仿真验证，本算法可以有效保护模拟电路IP核，同时对电路性能的影响和面积开销也处于可接受的范围.由于本算法只针对模拟电路的拓扑结构进行了加密，属于静态加密，未来考虑引入动态加密信息，进一步提高加密性能.

［1］Chakraborty R S，Bhunia S.HARPOON：An obfuscation－based SoC design methodology for hardware protection［J］.Computer－Aided Design of Integrated Circuits and Systems，IEEE Transactions on，2009，28（10）：1493－1502.

［2］Majzoobi，M，Koushanfar，F，Devadas，S.FPGA PUF using programmable delay lines［C］∥International Workshop on Information Forensics and Security（WIFS）.Seattle，USA：IEEE Press，2010：1－6.

［3］Liang W，Zhang D F，Long J，et al.An IP protection algorithm by watermarking multiple scan chains based on minimum correlation degree of vectors［C］∥High Performance Computing and Communications＆ 2013 IEEE International Conference on Embedded and Ubiquitous Computing（HPCC＿EUC）.Zhangjiajie，China：IEEE Press，2013：533－540.

［4］Lach J，Mangione－Smith W H，Potkonjak M.FPGA fingerprinting techniques for protecting intellectual property［C］∥Custom Integrated Circuits Conference.San Jose，USA：IEEE Press，1998：299－302.

［5］Lach J，Mangione－Smith W H，Potkonjak M.Fingerprinting techniques for field－programmable gate array intellectual property protection［J］.IEEE Transactions on Computer－Aided Design of Integrated Circuits and Systems，2001，20（10）：1253－1261.

［6］Irby D L，Carothers R D，Rodriguez J D，et al.Low level watermarking of VLSI designs for intellectual property protection［C］∥13th Annual IEEE International Conference on ASIC／SOC.Arlington，USA：IEEE Press，2000：136－140.

［7］冷明平，孙凌宇，郭恺强，等.赋权超图划分算法的电路划分实验比较研究［J］.计算机工程与应用，2012，48（16）：74－79.

［8］薛冀颖，孙 楠，张 炜，等.一种新的基于晶体管级的电路划分算法［J］.电子与信息学报，2009，31（12）：2980－2983.

［9］Bhattacharya S，Jangkrajang N，Hartono R，et al.Hierarchical extraction and verification of symmetry constraints of analog layout automation［C］∥ASP－DAC′04.Yokohama，Japan：IEEE Press，2004：400－405.

［10］Andersson G，Engebretsen L.Better approximation algorithms for SET SPLITTING and NOT－ALLEQUAL SAT［J］.Information Processing Letters，1998，65（6）：305－311.

［11］Ageev A，Hassin R，Sviridenko M.A 05－approximation algorithm for max dicut with given sizes of parts［J］.SIAM Journal on Discrete Mathematics，2001，14（2）：246－255.

［12］Zhu W，Guo C.A local search approximation algorithm for Max－k－Cut of graph and hypergraph［C］∥International Symposium on Parallel Architectures，Algorithms and Programming（PAAP）.Tianjin，China：IEEE Press，2011：236－240.

［13］Fiduccia C M，Mattheyses R M.A linear－time heuristic for improving network partitions［C］∥Design Automation Conference.Las Vegas，USA：IEEE Press，1982：175－181.

［14］毕查德·拉扎维.模拟CMOS集成电路设计［M］.陈贵灿，程军，张瑞智等译.西安：西安交通大学出版社，2003.

［15］Karypis G，Kumar V.hMETIS 15：A hypergraph partitioning package［R］.University of Minnesota：Department of Computer Science，1998.