Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Combinatorial Methods for Trust and Assurance

Functional Verification of Semiconductor Logic Designs

Combinatorial test and measurement methods have demonstrated 20% to 30% cost reductions and more effective testing for complex software.  Detection of security vulnerabilities and ultra-rare defects is significantly better than conventional test methods. Combinatorial testing compresses all t-way combinations of parameter values into very small test arrays, so that it is in many ways comparable to exhaustive testing. As over half the cost for a new chip design is from functional verification [1], extending combinatorial testing to semiconductor design problems has the potential to reduce total cost for a new design by 10% to 20%.    

Background

  • As of 2022, typically 50% to 60% of total IC/ASIC project time goes to functional verification, with some new design IP requiring 70% or more [1].
  • With current functional verification methods, 84% of FPGA designs include non-trivial bugs that are missed in verification and escape into production [1].  The largest categories of these bugs are logic and function flaws.
  • Because of the combinatorial explosion problem, the most common method for functional verification is generation of random tests, sometimes supplemented with constraints or machine learning to enhance detection of possible very rare errors.
  • According to industry experts, there are currently no tools available to systematically search and detect outlier bugs, which can only be triggered with rare and precise sequences [2]. It is infeasible for verification teams to think of every possible corner-case situation and to verify it with hand-written tests.
  • The problem is even greater for security-critical bugs in chip designs.  A large study involving 54 teams of experts was able to find only 61% of security vulnerabilities using conventional test and inspection techniques, and only 48% using formal verification [3].  
    ​​​
    [1] 2022 Wilson Research Group Functional Verification Study https://blogs.sw.siemens.com/verificationhorizons/2022/12/12/part-8-the-2022-wilson-research-group-functional-verification-study/
    [2] https://semiengineering.com/when-bugs-escape/
    [3] Dessouky, G., Gens, D., Haney, P., Persyn, G., Kanuparthi, A., Khattri, H., ... & Rajendran, J. (2019). {HardFails}: Insights into {Software-Exploitable} Hardware Bugs. In 28th USENIX Security Symposium (USENIX Security 19) (pp. 213-230).

Rationale

  • Combinatorial testing of software has been shown to improve software fault detection effectiveness by a factor of 10X or more, with significant reduction in overall costs.  Coverage is also significantly greater and produced more efficiently.  Combinatorial testing has also been shown to provide much stronger testing with far fewer test cases than random testing.  The improvements in cost reduction and test effectiveness are especially strong for complex embedded systems, such as avionics.  [https://csrc.nist.gov/acts]
  • Combinatorial testing excels at rare flaws as it systematically enumerates and exercises all possible t-way input interactions leading to rare sequences.
  • The project is likely to provide advanced capability to industry within 1-3 years.  Tools for advanced software program testing developed by NIST have been adopted widely by industry.  These tools can be adapted and extended to be applied to hardware description languages (HDL) used in all new semiconductor designs.  The modifications to adapt to chip design languages will focus on the greater parallelism in hardware description languages, and capability for input sequences to ensure reachability of even extremely rare states within a design.  New theorems published by NIST demonstrate how this may be done, and these results can be implemented in new tools for verification of advanced models.
  • The combinatorial test methods that are the focus of this work have been demonstrated to reduce testing cost for complex software by 20% to 30% or more.  If similar results can be shown for hardware description languages, it may be possible to reduce new chip design costs by 10% to 20%, as testing costs average more than half the total cost of a new chip design, and even higher for new designs using less existing IP. 

Combinatorial test methods can potentially identify much larger fraction of security vulnerabilities than are generally known to be discoverable through traditional testing methods (found to be 61% in [3]). This will tremendously reduce the risk of hardware vulnerabilities escaping into production.

Goals

The output of the project will be a set of combinatorial testing tools for semiconductor design verification and testing.  The tools will be extended and enhanced adaptation of the NIST combinatorial testing tool that has been distributed to more than 4,500 industry and academic users, and used by some of the world's largest organizations.

Created May 24, 2016, Updated May 23, 2024