skip to main content

Title: NNgSAT: Neural Network guided SAT Attack on Logic Locked Complex Structures
The globalization of the IC supply chain has raised many security threats, especially when untrusted parties are involved. This has created a demand for a dependable logic obfuscation solution to combat these threats. Amongst a wide range of threats and countermeasures on logic obfuscation in the 2010s decade, the Boolean satisfiability (SAT) attack, or one of its derivatives, could break almost all state-of-the-art logic obfuscation countermeasures. However, in some cases, particularly when the logic locked circuits contain complex structures, such as big multipliers, large routing networks, or big tree structures, the logic locked circuit is hard-to-be-solved for the SAT attack. Usage of these structures for obfuscation may lead a strong defense, as many SAT solvers fail to handle such complexity. However, in this paper, we propose a neural-network-guided SAT attack (NNgSAT), in which we examine the capability and effectiveness of a message-passing neural network (MPNN) for solving these complex structures (SAT-hard instances). In NNgSAT, after being trained as a classifier to predict SAT/UNSAT on a SAT problem (NN serves as a SAT solver), the neural network is used to guide/help the actual SAT solver for finding the SAT assignment(s). By training NN on conjunctive normal forms (CNFs) corresponded to a more » dataset of logic locked circuits, as well as fine-tuning the confidence rate of the NN prediction, our experiments show that NNgSAT could solve 93.5% of the logic locked circuits containing complex structures within a reasonable time, while the existing SAT attack cannot proceed the attack flow in them. « less
Award ID(s):
Publication Date:
Journal Name:
2020 IEEE/ACM International Conference On Computer Aided Design (ICCAD)
Sponsoring Org:
National Science Foundation
More Like this
  1. In this paper, we introduce the Satisfiability Modulo Theory (SMT) attack on obfuscated circuits. The proposed attack is the superset of Satisfiability (SAT) attack, with many additional features. It uses one or more theory solvers in addition to its internal SAT solver. For this reason, it is capable of modeling far more complex behaviors and could formulate much stronger attacks. In this paper, we illustrate that the use of theory solvers enables the SMT to carry attacks that are not possible by SAT formulated attacks. As an example of its capabilities, we use the SMT attack to break a recentmore »obfuscation scheme that uses key values to alter delay properties (setup and hold time) of a circuit to remain SAT hard. Considering that the logic delay is not a Boolean logical property, the targeted obfuscation mechanism is not breakable by a SAT attack. However, in this paper, we illustrate that the proposed SMT attack, by deploying a simple graph theory solver, can model and break this obfuscation scheme in few minutes. We describe how the SMT attack could be used in one of four different attack modes: (1) We explain how SMT attack could be reduced to a SAT attack, (2) how the SMT attack could be carried out in Eager, and (3) Lazy approach, and finally (4) we introduce the Accelerated SMT (AccSMT) attack that offers significant speed-up to SAT attack. Additionally, we explain how AccSMT attack could be used as an approximate attack when facing SMT-Hard obfuscation schemes.« less
  2. Logic locking has been widely evaluated as a proactive countermeasure against the hardware security threats within the IC supply chain. However, the introduction of the SAT attack, and many of its derivatives, has raised big concern about this form of countermeasure. In this paper, we explore the possibility of exploiting chaos computing as a new means of logic locking. We introduce the concept of chaotic logic locking, called ChaoLock, in which, by leveraging asymmetric inputs in digital chaotic Boolean gates, we define the concept of programmability (key-configurability) to the sets of underlying initial conditions and system parameters. These initial conditionsmore »and system parameters determine the operation (functionality) of each digital chaotic Boolean gate. Also, by proposing dummy inputs in chaotic Boolean gates, we show that during reverse-engineering, the dummy inputs conceal the main functionality of the chaotic Boolean gates, which make the reverse-engineering almost impossible. By performing a security analysis of ChaoLock, we show that with no restriction on conventional CMOS-based ASIC implementation and with no test/debug compromising, none of the state-of-the-art attacks on logic locking, including the SAT attack, could reformulate chaotic Boolean gates while dummy inputs are involved and their parameters are locked. Our analysis and experimental results show that with a low number of chaotic Boolean gates mixed with CMOS digital gates, ChaoLock can guarantee resiliency against the state-of-the-art attacks on logic locking at low overhead.« less
  3. Protecting intellectual property (IP) has become a serious challenge for chip designers. Most countermeasures are tailored for CMOS integration and tend to incur excessive overheads, resulting from additional circuitry or device-level modifications. On the other hand, power density is a critical concern for sub-50 nm nodes, necessitating alternate design concepts. Although initially tailored for error-tolerant applications, imprecise computing has gained traction as a general-purpose design technique. Emerging devices are currently being explored to implement ultra-low-power circuits for inexact computing applications. In this paper, we quantify the security threats of imprecise computing using emerging devices. More specifically, we leverage the innatemore »polymorphism and tunable stochastic behavior of spin-orbit torque (SOT) devices, particularly, the giant spin-Hall effect (GSHE) switch. We enable IP protection (by means of logic locking and camouflaging) simultaneously for deterministic and probabilistic computing, directly at the GSHE device level. We conduct a comprehensive security analysis using state-of-the-art Boolean satisfiability (SAT) attacks; this study demonstrates the superior resilience of our GSHE primitive when tailored for deterministic computing. We also demonstrate how probabilistic computing can thwart most, if not all, existing SAT attacks. Based on this finding, we propose an attack scheme called probabilistic SAT (PSAT) which can bypass the defense offered by logic locking and camouflaging for imprecise computing schemes. Further, we illustrate how careful application of our GSHE primitive can remain secure even on the application of the PSAT attack. Finally, we also discuss side-channel attacks and invasive monitoring, which are arguably even more concerning threats than SAT attacks.« less
  4. Abstract—In this paper, we introduce DFSSD, a novel logic locking solution for sequential and FSM circuits with a restricted (locked) access to the scan chain. DFSSD combines two techniques for obfuscation: (1) Deep Faults, and (2) Shallow State Duality. Both techniques are specifically designed to resist against sequential SAT attacks based on bounded model checking. The shallow state duality prevents a sequential SAT attack from taking a shortcut for early termination without running an exhaustive unbounded model checker to assess if the attack could be terminated. The deep fault, on the other hand, provides a designer with a technique formore »building deep, yet key recoverable faults that could not be discovered by sequential SAT (and bounded model checker based) attacks in a reasonable time.« less
  5. Logic locking has emerged as a promising solution to protect integrated circuits against piracy and tampering. However, the security provided by existing logic locking techniques is often thwarted by Boolean satisfiability (SAT)-based oracle-guided attacks. Criteria for successful SAT attacks on locked circuits include: (i) the circuit under attack is fully combinational, or (ii) the attacker has scan chain access. To address the threat posed by SAT-based attacks, we adopt the dynamically obfuscated scan chain (DOSC) architecture and illustrate its resiliency against the SAT attacks when inserted into the scan chain of an obfuscated design. We demonstrate, both mathematically and experimentally,more »that DOSC exponentially increases the resiliency against key extraction by SAT attack and its variants. Our results show that the mathematical estimation of attack complexity correlates to the experimental results with an accuracy of 95% or better. Along with the formal proof, we model DOSC architecture to its equivalent combinational circuit and perform SAT attack to evaluate its resiliency empirically. Our experiments demonstrate that SAT attack on DOSC-inserted benchmark circuits timeout at minimal test time overhead, and while DOSC requires less than 1% area and power overhead.« less