∎

11institutetext: Ramakrishna Vaikuntapu 22institutetext: Department of
Electronics & Telecommunication Engineering
Government Engineering College, Bilaspur(C.G) INDIA
22email<EMAIL_ADDRESS>Vineet Sahula
44institutetext: Department of Electronics and Communication Engineering
Malaviya National Institute of Technology Jaipur INDIA
44email<EMAIL_ADDRESS>Lava Bhargava 66institutetext:
Department of Electronics and Communication Engineering
Malaviya National Institute of Technology Jaipur INDIA
66email<EMAIL_ADDRESS>
# Variability aware Golden Reference Free methodology for Hardware Trojan
Detection Using Robust Delay Analysis

Ramakrishna Vaikuntapu  Vineet Sahula  Lava Bhargava

(Received: date / Accepted: date)

###### Abstract

Many fabless semiconductor companies outsource their designs to third-party
fabrication houses. As trustworthiness of chain after outsourcing including
fabrication houses is not established, any adversary in between, with
malicious intent may tamper the design by inserting Hardware Trojans (HTs).
Detection of such HTs is of utmost importance to assure the trust and
integrity of the chips. However, the efficiency of detection techniques based
on side-channel analysis is largely affected by process variations. In this
paper, a methodology for detecting HTs by analyzing the delays of
topologically symmetric paths is proposed. The proposed technique, rather than
depending on golden ICs as a reference for HT detection, employs the concept
of self-referencing. In this work, the fact that delays of topologically
symmetric paths in an IC will be affected similarly by process variations is
exploited. A procedure to chose topologically symmetric paths that are
minimally affected by process variations is presented. Further, a technique is
proposed to create topologically symmetric paths by inserting extra logic
gates if such paths do not exist in the design intrinsically. Simulations
performed on ISCAS-85 benchmarks establish that the proposed method is able to
achieve a true positive rate of 100% with a false positive rate less than 3%.
In our experimentation, We have considered the maximum of 15% intra-die and
20% inter-die variations in threshold voltage ($V_{th}$).

###### Keywords:

Hardware Trojan detection Self-referencing Process variation Path delay

##  1 Introduction

Area, power, and performance have been major concerns for integrated circuit
(IC) designers traditionally, whereas the security aspects of ICs have now
gained a lot of significance. In the present scenario, the semiconductor
industry has adopted a horizontal business model to reduce time-to-market and
stay competitive. In such a production model, the IC manufacturing process is
spread over the globe and involves many third-party design and fabrication
houses. The trustworthiness of such design and fabrication houses is not
established. Thus, the security of these chips has become a major concern for
system designers and gained the interest of many researchers in recent years.
Hardware Trojan (HT) is one such threat to the security and trust of ICs
Spectrum2008-The_Kill_Switch . Hardware Trojans can be introduced by an
adversary at a design house or an untrusted foundry. Depending on the
interests of the adversary the HT can cause changes in functionality, denial-
of-service, reliability reduction or leaking of secret information
Tehranipoor2010-HT-taxonomy . Skorobogatov et al. have reported an incident of
HT in real chips which is a backdoor in military-grade FPGAs
Skorobogatov2012-backdoor-in-military-chip . Hardware Trojan (HT) can be
defined as the unauthorized modification of the original design by an
adversary with malicious intent. Such Trojans can be inserted at any
abstraction level of IC design and manufacturing process. The detailed
taxonomy of hardware Trojans at various abstraction levels can be found in
Tehranipoor2010-HT-taxonomy . In general, Trojans are intelligently designed
to be stealthy, so they do not change the normal functionality of the IC
unless they are activated. Such Trojans may not be detected by using
conventional functional and structural testing techniques, which are used to
test the functionality and detect faults like stuck-at-faults etc. Different
methods have been proposed for detecting Trojans inserted at different
abstraction levelsLi2015-HTD_survey . Such detection methods can be classified
as design verification phase (pre-silicon), test phase (post-silicon) and run-
time Bao2015-HTD-Temp_Tracking  (post-deployment) methods, based on their
applicability at different phases of IC production. The pre-silicon detection
methods mainly focus on the Trojans that are inserted by modifying RTL code
and/or netlist of the design. These methods use the concepts like unused
circuit identification (UCI) Hicks2010-untrusted-computing-base-UCI ,
identification of signals with very low activation probabilities, etc
Zhang2015-Veritrust .

The test phase i.e post-silicon detection methods aim to detect hardware
Trojans in fabricated ICs inserted at untrusted and malicious fabrication
foundries. Even though Logic testing Voyiatzis2016-HT-Triggering-logic ;
Lesperance2015-HTD-Logic-Test  based approaches for HT detection have been
proposed, their efficiency is limited by the stealthy nature of the hardware
Trojans and the generation of tests and test execution time. The majority of
existing post-silicon methods are devised based on side-channel analysis i.e
analyzing the side channel parameters like power, path delay, and
electromagnetic measurements, etc. Many existing side-channel analysis (SCA)
based HT detection techniques depend on the availability of genuine ICs
(golden ICs i.e ICs without any HTs), which are used for generating a
reference signature. This signature is then compared against the side-channel
signature of suspect IC to decide whether any Trojan exists in the IC under
consideration. Obtaining such golden ICs for all the cases is not always
feasible, as it involves expensive invasive techniques such as reverse
engineering Bao2015b-reverse_engg_HT_Detection . Another challenge for side-
channel analysis-based methods is the process variation (PV) which impacts the
efficiency of detection even if golden ICs are available. To overcome these
issues, some golden IC free detection methods have been proposed Liu2014d-HTD-
Golden-free-Statistical ; Zheng2015-Semia ; Chen2016-HTD-Framework-
Statistical-ML ; Zhang2018-Golden-free-Processor-HT , which are based on the
concepts of self-referencing and side-channel signature prediction. If the
size of inserted Trojan is very small compared to the size of the design, its
effect on side-channel parameters may not be differentiable due to process
variations (PVs). In the presence of process variation, even if golden ICs are
available, direct comparison of the side-channel signatures of the suspect
chip with the golden chips may not accurately detect HTs. To mitigate the
effects of process variation on side-channel parameters, researchers have
proposed a technique known as self-referencing Self-referencing-HTD . In this
method, the side channel parameter of an IC is compared with the side channel
parameter of the IC itself, instead of comparing with the golden signature.
The major advantages of self-referencing-based methods are (i) it eliminates
the requirement of golden IC and (ii) the effects of inter-die process
variation are mitigated.

In the present work, a golden IC-free methodology is proposed to detect
Hardware Trojans inserted during fabrication. We have chosen path delay as a
medium for Trojan detection because of its specific advantages such as
hardware Trojan effect is local to the path and the Trojan affects path delay
irrespective of its activation status eliminating the need to activate
Trojans. Every IC contains many paths out of which some paths are
topologically similar, which we term as symmetric paths. Any two paths which
have an equal number of gates of the same type could be considered symmetric
paths (see Fig.2). We analyze the design netlist to identify vulnerable nets
which could be potential locations for hardware Trojan insertion. We select a
path through such a vulnerable net and we term it as the suspect path. A
symmetric path that is topologically similar to the selected suspect path is
identified and it is termed as reference path. A symmetric path pair
consisting of a suspect and its corresponding reference path is formed. As
both the paths in a symmetric path pair pass through the gates of the same
type, their delays experience a strong correlation under the inter-die (global
or die-to-die) process variation effects. A symmetric path pair has been
selected for each vulnerable net in the design netlist. When the delays of
paths in such symmetric path pairs are analyzed by plotting on a two-
dimensional space they follow straight lines under inter-die variation (see
Fig. 3). If a hardware Trojan has presumably been inserted at a vulnerable
net, then the delay of the suspect path will be increased by an amount of HT-
induced delay. This in turn deviates the point of path delays away from the
expected straight line as shown in Fig. 3. The distance between the expected
line and the point of delays, due to Trojan-induced deviation has been used to
calculate a detection metric (DM) for a selected pair of IC under test. In the
presence of intra-die (local or within-die) process variations, the delays of
paths in selected symmetric path pairs may tend to deviate from the expected
straight line. Therefore, this detection metric is compared with a pre-defined
threshold to separate Trojan inserted ICs from Trojan free ICs. This work
mainly focuses on detecting the logical Trojans having payload gate(s). The
detection of other types of Trojans like parametric Trojans is out of the
scope of this paper.

###  1.1 Our Contribution

Following are the contributions of our paper.

  * •

We propose a novel path selection algorithm to select symmetric path pairs in
a way to mitigate the effects of inter-die variation as well as to minimize
the effects of intra-die process variations on hardware Trojan detection
accuracy.

  * •

We present a procedure to create symmetric path pairs if they do not exist in
the design intrinsically to cover all vulnerable nodes of the design for
efficient Trojan detection.

  * •

The proposed Trojan detection methodology employs the concept of self-
referencing wherein the delays of topologically symmetric paths are analyzed
for detecting hardware Trojans. The methodology doesn’t need a golden
reference IC.

The rest of this paper is organized as follows. A brief overview of existing
hardware Trojan detection methods is presented in Section 2. Basics of
hardware Trojan structure, process variation model, and problem formulation
are presented in Section 3. In Section 4, we present the details of the
proposed methodology; and path selection procedure is explained in Section 5.
Simulation results are reported in Section 6 and we conclude in Section 7.

##  2 Related work

The detailed taxonomy and classification of hardware Trojans have been
presented in Tehranipoor2010-HT-taxonomy . Several methods based on logic
testing have been proposed for detecting such Trojans, but these methods may
not always detect active and parametric HTs. The efficiency of these methods
is limited due to the large trigger space of hardware Trojan, which is not
known to the designer. Thus, side-channel analysis (SCA) based techniques have
been considered to be more efficient for detecting hardware Trojans (HTs).
Agarwal et al. proposed to use side-channel parameter (power) for Trojan
detection Agrawal2007-IC-fingerprinting . They constructed a fingerprint using
golden ICs and compared it with the signatures of suspect ICs for HT
detection. Path delays were used to generate the fingerprint of an IC family
for HT detection in Jin2008-path-dly-fingerprint . They have selected a set of
paths that covers the entire design. The path delays of genuine ICs are
measured and principle component analysis (PCA) was used to construct the
fingerprint. The delays of HT inserted ICs are compared against the
fingerprint for HT detection. This method is not scalable for larger designs
as it requires a large test time to measure the delays of such a large number
of paths covering the entire design. The main limitations of these methods
are- (i) the requirement of a set of golden ICs and (ii) the detection
accuracy is largely affected by process variations. Authors in
Li2008-HTD_delay_shadow_reg , a technique was proposed for delay measurement
to detect HTs. This technique uses shadow registers to measure the path delays
and it can be performed at speed at both test time and run time. This method
requires multiple clocks and requires extra registers inserted at the end of
each selected path which incurs higher area overhead. The efficiency of delay-
based HT detection techniques in the presence of process variations was
studied in Rai2009-delay-based-T-D-Process-variation . Authors have considered
process variation in different transistor parameters like channel length ($L$)
and threshold voltage ($V_{th}$). They computed path delays for HT detection
by leveraging statistical techniques, even though process variation affects
the HT detection accuracy. Authors in Lamech2012-HTD_delay_variations_REBEL
proposed an embedded test structure by using existing scan structures to
measure path delays to detect HTs. In this work, they considered only a small
number of arbitrary paths for delay measurement. This technique is not
feasible for larger designs as it incurs a large area overhead for on-chip
control logic. Authors Xiao et al in Tehranipoor2013-HTD_Clk_Sweeping
proposed a clock sweeping-based path delay measurement technique for detecting
HTs. The authors considered a set of few long paths and used transition delay
fault (TDF) test patterns for delay measurements. Statistical techniques were
used for signature generation and HT detection. This technique can only be
used to detect the HTs inserted in long paths and can not detect the HTs in
short paths due to the maximum frequency and power limit of the IC. Authors
Cha and Gupta in Cha2013-Approach-to-select-paths-vectors , proposed to choose
the shortest paths through each possible Trojan location to enhance the effect
of HT thus, improving HT detection accuracy in the presence of process
variations. By choosing shortest paths only the effect of inter-die variation
is minimized and intra-die variation still dominates the detection accuracy.
Moreover, this technique cannot perform well when the HT is inserted at such
locations through which no shorter path exists. A clock glitching method was
proposed to measure path delays and statistical techniques are used to reduce
the effects of process variations in Exurville2015_HTD_resilient_pv .

All the aforesaid hardware Trojan detection methods require golden ICs as
reference for detecting HTs and they all suffer more or less from both inter-
die and intra-die process variations. A self-referencing-based golden-IC free
HT detection method using path delays has been proposed in Norimasa2014-HTD-
Symmetry-Breaking-PDly . It compares the delays of symmetric paths in the
design for detecting HTs. This method identifies the symmetries in the design
by applying and analyzing the input vector space. This method can not scale up
for larger ICs and to do so one has to strike through all possible states
which are not always feasible. Authors have suggested developing and use
algorithms for identifying symmetries in the design, but they have not
reported any such procedure in their work. A pulse propagation technique is
proposed by authors in Deyati2016-HTD-Pulse-propagation  to detect extra
capacitance induced by HT on logical paths. Instead of measuring path delays,
current sensing circuitry is used for sensing the pulse propagating through
the logic paths in the design for HT detection. The efficiency of the method
decreases with the increasing number of high fanout nets in the design. A high
resolution on-chip embedded test structure called time-to-digital converter
(TDC) for measuring path delays and a chip-averaging technique was proposed to
detect delay anomalies introduced by HTs in Ismari2016-HTD-delay-anomalies .
An on-chip self-referencing based HT detection method was proposed in
Zarrinchian2016-latch-based-self-ref-HTD . Two paths with some pre-defined
delay difference are connected to a latch and the output of the latch is
considered for HT detection. If a Trojan affects the path having minimum delay
then the output of latch changes leading to detection of the HT. This method
suffers from the inter-die variation effects as the selected paths may not
remain symmetric, resulting in high false-positive rates. Moreover, this
method incurs higher area and power overheads for implementing the latches and
supporting additional logic such as multiplexers. In
Esirci2017-HTD_correlated_path_delays  an HT detection method was proposed by
using the ratio of delays of two paths. To reduce the effects of inter-die
variations, shorter paths are selected. The design was simulated for
identifying paths in order to minimize the effects of inter-die variations.
Simulating the design and identifying such paths is very difficult and incurs
longer design times for larger circuits as the number of possible paths
increases exponentially. Moreover, this method would not perform well if
sufficiently shorter paths do not exist in the design. A variability-aware
path selection procedure was reported in Ramakrishna2018-VLSID2018 . Authors
have considered only shorter symmetric paths to mitigate process variation
effects, in fact, longer symmetric paths could also perform well in detecting
if they are close enough.

Our proposed methodology in this paper attempts to mitigate the effects of
inter-die variation as well as tries to minimize the effects of intra-die
variation as much as possible enabling more accurate detection of hardware
Trojans. However, like any other delay-based detection techniques, the
proposed method is also not able to detect Trojans that don’t have any impact
on path delays.

##  3 Preliminaries and Problem Formulation

###  3.1 Path delay affected by Hardware Trojan

A Hardware Trojan is constituted by two parts- trigger and payload. The
interconnects in the circuit as shown in Fig. 1, provide inputs to the gates
in the HT trigger. However, some additional capacitance, of this additional
fanout, in turn, impacts the delay. The attack is launched by the payload
gate, which is inserted by ripping a present net in the original circuit (see
Fig. 1). This net affects the delay of all such paths, which pass through it.
The delay is increased by an amount equal to the delay of the payload gate,
which usually is higher than the delay caused by the trigger gate.

Figure 1: Hardware Trojan structure Ramakrishna2018-VLSID2018

###  3.2 Hardware Trojan insertion at vulnerable locations

To defy detection by either testing or side-channel-based techniques, stealthy
HTs might be inserted by the attacker. It has been observed that nodes with
very low switching activity satisfy the requirements sought after by the
attacker Salmani2009-HTD-improving_DPr_reducing_ActTime ;
Salmani2016-Analysis-Layout-HT-Insertion ; Zou2017-Trigger-HTD . Hence, we too
consider, low switching nets in the circuit as vulnerable locations
Ramakrishna2018-VLSID2018 .

###  3.3 Process Variations

As the HTs are very small in size compared to the entire design, their effect
on side-channel parameters is not distinguishable from the effects due to
process variation. The inter-die variation component affects all transistors
of an IC in a similar fashion, whereas, the intra-die variation component is
different depending on their physical locations on the IC Liu2007-PV-spatial-
modeling ; Chang2003-PV-Spatial-modeling . Normally, intra-die variations are
smaller than inter-die variations. We have considered variations in transistor
threshold voltage $V_{th}$ Ramakrishna2018-VLSID2018 . The variation model
considered in this work is shown in (1)). Further, the intra-die component
$\Delta v_{intra}(x,y)$ is divided into- (i) a correlated spatial component
and (ii) a random component, as shown in (2).

$\displaystyle v_{th}(x,y)=v_{th,nominal}+\Delta v_{inter}+\Delta
v_{intra}(x,y)$ (1) $\displaystyle\Delta v_{intra}(x,y)=\Delta
v_{spatial}(x,y)+\Delta v_{random}(x,y)$ (2)

Here, $v_{th,nominal}$ is the nominal value of the threshold voltage, and the
inter-die variation is $\Delta v_{inter}$. Also, $\Delta v_{spatial}(x,y)$ is
a spatially correlated component, for which a representative model is a
correlated multivariate Gaussian random variable; whereas $\Delta
v_{random}(x,y)$ is the random component, modeled as an independent Gaussian
random variable.

###  3.4 Topologically symmetric paths

In this work, we have considered two paths as topologically symmetric if they
pass through similar types of logic gates as shown in Fig. 2. It can be
observed that all the three paths shown in Fig. 2 are symmetric to each other.
Assuming Fig. 2(a) shows a selected suspect path through a vulnerable net, any
one of the two paths shown in Fig. 2(b) and 2(c) can be selected as a
reference path for the selected suspect path as these paths are topologically
symmetric to path shown in Fig. 2(a). We call the path shown in Fig. 2(b) as
type–1 reference path and the path shown in Fig. 2(c) as type–2 reference
path. The delay of the paths shown in Fig. 2 may or may not be equal as it
also depends on the fanout and interconnects delays experienced by gates in
the respective paths of the design.

Figure 2: Symmetric paths. (a) suspect path (b) type–1 reference path (c) type–2 reference path Figure 3: Deviation from expected straight line Table 1: Correlation between path delays of a symmetric path pair for different delay models Symmetric path pair | type–1 | type–2
---|---|---
Delay model | $rise\\_delay$ | $fall\\_delay$ | $\frac{rise\\_delay+fall\\_delay}{2}$ | $rise\\_delay$ | $fall\\_delay$ | $\frac{rise\\_delay+fall\\_delay}{2}$
Correlation (%) | 100 | 100 | 100 | 98.712 | 97.687 | 99.997
Table 2: Correlation between path delays of a symmetric path pair for different path lengths and fanout difference Symmetric path pair | path length | fanout difference (fod)
---|---|---
9 | 12 | 15 | 18 | 0 | 3 | 6 | 9 | 12
Correlation (%) | 99.973 | 99.984 | 99.995 | 99.965 | 100 | 99.996 | 99.993 | 99.974 | 99.922

The fundamental difference between type–1 and type–2 reference paths can be
explained by propagating a transition through these paths concerning the
suspect path. In the type–1 path the signal transition propagates through
gates of the same type in the same order as that of the suspect path. Whereas,
in type-2 paths, the signal transition propagates through similar gates but in
a different order as that of the suspect path. For example, the XOR gate in
Fig. 2(b) experiences the same transition as that of the XOR gate in Fig. 2(a)
when an identical transition is applied at the input pin of the two paths.
Whereas, the XOR gate in Fig. 2(c) experiences the opposite transition as that
of the XOR gate in Fig. 2(a) when an identical transition is applied at the
input pin of the two paths. Further, we identify a symmetric path pair as a
type–1 (type–2) if the selected reference path is of type–1 (type–2). In our
work, the path delay has been considered differently for paths in type–1 and
type–2 symmetric path pairs. We assume the delay of a path for propagating a
rising (falling) transition at its input port through it is represented by
$rise\\_delay$ ($fall\\_delay$).

In type–1 symmetric path, every gate in the reference path experiences the
same transition (rise or fall) concerning the same type of gate in the suspect
path. Thus, the delays of the suspect path and the reference path are highly
correlated for the identical transition applied at their input ports.
Therefore, for paths in type–1 symmetric path pairs the path delay has been
considered as either rise delay or fall delay as shown in (3). i.e. if
$rise\\_delay$ ($fall\\_delay$) is considered as path delay for suspect path
then $rise\\_delay$ ($fall\\_delay$) of the reference path has to be
considered as path delay.

$\centering\text{path\\_delay}=\begin{cases}\text{rise\\_delay}&\text{or}\\\
\text{fall\\_delay}\end{cases}\@add@centering$ (3)

In type–2 symmetric path pairs, some gates of reference path may experience
different transitions concerning the gates of the same type in the suspect
path. To compensate for the effects of such transition difference on the
correlation between the suspect and reference path delays, the average of rise
and fall delays has been considered as the path delay. The rationale behind
the average delay is when rising and falling transitions are applied at the
inputs of both suspect and reference paths, all the gates in these paths also
experience both rising and falling transitions. Therefore, for paths in type–2
symmetric path pairs the path delay has been considered as the average of rise
and fall delays as shown in (4).

$\text{path\\_delay}=\frac{\text{rise\\_delay + fall\\_delay}}{2}$ (4)

The correlation between different delays of suspect path shown in Fig. 2(a)
and reference path shown in Fig. 2(b) of a type–1 symmetric path pair under
inter-die variation is shown in Fig. 4LABEL:sub@fig:type-1_dly_model. It can
be observed that the rise, fall and average of rise and fall delays of suspect
and reference paths are highly correlated under inter-die variation effects.
Therefore, either $rise\\_delay$ or $fall\\_delay$ an be considered as the
path delay for the paths in type–1 symmetric path pairs. The percentage
correlation coefficient between the delays of paths in type–1 symmetric path
pair is shown in Table 1.

Similarly, a type–2 symmetric path pair has been formed by considering the
path shown in Fig. 2(a) as suspect path and the path shown in Fig. 2(c) as
reference path. The correlation between the suspect and reference path delays
of the type–2 symmetric path pair for different delay models considered under
inter-die variations is shown in Fig. 4LABEL:sub@fig:type-2_dly_model. The
percentage correlation coefficient between the rise, fall, and the average of
both delays of the suspect and the reference paths is shown in Table 1. It is
observed that the correlation between rise delays of the suspect path and the
reference path is 98.712%. Similarly, the correlation between the fall delays
is 97.687%. Whereas, the correlation between the average rise and fall delays
of suspect and reference paths of a type–2 symmetric path pair is 99.997%.
Therefore, to maintain a high correlation, the average of rise and fall delays
as shown in (4), has been considered as the path delay for the paths in type–2
symmetric path pairs.

The effect of inter-die variation on the delays of paths of symmetric path
pairs with different path lengths has been shown in Fig.
5LABEL:sub@fig:different-path-lengths. We have considered the number of gates
in a path as the path length. The path pairs with lengths 9 and 12 are
extracted from c1908 and c2670 benchmark circuits respectively. The path pairs
with path lengths 15 and 18 are selected from the c7552 benchmark circuit. It
is observed that the delays are as expected for all the path lengths, thus
leading to the inference that the effect of inter-die variation is mitigated
irrespective of the length of symmetric paths considered. We can even observe
that the nominal delays of suspect and reference paths are not equal even
though they pass through the same type of gates. This is due to the difference
in fanout of each gate and the length of interconnects between the gates in
these paths.

We have analyzed the effect of fanout difference on the correlation between
the delays of the suspect and the reference paths shown in Fig. 2(a) and Fig.
2(b) respectively. The fanout difference (fod) is considered as the difference
between the total fanout of suspect and reference paths. We have connected
INVX1_RVT gate to the nets in the suspect and reference paths randomly to
create the fanout difference. For example, to create a fanout difference of 3,
we have connected 2 INVX1_RVT gates to the randomly chosen nets of the suspect
path and 5 INVX1_RVT gates to the nets of reference path randomly. The
correlation between path delays of suspect and reference paths under inter-die
variation for several fanout differences has been shown in Fig.
5LABEL:sub@fig:different-fanout-differences. It can be observed that the
fanout difference only affects the slope of the expected lines but does not
have any impact on the correlation between path delays under the effects of
inter-die variation. Table 2 presents the correlation between the delays of
symmetric paths under inter-die variation for different path lengths and
fanout differences. It can be observed that the percentage correlation
coefficient is greater than 99.9% in all the considered cases. Therefore, we
infer that the inter-die process variation effects on hardware Trojan
detection can be mitigated by selecting topologically symmetric paths,
irrespective of their type, length, and fanout differences.

(a)

(b)

Figure 4: Correlation between suspect path and reference path delays under
inter-die variations for different delay models considered
LABEL:sub@fig:type-1_dly_model for paths in type–1 symmetric path pair
LABEL:sub@fig:type-2_dly_model for paths in type–2 symmetric path pair

(a)

(b)

Figure 5: Effect of inter-die process variations on delays of suspect and
reference paths along the expected line LABEL:sub@fig:different-path-lengths
for different path lengths LABEL:sub@fig:different-fanout-differences for
different fanout differences

Let us consider Fig. 3, the nominal delays of suspect path and reference path
are represented by $P_{s,nom}$ and $P_{r,nom}$ respectively i.e. these are the
delays at nominal transistor threshold voltage $v_{th,nom}$. $P_{s,rs}$ and
$P_{r,rs}$ are the delays of suspect and reference paths respectively for a
random sample due to inter-die variation i.e. these are the delays at
transistor threshold voltage $v_{th,nom}+\Delta v_{inter}$. where $\Delta
v_{inter}$ is a random sample from inter-die variation distribution modeled
using (1), which will be same for all the transistors in the two paths as
explained in Section 3.3. The expected straight line equation can be
determined by using the nominal and random sample delay points as shown in
(5).

$y-P_{r,nom}=\frac{P_{r,rs}-P_{r,nom}}{P_{s,rs}-P_{s,nom}}(x-P_{s,nom})$ (5)

By rearranging the terms in (5) we get the equation of the expected straight
line as follows, where $\alpha=(P_{r,rs}-P_{r,nom})/(P_{s,rs}-P_{s,nom})$ and
$\beta=(P_{r,nom}-\alpha P_{s,nom})$.

$\alpha x-y+\beta=0$ (6)

Assuming a hardware Trojan gate has presumably been inserted in the suspect
path and it, in turn, induces some extra delay. The delays of suspect path
after Trojan insertion and reference path are represented by $P_{s}$ and
$P_{r}$, respectively. Due to HT-induced extra delay, the point
($P_{s},P_{r}$) deviates from the expected straight line. This deviation
causes the distance $d$ between the point ($P_{s},P_{r}$) and the expected
line. This distance $d$ has been used to calculate the detection metric ($DM$)
to detect hardware Trojan. The distance $d$ can be calculated as per (7).

$d=\frac{1}{\sqrt{1+\alpha^{2}}}\left(\left|\alpha
P_{s}-P_{r}+\beta\right|\right)$ (7)

The detection metric $DM$ is calculated as the normalized distance
Ramakrishna2018-VLSID2018  from the expected straight line as shown in (8).

$DM=\frac{d}{\sqrt{(P_{s,nom})^{2}+(P_{r,nom})^{2}}}$ (8)

Under the influence of process variations, the delays of the suspect and the
reference paths may deviate from their nominal values. These delays follow the
expected line under inter-die variation as the paths are topologically
symmetric. The intra-die variation effects cause the deviation of the delay
point away from the expected line as it affects transistors in the symmetric
paths differently depending on their physical location on the die. Thus,
ideally, under no process variations, the value of $DM$ should be zero. It can
be understood that even in the presence of inter-die variation also the $DM$
is zero as the delay points lie on the expected line. But, under intra-die
variation as the delay points deviate from the expected line, the $DM$ becomes
non-zero i.e. $DM>0$. Therefore, the computed detection metric $DM$ is
compared with a pre-defined threshold ($DT$) to separate Trojan inserted ICs
from Trojan free ICs. The detection threshold $DT$ can be obtained by
performing Monte-Carlo simulations with reliable process variation models. The
hardware Trojan detection problem can be formulated as

$\text{IC\ under\ test}=\begin{cases}\text{is Trojan free}&\text{if }DM<DT\\\
\text{has Trojan inserted}&\text{otherwise}\end{cases}$ (9)

Figure 6: Proposed Hardware Trojan Detection Methodology

##  4 Detection Methodology

In this section, we discuss our proposed methodology in detail. The proposed
methodology consists of two stages i.e (i) the Pre-fabrication stage and (ii)
the Post-fabrication stage. The complete flow of the proposed HT detection
methodology is shown in Fig. 6.

###  4.1 Pre-fabrication stage

We assume that the golden model of the design is available since we have
considered the threat model of HT insertion at untrusted foundry i.e. the HT
is assumed to be inserted after design sign-off while fabrication. The design
netlist has been analyzed to find vulnerable nets, which are considered to be
potential locations of HT insertion. We have considered low activity nets as
the vulnerable locations for HT insertion as explained in Section 3.2. The set
of vulnerable nets $\\{N_{v}\\}$ has been identified using the simulation of
the golden netlist of the design over a large number of random test vectors. A
symmetric path pair (SPP) consisting of a suspect path and a reference path is
selected for each vulnerable net in the design. The path selection algorithm
which is used to select suspect and reference paths is explained in Section 5.
A set of symmetric path pairs $\\{N\\}$ is formed by combining a suspect path
and its corresponding reference path for each net $n$ in $\\{N_{v}\\}$. The
nominal delays of suspect path and reference path of $i^{th}$ symmetric path
pair corresponding to $i^{th}$ vulnerable net in $\\{N_{v}\\}$ are represented
by $P_{s,nom}^{i}$ and $P_{r,nom}^{i}$ respectively. The detection metric
corresponding to $i^{th}$ pair $DM_{i}$ is calculated as the normalized
distance from expected straight line using (7) and (8). Monte-Carlo
simulations are performed using reliable process variation models provided by
the foundry to generate a set of Trojan-free IC instances. The metric $DM$ =
$\\{DM_{1},DM_{2},.....,DM_{N}\\}$ corresponding to all selected symmetric
path pairs of the design is calculated for all Trojan free IC instances. Using
this data a detection threshold is decided for each symmetric path pair. The
set $DT$ = $\\{DT_{1},DT_{2},.....,DT_{N}\\}$ contains these threshold values.
This $DT$ is used in the post-fabrication stage for HT detection.

###  4.2 Post-fabrication stage

The post-fabrication stage involves the measurement and analysis of delays of
the paths present in selected symmetric path pairs. The path delays of all
$2N$ paths in $N$ pairs are measured for each suspected IC. Techniques
presented inLi2008-HTD_delay_shadow_reg ; Tehranipoor2013-HTD_Clk_Sweeping
can be used to measure the delays of selected paths. The $DM$ of each pair is
calculated using (7) and (8). Each $DM_{i}$ is compared with pre-defined
detection threshold $DT_{i}$ in order to infer whether the IC under test is
Trojan free as shown in (10).

$\text{IC\ under\ test}=\begin{cases}\text{is\ Trojan\ free\ }\hskip
29.87547ptif\ DM_{i}<DT_{i}\\\ \hskip 112.38829pt\forall\ 1<i\leq N\\\
\text{has\ Trojan\ inserted\ }\ \ \ \ \ \ \ \ otherwise\end{cases}$ (10)

##  5 Path selection Procedure

The proposed path selection procedure and reference path creation technique
are described in this Section.

###  5.1 Path selection algorithm

The proposed path selection technique is presented in Algorithm 1. This
algorithm takes a set of vulnerable nets ${N_{v}}$ and the golden design
netlist as inputs and returns a topologically symmetric path pair (SPP)
consisting of a suspect path and its corresponding reference path for each
vulnerable net in the design. All sensitizable paths passing through the
vulnerable net $n_{i}$ are collected in set $S_{all\\_paths}^{i}$. We have
used Boolean satisfiability (SAT) based techniques to decide whether a path is
sensitizable MarquesFelipeS2005-SAT-Falepath-Detection ; Lu2008-SAT-based-PD-
ATPG ; Sauer2016-PHAETON-SAT . For the sake of clarity and simplicity,
wherever we refer to a path in the remainder of the paper, it is to be
considered as a sensitizable path. All the paths that have symmetric paths
(i.e. either type-1 or type-2) are collected in set $S_{suspect}^{i}$. The
nets which have at least one symmetric path for at least one path out of all
paths passing through them are collected in set $N_{covered}$ and called
covered nets. If there are no symmetric paths for at least one path in
$S_{all\\_paths}^{i}$ then we call such nets as uncovered nets. We need to
create a symmetric path to be used as a reference path for each of such nets.
The procedure as explained in Algorithm 3, is used for reference path
creation. All possible suspect paths through the net $n_{i}$ are collected in
set $S_{suspect}^{i}$ and all the paths symmetric to the path
$P_{suspect,j}^{i}$ in $S_{suspect}^{i}$ are collected in
$S_{symmetric,j}^{i}$.

After finding out possible suspect paths and corresponding symmetric paths for
each vulnerable net, the final layout of the netlist is prepared. The physical
location information of each gate is collected from the layout of the netlist
and is used for selecting the nearest symmetric path pair to exploit the
spatial correlation component of intra-die variation. We compute the rank of a
symmetric path pair as the average of distances between similar gates in a
symmetric path pair. The procedure for computing the rank of a symmetric path
pair is presented in Algorithm 2. The suspect path and corresponding symmetric
path are represented by $P_{suspect,j}^{i}$ and $P_{symmetric,k}^{i}$
respectively. The gates in paths $P_{suspect,j}^{i}$ and $P_{symmetric,k}^{i}$
are collected in sets $G_{susp}$ and $G_{sym}$, respectively. Assume $g_{l}$
and $g_{m}$ are similar type gates present in $G_{susp}$ and $G_{sym}$ and
their locations on the layout of the design are represented by ($x_{l}$,
$y_{l}$) and ($x_{m}$, $y_{m}$), respectively. The Euclidean distance
$dist_{q}$ between these two gates $g_{l}$ and $g_{m}$ is calculated as shown
in line 8 of Algorithm 2. The rank of the symmetric path pair is computed by
taking the average of the distances $dist_{q}$ for all the gates in $G_{susp}$
as shown in line 10 of algorithm 2. Here, $|G_{susp}|$ represents the
cardinality of the set $G_{susp}$ which is nothing but the number of gates in
the suspect path. An example illustrating the Algorithm 2 is presented in Fig.
7. A pair that has nearest symmetric paths i.e with lowest rank is selected
and a symmetric path pair $SymmetricPathPair_{i}$ corresponding to net $n_{i}$
is formed as $(p_{susp}^{i},p_{ref}^{i})$.

Input : Netlist, $N_{v}$ = set of vulnerable nets

Output : Symmetric path pairs

1

2foreach  _net $n_{i}$ in $N_{v}$_ do

3

4 $S_{all\\_paths}^{i}$ = set of all sensitizable paths passing through the
net $n_{i}$

5 $S_{suspect}^{i}$ = $S_{all\\_paths}^{i}$

6 foreach  _path $P_{suspect,j}^{i}$ in $S_{all\\_paths}^{i}$_ do

7 $S_{symmetric,j}^{i}$ = set of paths that are symmetric (type-1 or type-2)
to $P_{suspect,j}^{i}$ and not passing through net $n_{i}$

8 if  _$|S_{symmetric,j}^{i}|=0$_ then

/* If there are no symmetric paths for path $P_{suspect,j}^{i}$ then drop it
from the suspect path list $S_{suspect}^{i}$ */

9 $S_{suspect}^{i}$ = $S_{suspect}^{i}$ \- $P_{suspect,j}^{i}$

10

11 end if

12

13 end foreach

14

15 if  _$|S_{suspect}^{i}|=0$_ then

16

/* If there are no symmetric paths for at least one path in
$S_{all\\_paths}^{i}$ then create a symmetric path */

17 refpathgen($n_{i},S_{all\\_paths}^{i}$)

18 else

19 Add net $n_{i}$ to the set of covered nets $N_{covered}$

20 end if

21

22 end foreach

23Perform physical synthesis of (modified) netlist for generating layout of
the design

24 Prepare the physical location information of each gate in the netlist

25 foreach  _net $n_{i}$ in $N_{covered}$_ do

26 $rank\\_initial=\infty$

27 foreach  _path $P_{suspect,j}^{i}$ in $S_{suspect}^{i}$_ do

28 foreach  _path $P_{symmetric,k}^{i}$ in $S_{symmetric,j}^{i}$_ do

29 Compute the rank of the path pair $P_{suspect,j}^{i}$ and
$P_{symmetric,k}^{i}$ which is dependent on the distance between the two
paths.

30 $rank_{jk}$ = rank($P_{suspect,j}^{i},P_{symmetric,k}^{i}$)

31 if  _$rank_{jk} <rank\\_initial$ _ then

/* selects the path pair with lowest rank i.e the nearest symmetric path pair
*/

32 $P_{susp}^{i}=P_{suspect,j}^{i}$ and $P_{ref}^{i}=P_{symmetric,k}^{i}$

33 $rank\\_initial=rank_{jk}$

34

35 end if

36

37 end foreach

38

39 end foreach

40 $SymmetricPathPair_{i}\leftarrow(P_{susp}^{i},P_{ref}^{i})$

41

42 end foreach

Algorithm 1 Path selection algorithm

Input : A pair of paths $P_{suspect,j}^{i}$, $P_{symmetric,k}^{i}$

Output : Rank of the path pair

1 $G_{susp}$ = Set of all gates in path $P_{suspect,j}^{i}$

2 $G_{sym}$ = Set of all gates in path $P_{symmetric,k}^{i}$

3 foreach  _gate $g_{l}$ in $G_{susp}$ _ do

4 foreach  _gate $g_{m}$ in $G_{sym}$ _ do

5 if  _$g_{l}$ =$g_{m}$_ then

/* If both gates are of same type */

6 location of $g_{l}$ on layout is ($x_{l},y_{l}$)

7 location of $g_{m}$ on layout is ($x_{m},y_{m}$)

8 $dist_{q}=\sqrt{(x_{l}-x_{m})^{2}+(y_{l}-y_{m})^{2}}$

9 end if

10 $rank=\frac{\sum_{q=1}^{|G_{susp}|}dist_{q}}{|G_{susp}|}$

11

12 end foreach

13

14 end foreach

15return $rank$

Algorithm 2 Calculation of rank of a path pair – rank() Figure 7: Example for
ranking symmetric path pairs according to the locations of gates in the layout
(a) suspect path (b) symmetric path with rank = 3 i.e. $(2+2+5)/3$ (c)
symmetric path with rank = 21 i.e. $(50+5+10)/3$

###  5.2 Reference path creation

Figure 8: Generating symmetric path (a) selected suspect path (b) a non-
critical path (c) generated symmetric path to cover the vulnerable net

Input : Uncovered vulnerable net $n_{i}$, $S_{all\\_paths}^{i}$

Output : Symmetric path pair through net $n_{i}$

1

2$p_{short}$ = a sensitizable path with minimum delay in $S_{all\\_paths}^{i}$

3 $S_{sub}$ = a set non-critical paths $p_{sub}$ that have set of all gates in
each path as subset of gates in the path $p_{short}$ i.e.
$\textit{gatesof}(p_{sub})\subset\textit{gatesof}(p_{short})$

4 if  _$|S_{sub}|=0$_ then

5 $S_{all\\_paths}^{i}=S_{all\\_paths}^{i}-p_{short}$ and goto to step: 1

6

7 end if

8foreach  _$p_{sub}$ in $S_{sub}$ _ do

9 $extragates=\textit{gatesof}(p_{short})-\textit{gatesof}(p_{sub})$

10 Compute area overhead i.e. area of extra gates

11

12 end foreach

13Select the path $p_{sub}$ from $S_{sub}$ with minimum area overhead

14 $p_{ref}$ = path $p_{sub}$ with $extragates$ inserted at its input net

15 Connect off-path inputs of $extragates$ to non-controlling values

16 Check the functionality after extra gates insertion

17 Check the timing of all paths through the input net of $p_{ref}$

18 if  _functionality and timing are satisfied_ then

19 $P_{susp}^{i}=p_{short}$ and $P_{ref}^{i}=p_{ref}$

20 else

21 $S_{sub}=S_{sub}-p_{sub}$ and $goto$ step: 10

22 end if

23

24return $SymmetricPathPair_{i}\leftarrow(P_{susp}^{i},P_{ref}^{i})$

Algorithm 3 Reference path creation – refpathgen()

There may be some vulnerable nets for which a symmetric path pair (SPP) may
not exist intrinsically in the design. We call such nets uncovered nets. To
cover such nets, we create a symmetric path to be used as a reference path by
adding few extra logic gates to the existing non-critical paths of the design
as shown in Fig. 8. Algorithm 3 presents the procedure for creating the
reference path to cover an uncovered net $n_{i}$. We chose the shortest path
through the uncovered net $p_{short}$ as the shorter paths experience less
intra-die variation effects as they consist less number of gates. The non-
critical paths which have gates that are a subset of gates of $p_{short}$ are
collected in $S_{sub}$. The path $p_{sub}$ in $S_{sub}$ with minimum area
overhead is selected and the extra gates are found as
$\textit{gatesof}(p_{short})-\textit{gatesof}(p_{sub})$. These extra gates are
inserted at the input net of $p_{sub}$, thus forming a type-1 or type-2
symmetric path to be used as a reference path $p_{ref}$. The off-path inputs
of extra inserted gates must be connected to non-controlling values. The
functionality of the design should not change due to the addition of extra
gates. Moreover, the timing of all paths passing through the input net of
$p_{ref}$ must not violate any timing constraints. The designer has to ensure
that all paths through the input net of the created new path must be non-
critical even after the addition of extra gates and functionality must remain
the same. Moreover, the created paths will be non-critical but are not
redundant as they are part of the design. If the functionality and timing are
satisfied $p_{short}$ and $p_{ref}$ are assigned to suspect $p_{susp}^{i}$ and
reference $p_{ref}^{i}$ paths respectively. A symmetric path pair for an
uncovered net $n_{i}$ is returned as
$SymmetricPathPair_{i}\leftarrow(p_{susp}^{i},p_{ref}^{i})$.

##  6 Results

Simulations have been performed on ISCAS-85 benchmark
circuitsiscas85_benchmarks  to evaluate the proposed methodology. We carried
out the experiments on a computer with an Intel Core<EMAIL_ADDRESS>GHz processor
and 8GB memory and the flow and proposed algorithms were implemented in python
language. The benchmarks have been synthesized using Synopsys generic
(SAED_EDK32nm) library. For performing SPICE level simulations 32nm CMOS
Predictive Technology Models (PTM)ptm-models  are considered. The netlists are
simulated over a large number of random test vectors (i.e. $1\times 10^{6}$)
and nets with switching activity less than a predefined threshold ($1\times
10^{-3}$) are considered as vulnerable nets as explained in Section 3.2.
Static timing analysis (STA) is performed using Synopsys’s PrimeTime to
generate path data. We used SAT-based techniques to isolate sensitizable paths
out of all possible paths in the design and the SAT solver used was
MiniSat-2.2. Symmetric paths are created to cover the uncovered nets as
explained in Section 5.2. Physical layout synthesis of design is carried out
using Synopsys IC Compiler for generating the layout. This layout has been
partitioned into $16\times 16$ grids to model spatially correlated intra-die
variations. We have assumed that all transistors in a gate and all the gates
in a grid experience the same within-die variations. Symmetric path pairs are
selected using path selection procedure explained in Section 5. Selected paths
are extracted in SPICE netlist format from the layout of the design. Process
variation on threshold voltage ($V_{th}$) is modeled as explained in Section
3.3. The $3\sigma$ values for inter-die and intra-die variation are considered
as $20\%$ and $15\%$ respectively Kuhn2010-32nm-pv1 ; Bonfiglio2013-32nm-pv2 ;
Damrongplasit2014-32nm-pv4  . As the layout has been partitioned into
$16\times 16$ grids, $256$ correlated multivariate random variables are
generated to model the spatial variation. The spatial correlation is
considered as 0.8 to 0.3 according to the distance between the grids. Spatial
correlation decreases with an increase in distance between grids. 500 IC
instances without HT and 500 IC instances with Trojan shown in Fig. 1 are
generated using the $V_{th}$ PV model (1) and (2). HSPICE is used to perform
SPICE level simulations using the generated $V_{th}$ profiles.

Table 3: Run time of the proposed path selection algorithm for ISCAS-85 benchmark circuits (in minutes) Circuit | Run time
---|---
c432 | 68
c499 | 12
c880 | 13
c1355 | 27
c1908 | 6
c2670 | 14
c3540 | 765
c5315 | 143
c7552 | 285

(a)

(b)

(c)

(d)

(e)

(f)

Figure 9: Effect of process variation and hardware Trojan on symmetric path pair of (a) c432 (b) c1908 (c) c5315 and corresponding detection metric of (d) c432 (e) c1908 (f) c5315. Table 4: Simulation results on ISCAS-85 benchmarks Circuit | c432 | c499 | c880 | c1355 | c1908 | c2670 | c3540 | c5315 | c7552
---|---|---|---|---|---|---|---|---|---
Total gates | 84 | 159 | 179 | 188 | 119 | 240 | 377 | 556 | 659
Total nets | 120 | 200 | 238 | 229 | 398 | 152 | 427 | 734 | 866
Sensitizable paths (%) | 44 | 64 | 98 | 71 | 94 | 99 | 49 | 83 | 77
Vulnerable nets | 9 | 42 | 17 | 40 | 16 | 27 | 76 | 8 | 9
Uncovered nets | 2 | 0 | 3 | 0 | 6 | 9 | 7 | 3 | 4
Extra gates added | 4 | 0 | 11 | 0 | 22 | 14 | 15 | 9 | 5
Symmetric path pairs | 13 | 32 | 32 | 32 | 27 | 25 | 81 | 10 | 12
Type-1 pairs | 2 | 30 | 6 | 32 | 5 | 12 | 46 | 3 | 2
Type-2 pairs | 11 | 2 | 26 | 0 | 22 | 13 | 35 | 7 | 10
Net coverage (%) | 49.1 | 48.5 | 32.7 | 50.6 | 11.3 | 48.6 | 55.5 | 3.8 | 7.6
Area overhead (%) | 3.6 | 0 | 4.7 | 0 | 14.2 | 4.5 | 3.1 | 1.2 | 0.6
TPR (%) | 100 | 100 | 100 | 100 | 99 | 100 | 100 | 100 | 100
FPR (%) | 3 | 0 | 0 | 0 | 3 | 0 | 0 | 3 | 0

The summary of our experimental results is presented in Table 4. Rows 2 and 3
present the number of gates and nets present in each benchmark circuit
considered. The percentage of sensitizable paths out of total possible paths
in the design netlist is shown in row 4. We have considered only sensitizable
paths for selecting symmetric path pairs using the proposed path selection
algorithm. Total vulnerable nets i.e. the nets with switching activity less
than the predefined threshold are presented in row 5. The uncovered nets i.e.
the vulnerable nets which do not have symmetric paths intrinsically in the
design are presented in row 6. We have created a symmetric path pair for each
uncovered net by inserting few additional gates. The number of extra gates
added to the design to create symmetric path pairs for all uncovered nets are
presented in row 7. The number of symmetric path pairs (SPPs) selected to
cover all the vulnerable nets is presented in row 8. We have observed that few
suspect paths pass through more than one vulnerable net. Thus, the number of
selected SPPs is lower than the number of vulnerable nets in c499, c1355,
c2670. As we selected an SPP for every fanout branch of each vulnerable net,
the number of selected SPPs is higher than the number of vulnerable nets in
c432, c880, c1908, c3540, c5315, c7552. Rows 9 and 10 represent the type-1 and
type-2 symmetric path pairs out of the total selected path pairs. Row 11
represents the ratio of nets covered by the selected SPPs. The net coverage
ratio of c1355 is 50.6% with no area overhead, whereas it is 11.3% even with
14.2% area overhead for c1908. We have observed that the net coverage ratio is
higher if the majority of the paths in selected SPPs are mutually disjoint
i.e. they do not share many common segments of other paths, otherwise the net
coverage ratio is lower. The area overhead, due to extra gates added to the
design for creating SPPs to cover uncovered nets, is presented in row 12.
Finally, the true positive rate (TPR) and false-positive rate (FPR) are shown
in rows 13 and 14 respectively.

The runtime of the proposed path selection procedure for different benchmark
circuits is presented in Table 3. Our automated flow considers a set of
vulnerable nets and design netlist as inputs and reports the set of selected
symmetric path pairs as output. Circuit c3540 has the longer run time of 765
minutes and c1908 has the shorter run time of 6 minutes. We observe that both
of these circuits have a moderate number of gates and nets in comparison to
the remaining circuits (i.e. neither c3540 has the highest number of gates and
nets nor c1908 has the lowest). Therefore, it can be inferred that the runtime
is not dependent on the number of gates and nets present in the design. We
observed that it is dependent on the total number of possible paths and the
number of sensitizable paths out of the total number of possible paths in the
design.

###  6.1 HT detection analysis

The variation in delays of suspect and reference paths of a symmetric path
pair (SPP) of several benchmark circuits are shown in Fig. 9. The path delays
vary along the expected straight line passing through the point of nominal
delays despite inter-die variations, However, due to intra-die variations they
tend to deviate away from the straight line. It is observed that the points
representing the delays of SPPs in HT inserted ICs are away from the expected
straight line. The graphs illustrating the effect of variation and HT on a
selected SPP of some benchmarks are presented in Fig. 9LABEL:sub@fig:c432-pv,
9LABEL:sub@fig:c1908-pv and 9LABEL:sub@fig:c5315-pv. Detection metric ($DM$)
for SPPs of each IC under test is calculated as per (8). The $DM$ of trojan
free and with trojan ICs are shown in Fig. 9LABEL:sub@fig:c432-dm,
9LABEL:sub@fig:c1908-dm and 9LABEL:sub@fig:c5315-dm. The detection threshold
$DT$ has been decided in a pessimistic way by allowing a false positive rate
of $3\%$. The dashed horizontal lines in Fig. 9LABEL:sub@fig:c432-dm,
9LABEL:sub@fig:c1908-dm and 9LABEL:sub@fig:c5315-dm represent the selected
$DT$ for the considered SPP of each benchmark. It can be observed that the
$DM$ of few HT free ICs, is above the threshold line in Figs.
9LABEL:sub@fig:c432-dm, 9LABEL:sub@fig:c1908-dm and 9LABEL:sub@fig:c5315-dm.
Nevertheless, the $DM$ of few Trojan inserted ICs is below the threshold line
only in Fig. 9LABEL:sub@fig:c1908-dm. True positive rate (TPR) is defined as
the ratio of number of ICs that are detected as HT inserted out of the total
number of ICs with HT inserted. False positive rate (FPR) is defined as the
ratio of number of ICs that are detected as HT inserted but which in fact are
HT free out of total number of ICs without HT.

The TPR and FPR shown in Table 4 are for the worst-case symmetric path pair
i.e the pair with lower TPR and/or higher FPR out of all selected SPPs for a
benchmark under consideration. The TPR and FPR for c432 and c5315 benchmarks
are 100% and 3%. Though the proposed method correctly detects all the Trojan
inserted ICs, it falsely classifies a few Trojan free ICs as Trojan inserted
ones. It is because the paths in these SPPs are not close enough to each
other. The TPR and FPR of c1908 are 99% and 3%. Even with an FPR of 3%, the
proposed methodology cannot detect all the trojan inserted ICs and few Trojan
affected ICs are identified as Trojan free. The SPPs of c432 and c1908 are
intrinsic to the design, whereas the SPP of the c5315 circuit is not intrinsic
but it is a created SPP to cover an uncovered net. Even though the SPP
contains the shortest suspect path the created reference path is not closer to
the suspect path. This leads to higher FPR in c5315. One way to improve the
detection accuracy is to place the suspect and reference paths closer to each
other manually while preparing the layout. However, this would incur extra
area and routing overhead and requires additional design efforts.

###  6.2 Overhead analysis

The area overhead of the proposed methodology is due to the additional gates
used to create symmetric path pairs for covering uncovered nets. The benchmark
circuit c1908 has the highest area overhead of 14.2%. Whereas, the area
overhead of c499 and c1355 circuits is 0% as all the vulnerable nets are
covered by the symmetric path pairs that exist in the design intrinsically. It
is observed that the area overhead is dependent on the number of extra gates
required to cover the uncovered nets. For circuits c1908 and c2670, even
though the number of uncovered nets in c1908 is less than that of c2670, the
number of extra gates required for c1908 is higher than that of c2670.
Therefore, we conclude that the area overhead of the proposed method is not
only dependent on the number of uncovered nets but also depends on the circuit
structure.

###  6.3 Security analysis

As the proposed hardware Trojan detection (HT) method depends on the
difference in path delays of two symmetric paths, it may be argued that this
method may fail to detect hardware Trojans if the same Trojan gate is inserted
in both the symmetric paths considered. To be able to do so, an attacker must
be aware of the detection method employed which is highly unlikely. Even if
the attacker knows the method, he/she has to double the number of alterations
to the design to bypass the proposed method. Even if the attacker possesses
the knowledge that a delay-based scheme is being used to detect HT, it is
highly unlikely that he can determine the exact paths under consideration.
Because there would be many paths available to pick a suspect path and for
each of such selected suspect paths there would be many possible reference
paths. The probability of identifying the selected path pairs for ISACS-85
circuits is shown in table 5.

Table 5: Probability of an attacker identifying the selected path pair in order to bypass the proposed method Circuit | Probability
---|---
c432 | $3.2895\times 10^{-7}$
c499 | $1.0377\times 10^{-6}$
c880 | $4.6964\times 10^{-6}$
c1355 | $1.2752\times 10^{-7}$
c1908 | $5.3892\times 10^{-6}$
c2670 | $2.7472\times 10^{-6}$
c3540 | $1.5922\times 10^{-7}$
c5315 | $1.8503\times 10^{-7}$
c7552 | $1.0382\times 10^{-6}$

The procedure of selecting a reference path arises only during detecting
Trojan. To make the advantage of self-referencing, more clear, we compute the
probability of selection of a reference path corresponding to the suspect path
by the attacker while hiding the Trojan.

Consider a vulnerable net of the design. Assume there are $m$ paths $P_{s1}$,
$P_{s2}$,…,$P_{sm}$ passing through this net. Suppose each one of these $m$
paths have corresponding symmetric paths from which a reference path is chosen
i.e path $P_{si}$ has $k_{i}$ symmetric paths. The probability of the attacker
finding the correct symmetric path pair is P{ selecting the correct pair} =
$\frac{1}{\sum\limits_{i=1}^{m}k_{i}}$. If there are $N$ nets in the design
then P{ Attacker bypassing the method} =
$\frac{1}{N\sum\limits_{i=1}^{m}k_{i}}$.

##  7 Conclusion

In the present work, we have considered a threat model of hardware Trojan
insertion during fabrication at untrusted foundries. We have presented a novel
methodology for hardware Trojan (HT) detection by analyzing the delays of
topologically symmetric paths. Further, we have proposed a procedure to select
paths that mitigates the effect of inter-die variation and minimizes the
intra-die variation effects. We have selected topologically symmetric paths to
mitigate the effects of inter-die variation and selected physically closer
paths to exploit the spatial correlation for reducing the impact of intra-die
variation on hardware Trojan detection accuracy. Moreover, this method uses
the concept of self-referencing, which eliminates the requirement of golden
reference ICs. We have proposed and validated a procedure to create symmetric
paths to cover all vulnerable nets in the design. Simulation results establish
that the proposed method is able to detect HTs, which are as small as one
gate. In this work, we have used simulation results to decide the detection
threshold. Further work could use on-chip process variation monitors to
estimate the detection threshold of each suspect IC. We are currently working
on locating the trojan.

###### Acknowledgements.

This work is partly supported by the SMDP-C2SD project, sponsored by the
Ministry of Electronics & Information of Technology, Government of INDIA.

## References

  * (1) Predictive Technology Model (2017).  URL http://ptm.asu.edu/
  * (2) Adee, S.: The Hunt For The Kill Switch.  IEEE Spectrum 45(5), 34–39 (2008).  DOI 10.1109/MSPEC.2008.4505310
  * (3) Agrawal, D., Baktir, S., Karakoyunlu, D., Rohatgi, P., Sunar, B.: Trojan Detection using IC Fingerprinting.  In: Proceedings of IEEE Symposium on Security and Privacy, pp. 296–310 (2007).  DOI 10.1109/SP.2007.36
  * (4) Bao, C., Forte, D., Srivastava, A.: Temperature Tracking : Towards Robust Run-time Detection of Hardware Trojans.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 34(10), 1577–1585 (2015).  DOI 10.1109/TCAD.2015.2424929
  * (5) Bao, C., Forte, D., Srivastava, A.: On Reverse Engineering-Based Hardware Trojan Detection.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 35(1), 49–57 (2016).  DOI 10.1109/TCAD.2015.2488495
  * (6) Bonfiglio, V., Iannaccone, G.: Sensitivity-based investigation of threshold voltage variability in 32-nm flash memory cells and MOSFETs.  Solid-State Electronics 84(Supplement C), 127–131 (2013).  DOI 10.1016/j.sse.2013.02.029
  * (7) Brglez, F. and Fujiwara, H.: A Neutral Netlist of 10 Combinational Benchmark Circuits and a Target Translator in Fortran.  In: Proceedings of IEEE Int’l Symposium Circuits and Systems (ISCAS 85), pp. 677–692 (1985)
  * (8) Cha, B., Gupta, S.K.: Trojan Detection via Delay Measurements: A New Approach to Select Paths and Vectors to Maximize Effectiveness and Minimize Cost.  In: Proceedings of Design, Automation Test in Europe Conference Exhibition (DATE), pp. 1265–1270 (2013).  DOI 10.7873/DATE.2013.262
  * (9) Chen, X., Wang, L., Wang, Y., Liu, Y., Yang, H.: A General Framework for Hardware Trojan Detection in Digital Circuits by Statistical Learning Algorithms.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 36(10), 1633–1646 (2017).  DOI 10.1109/TCAD.2016.2638442
  * (10) Damrongplasit, N.: Study of Variability in Advanced Transistor Technologies.  Ph.D. thesis, University of California, Berkeley (2015)
  * (11) Deyati, S., Muldrey, B.J., Chatterjee, A.: Trojan Detection in Digital Systems Using Current Sensing of Pulse Propagation in Logic Gates.  In: Proceedings of 17th International Symposium on Quality Electronic Design (ISQED), pp. 350–355 (2016).  DOI 10.1109/ISQED.2016.7479226
  * (12) Dong, C., Xu, Y., Liu, X., Zhang, F., He, G., Chen, Y.: Hardware Trojans in Chips: A Survey for Detection and Prevention.  Sensors 20(18), 5165 (2020).  DOI 10.3390/s20185165.  URL https://www.mdpi.com/1424-8220/20/18/5165
  * (13) Du, D., Narasimhan, S., Chakraborty, R.S., Bhunia, S.: Self-referencing: A Scalable Side-channel Approach for Hardware Trojan Detection.  In: Proceedings of the 12th International Conference on Cryptographic Hardware and Embedded Systems, vol. CHES’10, pp. 173–187 (2010).  DOI 10.1007/978-3-642-15031-9_12
  * (14) Esirci, F.N., Bayrakci, A.A.: Hardware Trojan detection based on correlated path delays in defiance of variations with spatial correlations.  In: Proceedings of Design, Automation Test in Europe Conference Exhibition (DATE), pp. 163–168 (2017).  DOI 10.23919/DATE.2017.7926976
  * (15) Exurville, I., Zussa, L., Rigaud, J.b., Robisson, B.: Resilient Hardware Trojans Detection based on Path Delay Measurements.  In: Proceedings of IEEE International Symposium on Hardware Oriented Security and Trust (HOST), pp. 151–156 (2015)
  * (16) Ghobad, Z., Morteza, S.Z.: Latch-Based Structure: A High Resolution and Self-Reference Technique for Hardware Trojan Detection.  IEEE Transactions on Computers 66(1), 100–113 (2017).  DOI 10.1109/TC.2016.2576444
  * (17) Hicks, M., Finnicum, M., King, S.T., Martin, M.M.K., Smith, J.M.: Overcoming an Untrusted Computing Base: Detecting and Removing Malicious Hardware Automatically.  In: Proceedings - IEEE Symposium on Security and Privacy, pp. 159–172 (2010).  DOI 10.1109/SP.2010.18
  * (18) Hongliang, C., Sapatnekar, S.S.: Statistical Timing Analysis Considering Spatial Correlations Using a Single PERT-like Traversal.  In: Proceedings of IEEE International Conference on Computer Aided Design, pp. 621–625 (2003).  DOI 10.1109/ICCAD.2003.159746
  * (19) Ismari, D., Plusquellic, J., Lamech, C., Bhunia, S., Saqib, F.: On Detecting Delay Anomalies Introduced by Hardware Trojans.  In: Proceedings of IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pp. 1–7 (2016).  DOI 10.1145/2966986.2967061
  * (20) Jin, Y., Makris, Y.: Hardware Trojan Detection Using Path Delay Fingerprint.  In: Proceedings of IEEE International Workshop on Hardware-Oriented Security and Trust, pp. 51–57 (2008).  DOI 10.1109/HST.2008.4559049
  * (21) K. Xiao, Zhang, X., Tehranipoor, M.: A Clock Sweeping Technique for Detecting Hardware Trojans Impacting Circuits Delay.  IEEE Design & Test 30(2), 26–34 (2013).  DOI 10.1109/MDAT.2013.2249555
  * (22) Kuhn, K.J.: CMOS Transistor Scaling Past 32nm and Implications on Variation.  In: Proceedings of IEEE/SEMI Advanced Semiconductor Manufacturing Conference (ASMC), pp. 241–246 (2010).  DOI 10.1109/ASMC.2010.5551461
  * (23) Lamech, C., Plusquellic, J.: Trojan Detection based on Delay Variations Measured using a High-Precision, Low-Overhead Embedded Test Structure.  In: proceedings of IEEE International Symposium on Hardware-Oriented Security and Trust (HOST), pp. 75–82 (2012).  DOI 10.1109/HST.2012.6224324
  * (24) Lesperance, N., Kulkarni, S., Cheng, K.T.T.: Hardware Trojan Detection Using Exhaustive Testing of k-bit Subspaces.  In: Proceedings of 20th Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 755–760 (2015)
  * (25) Li, H., Liu, Q., Zhang, J., Lyu, Y.: A Survey of Hardware Trojan Detection, Diagnosis and Prevention.  In: Proceedings of the 14th International Conference on Computer-Aided Design and Computer Graphics (CAD/Graphics), pp. 173–180 (2015).  DOI 10.1109/CADGRAPHICS.2015.41
  * (26) Li, J., Lach, J.: At-Speed Delay Characterization for IC Authentication and Trojan Horse Detection.  In: Proceedings of IEEE International Workshop on Hardware-Oriented Security and Trust, HOST, pp. 8–14 (2008).  DOI 10.1109/HST.2008.4559038
  * (27) Liu, F.: A general framework for spatial correlation modeling in VLSI design.  In: Proceedings of the 44th Annual Design Automation Conference, pp. 817–822 (2007).  DOI 10.1109/DAC.2007.375277
  * (28) Liu, Y., Huang, K., Makris, Y.: Hardware Trojan Detection through Golden Chip-Free Statistical Side-Channel Fingerprinting.  In: Proceedings of the The 51st Annual Design Automation Conference on Design Automation Conference - DAC ’14, pp. 155:1—-155:6 (2014).  DOI 10.1145/2593069.2593147
  * (29) Lu, S.Y., Hsieh, M.T., Liou, J.J.: An efficient SAT-based path delay fault ATPG with an unified sensitization model.  In: Proceedings - International Test Conference, pp. 1–7 (2008).  DOI 10.1109/TEST.2007.4437589
  * (30) Malik, S.: Detecting hardware trojans: a tale of two techniques.  pp. 6–6. Institute of Electrical and Electronics Engineers (IEEE) (2016).  DOI 10.1109/fmcad.2015.7542244
  * (31) Marques, F.S., Ribas, R.P., Sapatnekar, S., Reis, A.I.: A New Approach to the Use of Satisfiability in False Path Detection.  In: Proceedings of the 15th ACM Great Lakes Symposium on VLSI, pp. 308–311 (2005)
  * (32) Rai, D., Lach, J.: Performance of Delay-Based Trojan Detection Techniques under Parameter Variations.  In: Proceedings of IEEE International Workshop on Hardware-Oriented Security and Trust (HOST), pp. 58–65 (2009).  DOI 10.1109/HST.2009.5224966
  * (33) Salmani, H., Tehranipoor, M.: Vulnerability Analysis of a Circuit Layout to Hardware Trojan Insertion.  IEEE Transactions on Information Forensics and Security 11(6), 1214–1225 (2016).  DOI 10.1109/TIFS.2016.2520910
  * (34) Salmani, H., Tehranipoor, M.M., Plusquellic, J.: New Design Strategy for Improving Hardware Trojan Detection and Reducing Trojan Activation Time.  In: Proceedings of IEEE International Workshop on Hardware-Oriented Security and Trust, HOST ’09, pp. 66–73 (2009).  DOI 10.1109/HST.2009.5224968
  * (35) Sauer, M., Becker, B., Polian, I.: PHAETON: A SAT-Based Framework for Timing-Aware Path Sensitization.  IEEE Transactions on Computers 65(6), 1869–1881 (2016).  DOI 10.1109/TC.2015.2458869
  * (36) Shang, N., Wang, A., Ding, Y., Gai, K., Zhu, L., Zhang, G.: A machine learning based golden-free detection method for command-activated hardware Trojan.  Information Sciences 540, 292–307 (2020).  DOI 10.1016/j.ins.2020.05.053
  * (37) Skorobogatov, S., Woods, C.: Breakthrough Silicon Scanning Discovers Backdoor in Military Chip.  In: Proceedings of the 14th International Conference on Cryptographic Hardware and Embedded Systems, pp. 23–40 (2012)
  * (38) Su, T., Li, S., Tang, Y., Chen, J.: Part I: Evaluation for Hardware Trojan Detection Based on Electromagnetic Radiation.  Journal of Electronic Testing pp. 1–16 (2020).  DOI 10.1007/s10836-020-05905-1.  URL http://link.springer.com/10.1007/s10836-020-05905-1
  * (39) Tehranipoor, M., Koushanfar, F.: A Survey of Hardware Trojan Taxonomy and Detection.  IEEE Design and Test of Computers 27(1), 10–25 (2010).  DOI 10.1109/MDT.2010.7
  * (40) Vaikuntapu, R., Bhargava, L., Sahula, V.: Novel Variability Aware Path Selection for Self-Referencing Based Hardware Trojan Detection.  In: Proccedings of 31st International Conference on VLSI Design and 17th International Conference on Embedded Systems (VLSID), pp. 1–6 (2018)
  * (41) Voyiatzis, A.G., Stefanidis, K.G., Kitsos, P.: Efficient Triggering of Trojan Hardware Logic.  In: proceeding of 19th IEEE International Symposium on Design and Diagnostics of Electronic Circuits Systems (DDECS), pp. 200–205 (2016)
  * (42) Yoshimizu, N.: Hardware Trojan Detection By Symmetry Breaking In Path Delays.  In: Proceedings of IEEE International Symposium on Hardware-Oriented Security and Trust (HOST), pp. 107–111 (2014)
  * (43) Zhang, J., Yuan, F., Wei, L., Liu, Y., Xu, Q.: VeriTrust: Verification for Hardware Trust.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 34(7), 1148–1161 (2015).  DOI 10.1109/TCAD.2015.2422836
  * (44) Zhang, Y., Quan, H., Li, X., Chen, K.: Golden-Free Processor Hardware Trojan Detection Using Bit Power Consistency Analysis.  Journal of Electronic Testing: Theory and Applications (JETTA) 34(3), 305–312 (2018).  DOI 10.1007/s10836-018-5715-z
  * (45) Zheng, Y., Yang, S., Bhunia, S.: SeMIA: Self-Similarity based IC Integrity Analysis.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 35(1), 37–48 (2016).  DOI 10.1109/TCAD.2015.2449231
  * (46) Zou, M., Cui, X., Shi, L., Wu, K.J.: Potential Trigger Detection for Hardware Trojans.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems PP(99), 1–1 (2018).  DOI 10.1109/TCAD.2017.2753201


# Low-complexity CNNs for Acoustic scene classification

###### Abstract

This paper presents a low-complexity framework for acoustic scene
classification (ASC). Most of the frameworks designed for ASC use
convolutional neural networks (CNNs) due to their learning ability and
improved performance compared to hand-engineered features. However, CNNs are
resource hungry due to their large size and high computational complexity.
Therefore, CNNs are difficult to deploy on resource constrained devices. This
paper addresses the problem of reducing the computational complexity and
memory requirement in CNNs. We propose a low-complexity CNN architecture, and
apply pruning and quantization to further reduce the parameters and memory. We
then propose an ensemble framework that combines various low-complexity CNNs
to improve the overall performance. An experimental evaluation of the proposed
framework is performed on the publicly available DCASE 2022 Task 1 that
focuses on ASC. The proposed ensemble framework has approximately 60K
parameters, requires 19M multiply-accumulate operations and improves the
performance by approximately 2-4 percentage points compared to the DCASE 2022
Task 1 baseline network.

Index Terms—  Acoustic scene classification, Low-complexity, Pruning,
Quantization. Convolution neural network.

##  1 Introduction

Convolutional neural networks (CNNs) have shown state-of-the-art performance
in comparison to traditional hand-crafted methods in various domains [1].
However, CNNs are resource hungry due to their large size and computational
complexity [2, 3], and hence it is difficult to deploy CNNs on resource
constrained devices. For example, Cortex-M4 devices (STM32L496@80MHz or
Arduino Nano 33@64MHz) have a maximum allowed limit of 128K parameters and 30M
multiply-accumulate operations (MACs) per second during inference. Thus, the
issue of reducing the size and the computational cost of CNNs has drawn a
significant amount of attention in the detection and classification of
acoustic scenes and events (DCASE) research community.

In the literature, some CNN parameters such as filters or weights may be
redundant, and contribute to extra memory and computational complexity only
[4, 5]. For example, Li et al. [6] found that 64% of the parameters which
contribute approximately 34% of computation time are redundant. Removing the
redundant parameters from CNNs gives similar performance with an advantage of
reduced memory and less computational cost.

The majority of the methods applied to eliminate redundant parameters are on
filter pruning [7, 8, 9, 10], where a redundant filter from the network is
being eliminated. Filter pruning methods have been widely employed in the
computer vision. However, only a few works [5, 11] have applied filter pruning
methods in the audio domain, and the issue of designing CNNs for resource
constrained devices with constraints on both memory and MACs have not yet been
fully explored. Recently, the DCASE community has considered on designing low-
complexity frameworks for ASC with constraints on both memory and MACs. The
DCASE challenge 2022 Task 1 [12] provides a baseline CNN which has 46512
parameters and 29.24M MACs with accuracy approximately 43% and 1.575 log-loss
for audio scene classification (ASC) .

This paper aims to design “low-complexity CNNs” which have a maximum number of
parameters less than 128K and a maximum number of MACs per seconds less than
30M and performance better than that of the DCASE 2022 Task 1 baseline network
for ASC.

The major contributions of the paper is summarized below,

  1. (a)

We design a “low-complexity” CNN that has a fewer parameters and MACs with
better performance than that of the DCASE 2022 Task 1 baseline CNN.

  2. (b)

A filter pruning method is applied to compress the “low-complexity CNN” of (a)
further. Subsequently, we quantize each parameter from float32 to INT8 data
type, reducing networks memory by four times.

  3. (c)

An ensemble approach is proposed which combines predictions obtained from
several (b) low-complexity CNNs.

  4. (d)

Experimental evaluation is undertaken to compare performance of classical
methods such as Gaussian Mixture Model (GMMs) and random forest (RF)
classifiers, learning based methods such as dictionary learning and a pre-
trained high complexity CNN, VGGish with the proposed framework.

The rest of the paper is organized as follows. In Section 2, a brief overview
of dataset used and features used for experimentation is described. In Section
3, a procedure to obtain low-complexity CNN and an ensemble framework is
described. Section 4 presents experimental analysis. Finally, discussion and
conclusion is presented in Section 5 and 6 respectively.

##  2 Experimental dataset and feature extraction

DCASE 2022 Task 1 uses the TAU Urban Acoustic Scenes 2022 Mobile, development
and evaluation datasets [13]. The dataset contains recordings from 12 European
cities in 10 different acoustic scenes using 4 different recording devices.
Each audio recording has 1 second length. The development dataset is divided
in training and validation sets. The training dataset consists of 139620 audio
examples and the validation dataset consists of 29680 audio examples. The
evaluation dataset consists of only audio examples without any groundtruth
available publicly, and the evaluation is performed by the DCASE challenge
community.

Feature extraction: For time-frequency representations, log-mel band energies
of size (40 $\times$ 51) corresponding to an audio signal of 1 second length
are extracted. A Hamming asymmetric window of length 40ms, and a hop length of
20ms is used to extract magnitude spectrogram. Next, log-mel spectrogram is
computed using 40 mel bands.

##  3 Obtaining low-complexity CNNs

Low-complexity optimal CNN architecture: We design a simple low-complexity CNN
architecture which consists of three convolutional layers (C1, C2 & C3), two
pooling layers (P1, P2), a dense layer (D) and a classification layer. We
perform an empirical analysis to select an appropriate size of CNN filters and
activation functions across the different layers. The filter size for each
convolutional layer is chosen from a set, $\\{1\times 1,3\times 3,5\times
5,7\times 7\\}$. We choose hyperbolic tangent (tanh) or rectified linear unit
(ReLU) activation function for different layers. The low-complexity CNN is
trained using the training dataset with a batch size of 64 with an Adam
optimizer for 1000 epochs. A categorical cross-entropy loss function is used
during the training process. We apply an early stopping criterion to yield the
best network that gives the minimum log-loss for the validation dataset.

The optimal architecture obtained after performing empirical analysis is given
in Table 1. The details of the experiments are given in Section 4. The
proposed architecture requires approximately 5M MACs to produce an output
corresponding to an input of size (40 x 51), and has 14886 parameters. The
performance of the trained network is measured in terms of accuracy and log-
loss, averaged over 5 different iterations.

Reducing redundancy in the low-complexity optimal CNN via filter pruning: To
eliminate redundant filters from the low-complexity optimal architecture as
given in Table 1, we apply a filter pruning strategy. For each convolutional
layer, we identify filter pairs which are similar. Our hypothesis is that
similar filters produce similar output or feature maps and hence, contribute
to redundancy only. Therefore, one of the similar filters can be eliminated.
The similarity between the filters is measured using a cosine distance. We
identify the closest filter pairs for each layer separately. A filter from
each pair is deemed redundant and eliminated from the network. More
information about the similarity based filter pruning method can be found at
[14].

The number of redundant filters obtained after performing similarity-based
filter pruning for C1 layer is 4 out of 16, C2 layer is 4 out of 16 and C3
layer is 10 out of 32. We obtain 6 different pruned networks that are obtained
after pruning C1 layer only, C2 layer only, C3 layer only, C1 and C2 layers,
C2 and C3 layers, C1 and C2 and C3 layers. The number of MACs and the number
of parameters for each pruned network are given in Table 2.

To regain the loss in performance due to pruning, the pruned networks are
fine-tuned with a similar process to that used for the training of the
unpruned low-complexity optimal network.

Reducing memory requirement via quantization: To reduce size of the network,
we perform quantization on parameters of each pruned network using Tensorflow-
Lite (TFLite). TFlite [15] is an open-source framework to quantizes a pre-
trained full-precision network for embedded devices. We quantize the network
parameters from 32-bit floating point to 8-bit integers. This leads to reduce
the network size 4x.

An ensemble framework: Next, the predictions obtained from various pruned
networks are aggregated together in an ensemble framework. The total number of
parameters in the ensemble framework that aggregates predictions from all 6
pruned networks are 70.97K and the total number of MACs are 23.84M.

The codes and the pruned networks can be found online 111Link: Pruned
Quantized models, confusion matrices, evaluation scripts.222Link: Model size
and complexity calculation..

Table 1: Low-complexity optimal CNN architecture. Here, tanh is a hyperbolic
tangent activation function and ReLU is a rectified linear unit activation
function.

Layer name | Description
---|---
C1 |  |  Convolution 16@(3 $\times$ 3) + Batch Normalization + tanh
---
C2 |  |  Convolution 16@(3 $\times$ 3) + Batch Normalization + ReLU
---
P1 |  Average Pooling (5 $\times$ 5)
C3 |  |  Convolution 32@(3 $\times$ 3) + Batch Normalization + tanh
---
P2 |  Average Pooling (4 $\times$ 10)
D |  | Dense (100) + tanh
---
Classification | softmax (10)

Table 2: Various low-complexity CNNs obtained after pruning and applying
quantization (INT8).

Sr No. | Network Name | Pruned layer | Architecture (C1-C2-C3-Dense) | Parameters | Size (KB) | MACs (millions)
---|---|---|---|---|---|---
1 | Unpruned optimal low-complexity | NA | 16-16-32-100 | 14886 | 18.59 | 5.41
2 | Pruned_C1 | C1 | 12-16-32-100 | 14254 | 17.86 | 4.16
3 | Pruned_C2 | C2 | 16-12-32-100 | 13138 | 16.85 | 4.13
4 | Pruned_C3 | C3 | 16-16-22-100 | 11396 | 15.11 | 5.29
5 | Pruned_C12 | C1 + C2 | 12-12-32-100 | 12650 | 16.26 | 3.18
6 | Pruned_C23 | C2 + C3 | 16-12-22-100 | 10008 | 13.73 | 4.04
7 | Pruned_C123 | C1 + C2 + C3 | 12-12-22-100 | 9520 | 13.14 | 3.08

##  4 Performance Analysis

The accuracy and the log-loss obtained at various filter size and different
activation functions in the low-complexity CNN is shown in Figure 1. The low-
complexity CNN with (3 x 3) filter size outperforms networks with other filter
size.

Using “ReLU” activation function across all layers results in smaller log-loss
in comparison to that of the the “tanh” activation function. On the other
hand, combining “tanh” and “ReLU” activation functions across different layers
improves the log-loss further as shown in Figure 2. We find that the “tanh”
activation function in the first layer and “ReLU” for other layers improves
the performance over that of using “ReLU” for all layers. Finally, we choose
the low-complexity optimal CNN architecture which performs better than that of
architectures with different combinations of activation function. The optimal
low-complexity CNN has “tanh” activation function in all layers except C2 and
the filter size is (3 x 3) in each convolutional layers.

Figure 1: Accuracy and log loss obtained for DCASE 2022 Task 1 development
validation dataset using the low-complexity CNNs at different filter size and
activation function. Figure 2: Accuracy and log loss obtained for DCASE 2022
Task 1 development validation dataset using the low-complexity CNN with (3 x
3) filter size when different combinations of activation functions are applied
across “C1”, “C2”, “C3” and “D” layers. Here, “T” represents tanh activation
function and “R” represents ReLU activation function.

Next, we analyse the performance obtained using the low-complexity optimal CNN
without performing any pruning and after pruning it. Figure 3 shows the
accuracy and the log-loss obtained for the unpruned low-complexity optimal
network and its various pruned networks. The unpruned low-complexity optimal
network gives 1.475 log-loss and 45.92% accuracy. Eliminating filters from the
unpruned network results in a significant reduction in performance, but this
is almost entirely restored after fine-tuning.

The performance obtained after aggregating predictions from various pruned
networks is given in Table 3. The ensemble framework improves the performance
in comparison to that of individual pruned networks.

Performance comparisons: The proposed ensemble framework improves performance
as compared to the DCASE 2022 Task 1 baseline network for development and
evaluation datasets as given in Table 4. We also compare the performance with
the following methods,

  * •

GMM: We train Gaussian Mixture Models (GMMs) for each scene class separately,
and perform classification using maximum likelihood estimates. The log-mel
spectrogram of size (40 x 51) is averaged along temporal dimension to yield
(40 x 1) vector, which is given as an input to train the GMMs. The number of
mixtures (n) per class are chosen from {5,10,15,20,30,50}.

  * •

RF: A random forest (RF) classifier is trained using the log-mel spectrogram
averaged along the temporal dimension. The number of estimators are set to 100
and the depth (d) is chosen from {5,20,40,50,100,200}.

  * •

Dictionary learning: A dictionary learning framework with structured
incoherence and shared features (DLSI) [16] is trained. DLSI framework learns
the dictionary for each class by minimizing the reconstruction error and
reduces the redundant dictionary atoms in the learning process itself. The
number of dictionary atoms per class (k) are chosen from {5,10,15,20,40}.

  * •

MLP: A multi-layer perceptron (MLP) network with 2 dense layers each having
100 and 50 units is trained on averaged log-mel spectrogram along the temporal
dimension.

  * •

Pre-trained CNN: We use pre-trained convolutional layers of VGGish [17, 18]
followed by a dense and a classification layer to yield an end-to-end VGGish
network. The input to the end-to-end VGGish is log-mel spectrogram of size (40
x 51). We train the end-to-end VGGish for 1000 epochs with similar training
settings as used to train the low-complexity CNNs.

The proposed ensemble framework outperforms the other methods as shown in
Figure 4. It is interesting to note that the proposed low-complexity optimal
CNN performs better than that of the large-scale pre-trained CNN which has
4.5M parameters and has 1077M MACs.

Figure 3: (a) Accuracy and (b) log-loss obtained after pruning different
intermediate layers (C1, C2, C3, C1+C2, C2+C3, C1+C2+C3) in the unpruned low-
complexity optimal CNN for DCASE 2022 Task 1 development validation dataset.
The accuracy and the log-loss is obtained with and without performing the
fine-tuning of the pruned network. Figure 4: Accuracy comparison of various
methods for DCASE 2022 Task 1 development validation set. Here, we show the
best accuracy obtained from the DLSI, GMM and RF framework. Figure 5: (a)
Aggregated MSE computed between the feature maps generated using Pruned_C2 and
Pruned_C3 network from the C1 layer. (b) shows the different and the similar
feature maps corresponding to $4^{\text{th}}$ and $6^{\text{th}}$ feature map
index. Table 3: Performance obtained for DCASE 2022 Task 1 development
validation dataset using the ensemble framework that combines various low-
complexity optimal CNNs obtained after pruning and quantization.

Sr No. | Ensemble framework | Number of parameters | MACs (millions) | Size (KB) | Accuracy (%) | Log-loss
---|---|---|---|---|---|---
1 | All pruned networks except Pruned_C1 | 56712 | 19.72 | 75.09 | 47.14 | 1.394
2 | All pruned networks except Pruned_C2 | 57828 | 19.75 | 76.10 | 47.10 | 1.396
3 | All pruned networks except Pruned_C3 | 59570 | 18.60 | 77.84 | 47.26 | 1.392
4 | All pruned networks except Pruned_C12 | 58316 | 20.70 | 76.69 | 47.45 | 1.394
5 | All pruned networks except Pruned_C23 | 60958 | 19.84 | 79.22 | 47.52 | 1.389
6 | All pruned networks except Pruned_C123 | 61446 | 20.80 | 79.81 | 47.35 | 1.392
7 | Ensemble on all pruned networks | 70966 | 23.84 | 92.95 | 47.45 | 1.389

Table 4: Performance comparison

Framework | Dataset
---|---
Development | Evaluation
Accuracy (%) | log-loss | Accuracy (%) | log-loss
|  DCASE baseline network [12]
---
42.9 | 1.575 | 44.2 | 1.532
Proposed ensemble | 47.26 | 1.392 | 45.9 | 1.492

Similarity analysis among various pruned models: We analyse similarity between
the different pruned models as given in Table 2. For this, we use 10k audio
examples from the validation dataset, and generated outputs from the various
filters (feature maps). The similarity is measured using the aggregated mean
square error (MSE) across 10k examples, computed between the corresponding
feature maps of two different pruned models.

We find that a few of the feature maps generated by the two different pruned
models are similar with MSE $\leq 10^{4}$. To show this, the aggregated MSE
computed across corresponding feature maps generated by the Pruned_C2 and the
Pruned_C3 network is plotted in Figure 5(a). A few of the feature maps have
MSE close to zero, and hence these feature maps are similar. We also show the
different and the similar feature maps obtained from the Pruned_C2 network and
the Pruned_C3 network corresponding to 4${}^{\text{th}}$ and 6${}^{\text{th}}$
index for a given input in Figure 5(b). This suggests that similar feature
maps across different pruned networks are redundant, and are not required to
compute again for the other network.

We find that the Pruned_C1 network shares 7 feature maps with the Pruned_C12
network, and 3 feature maps with the Pruned_C123 network across C1 layer.
Similarly, the Pruned_C2 network shares 7 feature maps with the Pruned_C3,
network and 6 feature maps with the Pruned_C23.

Ignoring similar feature maps across different pruned models, the MACs are
further reduced by 6M points, and the number of total parameters are reduced
by approximately 3.4k in the ensemble framework that combines all pruned
networks.

##  5 Discussion

Advantage of obtaining low-complexity CNNs via Pruning: The accuracy obtained
using the Pruned_C123 CNN having 9.5k parameters is approximately 16
percentage point better than that of the low-complexity CNN with 8.6k
parameters. This suggests that the smaller network obtained from the
relatively large size network after pruning gives better performance as
compared to the similar size smaller network.

We find that the ensemble on various CNNs improves the performance as compared
to the individual CNN. However, the ensemble on the various CNNs consumes more
resources. Therefore, pruning individual CNNs provide an advantage to use the
ensemble framework efficiently. To improve the efficiency of the ensemble
further, the shared feature maps (similarity) across various CNNs can be
ignored.

##  6 Conclusion

This paper focuses on designing a low-complexity system for acoustic scene
classification. A filter pruning, quantization and ensemble procedure is
applied to obtain compressed, accelerated, and low-size CNN. The proposed
framework shows promising results in terms of reduction in parameters and
performance. In future, our aim is to improve the performance of the low-
complexity framework further.

##  7 Acknowledgements

This work was partly supported by Engineering and Physical Sciences Research
Council (EPSRC) Grant EP/T019751/1 “AI for Sound (AI4S)”. For the purpose of
open access, the authors have applied a Creative Commons Attribution (CC BY)
licence to any Author Accepted Manuscript version arising. Thanks to James A.
King and Xubo Liu, PhD students at University of Surrey, UK for the
discussions.

## References

  * [1] J. Gu, Z. Wang, J. Kuen, L. Ma, A. Shahroudy, B. Shuai, T. Liu, X. Wang, G. Wang, J. Cai, _et al._ , “Recent advances in convolutional neural networks,” _Pattern Recognition_ , vol. 77, pp. 354–377, 2018.
  * [2] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” _International Conference on Learning Representations, ICLR (arXiv preprint arXiv:1409.1556)_ , 2015.
  * [3] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “ImageNet classification with deep convolutional neural networks,” _Advances in Neural Information Processing Systems_ , pp. 1097–1105, 2012.
  * [4] Y. Wen and D. Gregg, “Exploiting weight redundancy in CNNs: Beyond pruning and quantization,” _arXiv preprint arXiv:2006.11967_ , 2020.
  * [5] A. Singh, P. Rajan, and A. Bhavsar, “SVD-based redundancy removal in 1-D CNNs for acoustic scene classification,” _Pattern Recognition Letters_ , vol. 131, pp. 383–389, 2020.
  * [6] H. Li, A. Kadav, I. Durdanovic, H. Samet, and H. P. Graf, “Pruning filters for efficient ConvNets,” _International Conference on Learning Representations, ICLR_ , 2017.
  * [7] Z. Liu, J. Li, Z. Shen, G. Huang, S. Yan, and C. Zhang, “Learning efficient convolutional networks through network slimming,” _Proceedings of the IEEE international conference on computer vision_ , pp. 2736–2744, 2017.
  * [8] Y. He, X. Zhang, and J. Sun, “Channel pruning for accelerating very deep neural networks,” _Proceedings of the IEEE International Conference on Computer Vision_ , pp. 1389–1397, 2017.
  * [9] Y. He, P. Liu, Z. Wang, Z. Hu, and Y. Yang, “Filter pruning via geometric median for deep convolutional neural networks acceleration,” _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 4340–4349, 2019.
  * [10] M. Lin, R. Ji, Y. Wang, Y. Zhang, B. Zhang, Y. Tian, and L. Shao, “HRank: Filter pruning using high-rank feature map,” _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 1529–1538, 2020.
  * [11] B. Kim, S. Yang, J. Kim, and S. Chang, “QTI submission to DCASE 2021: Residual normalization for device imbalanced acoustic scene classification with efficient design,” _DCASE2021 Challenge, Tech. Rep_ , 2021.
  * [12] I. Martín-Morató, F. Paissan, A. Ancilotto, T. Heittola, A. Mesaros, E. Farella, A. Brutti, and T. Virtanen, “Low-complexity acoustic scene classification in DCASE 2022 Challenge,” _arXiv preprint arXiv:2206.03835_ , 2022.
  * [13] T. Heittola, A. Mesaros, and T. Virtanen, “Acoustic scene classification in DCASE 2020 Challenge: Generalization across devices and low complexity solutions,” _Proceedings of the Detection and Classification of Acoustic Scenes and Events (DCASE) Workshop_ , 2020.
  * [14] A. Singh and M. D. Plumbley, “A passive similarity based CNN filter pruning for efficient acoustic scene classification,” _Interspeech (arXiv preprint arXiv:2203.15751)_ , 2022.
  * [15] R. David, J. Duke, A. Jain, V. Janapa Reddi, N. Jeffries, J. Li, N. Kreeger, I. Nappier, M. Natraj, T. Wang, _et al._ , “TensorFlow Lite Micro: Embedded machine learning for TinyML systems,” _Proceedings of Machine Learning and Systems_ , vol. 3, pp. 800–811, 2021.
  * [16] I. Ramirez, P. Sprechmann, and G. Sapiro, “Classification and clustering via dictionary learning with structured incoherence and shared features,” _IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ , pp. 3501–3508, 2010.
  * [17] J. Cramer, H.-H. Wu, J. Salamon, and J. P. Bello, “Look, listen, and learn more: Design choices for deep audio embeddings,” _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 3852–3856, 2019.
  * [18] S. Hershey, S. Chaudhuri, D. P. W. Ellis, J. F. Gemmeke, A. Jansen, C. Moore, M. Plakal, D. Platt, R. A. Saurous, B. Seybold, M. Slaney, R. Weiss, and K. Wilson, “CNN architectures for large-scale audio classification,” _International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pp. 131–135, 2017.