Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
2000-11-30
2004-08-17
Iqbal, Nadeem (Department: 2114)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C714S037000
Reexamination Certificate
active
06779135
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to testing software, and specifically to testing concurrent and/or distributed software.
BACKGROUND OF THE INVENTION
Tests for checking sequential software, i.e., software which runs on one platform and which has only one thread, are well known in the art. The tests are used to give a level of assurance that the software is fault-free, and may also detect and locate faults in the software. The tests vary in their ability to perform these tasks. For example, one may create a set of tests which ensures that every statement in a program has been executed. In this case, however, even successful completion of the tests will not necessarily detect a fault due to a statement which incorrectly defines a value of a variable. In order to detect such a fault, a second test checking and/or setting values of variables may be necessary. In general, whether a particular set of tests on sequential software detects a fault depends on the tests and on values of variables which are used by the tests.
In the context of the present patent application and in the claims, the terms “coverage,” “coverage level,” and “level of coverage” refer to a metric of completeness with respect to a test or a set of tests. Considering the example above, a test or set of tests may ensure that all statements are executed, in which case these tests provide 100% statement coverage. However, as shown in the example above, tests which provide 100% statement coverage for specific software being tested do not necessarily complete testing coverage for the software in all respects, so that the overall level of coverage of the software may be low.
Coverage analysis defines the concept of a “good set of tests” by formalizing the tests developed to ensure that as many areas of a program as possible are tested, to ensure that the coverage level of each of the areas is known, and to give measures for these coverage levels and for the overall coverage for the program. The purpose of coverage analysis is to direct the sampling process of a set of tests so that the end result is effective in revealing defects. Coverage analysis creates a sequence of testing goals, usually expressed as a hierarchy of coverage requirements, so that achieving each goal marks a higher confidence level in the “correctness” of the program. Thus, when a required overall level of coverage is achieved, we can state with some level of certainty (related to the overall level of coverage) that the software under test is free of defects. Coverage may also be used as a stopping criterion for the testing process, i.e., when a certain level of coverage is achieved testing is stopped.
In the context of the present patent application and in the claims, a “coverage task” denotes a Boolean function on a test, and a “coverage model” denotes a definition of a particular type of coverage which is able to generate a corresponding set of coverage tasks. The outcome of a Boolean function on a test is the result of the function. For example, in a model designed to determine statement coverage of a program, the model will provide a set of outcomes of coverage tasks, such as “ . . . , statement
534
was executed in this text, statement
535
was not executed in this test, statement
536
was executed in this test, . . . .”
FIG. 1
is a flowchart that schemtically shows a method for testing software, as is known in the art. In order to test the software, in a first step
10
, a set of tests is generated according to predetermined guidelines, such as in the example described above. In a run step
11
, the tests are run on the software, and the coverage is estimated. In a check step
12
, missing coverage is estimated by comparing a coverage list comprising all possible coverage tasks with the actually covered coverage tasks from the tests. Further tests are performed, in a generate new tests step
13
, in order to reduce the missing coverage. The further tests may follow the initial guidelines and/or may comprise further guidelines. The testing procedure concludes when a required level of coverage has been reached.
FIG. 2
is a block diagram schematically showing a process for testing sequential software
16
, as is known in the art. Initially, sets of tests
14
are developed which are intended to perform checks
15
corresponding to execute each statement, execute each branch, and execute each define-use relation of the program. The sets of tests are run on the software, with initial inputs from a sample space
17
of all possible inputs for the software. After the tests have been run, software
16
outputs coverage lists
18
of which statements, branches, and define-use relations have been executed. From these lists an estimate of the coverage of the tests can be made. The tests may then be modified to change how the tasks listed above are preformed and/or to choose different inputs from the sample space. The modified tests are run and the process is continued, as described above with reference to
FIG. 1
, until a required level of coverage is achieved. It will be appreciated that because the sample space of a typical program is in general extremely large or even infinite, it is impossible to run all possible tests on the program.
Testing concurrent and/or distributed programs (CDPs), which comprise a plurality of threads and/or operate on a plurality of distributed platforms, is known to be significantly more complicated than testing sequential software. Whereas in sequential software the result produced by the program is uniquely determined by the inputs selected, in the case of CDPs the result produced depends both on the input space and on the order in which different tasks implemented by the CDP are performed. Thus, in order to determine the result for a specific CDP, additional information in the form of a sequence of schedule decisions in the case of concurrent programs, and/or an order of message arrival in the case of distributed programs, is required. In the context of the present patent application and in the claims, a set of such additional information is termed an “interleaving,” and the set of all possible interleavings for a CDP is termed the interleaving space for the CDP. A test on the CDP is of the form (input, interleaving), wherein the interleaving is applied in conjunction with the given input. While a set of tests which covers all possible inputs and all possible interleavings will theoretically detect all defects, such a set cannot be implemented in practice.
Practical methods for testing the CDPs are known in the art. For example, in an article entitled “All-define-use-path Coverage for Parallel Programs” by Cheer-Sun D. Yang et al., presented in the Association of Computing Manufacturer's Special Interest Group on Software Engineering (ACM SIGSOFT), in their International Symposium on Software Testing and Analysis, 1998 (ISSTA 98), which is incorporated herein by reference, the authors suggest applying a define-use coverage criterion to a generalized control-graph of the CDP.
In an article entitled “Testing Concurrent Programs: A Formal Evaluation of Coverage Criteria” by Factor et al., in
Proceedings of the
7
th
Isreal Conference on Computer Systems and Software Engineering
(1996), which is incorporated herein by reference, the authors describe an adaptation of techniques used for evaluating sequential program coverage criteria to an abstract concurrent language.
Methods for testing CDPs typically look for defects which occur in patterns. For example, access to a common variable by two or more external agents could affect the result of the CDP, depending on which agent accesses the variable first. Thus, a general defect pattern which could cause defects is access to a global common variable.
In a section of a “User Manual of a Generic Coverage Tool (GCT)” entitled “Using Race Coverage with GCT” by Marick, which manual can be found at http://www.mirror.ac.uk/sites/ftp.cs.uiuic.edu/pub/testing/gct.files/ftp.txt, and which is incorporated herein by reference, the author describe
Farchi Eitan
Ur Shmuel
Bonura Timothy M.
Darby & Darby
Iqbal Nadeem
LandOfFree
Interleaving based coverage models for concurrent and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interleaving based coverage models for concurrent and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interleaving based coverage models for concurrent and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3272945