Skip to main content
U.S. flag

An official website of the United States government

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.

Patent of the Month: November 2020

Patent of the Month:Oracle-free match testing of a program using covering arrays and equivalence classes

Technology Description

This is a method and software for testing computer software. The method applies to a broad range of software but is particularly applicable software with complex conditions and decision, e.g., process control, avionics, and other areas.  This method also verifies equivalence classes for module unit testing. Both testing and equivalence class verification is achieved using a two-layer covering array which some or all values of a primary covering array represent equivalence classes. A second layer covering array of the equivalence class values is computed, and its values substituted for the equivalence class names in the primary array. It is shown that this method can also detect certain classes of errors without a conventional test oracle.

With reference to the flowchart below, the data processing system executes the program as part of process for testing the program. Here, the process starts (step 126) by receiving (e.g., by processor or memory) a variable (step 128) that includes a plurality of input values, accessing the input values (step 130) (e.g., by processor 102), partitioning the input values (step 132), producing equivalence classes from the partitioned input values (step 134), producing a primary covering array (step 136) (that includes a primary vector having a primary entry), producing a secondary covering array (that includes a secondary vector having a secondary entry) for each role in the primary covering array (step 138), subjecting each secondary covering array to the program (step 140), producing from the program a result vector for each secondary covering array (step 142), and determining whether result entries in the result vector are self-consistent (step 144).

If the result entries in the result vector are self-consistent (at step 144), the process includes determining whether a result vector was produced for each secondary covering array (step 146). If a result vector was produced for every secondary covering array (at step 146), then the process ends (step 140). If a result vector (having a plurality of result entries) was not produced for every secondary covering array (at step 146), then the process reiterates to produce in other result vector (step 142).

If the result entries in the result vector are not self-consistent (at step 144), the process includes determining whether equivalence classes were produced correctly (step 150). If equivalence classes were produced correctly (step 152), process 124 determines the program includes error in code (step 154), and process 124 includes error handling (step 156) such as producing an error flag, error message, error alarm, and the like. If equivalence classes were not produced correctly (step 152), process 124 includes correcting partitioning of input values (step 158) and repartitioning the input values (step 132) by applying a corrected partitioning rule.

The program is tested against input values that are partitioned into the equivalence classes. In a particular embodiment, representative values from each equivalence class is provided to the program, and the output the program is stored, e.g., in memory as a result vector. It is contemplated that the program can be executable code (including units, modules, scripts, and the like), data, system configuration files, machine environment state settings, and the like. In a certain embodiment, the program is executable program that receives the representative values as a substitute for the input values of the variable, which is the expected input by the program.

flow chart for testing computer software
Credit: NIST

 

Inventors

D. Richard Kuhn

Raghu N. Kacker

Technology Type

Information Technology

 

 

Benefits

Conventional software testing requires the use of a 'test oracle', i.e., expected results for each set of inputs designated by a test. This invention eliminates the requirement for a test oracle for a significant class of software errors thus reduces cost. It is fully automated, obviating the need for the highest-cost components of testing - human involvement or a mathematical model of the system.

Licensing Inquiries may be sent to TPO [at] NIST.GOV

View other patents of the month here.

Created November 2, 2020, Updated August 23, 2023