A ring oscillator-based detection circuit is employed herein to see whether there exists any hardware Trojans, and a path tracking algorithm and a multiplexer are presented as well. The detection performance is tested on the ISCAS85 c17 benchmark.
3.2 An Alternative Way for Hardware Trojan Detection
A hardware Trojan can be detected once there is a frequency shift in a ring oscillator. However, the frequency shift is susceptible to the way that the hardware Trojan is inserted.
Hardware Trojans are categorized according to the way they are inserted. An original detection circuit is illustrated in Fig. 5, where PATH represents a chosen path and D denotes an added circuit for Trojan detection with the frequency
$$F=\frac{1}{2\times N\times D}$$
1
where N represents the number of inverters, and D represents the delay of a single inverter.
Based on the original detection circuit, Trojan detections are classified into two types according to the added path configuration. A path is on a single route in Type 1, while a path is across multiple routes in Type 2, and both types are illustrated as follows.
Path is on a single route, and Type 1 is further categorized into three modes below.
As illustrated in Fig. 6a, a path is inserted between the input and PATH. Taking into account the added path, the frequency of the detection circuit is modified as
$$F=\frac{1}{2\times {(D}_{ip}+{D}_{p}+{D}_{d})}$$
2
where Dip, Dp and Dd represent the delay between the input and PATH, the delay of PATH and the delay of the added inverters, respectively.
As illustrated in Fig. 6b, a path is inserted between the output and PATH. Taking into account the added path, the frequency of the detection circuit is now modified as
$$F=\frac{1}{2\times {(D}_{op}+{D}_{p}+{D}_{d})}$$
3
where Dop, Dp and Dd represent the delay between the output and PATH, the delay of PATH and the delay of the added inverters, respectively.
Mode 3 is further classified into five cases, and the frequency is now modified as
$$F=\frac{1}{2\times {(D}_{ex}+{D}_{p}+{D}_{d})}$$4
where Dex, Dp and Dd represent the delay of the added path, the delay of PATH and the delay of the added inverters for detection.
As illustrated in Fig. 6c, a path is added inside PATH in case 1, is added outside PATH in case 2, is added within the detection circuit in case 3, is added between the detection circuit and input/output in case 4, and is added inside the detection circuit and PATH in case 5.
Not as in Type 1, a path is added between PATHs. As illustrated in Fig. 6d, Type 2 is further categorized into 8 cases, that is, a path is added between input 1 and input 2 in case 1, is added between output 1 and output 2 in case 2, is added between input 1 and output 2 in case 3, is added between PATH 1 and PATH 2 in case 4, is added between input 1 and PATH 2 in case 5, is added between output 1 and PATH 2 in case 6, is added between the detection circuits D1 and D2 in case 7, and is added between D1 and PATH 2 in case 8.
As explicitly stated previously, paths are added across PATHs, meaning that it is rather difficult to analyze the frequency of Type 2 cases. Besides, added paths in either type are found to demonstrate a strong effect on the frequency.
3.3 Detection Circuits for Series and Parallel Configurations
Detection circuits are categorized into two types according to the way they are configured, i.e. series, parallel and mixed configurations, and are detailed in turn as follows. Illustrated in Fig. 7 is the configuration of an original detection circuit.
Firstly illustrated is the series configuration, and is then the parallel configuration which is further categorized into two cases. A mixed configuration is finally described.
Series configuration is illustrated in Fig. 8, and all the PATHs are connected in series. A loop is formed by a detection circuit D1 and the PATHs so as to detect a hardware Trojan.
Parallel configuration is further classified into two types according to the configuration of added paths. A path is added to a single PATH in Type 1 configuration, while is added between PATHs in Type 2 configuration.
It is assumed that a hardware Trojan is inserted into a single PATH, and a detection circuit is built across each PATH accordingly, as illustrated in Fig. 9a. However, Fig. 9a can be simplified into Fig. 9b, due to the fact that there is a frequency change once a hardware Trojan is inserted into an arbitrary PATH.
As illustrated in Fig. 10a, a hardware Trojan is inserted into a path, shown in blue, between PATHs. In this context, there is no way that the inserted Trojan can be detected using the configuration in Fig. 10a, but instead can be detected using the configuration in Fig. 10b where a detection circuit Dex, shown in red, is inserted into the blue path.
The mixed configuration is finally illustrated in Fig. 11, where a mixture of the above-stated series and parallel configurations is employed for hardware Trojan detection.
3.4 Algorithm
In a large-scale integrated circuit, there are tens of thousands of paths. Therefore, path selection is seen as critical for the circuit detection performance optimization.
3.4.1 A Brief Flowchart
As illustrated in Fig. 12, a Verilog file is first read for getting the configuration information of a circuit. Subsequently, matrices are built for path search using the Verilog file, and path match is performed to locate the optimal path and then to assign the input nodes to the chosen path. The above steps comprise the path tracking algorithm herein, while the rest is referred to as the multiplexer match algorithm aiming to improve the coverage in an attempt to reach a 100% detection.
As illustrated in Fig. 13, a Verilog file contains the information on each gate and its inputs. A total of 2 matrices are created using the Verilog file.
The first of the two matrices clearly specifies the configuration between nodes, according to which path tracking is performed until all the edges are detected. A logic 0 and a logic 1 represent the existence and non-existence of interconnection between nodes, respectively. The second matrix clearly specifies the configuration between nodes and inputs, due to which path match can be performed efficiently. A logic 0 and a logic 1 in this matrix represent the same things as in the first matrix. The “path search” step, illustrated in Fig. 12, involves the first matrix.
3.4.2 Path Tracking Algorithm
Path tracking is performed as a prerequisite of the “path match” step, and is illustrated as follows.
Line 5 in algorithm 1 performs the intersection of a prebuilt matrix containing the information on the node connections and sought paths, as illustrated in Fig. 14, and then locates the path with the greatest number of intersections.
Line 7 indicates the number of edge traversals using the first matrix, as listed in Table 3.
Subsequently, lines 15–21 perform the intersection of the node configurations and path, as illustrated in Fig.
14. Paths with the intersection containing the largest number of elements are chosen, as illustrated in Table
4.
Path tracking is optimized using Table 4, and is described as follows. Path with the least number of edge traversals is chosen for optimization, since it is likely to have an inadequate number of inputs. In this case, path 4 is chosen for the reason that merely edges 3 and 6 are traversed.
Line 22 assigns the chosen paths to an input using the second matrix, as shown in Table 5.
Table 5
Connections between inputs and nodes
Input
|
Gate
|
1
|
1
|
2
|
3
|
3
|
1, 2
|
6
|
2
|
7
|
4
|
As illustrated in Table 4, node 2 is the first node in path 4, and a corresponding gate is chosen. In this case, two inputs are available for choice, either of which can be taken to form a path and a ring oscillator-based detection circuit accordingly.
Lines 23–25 delete part of the chosen inputs, edges and paths, constituting a detection circuit, to avoid repetition, meaning that an input is unlikely to be assigned to two different paths. For instance, deletion of path 4 and input 6 gives Tables 6 and 7.
Table 7
Influence of deleting input 6
Input
|
Gate
|
1
|
1
|
2
|
3
|
3
|
1, 2
|
7
|
4
|
The path tracking algorithm terminates once the following conditions, i.e. those listed on line 9, are fulfilled.
Condition 1: All the edges are traversed, while a number of inputs may not get involved.
Condition 2: Contrary to condition 1, all the inputs are involved, while not all the edges are traversed.
Condition 3: Part of the edges cannot be traversed, using the remaining inputs.
Condition 1 is detailed as follows. It is that all the edges are covered by the paths, meaning that a hardware Trojan detection may not involve all the inputs. Condition 1 is further classified into two cases. In the first case, a Trojan is maliciously inserted right at the input of a circuit, and the introduction of a ring oscillator requires a multiplexer, leading to a rise in the cost. In contrast with the first case, there is no point to handle the second case.
Condition 2 is due to the shortage of inputs. It is that the inputs are all involved, while not all the edges are traversed, meaning that the path match can be performed by no means anymore. There are solutions to the hardware limitation, e.g. use of alternative multiplexers, while the issue is not addressed herein.
Condition 3, as opposed to condition 2, frequently occurs in large scale circuits, and is simply due to a shortage of edges.
The above steps are illustrated as a flowchart in Fig. 15, where path match mechanism is highlighted grey. To begin with, paths are chosen from those given in the “path search” step, and the output of the final step is determined as the path for building a ring oscillator.
3.4.3 Multiplexer Match Algorithm
An algorithm, designated as the multiplexer match algorithm and listed below, is developed to improve the coverage, since a 100% coverage cannot be reached by a single use of the above-stated path tracking algorithm, and the use of a multiplexer is found to be a key factor in the determination of the coverage.
Line 29 gives the value of N as a function of the number of paths involving an input, and line 30 specifies the required multiplexer. For instance, an 8-to-1 multiplexer is required in the case of UIN = 7.