Paper 2014/943

HaTCh: Hardware Trojan Catcher

Syed Kamran Haider and Chenglu Jin and Masab Ahmad and Devu Manikantan Shila and Omer Khan and Marten van Dijk

Abstract

With the growing trend of repeated reuse of existing design components, use of third party IP cores has become a common practice in Electronic Design Automation (EDA) industry. However third party IP cores are known to have potential malwares or hardware trojans which could compromise the security of the whole system. We provide a formal classification of possible hardware trojans according to their different properties and analyze in detail the class coined \textit{XX-St-D-F}, which is the collection of trojans that (1) use \textit{\underline{St}}andard I/O channels to deliver malicious payload, (2) are embedded in an IP core with \textit{\underline{D}}eterministic functionality, and (3) are designed to violate the \textit{\underline{F}}unctional specification. We provide a hierarchy of subclasses $H_{t,1}\subseteq H_{t,2}\subseteq \ldots \subseteq H_{t,d} \subseteq \ldots \subseteq \underset{d \ge 1}{\cup} H_{t,d}=H_t \subseteq \underset{t \ge 0}{\cup} H_t=$\textit{XX-St-D-F}, where $t$ indicates the number of clock cycles between ``activating/triggering'' the trojan and the moment a malicious payload is delivered and where $d$ stands for the number of wires involved in the ``trigger signal''. We show that most of \textit{XX-St-D-F} trojans benchmarked by Trusthub~\cite{trust_hub} belong to $H_{t,d}$ for small $d$ where the $d$ wires are a mix of trojan related wires and the normal core wires. We design new trojans that belong to each of the classes $H_{t,d}$ where the $d$ wires all belong to the hardware trojan itself: the new hardware trojan design universally applies to cores that include the computation of an $XOR$ over $\approx 2^d$ inputs. This analysis demonstrates that the currently found/benchmarked trojans are very likely only the tip of the iceberg. By using the synthesized netlist description of an IP core as input, we introduce a new tool called HaTCh which learns in a precomputation or ``learning'' phase how to add additional ``tagging'' circuitry to the IP core such that, as soon as an embedded \textit{XX-St-D-F} trojan is triggered, the tagging circuitry raises an exception to prevent the trojan from manifesting malicious behavior. We show that HaTCh parameterized for $H_{t,d}$ has zero false negatives among trojans in $H_{t,d}$ and depending on the duration of the precomputation (learning phase) the probability of a non-zero false positive rate can be designed to approach zero. For a sample among the Trusthub~\cite{trust_hub} benchmarks in \textit{XX-St-D-F}, we show a non-zero false positive rate of at most $10^{-5}$ (for $d=1$). The learning phase of HaTCh has a complexity of $O(|Core|^d(\tau + d\ln |Core|))$ where $|Core|$ is the number of wires in the IP core and $e^{-\tau}$ is the probability of non-zero false positive rate. We show how this complexity can potentially be reduced by considering ``interesting'' subsets of $H_{t,d}$, one of which leads to $O(|Core|^3)$ complexity independent of $d$. The tagging circuitry for our sample of benchmarks has area overhead from $0.02\%$ to $7.63\%$ for non-pipelined tagging circuitry, and from $0.02\%$ to $15.25\%$ for pipelined tagging circuitry which is useful for designs having strict timing constraints.

Note: Updates in Section 7.1.2 Non-Zero False Positives