Cryptology ePrint Archive: Report 2019/983

Graph Similarity and Its Applications to Hardware Security

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

Abstract: 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.

Category / Keywords: Graph Similarity, Hardware Reverse Engineering, Hardware Trojan, Hardware Obfuscation Assessment

Date: received 28 Aug 2019

Contact author: sebastian wallat at rub de

Available format(s): PDF | BibTeX Citation

Version: 20190829:111804 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]