Analysis of Graph-based Partitioning Algorithms and Partitioning Metrics for Hardware Reverse Engineering

International audienceWith modern Integrated Circuit (IC) fabrication taking place offshore and with thirdparty companies, hardware reverse engineering has become an effective method to ensure the security of chips. Recently, it has gained more and more attention to counteract the threats of Intellectual Property (IP) theft, overproduction, and Hardware Trojan (HT) insertion. However, to reverse engineer real-world ICs, methods must scale to millions of logic gates. This is also true for the final step in hardware reverse engineering: netlist abstraction. Here, a divide and conquer approach has become necessary, where the gate-level netlist is divided into smaller partitions, which are then identified separately. This work introduces several graph-based methods for netlist partitioning, which are faster, more accurate, more flexible, and require less information about the design than current solutions. The algorithmic efficiency of these methods is compared using theoretic analysis and experimental assessment. These experiments also evaluate the correctness of the partitioning methods for small and large netlists, using several evaluation metrics. Furthermore, this work analyses these metrics' behavior for different types of netlists and discusses why a single metric is insufficient to evaluate partitioning methods correctly