A TRAP for SAT: On the Imperviousness of a Transistor-Level Programmable Fabric to Satisfiability-Based Attacks

Aj Fowler, Mohammed Shayan, Mustafa Shihab, Thomas Broadfoot, Peter A. Beerel, Carl Sechen, Yiorgos MakrisIACR 2025 · DOI

This paper explores the "arms race" between hardware designers trying to protect their intellectual property (IP) and adversaries trying to steal it. Specifically, it investigates whether a sophisticated defense called TRAP (Transistor-Level Programmable fabric) can withstand the industry-standard SAT attack.

TL;DR

Researchers developed a novel framework to translate complex transistor-level physics into the Boolean logic used by SAT solvers, enabling the first-ever "switch-level" SAT attack. While they proved that attacking these fabrics is theoretically possible, the sheer complexity of transistor-level modeling makes TRAP practically impervious to SAT attacks for any non-trivial design.

What Problem Does This Paper Address?

Most modern microchips are designed by "fabless" companies but manufactured in external, often overseas, foundries. This creates a massive security risk: an untrusted foundry could reverse-engineer the design, steal the IP, or produce unauthorized clones.

To counter this, designers use logic redaction. They replace sensitive parts of the circuit with a "programmable fabric" that only works when a secret key is loaded after manufacturing. However, a powerful algorithmic tool called the SAT attack has historically been able to "crack" these keys by iteratively ruling out incorrect values.

TRAP was proposed as a more robust defense because it operates at the transistor level (the "switch level") rather than the gate level. Until now, it was widely believed that SAT attacks were impossible against TRAP because SAT solvers only understand 1s and 0s, whereas transistors involve bidirectional signals, floating nodes (high impedance), and electrical loops—concepts that don't exist in standard Boolean logic.

Methods

The authors bridge the gap between physics and logic by creating a propositional logic model that "teaches" a SAT solver how transistors behave. Their key innovations include:

  • Dual-Variable Modeling: For every wire, they use two Boolean variables: one for the logic value (0 or 1) and one for the "drive" (is the wire actually connected to power, or is it "floating"?).
  • Directional Logic: They introduced variables to track the direction of signal flow, accounting for the fact that transistors can conduct in both directions.
  • Path Counting: To prevent the SAT solver from falling into "circular reasoning" (where a signal appears to drive itself in a loop), they implemented a path-counting requirement. A signal is only valid if it can be traced back to a physical power or ground rail.
  • TRANSAT Tool-set: They integrated these models into a custom tool-set using Python, the Z3 SMT solver, and Icarus Verilog, which they have released to the research community.

Datasets

The authors evaluated their attack against several benchmarks implemented on TRAP fabrics:

  • Standard Logic Gates: NAND2, NOR3, and AOI22 (And-Or-Invert).
  • Benchmark Circuits: The C17 combinational circuit from the ISCAS'85 suite.
  • Fabric Scales: They tested these on a single TRAP unit and a $2 \times 2$ tiled fabric (containing hundreds of potential key bits).

Key Insights and Ideas

  • The "Sea of Transistors" Advantage: Unlike FPGAs, which have a rigid hierarchy (Look-Up Tables, slices, etc.), TRAP is a "continuous sea" of transistors. This lack of hierarchy is a nightmare for attackers because they cannot break the problem down into smaller, manageable pieces; they must model the entire fabric as one giant, complex function.
  • Linear Scaling, Exponential Difficulty: While the size of the logic model grows linearly with the number of transistors (which is good for the tool's efficiency), the time required for the SAT solver to find a solution grows exponentially.
  • Redundancy is a Feature: In TRAP, many different key combinations might result in the same physical circuit. Paradoxically, this makes the SAT attack harder because it struggles to find "distinguishing" inputs that rule out incorrect keys.

Key Results

The results confirm that TRAP is a formidable defense:

  • Small Scale: The tool successfully broke a single TRAP unit implementing a NAND gate in just 24 seconds.
  • Medium Scale: Breaking a NOR3 gate on a single unit took about 4 minutes.
  • Large Scale (The "Wall"): When trying to break an AOI22 gate or the C17 circuit on a $2 \times 2$ fabric, the attack failed to finish. One attempt was terminated after 189 days (over 6 months) of continuous computation without finding the key.
  • Complexity: A $2 \times 2$ fabric involves over 700 key bits and a logic model with nearly 12,000 clauses, creating a search space that is practically insurmountable for current SAT-solving technology.

Limitations and Future Work

The primary limitation acknowledged by the authors is that their current framework only handles combinational logic (circuits where the output depends only on the current input). Real-world chips are sequential, meaning they have memory (flip-flops and latches).

The authors suggest that future work should focus on extending this transistor-level modeling to sequential SAT attacks. However, given how much the complexity exploded for simple combinational circuits, TRAP appears to be one of the most "impervious" hardware security measures currently available.

Summary updated

Abstract

Locking-based intellectual property (IP) protection for integrated circuits (ICs) being manufactured at untrusted facilities has been largely defeated by the satisfiability (SAT) attack, which can retrieve the secret key needed for instantiating proprietary functionality on locked circuits. As a result, redaction-based methods have gained popularity as a more secure way of protecting hardware IP. Among these methods, transistor-level programming (TRAP) prohibits the outright use of SAT attacks due to the mismatch between the logic-level at which SAT attack operates and the switch-level at which the TRAP fabric is programmed. Herein, we discuss the challenges involved in launching SAT attacks on TRAP and we propose solutions which enable expression of TRAP in propositional logic modeling in a way that accurately reflects switch-level circuit capabilities. Results obtained using a transistor-level SAT attack tool-set that we developed and are releasing corroborate that SAT attacks can be launched against TRAP. However, the increased complexity of switch-level circuit modeling prevents the attack from realistically compromising all but the most trivial IP-protected designs.
BibTeX
@inproceedings{fowler2025trap,
  author = {AJ Fowler and Mohammed Shayan and Mustafa Shihab and Thomas Broadfoot and Peter A. Beerel and Carl Sechen and Yiorgos Makris},
  title = {{A TRAP for SAT: On the Imperviousness of a Transistor-Level Programmable Fabric to Satisfiability-Based Attacks}},
  booktitle = {IACR},
  year = {2025},
  doi = {10.46586/tches.v2025.i2.579-603},
}
Figure