Scalable Activation of Rare Triggers in Hardware Trojans by Repeated Maximal Clique Sampling

Hardware Trojans are serious threat to security and reliability of computing systems. It is hard to detect these malicious implants using traditional validation methods since an adversary is likely to hide them under rare trigger conditions. While existing statistical test generation methods are pro...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computer-aided design of integrated circuits and systems 2021-07, Vol.40 (7), p.1287-1300
Main Authors: Lyu, Yangdi, Mishra, Prabhat
Format: Article
Language:English
Subjects:
Algorithms
Benchmark testing
Clique cover
Hardware
Logic testing
Malware
Payloads
random sampling
Sampling
Statistical methods
Statistical tests
test generation
Test pattern generators
trigger activation
Trojan detection
Trojan horses
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Hardware Trojans are serious threat to security and reliability of computing systems. It is hard to detect these malicious implants using traditional validation methods since an adversary is likely to hide them under rare trigger conditions. While existing statistical test generation methods are promising for Trojan detection, they are not suitable for activating extremely rare trigger conditions in stealthy Trojans. To address the fundamental challenge of activating rare triggers, we propose a new test generation paradigm for trigger activation by repeated maximal clique sampling (TARMAC). The basic idea is to utilize a satisfiability modulo theories (SMTs) solver to construct a test corresponding to each maximal clique. This article makes three fundamental contributions: 1) it proves that the trigger activation problem can be mapped to clique cover problem, and the test vectors generated by covering maximal cliques are complete and compact; 2) it proposes efficient test generation algorithms to activate trigger conditions by repeated maximal clique sampling; and 3) it outlines an efficient mechanism to run the clique sampling in parallel to significantly improve the scalability of our test generation framework. The experimental results demonstrate that our proposed approach is scalable and it outperforms state-of-the-art approaches by several orders-of-magnitude in detecting stealthy Trojans.
ISSN:0278-0070
1937-4151
DOI:10.1109/TCAD.2020.3019984