An Approach to Fault Modeling and Fault Seeding Using the Program Dependence Graph

Abstract

We present a fault classification scheme and a fault seeding method that is based on the manifestation of faults in the program dependence graph (PDG). We enhance the domain/computation fault classification scheme developed by Howden to further characterize faults as structural and statement-level, depending on the differences between the PDG for the original program and the PDG for the faulty program. We perform transformations on the PDG to produce the different types of faults described in our PDG-based fault classification scheme. To demonstrate the usefulness of our technique, we implemented a fault seeder to embed faults in C programs. Our fault seeder makes controlled fault transformations to the PDG for a C program, and generates C code from the transformed PDG. We performed an empirical study of the relative effectiveness of dataflow testing and mutation testing using a set of faulty programs generated by our fault seeder. We found that both techniques were almost equally effective at detecting the structural faults seeded. We performed another experiment to determine the mutation and dataflow adequacy of the fault-detecting test sets. The results showed that in several cases a test set constructed to detect all structural faults in the program was nearly 100% dataflow and mutation adequate, but in some cases such fault-detecting test sets were only poorly mutation and dataflow adequate. We found that the low adequacy scores were related to the types of faults seeded, which was dependent on the program structure. An examination of the mutant profiles for the subject programs revealed that the fault-detecting test sets target particular mutant classes, and are ineffective at exposing faults that correspond to certain other mutant classes.


Related research categories:
(1) Program Analysis
(2) Testing
(3) Control Dependence

Go To Publications