Characterize the ability of GNNs in attacking logic locking

Recent research has showcased the capability of Graph Neural Networks (GNNs) to uncover the correct keys from locked circuits without an oracle. However, a comprehensive comprehension and discourse regarding their achievements remain limited. For instance, which specific GNN architectures possess a greater potency in effectively uncovering these keys? In this paper, we model their ability to identify circuit changes that stem from a logic lock as the ability to decide the isomorphism between logic netlists. We examine different netlist graph representations and characteristics of GNNs that improve the ability in graph isomorphism. We show that GNNs are always upper bounded by heterogeneous Weisfeiler Lehman test for netlist isomorphism determination, and give the conditions when GNNs reach the bound. Motivated by these conditions, a specific GNN architecture, NetlistGNN, is proposed. Experimental results align with our theorems, and demonstrate that GNN-based state-of-the-art attacking models can benefit from our findings by simply replacing the original GNN model to NetlistGNN.