摘要： 采用逻辑分析法实现加密可编程逻辑器件(PLD)逆向分析的关键是为逻辑综合提供有效、完备的数据集，特别是对时序型PLD，在未知状态图的情况下，如何高效地采集到所有有效状态下的数据，是逆向分析研究的核心问题之一。该文在理论分析同步时序型PLD逆向分析可行性的基础上，提出一种适合多状态、复杂同步时序型PLD的高效数据采集算法，以动态建立非完全状态图为基础，求解状态驱动的最短路径，使得数据采集算法具有理想的时空开销。

关键词: 可编程逻辑器件, 同步时序, 非完全状态图, 最短路径, 数据采集

Abstract: The key problem in the reverse analysis of encrypted Programmable Logic Devices(PLD) using logic analysis techniques is to collect effective and self-contained data set, especially for timing PLD. An efficient data collecting algorithm is presented whichs suit for large scale and multi-state synchronous PLDs. The algorithm builds non-complete state graph and finds the shortest path for state migration form initial state to each effect state. The algorithm has ideal time and space cost and has been used in the PLD reverse engineering system.

Key words: Programmable Logic Devices(PLD), synchronous logic, non-complete state graph, shortest path, data collecting

中图分类号: 

• TP309.7