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

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

TL;DR

UNTANGLE is a novel "oracle-less" attack that breaks advanced hardware logic locking (specifically InterLock) by treating netlist de-obfuscation as a graph link prediction problem. By leveraging Graph Neural Networks (GNNs) to learn the structural "idioms" of integrated circuits, it can reconstruct hidden connections with 100% precision in seconds—even when state-of-the-art SAT-based attacks fail or time out.

What Problem Does This Paper Address?

In the globalized semiconductor supply chain, designers often outsource fabrication to offshore foundries, risking Intellectual Property (IP) theft or unauthorized overproduction. Logic locking is a primary defense, where "key-gates" are inserted into a netlist; the circuit only functions correctly if the right secret key is provided.

However, a "cat-and-mouse" game has emerged. Early locking was broken by Boolean Satisfiability (SAT) attacks. In response, designers created "SAT-hard" defenses like InterLock, which uses complex, symmetric routing blocks (KeyRBs) and multiplexer (MUX) trees to create massive search spaces and combinational loops that crash traditional attack tools.

The authors of UNTANGLE address a critical gap: most existing attacks require an "oracle" (a working, activated chip) to function. UNTANGLE proves that an attacker doesn't need a working chip; they only need the locked netlist and a GNN to "guess" the missing connections based on the surrounding circuit's patterns.

Methods

The core innovation of UNTANGLE is formulating hardware de-obfuscation as a link prediction task on a graph.

  1. Graph Representation: The circuit netlist is converted into an undirected graph where gates are nodes (labeled with one-hot features representing their Boolean function) and wires are edges.
  2. GNN Architecture: The authors use a Deep Graph Convolutional Neural Network (DGCNN). For every potential hidden link in an obfuscated block, the GNN extracts an "$h$-hop enclosing subgraph"—essentially a local neighborhood of the circuit.
  3. Node Labeling: They apply Double Radius Node Labeling (DRNL) to these subgraphs. This helps the GNN understand the relative distance and structural role of every node with respect to the two target gates it is trying to "link."
  4. Iterative Post-processing: Instead of predicting the whole key at once, UNTANGLE uses a greedy, iterative algorithm. It identifies the links predicted with the highest confidence, "plugs" them into the netlist, and then re-runs the prediction for the remaining links. This step-by-step "untangling" significantly boosts final precision.

Datasets

The authors evaluated UNTANGLE using standard industry benchmarks:

  • ISCAS-85 and ITC-99: These are classic circuit benchmarks (e.g., c7552, b14, b22) used to simulate real-world logic.
  • Locking Schemes: The benchmarks were locked using InterLock (with KeyRB sizes of 8 and 16) and random MUX-based locking with key sizes ranging from 64 to 512 bits.
  • Training Scenarios: They tested a "Self-referencing" mode (learning from the non-obfuscated parts of the same chip) and a "Circuit Library" mode (learning from a library of similar, known designs).

Key Insights and Ideas

  • ICs are Repetitive: Modern integrated circuits aren't random; they are composed of repeated functional blocks and standard design patterns. GNNs are exceptionally good at learning these implicit "design rules" without being explicitly told what they are.
  • The "Oracle-less" Threat: Most hardware security assumes the attacker needs a working chip to compare outputs. UNTANGLE shows that the structural leakage of the netlist itself is a massive vulnerability.
  • InterLock's Hidden Weakness: The authors discovered that InterLock’s "100% utilization" (ensuring every gate in a routing block is used) actually restricts the possible connection combinations. This constraint makes the link prediction task easier for the GNN.
  • Loops are No Obstacle: While combinational loops break SAT solvers and structural tools like SWEEP or SCOPE, the GNN-based approach is indifferent to them because it treats the circuit as a static graph.

Key Results

  • Perfect Precision: UNTANGLE achieved 100% precision in identifying true links for InterLock-protected benchmarks.
  • High Key Recovery: It successfully deciphered up to 100% of the keys for InterLock and over 99% for random MUX-based locking.
  • Efficiency: While SAT-based attacks (CycSAT, CP&SAT) timed out after 24 hours on these benchmarks, UNTANGLE recovered the keys in less than one second (0.32s to 0.53s).
  • Low Error: The Hamming Distance (a measure of functional error) of the reconstructed circuits was nearly zero (averaging 0.0015% to 0.013%), meaning the "unlocked" circuit was functionally identical to the original.

Limitations and Future Work

  • Local vs. Global Obfuscation: UNTANGLE succeeds because InterLock's changes are localized within specific routing blocks. If a defense were to obfuscate the global structure of the chip, the GNN might struggle to find a clean "context" for prediction.
  • Interconnected Blocks: The authors suggest that one way to improve InterLock would be to ensure that multiple KeyRBs are heavily interconnected, making the surrounding circuitry of one block just as "noisy" as the block itself.
  • Future Directions: The team plans to investigate large-scale MUX-based locking that intentionally disrupts the global graph properties of the netlist to thwart GNN-based structural analysis.

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},
}

Loading related content...

Figure