# Improving Slot Filling Performance with Attentive Neural Networks on
Dependency Structures

Lifu Huang
Rensselaer Polytechnic Institute
<EMAIL_ADDRESS>&Avirup Sil
IBM T.J. Watson Research Center
<EMAIL_ADDRESS>Heng Ji
Rensselaer Polytechnic Institute
<EMAIL_ADDRESS>&Radu Florian
IBM T.J. Watson Research Center
<EMAIL_ADDRESS>
###### Abstract

Slot Filling (SF) aims to extract the values of certain types of attributes
(or slots, such as person:cities_of_residence) for a given entity from a large
collection of source documents. In this paper we propose an effective DNN
architecture for SF with the following new strategies: (1). Take a regularized
dependency graph instead of a raw sentence as input to DNN, to compress the
wide contexts between query and candidate filler; (2). Incorporate two
attention mechanisms: local attention learned from query and candidate filler,
and global attention learned from external knowledge bases, to guide the model
to better select indicative contexts to determine slot type. Experiments show
that this framework outperforms state-of-the-art on both relation extraction
(16% absolute F-score gain) and slot filling validation for each individual
system (up to 8.5% absolute F-score gain).

##  1 Introduction

The goal of Slot Filling (SF) is to extract pre-defined types of attributes or
slots (e.g., per:cities_of_residence) for a given query entity from a large
collection of documents. The slot filler (attribute value) can be an entity,
time expression or value (e.g., per:charges). The TAC-KBP slot filling task Ji
et al. (2011a); Surdeanu and Ji (2014) defined 41 slot types, including 25
types for person and 16 types for organization.

One critical component of slot filling is relation extraction, namely to
classify the relation between a pair of query entity and candidate slot filler
into one of the 41 types or none. Most previous studies have treated SF in the
same way as within-sentence relation extraction tasks in ACE
111http://www.itl.nist.gov/iad/mig/tests/ace/ or SemEval Hendrickx et al.
(2009). They created training data based on crowd-sourcing or distant
supervision, and then trained a multi-class classifier or multiple binary
classifiers for each slot type based on a set of hand-crafted features.

Although Deep Neural Networks (DNN) such as Convolutional Neural Networks
(CNN) and Recurrent Neural Networks (RNN) have achieved state-of-the-art
results on within-sentence relation extraction Zeng et al. (2014); Liu et al.
(2015); Santos et al. (2015); Nguyen and Grishman (2015); Yang et al. (2016);
Wang et al. (2016), there are limited studies on SF using DNN. Adel and
Schütze (2015) and Adel et al. (2016) exploited DNN for SF but did not achieve
comparable results as traditional methods. In this paper we aim to answer the
following questions: What is the difference between SF and ACE/SemEval
relation extraction task? How can we make DNN work for SF?

We argue that SF is different and more challenging than traditional relation
extraction. First, a query and its candidate filler are usually separated by
much wider contexts than the entity pairs in traditional relation extraction.
As Figure 1 shows, in ACE data, for 70% of relations, two mentions are
embedded in each other or separated by at most one word. In contrast, in SF,
more than 46% of $\langle$query, filler$\rangle$ entity pairs are separated by
at least 7 words. For example, in the following sentence:

  1. E1.

“Arcandorquery owns a 52-percent stake in Europe’s second biggest tourism
group Thomas Cook, the Karstadt chain of department stores and iconic shops
such as the KaDeWefiller in what used to be the commercial heart of West
Berlin.”,

Here, Arcandor and KaDeWe are far separated and it’s difficult to determine
the slot type as org:subsidiaries based on the raw wide contexts.

Figure 1: Comparison of the Percentage by the # of Words between two entity
mentions in ACE05 and SemEval-2010 Task 8 relations, and between query and
slot filler in KBP2013 Slot Filling.

In addition, compared with relations defined in ACE (18 types) and SemEval (9
types), slot types are more fine-grained and heavily rely on indicative
contextual words for disambiguation. Yu et al. (2015) and Yu and Ji (2016)
demonstrate that many slot types can be specified by contextual trigger words.
Here, a trigger is defined as the word which is related to both the query and
candidate filler, and can indicate the type of the target slot. Considering
E$1$ again, owns is a trigger word between Arcandor and KaDeWe, which can
indicate the slot type as org:subsidiaries. Most previous work manually
constructed trigger lists for each slot type. However, for some slot types,
the triggers can be implicit and ambiguous.

To address the above challenges, we propose the following new solutions:

  1. $\bullet$

To compress wide contexts, we model the connection of query and candidate
filler using dependency structures, and feed dependency graph to DNN. To our
knowledge, we are the first to directly take dependency graphs as input to
CNN.

  2. $\bullet$

Motivated by the definition of trigger, we design two attention mechanisms: a
local attention and a global attention using large external knowledge bases
(KBs), to better capture implicit clues that indicate slot types.

##  2 Architecture Overview

Figure 2: Overview of the Architecture.

Figure 2 illustrates the pipeline of a SF system. Given a query and a source
corpus, the system retrieves related documents, identifies candidate fillers
(including entities, time, values, and titles), extracts the relation between
query and each candidate filler occurring in the same sentence, and finally
determines the filler for each slot. Relation extraction plays a vital role in
such a SF pipeline. In this work, we focus on relation extraction component
and design a neural architecture.

Given a query, a candidate filler, and a sentence, we first construct a
regularized dependency graph and take all $\langle$governor,
dependent$\rangle$ word pairs as input to Convolutional Neural Networks (CNN).

Moreover, We design two attention mechanisms: (1) Local Attention, which
utilizes the concatenation of Query and Candidate Filler vectors to measure
the relatedness of each input bigram (we set filter width as 2) to the
specific query and filler. (2) Global attention: We use pre-learned slot type
representations to measure the relatedness of each input bigram with each slot
type via a transformation matrix. These two attention mechanisms will guide
the pooling step to select the information which is related to query and
filler and can indicate slot type.

##  3 Regularized Dependency Graph based CNN

###  3.1 Regularized Dependency Graph

Dependency parsing based features, especially the shortest dependency path
between two entities, have been proved to be effective to extract the most
important information for identifying the relation between two entities
Bunescu and Mooney (2005); Zhao and Grishman (2005); GuoDong et al. (2005);
Jiang and Zhai (2007). Several recent studies also explored transforming a
dependency path into a sequence and applied Neural Networks to the sequence
for relation classification Liu et al. (2015); Cai et al. (2016); Xu et al.
(2015).

However, for SF, the shortest dependency path between query and candidate
filler is not always sufficient to infer the slot type due to two reasons.
First, the most indicative words may not be included in the path. For example,
in the following sentence:

  1. E2.

Survivors include two sons and daughters-in-law, Troyfiller and Phyllis Perry,
Kennyquery and Donna Perry, all of Bluff City.

the shortest dependency path between Kenny and Troy is: “Troy
$\leftarrow^{conj}$ Perry $\leftarrow^{conj}$ Kenny”, which does not include
the most indicative words: sons and daughters for their per:siblings relation.
In addition, the relation between query and candidate filler is also highly
related to their entity types, especially for disambiguating slot types such
as per:country_of_birth per:state_of_birth and per:city_of_birth. Entity types
can be inferred by enriching query and filler related contexts. For example,
in the following sentence:

  1. E3.

Merkelquery died in the southern German city of Passaufiller in 1967.

we can determine the slot type as city related by incorporating rich contexts
(e.g., “city”).

To tackle these problems, we propose to regularize the dependency graph,
incorporating the shortest dependency path between query and candidate filler,
as well as their rich contextual words.

Figure 3: Regularized Dependency Graph for Query Arcandor and Filler KaDeWe in
E1.

Given a sentence $s$ including a query $q$ and candidate filler $f$, we first
apply the Stanford Dependency Parser Manning et al. (2014) to generate all
dependent word pairs: $\langle$governor, dependent$\rangle$, then discover the
shortest dependency path between query and candidate filler based on Breadth-
First-Search (BFS) algorithm. The regularized dependency graph includes words
on the shortest dependency path, as well as words which can be connected to
query and filler within $n$ hops. In our experiments, we set $n=1$. Figure 3
shows the dependency parsing output for E1 mentioned in Section 1, and the
regularized dependency graph with the bold circled nodes. We can see that, the
most indicative trigger owns can be found in both the shortest dependency path
of Arcandor and KaDeWe, and the context words of Arcandor. In addition, the
context words, such as shops, can also infer the type of candidate filler
KaDeWe as an Organization.

###  3.2 Graph based CNN

Previous work Adel et al. (2016) split an input sentence into three parts
based on the positions of the query and candidate filler and generate a
feature vector for each part using a shared CNN. To compress the wide
contexts, instead of taking the raw sentence directly as input, we split the
regularized dependency graph into three parts: query related subgraph,
candidate filler related subgraph, and the dependency path between query and
filler. Each subgraph will be taken as input to a CNN, as illustrated in
Figure 2. We now describe the details of each part as follows.

Input layer: Each subgraph or path $G$ in the regularized dependency graph is
represented as a set of dependent word pairs $G=\\{\langle
g_{1},d_{1}\rangle,\langle g_{2},d_{2}\rangle,...\langle
g_{n},d_{n}\rangle\\}$. Here, $g_{i},d_{i}$ denote the governor and dependent
respectively. Each word is represented as a $d$-dimensional pre-trained
vector. For the word which does not exist in the pre-trained embedding model,
we assign a random vector for it. Each word pair $\langle g_{i},d_{i}\rangle$
is converted to a $\mathbb{R}^{2\times d}$ matrix. We concatenate the matrices
of all word pairs and get the input matrix $M\in\mathbb{R}^{2n\times d}$.

Convolution layer: For each subgraph, $M\in\mathbb{R}^{2n\times d}$ is the
input of the convolution layer, which is a list of linear layers with
parameters shared by filtering windows with various size. We set the stride as
2 to obtain all word pairs from the input matrix $M$. For each word pair
$p_{in}=\langle v_{g_{i}},v_{d_{i}}\rangle$, we compute the output vector
$p_{out}$ of a convolution layer as:

$p_{out}=tanh(W\cdot p_{in}+b)$

where $p_{in}$ is the concatenation of vectors for the words $v_{g_{i}}$ and
$v_{d_{i}}$, $W$ denotes the convolution weights, and $b$ is the bias. In our
work all three convolution layers share the same $W$ and $b$.

K-Max Pooling Layer:  we follow Adel et al. (2016) and use K-max pooling to
select K values for each convolution layer. Later we will incorporate
attention mechanisms into K-max pooling.

Fully Connected Layer:  After getting the high-level features based on the
(attentive) pooling layer for each input subgraph, we flatten and concatenate
these three outputs as input to a fully connected layer. This layer connects
each input to every single neuron it contains, and learns non-linear
combinations based on the whole input.

Output Layer:  It takes the output of the fully connected layer as input to a
softmax regression function to predict the type. We use negative log-
likelihood as loss function to train the parameters.

##  4 Attention Strategies for SF

###  4.1 Local Attention

The basic idea of attention mechanism is to assign a weight to each position
of a lower layer when computing the representations for an upper layer, so
that the model can be attentive to specific regions Bahdanau et al. (2014). In
SF, the indicative words are the most meaningful information that the model
should pay attention to. Wang et al. (2016) applied attention from the
entities directly to determine the most influential parts in the input
sentence. Following the same intuition, we apply the attention from the query
and candidate filler to the convolution output instead of the input, to avoid
information vanishing during convolution process Yin et al. (2016).

Figure 4: Local Attention.

Figure 4 illustrates our approach to incorporate local attention. We first
concatenate the vector of query $q$ and candidate filler $f$ using pre-trained
embeddings $v=[v_{q},v_{f}],\in\mathbb{R}^{2d}$. For $q$ or $f$ that includes
multiple words, we average the vectors of all individual words. For each
convolution output $F$, which is a feature map
$\in\mathbb{R}^{\widehat{K}\times N}$, where $N$ is the number of word pairs
from the input, and $\widehat{K}$ is the number of filters, we define the
attention similarity matrix $A\in R^{N\times 1}$ as:

$A_{i}=cosine(L\cdot v,F[:,i])$

where $L\in\mathbb{R}^{\widehat{K}\times 2d}$ is the transformation matrix
between the concatenated vector $v$ and convolution output. $F[:,i]$ denotes
the vector of column $i$ in $F$. Then we use the attention matrix $A$ to
update each column of the feature map $F$, and generate an updated attention
feature map $F^{{}^{\prime}}$ as follows:

$F^{{}^{\prime}}[:,i]=F[:,i]\cdot A[i]$

###  4.2 Global Attention

Considering E1 in Section 1 again, the most discriminating word owns is not
only related to the query and filler, but more specific to the type
org:subsidiaries. Local attention aims to identify the query and filler
related contexts. In order to detect type-indicative parts, we design global
attention, using pre-learned slot type representations.

Wang et al. (2016) explored relation type attention with automatically learned
type vectors from training data. However, in most cases, the training data is
not balanced and some relation types cannot be assigned high-quality vectors
with limited data. Thus, we designed two methods to generate pre-learned slot
type representations.

First, we compose pre-trained lexical word embeddings of each slot type name
to directly generate type representations. For example, for the type
per:date_of_birth, we average the vectors of all single tokens (_person_ ,
_birth_ , _date_) within the type name as its representation.

Another new method is to take advantage of the large size of facts from
external knowledge base (KB) to represent slot types. We use DBPedia as the
target KB and manually map KB relations to slot types. For example,
per:alternate_names can be mapped to alternativeNames, birthName and nickName
in DBPedia. Thus for each slot type, we collect many triples: $\langle$query,
slot, filler$\rangle$ and use TransE Bordes et al. (2013), which models slot
types as translations operating on the embeddings of query and filler, to
derive a representation for each slot type. Compared with the first lexical
based slot type representation induction approach, TransE jointly learns
entity and relation representations and can better capture the correlation and
differentiation among various slot types. Later, we will show the impact of
these two types of slot type representations in Section 5.2.

Next we use the pre-learned slot type representations to guide the pooling
process. Formally, let $R\in\mathbb{R}^{d\times r}$ be the matrix of all slot
type vectors, where $d$ is the vector dimension size and $r$ is the number of
slot types. Let $F\in{\mathbb{R}^{\widehat{K}\times N}}$ be a convolution
output, which is the same as Section 4.1. We define the attention weight
matrix $S$ as:

$S_{i,j}=cosine(F[:,i],W\cdot R[:,j])$

where $W\in\mathbb{R}^{\widehat{K}\times d}$ is the transformation matrix for
pre-learned slot type representations and convolution output. Given the weight
matrix $S$, we generate the attention feature map $F^{{}^{\prime\prime}}$ as
follows:

$F^{{}^{\prime\prime}}[:,i]=F[:,i]\cdot\max_{j}\\{S[i,j]\\}\vspace{-0.2cm}$

where $S[i,:]$ denotes the similarity scores between column $i$ in $F$ with
all slot type vectors, and $\max\\{S[i,:]\\}$ is the $max$ value among all
similarity scores for column $i$ in $F$.

Figure 5: Global Attention.

We apply local attention to each convolution output of each subgraph, then
take the concatenation of three flattened attentive pooling outputs to a fully
connected layer and generate a robust feature representation. Similarly,
another feature representation is generated based on global attention. We
concatenate these two features to the softmax layer to get the predicted
types.

##  5 Experiments

###  5.1 Data

For model training, Angeli et al. (2014) created some high-quality clean
annotations for SF based on crowd-
sourcing222http://nlp.stanford.edu/software/mimlre-2014-07-17-data.tar.gz. In
addition, Adel et al. (2016) automatically created a larger size of noisy
training data based on distant supervision, including about 1,725,891 positive
training instances for 41 slot types. We manually assessed the correctness of
candidate filler identification and their slot type annotation, and extracted
a subset of their noisy annotations and combined it with the clean
annotations. Ultimately, we obtain 23,993 positive and 3,000 negative training
instances for all slot types.

We evaluate our approach in two settings: (1) relation extraction for all slot
types, given the boundaries of query and candidate fillers. We use a
script333http://cistern.cis.lmu.de. to generate a test set (4892 instances)
from KBP 2012/2013 slot filling evaluation data sets with manual assessment.
(2) apply our approach to re-classify and validate the results of slot filling
systems. We use the data from the KBP 2013 Slot Filling Validation (SFV)
shared task, which consists of merged responses returned by 52 runs from 18
teams submitted to the Slot Filling task.

We used the May-2014 English Wikipedia dump to learn word embeddings based on
the Continuous Skip-gram model Mikolov et al. (2013). Table 1 shows the hyper-
parameters that we use to train embeddings and our model.

Parameter |  Parameter Name |  Value
---|---|---
$d$ |  Word Embedding Size |  50
$\lambda$ |  Initial Learning Rate |  0.1
$\widehat{K}$ |  # of Filters in Convolution Layer |  500
$h$ |  Hidden Unit Size in Fully Connected Layer |  1000
$k^{p}$ |  Max Pooling Size |  3
Table 1: Hyper-parameters. |  Method |  Description |  Features
---|---|---|---
Previous Methods |  FCM Yu et al. (2014b) |  A factor-based compositional embedding model by deriving sentence-level and substructure representations |  word embedding, dependency parse, WordNet, name tagging
CR-CNN Santos et al. (2015) |  Applying a pairwise ranking loss function over CNNs |  word embedding, word position embedding
Context-CNN Adel et al. (2016) |  Splitting each sentence into three parts based on query and filler positions, and apply a CNNs to each part |  word embedding
Our Methods |  DepCNN |  Applying CNNs to the shortest dependency path between query and filler |  word embedding, dependency parse
GraphCNN |  DepCNN + applying CNNs to both query and filler related contextual graphs |  word embedding, dependency parse
GraphCNN+L |  incorporating query and filler information as local attention into the GraphCNN |  word embedding, dependency parse
GraphCNN+G1 |  incorporating slot type representations learned from type names as global attention into the GraphCNN |  word embedding, dependency parse
GraphCNN+G2 |  incorporating slot type representations learned from external KB as global attention into the GraphCNN |  word embedding, dependency parse, knowledge base
GraphCNN+L+G2 |  incorporating both local and KB based global attentions into the GraphCNN |  word embedding, dependency parse, knowledge base
Table 2: Approach Descriptions for Multi-Class Relation Classification

###  5.2 Relation Extraction

We compare with several existing state-of-the-art slot filling and relation
extraction methods. Besides, we also design several variants to demonstrate
the effectiveness of each component in our approach. Table 2 presents the
detailed approaches and the features used by these methods.

We report scores with Macro F1 and Micro $F_{1}$. Macro F1 is computed from
the average precision and recall of all types while Micro F1 is computed from
the overall precision and recall, which is more useful when the size of each
category varies. Table 3 shows the comparison results on relation extraction.

|  Method |  Micro F1 |  Macro F1
---|---|---|---
Previous Methods |  FCM |  41.13 |  12.68
CR-CNN |  41.61 |  -
ContextCNN |  41.31 |  29.01
Variants of Our Methods |  DepCNN |  54.91 |  36.63
GraphCNN |  55.63 |  36.74
GraphCNN+L |  56.29 |  37.12
GraphCNN+G1 |  56.18 |  36.87
GraphCNN+G2 |  56.81 |  38.15
Our Method |  GraphCNN+L+G2 |  57.39 |  38.26
Table 3: Relation Extraction Component Performance on Slot Filling Data Set
(%).

We can see that by incorporating the shortest dependency path or regularized
dependency graph into neural networks, the model can achieve more than 13%
micro F-score gain over the previously widely adopted methods by state-of-the-
art systems for SemEval relation classification. It confirms our claim that SF
is a different and more challenging task than traditional relation
classification and also demonstrates the effectiveness of dependency knowledge
for SF.

In addition, by incorporating local or global attention mechanism into the
GraphCNN, the performance can be further improved, which proves the
effectiveness of these two attention mechanisms. Our method finally achieves
absolute 16% F-score gain by incorporating the regularized dependency graph
and two attention mechanisms.

To better quantify the contribution of different attention mechanisms on each
slot type, we further compared the performances on each single slot type.
Table 4 shows the gain/loss percentage of the Micro F1 by adding local
attention or global attention into GraphCNN for each slot type. We can see
that both attentions yield improvement for most slot types.

Slot Type |  Impact of Attention (%) |  Training Data Distribution (%) |  F1 (%) |  Wide Context Distribution (%) |  Impact of Depen- dency Graph (%)
---|---|---|---|---|---
Local |  Global-KB |  |  |  |
state_of_death |  9.8 |  -0.4 |  0.9 |  41.8 |  66.7 |  44.2
date_of_birth |  7.3 |  121.3 |  1.3 |  84.1 |  20.0 |  -81.9
age |  4.1 |  -5.3 |  1.3 |  98.5 |  15.9 |  28.5
per:alternate_names |  -2.0 |  21.2 |  1.5 |  36.6 |  41.5 |  62.0
origin |  -0.9 |  7.8 |  1.7 |  61.5 |  29.3 |  137.3
country_of_birth |  16.7 |  12.0 |  1.9 |  61.5 |  55.6 |  162.5
city_of_death |  1.1 |  3.3 |  1.9 |  61.3 |  70.3 |  24.4
state_of_headq. |  9.7 |  -5.1 |  3.1 |  51.7 |  54.8 |  95.7
cities_of_residence |  4.5 |  5.7 |  3.5 |  57.3 |  77.0 |  40.5
states_of_residence |  -4.3 |  2.3 |  3.8 |  50.5 |  45.9 |  175.8
country_of_headq. |  5.6 |  -0.8 |  5.3 |  41.5 |  54.4 |  146.3
city_of_headq. |  1.6 |  -6.9 |  6.7 |  30.3 |  54.9 |  39.3
employee__of |  14.9 |  4.9 |  7.3 |  65.9 |  54.9 |  132.5
countries_of_residence |  37.7 |  8.6 |  7.4 |  47.4 |  47.2 |  134.9
Table 4: Comparison Analysis for Each Slot Type.

###  5.3 Slot Filling Validation

In TAC-KBP 2013 Slot Filling Validation (SFV) Ji et al. (2011b) task, there
are 100 queries. We first retrieve the sentences from the source corpus (about
2,099,319 documents) and identify the query and candidate filler using the
offsets generated by each response, then apply our approach to re-predict the
slot type. Figure 6 shows the F-scores based on our approach and the original
system. For a system which has multiple runs, we select one for comparison. We
can see that our approach consistently improves the performance of almost all
SF systems in an absolute gain range of [-0.18%, 8.48%]. With analysis of each
system run, we find that our approach can provide more gains to the SF systems
which have lower precision.

Figure 6: Comparison on Individual System

Previous studies Tamang and Ji (2011); Rodriguez et al. (2015); Zhi et al.
(2015); Viswanathan et al. (2015); Rajani and Mooney (2016a); Yu et al.
(2014a); Rajani and Mooney (2016b) for SFV trained supervised classifiers
based on features such as confidence score of each response and system
credibility. For comparison, we developed a new SFV approach: a new SVM
classifier based on a set of features (docId, filler string, original
predicted slot type and confidence score, new predicted slot type confidence
score based on our neural architecture) for each response to take advantage of
the redundant information from various system runs. Table 5 compares our SFV
performance against previous reported scores on judging each response as true
or false. We can see that our approach advances state-of-the-art methods.

Methods |  Precision (%) |  Recall (%) |  F-score (%)
---|---|---|---
Random |  28.64 |  50.48 |  36.54
Voting |  42.16 |  70.18 |  52.68
Linguistic Indicators |  50.24 |  70.69 |  58.73
SVM |  56.59 |  48.72 |  52.36
MTM Yu et al. (2014a) |  53.94 |  72.11 |  61.72
Our Approach |  70.46 |  64.07 |  67.11
Table 5: Overall Performance for SFV: all the Baseline Systems are from Yu et
al. (2014a).

###  5.4 Detailed Analysis

Significance Test:  Table 3 shows the results of multiple variants of our
approach. To demonstrate the difference between the results of these
approaches are not random, we randomly sample 10 subsets (each contains 500
instances) from the testing dataset, and conduct paired t-test between each of
these two approaches over these 10 data sets to check whether the average
difference in their performances is significantly different or not. Table 6
shows the two-tailed P values. The differences are all considered to be
statistically significant while all p-values are less than 0.05.

Method 1 |  Method 2 |  P Value
---|---|---
DepCNN |  GraphCNN |  0.0165
GraphCNN |  GraphCNN+L |  0.0007
GraphCNN |  GraphCNN+G1 |  0.0160
GraphCNN |  GraphCNN+G2 |  $<$0.0001
GraphCNN+L |  GraphCNN+L+G2 |  0.0009
GraphCNN+G2 |  GraphCNN+L+G2 |  0.0010
Table 6: Statistical Significance Test.

Impact of Training Data Size:  We examine the impact of the size of training
data on the performance for each slot type. Table 4 shows the distribution of
training data and the F-score of each single type. We can see that, for some
slot types, such as per:date_of_birth and per:age, the entity types of their
candidate fillers are easy to learn and differentiate from other slot types,
and their indicative words are usually explicit, thus our approach can get
high f-score with limited training data (less than 507 instances). In
contrast, for some slots, such as org:location_of_headquarters, their clues
are implicit and the entity types of candidate fillers are difficult to be
inferred. Although the size of training data is larger (more than 1,433
instances), the f-score remains quite low. One possible solution is to
incorporate fine-grained entity types from existing tools into the neural
architecture.

Impact of Wide Context Distribution:  We further compared the performance and
distribution of instances with wide contexts across all slot types. A context
is considered as wide if the query and candidate filler are separated with
more than 7 words. The last column of Table 4 shows the performance by
incorporating regularized dependency graph (ContextCNN v.s. GraphCNN). We can
see that, for most slot types with wide contexts, such as
per:states_of_residence and per:employee_of, the f-scores are improved
significantly while for some slots such as per:date_of_birth, the f-scores
decrease because most date phrases do not exist in our pre-trained embedding
model.

Error Analysis:  Both of the relation extraction and SFV results showed that,
more than 58% classification errors are spurious. Besides, we also observed
many misclassifications that are caused by conflicting clues. There may be
several indicative words within the contexts, but only one slot type is
labeled, especially between per:location_of_death and
per:location_of_residence. For example, in the following sentence:

  1. E4.

Billy Maysquery, a beloved and parodied pitchman who became a pop-culture
figure through his commercials for cleaning products like Orange Glo, OxiClean
and Kaboom, died Sunday at his home in Tampafiller, Fla.,

the correct slot type is per:city_of_death while our approach mistakenly
labeled it as per:city_of_residence with clue words like home. In addition, as
we mentioned before, slot typing heavily relies on the fine-grained entity
type of candidate filler, especially for the location (including city, state,
country) related slot types. When the context is not specified enough, we can
only rely on the pre-trained embeddings of candidate fillers, which may not be
as informative as we hope. Such cases will benefit from introducing additional
gazetteers such as Geonames 444http://www.geonames.org/.

##  6 Related Work

One major challenge of SF is the lack of labeled data to generalize a wide
range of features and patterns, especially for slot types that are in the
long-tail of the quite skewed distribution of slot fills Ji et al. (2011a).
Previous work has mostly focused on compensating the data needs by
constructing patterns Sun et al. (2011); Roth et al. (2014b), automatic
annotation by distant supervision Surdeanu et al. (2011); Roth et al. (2014a);
Adel et al. (2016), and constructing trigger lists for unsupervised dependency
graph mining Yu and Ji (2016). Some work Rodriguez et al. (2015); Zhi et al.
(2015); Viswanathan et al. (2015); Rajani and Mooney (2016a); Yu et al.
(2014a); Rajani and Mooney (2016b); Ma et al. (2015) also attempted to
validate slot types by combining results from multiple systems.

Our work is also related to dependency path based relation extraction. The
effectiveness of dependency features for relation classification has been
reported in some previous work Bunescu and Mooney (2005); Zhao and Grishman
(2005); GuoDong et al. (2005); Jiang and Zhai (2007); Neville and Jensen
(2003); Ebrahimi and Dou (2015); Xu et al. (2015); Ji et al. (2014). Liu et
al. (2015), Cai et al. (2016) and Xu et al. (2015) applied CNN, bidirectional
recurrent CNN and LSTM to CONLL relation extraction and demonstrated that the
most important information has been included within the shortest paths between
entities. Considering that the indicative words may not be included by the
shortest dependency path between query and candidate filler, we enrich it to a
regularized dependency graph by adding more contexts.

##  7 Conclusions and Future Work

In this work, we discussed the unique challenges of slot filling compared with
tradition relation extraction tasks. We designed a regularized dependency
graph based neural architecture for slot filling. By incorporating local and
global attention mechanisms, this approach can better capture indicative
contexts. Experiments on relation extraction and Slot Filling Validation data
sets demonstrate the effectiveness of our neural architecture. In the future,
we will combine additional rules, patterns, and constraints from slot filling
task definition with DNN techniques to further improve slot filling.

## References

  * Adel et al. (2016) Heike Adel, Benjamin Roth, and Hinrich Schütze. 2016.  Comparing convolutional neural networks to traditional models for slot filling.  In Proc. NAACL2016.
  * Adel and Schütze (2015) Heike Adel and Hinrich Schütze. 2015.  Cis at tac cold start 2015: Neural networks and coreference resolution for slot filling.  In Proc. TAC2015.
  * Angeli et al. (2014) Gabor Angeli, Julie Tibshirani, Jean Wu, and Christopher D Manning. 2014.  Combining distant and partial supervision for relation extraction.  In Proc. EMNLP2014.
  * Bahdanau et al. (2014) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2014.  Neural machine translation by jointly learning to align and translate.  arXiv preprint arXiv:1409.0473 .
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013.  Translating embeddings for modeling multi-relational data.  In Proc. NIPS2013.
  * Bunescu and Mooney (2005) Razvan C Bunescu and Raymond J Mooney. 2005.  A shortest path dependency kernel for relation extraction.  In Proc. EMNLP2005.
  * Cai et al. (2016) Rui Cai, Xiaodong Zhang, and Houfeng Wang. 2016.  Bidirectional recurrent convolutional neural network for relation classification.  In Proc. ACL2016.
  * Ebrahimi and Dou (2015) Javid Ebrahimi and Dejing Dou. 2015.  Chain based rnn for relation classification.  In Proc. NAACL2015.
  * GuoDong et al. (2005) Zhou GuoDong, Su Jian, Zhang Jie, and Zhang Min. 2005.  Exploring various knowledge in relation extraction.  In Proc. ACL2005.
  * Hendrickx et al. (2009) Iris Hendrickx, Su Nam Kim, Zornitsa Kozareva, Preslav Nakov, Diarmuid Ó Séaghdha, Sebastian Padó, Marco Pennacchiotti, Lorenza Romano, and Stan Szpakowicz. 2009.  Semeval-2010 task 8: Multi-way classification of semantic relations between pairs of nominals.  In Proceedings of the Workshop on Semantic Evaluations: Recent Achievements and Future Directions.
  * Ji et al. (2014) Heng Ji, Taylor Cassidy, Qi Li, and Suzanne Tamang. 2014.  Tackling representation, annotation and classification challenges for temporal knowledge base population.  Knowledge and Information Systems .
  * Ji et al. (2011a) Heng Ji, Ralph Grishman, and Hoa Trang Dang. 2011a.  An overview of the tac2011 knowledge base population track.  In Proc. Text Analysis Conference (TAC2011).
  * Ji et al. (2011b) Heng Ji, Ralph Grishman, and Hoa Trang Dang. 2011b.  Overview of the tac2011 knowledge base population track .
  * Jiang and Zhai (2007) Jing Jiang and ChengXiang Zhai. 2007.  A systematic exploration of the feature space for relation extraction.  In HLT-NAACL. pages 113–120.
  * Liu et al. (2015) Yang Liu, Furu Wei, Sujian Li, Heng Ji, and Ming Zhou. 2015.  A dependency-based neural network for relation classification.  In Proc. ACL2015.
  * Ma et al. (2015) Fenglong Ma, Yaliang Li, Qi Li, Minghui Qiu, Jing Gao, Shi Zhi, Lu Su, Bo Zhao, Heng Ji, and Jiawei Han. 2015.  Faitcrowd: Fine grained truth discovery for crowdsourced data aggregation.  In Proc. SIGKDD.
  * Manning et al. (2014) Christopher D. Manning, Mihai Surdeanu, John Bauer, Jenny Finkel, Steven J. Bethard, and David McClosky. 2014.  The stanford corenlp natural language processing toolkit.  In Proc. ACL2014.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013.  Distributed representations of words and phrases and their compositionality.  In Proc. NIPS2013.
  * Neville and Jensen (2003) Jennifer Neville and David Jensen. 2003.  Collective classification with relational dependency networks.  In Proceedings of the Second International Workshop on Multi-Relational Data Mining.
  * Nguyen and Grishman (2015) Thien Huu Nguyen and Ralph Grishman. 2015.  Relation extraction: Perspective from convolutional neural networks.  In Proceedings of NAACL Workshop on Vector Space Modeling for NLP.
  * Rajani and Mooney (2016a) Nazneen Fatema Rajani and Raymond J Mooney. 2016a.  Combining supervised and unsupervised ensembles for knowledge base population.  In Proc. EMNLP2016.
  * Rajani and Mooney (2016b) Nazneen Fatema Rajani and Raymond J Mooney. 2016b.  Supervised and unsupervised ensembling for knowledge base population.  arXiv preprint arXiv:1604.04802 .
  * Rodriguez et al. (2015) Miguel Rodriguez, Sean Goldberg, and Daisy Zhe Wang. 2015.  University of florida dsr lab system for kbp slot filler validation 2015\.  In Proc. TAC2015.
  * Roth et al. (2014a) Benjamin Roth, Tassilo Barth, Michael Wiegand, Mittul Singh, and Dietrich Klakow. 2014a.  Effective slot filling based on shallow distant supervision methods.  In Proc. TAC KBP 2014.
  * Roth et al. (2014b) Benjamin Roth, Emma Strubell, John Sullivan, Lakshmi Vikraman, Kate Silverstein, and Andrew McCallum. 2014b.  Universal schema for slot-filling, cold-start kbp and event argument extraction: Umassiesl at tac kbp 2014.  In TAC KBP.
  * Santos et al. (2015) Cicero Nogueira dos Santos, Bing Xiang, and Bowen Zhou. 2015.  Classifying relations by ranking with convolutional neural networks.  In Proc. ACL2015.
  * Sun et al. (2011) Ang Sun, Ralph Grishman, Wei Xu, and Bonan Min. 2011.  Nyu 2011 system for kbp slot filling.  In Proc. TAC2011.
  * Surdeanu et al. (2011) Mihai Surdeanu, Sonal Gupta, John Bauer, David McClosky, Angel X Chang, Valentin I Spitkovsky, and Christopher D Manning. 2011.  Stanfords distantly supervised slot-filling system.  In Proc. TAC2011.
  * Surdeanu and Ji (2014) Mihai Surdeanu and Heng Ji. 2014.  Overview of the english slot filling track at the tac2014 knowledge base population evaluation.  In Proc. TAC2014.
  * Tamang and Ji (2011) Suzanne Tamang and Heng Ji. 2011.  Adding smarter systems instead of human annotators: re-ranking for system combination.  In Proceedings of the 1st international workshop on Search and mining entity-relationship data. ACM, pages 3–8.
  * Viswanathan et al. (2015) Vidhoon Viswanathan, Nazneen Fatema Rajani, Yinon Bentor, and Raymond Mooney. 2015\.  Stacked ensembles of information extractors for knowledge-base population.  In Proc. ACL2015.
  * Wang et al. (2016) Linlin Wang, Zhu Cao, Gerard de Melo, and Zhiyuan Liu. 2016.  Relation classification via multi-level attention cnns.  In Proc. ACL2016.
  * Xu et al. (2015) Yan Xu, Lili Mou, Ge Li, Yunchuan Chen, Hao Peng, and Zhi Jin. 2015.  Classifying relations via long short term memory networks along shortest dependency paths.  In Proc. EMNLP2015.
  * Yang et al. (2016) Yunlun Yang, Yunhai Tong, Shulei Ma, and Zhi-Hong Deng. 2016.  A position encoding convolutional neural network based on dependency tree for relation classification.  In Proc. EMNLP2016.
  * Yin et al. (2016) Wenpeng Yin, Hinrich Schütze, Bing Xiang, and Bowen Zhou. 2016.  Abcnn: Attention-based convolutional neural network for modeling sentence pairs.  In Proc. TACL2016.
  * Yu et al. (2014a) Dian Yu, Hongzhao Huang, Taylor Cassidy, Heng Ji, Chi Wang, Shi Zhi, Jiawei Han, and Clare R anfd Magdon-Ismail Malik Voss. 2014a.  The wisdom of minority: Unsupervised slot filling validation based on multi-dimensional truth-finding.  In Proc. COLING2014.
  * Yu and Ji (2016) Dian Yu and Heng Ji. 2016.  Unsupervised person slot filling based on graph mining.  In Proc. ACL2016.
  * Yu et al. (2015) Dian Yu, Heng Ji, Sujian Li, and Chin-Yew Lin. 2015.  Why read if you can scan? trigger scoping strategy for biographical fact extraction.  In Proc. NAACL-HLT 2015.
  * Yu et al. (2014b) Mo Yu, Matthew Gormley, and Mark Dredze. 2014b.  Factor-based compositional embedding models.  In NIPS Workshop on Learning Semantics.
  * Zeng et al. (2014) Daojian Zeng, Kang Liu, Siwei Lai, Guangyou Zhou, and Jun Zhao. 2014.  Relation classification via convolutional deep neural network.  In Proc. COLING2014.
  * Zhao and Grishman (2005) Shubin Zhao and Ralph Grishman. 2005.  Extracting relations with integrated information using kernel methods.  In Proc. ACL2005.
  * Zhi et al. (2015) Shi Zhi, Bo Zhao, Wenzhu Tong, Jing Gao, Dian Yu, Heng Ji, and Jiawei Han. 2015\.  Modeling truth existence in truth discovery.  In Proc. SIGKDD2015.


# Unraveling Latch Locking Using Machine Learning, Boolean Analysis, and ILP
††thanks: This material is based on research sponsored by the Air Force
Research Labs (AFRL) and the Defense Advanced Research Projects Agency (DARPA)
under agreement number #FA8650-18-1-7817. The U.S. Government is authorized to
reproduce and distribute reprints for Governmental purposes notwithstanding
any copyright notation thereon. The views and conclusions contained herein are
those of the authors and should not be interpreted as necessarily representing
the official policies or endorsements, either expressed or implied, of the
U.S. Government.

Dake Chen1, Xuan Zhou1, Yinghua Hu1, Yuke Zhang1, Kaixin Yang1, Andrew
Rittenbach2,
Pierluigi Nuzzo1 and Peter A. Beerel1 1University of Southern California, 2USC
Information Sciences Institute
{dakechen, zhouxuan, yinghuah, yukezhan, kaixinya, nuzzo<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Logic locking has become a promising approach to provide hardware security in
the face of a possibly insecure fabrication supply chain. While many
techniques have focused on locking combinational logic (CL), an alternative
latch-locking approach in which the sequential elements are locked has also
gained significant attention. Latch (LAT) locking duplicates a subset of the
flip-flops (FF) of a design, retimes these FFs and replaces them with latches,
and adds two types of decoy latches to obfuscate the netlist. It then adds
control circuitry (CC) such that all latches must be correctly keyed for the
circuit to function correctly. This paper presents a two-phase attack on
latch-locked circuits that uses a novel combination of deep learning, Boolean
analysis, and integer linear programming (ILP). The attack requires access to
the reverse-engineered netlist but, unlike SAT attacks, is oracle-less, not
needing access to the unlocked circuit or correct input/output pairs. We
trained and evaluated the attack using the ISCAS’89 and ITC’99 benchmark
circuits. The attack successfully identifies a key that is, on average, 96.9%
accurate and fully discloses the correct functionality in 8 of the tested 19
circuits and leads to low function corruptibility (less than 4%) in 3
additional circuits. The attack run-times are manageable.

###### Index Terms:

hardware security, logic locking, oracle-less attack, machine learning,
integer linear programming

##  I Introduction

Modern integrated circuit (IC) design and manufacturing often rely on a global
supply chain in which security and intellectual property (IP) rights are a
significant concern. Logic locking (LL) is a common approach to protect
hardware IP from an untrusted foundry [1, 2, 3, 4, 5]. In general, these
approaches incorporate additional logic that supports the introduction of
secret keys. When the user applies an incorrect key value to the locked
circuit, the circuit outputs will often be wrong, thus locking the correct
functionality.

Several LL approaches have been developed for combinational [6, 3, 7, 8] and
sequential circuits [9, 10, 11, 12] as well as for scan chains [13, 14, 15].
Most of the proposed attacks on these defenses are oracle-based; they assume
the attacker has access to a functioning unlocked circuit’s primary inputs and
outputs. These include attacks based on satisfiability checkers (SAT) [16],
sensitization [17], removal and bypass [18, 19], functional analysis [20],
GF(2) linear algebra [21], and various forms of machine learning (ML) [22, 23,
24].

In contrast, several oracle-less attacks have been proposed that require
access to the netlist but not a functional circuit, making them, in some ways,
more dangerous. These attacks take advantage of structural signatures
associated with specific defenses [25, 26, 27], often using machine learning,
such as OMLA [28], GNNUnlock [29] and Snapshot [30], etc [31, 32, 33, 34, 35].
Some attacks, like SAIL [36], target structural signatures left by synthesis
tools inserting XOR and other gate-level locking components. Other techniques
focus on identifying the unique structural signatures of SAT-resilient logic
[29]. Many of these use ML classification as a critical step in identifying
the secret key [25, 26, 30, 36]. Others, in contrast, are focusing on the
identification of gates as either original or locking-related [29, 37, 38].
None of these attacks, however, have been applied to locked latch-based
circuits.

Latch-Based Logic Locking (LBLL) [39], referred to more simply as latch
locking, is a less studied defense that aims to combine the merits of
combinational and sequential logic locking. It first duplicates a subset of a
design’s FFs, then retimes them, and replaces them with latches. It then
inserts two types of decoy latches, delay decoys and logic decoys, to
obfuscate the netlist. After that, control circuitry is added such that all
latches must be correctly keyed for the circuit to function correctly as a
primary-secondary-based design. In particular, when correctly keyed, the delay
decoys are forced to be transparent, and the logic decoys are forced to emit a
constant 0. Additional combinational logic is added to ensure the 0 does not
alter the correct operation of the circuit. The approach demonstrates
resilience to standard SAT and model-checking-based attacks [39] and, to the
best of our knowledge, has yet to be broken.

This paper proposes an oracle-less attack on LBLL that combines deep learning,
Boolean analysis, and integer linear programming. Our attack is based on the
observation that the sequential graph associated with primary-secondary111In
[39], the authors adopt the terminology master and slave latches. We choose to
use the terminology primary and secondary latches. latch-based designs have a
regular structure that is broken by the random insertion of decoy latches.
This distinction yields structural signatures that can be taken advantage of
by machine learning. The first phase of our attack identifies the logic
decoys. The logic decoys are then removed, and the circuit is simplified via
constant propagation. In the second phase, the simplified circuit is input to
a second ML classifier that identifies delay decoy latches. The softmax
outputs of the classifier are fed as the coefficients in the objective
function of an ILP whose constraints understand the correct structure of a
primary-secondary latch-based design. The ILP finds a large pool of potential
keys that are close to the classified output but also adhere to the latch
constraints. We assume each of the identified keys can be independently
evaluated by the attacker.

Our attack was trained and evaluated using the ISCAS’89 and ITC’99 benchmarks
and configured to find a pool of 10k potential keys for each test circuit. The
best key within the pool is on average 96.9% accurate and measured the impact
of incorrect keys by measuring its functional corruptibility [40]. We found
that the best-identified key unlocks the correct functionality in 8 of the
tested 19 circuits and leads to low function corruptibility (less than 4%) in
3 additional circuits. The attack run times demonstrate the scalability of the
approach, remaining less than 15 minutes in all circuits tested.

A plethora of research tries to combine machine learning and constrained
optimization in various ways, including using machine learning to speed up
constrained optimization algorithms and end-to-end methods that feed the
machine learning results into optimization algorithms [41]. In particular,
this specific combination of classification with ILPs has been applied in
natural language processing to detect disfluencies in speech [42]. To the best
of our knowledge, however, this is the first hardware security attack that
combines the benefits of a trained ML classifier with an ILP.

The remainder of this paper is organized as follows. Section II reviews latch
locking and related background in machine learning. Section III describes the
proposed attack, including the motivation for our two-phase approach. Section
IV details experimental results together with two ablation studies that
quantify the benefits of aspects of our attack. Some conclusions and
opportunities for future work are discussed in the last section.

##  II Background

###  II-A Latch-Based Logic Locking (LBLL)

Figure 1: The four steps of latch-based logic locking. Step 1: Select some
interdependent FFs. Step 2: Duplicate FFs, retime some FFs and replace all
duplicated FFs with latches. Step 3: Add delay decoys and logic decoys. Step
4: Add control circuitry.

Figure 1 illustrates the four steps of latch locking. Step one uses a
community detection algorithm to select a subset of FFs. Each selected FF is
then duplicated and some of them are retimed (step 2) before being replaced
with latches (step 3).222In principle, it is also possible to convert the FFs
to latches before retiming, but commercial tools have better support for FF-
based retiming. Note, at this point, the latches must be two-colorable as
alternating primary and secondary latches. Next, the latch locking script
randomly inserts delay and logic decoy latches into the netlist to obfuscate
the netlist and connects all latches to control circuitry (step 4). The
control circuitry accepts two-bit keys to configure the four types of latches.
In particular, delay decoys, when keyed correctly, are forced to be
transparent and thus only influence the delay of the circuit. Logic decoys, on
the other hand, when keyed correctly, output a fixed 0 value. The insertion of
logic decoys must be coupled with extra OR/XOR/MUX gates to ensure the latch,
when keyed correctly, does not corrupt the circuit’s functionality. The
possible cyclic connections and difficulty in setting the initial state
complicate a SAT attack [39].

Figure 2: Overview of the proposed two-phase attack on LBLL.

###  II-B Machine Learning Models

####  II-B1 Multi-layer Perceptrons (MLP)

A Multi-layer Perceptron (MLP) consists of an input, several hidden, and an
output layer of fully connected neurons. The universal approximation theorem
has proven that MLPs can learn any input-output function, motivating their
widespread use in classification tasks. The softmax activation function is
often used at the output layer to produce a probability for each class.
Typically, the class with the highest probability is selected as the
classification result.

####  II-B2 Random Forest (RF)

A random forest (RF) is another widely used classifier that consists of many
decision trees acting as an ensemble. Each decision tree recursively splits
input samples based on features that lead to the smallest conditional entropy
and output a classification vote. The class with the most votes from the
ensemble of decision trees is selected as the final class prediction.

###  II-C Attacker Model

Similar to most oracle-less attacks [29, 20, 26], we assume the adversary has
access to the GDSII mask and has reverse-engineered the gate-level netlist.
The adversary also has information about the technology library and thus can
estimate the circuit’s static delays. Finally, we assume the attacker has
detailed knowledge of the LBLL algorithm. We do not assume that the adversary
has access to the unlocked circuit. That said, to evaluate the accuracy of our
attack, we use the ground truth latch types and netlist.

##  III Proposed Two-Phase Attack

This section first provides motivation and an overview of our two-phase
approach, as illustrated in Figure 2. It then formalizes our notion of a
sequential graph, describes the features used in our ML classifiers and
provides details of each attack phase.

###  III-A Motivation and Overview

Figure 3: (a) Introduction of false paths by logic decoys. (b) A false path
example.

The sequential graph of a circuit abstracts away the combinational logic of a
circuit. Its nodes are primary input/outputs as well as sequential elements,
flip-flops, and latches, and the edges represent the presence of combinational
logic between nodes. The sequential graph of primary-secondary latch-based
designs has a very regular structure; the graph is two-colorable. Our
experiments have shown that it is relatively easy to identify the insertion of
delay decoys that break this structure. However, the insertion of logic decoys
makes the circuit structure more complex. In particular, as shown in Figure 3,
the insertion of logic decoys is sometimes coupled with the insertion of MUXes
that create false paths between latches. In particular, the LBLL flow randomly
inserts a MUX whose selection port is the output of a logic decoy. The “0”
input to the MUX is attached to the near end of a randomly selected net that
is cut. The output of the MUX is connected to the far end of the cut net.
Therefore, when the logic decoy is keyed correctly, the MUX effectively re-
connects the cut net and the circuit operates as if no decoy is added. On the
other hand, the “1” input to the MUX is randomly connected to another pin in
the community, which can create a false path between latches, making the
sequential graph’s structure more complex.

This observation motivates our two-phase approach. In our first phase (see
Figure 2 top), we use ML to detect the logic decoys and then use Boolean
analysis to remove the false paths created by these decoys. With the logic
decoys and associated false paths removed, our second phase (see Figure 2
bottom) classifies the remaining latches using a combination of ML and ILP. In
particular, we use the softmax outputs of a second classifier to create the
objective function of an ILP whose constraints limit the solution space to
legal primary-secondary configurations with delay decoys. The ILP solver is
configured to not only find the closest legal key to that identified by the ML
classifier but also identify many keys that are close to optimal, which the
attacker can individually test.

###  III-B Sequential Graph and Node Feature Set

Figure 4: Illustration of generating a circuit’s sequential graph.

An example is the abstraction of a sequential graph from a circuit is
illustrated in Figure 4. A sequential graph is formally defined as $G=(V,E,F)$
where the set of nodes $V$ consists of latches, FFs, and primary inputs and
outputs. An edge $e\in E$ exists between nodes if there is a combinational
path between the node elements. $F$ represents a vector of structural features
associated with each latch node used by our machine learning models to
classify each latch individually.

In the proposed approach, we extract fourteen features for each node latch,
some of which are illustrated in Figure 5:

Figure 5: Several structural features identified.

  1. 1.

Triangle feature: the fraction of fan-ins $v_{1}$ of a node of interest (NOI)
$v_{2}$ that share a fan-out. As defined below, it may detect decoys because
this structure is not 2-colorable.

$\frac{\sum_{v_{1}\in FI(v_{2})}I[FO(v_{2})\cap FO(v_{1})]}{|FI(v_{2})|}$ (1)

where $I$ denotes the indicator function, $FI$ and $FO$ return the fan-ins and
fan-outs of a node.

  2. 2-3.

As an extension of the triangle feature, we define two trapezoidal features to
detect when two consecutive decoy latches are inserted between primary and
secondary latches. The first feature is

$\frac{\sum_{v_{1}\in FI(v_{2})}I[FO(FO(v_{2}))\cap FO(v_{1})]}{|FI(v_{2})|}$
(2)

where $v_{2}$ is the NOI. The second feature is similar but focuses on the
fan-ins of fan-ins of the NOI (labeled $v_{3}$ in Figure 5).

  3. 4-5.

Max fan-out delay and max fan-in delay, normalized for each circuit.

  4. 6.

Loop: a binary feature that detects if the NOI resides in a loop of three
nodes, as shown in Figure 5

  5. 7.

Single fan-in or fan-out: a binary feature that detects if the NOI has only
one fan-in or fan-out

  6. 8-10.

Three fan-in features: number of fan-in latches, FFs, and primary inputs.

  7. 11-13.

Three fan-out features: number of fan-out latches, FFs, and primary outputs.

  8. 14.

False self-loop feature: used for detecting logic decoy latches that introduce
false self-loops in their fan-out latches, as shown in Figure 5, and defined
as

$\max_{\begin{subarray}{c}v_{2}\in FO(v_{1})\\\ v_{2}\in
SL\end{subarray}}\frac{1}{|FI(v_{2})|}$ (3)

where $SL$ is the set of latches that have a self-loop, and the max operation
effectively yields the highest likelihood that the NOI $v_{1}$ is the cause of
one of its fan-out $v_{2}$ to have a false self-loop.

This set combines structural features that are specific to latch-based
circuits with generic features that have been used in previous attacks [28,
30, 29].

###  III-C Phase 1: Identify Logic Decoys

Once the sequential graphs and feature vectors are extracted, phase 1 aims to
identify the logic decoy latches and remove them. The circuit is then
simplified via constant propagation. For the classifier in this phase, we
found that a random forest outperforms other classifiers, including a support
vector machine (SVM), MLP, and convolutional neural network (CNN), many of
whom, for this problem, suffer from overfitting.

Note that this phase has a similar goal as the SAAM attack in [43] in that it,
to some degree, is trying to identify randomly inserted MUXes. However, our
approach is different because it focuses on the impact of insertion on the
circuit’s sequential graph and does not directly rely on the probabilities of
the MUX input being connected. This means that our approach might still be
effective even if LL was improved to incorporate their intelligent MUX
insertion algorithm [43]. That said, guiding the LBLL MUX insertion step such
that it can fool ML is an interesting area of future work.

###  III-D Phase 2: Identify Remaining Latches

To train the second phase of our attack, we use ground-truth labels to remove
logic decoys from the locked circuit, generate simplified sequential graphs
and the associated feature vectors, then train a second classifier. For this
classifier, we explore options with two and three output classes. The first
distinguishes the delay decoys from primary/secondary latches, and the latter
classifies all three types. In this phase, we use an MLP whose output
activation function is a softmax to yield probabilities for each class. These
probabilities are used as the coefficients in the ILP objective function and
guide the optimization process.

For the ILP, two sets of binary variables, $T$ and $C$, are used. Each latch
is associated with three $T$ variables, $T_{P}$, $T_{S}$, and $T_{DD}$, as
logic decoys are presumably already identified and removed in phase 1. A $T$
variable equal to 1 indicates that the latch belongs to the corresponding type
($T_{P}(i)=1$ indicates that the $i^{th}$ latch is classified as a primary
latch). Each latch also has one $C$ variable, which specifies its color, whose
related constraints will be explained later in this section. The ILP objective
function is to maximize

$\sum_{i=1}^{N}[Pr_{P}(i)\cdot T_{P}(i)+Pr_{S}(i)\cdot
T_{S}(i)+Pr_{DD}(i)\cdot T_{DD}(i)]$

Where $N$ is the number of latches and $Pr_{P}$, $Pr_{S}$, and $Pr_{DD}$ are
the softmax probabilities from the MLP classifier. Note that
$Pr_{P}=Pr_{S}=Pr_{PS}$ in our two-level classifier.

We generate three sets of constraints for the ILP, as described below.

####  III-D1 Fundamental Constraints

We refer to the first set of constraints as fundamental, as follows

  1. F0:

$T_{P}(i)+T_{S}(i)+T_{DD}(i)=1$

  2. F1:

If $T_{P}(i)=1$, then $C(i)=1$

  3. F2:

If $T_{S}(i)=1$, then $C(i)=0$

The F0 constraint ensures that each latch is classified into precisely one
type of latch. The next two constraints, F1 and F2, correlate the latch’s $T$
variable to its color $C$. In particular, the $C$ variable of every primary
latch is equal to 1, and that of every secondary latch is equal to 0.

Note that there are no such constraints for DD latches, which means that the
$C$ variable of a DD latch can either be 1 or 0. Because of the potential
existence of delay decoy latches between primary and secondary latches, the
color variable $C$ is used to capture the identity of the neighboring
primary/secondary latches along the path, as described next.

Figure 6: Illustration of ILP constraints.

####  III-D2 Coloring Constraints

The second set of constraints is for coloring and is applied to every pair of
neighbor latches, where latch $i$ drives latch $j$. This set of constraints
aims to constrain solutions to those in which the primary and secondary
latches are placed alternately.

  1. C0:

If $T_{P}(i)=1$, then $T_{P}(j)=0$

  2. C1:

If $T_{S}(i)=1$, then $T_{S}(j)=0$

Recall that primary and secondary latches are created by splitting the FFs,
the neighbor latches of a primary latch must be secondary latches or delay
decoys, and the neighbor latches of a secondary latch must be primary latches
or delay decoys. In other words, a primary latch cannot follow a primary
latch. Similarly, a secondary latch cannot be followed by a secondary latch.

Moreover, with only the two constraints above that ensure primary and
secondary latches cannot be neighbors with the same type of latches, there
still can be cases where two primary latches or two secondary latches are each
other’s non-decoy neighbors, which should also be avoided. To address this
issue, we propose two more coloring constraints.

  1. C2:

If $T_{DD}(j)=1$, then $C(j)=C(i)$

  2. C3:

If $T_{DD}(i)=1$ and $T_{P}(j)+T_{S}(j)=1$, then $C(j)\neq C(i)$

The C2 constraint ensures the color of delay decoy latches will be the same as
their driving latch, effectively passing the color information to any fan-out
latch. The C3 constraint guarantees that the color of a primary/secondary fan-
out latch will be different from that of a driving delay decoy. Together,
these two constraints guarantee that the color of a primary/secondary latch
after a delay decoy chain will differ from the color of the primary/secondary
latch before the delay decoy chain.

An example of the impact of these constraints is illustrated in Figure 6. It
shows a primary latch (with C=1) driving a chain of delay decoys followed by a
secondary latch (with C=0). The color of the delay decoy that is the immediate
fan-out of the primary latch is 1 because the delay decoy carries the color of
the previous non-decoy latch (due to C2). The second delay decoy also has the
same color as the first delay decoy to pass the information that the previous
non-decoy latch is a primary (also due to C2). In other words, the delay
decoys here act as “pseudo primary latches” as they have the same color as the
primary latches. The last pair of neighbor latches is a delay decoy driving a
secondary latch. The delay decoy, which can be regarded as a “pseudo primary
latch”, indicates that the next non-decoy latch should be a secondary instead
of a primary latch (due to constraint C3).

####  III-D3 Boundary Constraints

The third set of constraints is the latch boundary constraints which helps
disambiguate the coloring options and avoids the assignment of primary and
secondary to be switched. Since the community-based algorithm applied in LBLL
backtracks from the largest fan-in cone [39], the sub-graph near the POs has
less complexity than near the PIs. Thus, we select the primary output
constraint to direct the coloring.

  1. B0:

If latch $i$ is connect to a PO and $T_{DD}(i)=0$, then $T_{S}(i)=1$

  2. B1:

If latch $i$ is connect to a PO and $T_{DD}(i)=1$, then $C(i)=0$

  3. B2:

If latch $i$ is connected to a PI and PO, then $T_{DD}(i)=1$

The first boundary constraint B0 is motivated by the observation that every
flip-flop is divided into a pair of primary and secondary latches. That is to
say, there must be a secondary latch after every primary latch. Therefore, if
a latch is immediately connected to PO and is not a delay decoy, it must be a
secondary latch, as illustrated in Figure 6. Conversely, if a latch
immediately connected to a PO is a delay decoy, then its $C$ variable must be
0 to ensure any primary/secondary latch that drives it is classified as a
secondary (see B1). This is because the color of delay decoys is always
consistent with that of its fan-in latches as enforced by the coloring
constraints. Lastly, if a latch is connected to both a PI and a PO, it can
neither be a primary nor secondary because they appear in pairs (see B2).
Thus, such a latch must be a delay decoy with a color equal to 0. Because FFs
have similar boundary effects, we treat fan-in FFs to latches as PIs and fan-
out FFs to latches as POs.

##  IV Experimental Results

###  IV-A Experiment Setup

The proposed two-phase attack was evaluated on ISCAS’89 and ITC’99 benchmark
circuits333We added reset to the ITC’99 benchmark circuits.. The netlist to
graph and sequential graph extraction was implemented in Python with the
NetworkX library. The model training, inference, and subsequent ML analysis
were implemented using Pytorch and scikit-learn. The Boolean analysis was
performed in the Cadence Genus tool. All experiments, other than the ILP
components, were performed on an Intel i7-8700 CPU running at 3.20 GHz with
16-GB RAM and NVIDIA GeForce RTX 2080 GPU with 16-GB memory. The ILPs were
conducted on an Intel i7-10850H CPU running at 2.70 GHz with 32-GB RAM.

###  IV-B Dataset Generation

In total, we tested 19 circuits across the two benchmark suites. For each
circuit, we locked it with LBLL scripts and generated 11 locked variants with
different random seeds.444We thank the authors of [39] for making their
scripts available to us. To attack each of the 19 benchmark circuits, we
trained a model using the 18 other circuits and their variants, splitting
samples between training and validation. The number of latch samples for
training the models ranged from 75k to 77k. For the first classifier (phase
1), we trained the models with the original locked circuits.Then, we trained
the models with simplified circuits for the second classifier (phase 2),
removing the ground-truth logic decoys and associated false paths.

###  IV-C Accuracy and Run-Time Results

The first-phase models achieve an average accuracy of 98.1%. For the second
phase, Columns 3-4 in Table I and II details the overall accuracy under four
different MLP and ILP configurations used in the second phase. In particular,
we tested both a 2-level and 3-level classifier and, in both cases, configured
the ILP to search for the top 1 (labeled “T-1”) and top 10k (labeled “T-10k”)
potential classifications of latches. We report the accuracy of the only/best-
identified classifications.

For both top-1 and top-10k results, the latch constraints with the 2-level
classifier yielded the highest average accuracy, fully disclosing the
specified secret key in 6 of 19 circuits and, on average, achieving keys that
are, on average, 96.9% accurate.

Note that even for the largest circuit tested, the MLP inference run-time is
less than 5 minutes and the ILP completes its search in less than 15
minutes.555To aid reproducibility, we have posted our attack code on the web
page https://github.com/siriuscdk/LBLL

Circuit | # of | 3-Level MLP (%)
---|---|---
keys | T-1 | T-10k | FC
s298 | 100 | 85.0 | 88.0 | 8.6
s9234 | 188 | 87.2 | 94.1 | 0.02
s13207 | 116 | 98.3 | 100.0 | 0
s15850 | 252 | 89.7 | 96.0 | 0
s35932 | 592 | 90.5 | 91.6 | 3.2
s38417 | 1060 | 97.5 | 99.0 | 17.4
s38584 | 452 | 93.8 | 97.8 | 8.5
b03 | 124 | 83.1 | 93.5 | 19.8
b04 | 112 | 100.0 | 100.0 | 0
b07 | 412 | 90.8 | 95.1 | 15.1
b11 | 412 | 91.3 | 96.1 | 34.1
b12 | 424 | 94.6 | 97.9 | 0
b13 | 156 | 97.4 | 100.0 | 0
b14 | 984 | 97.5 | 98.3 | 3.3
b15 | 2736 | 94.6 | 95.0 | 6.6
b17 | 3858 | 92.0 | 92.5 | 7.9
b20 | 940 | 99.8 | 100.0 | 0
b21 | 840 | 99.0 | 100.0 | 0
b22 | 920 | 99.6 | 100.0 | 0
Ave. |  | 93.8 | 96.6 | 6.6
TABLE I: Attack accuracy results for 3-Level MLP. Circuit | # of | 2-Level MLP (%)
---|---|---
keys | T-1 | T-10k | FC
s298 | 100 | 84.0 | 88.0 | 8.6
s9234 | 188 | 87.2 | 94.1 | 0.03
s13207 | 116 | 98.3 | 100.0 | 0.0
s15850 | 252 | 91.7 | 97.2 | 0.0
s35932 | 592 | 90.7 | 92.7 | 1.5
s38417 | 1060 | 97.3 | 99.1 | 17.3
s38584 | 452 | 93.8 | 97.6 | 8.5
b03 | 124 | 89.5 | 93.5 | 19.8
b04 | 112 | 100.0 | 100.0 | 0.0
b07 | 412 | 91.7 | 95.6 | 10.6
b11 | 412 | 93.0 | 96.8 | 46.8
b12 | 424 | 96.5 | 99.3 | 0.0
b13 | 156 | 96.2 | 100.0 | 0.0
b14 | 984 | 96.8 | 98.1 | 3.3
b15 | 2736 | 95.4 | 95.9 | 6.6
b17 | 3858 | 92.9 | 93.5 | 8.2
b20 | 940 | 99.1 | 100.0 | 0.0
b21 | 840 | 99.3 | 100.0 | 0.0
b22 | 920 | 99.6 | 100.0 | 0.0
Ave. |  | 94.4 | 96.9 | 6.9
TABLE II: Attack accuracy results for 2-Level MLP.

###  IV-D Functional Corruptibility Analysis

We also measured the functional corruptibility of each circuit with the best-
identified key in the two configurations whose accuracy is shown in Table I
and II. The functional corruptibility of a keyed combinational circuit is the
fraction of output bits that are incorrect [44, 45]. For sequential circuits,
however, the inputs should be randomly selected and sequentially applied over
$b$ clock cycles to enable errors in the next state logic to propagate to the
primary outputs [40]. We chose $b=1000$ with different random inputs 1,000
times and averaged the results to obtain a more comprehensive measure of
average functional corruptibility.

The results are shown in the FC columns in Table I and II. For several cases,
even a small number of incorrect key bits lead to a large fraction of output
errors, as may be expected for a sequential circuit. However, overall, 8
circuits achieve 100% correct functionality (FC=0). An FC=0 is expected for
keys that are 100% accurate. Interestingly, however, in some cases, FC=0 for
keys that are less than 100% accurate. We manually investigated these cases
and found that at least some misclassified latches are actually functionally
redundant because all their fanouts are logic decoys. We believe this is a
consequence of the locking script sequentially adding decoys without verifying
that the decoy is not functionally redundant. For many other cases, the
relatively low average functional corruptibility indicates that the identified
keys, even if not perfectly accurate, disclose most of the circuit’s
functionality.

###  IV-E Feature Importance Analysis

Figure 7: Feature importance for the two ML classifiers.

We performed feature importance analysis for the two classifiers used in our
attack, as shown in Figure 7. For the RF classifier, which is used to detect
logic decoy latches, the max fan-out delay, triangle, and the number of fan-
out FFs are the most salient features. Logic decoys usually have relatively
small fan-out delay compared to other latches, and most of them have zero fan-
out FFs. The triangle and two trapezoid features are the most important for
the second MLP classifier and are used to detect delay decoys. This result
makes sense because these three features help in detecting insertions of
individual and pairs of decoy latches that create non-2-colorable sub-graphs.

###  IV-F Baseline MLP and Ablation Studies

To further justify our approach, we first created a baseline, one-stage
4-class MLP to classify all latches with the features described in Section
III-B and obtained an average accuracy of 82.99%. We conducted two ablation
studies to quantify the value of different components of our attack, as shown
below.

####  IV-F1 Value of ILP

To quantify the value of our ILP, we replaced it with a recursive search
algorithm that found the 10k _closest_ keys to the MLP identified result,
where we used the MLP softmax probabilities to define the (weighted) distance
between keys. The average accuracy for this algorithm is 87.4%. The resulting
drop in accuracy of around 9% illustrates the significant benefit of the ILP
limiting the search space to properly colorable classifications.

####  IV-F2 Number of Classifiers

To quantify the advantage of the two-phase approach over a single-phased
approach, we combined the baseline 4-level MLP with false path removal and an
ILP. After the classifier, we removed the identified logic decoys and
simplified the circuit. We then formulated a T-10k ILP with the simplified
circuit and the objective function coefficients from the MLP. The average
accuracy for this approach is 89.8%. The result shows an overall degradation
in an average accuracy of around 7%.

##  V Conclusions and future work

This paper presents an oracle-less attack on latch-based logic locking (LBLL).
Our empirical results show that the best-identified keys are, on average,
96.9% accurate and the correct functionality is fully or mostly disclosed in
the majority of the circuits tested. The attack run times are all less than 15
minutes. Even though the secret key and associated functionality sometimes
remain partially hidden, our results show that the current structure of LBLL
circuits can leak important information to an attacker. This attack motivates
improvements in latch locking to better obfuscate the structure of the locked
circuits. These improvements can include (i) actively avoiding the information
leakage of structures closely adhering to the identified coloring constraints
and (ii) introducing other types of logic decoys, such as logic decoys that
emit a logic one instead of a logic zero.

Since the proposed attack is based on graph analysis, we also note that graph-
based methods may complement our node-based approach. This may include
characterizing and classifying paths with two or three latches. Moreover,
while our classifiers rely on specific structural signatures that we manually
identified, identifying these features automatically using other forms of ML
is interesting future work. In addition, another interesting direction to
explore is to add our novel constraints to more traditional oracle-aided
sequential SAT (Boolean Satisfiability) attacks of unrolled LBLL circuits.
Finally, we note that our attack illustrates the benefits of combining data-
driven and structural analyses and assert that the proposed combination of MLP
and ILP is a good template for many CAD problems.

## References

  * [1] H. M. Kamali, K. Z. Azar, H. Homayoun, and A. Sasan, “InterLock: An Intercorrelated Logic and Routing Locking,” in _2020 ACM/IEEE International Conference On Computer Aided Design (ICCAD)_ , 2020.
  * [2] K. Shamsi, M. Li, K. Plaks, S. Fazzari, D. Z. Pan, and Y. Jin, “IP Protection and Supply Chain Security through Logic Obfuscation: A Systematic Overview,” _ACM Transactions on Design Automation of Electronic Systems (TODAES)_ , vol. 24, no. 6, pp. 1–36, 2019.
  * [3] M. Yasin, A. Sengupta, M. T. Nabeel, M. Ashraf, J. Rajendran, and O. Sinanoglu, “Provably-Secure Logic Locking: From Theory To Practice,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 1601–1618.
  * [4] B. Shakya, X. Xu, M. Tehranipoor, and D. Forte, “CAS-lock: A Security-Corruptibility Trade-off Resilient Logic Locking Scheme,” in _2020 IACR Trans. on Cryptographic Hardware and Embedded Systems (CHES)_ , 2020, p. 175–202.
  * [5] H. M. Kamali, K. Z. Azar, H. Homayoun, and A. Sasan, “Full-Lock: Hard Distributions of SAT instances for Obfuscating Circuits using Fully Configurable Logic and Routing Blocks,” in _2019 ACM/IEEE Design Automation Conference (DAC)_ , 2019.
  * [6] M. Yasin, B. Mazumdar, J. J. Rajendran, and O. Sinanoglu, “SARLock: SAT attack resistant logic locking,” in _2016 IEEE International Symposium on Hardware Oriented Security and Trust (HOST)_ , 2016.
  * [7] G. Takhar, R. Karri, C. Pilato, and S. Roy, “HOLL: Program synthesis for higher order logic locking,” in _Tools and Algorithms for the Construction and Analysis of Systems_ , D. Fisman and G. Rosu, Eds. Cham: Springer International Publishing, 2022, pp. 3–24.
  * [8] M. R. Muttaki, R. Mohammadivojdan, M. Tehranipoor, and F. Farahmandi, “HLock: Locking ips at the high-level language,” in _2021 58th ACM/IEEE Design Automation Conference (DAC)_ , 2021, pp. 79–84.
  * [9] R. S. Chakraborty and S. Bhunia, “HARPOON: An Obfuscation-Based SoC Design Methodology for Hardware Protection,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 2009.
  * [10] K. Z. Azar, H. M. Kamali, S. Roshanisefat, H. Homayoun, C. P. Sotiriou, and A. Sasan, “Data Flow Obfuscation: A New Paradigm for Obfuscating Circuits,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 29, no. 4, pp. 643 – 656, 2021.
  * [11] L. Li and A. Orailoglu, “JANUS-HD: Exploiting FSM Sequentiality and Synthesis Flexibility in Logic Obfuscation to Thwart SAT Attack While Offering Strong Corruption,” in _2022 Design Automation & Test in Europe Conf. (DATE)_, 2022.
  * [12] M. S. Rahman, R. Guo, H. M. Kamali, F. Rahman, F. Farahmandi, M. Abdel-Moneum, and M. Tehranipoor, “O’clock: Lock the clock via clock-gating for soc ip protection,” in _Proceedings of the 59th ACM/IEEE Design Automation Conference_ , ser. DAC ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 775–780. [Online]. Available: https://doi.org/10.1145/3489517.3530542
  * [13] X. Wang, D. Zhang, M. He, D. Su, and M. Tehranipoor, “Secure Scan and Test Using Obfuscation Throughout Supply Chain,” _IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems_ , 2018.
  * [14] R. Karmakar, S. Chattopadhyay, and R. Kapur, “A Scan Obfuscation Guided Design-for-Security Approach for Sequential Circuits,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 67, no. 3, pp. 546–550, 2020.
  * [15] S. Potluri, A. Aysu, and A. Kumar, “SeqL: Secure Scan-Locking for IP Protection,” in _2020 21st International Symposium on Quality Electronic Design (ISQED)_ , 2020, pp. 7–13.
  * [16] P. Subramanyan, S. Ray, and S. Malik, “Evaluating the security of logic encryption algorithms,” in _2015 IEEE International Symposium on Hardware Oriented Security and Trust (HOST)_ , 2015.
  * [17] M. Yasin, J. J. Rajendran, O. Sinanoglu, and R. Karri, “On Improving the Security of Logic Locking,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 2016.
  * [18] X. Xu, B. Shakya, M. M. Tehranipoor, and D. Forte, “Novel Bypass Attack and BDD-based Tradeoff Analysis Against all Known Logic Locking Attacks,” in _International Conference on Cryptographic Hardware and Embedded Systems_. Springer, 2017, pp. 189–210.
  * [19] M. Yasin, B. Mazumdar, O. Sinanoglu, and J. Rajendran, “Removal Attacks on Logic Locking and Camouflaging Techniques,” _IEEE Transactions on Emerging Topics in Computing_ , 2020.
  * [20] D. Sirone and P. Subramanyan, “Functional Analysis Attacks on Logic Locking,” in _2019 Design Automation and Test in Europe Conference Exhibition (DATE)_ , 2019.
  * [21] D. Chen, C. Lin, and P. A. Beerel, “GF-Flush: A GF(2) Algebraic Attack on Secure Scan Chains,” in _2021 IEEE Int. Symp. on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFT)_ , 2021.
  * [22] P. Chakraborty, J. Cruz, and S. Bhunia, “SURF: Joint Structural Functional Attack on Logic Locking,” in _2019 IEEE International Symposium on Hardware Oriented Security and Trust (HOST)_ , 2019, pp. 181–190.
  * [23] H. Chen, C. Fu, J. Zhao, and F. Koushanfar, “GenUnlock: An Automated Genetic Algorithm Framework for Unlocking Logic Encryption,” in _2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)_ , 2019, pp. 1–8.
  * [24] K. Z. Azar, H. M. Kamali, H. Homayoun, and A. Sasan, “NNgSAT: Neural Network guided SAT Attack on Logic Locked Complex Structures,” in _2020 IEEE/ACM International Conference On Computer Aided Design (ICCAD)_ , 2020.
  * [25] D. Sisejkovic, L. M. Reimann, E. Moussavi, F. Merchant, and R. Leupers, “Logic Locking at the Frontiers of Machine Learning: A Survey on Developments and Opportunities,” _arXiv_ , 2021.
  * [26] A. Alaql, D. Forte, and S. Bhunia, “Sweep to the Secret: A Constant Propagation Attack on Logic Locking,” in _2019 Asian Hardware Oriented Security and Trust Symposium (AsianHOST)_ , 2019, pp. 1–6.
  * [27] S. Roshanisefat, H. Mardani Kamali, H. Homayoun, and A. Sasan, “RANE: An open-source formal de-obfuscation attack for reverse engineering of logic encrypted circuits,” ser. GLSVLSI ’21. New York, NY, USA: Association for Computing Machinery, 2021, p. 221–228. [Online]. Available: https://doi.org/10.1145/3453688.3461760
  * [28] L. Alrahis, S. Patnaik, M. Shafique, and O. Sinanoglu, “OMLA: An oracle-less machine learning-based attack on logic locking,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 69, no. 3, pp. 1602–1606, 2022\.
  * [29] L. Alrahis, S. Patnaik, F. Khalid, M. A. Hanif, H. Saleh, M. Shafique, and O. Sinanoglu, “GNNUnlock: Graph Neural Networks-based Oracle-less Unlocking Scheme for Provably Secure Logic Locking,” in _2021 Design Automation and Test in Europe Conf. Exhibition (DATE)_ , 2021.
  * [30] D. Sisejkovic, F. Merchant, L. M. Reimann, H. Srivastava, A. Hallawa, and R. Leupers, “Challenging the Security of Logic Locking Schemes in the Era of Deep Learning: A Neuroevolutionary Approach,” _ACM Journal on Emerging Technologies in Computing Systems (JETC)_ , 2021.
  * [31] L. Alrahis, S. Patnaik, M. A. Hanif, M. Shafique, and O. Sinanoglu, “UNTANGLE: Unlocking routing and logic obfuscation using graph neural networks-based link prediction,” in _2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD)_ , 2021, pp. 1–9.
  * [32] K. Shamsi and G. Zhao, “An oracle-less machine-learning attack against lookup-table-based logic locking,” in _Proceedings of the Great Lakes Symposium on VLSI 2022_ , ser. GLSVLSI ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 133–137. [Online]. Available: https://doi.org/10.1145/3526241.3530377
  * [33] A. Alaql, M. M. Rahman, and S. Bhunia, “SCOPE: Synthesis-based constant propagation attack on logic locking,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 29, no. 8, pp. 1529–1542, 2021.
  * [34] L. Alrahis, S. Patnaik, M. A. Hanif, H. Saleh, M. Shafique, and O. Sinanoglu, “GNNUnlock+: A systematic methodology for designing graph neural networks-based oracle-less unlocking schemes for provably secure logic locking,” _IEEE Transactions on Emerging Topics in Computing_ , vol. 10, no. 3, pp. 1575–1592, 2022.
  * [35] L. Alrahis, S. Patnaik, M. Shafique, and O. Sinanoglu, “MuxLink: Circumventing learning-resilient mux-locking using graph neural network-based link prediction,” in _2022 Design Automation & Test in Europe Conference & Exhibition (DATE)_, 2022, pp. 694–699.
  * [36] P. Chakraborty, J. Cruz, and S. Bhunia, “SAIL: Machine Learning Guided Structural Analysis Attack on Hardware Obfuscation,” in _2018 AsianHOST_ , 2018, pp. 56–61.
  * [37] L. Alrahis, A. Sengupta, J. Knechtel, S. Patnaik, H. Saleh, B. Mohammad, M. Al-Qutayri, and O. Sinanoglu, “GNN-RE: Graph Neural Networks for Reverse Engineering of Gate-Level Netlists,” _IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems_ , 2021.
  * [38] S. D. Chowdhury, K. Yang, and P. Nuzzo, “ReIGNN: State register identification using graph neural networks for circuit reverse engineering,” in _2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD)_ , 2021, pp. 1–9.
  * [39] J. Sweeney, V. Mohammed Zackriya, S. Pagliarini, and L. Pileggi, “Latch-Based Logic Locking,” in _2020 IEEE International Symposium on Hardware Oriented Security and Trust (HOST)_ , 2020, pp. 132–141.
  * [40] Y. Hu, Y. Zhang, K. Yang, D. Chen, P. A. Beerel, and P. Nuzzo, “Fun-SAT: Functional corruptibility-guided SAT-based attack on sequential logic encryption,” in _2021 IEEE International Symposium on Hardware Oriented Security and Trust (HOST)_ , 2021, pp. 281–291.
  * [41] J. Kotary, F. Fioretto, P. Van Hentenryck, and B. Wilder, “End-to-end constrained optimization learning: A survey,” _arXiv_ , 2021.
  * [42] K. Georgila, “Using Integer Linear Programming for Detecting Speech Disfluencies,” in _2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics_ , 2009.
  * [43] D. Sisejkovic, F. Merchant, L. M. Reimann, and R. Leupers, “Deceptive Logic Locking for Hardware Integrity Protection against Machine Learning Attacks,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 2021.
  * [44] J. Rajendran, H. Zhang, C. Zhang, G. S. Rose, Y. Pino, O. Sinanoglu, and R. Karri, “Fault analysis-based logic encryption,” _IEEE Transactions on Computers_ , vol. 64, no. 2, pp. 410–424, 2015.
  * [45] M. Merten, M. E. Djeridane, S. Huhn, and R. Drechsler, “SAT-based key determination attack for improving the quality assessment of logic locking mechanisms.”