Paper 2014/943

Advancing the State-of-the-Art in Hardware Trojans Detection

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

Abstract

Over the past decade, Hardware Trojans (HTs) research community has made significant progress towards developing effective countermeasures for various types of HTs, yet these countermeasures are shown to be circumvented by sophisticated HTs designed subsequently. Therefore, instead of guaranteeing a certain (low) false negative rate for a small \textit{constant} set of publicly known HTs, a rigorous security framework of HTs should provide an effective algorithm to detect any HT from an \textit{exponentially large} class (exponential in number of wires in IP core) of HTs with negligible false negative rate. In this work, we present HaTCh, the first rigorous algorithm of HT detection within the paradigm of pre-silicon logic testing based tools. HaTCh detects any HT from $H_D$, a huge class of deterministic HTs which is orders of magnitude larger than the small subclass (e.g. TrustHub) considered in the current literature. We prove that HaTCh offers negligible false negative rate and controllable false positive rate for the class $H_D$. Given certain global characteristics regarding the stealthiness of the HT within $H_D$, the computational complexity of HaTCh for practical HTs scales polynomially with the number of wires in the IP core. We implement and test HaTCh on TrustHub and other sophisticated HTs.

Note: Included the Explicit vs. Implicit malicious behavior and the probability \alpha which caused several major changes.