Huan Zhang,Jiliu Zhou,★and Xi Wu

1College of Computer Science,Sichuan University,Chengdu,610065,China

2School of Computer Science,Chengdu University of Information Technology,Chengdu,610225,China

ABSTRACT In hardware Trojan detection technology,destructive reverse engineering can restore an original integrated circuit with the highest accuracy.However,this method has a much higher overhead in terms of time,effort,and cost than bypass detection.This study proposes an algorithm, called mixed-feature gene expression programming, which applies non-destructive reverse engineering to the chip with bypass detection data.It aims to recover the original integrated circuit hardware,or else reveal the unknown circuit design in the chip.

KEYWORDS Hardware Trojans; Trojan detection; mixed-feature; gene expression programming

1 Introduction

The term hardware Trojan refers either to a particular circuit module deliberately implanted or changed during the process of designing or manufacturing an integrated circuit (IC), or to an unintentional design defect in the IC [1-5].Once activated, the Trojan may change the function or specifications of the IC, which may cause leaking of sensitive information, a decrease in performance, or even irreversible damage to the IC [6-9].

In the global semiconductor supply chain, the traditional security strategy of implementing protection based on the underlying hardware, is no longer valid [1].As shown in Fig.1 [2],untrusted entities participate, directly and indirectly, in all stages of the lifecycle of electronic devices and ICs.This leads to hardware security vulnerabilities in the chain of design, manufacturing, testing, deployment, and application [1,2].In the design and production processes,attackers are capable of implanting Trojans on target chips at any stage, through various methods.The vulnerabilities further enable the attackers to tamper with the original design, reduce circuit performance, monitor, control, and wage denial of service, and disclose confidential information that may cause irreversible damage to IC [3,4].

In today’s hardware Trojan detection technology [1-9], destructive reverse engineering [1,3,10-12] restores the original IC to be detected with the highest accuracy, but it incurs a great deal of time, effort, and money, and the chip will be destroyed after detection.Therefore, such application of detection technology has been limited to sampling or replication of a specific type of chip.Bypass detection [13-19] determines if an IC contains a Trojan by analyzing the bypass signals, such as timing, power, electromagnetics, and heat.This detection technology is considered as perhaps the most effective because it does not damage the chip and only a relatively small amount of data and resources are required.

Figure 1: Threats in the IC and IP supply chain

Unlike some previous work that researched evolvable hardware [20-26] using evolutionary algorithms, this paper proposes an evolutionary algorithm called mixed-feature gene expression programming (MF-GEP) and attempts to find the original IC.The algorithm can be evolved by using a single circuit component or a group of circuit structures as the node and mixing multiple features into a single operator.

2 Related Works

2.1 Hardware Trojan

2.1.1 Composition and Attack Mechanism of Hardware Trojan

A hardware Trojan primarily consists of two components: the trigger logic and the payload.A model of the structure of a hardware Trojan is shown in Fig.2.In this model, the payload is activated by the trigger logic through monitoring the input signal, data/control bus, register status,or a set work time.The payload is responsible for executing the attack.

Figure 2: A hardware Trojan modifies signal S to S’when triggered [3]

2.1.2 Destructive Detection Methods

Destructive detection methods usually use destructive reverse engineering to decapsulate an IC and obtain images of each layer, so as to reproduce and verify the trusted design of the final product [1,3,10-12].However, the process of reverse engineering is irreversible, which means an IC can no longer be used once the intrusion process is completed, and only the information of a single IC sample is available [7-9].

Courbon et al.[10] proposed a fast-intrusive technique, which divided the IC to be tested into regions, and extracted images of each region by scanning before multiple images were stitched to reproduce the original design.Although this invasive method only works for hardware Trojans implanted by modifying functional units at the manufacturing stage, it significantly decreases the time and cost of the reverse process.Bhasin et al.[9,10] proposed the use of machine learning methods, such as support vector machine (SVM) and clustering (K-means), to identify an IC with no hardware Trojans.

The specific operation process of the SVM method is depicted in Fig.3.This has been modified from [11].

Figure 3: Hardware Trojan detection based on SVM

The author uses the golden layout ofNchips to classify parameter values with grid size and noise margindnmas input.First, the images of each layer ofNchips are obtained.Then, each layer of the chips is divided into a non-overlapping grid based on the obtained images.The size and noise margindnmof each grid are tested in the classification conditions.These grids are used to train the classifier and are subsequently classified as Trojan-free (TF) or Trojan-inserted (TI)through SVM.Finally, the classification results are used to identify whether the chip contains a Trojan.

2.1.3 Logic Test and Bypass Analysis Method

The main goal of the logic test method is to activate a hardware Trojan by applying function,structure, or random test vectors, and then compare the response result with the correct one [1,7].However, by devising rare triggering conditions, attackers can escape traditional functional and structural tests during production testing.In addition, it is not practical to list all of the state nodes and gate circuits inside the IC.Methods based on logic testing cannot detect Trojans that do not aim at tampering with the data or functions of the original circuit, but can detect an attempt to disclose confidential information through antennas or to modify design specifications [6].

The bypass analysis method detects hardware Trojans through the parameters of an IC during normal operation, such as delay [14], power consumption [13,15], thermal radiation [16], and electromagnetic [17,18].The method makes full use of the features of changed bypass information that are caused by additional circuits or hardware Trojans, which compensates for the lack of logic test [1,3,9,19].However, one of the biggest challenges of this method is that bypass information analysis techniques assume a comparable “golden model,” which is often difficult to achieve in practical applications.

2.2 Evolvable Hardware

The concept of evolvable hardware (EHW) was initially proposed in 1993 by Hugo de Garis while at the Advanced Telecommunications Research Institute in Japan and scientists from the Swiss Federal Institute of Technology.EHW aims to make use of the reconfigurable internal structure of programmable devices, as well as the capabilities of the evolutionary algorithm in combinatorial optimization and universal search.The algorithm can help to locate the structure of the bit string combination of programmable devices for specific tasks, which obtains the hardware circuit with expected functions [21-27] through programming and configuration during the programmable periods.

For example [22], Fig.4 illustrates the array of logic cells, and Fig.5 shows its genotype.

Figure 4: A digital circuit encoded within a genotype by an array of logic cells

Figure 5: The genotype with respect to the rectangular array of logic cells

Xie et al.[27] proposed a two-phase EHW framework, which consists of an evolution phase based on an express tree genetic programming (ETGP) algorithm and an optimization phase based on a mining frequency digital circuit (MFDC) algorithm.It is believed that the application of GEP to EHW can rapidly generate the optimal solution of an evolutionary circuit.

2.3 Introduction to GEP

Gene expression programming (GEP) [28] follows the basic steps of evolutionary computation(EC), which combines the advantages of genetic algorithms and genetic programming.Genetic material consists of two kinds of symbols: terminators and functions.A gene consists of a linear,fixed-length string of symbols and the code for expression trees, in different sizes and shapes.A chromosome can be composed of a single gene or multiple ones, decoded to map as a candidate solution for problem response.

Fis the set of functions, andTis the set of terminals.GEP’s gene contains a head and a tail.The head contains symbols that represent bothFandT, whereas the tail only containsT.For each problem, the length of the headhis chosen, and the length of the taileis a function ofh.The number of arguments of the function with more argumentsn(also called maximum order) is evaluated by expression 1:

For example, consider a gene for the set of functionsF={+,-, *, /, Q}and the set of terminalsT={a,b}.In this case,n= 2, and ifh= 10, thene= 11, and the length of the gene is 21.String 1 describes such a gene (the tail is shown in bold).

+Q-/b*abQbabababbaaabString 1

Fig.6 shows the expression tree (ET) decoded from String 1.

Figure 6: The expression tree decoded from String 1

The algebraic expression represented by Fig.6 is

The redundant symbols in the tail are discarded directly.Then GEP can use fixed-length encoding to express different sizes and shapes of expression trees.

3 Using GEP to Represent Circuit

GEP has performed well in mining association rules, clustering, classification rules, time-series predictions, and sunspot predictions [29-32].

As the structure shows, GEP performs well in resolving tree-structured problems.In other words, if one circuit can be represented as a tree-shaped structure withnleaf nodes, it can be described directly with GEP.The logic circuit of the 6-in/1-out in Fig.7a can be easily represented in an ET in Fig.7b, which replaces the logic gate function with the logic symbol.The effective gene in GEP is shown as String 2.

And,And,And,A,Not,And,And,B,C,Not,E,F,DString 2

Figure 7: (a) The 6-in/1-out circuit represented by String 2 and (b) ET of the circuit shows in (a)

In GEP, uppercase letters represent operators and lowercase letters represent terminators.In this paper, however, we use the name string of the logic gate to represent logic gate, and uppercase letters to represent input parameters.The purpose of this modification is to facilitate the use of circuit simulation software.

However, if only logical values are used to represent the circuit, there would be too many isomorphic situations, For example, the circuit and its ET in Fig.7 can be replaced with the circuit and the ET in Fig.8.

Figure 8: (a) A circuit isomorphic to Fig.7 and (b) ET of the circuit shows in (a)

String 3 describes the corresponding effective gene of Fig.8.

And,A,And,Not,And,B,C,And,Not,And,D,E,FString 3

The two circuits are fully equivalent in terms of logic values, and both are shown in expression (3):

This example is only for the logic value of the circuit.A similar situation exists in terms of bypass information detection, and many different circuit structures could result from any single bypass information, which is referred to asIsomorphicin this paper.

Therefore, if a circuit is described only by logical values or a certain kind of bypass information, the circuit structure cannot be confirmed because of so much isomorphism.This paper proposes an algorithm called mixed-feature GEP (MF-GEP), which represents multiple circuit features by using the same structure in GEP.This algorithm can reduce the number of isomorphic circuits and can be used to detect hardware Trojans.

4 Formal Definition of Trojan Circuit

For a circuitR, we provide the following symbols:

LetA={Ak |k=1,...,c}be the set of allcfeature values that can be tested onR.

ik =[i1,i2,...,in]is the input value vector corresponding to feature valueAk, andnis the number of input parameters of the circuit.

ok =[o1,o2,...,om]is the output value vector of input vectorikcorresponding to circuitR,denoted asok =R(ik), andmis the number of output values ofR.

Ik ={ik |k=1,2,...,d}is the domain ofik,Ok ={ok |k=1,2,...,d}is the value domain ofIk.

We provide the following definitions:

Def 1

For two circuitsRS, if there is a feature value setAk∈A:

For ∃ik∈Ik, there isR(ik)=S(ik).

Then we call circuitsRandSthe same-valued isomeric circuits (SVIC) on featureAkfor input vectorik.

Def 2

For ∀ik∈Ik, there isR(ik)=S(ik).

Then we call circuitsRandSthe full same-valued isomeric circuits (FSVIC) on featureAk.

Def 3

For ∃Ik⊂Ik, there are

Then we call circuitsRandSthe part same-valued isomeric circuits (PSVIC) on featureAk.

Although Strings 2 and 3 represent two different circuits, they are exactly the same in the logical value test, and both represent the circuits in expression (2).According to Def 2, Strings 2 and 3 are FSVIC in logical values.However, it is always possible to find a certain feature (such as current) that makes Strings 2 and 3 PSVIC.Therefore, Strings 2 and 3 are considered as PSVIC.

A formal definition of a Trojan circuit is as follows:

Def 4:Definition of Trojan Circuit

If the circuitsRandSmeet the following conditions, we call circuitRa Trojan circuit with a Trojan added to circuitSif:

(1)Rclaims it is circuitS.

(2) In fact,Ris one of the PSVICs ofS.

For the input domainI:

(1) There are two sets ofXandY,X∩Y=ΦandX∪Y=I.

(2) For ∀i∈X, there isR(i)=S(i), and a Trojan will not be triggered.

(3) For ∀i∈Y, there isR(i)S(i), and a Trojan will be triggered.

The smaller the scale ofY, the more difficult it is to detect the difference betweenRandS,and the deeper the Trojan is.

5 Mixed-Feature GEP

In order to make setYin Def 4 easier to find, multiple features of the circuit were detected at the same time.Although the detection results of each feature value can build many FSVICs,different FSVICs of different features will form some PSVICs, of which the same part is possible in the real circuit.

Fig.9 shows a Not gate designed by a triode.It is used as an example to illustrate the concept of a mixed-feature GEP algorithm.

Figure 9: A Not gate designed by triode

· Feature Value 1:

In digital logic terms, the description of this circuit is:

· Feature Value 2:

In terms of voltage, the description of this circuit is:

whereVSHrepresents the higher threshold and lower potential limit of “1” in the circuit, andVCESrepresents a saturation voltage drop of the triode.

· Feature Value 3:

In terms of current, the description of this circuit is:

whereNis the magnification of the current.

In addition, there are a variety of other bypass information detection items, such as delay and spectrum.

With any of the above three feature values, the circuit structure cannot be determined.However, it is possible to determine the circuit structure if the three features are combined.

In GEP, an operator represents only one computation.A GEP individual only represents a description of one feature value and obtains an unlimited number of isomorphic circuits.It is impossible to determine the actual circuit structure.

The MF-GEP proposed in this paper combines the test results of multiple feature values on a circuit into a single function representation, which integrates them into a composite function, i.e.,a function that represents multiple calculations at the same time.Then it evolves representations close to the original circuit by using GEP’s functional evolutionary ability.

Detection values are included in a function.The input comes from multiple feature values and the output is a vector, like the Not-gate circuit.In GEP’s ET, it is still represented by “Not,”but the implication becomes the calculation of the vector below:

whereAk (k=1,...,n)is the input value of a type of feature detection, andFk (Ak)(k=1,...,n)is the result of this feature value detection corresponding to input valueAk.

However, in an electronic component, each feature value should have a different importance.So, each member of this vector should be multiplied by a weight:

For normalization, it can be specified as

For example, corresponding to this Not gate circuit, the symbol Not indicates the following meaning:

whereArepresents the logical value (1 or 0) by the voltage entered at pointA,VArepresents the input voltage of pointA, andCArepresents the input current of pointA.[0.4,0.3,0.3]is the weight vector.

Therefore, when using GEP evolution, a single symbol Not also represents multiple feature values that are not associated with each other.

6 Experiments

6.1 Experimental Settings

In this paper, four groups of experiments (Experiments 1-4) were designed initially.Later, in order to verify the new problems in Experiments 1-4, Experiment 5 was added.As comparison experiments, most of the parameters and fitness functions are exactly the same.

6.1.1 Parameters

The circuit has multiple inputs and only one output.Experiment 1 used one feature, Experiments 2 and 3 used two features, Experiment 4 used three features, and Experiment 5 used two features.The three features are logical value, voltage value and current value.The GEP parameters of all the experiments are exactly the same.Tab.1 lists the GEP parameters.

Table 1: Experiment parameters

6.1.2 Fitness Functions

The feature data includes logical data, voltage data, and current data, and each has its respective fitness function:

(1) Logical fitness function:

whereNis the amount of test data,is the logical value calculated from the expression represented by the individual, andyiis the actual logical value in the test data.The range ofF1is now discussed as follows:

Then

Then the maximum value ofF1is 1.

b) Because of the logic value, the worst case is that everyis only againstyi, then every|-yi|(i=1,...,N)equals 1.There is:

Then

Then the minimum value ofF1is 0.

c) Suppose there are two GEP individuals,G1andG2.For the same set of test data,

ForG1, there aremequal toyi..

ForG2, there arenequal toyi.(0 ＜m ＜n ＜N).

ForG1, a rearrangement ofleads to=yiwheni=1,...,m, then

ForG2, a rearrangement of,yi) leads to=yiwheni=1,...,n, then

Becausem ＜n, soF1(G1)＜F1(G2).

Therefore, the conclusion can be drawn as follows:

(i) The range ofF1is in[0,1].

(ii) With the improvement of the matching degree between the calculated valueand the tested valueyi, the value ofF1increases monotonically.

(2) Voltage fitness function

Nis the amount of test data.is the voltage value calculated from the expression represented by the individual.yiis the actual voltage value in the test data.(VCC-VDD)is a fixed value.IfVmx=(VCC-VDD), thenF2can be defined as

Then

Then the maximum value ofF2is 1.

b) The worst case is that everyhas the max distant to theyi, which means that every-yi |=Vmx (i=1,...,N).Then

Then the minimum value ofF2is 0.

c) Suppose there arek(0≤k ＜N)equal toyiin a GEP individualG.A rearrangement ofyi) leads to=yiwheni=k+1,...,N, then

Then,

Then

When

Then

d) Suppose there are two GEP individuals,G1andG2.

ForG1,k=m, and forG2,k=n,(0 ＜m ＜n ＜N).The function forms ofF2(G1)and F2(G2)are shown in Fig.10.

Figure 10: The function forms of F2(G1)and F2(G2)

Therefore, we can draw the conclusion that:

(i) The range ofF2is in[0,1].

(ii) If individualG2is more similar to the destination circuit thanG1, there isF2(G2) ＞F2(G1).

(3) Current fitness function

Nis the amount of test data.is the current value calculated from the expression represented by the individual.yiis the actual current value in the test data.is the average ofy.SSEis residual sum of squares.SSTis sum of squares of deviations.F3is the square of the multiple correlation coefficient in statistics, whose value is in [0, 1].

(4) Individual’s fitness

According to the previous description of the algorithm, the individual’s fitness should be a combination of the three fitness functions, and therefore the individual’s fitness is defined as:

ciis the weight of correspondingFiin final fitness.The sum ofciis 1:

If we set the weight vector

then

6.2 Experimental Results

Fig.11 shows a circuit that has no Trojan.

Its Boolean expression is:

The circuit makes the computation:

After several logic gates are added to the circuit of Fig.11, it becomes a circuit with Trojan(Fig.12).In the new circuit,Ywill also get a value of 0 when(ABCD)2=7:

Figure 11: A circuit has no Trojan

Figure 12: The circuit formed by injecting Trojan into the circuit shown in Fig.11

Its Boolean expression becomes:

String 4 describes the corresponding effective gene of Fig.12.

Or,A,Or,And,And,B,And,B,And,Not,D,C,Not,C,DString 4

Only a portion of the values can be tested if there are too many pins.The input value used to activate the Trojan(ABCD)2=(0111)2may be missed at this time.In the following experiment,the input value(0111)2will not be provided, and the output will be determined by the evolved circuit.

Four groups of experiments were designed using different provided values and weight vectors.Considering that the logic values are first required to be correct in the circuit, the voltage and current values must be based on the correct logic values in order to make sense.The individual’s fitness is a combination of several data, in which the proportion of logical value is larger.

6.2.1 Experiment 1

Tab.2 lists the setting of Experiment 1.None of the 100 exercises were able to discover the Trojan circuit if only logical values were provided.Fig.13 shows some typical results.

Table 2: Setting of Experiment 1

Figure 13: (a) One of the circuits evolved by mixed-feature GEP in Experiment 1, (b) Another circuit evolved by mixed-feature GEP in Experiment 1, and (c) The 3rd circuit evolved by mixedfeature GEP in Experiment 1

The simplified Boolean expression of all the circuits above is:

6.2.2 Experiment 2

Tab.3 lists the setting of Experiment 2.None of the 100 exercises were able to discover the Trojan circuit if both logical values and voltage values were provided.Fig.14 shows some typical results.

Table 3: Setting of Experiment 2

Figure 14: (a) One of the circuits evolved by mixed-feature GEP in Experiment 2, (b) Another circuit evolved by mixed-feature GEP in Experiment 2, (c) The 3rd circuit evolved by mixed-feature GEP in Experiment 2, and (d) The 4th circuit evolved by mixed-feature GEP in Experiment 2

The simplified Boolean expression of all the circuits above is:

A Trojan still cannot be found, although both the logical value and the voltage value were provided.The reason is that in digital circuits, the logic value is expressed in the form of voltage values.For example, a voltage value less than3Vis considered to be0, and one that is greater than3Vis considered to be1.Therefore, the choice of logical value and voltage value as feature values on this issue is as same as if only the logical value were provided.

6.2.3 Experiment 3

Tab.4 lists the setting of Experiment 3.During the 100 exercises, the Trojan circuit was discovered 72 times when logical values and voltage values were provided.Fig.15 shows some typical results.

Table 4: Setting of Experiment 3

The simplified Boolean expression of both Figs.15a and 15b is:

The equivalent circuit has been discovered, although the original circuit was hidden.

Fig.15c is a failed result in finding the right circuit.Its Boolean expression is:

Figure 15: (a) One of the circuits evolved by mixed-feature GEP in Experiment 3, (b) Another circuit evolved by mixed-feature GEP in Experiment 3, and (c) The 3rd circuit evolved by mixedfeature GEP in Experiment 3

6.2.4 Experiment 4

Tab.5 lists the setting of experiment 4.During the 100 exercises, the Trojan circuit was discovered 67 times when all three feature values were provided.Fig.16 shows a different result.

Table 5: Setting of Experiment 4

Figure 16: Typical circuit evolved by mixed-feature GEP in Experiment 4

Its simplified Boolean expression is:

A circuit equivalent to the original circuit has been found.The equivalent circuit has been discovered even though the original circuit was hidden.

In this group of experiments, some wrong circuits were found by the failed evolution.As shown in Fig.17, their Boolean expressions are:

Figure 17: (a) One of the false results in Experiment 4 and (b) Another false result in Experiment 4

Although three feature values were used in this group of experiments, the efficiency in discovering the Trojan was similar to that in Experiment 3, which used only two feature values.This is because the logical value itself is expressed in the form of voltage values and the three feature values are equal to the two feature values.

6.2.5 Experiment 5

As discussed in Experiments 2 and 4, in digital circuits, the logical value is expressed in the form of voltage value, e.g., a voltage value less than 3V is referred to as 0, while a voltage value 3V and above is considered to be 1.Therefore, the result of using the logical value as the feature value should be similar to that of the voltage value.To verify this hypothesis, Experiment 5 is designed as a control test to Experiment 3.Tab.6 shows the parameters and results.It differs from Experiment 3 in the replacement of the logical value by the voltage value, and the modification of the fitness function page accordingly.

Table 6: Setting of Experiment 5

We can see that in 53 of the 100 experiments, results equivalent to Trojan circuits were obtained, but these circuits failed to make breakthrough findings in Experiments 3 and 4.However, several false circuits were found, as shown in Fig.18.The Boolean expressions are:

Experiment 5 shows a lower probability in detecting Trojan circuits than Experiment 3.Nevertheless, the result is acceptable considering the randomness of evolutionary calculation.Results indicate that voltage data and logical value data in the mixed-feature GEP algorithm produce similar results.This verifies the hypothesis in Experiments 2 and 4 that two feature values are inter-replaceable in the algorithm if there is a simple correlation between them.Therefore,the maximization of variance between feature values helps to improve the effectiveness of the algorithm when the simple and direct correlation is uncertain.

Figure 18: (a) One of the false results in Experiment 5 and (b) Another false result in Experiment 5

7 Conclusions

This paper proposes a mixed-feature GEP (MF-GEP) algorithm in which multiple feature values were fused into the same operator.There is a specific probability that Trojan circuits could be detected by MF-GEP, which automatically discovers the evolutionary power of mathematical formulas.The fewer features that are used, the higher the efficiency of the GEP evolution, but the conclusion is in wider disparity from the real circuit.At the same time, as the number of features used increases, the efficiency of GEP evolution decreases, but the conclusion drawn gets closer to the real circuit.However, if there is a direct conversion relationship between the multiple feature values used, these values can be considered as one and the accuracy of MF-GEP evolution will not be increased.

Funding Statement:This work was supported by the National Key Research and Development Program of China (Grant No.2018YFB1502803).

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.