1. LFSR-based Hardware Trojan
Hardware trojans can be classified based on its activation mechanism, trigger and
payload. Basically, executing malicious functions, which can be defined as the payload,
depends on the trigger of the hardware trojan design as shown in Fig. 1. The design of the trigger specifies how stealthy a hardware trojan can be and the
inputs for the trigger can be from the external signal through an antenna or from
internal circuit signals. Once the conditions are met on the trigger logic, it will
send a signal to the payload circuitry to perform the malicious behavior which eventually
activates the hardware trojan. Moreover, hardware trojans can be inserted in different
phase of the integrated circuit (IC) production lifecycle. The proposed hardware trojan
follows these classifications, it employs triggering mechanism and can be inserted
in the design phase of the IC production lifecycle specifically on the third-party
IP cores.
Existing hardware trojans, specifically the timer-based hardware trojan, uses digital
counters as a trigger where it counts the number of clock cycles or the number of
rare events on a certain system and executes the payload whenever the timer reaches
its maximum value or specified number. In (5), instead of using a digital counter, it used linear feedback shift register (LFSR)
and combined with the circuitry of an IP core to have an XORed result from LFSR and
non-malicious internal signals. However, this hardware trojan implementation can be
detected by considering the high number of incoming signals to the output node as
discussed in Section III.
For the proposed hardware trojan, it also employs the use of LFSR, as the trigger
and, instead of incrementing the value using the clock or rare events, it changes
the value according to its feedback polynomial and compared to the predefined pattern.
2. Extending the LFSR-based Hardware Trojan
Using LFSR alone can be comparable as the timer-based hardware trojan given that the
number of the stage is increased to come up with a longer time before the activation
of the hardware trojan. But this way of implementation can be detected using the existing
hardware trojan detection method as discussed in Section III.
Another way of implementing can be done by adding shift register after the LFSR circuit
as shown in Fig. 2(a). The input data from non-malicious internal signals is used to initialize the LFSR
and serve as the combination to be compared on the LFSR state to control the shifting
of the shift register. The size of the shift register is always (n + 2)-bit where
n is the size of the LFSR. The extra 2-bits of the shift register serves as the result
values from shifting the shift register which means that its values change whenever
a shifting occurs. The shifting happens whenever the state value of the LFSR has the
same value with the input signal where input signals are specified non-malicious internal
signals. Otherwise, the state value of LFSR is passed to the n-bit value of the shift
register. Further, the extra 2-bits of the shift register are added to lower the activation
probability. Based on this, Algorithm 1 is proposed. In line 4-6, the value of the
LFSR is always passed to the n-bit value of the shift register to vary its value every
clock cycle. Then in line 8-10, the hardware trojan signal, which is connected directly
to the payload, is triggered when the value of the shift register and the predefined
combination is equal.
3. Activation Probability
In order to avoid detection during functional verification, timer-based hardware trojans
tend to be large in number which could reach at least millions of cycles. In this
assumption, the number of bits of a timer could be approximately twenty bits (since
$10^{6} \approx 2^{20}$) (7), which gave an activation probability of
Input: Non-malicious internal signals
Output: Hardware Trojan Signal
Initial Value: Initial state of n-bit LFSR from input
1 $\quad$for every clock cycle
2 $\quad$$\quad$ if state of n-bit LFSR is equal to the signal input, then
3 $\quad$$\quad$$\quad$ shift (n+2)-bit shift register by 1
4 $\quad$$\quad$ else
5 $\quad$$\quad$$\quad$ set [(n-1):0] value of (n+2)-bit shift register using
6 $\quad$$\quad$$\quad$ the LFSR state
7 $\quad$if value of (n+2)-bit shift register equals to predefined
8 $\quad$(n+2)-bit combination, then
9 $\quad$$\quad$ Propagate the hardware trojan signal
Algorithm 1. Extending LFSR-based Hardware Trojan
$\quad$
Input: Information Flow Graph
Output: Possible Hardware Trojan Candidate
1 $\quad$for each node do
2 $\quad$$\quad$ if nodes l, m, n creates a loop, then
3 $\quad$$\quad$$\quad$ Add l, m, n in a loop group
4 $\quad$for each node in loop group do
5 $\quad$$\quad$ List all immediate node/s except the nodes already
6 $\quad$$\quad$ in the loop group
7 $\quad$for each immediate node do
8 $\quad$$\quad$ if immediate node is common to all nodes in the
9 $\quad$$\quad$ loop group, then
10 $\quad$$\quad$$\quad$ Report loop group as hardware trojan candidate
Algorithm 2. Proposed extended algorithm
On the other hand, for the proposed hardware trojan with n-bit LFSR and (n+2)-bit
shift register, the activation probability can be computed by
where $\left(\frac{1}{2^{n}-1}\right)^{3}$ is the probability that the input signal
is equal to LFSR state and the degree of three signifies the number of shifting to
have (n+2)-bit combination. $\left(\frac{1}{2^{n}-1}\right)$ is the probability that
the [(n-1):0] value of (n+2)-bit shift register is equal to [(n-1):0] value of predefined
combination. Lastly, the $\left(\frac{2^{n}}{2\left(2^{n}-1\right)}\right)^{2}$ is
the probability for the remaining 2-bits to be equal to [(n+2):n] value of predefined
combination.
With 5-bits LFSR and 7-bits shift register, the activation probability is $0.2884
\times 10^{-6}$ which is comparable with the 20-bits timer-based hardware trojan,
but the number of bits used is lesser. Also, the number of bits is intentionally lessened
to prevent from being detected on the existing detection methods.