TRAP-GATE: A Probabilistic Approach to Enhance Hardware Trojan Detection and its Game Theoretic Analysis

Abstract

Rescuing Hardware from malware attacks is a great challenge today. Moreover detecting the presence of malicious intrusion using low-cost techniques is very challenging especially when it is believed that hardware Trojans are integrated into the rarely excited nodes. Though logical testing is admitted to be the accurate way to check the functional correctness of the circuit, the method becomes inefficient for circuits requiring humongous number of test patterns to activate the hardware trojan. This paper proposes a probabilistic approach to generate a set of test patterns that activate the Trojan explicitly by observing the incorrect responses to the applied test patterns. Our experimental result in ISCAS’85 benchmark circuits show that the test patterns generated by our approach enclose all nets where there is a high chance for trojan insertion. We stress that though our results are circuit specific, the proposed approach is generic and hence it can be applied to any digital circuit. In fact, we demonstrate that for the C880 circuit, our approach requires only 2¹⁷ inputs to be tested whereas the naive approach needs 2⁶⁰ test patterns. In addition to the experimental results, we use a game-theoretic framework to show the effectiveness of our approach in generating trojan activating test patterns compared to naive and ATPG testing process.

APPENDIX A

1.1 Important Deftnitions in Game Theory

In this section we give a preliminary background on game theory. We briefly describe zero- sum game, types of strategies, payoffs, solution concepts. We always assume that the players are rational who would like to maximize their payoffs.

Game Theory is an approach that helps in decision making. The decision making can be made with respect to the situations viz., Deterministic situation, Probabilistic situation and uncertainty situation. The terminologies used in Game Theory for decision making are players, who are involved in the game and the strategy, which is a course of action taken by the players. The strategy chosen may be pure or mixed strategy. A pure strategy is if the player selects only one strategy and ignores rest of the strategies, where the sum of the probability is one. A mixed strategy is if a player follows more than one strategy and the probability of selection of individual strategy is less than 1. Because the player will select more than 1 strategy and the sum of the total probability is 1 where each probability value will be less than 1. An example for Pure strategy is given in the below Table 8, where the player has chosen the second strategy and sum of the probabilities is 1 (0+1+0 = 1).

Table 8 Table for Pure Strategy

An example for Mixed strategy is given in Table 9, where the sum of probabilities is 1 (0.65 + 0.35 + 0 = 1)

Table 9 Table for mixed Strategy

Payoff matrix is a matrix in which the players are involved and the matrix is formed as in Figs. 6, 7 and 9 based on number of players and the strategy they choose with the payoff. The elements filled in the matrix are with respect to the outcome of different combinations. For an instance, let us consider a matrix where two players are involved and the matrix elements are fill with the payoff value

Fig. 6

Matrix example with payoff

Fig. 7

Matrix for game with Pure Strategy

Here the payoff values of the players are filed with respect to their utilized of resources based on which a probabilistic calculation can be taken place in order to determine the gain or loss of the players. If the outcome is positive then it is the player A’s loss and player B’s gain. In the above matrix the strategic outcome value -40 indicates that it’s the player A’s loss and player B gained.

Principles in Game Theory: There are two different principles in Game Theory, they are maxmin and minmax. The term maxmin means to maximize the minimum guaranteed gain of the player. The term minmax means to minimize the maximum losses. When the maxmin value is equal to minmax value then it is known as Saddle point.

Value of the game is the value of the cell at the saddle point. Zero sum game is when the gain of player A is equal to the loss of player B. An example for the game with pure strategy to find the ameliorated strategies of the players is clearly derived in the following game. Let us consider a game with two players. The below matrix shown in Fig. 10 is formed where each elements of the matrix are filled with the payoff values.

• Step 1: To find the row minimum and the column maximum followed by finding the maxmin and minmax values as shown in Fig. 8

  Fig. 8

  

  Matrix for game with Pure Strategy

  Fig. 9

  

  Matrix for game with Pure Strategy

  Fig. 10

  

  Matrix for game with Pure Strategy

Since maxmin value is equal to minmax value, the value 45 is the saddle point.

• Step 2: To find the maxmin and minmax values (45,45). Player A maxmin value of player A denotes to maximize his gain. Player B minmax value of player B denotes to minimize his loss. Therefore, the value of the game (v) is 45. The optimal probability of Player A and player B is,

$$ {\displaystyle \begin{array}{c}A\left[p1,p2,p3\right]=A\left[0,1,0\right]=0+1+0=1\\ {}B\left[q1,q2,q3\right]=A\left[0,1,0\right]=0+1+0=1\end{array}} $$

A mixed strategic game theory with no saddle point or maxmin point considers the following payoff matrix with respect to player A and B. The way to solve it optimally with an instance is given below,

7ƒ = 9 (max min = min max). Hence no saddle point and the strategy analyzed is a mixed strategy in Game Theory. Step 1: Find the oddments for row and column.

Step 2: Find the probability. By using oddments,

$$ {\displaystyle \begin{array}{c}\kern6em p1=6/\left(6+2\right)=6/(8)=3/(4)\\ {}\kern6em p2=2/\left(6+2\right)=\\ {}\kern6.00em 2/(8)=1/4q1=4/\Big(4\\ {}\kern6em +4\Big)=4/8=1/2\;q2\\ {} Alternative=4/\left(4+4\right)=4/8=\\ {}\mathrm{method}:\kern1em \;\kern5em 1/2\end{array}} $$

By applying probability formula,

$$ {\displaystyle \begin{array}{l}p1=\frac{a22-a21}{\left(a11+a22\right)-\left(a12+a21\right)}\\ {}=\frac{11-5}{\left(9+11\right)-\left(7+5\right)}=6/8=3/4\end{array}} $$

(1)

$$ {\displaystyle \begin{array}{l}P2=1-p1\\ {}=1-3/4=1/4\end{array}} $$

(2)

$$ q1=\frac{a22-a12}{\left(a11+a22\right)-\left(a12+a21\right)} $$

(3)

$$ {\displaystyle \begin{array}{l}=\frac{\left(11-7\right)}{\left(9+11\right)-\left(7+5\right)}=4/8=1/2\\ {}q2=1-q1\\ {}=1-1/2=1/2\end{array}} $$

(4)

Step 3: Find the value of the game (v). Take 1st column value (9, 5) and oddments of 1st and 2nd row (6,2).

$$ v=\frac{\left({a}_{11}\kern0.5em \ast \kern0.5em oddmentof\;{1}^{st} row\right)+\left({a}_{21}\ast \kern0.5em oddmentof\;{2}^{nd} row\right)}{sumofrowoddments} $$

$$ v=\left(\left(5\ast 6\right)+\left(5\ast 2\right)\right)/6+2=54+10/8=8 $$

Alternatives

$$ v=\frac{\left({a}_{21}\kern0.5em \ast \kern0.5em oddmentof{1}^{st} row\right)+\left({a}_{22}\ast oddmentof{2}^{nd} row\right)}{sumofrowoddments} $$

or

$$ v=\frac{\left({a}_{11}\ast oddmentof{1}^{st} column\right)+\left({a}_{12}\ast oddmentof{2}^{nd} column\right)}{sumofcolumnoddments} $$

or

$$ v=\frac{\left({a}_{21}\ast oddmentof{1}^{st} column\right)+\left({a}_{22}\ast oddmentof{2}^{nd} column\right)}{sumofcolumnoddments} $$

Hence, The strategies of player A = (3/4 , 1/4). The strategies of player B = (1/2 , 1/2). Value of game (v) = 8

To Summarize, Game Theory is a strategic mathematical model of play which can be a non co-operative or a co-operative game between intelligent rational players or decision- makers. Game Theory is a versatile approach that can be applied in any domain where decision making plays a vital role. Game theory originally addressed zero-sum gaming which means the gain of one player will be the loss of other player. Then arrived the co-operative and non-co-operative game of rational and irrational players. A game is considered to be cooperative if the players are enforced externally to a form binding commitments. A game is non-cooperative if the players cannot accord. Cooperative games are analysed through the cooperative game theoretic framework, which focuses on the prediction of affiliation resulting in the collective payoffs. The players’ actions and payoffs can be analysed through Nash equilibrium.

Nash equilibrium in game theory is a concept of evolving solutions for a non-cooperative game involving two or more players in which each player will tend to know the equilibrium strategies of the other players, and no player has anything to gain by changing only their own strategy. If each player has chosen a strategy and no player can benefit by changing strategies while the other players keep theirs unchanged, then the current set of strategy choices and the corresponding payoffs constitutes Nash equilibrium. The Nash equilibrium is one of the foundational concepts in game theory. The reality of the Nash equilibrium of a game can be tested experimentally.