Svoboda | Graniru | BBC Russia | Golosameriki | Facebook
Next Article in Journal
A Fast and Cost-Effective Calibration Strategy of Inter-Stage Residual Amplification Errors for Cyclic-Pipelined ADCs
Next Article in Special Issue
Traffic-Aware Intelligent Association and Task Offloading for Multi-Access Edge Computing
Previous Article in Journal
Classification of Partial Discharge Sources in Ultra-High Frequency Using Signal Conditioning Circuit Phase-Resolved Partial Discharges and Machine Learning
Previous Article in Special Issue
GLRM: Geometric Layout-Based Resource Management Method on Multiple Field Programmable Gate Array Systems
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Electronics
Volume 13
Issue 12
10.3390/electronics13122400
electronics-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

A Hardware Trojan Diagnosis Method for Gate-Level Netlists Based on Graph Theory

by
Hongxu Gao
1,
Guangxi Zhai
1,
Zeyu Li
1,2,*,
Jia Zhou
3,
Xiang Li
4 and
Quan Wang
1
1
School of Computer Science and Technology, Xidian University, Xi’an 710071, China
2
School of Computer Science and Technology, North University of China, Taiyuan 030051, China
3
School of Microelectronics, Northwestern Polytechnical University, Xi’an 710071, China
4
School of Decision Sciences, The Hang Seng University of Hong Kong, Hong Kong 999077, China
*
Author to whom correspondence should be addressed.
Electronics 2024, 13(12), 2400; https://doi.org/10.3390/electronics13122400
Submission received: 2 April 2024 / Revised: 17 May 2024 / Accepted: 17 June 2024 / Published: 19 June 2024
(This article belongs to the Special Issue New Advances in Distributed Computing and Its Applications)
Browse Figures
Versions Notes

Abstract

:
With the increasing complexity of integrated circuit design, the threat of a hardware Trojan (HT) is becoming more and more prominent. At present, the research mainly focuses on the detection of HTs, but the amount of research on the diagnosis of HTs is very small. The number of existing HT diagnosis methods is generally completed by detecting the HT nodes in the netlist. The main reason is the lack of consideration of the integrity of HTs, so the diagnosis accuracy is low. Based on the above reason, this paper proposes two implanted node search algorithms named layer-by-layer difference search (LDS) and layer-by-layer grouping difference search (LGDS). The LDS algorithm can greatly reduce the search time, and the LGDS algorithm can solve the problem of input node disorder. The two methods greatly reduce the number of nodes sorting and comparing, and therefore the time complexity is lower. Moreover, the relevance between implanted nodes is taken into account to improve the diagnosis rate. We completed experiments on an HT diagnosis; the HT implantation example is from Trust-Hub. The experimental results are shown as follows: (1) The average true positive rate (TPR) of the diagnosis using KNN, RF, or SVM with the LDS or LGDS algorithm is more than 93%, and the average true negative rate (TNR) is 100%. (2) The average proportion of implanted nodes obtained by the LDS or LGDS algorithm is more than 97%. The proposed method has a lower time complexity compared with other existing diagnosis methods, and the diagnosis time is shortened by nearly 75%.

1. Introduction

Integrated circuits play a vital role in modern technology and industry. They are the core component of electronic devices, covering applications in various fields from smartphones to computers, automobiles and industrial control systems, and more [1]. However, integrated circuits injected with a hardware Trojan (HT) may lead to the following hazards: information leakage, functional damage, remote control, and economic loss [2,3,4]. These problems seriously endanger the security of individuals, enterprises, and countries. Therefore, it is essential to ensure the security and reliability of integrated circuits.
Nowadays, there have been many different HT-detection methods. Formal verification [5,6] is a logic verification method based on an algorithm, but it needs a gold netlist for comparison and has poor scalability. Logic testing [7,8] activates the HT by adding test vectors. However, the attacker can escape the test by adding rare trigger conditions. Side-channel analysis [9,10,11] detects an HT with the help of electrical parameters such as delay, power consumption, and electromagnetics during circuit operation. Based on reverse engineering [12,13,14,15,16], it is a kind of method in destructive detection, mainly through a series of reverse engineering to restore the design and details of the circuit. There are also some methods that combine machine learning for an HT detection [1,17,18,19], and these methods tend to have high detection rates.
Most of the existing HT-detection methods only detect whether there is an HT in the circuit and do not diagnose where the HT is implanted in the circuit [20,21]. However, HT diagnosis is also very important in integrated circuits. When a circuit is very large, just detecting it without diagnosing it may cause relevant personnel to spend a lot of time on comprehensive inspection and modification. The benefits brought by HT diagnosis mainly include the following aspects: (1) HT diagnosis can help designers to accurately find the infected part of the circuit, avoiding the overall inspection and modification of the whole circuit, reducing the time-to-market and cost. (2) HT diagnosis can help to exclude false detection and avoid false suspicion and the processing of normal circuit parts. (3) HT diagnosis can help designers understand the related mechanisms of an HT and improve defense strategies [22]. The deficiency of current diagnosis methods is the lack of consideration of the integrity of HTs, so there is a problem of low diagnosis accuracy.
In order to further improve the accuracy of gate-level HT diagnosis, this paper proposes a layer-by-layer difference search (LDS) and layer-by-layer grouping difference search (LGDS) algorithm based on [17]. Different from [17], this paper proposes two implanted node search algorithms, which reduce the amount of node sorting and comparing to reduce the time complexity. The specific steps are shown in Figure 1.
The contributions of this paper are summarized as follows:
(1)
In this paper, we propose a new method for an HT diagnosis based on graph theory.
(2)
The LDS algorithm is proposed, which takes into account the hierarchical relationship of HT load nodes in the netlist; the LGDS algorithm is proposed to solve the problem of out-of-order input nodes.
(3)
The proposed method reduces the number of non-implanted nodes and improves the diagnostic accuracy. Moreover, the amount of node sorting and comparing is reduced, which decreases the time complexity.
(4)
Experimental results show that the proposed method has lower time complexity. The average true positive rate (TPR) for diagnosis is higher than 93% and the true negative rate (TNR) is 100%. Compared with other existing diagnostic methods, the proposed method has a higher diagnostic accuracy and lower time complexity.
The structure of this paper is divided as follows: Section 2 discusses the related work on HT detection and diagnosis. Section 3 shows the research on gate-level HT diagnosis. Section 4 presents the experimental process and analyzes the results. Section 5 concludes this paper.

2. Related Work

In the early stage, people focus on HT-detection technology, which is the most direct way to deal with the security threats caused by HTs. Ludwig et al. [13] designed a framework that introduces a data validation technique based on physical layout confirmation to evaluate the results of reverse engineering both qualitatively and quantitatively, taking into account all possible sources of error. The proposed framework can avoid the natural error of reverse engineering to adversely affect HT detection. Banga et al. [14] proposed an HT-detection method based on circuit region division and power consumption characteristic measurements. This method can be regarded as the first method based on electrical properties. Rajendran et al. [15] proposed a non-intrusive trusted design technique for detecting HTs by analyzing frequency variations of ring oscillators. The proposed technique is capable of detecting HTs implanted in the integrated circuit as a whole or locally in the presence of process variations and measurement errors. While proposing the concept of an HT for the first time, Agrawal et al. [23] also designed a method to construct side channel information such as the power, temperature, and electromagnetic profile as the circuit fingerprint through noise modeling by referring to the principle of side channel cryptanalysis for the first time. Wolff et al. [24] first proposed the method based on a logic test. They first analyzed and investigated the HT effect, then expounded the mechanism of HT detection based on the frequency analysis of rare signal values, and finally designed the generation program of the input trigger vector and HT test vector to detect the HT effect.
Recently, some researchers have begun to pay attention to HT diagnosis techniques that can locate the location of HT implantation or show the extent of HT implantation. Du et al. [18] divided the circuit into sectors and extracted HT-related features from each sector. The label of the sector is used to predict whether it contains an HT during diagnosis. This method can report which sector the HT is implanted in, but the size of the sector is uncertain and there may be overlapping areas between different sectors. Wang et al. [17] divided the circuit into multiple Maximum Single-Output Submodules (MSOSs). MSOSs refer to strongly connected components composed of nodes and their corresponding cells. This method can ensure the uniqueness of the partition and avoid the existence of common strongly connected components among any MSOS.
Although the diagnosis of [17] is simple and effective, the execution time complexity is high. In addition, it does not consider the relevance between implanted nodes, so there may be many non-implanted nodes in the execution result.

3. Gate-Level HT Diagnosis Based on Graph Theory

At present, most of the HT diagnosis methods lack the consideration of the integrity of an HT. On this basis, the gate-level HT diagnosis method based on graph theory is proposed in this paper. This section mainly describes the experimental process, graph theory analysis, and algorithm design.

3.1. Complete Experimental Process

Figure 1 represents the flowchart of the proposed gate-level HT diagnosis method, which is mainly as follows:
(1)
The detection method of [17] was used to complete the detection of an HT and obtain the MSOSs containing an HT. If no HT is included, the diagnosis is terminated. The MSOS is obtained by the knowledge of graph theory. The MSOS is composed of a number of nodes and their corresponding units of strongly connected components. Then, the HT-related features in MSOSs are calculated and counted, and the hyperparameters in the machine learning algorithm are adjusted by the cross-validation method. We train a specific supervised learning model using the optimized hyperparameters. Finally, the MSOS containing HTs can be obtained through the trained model.
(2)
Find the additional implanted nodes of the target netlist relative to the gold netlist using the LDS or LGDS algorithm. The additional implanted nodes are also called difference nodes. After removing these difference nodes and their corresponding cells, the target netlist should satisfy graph isomorphism with the gold netlist as much as possible.
(3)
The MSOSs obtained in step (1) and the implanted nodes obtained in step (2) are intersected.
(4)
The obtained node intersection is then the HT node set.
The difference between our method and [17] lies in the second step of the implanted node search. In [17], the implanted node search based on a breadth-first comparison is adopted, which has the characteristics of a simple principle and easy implementation. However, it does not take into account the relevance of implanted nodes, so there may be some non-implanted nodes or even some actual implanted nodes in the execution results. This paper adds two different algorithms based on it, as shown in Figure 2. Our method searches according to the concept of layers, taking into account the relevance between nodes, and the innovation is that the method design is different. The main steps are as follows:
(1)
LDS or LGDS: by comparing the nodes in the target netlist and the gold netlist layer by layer, the difference nodes in each layer are found; that is, the load-tamper node pair.
(2)
Input-side breadth-first comparison: for each load-tamper node pair, the breadth-first comparison technique of [17] is used with the load node and tamper node as the root, respectively.
(3)
Implanted nodes search based on breadth-first comparison: taking the expansion set of payload nodes and the expansion set of tampered nodes as input, the implanted nodes search method based on a breadth-first comparison is executed to find the implanted nodes.

3.2. Graph Theory Analysis

A netlist is a circuit graph composed of nodes and their corresponding units, which can be regarded as a weighted graph in graph theory to a certain extent. Figure 3 and Figure 4 show the circuit diagram and its corresponding weighted graph. Nodes are vertices, cells are edges, and the type of the cell is the weight of the edge. The two nodes corresponding to cells T4 and G4 in Figure 3 are a load-tamper node pair. The node corresponding to unit T4 after the HT is implanted (i.e., the load node) and the node corresponding to unit G4 before the HT is implanted (i.e., the tamper node) are in the same layer, and they are the only pair of different nodes in their layer (i.e., difference nodes). Generally, HT features are not directly reflected in graph elements, but need to be mapped to specific vertex search conditions. Therefore, the key to study the graph theory of HTs is to determine the vertex search condition. The diagnosis method studied in this paper exploits a simple corollary: if the netlist does not contain HTs originally, but does after the addition of a specific module, then the added module must contain HTs. Therefore, the proposed method searches for additional implanted nodes of the target netlist with respect to the gold netlist. The corresponding vertex search criteria are present in the target netlist, but not in the gold netlist.
The method studied in this paper also addresses the problem of non-unique submodule partitioning schemes. We use the knowledge of graph theory: the MSOS partition is exactly unique. This shows that there exists only one scheme for partitioning MSOSs for any netlist. This is equivalent to no common strongly connected component existing between any two distinct MSOSs. The uniqueness of the partition can avoid the following situations: two submodules contain HT nodes, but the degree of influence of HT nodes on the characteristics of the two is too different, resulting in one submodule being judged as “with HT” and the other submodule being judged as “without HT”.

3.3. Gate-Level HT Implantation Methods

According to the circuit diagram structure, the nodes contained in gate-level HTs are divided into the following three categories in this paper:
(1) Load node: the main output node of the HT (such as the node corresponding to the T4 unit in Figure 3), masquerading as the input node of a specific node in the host netlist, so as to complete the HT function.
(2) Internal node: the internal node of the HT (such as the node corresponding to cell T3 in Figure 3) does not act as the input node or output node of any node in the host netlist.
(3) Trigger node: the secondary input node of the HT (such as the nodes corresponding to the T1, T2, and T4 cells in Figure 3) masquerades the output node of the host primary netlist-specific node (which can also be regarded as the primary input node of the HT) to activate the HT function.
Load node implantation mode: (a) A specific input node that replaces a specific node in the host netlist with a load node. (b) Replace a specific primary output node in the host netlist with a load node. (c) Add the load node as an additional input node for a specific node in the host netlist. (d) Add the load node as an additional primary output node for the host netlist. Among them, the two ways a and b essentially replace a specific node in the host netlist as a load node, and the replaced node can be used as the input node of the trigger node. In essence, in both ways, c and d add extra nodes to the host netlist, which have obvious influences on the function of the host netlist.
The implantation mode of the trigger node: (a) Add the trigger node as an additional output node for a specific node in the host netlist. (b) Add the trigger node as an additional output node for a specific primary output node in the host netlist. (c) A specific output node that replaces a specific node in the host netlist with a trigger node. (d) A specific output node that replaces a specific primary output node in the host netlist with a trigger node. (e) Add additional primary input nodes for the host netlist as input nodes for the trigger node. Among them, a and b only add an output branch for a specific node in the host netlist and basically do not affect the function of the host netlist. In essence, c and d replace a specific node in the host netlist as a trigger node, but it is usually necessary to use the replaced node as the output node of the load node to ensure that other functions of the host netlist are not affected. The effect of e on the function of the host netlist is too obvious.
The different implantation methods of load nodes and trigger nodes will affect the implantation node search, so the proposed method uses the corresponding difference analysis and non-implantation node filtering strategy. For example, if the designer implants the payload node with mode a or b when the gate-level HT is implanted, the replaced input node in the host (the host-tampered node) has an output branch without an end. In view of the HT designer’s handling of this output branch, the analysis is as follows:
(1) This output branch is used as the input of a specific trigger node; that is, the trigger node is implanted in c way, as shown in Figure 3 by connecting the G4 unit with the T4 unit. When performing the implanted node search method of LDS, such host-tampered nodes are added as candidate implanted nodes because of the set of input-side breadth-first comparison nodes belonging to the load node.
(2) Connect this output branch to an additional input port for a specific cell in the host netlist: when the implanted node search method based on a breadth-first comparison is executed, the node corresponding to the cell with an added input port will be added as a candidate implanted node because of the change in the number of input nodes.
(3) Delete the output branch: Removing the line between G4 and T4 in Figure 3 and changing T4 to G4 or not is an example of this approach. This processing usually causes a big change to the function of the host netlist, but it is the simplest case for the implanted node search method of LGDS and does not need to be targeted.

3.4. Design of LDS and LGDS Algorithm

When a payload node of an HT is implanted, it replaces a specific node in a specific layer of the target netlist with itself. Therefore, if we compare this layer of the target netlist and the gold netlist, we can find a pair of difference nodes; that is, the load-tamper node pair. According to this principle, in this paper, the target netlist and the gold netlist are simultaneously traversed in layer order to find the difference nodes of the two in each layer, as shown in Algorithm 1. According to step 5, the LDS algorithm must be affected by the out-of-order problem of input nodes because it has to compare the nodes of each layer one by one in order. Figure 5 is an example of LDS. Observations show that the target netlist and the gold netlist are exactly the same in layers 1, 2, and 4, but there is a load-tampering node pair in layer 3, which is the two nodes corresponding to T4 and G3 cells.
The problem of out-of-order input nodes can cause two nodes that should be the same to have different results when performing a breadth-first comparison. Based on the LDS algorithm, in order to solve the problem of input node disorder, the nodes in each layer need to be divided into several groups according to the corresponding unit type and the number of input nodes, and then each node group is compared in turn to find out the difference nodes, as shown in Algorithm 2. Among them, step 9 is the key to finding the load-tamper node pair. It first compares two groups of nodes with the same number of corresponding cell types and input nodes, then finds one group of redundant nodes, and finally finds the tampered nodes or load nodes corresponding to the redundant nodes. This process is usually very difficult because the LGDS algorithm solves the problem of input nodes out of order, which leads to large time complexity and may introduce non-implanted nodes. It is difficult to guarantee absolute correctness while ensuring low time complexity. However, for an implanted example containing multiple HTs, step 9 must be performed correctly to further distinguish each implanted HT.
Algorithm 1: LDS Algorithm
Electronics 13 02400 i001
The time complexity of Algorithm 1 depends on the number of levels of alignment and the number of nodes and operations in each level. The number of layers is assumed to be L, and the number of nodes in the target netlist and gold netlist are T and G, respectively. Then, the time complexity of Algorithm 1 is O ( L × T × G ) . The space complexity mainly depends on the size of the set P of load-tamper node pairs. Assuming that the number of load-tamper node pairs is P, the space complexity is O ( P ) . In Algorithm 2, the number of layers for alignment is assumed to be L, and the number of nodes for the target netlist and gold netlist are T and G, respectively. The time complexity of the algorithm is mainly composed of the grouping process and comparison process. The grouping process is O ( ( T × G ) × log ( T × G ) ) , and the comparison process is O ( N 2 ) , so the time complexity is O ( L × ( ( T × G ) × log ( T × G ) ) + N 2 ) . The set size is P of load-tamper node pairs, an then the space complexity is O ( P ) .
Algorithm 2: LGDS Algorithm
Electronics 13 02400 i002

4. Experiments and Results

This section describes the experimental process, evaluation metrics, and results.

4.1. Evaluation Measures

Evaluation metrics for binary classification problems are used in this experiment, as shown in Table 1. A higher true positive (TP) indicates that more HTs have been correctly located, and a higher true negative (TN) indicates that it will not mislocate. A higher TPR indicates a better diagnosis, and a higher TNR indicates that it is less likely to cause misjudgment. The formulas for calculating the TPR and TNR are shown in Table 2.

4.2. Experiment on Implanted Node Search

The CPU used in this experiment is AMD Ryzen 53600 with a main frequency of 3.6 GHZ. The memory is 16 G of DDR4 with a frequency of 3.2 GHZ. The HT example selected in this paper is from the combinational circuit designed in [17], and its naming rule is: “gold netlist name_T number”. In this paper, MSOSs containing HTs were obtained after completing the HT-detection experiment in [17]. Subsequently, LDS and LGDS algorithms are used, respectively, to find the additional implanted nodes of the target netlist relative to the gold netlist. The HT benchmarks used in this paper include c2670 c3540, c5315, c6288, s1423, s13207, s15850, and s35932. That is about 900 different circuits. Table 3 presents the results obtained on netlist s35932_T607 using different algorithms. The proportion of implanted nodes represents the proportion of the number of implanted nodes in all the nodes obtained by the search. The netlist is implanted with 2 HTs, totaling 24 HT nodes. According to Table 3, LDS and LGDS obviously consume less time. Since LGDS needs to deal with the problem of out-of-order input nodes, it may introduce some non-implanted nodes, resulting in a reduction in the proportion of implanted nodes. Table 4 shows the implant node search results in netlist c6288_T209. The table is implanted with an HT with 15 nodes. From Table 4, we can see that the running time of the LDS and LGDS methods is lower than the remaining methods. The effect of LDS is superior, and the proportion of LGDS is lower due to the introduction of non-implanted nodes.
The results of the implanted node search for all netlists are shown in Table 5. The maximum proportion refers to the maximum proportion of implanted nodes searched in the netlist. If the ratio reaches 100%, it means that the proposed method can search all implanted nodes in a certain netlist. Similarly, the minimum proportion means that in a certain netlist, only a part of the implanted nodes are searched. The average ratio is the average of the percentage of implanted nodes in each netlist. According to the comparison of the time taken by method [17] and LDS method, it can be found that the time taken by the LDS method is reduced by nearly 75%. The circuit partitioning method is unified as MSOS partitioning. Nowadays, there are also methods to divide sectors [18], but there may be overlapping nodes in the sector. Although the method in [17] and the method proposed in this paper can complete the search of implanted nodes, it is obvious that the search method in this paper is more efficient. In [25], the authors directly detect whether each node in the netlist is an HT node, although they could complete the diagnosis. It is not accurate because normal nodes may be reported as HT nodes.

4.3. HT Diagnosis Experiment

The HT diagnosis experiment follows the implanted node search experiment. For each netlist, if there is no MSOS predicted as “HT”, the diagnosis is terminated. Otherwise, the intersection between the nodes contained in the MSOS predicted as “HT” and the implanted nodes is obtained, so as to complete the diagnosis. The HT diagnosis results for all tested netlists are shown in Table 6. From this result analysis, it can be seen that the results of using KNN, RF, or SVM models with LGD or LGDS to diagnose achieve a sufficiently high level. The average TPR of both LDS and LGDS exceeds 93%, and the average TNR is 100%. It can be found that our method obtains the same experimental results because the essential difference between the LDS algorithm and the LGDS algorithm is not big. The most important difference is that the LGDS algorithm can solve the problem of input node disorder, but it will increase the time complexity. Therefore, the result is the same. The method in [17] can overcome the problem of out-of-order input nodes at the expense of some performance, and search to obtain enough complete and pure implanted nodes. However, since the average TPR is slightly lower than the method studied in this paper, some implanted nodes may be missing. Compared with [17], the proposed method takes into account the relevance between the implanted nodes and the concept of “layer” where the HT payload node is located in the whole netlist. Therefore, the average effect of the proposed method is better and the time consumption is shorter. Compared with [18], the detection effect of this paper is significantly better, which is because [18] does not search for implanted nodes. Compared with [25], the proposed method improves the average TPR and TNR of gate-level HT diagnosis by about 4% and 15%, respectively.

5. Conclusions

This paper focuses on HT diagnosis and proposes a diagnosis scheme based on graph theory. LDS and LGDS algorithms are proposed to search the implanted nodes. It greatly reduces the number of nodes that need to be sorted for difference and reduces the diagnosis time. At the same time, considering the integrity of HTs, the non-implanted nodes are reduced and the diagnosis accuracy is improved. Table 5 and Table 6 show that our proposed method has a good diagnostic performance. However, our method still has some shortcomings. For example, the LDS algorithm must be affected by the out-of-order problem of input nodes because it needs to compare nodes in each layer one by one in order. Secondly, the LGDS algorithm will miss the implanted nodes in some extreme cases. We will try to solve this problem in the future work.

Author Contributions

Conceptualization, H.G. and Z.L.; methodology, Z.L. and G.Z.; software, J.Z., X.L. and H.G.; writing—original draft preparation, H.G. and G.Z.; writing—review and editing, Z.L., J.Z. and Q.W.; funding acquisition, Z.L. All authors have read and agreed to the published version of the manuscript.

Funding

This work was supported in part by the National Natural Science Foundation of China under grant 61972302, in part by the Guangzhou Municipal Science and Technology Project under grant SL2022A04J00404, in part by the Fundamental Research Funds for the Central Universities under grant XJS220306, in part by the Natural Science Basic Research Program of Shaanxi under grant 2022JQ-680, and in part by the Key Laboratory of Smart Human Computer Interaction and Wearable Technology of Shaanxi Province.

Data Availability Statement

The data presented in this study are available on request from the corresponding author.

Acknowledgments

The authors would like to thank the editors and reviewers for their contributions to our manuscript.

Conflicts of Interest

The authors declare no conflicts of interest.

References

  1. Huang, Z.; Wang, Q.; Chen, Y.; Jiang, X. A survey on machine learning against hardware trojan attacks: Recent advances and challenges. IEEE Access 2020, 8, 10796–10826. [Google Scholar] [CrossRef]
  2. Li, H.; Liu, Q.; Zhang, J. A survey of hardware Trojan threat and defense. Integration 2016, 55, 426–437. [Google Scholar] [CrossRef]
  3. Bhunia, S.; Hsiao, M.S.; Banga, M.; Narasimhan, S. Hardware Trojan attacks: Threat analysis and countermeasures. Proc. IEEE. 2014, 102, 1229–1247. [Google Scholar] [CrossRef]
  4. Huang, Z.; Wang, Q.; Yang, P. Hardware trojan: Research progress and new trends on key problems. J. Comput. 2019, 42, 993–1017. [Google Scholar]
  5. Qin, M.; Hu, W.; Mu, D.; Tai, Y. Property based formal security verification for hardware Trojan detection. In Proceedings of the 2018 IEEE 3rd International Verification and Security Workshop (IVSW), Costa Brava, Spain, 2–4 July 2018; pp. 62–67. [Google Scholar]
  6. Ponugoti, K.K. Formal Verification for Hardware Trojan Detection; North Dakota State University: Fargo, ND, USA, 2023. [Google Scholar]
  7. Mukherjee, R.; Rajendran, S.R.; Chakraborty, R.S. A comprehensive survey of physical and logic testing techniques for Hardware Trojan detection and prevention. J. Cryptogr. Eng. 2022, 12, 495–522. [Google Scholar] [CrossRef]
  8. Pan, Z.; Mishra, P. Automated test generation for hardware trojan detection using reinforcement learning. In Proceedings of the 26th Asia and South Pacific Design Automation Conference, Tokyo, Japan, 18–21 January 2021; pp. 408–413. [Google Scholar]
  9. Farahmandi, F.; Huang, Y.; Mishra, P.; Farahmandi, F.; Huang, Y.; Mishra, P. Hardware trojan detection schemes using path delay and side-channel analysis. In System-on-Chip Security: Validation and Verification; Springer: Cham, Switzerland, 2020; pp. 221–271. [Google Scholar]
  10. Amelian, A.; Borujeni, S.E. A side-channel analysis for hardware Trojan detection based on path delay measurement. J. Circuits Syst. Comput. 2018, 27, 1850138. [Google Scholar] [CrossRef]
  11. Yang, S.; Chakraborty, P.; Bhunia, S. Side-channel analysis for hardware Trojan detection using machine learning. In Proceedings of the 2021 IEEE International Test Conference India (ITC India), Bangalore, India, 18–20 July 2021; pp. 1–6. [Google Scholar]
  12. Courbon, F.; Loubet-Moundi, P.; Fournier, J.J.; Tria, A. A high efficiency hardware trojan detection technique based on fast SEM imaging. In Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition (DATE), Grenoble, France, 9–13 March 2015; pp. 788–793. [Google Scholar]
  13. Ludwig, M.; Bette, A.C.; Lippmann, B. Vital: Verifying trojan-free physical layouts through hardware reverse engineering. In Proceedings of the 2021 IEEE Physical Assurance and Inspection of Electronics (PAINE), Washington, DC, USA, 30 November–2 December 2021; pp. 1–8. [Google Scholar]
  14. Banga, M.; Hsiao, M.S. A region based approach for the identification of hardware Trojans. In Proceedings of the 2008 IEEE International Workshop on Hardware-Oriented Security and Trust, Anaheim, CA, USA, 9 June 2008; pp. 40–47. [Google Scholar]
  15. Rajendran, J.; Jyothi, V.; Sinanoglu, O.; Karri, R. Design and analysis of ring oscillator based design-for-trust technique. In Proceedings of the 29th VLSI Test Symposium, Dana Point, CA, USA, 1–5 May 2011; pp. 105–110. [Google Scholar]
  16. Forte, D.; Bao, C.; Srivastava, A. Temperature tracking: An innovative run-time approach for hardware Trojan detection. In Proceedings of the 2013 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Jose, CA, USA, 18–21 November 2013; pp. 532–539. [Google Scholar]
  17. Wang, J.; Zhai, G.; Gao, H.; Xu, L.; Li, X.; Li, Z.; Huang, Z.; Xie, C. A Hardware Trojan Detection and Diagnosis Method for Gate-Level Netlists Based on Machine Learning and Graph Theory. Electronics 2023, 13, 59. [Google Scholar] [CrossRef]
  18. Du, M.; Huang, Z.; Chen, Y.; Li, L.; Wang, Q.; Liu, J. A HT detection and diagnosis method for gate-level netlists based on machine learning. In Proceedings of the 2021 IEEE 6th International Conference on Signal and Image Processing (ICSIP), Nanjing, China, 22–24 October 2021; pp. 1070–1074. [Google Scholar]
  19. Huang, Z.; Li, Z.; Xie, C.; Du, M.; Wang, Q. A hardware trojan detection and diagnosis method for gate-level netlists based on different machine learning algorithms. J. Circuits Syst. Comput. 2022, 31, 2250135. [Google Scholar] [CrossRef]
  20. Zhang, Y.; Li, S.; Chen, X.; Yao, J.; Mao, Z.; Yang, J.; Hua, Y. Hybrid multi-level hardware Trojan detection platform for gate-level netlists based on XGBoost. IET Comput. Digit. Tech. 2022, 16, 54–70. [Google Scholar] [CrossRef]
  21. He, J.; Zhao, Y.; Guo, X.; Jin, Y. Hardware trojan detection through chip-free electromagnetic side-channel statistical analysis. IEEE Trans. Very Large Scale Integr. (VLSI) Syst. 2017, 25, 2939–2948. [Google Scholar] [CrossRef]
  22. Kampel, L.; Kitsos, P.; Simos, D.E. Locating hardware trojans using combinatorial testing for cryptographic circuits. IEEE Access 2022, 10, 18787–18806. [Google Scholar] [CrossRef]
  23. Agrawal, D.; Baktir, S.; Karakoyunlu, D.; Rohatgi, P.; Sunar, B. Trojan detection using IC fingerprinting. In Proceedings of the 2007 IEEE Symposium on Security and Privacy (SP’07), Berkeley, CA, USA, 20–23 May 2007; pp. 296–310. [Google Scholar]
  24. Wolff, F.; Papachristou, C.; Bhunia, S.; Chakraborty, R.S. Towards Trojan-free trusted ICs: Problem analysis and detection scheme. In Proceedings of the Conference on Design, Automation and Test in Europe, Munich, Germany, 10–14 March 2008; pp. 1362–1365. [Google Scholar]
  25. Hasegawa, K.; Hidano, S.; Nozawa, K.; Kiyomoto, S.; Togawa, N. R-htdetector: Robust hardware-trojan detection based on adversarial training. IEEE Trans. Comput. 2022, 72, 333–345. [Google Scholar] [CrossRef]
Electronics 13 02400 g001
Figure 1. Gate-level HT diagnosis method based on graph theory.
Figure 1. Gate-level HT diagnosis method based on graph theory.
Electronics 13 02400 g001
Electronics 13 02400 g002
Figure 2. Implanted node search method based on LDS or LGDS.
Figure 2. Implanted node search method based on LDS or LGDS.
Electronics 13 02400 g002
Electronics 13 02400 g003
Figure 3. Example netlist circuit diagram.
Figure 3. Example netlist circuit diagram.
Electronics 13 02400 g003
Electronics 13 02400 g004
Figure 4. A weighted graph of a netlist circuit.
Figure 4. A weighted graph of a netlist circuit.
Electronics 13 02400 g004
Electronics 13 02400 g005
Figure 5. An example of LDS.
Figure 5. An example of LDS.
Electronics 13 02400 g005
Table 1. Binary classification evaluation.
Table 1. Binary classification evaluation.
The Prediction Is PositiveThe Prediction Is Negative
Positive ExampleTrue positive (TP)False Negative (FN)
Negative ExampleFalse Positive (FP)True negative (TN)
Table 2. TPR and TNR formulas.
Table 2. TPR and TNR formulas.
MetricCalculation Formula
TPR T P T P + F N
TNR T N T N + F P
Accuracy T N + T P T N + T P + F P + F N
Precision T P T P + F P
F1 Score 2 × P r e c i s i o n × T P R P r e c i s i o n + T P R
Balanced Accuracy T P R + T N R 2
Table 3. Implanted node search results in s35932_T607.
Table 3. Implanted node search results in s35932_T607.
MethodMethod in [17]Method in [18]LDSLGDS
Node cell nametrig23_0U1
trig23_0U2
.
.
.
tri23_0U9
troj7_0state_reg_0_
troj7_0state_reg_1_
tro_0Trojan_out0_reg
troj7_0U3
troj7_0U4
.
.
.
troj7_0U9
trojan7_0
troj7_1U1
troj7_1U2
troj7_1U3
trojan7_1		trig23_0U1
trig23_0U2
.
.
.
tri23_0U9
tro_0Trojan_out0_reg
troj7_0U3
troj7_0U4
.
.
.
troj7_0U9
trojan7_0
troj7_1U1
troj7_1U2
troj7_1U3
trojan7_1		trig23_0U1
trig23_0U2
.
.
.
tri23_0U9
troj7_0state_reg_0_
troj7_0state_reg_1_
tro_0Trojan_out0_reg
troj7_0U3
troj7_0U4
.
.
.
troj7_0U9
trojan7_0
troj7_1U1
troj7_1U2
troj7_1U3
trojan7_1		trig23_0U1
trig23_0U2
.
.
.
tri23_0U9
troj7_0state_reg_0_
troj7_0state_reg_1_
tro_0Trojan_out0_reg
troj7_0U3
troj7_0U4
.
.
.
troj7_0U9
trojan7_0
troj7_1U1
troj7_1U2
troj7_1U3
trojan7_1
U3783
U4537
Proportion100%91.7%100%92.3%
Time consuming (ms)1531052791
Table 4. Implanted node search results in c6288_T209.
Table 4. Implanted node search results in c6288_T209.
MethodMethod in [17]Method in [18]LDSLGDS
Node cell nametroj9_0U1
troj9_0U2
.
.
.
troj9_0U7
trojan9_0
troj9_1U1
.
.
.
troj9_1U6
trojan9_1		troj9_0U1
troj9_0U2
.
.
.
troj9_0U6
trojan9_0
troj9_1U1
.
.
.
troj9_1U6
trojan9_1		troj9_0U1
troj9_0U2
.
.
.
troj9_0U7
trojan9_0
troj9_1U1
.
.
.
troj9_1U6
trojan9_1		troj9_0U1
troj9_0U2
.
.
.
troj9_0U7
trojan9_0
troj9_1U1
.
.
.
troj9_1U6
trojan9_1
U2415
U2416
Proportion100%93.3%100%88%
Time consuming (ms)97641860
Table 5. Search results for all netlists.
Table 5. Search results for all netlists.
Method in [17]Our Proposed LDS MethodOur Proposed LGDS MethodMethod in [18]Method in [25]
Minimum proportion67.2%84.6%17.5%--
Maximum proportion100%100%100%--
Average proportion98.9%99.9%97.3%--
Time consuming (ms)453631214534574--
Circuit partitioning methodMSOSMSOSMSOSSectorDetecting nodes
Diagnosis or not11111
Table 6. HT diagnosis results.
Table 6. HT diagnosis results.
Principle of Search/Machine Learning ModeKNNRFSVMDTBayesAdversarial Training
TPR TNR TPR TNR TPR TNR TPR TNR TPR TNR TPR TNR
Method in [17]97.3%100%97.7%100%93.4%100%------
Method in [18]90.91%92.46%----86.36%98.61%100%65.15%--
Method in [25]----------94.9%85.3%
Our proposed LDS method98.0%100%98.4%100%93.9%100%91.3%100%93.7%100%--
Our proposed LGDS method98.0%100%98.4%100%93.9%100%95.6%100%96.0%100%--
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Share and Cite

MDPI and ACS Style

Gao, H.; Zhai, G.; Li, Z.; Zhou, J.; Li, X.; Wang, Q. A Hardware Trojan Diagnosis Method for Gate-Level Netlists Based on Graph Theory. Electronics 2024, 13, 2400. https://doi.org/10.3390/electronics13122400

AMA Style

Gao H, Zhai G, Li Z, Zhou J, Li X, Wang Q. A Hardware Trojan Diagnosis Method for Gate-Level Netlists Based on Graph Theory. Electronics. 2024; 13(12):2400. https://doi.org/10.3390/electronics13122400

Chicago/Turabian Style

Gao, Hongxu, Guangxi Zhai, Zeyu Li, Jia Zhou, Xiang Li, and Quan Wang. 2024. "A Hardware Trojan Diagnosis Method for Gate-Level Netlists Based on Graph Theory" Electronics 13, no. 12: 2400. https://doi.org/10.3390/electronics13122400

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop