skip to main content

Explore Research Products in the NSF-PAR

Title: Automated Trigger Activation 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 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 by mapping trigger activation problem to clique cover problem. The basic idea is to utilize a satisfiability solver to construct a test corresponding to each maximal clique. This paper makes two fundamental contributions: 1) it proves that the trigger activation problem can be mapped to clique cover problem, 2) it proposes an efficient test generation algorithm to activate trigger conditions by repeated maximal clique sampling. Experimental results demonstrate that our approach is scalable and it outperforms state-of-the-art approaches by several orders-of-magnitude in detecting stealthy Trojans.  more » « less
Award ID(s):
1908131
NSF-PAR ID:
10182329
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Asia and South Pacific Design Automation Conference (ASP-DAC)
Page Range / eLocation ID:
482 to 487
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ( , Asia and South Pacific Design Automation Conference (ASPDAC))
    null (Ed.)
    Due to globalized semiconductor supply chain, there is an increasing risk of exposing System-on-Chip (SoC) designs to malicious implants, popularly known as hardware Trojans. Unfortunately, traditional simulation-based validation using millions of test vectors is unsuitable for detecting stealthy Trojans with extremely rare trigger conditions due to exponential input space complexity of modern SoCs. There is a critical need to develop efficient Trojan detection techniques to ensure trustworthy SoCs. While there are promising test generation approaches, they have serious limitations in terms of scalability and detection accuracy. In this paper, we propose a novel logic testing approach for Trojan detection using an effective combination of testability analysis and reinforcement learning. Specifically, this paper makes three important contributions. 1) Unlike existing approaches, we utilize both controllability and observability analysis along with rareness of signals to significantly improve the trigger coverage. 2) Utilization of reinforcement learning considerably reduces the test generation time without sacrificing the test quality. 3) Experimental results demonstrate that our approach can drastically improve both trigger coverage (14.5% on average) and test generation time (6.5 times on average) compared to state-of-the-art techniques. 
    more » « less
  2. ; ; ; ; ( , Bioinformatics)
    Abstract Motivation

    Growth phenotype profiling of genome-wide gene-deletion strains over stress conditions can offer a clear picture that the essentiality of genes depends on environmental conditions. Systematically identifying groups of genes from such high-throughput data that share similar patterns of conditional essentiality and dispensability under various environmental conditions can elucidate how genetic interactions of the growth phenotype are regulated in response to the environment.

     Results

    We first demonstrate that detecting such ‘co-fit’ gene groups can be cast as a less well-studied problem in biclustering, i.e. constant-column biclustering. Despite significant advances in biclustering techniques, very few were designed for mining in growth phenotype data. Here, we propose Gracob, a novel, efficient graph-based method that casts and solves the constant-column biclustering problem as a maximal clique finding problem in a multipartite graph. We compared Gracob with a large collection of widely used biclustering methods that cover different types of algorithms designed to detect different types of biclusters. Gracob showed superior performance on finding co-fit genes over all the existing methods on both a variety of synthetic data sets with a wide range of settings, and three real growth phenotype datasets for E. coli, proteobacteria and yeast.

     Availability and Implementation

    Our program is freely available for download at http://sfb.kaust.edu.sa/Pages/Software.aspx.

     Supplementary information

    Supplementary data are available at Bioinformatics online.

     
    more » « less
  3. ; ( , ACM Transactions on Design Automation of Electronic Systems)
    null (Ed.)
    Detection of hardware Trojans is vital to ensure the security and trustworthiness of System-on-Chip (SoC) designs. Side-channel analysis is effective for Trojan detection by analyzing various side-channel signatures such as power, current, and delay. In this article, we propose an efficient test generation technique to facilitate side-channel analysis utilizing dynamic current. While early work on current-aware test generation has proposed several promising ideas, there are two major challenges in applying it on large designs: (i) The test generation time grows exponentially with the design complexity, and (ii) it is infeasible to detect Trojans, since the side-channel sensitivity is marginal compared to the noise and process variations. Our proposed work addresses both challenges by effectively exploiting the affinity between the inputs and rare (suspicious) nodes. The basic idea is to quickly find the profitable ordered pairs of test vectors that can maximize side-channel sensitivity. This article makes two important contributions: (i) It proposed an efficient test generation algorithm that can produce the first patterns in the test vectors to maximize activation of suspicious nodes using an SMT solver, and (ii) it developed a genetic-algorithm based test generation technique to produce the second patterns in the test vectors to maximize the switching in the suspicious regions while minimizing the switching in the rest of the design. Our experimental results demonstrate that we can drastically improve both the side-channel sensitivity (62× on average) and time complexity (13× on average) compared to the state-of-the-art test generation techniques. 
    more » « less
  4. ; ( , IEEE Transactions on Computers)
    Simulation is widely used for validation of Register-Transfer-Level (RTL) models. While simulating with millions of random or constrained-random tests can cover majority of the functional scenarios, the number of remaining scenarios can still be huge (hundreds or thousands) in case of today's industrial designs. Hard-to-activate branches are one of the major contributors for such remaining/untested scenarios. While directed test generation techniques using formal methods are promising in activating branches, it is infeasible to apply them on large designs due to state space explosion. In this paper, we propose a fully automated and scalable approach to cover the hard-to-activate branches using concolic testing of RTL models. While application of concolic testing on hardware designs has shown some promising results in improving the overall coverage, they are not designed to activate specific targets such as uncovered corner cases and rare scenarios. This paper makes two important contributions. (1) We propose a directed test generation technique to activate a target by effective utilization of concolic testing on RTL models. (2) We develop efficient learning and clustering techniques to minimize the overlapping searches across targets to drastically reduce the overall test generation effort. 
    more » « less
  5. ; ; ( , Frontiers in Nanotechnology)
    Hardware Trojans in Integrated Circuits (ICs), that are inserted as hostile modifications in the design phase and/or the fabrication phase, are a security threat since the semiconductor manufacturing process is increasingly becoming globalized. These Trojans are devised to stay hidden during standard structural and functional testing procedures and only activate under pre-determined rare conditions (e.g., after a large number of clock cycles or the assertion of an improbable net). Once triggered, they can deliver malicious payloads (e.g., denial-of-service and information leakage attacks). Current literature identifies a collection of logic Trojans (both trigger circuits and payloads), but minimal research exists on memory Trojans despite their high feasibility. Emerging Non-Volatile Memories (NVMs), such as Resistive RAM (RRAM), have special properties such as non-volatility and gradual drift in bitcell resistance under a pulsing voltage input that make them prime targets to deploy hardware Trojans. In this paper, we present two delay-based and two voltage-based Trojan triggers using emerging NVM (ENTT) by utilizing RRAM’s resistance drift under a pulsing voltage input. Simulations show that ENTTs can be triggered by reading/writing to a specific memory address N times (N could be 2,500–3,500 or a different value for each ENTT design). Since the RRAM is non-volatile, address accesses can be intermittent and therefore stay undetected from system-level techniques that can identify continuous hammering as a possible security threat. We also present three reset techniques to de-activate the triggers. The resulting static/dynamic power overhead and maximum area overhead incurred by the proposed ENTTs are 104.24 μW/0.426 μW and 9.15 μm2, respectively in PTM 65 nm technology. ENTTs are effective against contemporary Trojan detection techniques and system level protocols. We also propose countermeasures to detect ENTT during the test phase and/or prevent fault-injection attacks during deployment. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email