Error detection/correction and fault detection/recovery – Data processing system error or fault handling – Reliability and availability
Reexamination Certificate
2000-09-15
2004-02-24
Iqbal, Nadeem (Department: 2184)
Error detection/correction and fault detection/recovery
Data processing system error or fault handling
Reliability and availability
C714S032000
Reexamination Certificate
active
06697961
ABSTRACT:
BACKGROUND OF THE INVENTION
A software system contains a functionally closed set of procedures. In order to ensure correct implementation of the software system, it is desirable to determine a software contract, i.e., elements and functional specifications of external interfaces of the software system, and carry out conformance testing of the software contract implementation. Since the elements of the software contract are procedures, it is in fact Application Programming Interface (API) testing.
A kernel of an Operating System (OS) comprises API. For example, a Support Operating System (SOS) is a real-time OS for a Digital Multiplexing Switch (DMS) for a communication system. SOS comprises a plurality of processes for supporting the operation of DMS. The lowest layer of SOS is SOS kernel. The SOS kernel allocates resources to the processes running under SOS. The SOS kernel also provides communication among these processes. The SOS kernel also creates, controls and removes these processes.
SOS supports more than 25 million lines of code for applications and utilities. Thus, it is critical that user procedure interfaces of the SOS kernel be stable and reliable for correct performances of the DMS switch. The SOS kernel consists of over 1,700 procedures or over 230,000 lines of source code. Thus, it is very complicated and time consuming processes to generate a system for verifying such complex procedure interfaces. There existed no automatic or semi-automatic mechanisms to aid such generation of a verification system.
At the same time, SOS continuously evolves. Also, SOS is often ported to new hardware and software platforms. While more than 75% of the kernel procedures are machine-independent, the remainder of the kernel procedures are very machine dependent. The remainder describes particularity of memory, inter-processor communication and communication with peripheral devices. Accordingly, when SOS evolves or SOS is ported to a new platform, the SOS kernel and its procedure interfaces are also modified. Thus, the verification system for the procedure interfaces of the SOS kernel also needs to be modified. However, there existed no automatic or semi-automatic modifying mechanisms to aid such modifications.
To estimate test coverage, it is known to use Disjunct Normal Form (DNF) criterion. The DNF criterion allows estimating the number of functional branches in a procedure, i.e., the number of disjuncts in DNF. It also allows estimating conditions to follow a functional branch, depending on input parameter values and system state variables, i.e., conjunction of predicates in a disjunct.
For construction of DNF, the functional specification of a procedure is analysed as logic expression and is transformed into DNF. This method involves a problem that conventional methods of transformation of logic expression into DNF are developed only for the cases when the predicates of logic expression are independent from each other. However, in practice, the predicates, as a rule, have dependencies on each other.
There are two types of dependency. The first type of dependency exists between two predicates which cannot hold true simultaneously. The second type of dependency makes a predicate computable only when the other predicate holds a specific value, i.e., true or false. An example of the first type of dependency is the case when the first predicate is a function that holds true when its parameter is negative, and the second predicate holds true when parameter exceeds some positive value. An example of the second type of dependency is the case when the first predicate holds true when parameter i is in the range of allowable indices of some array, and the second predicate holds true when i-th element of this array is equal to some constant. In this case, if the first predicate does not hold true, then second predicate cannot be calculated at all since exception will be raised when attempting its calculation.
Such dependencies cannot be found automatically in general case by the existing method. If DNF is built without consideration of existing dependencies between predicates, a part of disjuncts will be unattainable, and estimation of test coverage will be incorrect.
In order to obtain correct test coverage estimation, DNF could be constructed manually by estimating the number of disjuncts, and then generating a procedure that calculates to which disjunct the given set of test parameters corresponds. However, manual construction of DNF involves the large effort required and tools needed to check correctness of the constructed DNF.
Another known test coverage criterion is Full Disjunct Normal Form (FDNF) criterion. The advantages of the FDNF criterion is its independence from the procedure implementation. Values of Boolean types, “true” and “false”, are typically used to describe values of predicates involved in disjuncts in FDNF. To define the FDNF criterion, all disjunct of FDNF must be described. Each disjunct is equal to the conjunction of all predicates defining the functional branches of the procedure or their negations. A list of boolean values of all predicates is used as the standard form of disjunct description. However, the standard form of disjunct description can be applied only in case when all predicates can be calculated. When there are the dependencies between the predicates the value of predicates cannot be calculated and the standard FDNF criterion cannot be defined.
It is therefore desirable to provide a system and method which efficiently and correctly allow estimation of test coverage of procedure testing carried out by a verification system for procedure interfaces.
SUMMARY OF THE INVENTION
The present invention uses logic expressions of predicates in functional branches in the procedure to generate functions of functional specification of the procedure to estimate test coverage during procedure testing. In an embodiment, Disjunct Normal Form (DNF) is generated using short logic which omits calculation of an operand when another operand defines the result of the calculation. In another embodiment, Full Disjunct Normal Form (FDNF) is generated using three-sign logic.
In accordance with an aspect of the present invention, there is provided a method for estimating test coverage of procedure testing with functional specification of a procedure. The method comprises describing predicates in functional branches in the procedure as logic expressions; adding the logic expressions of predicates to logic expressions of pre-condition of the procedure; generating, based on the logic expressions, functions of the functional specification of the procedure; and estimating coverage during the procedure testing.
In accordance with another aspect of the present invention, there is provided a method for describing dependencies between predicates for construction of Disjunct Normal Form (DNF) from functional specification of a procedure for estimation of test coverage of procedure testing with functional specification of a procedure. The method comprises describing dependencies between predicates in disjuncts in the procedure as logic expressions by: determining dependencies of pairs of predicates writing dependency as implication for a pair when predicates included in the pair are dependent; and constructing conjunction of the implications.
In accordance with another aspect of the present invention, there is provided a system for describing dependencies between predicates for construction of Disjunct Normal Form (DNF) from functional specification of a procedure. The system comprises a dependency handler, a short logic calculator and a long logic calculator. The dependency handler is provided for determining dependencies of pairs of predicates in disjuncts in the procedure, and for adding logic expressions of dependencies to logic expressions of pre-condition of the procedure. The short logic calculator is provided for calculating implication as logic expression of dependency of a pair of predicates when the predicates included in the pair are dependent. The long logic calculator is
Burdonov Igor B.
Galter Dmitri
Kossatchev Alexander S.
Maximov Andrei V.
Petrenko Alexander K.
Iqbal Nadeem
Nortel Networks Limited
Withrow & Terranova , PLLC
LandOfFree
Method and system for describing predicates in disjuncts in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for describing predicates in disjuncts in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for describing predicates in disjuncts in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3289344