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

Selina Weber (1) , Johanna Baehr (1) , Alexander Hepp (1) , Georg Sigl (1, 2)

1 TUM - Technische Universität Munchen - Technical University Munich - Université Technique de Munich
2 Fraunhofer AISEC - Fraunhofer Institute for Applied and Integrated Security [München]

With 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.

Domains: Computer Science [cs]; Cryptography and Security [cs.CR]; Hardware Architecture [cs.AR]; Embedded Systems; Modeling and Simulation

Selina Weber, Johanna Baehr, Alexander Hepp, Georg Sigl. Analysis of Graph-based Partitioning Algorithms and Partitioning Metrics for Hardware Reverse Engineering. 11th International Workshop on Security Proofs for Embedded Systems (PROOFS 2022), Sep 2022, Leuven, Belgium. ⟨hal-03780642⟩