启发式逻辑逆向综合算法研究
|
摘要
在线式芯片逆向分析方法是芯片逆向分析领域较为常见的方法之一,具有应用范围广、处理速度快等显著优点。随着集成电路制造工艺的发展,芯片结构日益复杂,对其在线逆向分析时采集到的工作数据集规模也急剧膨胀,致使逻辑逆向综合成为在线式逆向分析的瓶颈,即现有的逻辑逆向综合算法处理大规模复杂工作数据集的效率较低。
本文在深入分析在线式解析的数据特点和传统逻辑逆向综合算法的基础上,结合启发式思想,重点研究适于处理大规模、复杂的工作数据集的启发式逻辑逆向综合算法,并开发相应的在线式逻辑逆向综合子系统,以此获得可高效求解函数优化覆盖的能力,提高对逻辑芯片在线式逆向分析的整体效率。主要研究内容和创新点如下:
(1)针对BOOM算法缺少有效的迭代停止条件,提出了在算法的最优字面选择步骤加入辅助规则的方法,即当真值覆盖矩阵的字面频率统计过程出现多个输入位对应的值相等的情况时,结合对假值覆盖矩阵的字面频率统计结果来辅助选择最优字面,保证替换字面后的降维立方体与较少的OFF点存在相交关系,加快OFF集为空的速度,从而避免因随机选择而导致耗费大量时间却无法减小假值覆盖矩阵的规模的情形发生,以减少算法的迭代次数。
(2)针对EspressoII算法处理大规模零维体数据集时空开销大的问题,结合改进BOOM算法和EspressoII算法,设计了能够高效处理大规模工作数据集的Es-ImpBOOM算法。该算法首先利用改进BOOM算法对初始数据集进行初步优化,较大程度减小待处理数据集的规模,然后才采用EspressoII算法求解优化覆盖,从而提高在线式逻辑逆向综合的效率。
(3)针对解耦合模式无法高效处理大输出变量数据集的问题,介绍并详细分析了适于求解大输出变量数据集的优化覆盖的FC-Min算法。该算法直接以多输出形式的初始覆盖为原始解,通过搜索输出蕴涵矩阵和构造蕴涵项两个步骤求得优化覆盖,免去阵列分离和求解共享乘积项过程,从而能够在合理的时间和空间范围内求得优化覆盖。并在此基础上,针对FC-Min算法求得的优化覆盖因存在冗余项而导致输出成本较高的问题,对算法进行了改进。改进后的FC-Min算法通过加入去冗余项步骤,能够以较少的时间开销代价较大程度地降低优化覆盖的成本。
(4)根据在线式芯片逆向分析系统的实际需要,基于以上优化覆盖求解算法设计并实现了在线式逻辑逆向综合子系统。测试结果表明,在线式逻辑逆向综合子系统能够快速、准确地完成对在线数据集的优化处理,符合在线式芯片解析系统的要求。
The on-line reverse decrypting is an important validation method. It has wide application, fast processing speed and other significant advantages. With the development of integrated circuit manufacturing process and increasing complexity of chip structure, its online reverse analysis of working data sets collected from the on-line reverse decrypting expansion rapidly in scale, resulting in that the traditional logic synthesis algorithm can’t meet the requirement of cosmic-scale data processing.
Based on analyzing traditional logic synthesis algorithm deeply, this paper emphasizes studying logic reversible synthesis algorithm under the condition of the cosmic-scale working data size combining features of data collecting in the on-line reverse decrypting process. The major research content and development are as follows:
1. Contrary to the BOOM algorithm lack of effective stop condition, the paper proposed an assistant rule. Through this adding rule, the improved BOOM algorithm can reduce the number of iterations of the algorithm.
2. Combined with the improved BOOM algorithm and EspressoII algorithm, this paper designed the Es-ImpBOOM algorithm which can efficiently handle the large scale of working data sets. In this algorithm, firstly using BOOM algorithm to optimized the initial data set in order to reduce the size of data sets to be processed, and then employ EspressoII algorithm to get the optimal cover.
3. For the problem that the decoupled model can not efficiently handle the large number of output variable type of data sets, the paper describes and gives a detailed analysis of FC-Min algorithm which is suitable for solving optimal coverage of large output variable types of data sets. And then in allusion to the problem that the output cost of optimal cover solved by FC-Min algorithm is higher than required, the paper presents an improved algorithm. The improved algorithm can spend less time to reach a greater extent to reduce the output cost.
4. Based on the above various algorithms, this paper designs and implements the on-line reversible logic synthesis subsystem combining the pratical demand of on-line decrypting system of the logci indefinite chips to reversible system. The results show that the reverse logic synthesis subsystem can accomplish quickly and accurately optimizing the on-line data set to meet online chip analysis systems.
本文在深入分析在线式解析的数据特点和传统逻辑逆向综合算法的基础上,结合启发式思想,重点研究适于处理大规模、复杂的工作数据集的启发式逻辑逆向综合算法,并开发相应的在线式逻辑逆向综合子系统,以此获得可高效求解函数优化覆盖的能力,提高对逻辑芯片在线式逆向分析的整体效率。主要研究内容和创新点如下:
(1)针对BOOM算法缺少有效的迭代停止条件,提出了在算法的最优字面选择步骤加入辅助规则的方法,即当真值覆盖矩阵的字面频率统计过程出现多个输入位对应的值相等的情况时,结合对假值覆盖矩阵的字面频率统计结果来辅助选择最优字面,保证替换字面后的降维立方体与较少的OFF点存在相交关系,加快OFF集为空的速度,从而避免因随机选择而导致耗费大量时间却无法减小假值覆盖矩阵的规模的情形发生,以减少算法的迭代次数。
(2)针对EspressoII算法处理大规模零维体数据集时空开销大的问题,结合改进BOOM算法和EspressoII算法,设计了能够高效处理大规模工作数据集的Es-ImpBOOM算法。该算法首先利用改进BOOM算法对初始数据集进行初步优化,较大程度减小待处理数据集的规模,然后才采用EspressoII算法求解优化覆盖,从而提高在线式逻辑逆向综合的效率。
(3)针对解耦合模式无法高效处理大输出变量数据集的问题,介绍并详细分析了适于求解大输出变量数据集的优化覆盖的FC-Min算法。该算法直接以多输出形式的初始覆盖为原始解,通过搜索输出蕴涵矩阵和构造蕴涵项两个步骤求得优化覆盖,免去阵列分离和求解共享乘积项过程,从而能够在合理的时间和空间范围内求得优化覆盖。并在此基础上,针对FC-Min算法求得的优化覆盖因存在冗余项而导致输出成本较高的问题,对算法进行了改进。改进后的FC-Min算法通过加入去冗余项步骤,能够以较少的时间开销代价较大程度地降低优化覆盖的成本。
(4)根据在线式芯片逆向分析系统的实际需要,基于以上优化覆盖求解算法设计并实现了在线式逻辑逆向综合子系统。测试结果表明,在线式逻辑逆向综合子系统能够快速、准确地完成对在线数据集的优化处理,符合在线式芯片解析系统的要求。
The on-line reverse decrypting is an important validation method. It has wide application, fast processing speed and other significant advantages. With the development of integrated circuit manufacturing process and increasing complexity of chip structure, its online reverse analysis of working data sets collected from the on-line reverse decrypting expansion rapidly in scale, resulting in that the traditional logic synthesis algorithm can’t meet the requirement of cosmic-scale data processing.
Based on analyzing traditional logic synthesis algorithm deeply, this paper emphasizes studying logic reversible synthesis algorithm under the condition of the cosmic-scale working data size combining features of data collecting in the on-line reverse decrypting process. The major research content and development are as follows:
1. Contrary to the BOOM algorithm lack of effective stop condition, the paper proposed an assistant rule. Through this adding rule, the improved BOOM algorithm can reduce the number of iterations of the algorithm.
2. Combined with the improved BOOM algorithm and EspressoII algorithm, this paper designed the Es-ImpBOOM algorithm which can efficiently handle the large scale of working data sets. In this algorithm, firstly using BOOM algorithm to optimized the initial data set in order to reduce the size of data sets to be processed, and then employ EspressoII algorithm to get the optimal cover.
3. For the problem that the decoupled model can not efficiently handle the large number of output variable type of data sets, the paper describes and gives a detailed analysis of FC-Min algorithm which is suitable for solving optimal coverage of large output variable types of data sets. And then in allusion to the problem that the output cost of optimal cover solved by FC-Min algorithm is higher than required, the paper presents an improved algorithm. The improved algorithm can spend less time to reach a greater extent to reduce the output cost.
4. Based on the above various algorithms, this paper designs and implements the on-line reversible logic synthesis subsystem combining the pratical demand of on-line decrypting system of the logci indefinite chips to reversible system. The results show that the reverse logic synthesis subsystem can accomplish quickly and accurately optimizing the on-line data set to meet online chip analysis systems.
引文
[1]孙丕恕.关于发展我国集成电路产业的建议[EB/OL].:中国保护知识产权网, 2010-03-17:
[2]张苏.集成电路将长期主导经济发展[N].光明日报,2006,11(30):
[3]王阳元.集成电路产业的科技创新与机制创新[R].北京:中国科学家论坛,2007:
[4]李珂.中国集成电路发展现状与趋势分析[J].中国集成电路,2008,17(8):71-72.
[5] Sergei P. Skorobogatov. Semi-invasive attack-a new approach to hardware security analysis[EB/OL].:http://www.cl.can.ac.uk, 2005.
[6] W.David pan, Mahesh Nalasani. Reversible logic[J], IEEE Potentials. 2005, 24(3):38-41.
[7]周宝华,胡永楠等.可编程逻辑元件逆向工程之研究[J].大叶学报,2001,10(1):79-86.
[8]曾繁泰,李冰等.EDA工程概论[M].北京:清华大学出版社,2002:23-28.
[9]边计年,薛宏熙,苏明,吴为民.数字系统设计自动化[M].北京:清化大学出版社,2005:1-4,193-255.
[10] Hong S, Cain R, Ostapko D.MINI:A heuristic approach for logic minimization.IBM Joural of Research and Development, Vol.18, 1974: 443-458.
[11] Rudell R, Sangiovanni-Vincetrlli A.Multiple-valued minimization of programmable logic arrays[J].IEEE Transcations on CAD/ICAS, Vol.CAD-6, NO.5, 1987: 727-750.
[12] Brayton R, Hachtel G, McMullen C, Sangiovanni-Vincentelli A. Logic minimization algorithms for VLSI synthesis[M].Boston: Kluwer Academic Publishers, 1984:
[13]丛明煜,王丽萍.现代启发式算法理论研究[J].高技术通讯,2003,13(5):105-110.
[14]张德富.启发式算法研究及其应用[D]:华中科技大学博士论文.武汉:华中科技大学,2002.
[15]陈开.启发式优化算法的方法和应用研究[D]:同济大学大学博士论文.上海:同济大学大学,2003.
[16]刘岩.在线式芯片解析中逻辑综合及辅助验证系统的研究与实现[D]:解放军信息工程大学硕士论文.郑州:解放军信息工程大学,2008
[17]邢文训,谢金星.现代优化计算方法(第2版)[M].北京:清华大学出版社,2005:12-14.
[18] Morreale E.Recursive operators for prime implicant and irredundant normat form determination[J].IEEE Transacations on Computers, Vol.C-19, NO.6, 1970: 504-509.
[19] Reuse B.Generations of prime implicants from subfunctions and a unifying approach to the covering problem[J].IEEE Transactions on Computers, Vol.C-24, NO.9, 1975: 924-930.
[20] Sasao T . Input-variable assignment and output phase optimization for PLA optimization[J].IEEE Transactions on Computer, Vol.C-33, 1984: 727-750.
[21]沈嗣昌.计算机辅助逻辑综合[M].北京:高等教育出版社,1983:6-7,8-17,32-37.
[22]管致锦,张义清,邱建林,刘维富.巨大变量组合逻辑设计优化软件的研究与设计[J] .计算机工程,2004,30(19):55-56.
[23] Charies H.Roth,Jr.(美)著.解晓明,黎永志,王坤译.逻辑设计基础[M].第五版.北京:机械工业出版社,59-74.
[24] Ashar P, Devadas S, Newton A.Sequential logic synthesis[M].Boston: Kluwer Academic Publishers, 1992
[25] Villa T, Sangiovanni-Vincentelli A.NOVA: State assignment for finite state machines for optimal two-level logic implementation.IEEE Transactions on CAD/CAS, Vol.C-9, No.9, 1990: 905-924.
[26] Ciesielski M, Shen J, Davio M.A united approach to input–output encoding for FSM state assignment[A] . DAC, Prodeedings of the Design Automation Conference[C], 1991: 176-181.
[27] Yang S, Ciesielski M.Optimum and suboptimum algotithms for input encoding and its relationship to logic minimization[J].IEEE Transactions on CAD/ICAS, Vol.CAD-10, No.1, 1991: 4-12.
[28] Saldanha A, Villa T, Brayton R, Sangiovanni-Vincentelli A.A Framework for satisfying input and output encoding constrains[A].DAC, Prodeedings of the Design Automation Conference[C], 1991: 170-175.
[29]戴世虎.布尔代数[M].湖南:湖南教育出版社,1984:198-264.
[30] M.Morris Mano, Charles R.Kime(美)著.汪东,肖枫涛译.逻辑与计算机设计基础[M].第三版.北京:中国电力出版社,25-38.
[31]邱建林,王波,刘维富.超大变量多值单边逻辑函数优化算法研究[J].计算机研究与发展,2007,44:173-177.
[32] P.Fi?er, J.Hlavika and H.Kubátová. Column-Matching BIST Exploiting Test Don't-Cares“. Proc.8th IEEE Europian Test Workshop (ETW'03), Maastricht (NL), 2003, 215-216.
[33]丁渊.基于子集迭代相交算法的逻辑综合系统设计与实现[D]:解放军信息工程大学硕士论文.郑州:解放军信息工程大学,2007.
[34]郭毅.脱机式芯片解析中数据处理子系统的设计与实现[D]:解放军信息工程大学硕士论文.郑州:解放军信息工程大学,2008.
[35] Ding Yuan, Bai Yan, Lu WenTao, Guo Yi.Research And Implementation Of Reversible Logic Synthesis Algorithm In Digital System[A].The 7th International Conference on Computer– Aided Industrial Design & Conceptual Design[C].Hangzhou, China: IEEE, 2006: 346-352.
[36]管致锦,张义清,邱建林,王波.大变量逻辑函数最佳覆盖问题研究[J].计算机应用与软件,2003,20(12):11-13.
[37] J.Hlavicka and P.Fiser,“BOOM-a Heuristic Boolean Minimizer”, Proc.ICCAD-2001, San Jose, Cal.(USA), 2001, 439-442.
[38] P.Fi(?)er and J.Hlavika, BOOM-A Heuristic Boolean Minimizer“, Computers and Informatics, Vol.22, 2003, No.1, pp.19-51.
[39]黄伟.辑综合中等价验证算法研究[D].上海:复旦大学,2005:
[40] P.Fi(?)er, J.Hlavika and H. Kubátová. FC-Min: A Fast Multi-Output Boolean Minimizer“, Proc. Euromicro Symposium on Digital Systems Design (DSD'03), Antalya(TR), 2003.
[41]邱建林,王波,刘维富.多输人多输出单边逻辑函数优化系统的设计研究[J].南京邮电大学学报:自然科学版,2006,26(5):65-70.
[42]邱建林,陈建平,顾翔等.一种基于积项扩展的大变量多输出逻辑优化算法与实现[J].江南大学学报:自然科学版:2007,6(6):718-722.
[43] Leon Stok, Vivek Tiwari. Logic Synthesis and Verification [M]. Norwell: Kluwer Academic Publishers, 2001: 1-4.
[44] Aviad Mintz, Martin Charles Golumbic. Factoring boolean functions using graph partitionning[J]. Discrete Applied Mathematics, 2005, 149(1): 131-153.
[45]于磊,叶静,郭毅等.支持大规模变量集的近似最小覆盖迭代搜索算法[J].计算机辅助设计与图形学学报,2008,20(6):737-741.
[2]张苏.集成电路将长期主导经济发展[N].光明日报,2006,11(30):
[3]王阳元.集成电路产业的科技创新与机制创新[R].北京:中国科学家论坛,2007:
[4]李珂.中国集成电路发展现状与趋势分析[J].中国集成电路,2008,17(8):71-72.
[5] Sergei P. Skorobogatov. Semi-invasive attack-a new approach to hardware security analysis[EB/OL].:http://www.cl.can.ac.uk, 2005.
[6] W.David pan, Mahesh Nalasani. Reversible logic[J], IEEE Potentials. 2005, 24(3):38-41.
[7]周宝华,胡永楠等.可编程逻辑元件逆向工程之研究[J].大叶学报,2001,10(1):79-86.
[8]曾繁泰,李冰等.EDA工程概论[M].北京:清华大学出版社,2002:23-28.
[9]边计年,薛宏熙,苏明,吴为民.数字系统设计自动化[M].北京:清化大学出版社,2005:1-4,193-255.
[10] Hong S, Cain R, Ostapko D.MINI:A heuristic approach for logic minimization.IBM Joural of Research and Development, Vol.18, 1974: 443-458.
[11] Rudell R, Sangiovanni-Vincetrlli A.Multiple-valued minimization of programmable logic arrays[J].IEEE Transcations on CAD/ICAS, Vol.CAD-6, NO.5, 1987: 727-750.
[12] Brayton R, Hachtel G, McMullen C, Sangiovanni-Vincentelli A. Logic minimization algorithms for VLSI synthesis[M].Boston: Kluwer Academic Publishers, 1984:
[13]丛明煜,王丽萍.现代启发式算法理论研究[J].高技术通讯,2003,13(5):105-110.
[14]张德富.启发式算法研究及其应用[D]:华中科技大学博士论文.武汉:华中科技大学,2002.
[15]陈开.启发式优化算法的方法和应用研究[D]:同济大学大学博士论文.上海:同济大学大学,2003.
[16]刘岩.在线式芯片解析中逻辑综合及辅助验证系统的研究与实现[D]:解放军信息工程大学硕士论文.郑州:解放军信息工程大学,2008
[17]邢文训,谢金星.现代优化计算方法(第2版)[M].北京:清华大学出版社,2005:12-14.
[18] Morreale E.Recursive operators for prime implicant and irredundant normat form determination[J].IEEE Transacations on Computers, Vol.C-19, NO.6, 1970: 504-509.
[19] Reuse B.Generations of prime implicants from subfunctions and a unifying approach to the covering problem[J].IEEE Transactions on Computers, Vol.C-24, NO.9, 1975: 924-930.
[20] Sasao T . Input-variable assignment and output phase optimization for PLA optimization[J].IEEE Transactions on Computer, Vol.C-33, 1984: 727-750.
[21]沈嗣昌.计算机辅助逻辑综合[M].北京:高等教育出版社,1983:6-7,8-17,32-37.
[22]管致锦,张义清,邱建林,刘维富.巨大变量组合逻辑设计优化软件的研究与设计[J] .计算机工程,2004,30(19):55-56.
[23] Charies H.Roth,Jr.(美)著.解晓明,黎永志,王坤译.逻辑设计基础[M].第五版.北京:机械工业出版社,59-74.
[24] Ashar P, Devadas S, Newton A.Sequential logic synthesis[M].Boston: Kluwer Academic Publishers, 1992
[25] Villa T, Sangiovanni-Vincentelli A.NOVA: State assignment for finite state machines for optimal two-level logic implementation.IEEE Transactions on CAD/CAS, Vol.C-9, No.9, 1990: 905-924.
[26] Ciesielski M, Shen J, Davio M.A united approach to input–output encoding for FSM state assignment[A] . DAC, Prodeedings of the Design Automation Conference[C], 1991: 176-181.
[27] Yang S, Ciesielski M.Optimum and suboptimum algotithms for input encoding and its relationship to logic minimization[J].IEEE Transactions on CAD/ICAS, Vol.CAD-10, No.1, 1991: 4-12.
[28] Saldanha A, Villa T, Brayton R, Sangiovanni-Vincentelli A.A Framework for satisfying input and output encoding constrains[A].DAC, Prodeedings of the Design Automation Conference[C], 1991: 170-175.
[29]戴世虎.布尔代数[M].湖南:湖南教育出版社,1984:198-264.
[30] M.Morris Mano, Charles R.Kime(美)著.汪东,肖枫涛译.逻辑与计算机设计基础[M].第三版.北京:中国电力出版社,25-38.
[31]邱建林,王波,刘维富.超大变量多值单边逻辑函数优化算法研究[J].计算机研究与发展,2007,44:173-177.
[32] P.Fi?er, J.Hlavika and H.Kubátová. Column-Matching BIST Exploiting Test Don't-Cares“. Proc.8th IEEE Europian Test Workshop (ETW'03), Maastricht (NL), 2003, 215-216.
[33]丁渊.基于子集迭代相交算法的逻辑综合系统设计与实现[D]:解放军信息工程大学硕士论文.郑州:解放军信息工程大学,2007.
[34]郭毅.脱机式芯片解析中数据处理子系统的设计与实现[D]:解放军信息工程大学硕士论文.郑州:解放军信息工程大学,2008.
[35] Ding Yuan, Bai Yan, Lu WenTao, Guo Yi.Research And Implementation Of Reversible Logic Synthesis Algorithm In Digital System[A].The 7th International Conference on Computer– Aided Industrial Design & Conceptual Design[C].Hangzhou, China: IEEE, 2006: 346-352.
[36]管致锦,张义清,邱建林,王波.大变量逻辑函数最佳覆盖问题研究[J].计算机应用与软件,2003,20(12):11-13.
[37] J.Hlavicka and P.Fiser,“BOOM-a Heuristic Boolean Minimizer”, Proc.ICCAD-2001, San Jose, Cal.(USA), 2001, 439-442.
[38] P.Fi(?)er and J.Hlavika, BOOM-A Heuristic Boolean Minimizer“, Computers and Informatics, Vol.22, 2003, No.1, pp.19-51.
[39]黄伟.辑综合中等价验证算法研究[D].上海:复旦大学,2005:
[40] P.Fi(?)er, J.Hlavika and H. Kubátová. FC-Min: A Fast Multi-Output Boolean Minimizer“, Proc. Euromicro Symposium on Digital Systems Design (DSD'03), Antalya(TR), 2003.
[41]邱建林,王波,刘维富.多输人多输出单边逻辑函数优化系统的设计研究[J].南京邮电大学学报:自然科学版,2006,26(5):65-70.
[42]邱建林,陈建平,顾翔等.一种基于积项扩展的大变量多输出逻辑优化算法与实现[J].江南大学学报:自然科学版:2007,6(6):718-722.
[43] Leon Stok, Vivek Tiwari. Logic Synthesis and Verification [M]. Norwell: Kluwer Academic Publishers, 2001: 1-4.
[44] Aviad Mintz, Martin Charles Golumbic. Factoring boolean functions using graph partitionning[J]. Discrete Applied Mathematics, 2005, 149(1): 131-153.
[45]于磊,叶静,郭毅等.支持大规模变量集的近似最小覆盖迭代搜索算法[J].计算机辅助设计与图形学学报,2008,20(6):737-741.