A Hardware Trojan-Detection Technique Based on Suspicious Circuit Block Partition

Abstract

To ensure that a hardware Trojan remains hidden in a circuit, it is usually necessary to ensure that the trigger signal has a low testability, which has been widely recognized and proven. The most advanced testability-based detection methods are rather slow for large circuits, and the false-positive rate is not as low as that for small circuits. In this paper, a hardware Trojan, through the low testability of the trigger signal and its position characteristics in the circuit, was detected, which greatly improves the detection speed while maintaining a lower false positive rate when being applied to large circuits. First, the Sandia Controllability/Observability Analysis Program (SCOAP) was applied to obtain the 0–1 controllability of the signals in the netlist. Secondly, the controllability value was calculated by the differential amplification model, in order to facilitate K-means clustering to get better results. Then, we calculate the shortest path between each suspicious signal to get the connection between each suspicious signal. Finally, we divide the suspicious signals into several suspicious circuit blocks to screen the real trigger signal. As a result, the false-negative rate of 0% and the highest false-positive rate of 5.02% were obtained on the Trust-Hub benchmarks.

1. Introduction

With the rapid development of the integrated circuits (IC) industry in recent years, the IC supply chain is becoming globalized. Traditional strategies to solve information security issues based on the reliability of the underlying hardware and thereby add safeguards have become less trustworthy [1]. The direct or indirect involvement of an untrusted party in the design, fabrication, and testing process of an IC results in an “uncontrolled” phase of the IC’s life cycle that can be exposed to an attacker [2]. The intellectual property (IP) vendor who is not trusted in the design process of the integrated circuit can insert a malicious circuit, which is the so-called “hardware Trojan”, and the EDA tools that are not trusted may also automatically insert hardware Trojans in the process of design. During manufacturing, the foundry must reverse engineer the IC to be able to insert a hardware Trojan. During testing, testers may conceal the existence of hidden hardware Trojans. The threats to an IC during the whole life cycle is shown in Figure 1, wherein the graph label shows the threat degree from high to low with respect to the color changes. The most dangerous phase is that IP vendors directly insert hardware Trojans into the circuit, for the reason that IP vendors can directly access the unencrypted RTL code, and IP transactions are generally in the form of encrypted netlists. As a consequence, IP buyers cannot judge whether the IP contains additional malicious circuits. The harm of EDA tools inserting a hardware Trojan is the second, even if an untrusted EDA tool has the ability to insert hardware Trojans, it can only insert automatically. In this case, the placement, size, characteristics of hardware Trojans cannot be well controlled, which explains the reason why the hardware Trojans are not so covert. IP designers can compare the results obtained by different EDA tools. Therefore, it will be easier for them to find the existence of hardware Trojans. If the foundry wants to insert hardware Trojans by reverse engineering, the cost of the time and money will be ultrahigh. Furthermore, deliberately concealing the existence of hardware Trojans in the test process will indirectly cause the threat of hardware Trojans to an IC.

At present, a large number of research studies and explorations have been carried out on hardware Trojans all over the world [3]. Research on hardware Trojan detection can be divided into presilicon detection and postsilicon detection, as shown in Figure 2. Specifically, postsilicon testing can be divided into destructive and nondestructive detection. Destructive detection mainly uses reverse engineering to decapsulate an IC, obtain images of each layer, and compare them with golden chips [4,5,6]. Reverse engineering is the most accurate way by which to detect hardware Trojans for the reason that it can be compared with golden chips in the most detailed way. Because the cost of reverse engineering is very high, some algorithms have been proposed to accelerate reverse engineering [7]. However, in real industrial production, golden chips are very difficult to obtain. Thereby, the method of detecting hardware Trojans by reverse engineering is of high cost and low feasibility. In the study of non-destructive testing, electrical characteristics including the transient current [8] and the path delay [9,10,11] through the side-channel [12] information are currently hot spots. Similar to reverse engineering, detection methods based on side-channel information usually need the support of golden chips. Another type of nondestructive test is the logical test [13], which triggers hardware Trojans by applying test vectors to produce false outputs to prove the existence of hardware Trojans. In [14], the authors proposed a statistical Trojan-detection approach that uses rare logic values at internal nodes to generate test patterns, which reduce about 85% test length over the traditional method of using random patterns. The authors of ref. [15,16] were committed to locating circuit locations where hardware Trojans might be easily inserted. The authors of [17] worked on increasing the activation probability of the test patterns.

Presilicon detection mainly includes circuit function verification, circuit design analysis and formal verification, such as simulation and coverage of the gate-level netlist. However, these simple tests only evaluate the trust of the circuit and cannot accurately detect whether there is a hardware Trojan in the circuit. At present, the focus of the research is the analysis of the gate-level netlist [18]. Different from various methods of postsilicon detection, the analysis based on the gate-level netlist does not require golden chips, and is relatively more advanced and has more practical significance. Therefore, we will focus on the most serious threat of hardware Trojans in third-party IP, and research on gate-level netlist level hardware Trojan-detection technology.

The structure of this paper is as follows. Section 2 introduces the achievements of gate-level netlist hardware Trojan-detection technology. Section 3 discusses the motivation and contribution of this paper. In Section 4, a complete scheme of hardware Trojan-detection technology based on signal controllability and circuit structure is presented. Based on the detection results on the Trust-Hub [19], Section 5 compares the experimental results of this paper with those of previous experiments from the perspective of detection accuracy and speed. Section 6 summarizes the whole paper and describes the possible future research directions.

2. Related Work

The gate-level netlist detection technology mainly consists of two steps. First, it extracts the circuit features, and secondly analyzes the data based on these feature values. The existing gate-level netlist detection techniques can be divided into three categories: search-based methods, threshold-based methods, and machine learning-based methods.

• Search-based detection

Search-based detection technology mainly extracts the data in the netlist by applying excitation, and then analyzes the flipping characteristics of these signals to obtain suspicious signals.

In [20], the detection method of unused circuit identification (UCI) was proposed. The data flow graph between circuit nodes was applied to check which nets were not activated in the simulation test. In this way, these unused circuits can be defined as suspicious circuits and a manual check was performed to reduce the false positive rate. The detection method of VeriTrust proposed in [21] inserted a tracker and a checker into the circuit, recorded the activation history of each input through the tracker, and then judged the redundant input, which may be used to activate the hardware Trojan through these data.

Search-based detection is one of the earliest gate-level netlist detection techniques, but it is difficult to apply in large-scale circuits because of its low efficiency. Therefore, later researchers proposed detection techniques based on threshold and machine learning, which enhanced efficiency significantly.

• Threshold-based detection

The threshold-based detection has a certain efficiency improvement compared with search-based detection, for the reason that it quantifies the eigenvalue of the signals and sets the threshold for screening.

The idea of FANCI [22] is similar to that of UCI [20], both of which hope to extract unused circuits. FANCI detects malicious circuits by quantitatively evaluating the influence of input on output. It calculates control values (CV) based on the truth table to represent the impact of the input on the output. However, this method does not need to observe whether every circuit node is activated like UCI. In contrast, it can be judged according to whether the CV value reaches a certain threshold. However, the calculation of CV value will become more and more complex with the increase of circuit scale. In order to reduce the amount of calculation, [23] proposed to use the Sandia Controllability/Observability Analysis Program (SCOAP) [24] to judge whether the controllability and observability of the signal exceed the threshold. Compared with the calculation of CV, the calculation of SCOAP does not become complicated with the increasing of the circuit size, and the relevant values can be derived directly through Synopsis’ TetraMAX tool.

For threshold-based detection technology, the selection of a threshold is crucial, but the artificial selection based on experience is not reliable in the actual detection, which requires the further development of the detection technology based on machine learning.

• Machine learning-based detection

Ref. [25] for the first time put forward the idea of detecting hardware Trojans by a machine learning method according to the gate-level circuit structure. They detected the distance between input and output of the gate-level netlist, the fan-in number of the trigger signal and the fan-out number of the trigger signal, and uses the support vector machine (SVM) as a machine learning model. Furthermore, ref. [26] replaced SVM with a neural network algorithm to improve the performance. In [27,28,29,30], the selection of structural characteristics parameters of gate circuit and the types of machine learning algorithms are explored to improve the accuracy and efficiency of detection through richer parameters and superior algorithms.

COTD [31] is a detection method based on unsupervised learning k-means clustering. The author took the testability values including controllability and observability obtained by SCOAP as parameters to conduct k-means clustering. The suspicious cluster contains signals with poor controllability and observability, which were defined as suspicious signals in this method. Through the testability analysis of signals in [32], it was found that there was no direct relationship between observability and the suspiciousness of the signal, while 0/1-controllability was a more detailed measure. Therefore, they proposed a controllability differential amplification model, and the obtained data amplified the features of low controllability, which can help the data get a better clustering effect in the coordinate graph. At the same time, they also use dynamic simulation to obtain the signal transition probability in the circuit to reduce the false positive rate.

Compared with the former two methods, machine learning-based detection has a wider application range and higher accuracy. For the supervised learning methods, the thresholds are determined by the trained model and a large amount of data obtained by benchmarks; therefore, it is unnecessary to manually adjust the threshold. However, the relatively fixed types of hardware Trojans in the hardware Trojan benchmark library can lead to an overfitting problem on the dataset, making the experimental results much better than the actual ones. As for unsupervised learning methods, it is usually based on clustering to signals with certain anomalous characteristics. Similarly, unsupervised learning methods do not require manual adjustment of thresholds. However, the clustering-based methods are heavily demanding on the data and require a certain level of differentiation in terms of a certain characteristic.

3. Motivation and Contribution

Threshold-based detection techniques exhibit that the simplest and fastest signal feature to process is controllability/observability. The controllability/observability value is also applied in the machine learning-based detection, combined with the clustering method to screen the trigger signal of hardware Trojans, which has achieved good results. However, the false positive rate of simple COTD [31] is high and even has a certain false negative rate, which is unacceptable for hardware security. The improved method [32] can find out all the hardware Trojans in the 914 hardware Trojan benchmarks of Trust-Hub, and the highest false positive rate of this method is 11.7%. However, the dynamic simulation method to obtain the signal transition probability in the tested circuit is very inefficient because the test time of dynamic simulation increases exponentially with the circuit size (number of inputs). As a consequence, it is not feasible to use dynamic simulation to reduce the false positive rate for large-scale circuits.

However, it should be pointed out that the signal features for judging trigger signal are not only controllability/observability. The detection method based on circuit structure in [25,26,27,29,30,33,34] has verified that it is an effective means to detect hardware Trojan trigger circuits by circuit features such as fan-in density, circuit size and other gate-level characteristics. In this way, the false positive rate can be significantly reduced.

Therefore, on the basis of the abovementioned issues, we propose the use of unsupervised clustering k-means, with more superior differential amplification model, and capture the structural feature of the circuit to analyze the signal, so as to reduce the false positive rate. The contributions of this paper are as follows:

• We proposed a hardware Trojan-detection technology based on SCOAP and suspicious circuit block partition, which detected 914 hardware Trojans on Trust-Hub with the highest false positive rate of 5.02%.
• We built a pure static analysis hardware Trojan-detection platform, of which the processing speed is more than 10 times faster than [32].

4. Threat Model

Generally speaking, a hardware Trojan refers to a special function module deliberately inserted in the circuit. Hardware Trojans are generally divided into always-on hardware Trojans and triggered hardware Trojans. Always-on hardware Trojans generally have only the load circuit but no trigger circuit. Because of this, always-on hardware Trojans are always active. Always-on hardware Trojans can easily be found by code coverage detection or function detection during the IC verification process. Therefore, for the detection technology of hardware Trojan, it is generally planned for the triggered hardware Trojan with strong concealment. Different from always-on hardware Trojan, a triggered hardware Trojan consists of a trigger circuit and a load circuit, whereas the trigger circuit is the switch of the load circuit. In order to ensure the concealment of the hardware Trojan, the trigger conditions may be irrelevant state or rare nodes in the circuit to ensure that the hardware Trojan is not triggered during function verification.

The design of a simple hardware Trojan circuit was exhibited in Figure 3. Figure 3a is the original circuit design, Figure 3b is the design with the hardware Trojan trigger circuit inserted. It is obvious that $OUTPUT11$ and $OUTPUT12$ are different only when $INPUT1$ = $INPUT2$ = 1, whereas in the case of other conditions, the output of the circuit (b) can be consistent with that of the circuit (a). According to this principle, the attacker can design a small probability trigger circuit as the hardware Trojan trigger circuit.

As IP transactions between companies are widely carried out, IP security is more difficult to guarantee. Taking this into account, we should pay attention to the threat brought by the third-party IP. Hardware Trojans in third-party IP are inserted by IP vendors by adding small, malicious circuits directly into the RTL code after the original IP design is completed. Through this method, IP vendors can activate these hardware Trojans, in order to change the function, leak information, and reduce performance and reliability.

In reality, it is hard to find actual instances of hardware Trojans, so the researchers mainly use Trust-Hub [19], which is a hardware security and trust website that has a list of hardware Trojan test benchmarks in the form of gate-level netlist as standard benchmarks to evaluate detection methods. Among them, TRIT-TC and TRIT-TS are 914 different hardware Trojan benchmarks designed by Cruz et al. based on the ISCAS. The designs are mainly based on the circuit c2680, c2540, c5315, c6288, s13207, s1423, s15850, s35923 to insert hardware Trojans, whereas the difference lies in the insertion of the hardware Trojan type, the trigger condition, and the position. Because these are two libraries with relatively comprehensive hardware Trojan types at present, and ref. [32] have conducted experiments on TRIT-TC and TRIT-TS, our scheme is thereby applied to these 914 hardware Trojan benchmarks to compare the detection results.

5. Proposed Method

Figure 4 shows the proposed flow diagram. First, it takes the gate-level netlist of the hardware Trojan benchmarks as the input to analyze testability in TetraMAX, so as to determine the values of controllability/observability, and directly classify the signals with controllability/observability value greater than 254 as suspicious signals. It should be noted that TetraMAX limits the values to 254 when considering the SCOAP value, which means that the signal has very poor controllability. Secondly, the differential amplification model proposed in [32] was utilized to process the value of CC0/CC1 to obtain the value of CC0${}^{\prime }$/CC1${}^{\prime }$. Thereafter, k-means clustering was performed to classify all signals into three clusters, among which signals in cluster 2/3 were classified as suspicious signals whereas signals in cluster 1 were classified as normal signals. At this point, we can put the hardware Trojan trigger signal into the suspicious signal. Thereby, excluding the false positive signals from the suspicious signal is of great significance. Therefore, we calculate the shortest path between suspicious signals, that is, the suspicious path of these signals. In this way, the mutual relation between suspicious signals can be obtained, and the associated suspicious signals can be divided into a group, which can be defined as suspicious circuit blocks. Finally, in each suspicious circuit block according to the number of forward relevant suspicious signals, the number of suspicious paths are sorted to find the end of suspicious signal transmission, which is most likely to be the trigger signal.

5.1. Difference-Amplified Controllability Analysis

In order to prevent hardware Trojans from being activated during routine detection, designers of hardware Trojans often use rare trigger conditions as a switch of hardware Trojan load circuits. This also means that the trigger signal of hardware Trojans is of low controllability to remain covert. SCOAP is widely used for signal testability analysis, and Synopsis TetraMAX can process SCOAP analysis on the netlist, and directly output the testability value of each signal in the netlist. Testability includes controllability (CC) and observability (CO). Controllability is further divided into 0-controllability (CC0) and 1-controllability (CC1), which respectively represent the minimum number of times of forward signal assignment required for the signal to be set to 0 or 1. CO represents the minimum number of backward signal assignments required for data to be passed to the output.

According to the experimental results of COTD [31], simply using the controllability and observability to carry out k-means clustering to screen suspicious signals can indeed classify trigger signals into suspicious signal clusters. However, the observability value is a characteristic calculated according to the controllability of the backward signal, and the backward signal of trigger signal is the load circuit. Therefore, the structure of the load circuit is different due to different attack targets, so the observability may not be a suitable feature for detection. We have

$$\begin{array}{cc}\hfill \left(CC{0}^{\prime },CC{1}^{\prime }\right)& =\left(\frac{CC{0}^2}{\sqrt{CC0\times CC1}},\frac{CC{1}^2}{\sqrt{CC0\times CC1}}\right)\hfill \\ \hfill & =\left(CC0\times \sqrt{\frac{CC0}{CC1}},CC1\times \sqrt{\frac{CC1}{CC0}}\right).\hfill \end{array}$$

(1)

In this paper, the differential amplification model proposed by [32] is used to transform controllability CC0/CC1 into CC0${}^{\prime }$/CC1${}^{\prime }$, and then k-means clustering is carried out to obtain suspicious signal clusters. The calculation formula of (CC0${}^{\prime }$, CC1${}^{\prime }$) is shown in Formula (1). The advantages of this method are that the original numerical units are retained, the common mode remains unchanged, and the difference mode part is enlarged. Consequently, the imbalanced CC0/CC1 of signals can be better clustered. The clustering results of the differential amplification model are reflected in the coordinate diagram in the form of inverse proportion, which is obviously a superior data-processing method.

Taking c3540_T000 hardware Trojan benchmark as an example, we found that after 1190 signals were detected by COTD, the number of suspicious signals reached 692, whereas after the differential amplification model was used, there were only 35 suspicious signals in the cluster 2/3. In

Table 1. Suspicious signals of c3540_T000.

Signals	CC0	CC1	CC0${}^{\prime }$	CC1${}^{\prime }$
n1556	2	26	0.55	93.74
n1551	25	2	88.39	0.57
n1664	63	1	500.05	0.13
n1662	1	63	0.13	500.05
n1549	48	1	332.55	0.14
N5192	34	3	114.46	0.89
N1409	3	34	0.89	114.46
n1550	12	47	6.06	93.02
Trigger_en0_0	1	70	0.12	585.66
n1028	5	78	1.27	308.08
n707	1	28	0.19	148.16
N3987	82	5	332.07	1.23
n1004	49	8	121.27	3.23
n1533	1	34	0.17	198.25
n1660	48	6	135.76	2.12
n1488	1	42	0.15	272.19
n1659	6	48	2.12	135.76
n1658	47	6	131.54	2.14
n694	33	1	189.57	0.17
trojan0_On1	44	4	145.93	1.21
trojan0_On2	26	1	132.57	0.20
trojan0_On3	1	22	0.21	103.19
n938	43	1	281.97	0.15
n1573	42	1	272.19	0.15
n1532	22	1	103.19	0.21
n1524	1	22	0.21	103.19
n1548	42	6	111.12	2.27
n1575	1	43	0.15	281.97
n946	6	41	2.30	107.18
n760	1	27	0.19	140.30
n696	1	28	0.19	148.16
n1634	22	1	103.19	0.21
n758	1	24	0.20	117.58
n1605	21	1	96.23	0.22
N4028	6	52	2.04	153.08

, it can be observed that the imbalance between CC0 and CC1 can be better reflected in the differential amplification model (CC0${}^{\prime }$, CC1${}^{\prime }$) during the clustering. As shown in Figure 5, the advantage of the differential amplification model is more significant.

5.2. Suspicious Path Calculation

The existing concept of logical depth of a signal refers to the number of gates passed from input to this signal. Similarly, the minimum number of gates between signals can be defined as the logical distance. The logical distance between suspicious signals is defined as the shortest length of the suspicious path. According to the netlist of hardware Trojan benchmarks, the logical relationship between each signal in the circuit is expressed as {gate (input signal 1, input signal 2, …, output signal)}. In this way, we can easily represent it in Python as a dictionary, with the output signal as the key and the input signal as the value.

The specific calculation process of suspicious paths is shown in Algorithm 1 which is named as the shortest-path calculator. The input is (Dictionary G, Starting point A, Ending point B, Path, LEN), while $PATH$ and $LEN$ are initialized to an empty list, and the output is the shortest path S between A and B.

• Step 1: Add the starting point A to the $PATH$ and increase the $LEN$ to 1.
• Step 2: Judge whether the $LEN$ is greater than 10. If so, return null set.
• Step 3: Judge whether the starting point A and the ending point B are equal or whether A is not the key of G. If so, return the shortest path S.
• Step 4: Initializes the shortest path S to an empty list.
• Step 5: Find node N in G with the key is A. If N is not in the $PATH$ and N is the key of G, take (G,N,B,PATH,0) as the input to find the next-level path until the conditions of the first three steps are met, and return the path or null set.
• Step 6: Judge whether S is the shortest path. If not, assign $NEWPATH$ to S.
• Step 7: Judge whether the shortest path S exists, if so, return the shortest path S.

Thus, we can obtain the logical distance between each pair of related suspicious signals and the suspicious path between these suspicious signals.

Algorithm 1 Shortest-path calculator

Input: Dictionary G, Starting Point A, Ending Point B, $PATH=\left[\right]$ and $LEN=0$

Output: Shortest Path S

1: $PATH=PATH+\left[A\right]$, $LEN=LEN+1$

2: if $LEN$ > 10 then

3:  return 0

4: end if

5: if A == B or A not in G then

6:  return S

7: end if

8: Initialize shortest path $S=\left[\right]$

9: for node N in $G\left[A\right]$ do

10:    if N not in $PATH$ and N in G then

11:    $NEWPATH$ = $INPUT(G,N,B,PATH,LEN)$

12:    if $NEWPATH$ exists then

13:      if $S=\left[\right]$ or $NEWPATH$ shorter S then

14:       $S=NEWPATH$

15:      end if

16:    end if

17:    end if

18: end for

19: if S exists then

20:  return S

21: else

22:  return 0

23: end if

5.3. Suspicious Circuit Block Partition

After performing suspicious path calculation, the suspicious signals associated with each other and the suspicious paths between them can be obtained. We found that in these suspicious paths, many of them are not related to hardware Trojan-triggered circuit blocks but some circuits designed to achieve specific functions, resulting in the emergence of some low controllability circuit blocks. This also explains the high false-positive rate of large circuits in [32]. Another reason is that a large part of the false-positive signals detected in [32] are the pre-position signals of the trigger signals in the hardware Trojan trigger circuit. As for the former, we cannot distinguish the difference between specific functional circuit blocks and trigger circuit blocks based on controllability analysis. As for the latter, we can use suspicious paths to divide signals into blocks and find the real trigger signals. It should be pointed out that the trigger circuit of hardware Trojan is not necessarily the one with the largest number of related suspicious signals and the largest number of related suspicious paths for the reason that the scale of the specific functional circuit block might be larger than the trigger circuit block. Therefore, marking suspicious trigger signals in each suspicious circuit block is our main idea to reduce the false positive rate. After the suspicious circuit block partition, we can find the most-likely trigger signals in each suspicious circuit block by sorting the related suspicious signal quantity and the suspicious path in each suspicious circuit block.

When looking for the suspicious path, we use the method to search the signal near the output, recognizing that the number of suspicious signals and suspicious paths related to the signal near the output is larger than that of the forward signal. We first rank suspicious signals from most to least according to the number of suspicious paths. After obtaining the sequential signal_list, we carry out the Algorithm 2 of suspicious circuit block partition. The input is ($signal\_list$, $Suspicious\_Path$), whereas the output is $circuit\_block$.

Algorithm 2 Suspicious circuit block partition

Input:$signal\_list$, $suspiciou{s}_{p}ath$

Output:$circuit\_block$

1: Define number of signals is N, initialize $cnt$ = 0, n = 0

2: for i from 0 to N do

3:  if $cnt$ != 0 then

4:   $flag$ = 0

5:   for k from 0 to $cnt$ do

6:    if $signal\_list\left[i\right]$ in $circuit\_block\_cnt$ then

7:     $flag$ = 1

8:    end if

9:   end for

10:    end if

11:    if $flag$ == 0 then

12:     Put $signal\_list\left[i\right]$ into $circuit\_block\_cnt$, record $Num{b}_n$

13:     Put related signals of $signal\_list\left[i\right]$ into $circuit\_block\_cnt$,

14:     n = n + 1, record the number of signals in $circuit\_block\_cnt$ is $Num{b}_n$

15:     while $Num{b}_{n-1}$ != $Num{b}_n$ do

16:      for j from $Num{b}_{n-1}$ to $Num{b}_n$ do

17:       Put related signals of $circuit\_block\_cnt\left[j\right]$ into $circuit\_block\_cnt$

18:       n = n + 1, record the number of signals in $circuit\_block\_cnt$ is $stage\_n$

19:      end for

20:     end while

21:    end if

22: end for

23: return $circuit\_block$

• Step 1: Define number of signals in $signal\_list$ is N, initialize $cnt$ and n to be 0.
• Step 2: For $signal\_list\left[i\right]$ in $signal\_list$, judge whether $signal\_list\left[i\right]$ is not the first signal or signal is in $circuit\_block$; if so, set $flag$ to be 1.
• Step 3: Judge whether $flag$ is 0; if so, generate $circuit\_block\_cnt$ and put $signal\_list\left[i\right]$ into $circuit\_block\_cnt$, record the number of signals in $circuit\_block\_cnt$ as $Num{b}_n$.
• Step 4: Search related signals of $signal\_list\left[i\right]$ in $Suspicious\_Path$, and put them into $circuit\_block\_cnt$.
• Step 5: Set n = n + 1, record the number of signals in $circuit\_block\_cnt$ is $Num{b}_n$.
• Step 6: While $Num{b}_n$ increasing, put related signals of $signal\_list\left[i\right]$ into $circuit\_block\_cnt$.

The final output is $circuit\_block\_cnt$ and the signal contained therein.

On the c3540_T000 benchmark, we can find three suspicious circuit blocks as shown in

Table 2. Suspicious blocks of c3540_T000.

Suspicious Blocks	Signals
Block 1	n1556, n1551, n1664, n1662, n1549, n1550, n1660, n1658, n946, n1605, n1548, n1659
Block 2	N1409, N5192, n1533, n707, n760, n1524, n694, n696, n1532, n1004, n1605, n938, n1575, n1573, n1634
Block 3	n1028, Trigger_en0_0, trojan0_On1, trojan0_On2, trojan0_On3, n1533, n1532, n938, n1575, n696, n1605

after using related suspicious signals and suspicious path data. It can be clearly seen that the trigger signal is located near the front of Block 3. According to the position of each signal in the suspicious circuit block, we screened out the last two levels of suspicious path in the suspicious circuit block, and found the six signals listed as n1556, n1551, N1409, N5192, n1028, Trigger_en0_0. As a consequence, the false positive rate was greatly reduced. In [32], 17 suspicious signals were obtained after c3540_T000 screening. In large hardware Trojan benchmarks with more suspicious circuit blocks, our advantage is even more pronounced.

6. Results

In order to verify the hardware Trojan-detection method proposed in this paper, we detected a total of 914 hardware Trojan benchmarks on TRIT-TC and TRIT-TS. Then, we evaluated the false-negative rate, false-positive rate and detection speed, and compared the results with [31,32].

6.1. Accuracy

Because only COTD [31] has the probability of false negatives, the method proposed in this paper and [32] have no false negatives, so we only focus on the false positive rate here. The maximum false positive rate of COTD is 72.06%, while in [32] the maximum false positive rate is 11.7%, and the method in this paper we can reduce the maximum false positive rate to 5.02%. The false positive rate (FPR) is defined by the number of false positive signals (FP) and normal signals (N) as Formula (2):

$$\begin{array}{cc}\hfill FPR& =\frac{FP}{N}.\hfill \end{array}$$

(2)

Figure 6 is the coordinate diagram comparing the false positive rate of our method with [31,32] on 914 hardware Trojan benchmarks of TRIT-TC and TRIT-TS. As we can see, the orange points are the false positive rates of COTD, which is obviously higher than the other two. The yellow points are the false positive rates of our method. Compared with the blue one, our experiment results are more stable on 914 hardware Trojan benchmarks and do not have a particularly high false-positive rate.

The method in [32] performs very well in the small circuit, and can even achieve the effect of a 0 false-positive rate. At this point, our method is to screen trigger signals in suspicious circuit blocks, which causes a small number of false positives to be detected even in small circuits, but due to the small number it is generally only less than 5, within the tolerable range. However, in the case of large-scale circuit analysis, the method of [32] is to analyze the testability value and transition probability of the signal. The high values of testability and transition probability are not necessarily due to the designer’s deliberate intention not to activate these signals, but due to the existence of some special functional circuits in the circuit. If a large circuit block in the netlist has poor controllability similar to the hardware Trojan trigger circuit, the whole circuit according to [32] will be identified as a suspicious signal. The horizontal coordinate between 680 and 750 in the figure are large-scale hardware Trojan benchmarks. These circuits contain many suspicious circuit blocks, and the blue points in Figure 6 illustrate that method [32] cannot distinguish these circuits.

However, in our work, after dividing the suspicious circuit block, we can observe that the trigger signal is at the output side of the suspicious circuit block. Then, the signals closest to the output end according to the number of related suspicious signals and the suspicious path length of the signal calculated by the signal can be inferred. In the final suspicious trigger signal screening, we select the closest three level signals to the output of each circuit block. This can not only ensure the reduction of the false positive rate to the greatest extent, but also ensure that the hardware Trojan trigger signal is marked as suspicious signal.

6.2. Speed

Ref. [31] is the first to propose the method of hardware Trojan detection by SCOAP value, and is the founder of subsequent researchers. However, its detection process is very simple, consisting of only simple data acquisition and clustering; therefore, it will not be a reference in the comparison of operation speed. In view of the defects of the method described in [32], first, the false positive rate of large-scale circuit detection is high, and secondly, the efficiency of the method to reduce the false positive rate by dynamic simulation detection of signal transition probability is low. In comparison, the method of this paper directly reduces the false positive rate through static analysis, which is much more efficient.

After experiments, we find that it takes a long time to find the suspicious paths, and some paths of almost unrelated suspicious signals are included. Based on the experimental results, it is proposed that if there is a certain correlation between suspicious signals, the logical distance between them will not be more than 10. To preserve the margin, we define a pair of suspicious signals with more than 10 gates between each other as uncorrelated, which means the logical distance is infinite. In this way, we can not only screen out the paths of almost unrelated suspicious signals, but also greatly improve the efficiency of detection.

The total detection time for the 914 hardware Trojan benchmarks is shown in

Table 3. Calculation time.

Time	[32]	Ours
total time	88.5 h	8.2 h
average time	5.8 min	0.43 min

. Our method has improved the detection speed by more than 10 times, and it only takes 0.43 min on average to detect a hardware Trojan benchmark.

Hardware Trojan benchmarks of TRIT-TC and TRIT-TS are based on circuit c2680, c2540, c5315, c6288, s13207, s1423, s15850, s35923. The detection speed mainly depends on the circuit size and structure. In order to make it more clearly, we counted the average detection time of each type of benchmarks separately, which is shown in

Table 4. Average time of each type of benchmark.

Benchmark	[32]	Ours
c2670	2 min 14 s	8 s
c3540	3 min 14 s	15 s
c5315	6 min 32 s	16 s
c6288	30 min 28 s	2 min 55 s
s13207	2 min 36 s	23 s
s1423	47 s	16 s
s15850	1 min 48 s	18 s
s35932	4 min 46 s	16 s

.

7. Conclusions

In this paper, we propose a detection technique based on suspicious circuit block partition, which ensures a low false-positive rate while improving the detection speed. After the controllable data is processed by differential amplification model, the relationship between suspicious signals is found, and the method of suspicious circuit block partition is used to find the trigger signals. This method is a pure static detection method, which solves the problem that dynamic simulation is too slow to reduce the false positive rate in large circuits. In the following work, we will continue to explore other structural features of the suspicious circuit and detect the hardware Trojan trigger signal more precisely. The method based on suspicious circuit block partition can also be applied to the hardware Trojan circuit isolation technology. We can try to remove the suspicious circuit block automatically, then test whether the circuit function can still run normally.