`

Case Study 5 : Fault Coverage Test Code Generation using Evolutionary Computation

Some form of constraint is generally evident in any search and optimization problem. The simplest explicit form relates to the upper and lower bounds of each of the variable parameters that describe the problem. Other, more complex, explicit constraint relates to inter-variable dependencies common in combinatorial problems. These may relate to a pre-defined partial ordering of the parameters or the necessity for solutions to align with several differing parameter templates to ensure feasibility. Any violation of these constraints must be amended before we evaluate the solution.

The following work carried out for Rolls Royce Associates illustrates the manner in which evolutionary computing can manage such constraint whilst also avoiding convergence upon local optima and identifying high performance solutions. The work relates to the design of industrial test and monitoring systems (TAMS) widely used for real-time testing of the functionality of electronic circuits. TAMS operate by regularly initiating test cycles on simulated test circuits with constant monitoring of fault status. The integral component is the fault coverage test code which comprises a set of input test vectors and a set of expected output vectors. Fault analysis is utilised to determine the fault detection coverage of a particular test code. The problem involves the design of the input stimulus (ie test code) in order that the code fully exercises all components and increases testability - see figure below.

The degree of fault coverage within a design depends on the comprehensiveness of the test code. The problem therefore relates to the discovery of an effective set of input test vectors. A test code comprises N test vectors each of length m bits and strict constraints exist on the possible combinations of values within each individual test vector. These relate to a set of legal combinations in terms of the legal states of a number of channels. Each channel is logical grouping of input bits. Collectively the legal states of all channels define a set of legal (supporting) templates of the form:

1*0**1011**

where * is a don’t care symbol.

Channel 1Channel n
**0**0*1****0*0***1*1***
**0**1*1****0*1***0*1***
**1**0*0****0*1***1*1***
**1**0*1****1*0***0*1***
**1**1*0**** 

The set of legal test codes is defined by the legal states of a number of logical channels and the set of all legal templates defines the feasible region of the test code design space.

In order to integrate the powerful search and optimization capabilities of evolutionary computation with the test code design process it is necessary to ensure the generation of successive population of legal trial solutions. This was achieved through the design of feasibility preserving search operators which, when applied to feasible point(s) always produce another feasible point(s). Two versions of mutation and one of crossover were designed to comply with a selected constraint handling technique and the resulting software was fully tested and integrated with the TAMS test code design process.

The application of an Inductive Genetic Algorithm with the modified mutation and crossover routines on a fault coverage problem consisting of 200 possible faults with 24 input test vectors achieved a fault coverage of 71.5% within 9,000 fitness function calls. This was a very significant improvement over previous work within Rolls Royce and Associates which involved a classical genetic algorithm w ith no specialized where the best produced fault coverage for 9,000 fitness function calls was 57% which was below the 70% threshold for the circuitry to pass design specification.