Automatic data generation for MC/DC test criterion using metaheuristic algorithms

Testing has traditionally been one of the main techniques contributing to high software dependability and quality. Testing activity consumes about 50% of software development resources, so any technique aiming at reducing software-testing costs is likely to reduce software development costs. Indeed, exhaustive and thorough testing is often unfeasible because of the possibly infinite execution space or high cost with respect to tight budget limitations. High dependability computerized systems are often software intensive systems belonging to regulated domains such as aerospace and medical application domain. In such domains, quality assurance and testing activities are enforced by law or required by mandatory standards, such as DO-178B, DO-254, EN-50128, IEEE/EIA 12207, or ISO/IEC i2207. These standards and regulations enforce verification and validation activities and they specify the required testing coverage criteria.;This work explores the way search techniques can be integrated with branch distance, control and data dependencies to generate MC/DC test input data at method level. Our approach is organized in two steps. First, for any given predicate, we compute the sets of test cases that would cover the MC/DC criterion for this predicate. In the second step, we apply meta-heuristic search strategies to generate test input data assigning true and false Boolean values to clauses so that one of the MC/DC test case computed in step one is satisfied.;We propose a novel fitness function to efficiently generate test input data satisfying the MC/DC criterion. In particular we draw inspiration from the Chaining approach integrating data dependencies in the fitness design and evaluation. We extended the algorithm proposed by McMinn for the branch distance fitness adapting it to MC/DC.;To assess the feasibility of our approach we implemented a prototype of a test automation tool for code written in Java and applied it to the well-known 'Triangle' and 'NextDate' programs. We report evidence of the superiority of the new fitness function that is able to avoid plateau leading to the degradation of the optimisation search techniques to a random search as in the case of traditional white box fitness functions. The primary contribution of this work can be summarized as follows: (1) We propose a search based approach to generate MC/DC test input data; applying the Search Based Software Engineering problem techniques to testing. (2) We propose a novel fitness function in which we integrate data dependencies via control dependencies in a new fitness function tailored for MC/DC. (3) We extend the algorithm to define the fitness function to cope with mutually interacting data and control dependencies.;Proposed by NASA in 1994, the Modified Condition/Decision Coverage (MC/DC) criterion is a testing strategy required, among other practices, by the RTCA DO-178B. MC/DC is a white box testing criterion aiming at proving evidence that all clauses (Boolean expression not containing any logical operator such as z > x + y) involved in a predicate can influence the predicate value in the required way. It subsumes other well-known coverage criteria such as statement and decision coverage.