Dynamic Slicing of Feature-Oriented Programs

Abstract

Program slicing is the process of decomposing a program pertaining to a specific computation in a program. Program slicing has many applications in software engineering activities such as debugging, reverse engineering, software testing, software refactoring, etc. This thesis presents our work concerning dynamic slicing of feature-oriented programs. We first select the features that are required to be composed to produce a software product. The selected features are then composed using a composer. Then, we propose an algorithm called Execution Trace File Based Feature-Oriented Dynamic Slicing (ETBFODS) algorithm to compute the dynamic slices of feature-oriented programs. Our algorithm first executes the program with a given input. The executed statements are stored in a trace file called execution trace file in order of execution. Every time a statement is executed, it is stored in the execution trace file. The ETFBFODS algorithm uses a dependence based intermediate program representation called Dynamic Feature Composition Dependence Graph (DFCDG). The DFCDG is constructed by creating separate nodes for each statement in the execution trace file. The edges in the DFCDG represent various dependence relationships amongst statements. Then, the DFCDG is traversed either in breadth-first or depth-first manner beginning from a node of interest and the traversed nodes are mapped to the program to produce the dynamic slice. We have developed a tool called feature-oriented dynamic slicing tool (FODST) to implement our proposed algorithm. We have tested the performance of our tool with several case studies. Also, we have shown that the space complexity of our algorithms is O(S 2 ), and the time complexity is O(S 2 ), where S is the length of execution of the program. Next, we develop another suitable intermediate representation for simple feature-oriented programs. This intermediate representation is known as composite feature-oriented dependence graph (CFDG). Then, we present a dynamic slicing algorithm, called feature-oriented node-marking dynamic slicing (FONMDS) algorithm for simple feature-oriented programs using CFDG as the intermediate representation. Our FONMDS algorithm is based on marking and unmarking the executed nodes of the CFDG appropriately during run-time. We have developed a tool called feature dynamic slicing tool (FDST) to implement our proposed algorithm. We have taken several case studies to test the performance of our algorithm. We have shown that the space complexity of our algorithms is O(n 3 ), where n is the number of statements in the program and the time complexity is O(n 2S), where S is the length of execution of the program. vii Next, we develop an algorithm to compute dynamic slices of feature-oriented programs with aspect-oriented extension. We extend our intermediate representation CFDG to incorporate “aspects”. We have named this intermediate representation composite feature-aspect dependence graph (CFADG). Then, we extend our feature-oriented node marking dynamic slicing (FONMDS) algorithm to handle the “aspects”. We have named our algorithm feature-aspect node-marking dynamic slicing (FANMDS) algorithm for feature-oriented programs that contain “aspects”. Then, we construct a dynamic slicing tool called feature-aspect dynamic slicing tool for implementation of our FANMDS algorithm. The performance of our algorithm has been tested on several case studies. The space complexity of FANMDS algorithm is O(n 3 ), where n is the number of statements in the program and the time complexity is O(n 2S), where S is the length of execution of the program. Next, we propose an algorithm to compute dynamic slices of concurrent feature-oriented programs i.e., for feature-oriented programs with multithreading support. We extend our intermediate representation CFDG to support concurrency. We have named this intermediate representation concurrent composite feature dependence graph (CCFDG). Then, we extend our feature-oriented node marking dynamic slicing (FONMDS) algorithm to handle concurrency features. We have named our algorithm concurrent feature-oriented node-marking dynamic slicing (CFNMDS) algorithm. Then, we construct a dynamic slicing tool called concurrent feature-oriented dynamic slicer (CFDS) for implementation of our CFNMDS algorithm. Several case studies have been taken to test the performance of our algorithm. The space complexity of CFNMDS algorithm is O(n 3 ), where n is the number of statements in the program and the time complexity is O(n 2S), where S is the length of execution of the program. If a program contains neither aspect-oriented extensions nor concurrencies, then the slicing algorithm ETBFODS or FONMDS can be used. It has been found that out of ETBFODS algorithm and FONMDS algorithm, FONMDS algorithm gives much less slice computation time. For a feature-oriented program containing aspect-oriented extensions, the FANMDS algorithm can be used. For a feature-oriented program with support of concurrency, the CFNMDS algorithm can be used