Novel Bypass Attack and BDD-based Tradeoff Analysis Against all Known Logic Locking Attacks

Xiaolin Xu, Bicky Shakya, Mark Tehranipoor, Domenic Forte

TL;DR

This paper introduces a novel "bypass attack" that can circumvent even the latest SAT-resistant logic locking techniques, allowing an adversary to restore a circuit's original functionality with an incorrect key. The authors also propose a BDD-based framework for analyzing the trade-offs between different logic locking security measures and attack vectors.

What Problem Does This Paper Address?

The semiconductor industry faces significant risks from untrusted foundries, including intellectual property (IP) theft and counterfeiting. Logic locking is a promising technique to protect IC designs by embedding extra key-controlled logic, making the circuit function correctly only with the correct key. However, early logic locking methods were vulnerable to Boolean Satisfiability (SAT) attacks. While newer "SAT-resistant" techniques have emerged to counter these attacks, this paper argues that these advanced methods also possess unique vulnerabilities. Specifically, the authors address the problem of finding a way to bypass these SAT-resistant defenses, effectively rendering them useless without requiring the attacker to find the actual secret key.

Methods

The core contribution is the "bypass attack." This attack doesn't aim to find the correct key but rather to neutralize the effect of an incorrect key. The method involves:

  1. Identifying Distinguishing Input Patterns (DIPs): Similar to SAT attacks, the attacker uses a locked netlist and an "unlocked IC" (an oracle) to find input patterns that reveal an incorrect output when a specific wrong key is applied.
  2. Constructing a Bypass Circuit: Once DIPs for a wrong key are identified, a small bypass circuitry is designed. This circuitry monitors for these specific DIPs and, when detected, inverts the circuit's output to restore the correct functionality, effectively masking the effect of the wrong key.
  3. Miter Construction: To find DIPs efficiently, a "miter circuit" is constructed. This involves creating multiple copies of the locked netlist, each with different (wrong) keys, and using a SAT solver to find input patterns where their outputs differ.
  4. BDD-based Tradeoff Analysis: The authors propose using Binary Decision Diagrams (BDDs) to analyze logic locking at a functional level. BDDs offer a compact representation of Boolean functions and allow for a more holistic assessment of various attacks (SAT, bypass, removal) and their trade-offs with security and overhead.

Datasets

The paper evaluates its proposed bypass attack on a subset of benchmarks from the ISCAS, MCNC, and EPFL benchmark sets. These are standard benchmarks used in hardware design and verification. No new benchmarks were introduced.

Key Insights and Ideas

  • SAT Resistance Creates New Vulnerabilities: The very techniques designed to make logic locking resistant to SAT attacks (by minimizing the number of keys ruled out by each input pattern) inadvertently make them more susceptible to bypass attacks.
  • Bypass Attack: A Different Goal: The bypass attack doesn't aim to find the correct key but to neutralize the effect of an incorrect key, allowing the circuit to function as if the correct key were present.
  • Trade-off Between Attacks: There's an inherent trade-off: increasing resistance to SAT attacks often increases the feasibility and overhead of a bypass attack, and vice-versa. This suggests that a truly secure logic locking scheme needs to balance these competing threats.
  • BDDs as a Unified Analysis Platform: BDDs provide a powerful functional-level abstraction to analyze and visualize the complex interplay between different attack vectors and logic locking security mechanisms, enabling a more comprehensive design space exploration.
  • Resynthesis Can Mitigate Overhead: Surprisingly, applying resynthesis after embedding the bypass circuitry can sometimes lead to reduced area/delay overhead compared to the locked design, as the hardcoded bypass logic can be optimized away.

Key Results

  • The bypass attack successfully thwarts state-of-the-art SAT-resistant logic locking techniques like SARLock, SARLock+SLL, and Anti-SAT (in its secure integration mode).
  • The bypass circuitry incurs minimal area/delay overhead, often showing improvements after resynthesis compared to the locked designs. For some benchmarks, overheads are negligible (around 1%).
  • The execution time for generating the necessary DIPs for the bypass attack is very fast, typically under 2 seconds for the tested benchmarks.
  • The BDD-based analysis confirms the trade-off: higher SAT resistance generally leads to higher bypass attack feasibility and overhead.

Limitations and Future Work

  • Scalability of Bypass on Anti-SAT (RI): The bypass attack's scalability on Anti-SAT with random integration (RI) is uncertain and depends heavily on the selection of internal nodes.
  • BDD Area Overhead: BDD-based logic locking, while offering good SAT resistance, suffers from extremely high area overheads due to the exponential growth of BDD size with key length.
  • Future Work:
    • Making BDD-based logic locking more practical by addressing area overhead through better synthesis techniques and variable ordering.
  • Developing more robust logic locking schemes that simultaneously balance resistance against all known attacks (SAT, bypass, removal).
  • Exploring parametric tests (e.g., side-channel measurements) as a potential countermeasure, though practical concerns like cost and accuracy limit their applicability.

Summary updated

BibTeX
@article{xu2017novel,
  author = {Xiaolin Xu and Bicky Shakya and Mark Tehranipoor and Domenic Forte},
  title = {{Novel Bypass Attack and BDD-based Tradeoff Analysis Against all Known Logic Locking Attacks}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2017},
}
Figure