Oracle Guided SAT Attacks on Logic Locking

194 concepts66 papers2 proposals

The globalization of the semiconductor supply chain has forced a paradigm shift in hardware security. Because most design houses operate under a "fabless" model, they must trust third-party foundries with their highly valuable intellectual property (IP). To prevent these untrusted foundries or end-users from pirating, cloning, or reverse-engineering integrated circuits (ICs), hardware designers use a technique called logic locking.

By inserting key-controlled gates into a circuit's netlist, designers ensure that the chip will only function correctly if the correct secret key is loaded into its non-volatile memory. As reviewed by Johann Knechtel et al. in Protect Your Chip Design Intellectual Property: An Overview, early logic locking schemes assumed that finding a $k$-bit key would require an intractable brute-force search of $2^k$ combinations. However, this security model was fundamentally disrupted by the introduction of the oracle-guided Boolean Satisfiability (SAT) attack.

The Intuition Behind the SAT Attack

The devastating efficiency of the SAT attack stems from a highly realistic threat model. The adversary is assumed to have access to two distinct artifacts:

  1. The Locked Netlist: The gate-level schematic $f(X, K)$, where $X$ represents the primary inputs and $K$ represents the unknown key bits. This can be obtained by a malicious foundry or via physical reverse-engineering of a layout.
  2. An Activated Oracle: A fully functional, activated chip $f_{\text{true}}(X)$ purchased on the open market. The attacker can apply any input to this chip and observe the correct output, but they cannot read the key stored inside it.

Instead of guessing keys blindly, the attack uses a SAT solver to systematically prune the key space by finding a sequence of Distinguishing Input Patterns (DIPs).

A DIP is a specific input vector $X_d$ that can expose a disagreement between two different key hypotheses, $K_1$ and $K_2$. To find a DIP, the SAT solver evaluates the following formula:

$$f(X_d, K_1) \neq f(X_d, K_2)$$

If the solver finds such an input $X_d$, it means that $K_1$ and $K_2$ cannot both be correct, because they predict different behaviors for the exact same input.

                  +-------------------+
                  |    SAT Solver     |
                  | Finds $X_d$ where |
                  | f(X_d,K1) !=      |
                  | f(X_d,K2)         |
                  +---------+---------+
                            |
                            | Distinguishing Input ($X_d$)
                            v
                  +-------------------+
                  |  Physical Oracle  | ----> Observes True
                  |   (Active Chip)   |       Output ($Y_d$)
                  +---------+---------+
                            |
                            | Constraint: f(X_d, K) == Y_d
                            v
                  +-------------------+
                  |  Prune Key Space  |
                  | Eliminates wrong  |
                  |   equivalence     |
                  |     classes       |
                  +-------------------+

As detailed in the tutorial by Hammond Pearce et al. in High-Level Approaches to Hardware Security: A Tutorial, the attacker takes this $X_d$ and applies it to the physical oracle chip, observing the true, golden output $Y_d = f_{\text{true}}(X_d)$.

This single observation provides massive leverage. The attacker appends a new logical constraint to the SAT solver:

$$f(X_d, K) = Y_d$$

This constraint instantly eliminates entire equivalence classes of incorrect keys—specifically, every single key that would have produced the wrong output for $X_d$. The solver then looks for a new DIP under these tighter constraints. The process repeats iteratively. Because each iteration prunes a massive portion of the remaining key space, the algorithm typically converges on the correct key in just a few dozen iterations, completely bypassing the exponential complexity of a brute-force search.

The Role of Scan Chains

For an attacker to easily apply these DIPs and read out the resulting internal outputs, the target circuit must be combinational. However, real-world chips are sequential, containing deep chains of registers and state machines.

To bridge this gap, attackers exploit standard hardware testing structures called scan chains. As noted by Seetal Potluri in SeqL: Secure Scan-Locking for IP Protection, scan chains are designed to give test engineers full observability and controllability over a chip's internal registers. Unfortunately, they also give attackers an unintended window to isolate sequential logic blocks and treat them as easily solvable combinational circuits. This vulnerability has driven researchers like Seetal Potluri et al. in SeqL+: Secure Scan-Obfuscation with Theoretical and Empirical Validation to develop advanced scan-chain obfuscation techniques, forcing attackers to solve complex graph-routing problems (such as finding a Hamiltonian path) to even begin a SAT attack.

Breaking the SAT Solver's Assumptions

To defend against oracle-guided SAT attacks, modern hardware security researchers focus on breaking the fundamental mathematical assumptions that make SAT solvers efficient.

Introducing Cyclic Dependencies

Standard SAT solvers operate under the assumption that a circuit netlist can be modeled as a Directed Acyclic Graph (DAG). If a circuit contains loops, the solver cannot easily evaluate its logic.

By utilizing embedded FPGAs (eFPGAs) or transistor-level programmable fabrics (TRAP) for logic redaction, designers can introduce programmable routing networks that contain combinational loops. As demonstrated by Jitendra Bhandari et al. in Not All Fabrics Are Created Equal: Exploring eFPGA Parameters for IP Redaction and AJ Fowler et al. in A TRAP for SAT: On the Imperviousness of a Transistor-Level Programmable Fabric to Satisfiability-Based Attacks, a SAT solver attempting to analyze these fabrics is forced to "unroll" these loops into an acyclic representation. This unrolling causes an exponential explosion in the number of clauses and variables the solver must process, turning a seconds-long execution into an intractable computational task.

Eliminating Oracle Determinism

The SAT attack fundamentally relies on a stable, deterministic oracle that returns the exact same output every time it encounters a given input.

The authors of Opening the Doors to Dynamic Camouflaging: Harnessing the Power of Polymorphic Devices, Nikhil Rangarajan et al., propose breaking this assumption via run-time functional reconfiguration. Similarly, Satwik Patnaik et al. in Spin-Orbit Torque Devices for Hardware Security: From Deterministic to Probabilistic Regime leverage the tunable stochasticity of emerging spin-orbit torque devices to introduce controlled probabilistic noise. When the oracle behaves as a moving target, it feeds inconsistent input-output mappings back to the SAT solver, causing the mathematical constraints to contradict each other and preventing the solver from converging on a valid key.

The Security-Corruptibility Trade-off

When designing SAT-resilient logic locking, engineers face a strict mathematical dilemma known as the security-corruptibility trade-off.

  • High Corruptibility: If an incorrect key causes the circuit to fail across a wide range of input patterns, the error is highly visible. This makes the chip useless to an IP pirate, but it also means a SAT solver can easily find a DIP to eliminate that wrong key.
  • Low Corruptibility: If an incorrect key only corrupts a tiny fraction of inputs (e.g., a single input pattern), it becomes incredibly difficult for a SAT solver to stumble upon that specific DIP. The solver is forced into an exponential brute-force search. However, because the chip functions correctly for $99.9\%$ of inputs, an attacker might simply bypass the locking mechanism entirely, as the chip remains practically functional for most applications.

To break this trade-off, Yuntao Liu in Robust and Attack Resilient Logic Locking with a High Application-Level Impact demonstrates that locking logic can be engineered to focus corruption exclusively on high-impact "critical minterms" rather than distributing errors uniformly.

Furthermore, Bicky Shakya et al. in CAS-Lock: A Security-Corruptibility Trade-off Resilient Logic Locking Scheme introduce cascaded gate structures designed so that each incorrect key is invalidated by exactly one unique input pattern. This architecture achieves a mathematical lower bound of security equivalent to a brute-force search, while tightly integrating the locking logic into the functional logic cone to prevent physical removal attacks.

Real-World Imperfections and Alternative Attack Vectors

While oracle-guided SAT attacks are mathematically elegant in theory, their real-world deployment reveals distinct vulnerabilities.

As highlighted by Qinhan Tan et al. in Efficacy of Satisfiability Based Attacks in the Presence of Circuit Reverse Engineering Errors, physical reverse-engineering is an inherently messy process prone to gate-misidentification and structural errors. Because SAT solvers operate on rigid, exact logical constraints, any discrepancy between the extracted netlist and the physical oracle chip creates structural contradictions. These contradictions cause the solver to either fail outright or output a key that is completely non-functional on the actual hardware.

                  +---------------------------------------+
                  |       Is an Oracle Available?         |
                  +-------------------+-------------------+
                                      |
                   Yes                | No
                  v                   v
     +-------------------------+     +-------------------------+
     |    SAT-Based Attack     |     |   Oracle-less Attack    |
     |                         |     |                         |
     | Uses exact mathematical |     | Uses Graph Neural       |
     | constraints to prune    |     | Networks (GNNs) to find |
     | the key space via DIPs. |     | structural signatures   |
     |                         |     | and isolate key gates.  |
     | * Vulnerable to netlist |     |                         |
     |   errors and loops.     |     | * Vulnerable to deep    |
     +-------------------------+     |   algorithmic blending. |
                                     +-------------------------+

When SAT attacks are neutralized—either by netlist errors, combinational loops, or the lack of a physical oracle chip—adversaries pivot to oracle-less attacks.

Instead of analyzing functional behavior, these attacks exploit the structural artifacts left behind by logic-locking tools. For example, Lilas Alrahis et al. developed GNNUnlock: Graph Neural Networks-based Oracle-less Unlocking Scheme for Provably Secure Logic Locking, which treats the circuit netlist purely as a graph. By training Graph Neural Networks (GNNs) to recognize the structural "signatures" of protection logic, these models can isolate and remove key-gates without ever needing to execute a single input pattern on a physical chip. This ongoing cat-and-mouse game ensures that hardware security remains a multi-layered discipline, balancing functional complexity against structural indistinguishability.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 65 papers
  2. Version 1 · 2026-10-04 · 58 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_sat_based_reverse_engineering_c9bd33ee,
  title = {SAT-based reverse engineering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sat-based-reverse-engineering/rdr_c9bd33eecd72403cbd29e1dccb18eff2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_sat_based_reverse_engineering_c9bd33ee_v2,
  title = {SAT-based reverse engineering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/sat-based-reverse-engineering/rdr_c9bd33eecd72403cbd29e1dccb18eff2/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake