Reducing the complexity of finite state machine test generation using combinatorial designs

A method of verifying a design, comprising the steps of:

• modeling a behavior of said design as a finite state machine;
• generating a test program based on said finite state machine;
• and
• preparing a suite of test cases as an input for said test program, wherein said test eases comprise at least one command, said command having a plurality of parameters, said parameters having a predetermined level of mutual interactions, wherein said test cases are minimized to a near-optimal minimal plurality that includes at least one instance of each of said mutual interactions at said predetermined level, wherein said step of preparing a suite of test cases is performed by:
• defining relationships among said parameters as a plurality of t-tuples of values of said parameters;
• preparing a table of input sets, said table having a plurality of columns, each of said columns comprising a portion of said values;
• finding a partial test case comprising a set of t columns, wherein a deficiency comprising missing ones of said t-tuples is maximal;
• assigning one of said missing t-tuples as said values for said set of t columns;
• entering possible values of said missing t-tuples in others of said columns;
• ranking said other columns and said values thereof according to a reduction of said deficiency that is produced by inclusion in said partial test case of respective ones of said other columns;
• and
• selecting one of said other columns and said values thereof having a highest rank in said step of ranking, and including a value of said selected column in said input set.

A computer software product, comprising a computer-readable medium in which computer program instructions are stored, which instructions, when read by a computer, cause the computer to execute method of verifying a design, comprising the steps of:

• loading a behavior model of said design as a finite state machine;
• generating a test program based on said finite state machine;
• and
• preparing a sample of all possible inputs for said test program, wherein said sample comprise a list of parameters, said parameters being selected from a predetermined set of values, said parameters applying to transitions of said finite state machine, and having predetermined mutual interactions, wherein said sample is minimized to a near-optimal minimal plurality of said inputs that cover at least one instance of each said interactions.

A computer software product, comprising a computer-readable medium in which computer program instructions are stored, which instructions, when read by a computer, cause the computer to execute method of verifying a design, comprising the steps of:

• loading a behavior model of said design as a finite state machine;
• generating a test program based on said finite state machine;
• and
• preparing a sample of all possible inputs for said test program, wherein said sample comprise a list of parameters, said parameters having predetermined mutual interactions, wherein said sample is minimized to a near-optimal minimal plurality of said inputs, that cover at least one instance of each said interactions, wherein said step of preparing a sample is performed by:
• defining relationships among said inputs as a plurality of t-tuples of values of said inputs;
• preparing a table of input sets, said table having a plurality of columns, each of said columns comprising a portion of said values;
• finding a partial test case comprising a set of t columns, wherein a deficiency comprising missing ones of said t-tuples is maximal;
• assigning one of said missing t-tuples as said values for said set of t columns;
• ranking others of said columns and said values entered therein according to a reduction of said deficiency that is produced by inclusion in said partial test case of respective ones of said other columns;
• and
• selecting one of said other columns and said values entered therein having a highest rank in said step of ranking.

A computer software product, comprising a computer-readable medium in which computer program instructions are stored, which instructions, when read by a computer, cause the computer to execute method of verifying a design, comprising the steps of:

• loading a behavior model of said design as a finite state machine;
• generating a test program based on said finite state machine;
• and
• preparing a sample of all possible inputs for said test program, wherein said sample comprise a list of parameters, said parameters having predetermined mutual interactions, wherein said sample is minimized to a near-optimal minimal plurality of said inputs that cover at least one instance of each said interactions, wherein said step of preparing is performed by:
• defining relationships among said parameters;
• and
• constructing tables of input sets, each of said tables of input sets corresponding to one of said relationships.

A computer software products comprising a computer-readable medium in which computer program instructions are stored, which instructions, when read by said computer, cause said computer to execute a method of testing a design, comprising the steps of:

• defining a finite state machine as a behavior model of a system-under-test having transitions between states thereof;
• providing a partial ruleset comprising a rule and a parameter list thereof, and an input table having at least one set of parameters corresponding to members of said parameter list;
• and
• responsive to said partial ruleset, generating a test program for said system-under-test, wherein said rule of said partial ruleset is invoked at one of said transitions of said finite state machine using said set of parameters in said parameter list.