UNTANGLE: Unlocking Routing and Logic Obfuscation Using Graph Neural Networks-based Link Prediction

Lilas Alrahis, Satwik Patnaik, Muhammad Abdullah Hanif, Muhammad Shafique, Ozgur Sinanoglu

Introduction

The globalization of the semiconductor industry has introduced significant security risks, including intellectual property (IP) piracy and the unauthorized overproduction of integrated circuits (ICs). To mitigate these threats, designers employ logic locking—a technique where additional "key-gates" are integrated into the netlist. The resulting circuit only functions correctly when the correct secret key is applied. However, this has sparked a continuous "cat-and-mouse" game between circuit designers and attackers.

The Challenge: SAT-Hard Obfuscation

Early logic locking methods were quickly compromised by Boolean Satisfiability (SAT)-based attacks. In response, more sophisticated "SAT-hard" defenses were developed. One prominent example is InterLock, which combines logic and routing obfuscation. InterLock utilizes complex, symmetric routing blocks (KeyRBs) and multiplexer (MUX) trees to create massive search spaces and intentional combinational loops. These features are specifically designed to crash or cause timeouts in traditional SAT-based attack tools.

SAT-based attacks like CycSAT and CP&SAT frequently time out when attempting to break InterLock-protected circuits.

UNTANGLE: An Oracle-Less Approach

Most existing attacks on logic locking require an "oracle"—a functional, activated chip that an attacker can query to observe correct input-output behavior. The researchers behind UNTANGLE present a paradigm shift: an "oracle-less" attack. UNTANGLE demonstrates that an attacker only needs the locked netlist and a Graph Neural Network (GNN) to reconstruct the hidden connections by learning structural patterns from the surrounding circuit.

The core of UNTANGLE is formulating hardware de-obfuscation as a link prediction task on a graph. Integrated circuits are not random; they are built from repeated functional blocks and standard design idioms. UNTANGLE leverages this structural redundancy to "guess" missing wires.

The fundamental dilemma in routing obfuscation and how UNTANGLE's link prediction provides a solution.

Methodology

  1. Graph Representation: The netlist is transformed into an undirected graph where gates are nodes (labeled with Boolean function features) and wires are edges.
  2. GNN Architecture: The system employs a Deep Graph Convolutional Neural Network (DGCNN). For every potential hidden link, the GNN analyzes an "$h$-hop enclosing subgraph"—the local neighborhood surrounding the target gates.
  3. Node Labeling: Double Radius Node Labeling (DRNL) is used to help the GNN understand the relative distance and structural roles of nodes within the subgraph.
  4. Iterative Refinement: Rather than predicting the entire key at once, UNTANGLE uses a greedy, iterative process. It identifies the most confident link predictions, "plugs" them into the netlist, and then re-evaluates the remaining links. This step-by-step "untangling" significantly improves final accuracy.

Experimental Results

The authors evaluated UNTANGLE against standard industry benchmarks (ISCAS-85 and ITC-99) locked with InterLock and random MUX-based schemes.

  • Precision and Recovery: UNTANGLE achieved 100% precision in identifying true links for InterLock benchmarks and recovered over 99% of keys for random MUX-based locking.
  • Speed: While state-of-the-art SAT solvers (CycSAT, CP&SAT) timed out after 24 hours, UNTANGLE successfully recovered keys in less than one second (typically 0.32s to 0.53s).
  • Functional Accuracy: The reconstructed circuits exhibited nearly zero functional error, with Hamming Distances averaging between 0.0015% and 0.013%.

Conclusion and Future Directions

UNTANGLE proves that the structural leakage of a netlist is a critical vulnerability. Even defenses designed to thwart SAT solvers can be bypassed by learning the "language" of circuit design through GNNs. Because GNNs treat the circuit as a static graph, they are unaffected by the combinational loops that cripple traditional tools.

Future work will focus on developing "global" obfuscation techniques. Currently, UNTANGLE succeeds because InterLock's changes are localized. If a defense could disrupt the global graph properties of a netlist, it might effectively hide the structural context that GNNs rely on for link prediction.

Summary updated

Abstract

Logic locking aims to prevent intellectual property (IP) piracy and unauthorized overproduction of integrated circuits (ICs). However, initial logic locking techniques were vulnerable to the Boolean satisfiability (SAT)-based attacks. In response, researchers proposed various SAT-resistant locking techniques such as point function-based locking and symmetric interconnection (SAT-hard) obfuscation. We focus on the latter since point function-based locking suffers from various structural vulnerabilities. The SAT-hard logic locking technique, InterLock [1], achieves a unified logic and routing obfuscation that thwarts state-of-the-art attacks on logic locking. In this work, we propose a novel link prediction-based attack, UNTANGLE, that successfully breaks InterLock in an oracle-less setting without having access to an activated IC (oracle). Since InterLock hides selected timing paths in key-controlled routing blocks, UNTANGLE reveals the gates and interconnections hidden in the routing blocks upon formulating this task as a link prediction problem. The intuition behind our approach is that ICs contain a large amount of repetition and reuse cores. Hence, UNTANGLE can infer the hidden timing paths by learning the composition of gates in the observed locked netlist or a circuit library leveraging graph neural networks. We show that circuits withstanding SAT-based and other attacks can be unlocked in seconds with 100% precision using UNTANGLE in an oracle-less setting. UNTANGLE is a generic attack platform (which we also open source [2]) that applies to multiplexer (MUX)-based obfuscation, as demonstrated through our experiments on ISCAS-85 and ITC-99 benchmarks locked using InterLock and random MUX-based locking.
BibTeX
@inproceedings{alrahis2021untangle,
  author = {Lilas Alrahis and Satwik Patnaik and Muhammad Abdullah Hanif and Muhammad Shafique and Ozgur Sinanoglu},
  title = {{UNTANGLE: Unlocking Routing and Logic Obfuscation Using Graph Neural Networks-based Link Prediction}},
  booktitle = {ICCAD},
  year = {2021},
  doi = {10.1109/iccad51958.2021.9643476},
}
Figure