In this paper, we propose a canonical prune-and-SAT (CP&SAT) attack for breaking state-of-the-art routing-based obfuscation techniques. In the CP&SAT attack, we first encode the key-programmable routing blocks (keyRBs) based on an efficient SAT encoding mechanism suited for detailed routing constraints, and then efficiently re-encode and reduce the CNF corresponded to the keyRB using a bounded variable addition (BVA) algorithm. In the CP&SAT attack, this is done before subjecting the circuit to the SAT attack. We illustrate that this encoding and BVA-based pre-processing significantly reduces the size of the CNF corresponded to the routing-based obfuscated circuit, in the result of which we observe 100% success rate for breaking prior art routing-based obfuscation techniques. Further, we propose a new intercorrelated logic and routing locking technique, or in short InterLock, as a countermeasure to mitigate the CP&SAT attack. In Interlock, in addition to hiding the connectivity, a part of the logic (gates) in the selected timing paths are also implemented in the keyRB(s). We illustrate that when the logic gates are twisted with keyRBs, the BVA could not provide any advantage as a pre-processing step. Our experimental results show that, by using InterLock, with only three 8×8 or only two 16×16 keyRBs (twisted with actual logic gates), the resilience against existing attacks as well as our new proposed CP&SAT attack would be guaranteed while, on average, the delay/area overhead is less than 10% for even medium-size benchmark circuits.
more »
« less
DFSSD: Deep Faults and Shallow State Duality, A Provably Strong Obfuscation Solution for Circuits with Restricted Access to Scan Chain
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 for building deep, yet key recoverable faults that could not be discovered by sequential SAT (and bounded model checker based) attacks in a reasonable time.
more »
« less
- NSF-PAR ID:
- 10197816
- Date Published:
- Journal Name:
- 2020 IEEE 38th VLSI Test Symposium (VTS)
- Page Range / eLocation ID:
- 1 to 6
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In this paper, we introduce SCRAMBLE, as a novel logic locking solution for sequential circuits while the access to the scan chain is restricted. The SCRAMBLE could be used to lock an FSM by hiding its state transition graph (STG) among a large number of key-controlled false transitions. Also, it could be used to lock sequential circuits (sequential datapath) by hiding the timing paths' connectivity among a large number of key-controlled false connections. Besides, the structure of SCRAMBLE allows us to engage this scheme as a new scan chain locking solution by hiding the correct scan chain sequence among a large number of the key-controlled false sequences. We demonstrate that the proposed scheme resists against both (1) the 2-stage attacks on FSM, and (2) SAT attacks integrated with unrolling as well as bounded-modelchecking. We have discussed two variants of SCRAMBLE: (I) Connectivity SCRAMBLE (SCRAMBLE-C), and (b) Logic SCRAMBLE (SCRAMBLE-L). The SCRAMBLE-C relies on the SAT-hard and key-controlled modules that are built using near non-blocking logarithmic switching networks. The SCRAMBLE-L uses input multiplexing techniques to hide a part of the FSM in a memory. In the result section, we describe the effectiveness of each variant against state-of-the-art attacks.more » « less
-
null (Ed.)Circuit obfuscation is a recently proposed defense mechanism to protect the intellectual property (IP) of digital integrated circuits (ICs) from reverse engineering. There have been effective schemes, such as satisfiability (SAT)-checking based attacks that can potentially decrypt obfuscated circuits, which is called deobfuscation. Deobfuscation runtime could be days or years, depending on the layouts of the obfuscated ICs. Hence, accurately pre-estimating the deobfuscation runtime within a reasonable amount of time is crucial for IC designers to optimize their defense. However, it is challenging due to (1) the complexity of graph-structured circuit; (2) the varying-size topology of obfuscated circuits; (3) requirement on efficiency for deobfuscation method. This study proposes a framework that predicts the deobfuscation runtime based on graph deep learning techniques to address the challenges mentioned above. A conjunctive normal form (CNF) bipartite graph is utilized to characterize the complexity of this SAT problem by analyzing the SAT attack method. Multi-order information of the graph matrix is designed to identify the essential features and reduce the computational cost. To overcome the difficulty in capturing the dynamic size of the CNF graph, an energy-based kernel is proposed to aggregate dynamic features into an identical vector space. Then, we designed a framework, Deep Survival Analysis with Graph (DSAG), which integrates energy-based layers and predicts runtime inspired by censored regression in survival analysis. Integrating uncensored data with censored data, the proposed model improves the standard regression significantly. DSAG is an end-to-end framework that can automatically extract the determinant features for deobfuscation runtime. Extensive experiments on benchmarks demonstrate its effectiveness and efficiency.more » « less
-
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, 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.more » « less
-
null (Ed.)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 conditions 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.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/VTS48691.2020.9107629
