Paper 2019/983

Graph Similarity and Its Applications to Hardware Security

Marc Fyrbiak, Sebastian Wallat, Sascha Reinhard, Nicolai Bissantz, and Christof Paar


Hardware reverse engineering is a powerful and universal tool for both security engineers and adversaries. From a defensive perspective, it allows for detection of intellectual property infringements and hardware Trojans, while it simultaneously can be used for product piracy and malicious circuit manipulations. From a designer’s perspective, it is crucial to have an estimate of the costs associated with reverse engineering, yet little is known about this, especially when dealing with obfuscated hardware. The contribution at hand provides new insights into this problem, based on algorithms with sound mathematical underpinnings. Our contributions are threefold: First, we present the graph similarity problem for automating hardware reverse engineering. To this end, we improve several state-of-the-art graph similarity heuristics with optimizations tailored to the hardware context. Second, we propose a novel algorithm based on multiresolutional spectral analysis of adjacency matrices. Third, in three extensively evaluated case studies, namely (1) gate-level netlist reverse engineering, (2) hardware Trojan detection, and (3) assessment of hardware obfuscation, we demonstrate the practical nature of graph similarity algorithms.

Available format(s)
Publication info
Preprint. MINOR revision.
Graph SimilarityHardware Reverse EngineeringHardware TrojanHardware Obfuscation Assessment
Contact author(s)
sebastian wallat @ rub de
2019-08-29: received
Short URL
Creative Commons Attribution


      author = {Marc Fyrbiak and Sebastian Wallat and Sascha Reinhard and Nicolai Bissantz and Christof Paar},
      title = {Graph Similarity and Its Applications to Hardware Security},
      howpublished = {Cryptology ePrint Archive, Paper 2019/983},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.