Improved Test Pattern Generation for Hardware Trojan Detection Using Genetic Algorithm and Boolean Satisfiability

Sayandeep Saha, Rajat Subhra Chakraborty, Srinivasa Shashank Nuthakki, Anshul, Debdeep MukhopadhyayChes 2015 · DOI

TL;DR

This paper introduces a novel approach for detecting hardware Trojans (HTHs) by combining Genetic Algorithms (GAs) and Boolean Satisfiability (SAT) solvers. This method aims to generate more effective test patterns that can uncover stealthy Trojans, which are often missed by traditional testing methods, by considering both trigger conditions and the propagation of Trojan effects to the circuit's output.

What Problem Does This Paper Address?

Modern electronic designs are vulnerable to malicious modifications, leading to the insertion of Hardware Trojan Horses (HTHs). These Trojans are designed to be triggered by rare logic conditions within the circuit, making them extremely difficult to detect using conventional post-manufacturing testing. Existing detection methods often rely on side-channel analysis (e.g., power consumption, delay) which can be susceptible to noise and process variations, or design modification techniques that can be circumvented by sophisticated attackers. The challenge lies in generating test patterns that can reliably activate these rare trigger conditions and ensure that the Trojan's malicious effect is observable at the circuit's output.

Methods

The paper proposes a two-phase approach for generating test patterns to detect HTHs:

  1. Combined GA and SAT for Trigger Generation:
    • Genetic Algorithm (GA): Used to automatically generate test patterns that activate a large number of sampled trigger combinations, with a focus on those that are "hard-to-trigger." The GA's fitness function is designed to balance triggering multiple rare nodes and improving the "database" of discovered trigger-vector pairs.
  2. Boolean Satisfiability (SAT): Employed to solve for trigger combinations that the GA could not satisfy. This leverages SAT solvers' robustness in finding solutions for complex and pathological problems. The rationale is that GAs are good at exploring the search space quickly, while SAT solvers are effective for difficult-to-satisfy conditions.
  3. Payload Aware Test Set Selection and Compaction (Algorithm 3):
    • Pseudo-Test Vector (PTV) Generation: For each identified trigger combination and its associated test vectors, a PTV is created. This PTV uses 3-valued logic (0, 1, X) to represent constrained primary input values.
  4. Fault Simulation: The PTV is used to perform a 3-value logic simulation, and potential "payload" nodes are identified by considering stuck-at faults at internal wires.
  5. Test Set Selection and Compaction: A fault simulator (HOPE) is used to determine which of the generated test vectors can propagate the Trojan effect (represented by the identified faults) to the primary output. A greedy approach is then used to select a minimal subset of these test vectors that completely covers the detected faults, thus compacting the test set and improving Trojan coverage.

Datasets

The evaluation was performed on a subset of the ISCAS-85 and ISCAS-89 benchmark circuits. For sequential circuits, they were converted to full scan mode. The paper does not introduce new benchmark circuits.

Key Insights and Ideas

  • Synergy of GA and SAT: Combining GA for broad exploration and SAT for precise problem-solving is an effective strategy for generating test patterns for rare trigger conditions.
  • Payload Awareness is Crucial: Simply triggering a Trojan is insufficient; the test patterns must also ensure that the Trojan's effect is observable at the circuit's output. This "payload awareness" significantly improves detection effectiveness.
  • Test Compaction Enhances Effectiveness: Reducing the test set size while maintaining high coverage is achieved through a payload-aware selection process, leading to a more efficient and effective Trojan detection methodology.
  • Rareness Threshold Tuning: The choice of the "rareness threshold" (θ) for identifying rare nodes is critical. The paper suggests that an optimal range (around 0.08-0.12) balances coverage of both easily and hard-to-trigger Trojans.

Key Results

  • The proposed scheme significantly outperforms the MERO technique in terms of both trigger and Trojan coverage across various benchmark circuits.
  • For example, in Table 2, the proposed scheme (GA + SAT + Algo. 3) achieves higher Trojan coverage (e.g., 85.70% for c880) compared to GA only (83.59%) and MERO (69.96%).
  • Table 1 shows that the proposed scheme, after compaction (Algo-3), often results in a smaller test set size than MERO while achieving better coverage.
  • Figure 8 demonstrates that the proposed scheme consistently achieves higher trigger and Trojan coverage than MERO across different rareness thresholds (θ) for the c7552 circuit.

Limitations and Future Work

  • Incomplete Payload Enumeration: The paper acknowledges that it's not guaranteed that all possible test vectors triggering a specific combination will be generated, and thus, not all feasible payloads might be enumerated. The fault list (Fs) is calculated based on the generated test vectors, which might not cover all possible payloads.
  • Test Set Size: While compaction is applied, the overall test set size can still be significant for large circuits.
  • Future Work: The authors suggest extending the data structure (D) to a complete Trojan database that can be leveraged for Trojan diagnosis. They also propose developing comprehensive Trojan diagnosis methodologies based on this database. Further research could also explore more sophisticated test compaction schemes.

Summary updated

BibTeX
@inproceedings{saha2015improved,
  author = {Sayandeep Saha and Rajat Subhra Chakraborty and Srinivasa Shashank Nuthakki and Anshul and Debdeep Mukhopadhyay},
  title = {{Improved Test Pattern Generation for Hardware Trojan Detection Using Genetic Algorithm and Boolean Satisfiability}},
  booktitle = {Ches},
  year = {2015},
  doi = {10.1007/978-3-662-48324-4\_29},
}
Figure