Efficient Activation Method of Hardware Trojan Based on Greedy Algorithm

Yingjian Yan and Xin Chuan(Department of Microelectronics, Institute of Information Science and Technology, Zhengzhou 450001, China)

The globalization and development of the integrated circuit industry has made integrated circuits vulnerable to attacks and modifications from hardware Trojan[1]. Hardware Trojans are triggered, when needed, to steal sensitive information, destroy the circuit, and can cause harm politically, militarily, and economically[2-3]. Therefore, hardware Trojan detection has become a research hotspot in the field of integrated circuit security in recent years. Hardware Trojan detection methods for most studies are compared in Tab.1.

For the self-designed integrated circuits, the method based on the logic testing has better practicability and higher testing efficiency in numerous hardware Trojan detection methods. This is worth further research[4-6]. The goal of hardware Trojan detection method, based on logic testing, is to generate test vector sets that effectively activate the hardware Trojan. Kitsos et al. proposed a hardware Trojan detection method using combinatorial testing[7]. Pei et al. proposed a hardware Trojan detection method based on fast triggering[8]. Voyiatzis et al. proposed a method of effectively triggering hardware Trojan horse[9].

Tab.1 Comparison of the most studied hardware Trojan detection methods

This paper proposes a new hardware Trojan activation method to detect the hardware Trojan in the circuit. The proposed method , based on greedy algorithm, generates test vector sets of different combination correlation coefficients to detect hardware Trojans. The experimental results shows that the proposed method can effectively activate the combinatorial hardware Trojans, improve the activation probability of the hardware Trojan, and verify the effectiveness and practicability of the method.

1 Research on Hardware Trojan Detection

1.1 Hardware Trojan detection model

The combinational hardware Trojan is a type of hardware trojan with advantages of smaller area and better controllability. Attackers often insert such hardware Trojan into the cipher chip circuits to destroy the normal work of the circuit and make the circuit leak information, such as advanced encryption standard (AES), SMS4 and other encryption algorithm circuit. The detection method based on logic testing has low cost and is not affected by the detection environment. It is a practical and effective method for detecting the combinational hardware Trojan in the self-designed circuits[4,10].

It is difficult for attackers to control the nodes inside the circuit directly. Therefore, the attacker may combine some bits of the circuit into the hardware Trojan horse trigger to achieve controllable attack. Fig.1 depicts an example of a combinational hardware Trojan. The original circuit is a six-input (Ii,i=1,2,3,4,5,6) and function circuit module. The module is inserted into a combinatorial hardware Trojan which consists of one AND gate and one XOR gate. The AND gate is the trigger, the length of activation vector is 2 and the XOR gate is the payload. When input bitsI3I6are set to “01”, the hardware Trojan is activated, the output value is tampered by non-value of the correct output.

Fig.1 Example of combinatorial hardware Trojan

During hardware Trojan detection of this module, the output value is observed by applying a test set to the input value. If the output value is different from the standard output value upon comparing the two values, then there is a hardware Trojan in the module. Otherwise, the hardware Trojan does not exist[5]. Therefore, the hardware Trojan detection based on logic testing focuses on generating a test vector set that can activate the hardware Trojan given that the test vector set is of small scale and high efficiency.

1.2 Overview of the greedy algorithm

Greedy algorithm is one of the heuristic algorithms for solving non-deterministic, polynomial, complete, problem (NPC) problems and seeking a better solution[11]. The basic idea of the greedy algorithm is to formulate a greedy strategy based on an initial solution of the problem and gradually approximate the solution target. In the greedy algorithm, the greedy strategy is related to the optimization ability of the algorithm and the quality of the final solution. For each step in the process of solving the problem, the choice of solution is based on the greedy strategy, and the optimal solution is always chosen as the solution of this step. This solution is called the local optimal solution. Choosing the appropriate greedy strategy can obtain better approximation solution and can reduce the complexity of the algorithm.

In hardware Trojan detection based on logic testing, the goal is to generate a test vector setwith small scale and high efficiency. Because this is an optimization problem, the greedy algorithm can be used to find the optimal solution that will generate the test vector set. In this paper, greedy algorithm is used to formulate greedy strategy and generate a test vector set which is used to detect combinational hardware Trojans.

1.3 Research on test vector generation algorithm

If the input of a circuit hasnbits that can be used by the attacker, there will be 2npossible activation vectors[12]. When attackers design hardware Trojans, they need to consider the area, power consumption, concealment and other conditions. When the activation vector is longer, the area and power consumption is higher, and the concealment and controllability is reduced. Therefore, the paper assumes that the attacker does not use an activation vector of length greater than 5 (usually less than 5). Under this premise, the greedy algorithm is adopted to formulate the greedy strategy to generate the test vector set.

Algorithm 1 is the test vector generation algorithm based on the greedy algorithm. There are four parameters:n, the number of parameters in the test vector;t, the combinatorial correlation coefficient (i.e., the longest hardware Trojan activation vector length);us, the uncovered combination array that is calculated according tonandt;ts, the test vector set. The process of generating the test vector set is divided into two steps, the first step is to initialize parameters and calculate theus(line 1 to 2). The second step is to use the greedy algorithm to loop iterations that generate a test vector one by one until the test vector set ts is obtained (line 3 to 15). In the second step, the first vector is generated randomly (line 5). The following vectors are generated by loop iteration and each iterative round could generate a test vector (line 7 to 13). Update the values ofuswhile running the iterations in order to expand the vector. When theusis empty, end the iteration.tsis the final test vector set.

Algorithm1Test vectors generation algorithm

Algorithm2Greedy strategy

Fig.2 Process of the test vector set generation

2 Hardware Trojan Activation Scheme Design in Cryptographic Algorithm

2.1 Target circuits design

In this paper, the hardware implementation of AES symmetric encryption algorithm was used as the original circuit, and hardware Trojans of the different activation length were designed to insert the original circuit. These circuits act as target circuits[13]. The AES module inputs the 128-bit keys (key) and the 128-bit plaintexts/ciphertexts (data_in), outputs the 128-bit ciphertexts / plaintexts (data_out), and controls the encryption or decryption operations of the module through the control signal (en_de).

Fig.3 Hardware Trojan design

The operation of the AES module can be divided into two phases. The first phase is to expand the key according to the input 128-bit keys, and expand sub-keys of 10 rounds. The second phase is to encrypt or decrypt through the control signal (en_de). After 10 rounds of operation, the ciphertext or plaintext is outputed. Fig.3 describes a hardware Trojan. The length of activation is 4, i.e. the trigger logic consists of 4 inputs (21, 79, 97, 119). The load logic is an XOR gate. This function is to make the encryption control bit (en_de) invert. Hardware Trojan will implement denial of service attacks, resulting in AES module cannot be normal operation, the output value will be wrong. In addition, the hardware trojans of the activation length were 5(namely: 3,23,89,107,124), 3(namely: 21,79,114) and 2(namely: 21,114). These were also designed and inserted into the AES module.

Tab.2 Number of combination values for the attackers

2.2 Test vector generation scheme design

In section 1.3, the method of generating test vector set based on greedy algorithm was pro-posed, and the process of generating test vector setts(6, 2) was given whenn=6 andt=2. For the detection of AES cryptographic algorithm circuit, the number of input parameters was set asn=128. According to the proposed generation algorithm, the test vector sets with different combinations correlation coefficients (t=2, 3 and 4 respectively) were generated. Fig.4 is a test vector generation process when the combination correlation coefficientt=2 was used. When the correlation coefficient was taken from other values, the test vector set was generated according to this process.

Fig.4 Process of test vector generation

3 Experiment and Results

3.1 Experimental process

Fig.5 Experiment process

To verify the proposed hardware Trojan detection method, this paper was verified by the experimental process shown in Fig.5. The process mainly consists of three parts. The first part was the original circuit design and hardware Trojan insertion and constitutes the target circuit. The second part was the use of the proposed detection method to generate test vector set. The third part was to obtain the standard reference value by using the software method to implement the cryptographic algorithm.

At first, the paper designed the AES encryption circuit as the original circuit without hardware Trojan infection, combination hardware Trojans with activation length 2, 3, 4, 5 were inserted into the original circuit as target circuits in Section 2.1. Then C language is used to realize the proposed hardware Trojan detection method and generate test vector setts(128,2),ts(128,3) andts(128,4) with input parametern=128,t=2,3,4 as the input of the hardware part and software in Section 2.2. Finally, the software implementation of the AES encryption algorithm was carried out, according to the inputts(128,2),ts(128,3) andts(128,4). The standard results were calculated as reference values, and the hardware and software outputs were compared to determine whether there was hardware Trojan. In the whole process, visual studio was used to compile the C language and generate the test vectors, modelsim was used to verify and simulate, and FPGA was used as the platform of prototype verification.

3.2 Results and discussion

In the process of the experiment, the paper carried out the hardware Trojan detection experiment for the 128-bit AES cryptographic algorithm circuit using the proposed method. Experiments were conducted on two aspects respectively and the results were recorded.

Tab.3 is the data obtained by experiments using the greedy algorithm proposed in this paper, and is compared with the method proposed in Ref. [9]. In Tab.3, the hardware Trojan activation length of the experimental object is 3. This is the trigger unit associated with 3 input bits. The second and third columns is the experimental results to generate test vector sets based on greedy algorithm. The second column shows the length of different test vector sets generated by different combination correlation coefficients. The third column shows corresponding times at which the test vector sets could activate the hardware Trojan. The latter two columns are experimental data obtained by using the method in Ref.[9]. By contrast, although the proposed method of the paper has a longer test vector, it can increase the time that the hardware Trojan was activated, improve the detection success rate, and have higher practicability.

Tab.3 Greedy algorithm vs. Ref. [9]

Tab.4 shows the experimental results obtained for hardware Trojans of different activation lengths, using the proposed method of detection. The first column shows the hardware Trojan activation length, the second column shows the position of the triggers of different hardware Trojans, the last three columns shows times that the test vector sets could activate hardware trojan under different correlation coefficients. Experimental results show that the test vector sets generated by the proposed method can effectively realize the activation of hardware Trojans with different activation lengths and achieve the purpose of detecting hardware Trojan.

Tab.4 Activation number of different Trojans

Therefore, the paper proposes a hardware Trojan activation method based on greedy algorithm, which could effectively activate the hardware Trojan, increase the times that hardware Trojans are activated, has a strong practical value, and a wide range of applications.

4 Conclusion

The paper proposed a hardware Trojan activation method based on greedy algorithm for detecting hardware Trojan. Experimental results show that test vector sets generated using the proposed method could effectively improve probability of hardware Trojan activation and also enhance applicability and practicability of test vector sets. Based on the method proposed in this paper, the two aspects could be studied in future work, respectively detecting sequential hardware Trojans effectively and decreasing the size of test vector sets.

[1] George R. Why we should worry about the supply chain[J]. International Journal of Critical Infrastructure Protection, 2015, 11: 22-23.

[2] Liu Huafeng, Luo Hongwei, Wang Liwei. Survey on hardware Trojan horse[J]. Microelectronics, 2011, 41(5):709-713. (in Chinese)

[3] Niu Xiaopeng, Li Qingbao, Wang Wei, et al. Survey on the hardware Trojan technologies[J]. Journal of Information Engineering University, 2012, 13(6):740-748. (in Chinese)

[4] Wang X, Tehranipoor M, Plusquellic J. Detecting malicious inclusions in secure hardware: Challenges and solutions[C]∥IEEE International Workshop on Hardware-Oriented Security and Trust, Anaheim, CA, USA, 2008.

[5] Li H, Liu Q, Zhang J, et al. A survey of hardware Trojan detection, diagnosis and prevention[C]∥International Conference on Computer-Aided Design and Computer Graphics, Xi’an, China, 2016.

[6] Francq J, Frick F. Introduction to hardware Trojan detection methods[C]∥Design, Automation & Test in Europe Conference & Exhibition, Grenoble, France, 2015.

[7] Kitsos P, Simos D E, Torres-jimenez J, et al. Exciting FPGA cryptographic Trojans using combinatorial testing[C]∥International Symposium on Software Reliability Engineering, Gaithersbury, MD, USA, 2016.

[8] Pei Gen, Shi Chaoyang, Zou Xuecheng, et al. A hardware Trojan detection method based on rapid activation[J]. Application of Electronic Technique, 2016, 42(8):63-66. (in Chinese)

[9] Voyiatzis A G, Stefanidis K G, Kitsos P. Efficient triggering of Trojan hardware logic[C]∥IEEE International Symposium on Design & Diagnostics of Electronic Circuits & Systems, Kosice, Slovakia, 2016.

[10] Kitsos P, Voyiatzis A G. Towards a hardware Trojan detection methodology[C]∥Embedded Computing, Budva, Montenegro, 2014.

[11] Li Ling. Research on SAT-based test generation algorithm for integrated circuits [D]. Harbin: Harbin Engineering University, 2012. (in Chinese)

[12] Tang D T, Woo L S. Exhaustive test pattern generation with constant weight vectors[J]. IEEE Transactions on Computers, 1984, 32(12):1145-1150.

[13] Kumar K S, Chanamala R, Sahoo S R, et al. An improved AES hardware Trojan benchmark to validate Trojan detection schemes in an ASIC design flow[C]∥International Symposium on VLSI Design and Test, Ahmedabad, India, 2015.