Testing electronics for faults that occur due to natural phenomena is difficult enough; however, what if an anomaly is intentionally introduced? This is the question facing the electronics industry. In recent years, the research community has delved into the possibility that global outsourcing has made electronics manufacturing too risky. Integrated circuit (IC) manufacturing has attracted the most attention and spawned two major technical conferences—one in the U.S.1 and one in Asia.2 At these forums, researchers addressed the threat of malicious hardware being introduced into an IC—usually referred to as a hardware Trojan. Hardware Trojans are designed to evade detection when testing is performed in the traditional manner. When a hardware Trojan in an IC is activated it can make a system inoperable, cause it to malfunction, or even leak sensitive data.
Scoping the threat
The increasing complexity of microcircuits, coupled with fabless manufacturing, have ushered in more possibilities for tiny hardware Trojans to be introduced during an IC’s design or fabrication stages. This almost always leaves post-manufacturing test as the final hope before the device goes into the field. Detecting hardware Trojans at this stage becomes a vexing problem because we are compelled to apply Shannon’s maxim: “The enemy knows the system.” It was in his 1949 paper “Communication Theory of Secrecy Systems” that Claude Shannon made this assertion; yet, his maxim remains a mainstay for security today.
Applying the maxim’s skepticism to hardware Trojans means that we must assume that the attacker knows an IC’s design and the CAD/CAE tools used to create it. We further envision the situation where the attacker has infiltrated the process to design the IC, to fabricate it, or both. Only after the IC is manufactured do we assume that the attacker no longer has access to the system to enable a hardware Trojan. A post-manufacturing test, therefore, becomes the remaining obstacle for the attacker to overcome. To do this, the attacker calls upon his knowledge of the device’s CAD/CAE tools that include the test vector generation for the IC.
Testing the limits of the tester
Exhaustive testing is universally acknowledged to be prohibitive because even moderately complex designs would take hundreds of years to test so comprehensively. Thus, test generation is an engineering enterprise to balance cost and performance such that tester time is minimized while achieving high fault coverage. Tools for generating test vectors assume a fault model. For this article, we apply the commonly-used single stuck-at fault model. In this model the inputs and outputs of an IC’s gates are the fault sites. At these sites, stuck-at faults can occur such that an input or an output is either stuck-at-0 or stuck-at-1.
Although the model only affects inputs and outputs, tests derived for stuck-at faults at those sites are still valid for most physical defects, such as shorts, either on the gate’s inputs or output as well as internal to the gate. The “single” attribute of the fault model stems from the assumption that only a single fault will manifest in the IC. The usefulness of this assumption has been reinforced by evidence showing that tests to detect a single fault in an IC will usually detect multiple, concurrent faults. Equipped with these assumptions, test vector generation can proceed. Next, we show an example of test vector generation that yields a set of test vectors having complete single stuck-at fault coverage. Then we show how a knowledgeable attacker can plant a hardware Trojan that evades detection from those test vectors.
An AND gate has inputs A and B and output C. This AND gate can have a test generated for a stuck-at-1 fault (SA1) on its output C (Figure 1).
For the three wires (A, B, and C) associated with this AND gate, five more stuck-at faults remain: C stuck-at-0, A stuck-at-0, A stuck-at-1, B stuck-at-0, and B stuck-at-1. We chose to illustrate how additional tests can be generated to detect these last three faults (Figure 2).
Table 1 shows all possible input combinations to the AND gate and the single stuck-at-faults detected. Since Table 1 represents exhaustive testing of the AND gate, it is important to ask: what input combinations are needed to test for all single stuck-at faults while minimizing the number of tests? The answer is: A=0 and B=1; A=1 and B=0; and A=1 and B=1. These three combinations of inputs test for all possible single stuck-at faults for the AND gate. The test of A = 0 and B = 0 is redundant. Efficiency compels elimination of this input combination when generating the test set; yet full fault coverage is maintained.
This is precisely the knowledge that the attacker needs. Consider the use of the AND gate in a circuit (Figure 3) for performing bus select. However, a hardware Trojan has been added, too. The attacker severed the wire of the AND gate’s output and inserted an XOR gate and connected to it a NOR gate. The XOR gate is the hardware Trojan’s payload and the NOR gate is its trigger. Prior to insertion of the payload and trigger, the circuit, composed only of the AND gate, would raise the BUS-SEL line high only when CTRL and INT are both high (i.e., CTRL=1 and INT=1).
In the presence of the hardware Trojan’s two gates the circuit’s functionality can change dramatically. The payload is triggered when the output of the NOR gate goes high. This causes the XOR gate to invert the AND gate’s attempt to set BUS-SEL low. Instead of BUS-SEL being low, the resultant BUS-SEL signal would go high—creating, as intended by the attacker, haphazard functionality for the circuit.
We see that the attacker designed the hardware Trojan so that the payload is triggered when the NOR gate’s inputs are both zero (yellow portion of Figure 3). However, notice that this would only occur when the AND gate’s inputs are also both zero. Recall that this is the single input combination that would not be applied to the AND gate using the generated test set.
Fighting through the attack
At this point, we can see that the attacker nefariously used his knowledge of test generation so that the hardware Trojan would not be activated—and hence go undetected—during post-fabrication test. Thus, the attacker achieved his aim: the IC will pass through the testing phase; yet there is an input combination (INT = 1 and CNTL = 1) that will occur in the field causing Trojan activation.
The above scenario underscores that in the realm of outsourced manufacturing, the testing of incoming ICs for hardware Trojans cannot be done in the conventional manner. In the example given, if the seemingly inefficient AND gate test of applying zeroes to both its inputs were added to the IC’s test, then the hardware Trojan would have been activated and hence detected. Testing for hardware Trojans calls for augmentation of the tests for the random faults that can occur in an IC. The question becomes, aside from the infeasibility of near-exhaustive testing, what augmented test sets should be considered? Since testing is not limited to random faults but directed attacks, strategic considerations must harness the decision-making process between an attacker and a tester. Procurers of ICs for critical IC applications such as the power grid, aerospace, military, automotive, health, and finance become immersed in this decision-making process when they face the risk of a hardware Trojan. Booz Allen Hamilton, under contract with the Air Force Research Laboratory (AFRL), has developed a simulator to make testing for hardware Trojans more plausible and therefore a risk-balancer. The simulator is based on the mathematical discipline of game theory.3 Dr. John Nash (acclaimed in the movie A Beautiful Mind) discovered that applying game theory will always result in states where the opposing players (e.g., the IC procurer and the attacker) have no incentive to deviate from their respective strategies. This is the so-called “Nash equilibrium.” Based on a game theory engine, the simulator considers the attacker’s and tester’s strategies and utilities (cost and payoffs). It can display the ensuing game in matrix notation (Figure 4) that allows tracking the attacker’s and tester’s possible actions and the accompanying utility of each action. In this matrix, the tester has the possibility of applying different pairings of augmented test sets A, B, C, and D that, under certain probabilities, can detect the presence of various hardware Trojans A, B, C, etc., that an attacker plants with other probabilities. There are more sophisticated hardware Trojans than the example presented here, and more sophisticated testing methods are usually needed to detect them; nonetheless, the simulator is designed to incorporate these other methods of IC testing.
The simulator’s inputs allow applying realistic time and cost limits of testing for hardware Trojans versus the attacker’s incentives to plant them in an IC. The simulator’s output is an intelligent assessment of the testing resources to be applied and the resultant risk-balancing of the hardware Trojan threat. A cost-benefit analysis can then be made for IC testing flows that, in addition to testing for traditional faults, also seek to detect hardware Trojans. By applying game theory, procurers of ICs that use the simulator can strategically put their testing resources to use and attain a quantifiable, mathematically-based balancing of risk.
Most government-developed software can be made available for licensing for commercialization. In fact, this is often in the best interests of the government to ensure that it is properly maintained throughout its life cycle. In many cases, the government can release the software to anyone for any purpose (including commercialization); thus, government-developed software can often be licensed from either the government or the development contractor. Companies looking to license this simulator can contact the authors and we will direct you to the appropriate point-of-contact.
Fabless manufacturing and outsourced fabrication are important features of today’s IC industry. When Shannon’s maxim that “The enemy knows the systems” is applied to this industry, the hardware Trojan testing simulator aims to keep that knowledge from becoming a game-changer.
References
- IEEE International Symposium on Hardware Oriented Security and Trust (HOST).
- IEEE Asian Hardware Oriented Security and Trust Symposium (AsianHOST).
- Kamhoua, Charles; Zhao, Hong; Rodriguez, Manuel; and Kwiat, Kevin, “A Game-Theoretic Approach for Testing for Hardware Trojans,” IEEE Transactions on Multi-Scale Computing Systems, May 2016.
Disclaimer: The views and content expressed in this article are those of the authors and do not reflect the official policy or position of the Department of the Air Force, Department of Defense, or the U.S. Government.
About the authors
Kevin A. Kwiat, Ph.D., retired in 2017 as Principal Computer Engineer with the U.S. Air Force Research Laboratory (AFRL) after more than 34 years of service. During that time, he conducted research and development in a wide scope of areas: high reliability microcircuit selection for military systems; testability; logic and fault simulation; rad-hard microprocessors; benchmarking of experimental designs; distributed processing systems; assured communications; FPGA-based computing; fault tolerance; survivable systems; game theory; cyber-security; and cloud computing. His Ph.D. is in Computer Engineering from Syracuse University. He holds five patents. He is now co-founder and co-leading Haloed Sun TEK in Sarasota, FL—an LLC focusing on technology transfer and currently supported by the Department of Commerce.
Frank Born is currently Innovation Director for the Upstate Innovation Accelerator (Department of Commerce grant). Effort involves transferring technology from AFRL $1 billion per year information research budget to the commercial marketplace. He recently retired after 31 years as an AFRL research scientist. His AFRL career involved managing programs and developing innovative solutions in key fields of reliability, electronics prognostics, artificial intelligence, planning, scheduling, and cybersecurity. He designed and developed a software system used by more than 4,000 Air Force personnel and their contractors to manage over $5 billion in research contracts. He also designed and developed an initial prototype of browser security software being developed by commercial industry. He holds four patents in areas of browser security and aircraft wiring prognostics.
Both authors may be contacted at [email protected].
