FORM - 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
PROVISIONAL
specification
(See Section 10; rule 13) MODIFIED CONDITION DECISION COVERAGE (MCDC)
TATA CONSULTANCY SERVICES LTD.,
an Indian Company of Nirmal Building, 9th floor, Nariman Point, Mumbai 400 021, Maharashtra, India
THE FOLLOWING SPECIFICATION DESCRIBES THE INVENTION

This invention relates to Modified Condition Decision Coverage (MCDC).
MCDC is a software test coverage criterion.
MCDC has been found to be an effective measure of testing and hence various standards such as DO-178B, a standard followed by the airlines industry, require that the testing of critical software achieve MCDC. Developers of automotive software too are adopting MCDC as an effective measure of testing. However, creating test data to achieve MCDC is very effort intensive.
BACKGROUND:
Requirements based testing may not be sufficient to test code structure of the software, because in most cases, there isn't an exact mapping between the requirements specifications and the actual code. Because of this gap, there is a need for structural testing of the code. Structural testing is a way of measuring up to what extent the requirements based tests covered the code structure. If the requirements based tests do not satisfy a structural coverage criterion, then additional tests have to be generated until acceptable structural coverage is achieved for that measure. There are various types of structural coverage criteria: Statement, decision, condition, condition/decision, modified condition/decision and multiple condition coverage. For complete coverage of the code, multiple condition coverage is ideal, but not practical. MCDC provides the optimal practical alternative. Therefore, it has been rendered compulsory by DO-178B for level-A software certification.

The DO-178B definition of MCDC includes the property that each condition is shown to affect the decision's outcome independently. This is done by varying just that condition and holding fixed all other conditions. This is called the independent effect of that condition. Independent effect is the property that sets apart MCDC from the other coverage criteria because it guarantees a more comprehensive coverage (number of bugs found out due to MCDC) as compared to the rest of the feasible structural coverage criteria. Therefore, MCDC is demanded by software manufacturers and standardization organizations.
The independent effect property of MCDC influences the amount of test data to be created for a particular program. If the number of conditions present in the program is n, then the maximum test data that may have to be prepared is 2n, implying an average to a big test suite. But due to the following factors, the task of test suite preparation gets more and more complicated and time consuming,
1. size and complexity of the code
2. size and complexity of Boolean expressions in the code
It becomes extremely difficult to prepare test data for a large, deeply nested decisions which can be reached via multiple program paths.
3. Programmatic level of testing (unit level, functional level, module level).
Preparation of test data that satisfy MCDC for unit level testing is quite intuitive as compared to module level.
4. Validation and modification of the prepared test data due to human errors
also takes up a lot of manual time.

This invention provides a tool, that automatically generates test data to satisfy MCDC. The tool has been built around BLAST and SAL using model checking techniques. This invention also envisages optimizations required to analyze typical reactive software that have an outer loop.
The tool in accordance with this invention automates the process of test data generation for MCDC. The tool combines static and dynamic analysis on input C code. A model checker BLAST is used to generate program execution paths. These paths are fed as constraints to another model checker SAL which generates values required to satisfy these path constraints. In addition to that, the tool has execution means with the generated test data, verification means which verifies them and reporting means which reports coverage.
Figure 1 of the accompanying drawing is a flow diagram of the Tool architecture in accordance with this invention which is self explanatory.
The whole process of test data generation using the tool in accordance with this invention can be broken down into a 3-stage process:
Stage 1: In the first stage, the input code is annotated to form the input for the model checker BLAST.
Stage 2: The modified code is input to BLAST and it generates execution traces for all the conditions in the code.

Stage 3: The traces are translated to SAL specification language, which are then input to the model checker SAL. SAL generates the actual test data that satisfies MCDC.
The main strength of the tool is that the time and manual effort required to generate MCDC satisfying test data are considerably reduced. Since source code itself is taken as input, little manual effort is required to use the tool. Also, errors in generated test data are negligible. Since the tool uses model checkers at its back end, scalability of the tool is dependent on the scalability of the model checkers.
Although the invention has been described in terms of particular embodiments and applications, one of ordinary skill in the art, in light of this teaching, can generate additional embodiments and modifications without departing from the spirit of or exceeding the scope of the claimed invention. Accordingly, it is to be understood that the drawings and descriptions herein are proffered by way of example to facilitate comprehension of the invention and should not be construed to limit the scope thereof.