Patent US4060210A successfully refreshed from Google Patents.
US5831998A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of testcase optimization
Assignee: Nortel Networks Ltd
•
Filing: 1996-12-13
•
Granted: 1998-11-03
•
Expires: 2016-12-13
Abstract
Abstract A new method of testcase optimization for generating testcases is provided which is both efficient and effective. A 2-level heuristic is employed. The method is iterative, and at each iteration, at the first level of the heuristic, a greedy algorithm is used to select a testcase which covers the largest number of uncovered interactions from a remaining set of uncovered interactions. The second level heuristic consists of a simulation step which is employed at each iteration. Rather than conducting the greedy algorithm over an entire test domain, during each iteration the algorithm is applied over a randomly selected set of testcases. The method is efficient in the sense that a quasi-optimal number of testcases is generated which covers the most interactions with close to the fewest number of testcases. The method is effective in the sense that 100% coverage of all possible interactions is guaranteed. The method is generic in that it can be applied to any complex testing and verification task regardless of its domain.
Inventors
- 👤 Fatma Nur Ozmizrak
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 10:20
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/36; G06F11/3668; G06F11/3672; G06F11/3676; G01; G01R; G01R31/00; G01R31/28; G01R31/317; G01R31/3181; G01R31/3183; G01R31/318342; G01R31/31835; G06F11/3684
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
153 words
A processor implemented method for automatically generating testcases to test a system having a plurality N of test sets each having a corresponding plurality of possible values, each testcase including for each test set a single one of the corresponding plurality of possible values, each testcase belonging to a testcase domain, the method comprising the steps of: 1) defining an uncovered set of tuples, each tuple defining an interaction between two or more particular values, each value selected from a different test set; 2) performing a simulation to select a testcase which maximizes the number of tuples in the uncovered set which are covered by the testcase, a particular testcase covering a particular tuple if all the values in the tuple are included in the testcase; and 3) removing the tuples covered by the selected testcase from the uncovered set; wherein the uncovered set of tuples consists of all possible M-tuples where 2≦M≦N.
Claim 2
Dependent Claim
153 words
A processor implemented method for automatically generating testcases to test a system having a plurality N of test sets each having a corresponding plurality of possible values, each testcase including for each test set a single one of the corresponding plurality of possible values, each testcase belonging to a testcase domain, the method comprising the steps of: 1) defining an uncovered set of tuples, each tuple defining an interaction between two or more particular values, each value selected from a different test set; 2) performing a simulation to select a testcase which maximizes the number of tuples in the uncovered set which are covered by the testcase, a particular testcase covering a particular tuple if all the values in the tuple are included in the testcase; and 3) removing the tuples covered by the selected testcase from the uncovered set; wherein the uncovered set of tuples consists of all possible M-tuples where 2≦M≦N.
Claim 3
Dependent Claim
15 words
A method according to claim 1 wherein the testcase domain consists of all possible testcases.
Claim 4
Dependent Claim
49 words
A method according to claim 2 wherein the simulation performed in step 2) comprises the steps of: i) generating randomly K testcases from the testcase domain, where K>=2; and ii) selecting from the K randomly generated testcases the testcase covering the largest number of M-tuples in the uncovered set.
Claim 5
Dependent Claim
18 words
A method according to claim 1 wherein the testcase domain consists of a subset of all possible testcases.
Claim 6
Dependent Claim
16 words
A method according to claim 4 wherein the subset is defined by constraints upon permitted testcases.
Claim 7
Dependent Claim
59 words
A method according to claim 5 wherein the simulation performed in step 2) comprises the steps of: i) generating testcases at random from the set of all possible testcases until K testcase are found which satisfy the constraints, where K>2; and ii) selecting from the K testcases the testcase covering the largest number of M-tuples in the uncovered set.
Claim 8
Dependent Claim
15 words
A method according to claim 4 wherein the subset is a set of existing testcases.
Claim 9
Dependent Claim
49 words
A method according to claim 7 wherein the simulation performed in step 2) comprises the steps of: i) selecting randomly K testcases from the testcase domain, where K>=2; and ii) selecting from the K randomly selected testcases the testcase covering the largest number of M-tuples in the uncovered set.
Claim 10
Dependent Claim
49 words
A method according to claim 4 wherein the simulation performed in step 2) comprises the steps of: i) generating randomly K testcases from the testcase domain, where K>=2; and ii) selecting from the K randomly generated testcases the testcase covering the largest number of M-tuples in the uncovered set.
Claim 11
Dependent Claim
20 words
A method according to claim 1 further comprising of repeating steps 2) and 3) until the uncovered set is empty.
Claim 12
Dependent Claim
49 words
A method according to claim 10 wherein the simulation performed in step 2) comprises the steps of: i) generating randomly K testcases from the testcase domain, where K>=2; and ii) selecting from the K randomly generated testcases the testcase covering the largest number of M-tuples in the uncovered set.
Claim 13
Dependent Claim
62 words
A method according to claim 1 further comprising the steps of: 4) counting the number of uncovered M-tuples covered by the testcase; 5) maintaining a running total of the total number or percentage of uncovered M-tuples covered by the testcases generated thus far; and 6) repeating steps 2), 3) 4) and 5) until a predetermined percentage of the uncovered M-tuples are covered.
Claim 14
Dependent Claim
15 words
A method according to claim 12 further comprising outputting each testcase with the respective percentage.
Claim 15
Dependent Claim
49 words
A method according to claim 13 wherein the simulation performed in step 2) comprises the steps of: i) generating randomly K testcases from the testcase domain, where K>=2; and ii) selecting from the K randomly generated testcases the testcase covering the largest number of M-tuples in the uncovered set.
Claim 16
Dependent Claim
49 words
A method according to claim 12 wherein the simulation performed in step 2) comprises the steps of: i) generating randomly K testcases from the testcase domain, where K>=2; and ii) selecting from the K randomly generated testcases the testcase covering the largest number of M-tuples in the uncovered set.
Claim 17
Dependent Claim
49 words
A method according to claim 1 wherein the simulation performed in step 2) comprises the steps of: i) generating randomly K testcases from the testcase domain, where K>=2; and ii) selecting from the K randomly generated testcases the testcase covering the largest number of M-tuples in the uncovered set.
Claim 18
Dependent Claim
183 words
A processor implemented method for automatically generating testcases to test a system having a plurality N of test sets each having a corresponding plurality of possible values, each testcase including for each test set a single one of the corresponding plurality of possible values, each testcase belonging to a testcase domain, the method comprising the steps of: 1) defining an uncovered set of tuples, each tuple defining an interaction between two or more particular values, each value selected from a different test set; 2) performing a simulation to select a testcase which maximizes the number of tuples in the uncovered set which are covered by the testcase, a particular testcase covering a particular tuple if all the values in the tuple are included in the testcase; and 3) removing the tuples covered by the selected testcase from the uncovered set; wherein the simulation performed in step 2) comprises the steps of: i) generating randomly K testcases from the testcase domain, where K>=2; and ii) selecting from the K randomly generated testcases the testcase covering the largest number of tuples in the uncovered set.
Claim 19
Dependent Claim
183 words
A processor implemented method for automatically generating testcases to test a system having a plurality N of test sets each having a corresponding plurality of possible values, each testcase including for each test set a single one of the corresponding plurality of possible values, each testcase belonging to a testcase domain, the method comprising the steps of: 1) defining an uncovered set of tuples, each tuple defining an interaction between two or more particular values, each value selected from a different test set; 2) performing a simulation to select a testcase which maximizes the number of tuples in the uncovered set which are covered by the testcase, a particular testcase covering a particular tuple if all the values in the tuple are included in the testcase; and 3) removing the tuples covered by the selected testcase from the uncovered set; wherein the simulation performed in step 2) comprises the steps of: i) generating randomly K testcases from the testcase domain, where K>=2; and ii) selecting from the K randomly generated testcases the testcase covering the largest number of tuples in the uncovered set.
References Cited (Backward Citations)
US4935877A
Cited
US5485471A
Cited
US5604895A
Cited
US5664171A
Cited
US5542043A
Cited
US5724504A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-02 | 2002-05-04 | 2002-11-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-02 | 2006-05-04 | 2006-11-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-02 | 2010-05-04 | 2010-11-03 | $7700.00 | Window Closed / Lapsed |