Software-artifact Infrastructure Repository: Handbook of SPL Object Preparation: Seeding Faults in an SPL

Seeding Faults in an SPL

A software product line (SPL) can be implemented using any programming language. Given the limited availability and our limited experience with SPLs these instructions are currently written to describe fault seeding applied to Java source objects. In the future, this document will be expanded to describe fault seeding procedures applicable to other source code languages.

1. Placing regression faults in the code

Regression faults are faults in changed code, and these are the faults in which we are interested and describe here. (Other types of faults could be inserted following a similar process.)

Fault Seeders are programmers with at least two years of programming experience in Java. Ideally, at least two faults seeders work on each object.

1.1. Finding the changes between versions

With the assistance of a code differencing (diff) tool, determine where the changes occurred. We recommend using diff -u (unified diff) in order to get more accurate differences. Be aware that if the changes between versions were large, the diff tool may carry differences forward, even when the code is identical. You should verify the differences independently and use diff only as a guide. Also, if available, you can use adiff (this can be downloaded from tools) which produces a list of changed functions.

1.2. Introducing the fault

Each programmer must do this independently to make the process as objective/credible as possible.

1.2.1. Type of fault

In your life as a programmer, you have inserted and (hopefully) removed many type of faults. This fault seeding process needs to mimic what you have found during your experience in terms of type and number of faults. Here is a simple fault classification scheme that can be helpful for thinking about different types of faults:

Faults associated with variables: definition of variable, redefinition of variable, deletion of variable, change value of variable in existing assign statement.
Faults associated with control flow: addition of new block of code, deletion of path, redefinition of execution condition, removal of block, change order of execution, new call to external function, removal of call to external function, adding function, removing function.
Faults associated with language specific constructs or facilities (such as constructors or inheritance in Java).

Although faults are sometimes more complicated than the ones just mentioned, complex faults can be decomposed into these simpler types of faults. For the integrity of the experiment, it is very important that you try to include different types of faults to simulate a real fault insertion process.

1.2.2. Fault location

A regression fault can be located only within the changes between versions (limited by the differences found in 1.1). We will be assuming then, that the programmer that made the modification inserted a fault (although we will be modifying the modified code to simulate that). There is no restriction on the size or type of fault at this stage. The only requirement is that the changed program can still be compiled and executed.

1.2.3. Faulted code

As with C and Java objects, the preferred method of inserting faults into source code is to use the cpp preprocessor to activate faults. If the code contains symbols that would confuse the preprocessor, a source code overlay method is recommended. How to use/implement the overlay method is discussed in the SPL Overlaying Faults page.

Regardless of whether the cpp or overlay method is used, each target section of code (line, block, etc) where a fault is meant to be seeded needs to be duplicated (copy and pasted). One copy will be the original, the second copy is the one with the embedded fault. For cpp inserted faults, the copies need to be enclosed in preprocessor directives as follows:

#include FaultSeeds.h
	:
#ifdef fault-id

	// code with the embedded fault

#else

	// original code

#endif

(Yes, these are C directives, we will elaborate on using the C preprocessor on fault seeded files later.)

For overlay fault insertion methods, the source file is copied and the fault inserted into the code with a comment at the location of the faulted code segment. The file will be put into a separate directory tree that maintains the original directory tree structure.

In addition, the following files should be created to keep fault-id information:

     FaultSeeds.h


     FaultSeeds.org

The FaultSeeds.h file is used by the fault-matrices generator, to map faults to the test cases that reveal them. The FaultSeeds.org is a human-readable file that describes the location of the fault by filename and relative position within the original source file.

To test a faulty version, you need to turn one of the faults on before compiling faulty version. The C preprocessor (cpp) performs this process.

The following example describes how faults should be inserted into a Java source SPL. This procedure may be extensible to other languages (obviously C) however we have not addressed at this time the needs and capabilities of other programming languages to support preprocessing of source.

Example:

Assume you have two java files to be fault seeded: A.java and B.java. Copy A.java (or B.java) into A.cpp (or B.cpp) and keep A.java (or B.java) unmodified.

After you seeded faults, A.cpp has fault-id, F_A_HD_1 and F_A_AK_1, in order, and B.cpp has F_B_HD_1, F_B_HD_2, and F_B_AK_1 in order. That is, F_A_HD_1 appears earlier than F_A_AK_1 in A.cpp file.

The FaultSeeds.h file contains all faults that reside in an object version in the following format:

#define FAULT_ID
#define FAULT_ID
#define FAULT_ID
    .
    .

Using the example, FaultSeeds.h would contain:

#define F_A_HD_1
#define F_A_AK_1
#define F_B_HD_1
#define F_B_HD_2
#define F_B_AK_1

In use, the FaultSeeds.h file will only contain a single #define fault line but your script will save a copy of the original and generate a new FaultSeeds.h containing only the desired fault. Typically using a counter in a shell script to select each line sequentially is used, e.g.

#!/bin/bash
cd $experiment_root/SUBJECT_NAME/source
counter=1
cp FaultSeeds.h FaultSeeds.save
while [ $counter -lt `cat FaultSeeds.save | wc -l` ]
do
    #
    # this selects the line by line number in FaultSeeds.h
    # and creates a new FaultSeeds.h with only that fault
    #
    sed -n ${counter}p FaultSeeds.save > FaultSeeds.h
    #
    # EqualizeLineNumbers makes all line numbers agree
    # between orig & seeded versions this eliminates false
    # diffs due to line numbering in error outputs the zero
    # (0) indicates that it should not apply any faults
    #
    while read LINE
    do
        java EqualizeLineNumbers $LINE 0 `echo $LINE | sed "s/\.cpp/\.java/"`
    done < `find ./ -name "*.cpp"`
    #
    # this extracts the fault name, need this to examine FaultSeeds.org
    #
    fault_name=`awk '{print $2}' FaultSeeds.h`
    file_fault=`grep "${fault_name}" FaultSeeds.org | awk '{print $2}'`
    file_name=`grep "${fault_name}" FaultSeeds.org | awk '{print $3}'`
    #
    # this activates only the desired fault on only the desired file
    #
    java EqualizeLineNumbers $file_name $file_fault `echo $LINE | sed "s/\.cpp/\.java/"`
    #
    # execute the tests upon the now faulted subject here
    # in this example the script runall.sh executes the test suite
    #
    ${experiment_root}/SUBJECT_NAME/scripts/runall.sh
    counter=`expr ${counter} + 1`
done

The shell script example would sequentially activate each fault on the SUBJECT_NAME object and activate each fault present in the FaultSeeds.h file. The java EqualizeLineNumbers class used in the example can perform the same actions as cpp but also provides line number adjustment to the original (unfaulted) version thus eliminating one source of nondeterministic output. EqualizeLineNumbers is available in the Java tools on the SIR Download Tools link.

1.2.4. Format of FaultSeeds.org

The FaultSeeds.org file contains all faults that reside in an object version in the following format:

[fault_id] [fault_order_in_file] [fault_file_name]
[fault_id] [fault_order_in_file] [fault_file_name]
[fault_id] [fault_order_in_file] [fault_file_name]
    :

There are no empty lines, each line corresponds to exactly one fault.

For each fault, you need to keep a record that includes:

Fault ID

the order of the fault in the source file

the name of the source file with path information relative to the FaultSeeds.h file

Historically, the fault_id contained information about fault expressed in the format: F_ClassFileInitials_FaultSeederInitials_Number although this is not enforced.

Using the example, FaultSeeds.org should be:

F_A_HD_1 1 A.cpp
F_A_AK_1 2 A.cpp
F_B_HD_1 1 B.cpp
F_B_HD_2 2 B.cpp
F_B_AK_1 3 B.cpp

In this way the faulted source files can be easily found using the UNIX/LINUX find command and fault numbering can increment in a simple numeric sequence. The historic fault_id naming methodology is most useful when multiple people are inserting faults into multiple source files.

1.2.5. Iterate over faults

We typically aim to begin with approximately 20 faults per version.

A total of Z faults (Z = MIN (number of diffs in version / 2, 10)) should be generated per version. Thus you will seed 10 faults per version or less if the number of differences is smaller than 20. Repeat the process in 1.2 until Z faults are found.

2. Selecting faults to keep for experiments

2.1. Common fault filtering

Since two programmers do the seeding process independently, some faults may be repeated. Repeated faults will be removed after all Z faults have been inserted. Although the programmers could work together to avoid overlapping, this would hurt the validity and credibility of the process so we avoid this.

The two programmers can perform this process by looking at the fault record, referring to the code when necessary to compare seeded faults that seem to be similar. If two seeded faults are identical, just add DUP to the fault record of one of the faults.

2.2. Exposure filtering

The modified code from both programmers needs to be joined. Note that only one original section is necessary per program. This should be a simple and short (maximum 10 modifications) cut/paste process but needs to be done carefully. Make sure you compile, link and test your program as you did in 1.2.4. Then, run the test suite on each version to proceed with the filtering. We will filter out two types of faults:

2.2.1. Faults that are exposed by more than X% of the tests

Overly expressive faults are those faults that are removed because they are considered too easy to find (which are unlikely to be introduced by an experienced programmer, and if they are introduced, are likely to be detected during unit testing). If a seeded fault is exposed by more than X percent of the tests, then add easy to the fault record of the faults.

2.2.2. Faults that are not detected by any tests

These non-expressive faults afford two alternatives depending on time availability. If developing a test to expose the fault would take less than Y hours, then write the new test and verify that it works. If developing a test takes more than Y hours, the write an N-EXP next to the fault description to indicate it is not exposed. The number of hours, Y, is discretionary since only you know how much effort is required and the amount of time available.

Ultimately after filtering we want 3-8 faults per version. Note that we can include only one fault per line changed.

2.3. Final Setup

Keep in the header file (FaultSeeds.h) only those fault-ids that were not filtered/discarded due to their being non-expressive or overly-expressive.

2.3.1. Use the C preprocessor to activate your faults

When you create your seeded versions, use a unique filename extension (typically we use the .cpp extension regardless of the original source type) with the original source file name (e.g. jtcas.java is the original and jtcas.cpp has the faults activated within cpp directive blocks.) By inserting only the desired fault into the FaultSeeds.h you can cause only that fault to be inserted. A shell script can be used to copy the original FaultSeeds.h to a saved copy and extract only the desired fault activation line from the file. Alternatively, you can use a script to remove

Test the program and then move on to the next version!