【作者】 钟华；

【导师】 曾光裕；

【作者基本信息】 解放军信息工程大学 ， 计算机应用技术， 2010， 硕士

【摘要】 在线式芯片逆向分析方法是芯片逆向分析领域较为常见的方法之一,具有应用范围广、处理速度快等显著优点。随着集成电路制造工艺的发展,芯片结构日益复杂,对其在线逆向分析时采集到的工作数据集规模也急剧膨胀,致使逻辑逆向综合成为在线式逆向分析的瓶颈,即现有的逻辑逆向综合算法处理大规模复杂工作数据集的效率较低。本文在深入分析在线式解析的数据特点和传统逻辑逆向综合算法的基础上,结合启发式思想,重点研究适于处理大规模、复杂的工作数据集的启发式逻辑逆向综合算法,并开发相应的在线式逻辑逆向综合子系统,以此获得可高效求解函数优化覆盖的能力,提高对逻辑芯片在线式逆向分析的整体效率。主要研究内容和创新点如下:(1)针对BOOM算法缺少有效的迭代停止条件,提出了在算法的最优字面选择步骤加入辅助规则的方法,即当真值覆盖矩阵的字面频率统计过程出现多个输入位对应的值相等的情况时,结合对假值覆盖矩阵的字面频率统计结果来辅助选择最优字面,保证替换字面后的降维立方体与较少的OFF点存在相交关系,加快OFF集为空的速度,从而避免因随机选择而导致耗费大量时间却无法减小假值覆盖矩阵的规模的情形发生,以减少算法的迭代次数。(2)针对EspressoII算法处理大规模零维体数据集时空开销大的问题,结合改进BOOM算法和EspressoII算法,设计了能够高效处理大规模工作数据集的Es-ImpBOOM算法。该算法首先利用改进BOOM算法对初始数据集进行初步优化,较大程度减小待处理数据集的规模,然后才采用EspressoII算法求解优化覆盖,从而提高在线式逻辑逆向综合的效率。(3)针对解耦合模式无法高效处理大输出变量数据集的问题,介绍并详细分析了适于求解大输出变量数据集的优化覆盖的FC-Min算法。该算法直接以多输出形式的初始覆盖为原始解,通过搜索输出蕴涵矩阵和构造蕴涵项两个步骤求得优化覆盖,免去阵列分离和求解共享乘积项过程,从而能够在合理的时间和空间范围内求得优化覆盖。并在此基础上,针对FC-Min算法求得的优化覆盖因存在冗余项而导致输出成本较高的问题,对算法进行了改进。改进后的FC-Min算法通过加入去冗余项步骤,能够以较少的时间开销代价较大程度地降低优化覆盖的成本。(4)根据在线式芯片逆向分析系统的实际需要,基于以上优化覆盖求解算法设计并实现了在线式逻辑逆向综合子系统。测试结果表明,在线式逻辑逆向综合子系统能够快速、准确地完成对在线数据集的优化处理,符合在线式芯片解析系统的要求。更多还原

【Abstract】 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.更多还原