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.
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.
Methodology
- Graph Representation: The netlist is transformed into an undirected graph where gates are nodes (labeled with Boolean function features) and wires are edges.
- 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.
- 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.
- 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