SARLock: SAT Attack Resistant Logic Locking

Muhammad Yasin† , Bodhisatwa Mazumdar‡ , Jeyavijayan (JV)ξ Rajendran and Ozgur Sinanoglu‡
yasin@nyu.edu, bm105@nyu.edu, jv.ee@utdallas.edu, ozgursin@nyu.edu
† Electrical and Computer Engineering, NYU Tandon School of Engineering, NY, USA
ξ Erik Jonsson School of Engineering & Computer Science, The University of Texas at Dallas, TX, USA
‡ Electrical and Computer Engineering, New York University Abu Dhabi, Abu Dhabi, U.A.E.
Abstract—Logic locking is an Intellectual Property (IP) pro- will not generate correct output unless it is activated using the
tection technique that thwarts IP piracy, hardware Trojans, correct key. Even if an attacker gets access to the locked netlist
reverse engineering, and IC overproduction. Researchers have with the key gates, either by stealing in design house or by
taken multiple attempts in breaking logic locking techniques and
recovering its secret key. A Boolean Satisfiability (SAT) based reverse engineering the masks in the foundry, the netlist could
attack has been recently presented that breaks all the existing implement one of exponentially many functions determined
combinational logic locking techniques. In this paper, we develop by the key value unknown to the attacker.
a lightweight countermeasure against this and other attacks that Several researchers have exploited the weaknesses of dif-
aim at gradually pruning the key search space. Our proposed
ferent combinational logic locking techniques and developed
logic locking technique, referred to as SARLock, maximizes the
required number of distinguishing input patterns to recover the attacks that recover the secret key [8], [11], [13], [14]. An
secret key. SARLock thwarts the SAT attack by rendering the introduction of the logic locking techniques and a summary
attack effort exponential in the number of bits in the secret key, of the recent attacks are presented in Section VI. While
while its overhead grows only linearly. specific attacks focus on specific weak points of a logic locking
I. I NTRODUCTION technique, a more general attack was presented at HOST 2015
The evolving complexity of Integrated Circuits (ICs) and the that breaks all existing combinational logic locking techniques,
skyrocketing costs of building or maintaining a semiconductor recovering the secret key within a few hours for most of the
foundry have propelled the globalization of IC design and locked circuits [14].
manufacturing flow [1]. Design houses may purchase Intellec- The attack uses Boolean satisfiability (SAT) based algo-
tual property (IP) cores from third-party IP vendors to reduce rithms and we refer to it as SAT attack [14]. In the threat
their design effort and meet strict time-to-market constraints. model of the attack, the attacker is a malicious agent in the
Many companies, such as Apple, operate fabless and outsource foundry with access to the following:
the fabrication to offshore foundries. In a globalized IC supply
1) a locked netlist with the key gates.
chain, untrusted agents may obtain access to the valuable IP
2) a functional IC with the correct key embedded inside. The
or the physical IC, which gives rise to security threats. These
attacker can apply inputs to the IC and observe the outputs.
malicious agents can pirate the IP, overbuild ICs for illegal
sale, tamper the ICs to insert malicious circuitry in the form The objective of the attacker is to extract the secret key.
of Hardware Trojans (HTs), or reverse engineer the netlist The SAT attack uses modern SAT solvers to compute special
from an IC for unlicensed use [2]. distinguishing input patterns (DIP) [14]. These patterns, along
Countermeasures such as IC camouflaging [3], split man- with the correct output collected from the functional IC,
ufacturing [4], and IC metering [5] have been developed to are used to reduce the key search space by eliminating the
thwart these attacks. Logic locking1 is a set of techniques incorrect keys. A single distinguishing input pattern may elim-
that thwart IP piracy, overbuilding, and reverse engineering inate/discriminate multiple incorrect key values. The attack is
attacks by locking a design with a secret key [6], [10]– successful when all incorrect key values are eliminated.
[12]. To enable chip-locking features, additional logic, e.g., This paper focuses on defense against the SAT attack [14].
XOR/XNORs gates referred to as key gates, is added to the The specific contributions of this paper are as follows:
original netlist to obtain a locked netlist. 1) We analyze the strengths and weaknesses of the SAT at-
Figure 1(a) shows an example netlist, and Figure 1(b) shows tack [14]. Based on the discriminating ability of individual
its locked version through three XOR/XNOR key gates. One input patterns, we present a scenario that is hardest for the
of the inputs of each key gate is driven by a wire in the original SAT attack to break.
design, while the other input, referred to as key input, is driven 2) We present a lightweight SAT-Attack Resistant Logic
by a key bit stored in a tamper-proof memory. The inverters Locking (SARLock) technique that thwarts key-
in the netlist can be moved around to increase the obfuscation distinguishing attacks. The proposed technique adds
complexity as shown in Figure 1(c): An attacker will not know only a few XOR/XNOR gates; however, the attack effort
whether the inverter is a part of original design or added for increases exponentially with the number of key bits.
logic locking. This locked netlist passes through the untrusted We demonstrate the effectiveness of our approach using
design/fabrication stages. A locked IC (or a locked netlist) empirical attack results.
1 Researchers have previously used the terms “logic obfuscation” [6]–[9]
3) We demonstrate that SARLock can be used in conjunction
and “logic encryption” [10] for this purpose. However, echoing the call for with existing logic locking techniques to protect against a
consistent terminology in [11], we use the term “logic locking.” wide spectrum of attacks.
 a K1 K1
G1 a K1 a K1
b G1 G1
b b
K2 G5 Y K2 G5 Y
G5 Y K2 K2
G2 G2 G2
c c c
K3 G4 K3 G4
G4 G3
K3
G3
K3
G3

(a) Example circuit: majority of in- (b) Circuit locked using XOR/XNOR key (c) Locked circuit with inverters absorbed by
puts [14]. gates. The correct key is value is 110. the key gates. The correct key value is 110.
Fig. 1: Logic locking using XOR/XNOR gates [12]. This technique is vulnerable to SAT attack [14].

4) We present an analysis of the lower bound on the number to identify the correct key [14]. In iteration 1, the DIP 011
of distinguishing input patterns (#DIP s) needed for a is used. For this DIP, the key value k4 alone produces a
successful SAT attack. wrong output as highlighted in red. Thus, only one incorrect
II. P RELIMINARIES : T HE SAT ATTACK [14] key is ruled out in the first iteration. In the second and third
The SAT attack iteratively rules out incorrect key values iterations, key values k1 and k7 are ruled out, using the
using distinguishing input patterns [14]. A distinguishing input patterns 111 and 101, respectively. The pattern 100, used in
pattern Xd is an input value for which at least two different the fourth iteration, eliminates all incorrect keys and the attack
key values, k1 and k2, produce differing outputs, o1 and o2, successfully identifies the correct key as k6.
respectively. Since o1 and o2 are different, at least one of the The attack could have succeeded in the first iteration with
key values or both of them are incorrect. It is possible for a a single DIP 100, if this input pattern was tried first. Thus,
single DIP to rule out multiple incorrect key values. the execution time of the attack depends on the order in
The DIPs are found by constructing a miter-like circuit as which the input patterns are applied for the SAT attack. The
illustrated in Figure 2. The primary inputs are common to SAT attack, however, chooses the DIPs arbitrarily [14]. The
the two copies of the locked circuit, while the key inputs are larger the number of incorrect key values ruled out per DIP,
left independent. The corresponding outputs of two circuits are the fewer the patterns needed for the attack, which implies a
XORed and then ORed to generate diff signal. The conjunctive smaller execution time of the attack algorithm. We propose
normal form (CNF) of the resultant circuit is generated and to use #DIP s needed for a successful attack as a metric
passed to a SAT solver. The SAT solver finds a DIP Xd for for evaluating the resilience of a logic locking technique
which diff=1, i.e., the outputs of the two circuits are different. against the SAT attack.
Xd is applied to the functional IC, and correct output Id is III. R ESISTING THE SAT ATTACK
obtained. The input-output pair (Xd , Id ) is used to identify The SAT attack is successful against the existing logic lock-
incorrect key values. However, a single pattern may not rule ing techniques as the #DIP s needed for the attack against
out all incorrect keys. To rule out the remaining incorrect key these techniques is relatively small; 250 or fewer patterns
values, more distinguishing patterns are needed. A new pair are needed for a successful attack on 90% of the circuits in
(Xd , Id ) is added to the SAT formula in each iteration and the the study in [14]. The existing logic locking techniques fail
SAT formula is updated. The attack is successful when no to take into account the discriminating ability of individual
further DIP is found, which implies that all incorrect key input patterns and are thus vulnerable to the SAT attack. For
values have been pruned. example, in Figure 3, all incorrect key values k0-k5 and k7
Example. Let us consider the application of the SAT attack produce an incorrect output for the DIP 100, and the SAT
on the example locked circuit in Figure 1. Figure 3 presents attack could identify the correct key value using a single input
the output of the original circuit in column Y, and the output pattern. This represents the best-case scenario for the SAT
of the locked circuit for different key values in the following attack.
columns. For three key inputs, there are eight possible key The worst-case scenario for the SAT attack arises when
values, which are represented as k0, k1,..., k7. When the SAT the attack can discriminate at most one incorrect key
attack is launched on the locked circuit, it takes four DIPs value with each DIP. The truth table in Figure 4 illustrates
K1A K2A KnA SAT attack resistant locking for three primary inputs and three
... ! Output!Y!for!different!key!values! !
O1A
No.! a! b! c! Y! k0! k1! k2! k3! k4! k5! k6! k7! Pruned!key!values!!
O2A
I1
... 0! 0! 0! 0! 0! 1! 1! 1! 1! 1! 1! 0! 1! !
I2
... Circuit copy A
OnA
X1 1! 0! 0! 1! 0! 1! 1! 1! 1! 1! 1! 0! 1! !
In 2! 0! 1! 0! 0! 1! 1! 1! 1! 1! 1! 0! 1! !
X2 diff 3! 0! 1! 1! 1! 1! 1! 1! 1! 0! 1! 1! 1! iter!1:!k4!
K1B K2B
...Kn B ... 4! 1! 0! 0! 0! 1! 1! 1! 1! 1! 1! 0! 1! iter!4:!all!incorrect!
5! 1! 0! 1! 1! 1! 1! 1! 1! 1! 1! 1! 0! iter!3:!k7!
Xn
O1B
6! 1! 1! 0! 1! 1! 1! 0! 1! 1! 1! 1! 1! !
7! 1! 1! 1! 1! 1! 0! 1! 1! 1! 1! 1! 1! iter!2:!k1!
Circuit copy B
...
O2B
Fig. 3: Analysis of the !
SAT attack against logic locking [14]. Columns
!
OnB k0-k7 show the locked circuit’s output for different key values. Red
Fig. 2: Miter-like circuit to determine DIPs [14]. entries in each row denote an incorrect output. The correct key is k6.
 !
!
! Output!Y!for!different!key!values!
No.! a! b! c! Y! k0! k1! k2! k3! k4! k5! k6! k7!
0" 0" 0" 0" 0" 1" 0" 0" 0" 0" 0" 0" 0"
1" 0" 0" 1" 0" 0" 0" 1" 0" 0" 0" 0" 0"
2" 0" 1" 0" 0" 0" 1" 0" 0" 0" 0" 0" 0"
3" 0" 1" 1" 1" 1" 1" 1" 0" 1" 1" 1" 1"
4" 1" 0" 0" 0" 0" 0" 0" 0" 1" 0" 0" 0"
5" 1" 0" 1" 1" 1" 1" 1" 1" 1" 1" 1" 1"
6" 1" 1" 0" 1" 1" 1" 1" 1" 1" 0" 1" 1"
7" 1" 1" 1" 1" 1" 1" 1" 1" 1" 1" 1" 0"
Fig. 4: Resisting the SAT attack by controlling the discriminating
ability of input patterns. At most one incorrect key value corrupts
the output for any input pattern.
key inputs. In each row, there is at most one key value that
generates an incorrect output. As dictated by the truth table in
Figure 4, when the SAT attack is launched on a circuit with
|K| key bits, #DIP s ≥ 2|K| − 1. Thus, the attack effort
grows exponentially with |K|.
A. SARLock: SAT attack-resilient logic locking Fig. 6: Area, power, and delay overhead of SARLock for different
values of |K|.
To build a SAT attack resistant circuit that implements
a truth table similar to the one shown in Figure 4, in a SARLock, however, exhibits strong resilience against the
lightweight and scalable fashion, we use a small comparator SAT attack. As shown in Table II, the #DIP s for SARLock
circuit. The comparator generates a flip signal that is asserted grows exponentially with |K|, across all the benchmarks.
for specific input and key value combinations. The flip signal While the #DIP s doubles with each increment in |K|, the
will be XORed with one of the primary outputs as shown in change in execution time can be higher – 3× to 4× for most of
Figure 5. To prevent the flip signal from being asserted for the the circuits. The execution time varies across the benchmark
correct key value, such as 110 in Figure 4, a small mask logic circuits, because the number of clauses in the SAT formula
is inserted. The resulting locked circuit achieves the desired of each circuit is different. Although the key size |K| used in
resistance against the SAT attack at minimal overhead. We Table I and Table II is small, these key sizes are considered
refer to the proposed IP protection logic as SARLock. for comparing #DIP s and execution time of the SAT attack
For |K| key bits, the additional logic will consist of |K| + 1 empirically. While the attack completes within a minute for
two-input XOR/XNOR gates and 2|K| + 1 two-input AND most circuits for |K| = 10, the attack takes about 4 − 5 hours
gates. On increasing the key size, |K|, the area overhead grows for the OpenSPARC controller circuits for |K| = 14.
linearly, while there is an exponential increase in the #DIP s. Figure 8 shows that the area and power overhead of SAR-
B. Results Lock increases linearly with |K|, as the number of gates
In this section, we report the effectiveness of SARLock inserted by SARLock grows linearly with |K|. However,
against the SAT attack using empirical attack results2 . We the benefit from the security perspective is exponential. The
compare SARLock with strong logic locking (SLL) [8], since average delay overhead of SARLock is less than 0.7%.
amongst the existing (SAT attack vulnerable) logic locking C. Provably secure obfuscation
techniques, SLL offers the best resilience to the other attacks We now provide a security analysis of the SARLock from
on logic locking [6], [8], [11], [13] (see Section VI). the provable obfuscation perspective. The inputs to this logic
Table I reports the #DIP s and the execution time of the block are primary input IN and the key input K, while the
attack on SLL [8] for different key sizes |K|. SLL can be output is a single bit called flip. This logic block can be
broken with only a few DIPs. Moreover, the execution time of represented as the Boolean function flip = F (IN, K).
the attack is below one second for all the benchmark circuits, For each incorrect key guess, Kincorr , to the SARLock
which demonstrates how vulnerable SLL [8] and existing block, the output bit is different at only one input w.r.t.
locking techniques are to the SAT attack. the correct key input Kcorr . In other words, the function
F (IN, Kcorr ) ⊕ F (IN, Kcorr ⊕ α), α ∈ {0, 1}n \ {0n } is
IN Logic   a one-point function3 . The incorrect key Kincorr is defined as
cone   Y Kcorr ⊕ α. The study in [17] shows that the implementation
of this one-point function can be provably obfuscated, giving
?   Mask   the attacker no advantage beyond having a black-box access to
K =   flip
the implemented netlist. For instance, the one-point function
Fig. 5: SAT attack resistant circuit. The flip signal is asserted upon
a match between an input value and a key value. can be obfuscated as:

if rIN = rKcorr ⊕α

1,
2 The F (IN, Kcorr ) ⊕ F (IN, Kcorr ⊕ α) =
experiments are conducted using ISCAS85 benchmark circuits and 0, otherwise
OpenSPARC microprocessor controllers [15]. The SAT attack is executed on
a server with 6-core Intel Xeon W3690 CPU, running at 3.47GHz, with 24 3 A point function is a Boolean function that produces the output value 1
GB RAM [14], [16]. at exactly one point.
 TABLE I: #DIP s and the execution time (s) of the SAT attack [14] to break SLL [8] for different values of |K|.
#DIP s Execution time (s)
Benchmark 10 11 12 13 14 10 11 12 13 14
s5378 8 9 9 10 13 0.2 0.2 0.2 0.2 0.2
c5315 4 3 4 5 3 0.3 0.3 0.3 0.3 0.3
c7552 8 9 9 9 12 0.7 0.5 0.5 0.5 0.5
s9234 7 13 13 10 12 0.2 0.3 0.3 0.3 0.3
IFU 8 8 9 13 11 0.1 0.1 0.1 0.1 0.1
LSUrw 4 5 5 7 9 0.1 0.1 0.1 0.1 0.1
FPUin 6 7 8 5 9 0.1 0.1 0.1 0.1 0.1
LSUex 5 5 8 8 6 0.1 0.1 0.1 0.1 0.1
SB 7 5 6 6 6 0.1 0.1 0.1 0.1 0.1
IFQ 9 7 9 9 8 0.2 0.2 0.2 0.2 0.2
TLU 7 6 7 9 10 0.3 0.3 0.4 0.3 0.4

TABLE II: #DIP s and the execution time (s) of the SAT attack [14] to break SARLock for different values of |K|.
#DIP s Execution time (s)
Benchmark 10 11 12 13 14 10 11 12 13 14
s5378 1023 2047 4095 8191 16383 62.6 177.9 996.1 2710.2 9374.6
c5315 1023 2047 4095 8191 16383 79.6 247.4 1188.1 3441.4 11122.5
c7552 1023 2047 4095 8191 16383 73.1 311.1 1276.6 3561.3 11761.5
s9234 1023 2047 4095 8191 16383 77.7 279.0 1235.2 3491.2 12330.9
IFU 1023 2047 4095 8191 16383 32.5 104.3 589.6 2216.8 6650.8
LSUrw 1023 2047 4095 8191 16383 37.3 120.5 618.0 1762.8 6133.0
FPUin 1023 2047 4095 8191 16383 34.9 112.8 650.0 1898.6 6390.0
LSUex 1023 2047 4095 8191 16383 36.0 130.4 690.4 1941.0 7104.9
SB 1023 2047 4095 8191 16383 50.8 149.3 825.2 2412.9 7845.9
IFQ 1023 2047 4095 8191 16383 67.9 232.6 1135.9 2958.1 10521.1
TLU 1023 2047 4095 8191 16383 81.2 271.7 1198.7 3341.4 11628.5

In the exponentiation operation, r is a generator of a multi- logic locking techniques [8], [10], [12] that are resilient against
plicative cyclic group G and IN , Kcorr ⊕α are elements of G. reverse engineering attacks. From the existing (SAT attack
If the chosen family of groups is Z∗p , where p and q are primes vulnerable) logic locking techniques, we choose SLL [8] since,
and p = 2q + 1, then recovering Kcorr ⊕ α from rKcorr ⊕α to the best of our knowledge, SLL offers the maximum pro-
becomes a discrete logarithm (DL) problem. For large sizes of tection against the known attacks [6], [8], [11], [13] on logic
the primes p and q (say 1024 bits), the DL problem is com- locking. SLL inserts XOR/XNOR key-gates with increased
putationally hard. Thus, an attacker cannot extract Kcorr ⊕ α interference among them and protects a circuit from reverse
from rKcorr ⊕α . Under a variant of decisional Diffie-Hellman engineering and sensitization attacks [8] (see Section VI). By
(DDH) assumption4 [18], this construction provably satisfies intertwining the functional gates and the key gates, SLL hides
the strong definition of obfuscation. Hence, this technique can the implementation of a netlist, thwarting the removal attack.
be used to hide Kcorr in the logic block F . However, the To lock a particular circuit output, we propose SAR-
implementation of 1024-bit modular exponentiation incurs a Lock+SLL, a technique that integrates SARLock with SLL.
large area overhead [19] and is, thus, impractical. Given |K| = |K1| + |K2| key bits, SARLock+SLL will:
D. Is SARLock alone sufficient? 1) lock the logic cone (transitive fan-in of the output) with
SARLock successfully thwarts the SAT attack [14]; how-
SLL using |K1| key bits,
ever, it may not protect against other existing attacks, such
2) scramble K2 with K1, and protect the circuit with SAR-
as the removal attack and the sensitization attack5 [10] (see
Lock using the scrambled K2 bits.
Section VI). In removal attacks, for instance, an attacker iden-
tifies the components/gates that belong to the lock circuitry and The key K1 has two roles: it serves as the key for SLL,
removes them from the locked netlist. An attacker can obtain and it scrambles the key K2. Scrambling K2 is important,
the locked netlist either by reverse engineering or by stealing since otherwise, all the flips will occur in pre-determined
it in the design house. Since, the SARLock logic is isolated combinations of input and key values. Moreover, the scrambler
and not intertwined with the original circuit, the attacker can creates a dependency between the K1 and K2, thwarting the
easily separate it from the original circuit. To defend against removal attack, as will be explained further in Section IV-A.
such attacks, SARLock should be coupled with other defenses. SARLock+SLL is illustrated in Figure 7.
IV. T WO - LAYER LOGIC LOCKING The scrambler logic can be chosen by the designer based
To provide protection against a wide spectrum of attacks, on the permissible overheads. For instance, a bus-based IC
we propose to integrate SARLock with one of the existing protection technique [20] authorizes activation of each indi-
vidual chip by leveraging bit permutations as scrambler for
4 The assumption mentions that there is no efficient probabilistic algorithm
the bus data using a key unique to each IC. Some other
that, given any triplet < g a , g b , g c > in G3 , outputs “true” if a = bc, and techniques comprise logic locking techniques [13] such as
“false”, otherwise.
5 Sensitization of an internal line l to an output O implies that any change XOR gates, arithmetic transformations such as addition and
on l will be observable on O. subtraction, bit permutations using Benes network [20], and
 TABLE III: #DIP s and the execution time (s) of the SAT attack [14] to break SARLock+SLL for different values of |K2|.
#DIP s Execution time (s)
Benchmark 10 11 12 13 14 10 11 12 13 14
s5378 1024 2048 4096 8191 16384 54.1 190.6 619.7 4351.8 10250.7
c5315 1024 2049 4096 8191 16383 75.4 252.9 829.1 4778.2 15874.9
c7552 1025 2049 4096 8191 16386 78.3 234.1 757.0 3165.3 14573.1
s9234 1027 2049 4102 8195 16386 77.2 247.9 864.1 3225.7 15532.3
IFU 1023 2056 4100 8206 16389 55.2 166.7 789.5 2309.8 10258.7
LSUrw 1025 2049 4096 8194 16383 58.2 152.0 626.9 1802.6 7466.6
FPUin 1025 2049 4097 8194 16384 28.4 135.0 1359.6 4497.6 15457.2
LSUex 1024 2049 4096 8194 16384 52.8 268.3 1137.2 3101.3 16707.1
SB 1026 2050 4099 8194 16386 69.2 257.4 1416.6 3304.6 19193.7
IFQ 1024 2048 4098 8192 16384 63.3 290.8 1644.7 4185.4 14563.1
TLU 1027 2052 4099 8195 16385 57.2 227.0 2238.7 3507.6 18760.3

crossbar switches [21].

A. Protection against attacks
The scrambler performs mixing of the keys K1 and K2 to
prevent the comparator and the mask circuits from leaking
explicit information about K1 and K2. The attacker needs to
determine the value of K1 to recover K2 from the scrambler.
To determine K1, the attacker needs to perform SAT attack
on the locked logic cone. This, in turn, depends on K2 as the
IC’s output is a function of both K1 and K2, and K2 is the
key for the SARLock circuit that resists the SAT attack. This
circular dependency not only thwarts the removal attacks, but
also enables SARLock+SLL to inherit the protection that SLL
offers against sensitization attacks [8].
B. Results
For the SAT attack on SARLock+SLL, we assume that
Fig. 8: Area, power, delay overhead for SARLock+SLL for different
|K1| = |K2| = |K|/2. Table III reports the #DIP s for values of |K2|.
different values of |K2|. Since, SLL [8] can be broken with
a small #DIP s, the #DIP s is increased only minimally TABLE IV: Comparison of SARLock+SLL with RLL [12] and
by integrating with SLL [8]. The same table shows that the SLL [8] for |K| = 64. #DIP s and execution time are extrapolated
execution time of the SAT attack on SARLock+SLL is, on based on empirical data.
average, 1.29 times higher than that for SARLock. RLL [12] SLL [8] SARLock+SLL
#DIP s 19 26 4.3E09
The average area, power and delay overhead for SAR-
Exec. time (s) 0.4 0.7 3.1E09
Lock+SLL is 21.27%, 33.3%, and 4.95%, respectively, for Area (%) 29.6 32.2 35.2
|K2| = 14. As shown in Figure 8, the overhead grows Power (%) 45.0 59.2 61.0
only linearly with |K2|. The average delay overhead for Delay (%) 15.1 17.2 9.3
SARLock+SLL is, however, higher compared to SARLock. V. D ISCUSSION
Table IV presents a comparison of SARLock+SLL with SAT attack resistance vs. corruptibility. SARLock thwarts
existing locking logic techniques, random logic locking the SAT attack by corrupting/flipping the output bits selec-
(RLL) [12] and SLL [8], for |K| = 64. While the SAT tively, resulting in a small Hamming distance (HD) at the
attack [14] can break RLL [12] and SLL [8] within a second, outputs on applying incorrect keys [10]. There is a dichotomy
it will take about 3.1 × 109 seconds ≈ 100 years to break between the two security metrics, #DIP s and HD. A de-
SARLock+SLL. The average area, power and delay overhead signer can decide the optimal values of the #DIP s and the
of SARLock+SLL is 35.2%, 61% and 9.3% respectively, HD, based on the application and the threat model. SARLock
which is comparable to that of RLL [12] and SLL [8]. is suitable for protecting the output of the control units in
IN SLL microprocessors, where a single bit flip can vastly corrupt the
Locked  
Logic   overall sequence of operations [22].
cone   Y
K1
Flipping multiple output bits. SARLock aims to protect
the critical logic cones in a circuit while offering the maximum
? resistance to the SAT attack. Flipping multiple output bits
SARLock =
simultaneously increases the HD, and must be traded off
flip
K2 Scrambler   Mask   carefully with the #DIP s. In a setting where SARLock is
designed to flip multiple outputs, its integration with logic
Fig. 7: SARLock+SLL: two layer logic locking. |K1| key bits are locking techniques that increase the HD [10] can be investi-
used for SLL [8] and |K2| key bits for SARLock.
gated, and is part of our future work.
 TABLE V: Comparing logic locking threat models. VIII. C ONCLUSION
Attack Attacker’s assets Attack method
We propose a logic locking technique, SARLock+SLL,
Sensitiza- 1) Locked netlist Sensitization of key bits
tion [8] 2) Activated IC to outputs that thwarts key distinguishing attacks, and in particular, the
Logic cone 1) Locked netlist Brute force on individual SAT attack [14], in addition to thwarting all the attacks that
analysis [6] 2) Activated IC logic cones SLL protects against [8], [11]. SARLock+SLL increases the
SAT-based algorithm that required number of distinguishing input patterns exponentially
SAT [14] 1) Locked netlist rules out incorrect keys
2) Activated IC iteratively
with the key size, by reducing the number of key values
Key bit flipping guided filtered in each iteration of the attack. Thus, the execution
Hill climb- 1) Locked netlist by the Hamming distance
2) Test patterns and time of the attack grows exponentially with the key size. The
ing [11] between test response and
responses circuit output
extra hardware inserted by our proposed technique is provably
obfuscated to resist reverse engineering attacks. As part of our
Choice of the key sizes. SLL aims at maximizing the future work, we plan to explore if SARLock logic alone can
clique size in a graph of key gates, dictating |K1|. The desired be intertwined with the circuit, with minimal loss in #DIP s.
#DIP s dictates |K2|.
R EFERENCES
Low-overhead SARLock. To reduce the overhead, SAR- [1] “Defense Science Board (DSB) study on High Performance Microchip
Lock can be selectively applied on only the crucial parts of Supply,” 2005, [March 16, 2015]. [Online]. Available: www.acq.osd.
mil/dsb/reports/ADA435563.pdf
the design. Controllers typically represent the most valuable [2] R. Karri, J. Rajendran, K. Rosenfeld, and M. Tehranipoor, “Trustworthy
IP in processors while at the same time occupying a small Hardware: Identifying and Classifying Hardware Trojans,” Computer,
vol. 43, no. 10, pp. 39–46, 2010.
area (≈ 1% [5]). In resource-constrained settings, protecting [3] J. Rajendran, M. Sam, O. Sinanoglu, and R. Karri, “Security Analysis
of Integrated Circuit Camouflaging,” in Proc. ACM/SIGSAC Conference
the controllers alone can help achieve the security objectives on Computer & Communications Security, 2013, pp. 709–720.
with a minimal overhead on the overall system. [4] R. W. Jarvis and M. G. McIntyre, “Split Manufacturing Method for
Advanced Semiconductor Circuits,” March 2007, US Patent 7,195,931.
VI. R ELATED W ORK [5] Y. Alkabani and F. Koushanfar, “Active Hardware Metering for Intellec-
tual Property Protection and Security,” in Proc. USENIX Security, 2007,
A. Logic locking techniques pp. 291–306.
• Random logic locking inserts XOR/XNOR key gates at [6] Y.-W. Lee, N. Touba et al., “Improving Logic Obfuscation via Logic
Cone Analysis,” in Proc. IEEE Latin-American Test Symposium, 2015,
random locations in a netlist [12]. pp. 1–6.
[7] R. S. Chakraborty and S. Bhunia, “HARPOON: An Obfuscation-
• Fault analysis based logic locking addresses the limitations Based SoC Design Methodology for Hardware Protection,” IEEE Trans.
of RLE and locks an IC such that a random incorrect key Comput.-Aided Design Integr. Circuits Syst., vol. 28, no. 10, pp. 1493–
1502, 2009.
corrupts maximum output bits [10]. [8] J. Rajendran, Y. Pino, O. Sinanoglu, and R. Karri, “Security Analysis
• Strong logic locking inserts key gates such that it becomes of Logic Obfuscation,” in Proc. IEEE/ACM Design Automation Confer-
ence, 2012, pp. 83–89.
difficult to sensitize key bits to primary outputs on an [9] A. Baumgarten, A. Tyagi, and J. Zambreno, “Preventing IC Piracy Using
Reconfigurable Logic Barriers,” IEEE Des. Test. Comput., vol. 27, no. 1,
individual basis [8]. pp. 66–75, 2010.
B. Attacks against logic locking [10] J. Rajendran, H. Zhang, C. Zhang, G. Rose, Y. Pino, O. Sinanoglu,
and R. Karri, “Fault Analysis-Based Logic Encryption,” IEEE Trans.
Table V presents a summary of existing attacks against logic Comput., vol. 64, no. 2, pp. 410–424, 2015.
[11] S. M. Plaza and I. L. Markov, “Solving the Third-Shift Problem in IC
locking and the corresponding threat models. The sensitization Piracy With Test-Aware Logic Locking,” IEEE Trans. Comput.-Aided
attack generates key-leaking input patterns by analyzing the Design Integr. Circuits Syst., vol. 34, no. 6, pp. 961–971, 2015.
[12] J. Roy, F. Koushanfar, and I. L. Markov, “EPIC: Ending Piracy of
locked netlist. These patterns are applied to the functional Integrated Circuits,” in Proc. Design, Automation and Test in Europe,
2008, pp. 1069–1074.
IC to sensitize the key bits to the primary outputs [8]. The [13] G. K. Contreras, M. T. Rahman, and M. Tehranipoor, “Secure Split-
logic cone analysis attack is based on a divide and conquer Test for Preventing IC Piracy by Uuntrusted Foundry and Assembly,”
in Proc. IEEE International Symposium on Defect and Fault Tolerance
approach [6]. It identifies the logic cone with the smallest in VLSI and Nanotechnology Systems, 2013, pp. 196–203.
number of key bits and employs brute force to recover the [14] P. Subramanyan, S. Ray, and S. Malik, “Evaluating the Security of
Logic Encryption Algorithms,” in Proc. IEEE International Symposium
secret key. SARLock can be complemented with SLL to on Hardware Oriented Security and Trust, 2015, pp. 137–143.
[15] “OpenSPARC T1 Processor,,” 2015, [Nov 1, 2015].
defend against these attacks. [Online]. Available: {http://www.oracle.com/technetwork/systems/
The SAT attack uses Boolean satisfiability techniques to opensparc/opensparc-t1-page-1444609.html}
[16] “Decryption tool binaries and benchmark circuits.” 2015, [Sep
prune the incorrect key candidates (see Section II) [14]. 30, 2015]. [Online]. Available: {https://bitbucket.org/spramod/
The hill climbing search attack uses test data information to host15-logic-encryption}
[17] R. Canetti, “Towards Realizing Random Oracles: Hash Functions That
guess the secret key for ICs that are activated prior to the Hide All Partial Information,” in Proc. Annual International Cryptology
manufacturing test [11]. Unlike the SAT attack, where an Conference, 1997, pp. 455–469.
[18] D. Boneh, “The Decision Diffie-Hellman Problem,” in Algorithmic
attacker can choose I/O pairs of his choice, hill-climbing attack Number Theory. Springer, 1998, pp. 48–63.
[19] G. D. Sutter, J.-P. Deschamps, and J. L. Imaňa, “Modular Multiplication
only uses I/O pairs in the test data set. SARLock also defends and Exponentiation Architectures for Fast RSA Cryptosystem Based on
against the hill-climbing attack, since it increases the #DIP s Digit Serial Computation,” IEEE Trans. Ind. Electron., vol. 58, no. 7,
pp. 3101–3109, 2011.
to be greater than the number of I/O pairs in the test data set [20] J. A. Roy, F. Koushanfar, and I. L. Markov, “Protecting Bus-Based
Hardware IP by Secret Sharing,” in Proc. IEEE/ACM Design Automation
(see Table II and Table III). Conference, 2008, pp. 846–851.
[21] R. Naik and D. Walker, “Large Integrated Crossbar Switch,” in IEEE
VII. ACKNOWLEDGEMENT International Conference on Wafer Scale Integration, 1995, pp. 217–227.
This work was supported by the National Science Founda- [22] N. Karimi, M. Maniatakos, A. Jas, and Y. Makris, “On the Correlation
between Controller Faults and Instruction-Level Errors in Modern Mi-
tion, Computing and Communication Foundations (NSF/CCF) croprocessors,” in Proc. IEEE International Test Conference, 2008, pp.
under Grant 1319841. 1–10.