Article Preview
Top1. Introduction
Program slicing is a decomposition technique utilized to decompose programs depending on control flow and data flow amongst several lines of code in a program code. It is a kind of program analysis technique. It takes out statements related to computation of a variable’s value at a specified point in program. The pulled out statements, containing assignment and predicate statements, constitute a program slice. These statements may affect or be affected by value of variable v at program location l. A slice is computed by employing a slicing criterion. The tuple < l, v > is regarded as a slicing criterion. The slice may be static or dynamic according to input to program code. It is said to be static when it extracts all statements from a program code w.r.t. a slicing criterion regardless input to program (Weiser, 1981). On the other hand, it is said to be dynamic when all statements from a program are extracted w.r.t. a slicing criterion for a specific input to program code (Korel & Laski, 1988).
Program slices are computed in two steps. The first and foremost step is concerned with the construction of an intermediate symbolization of program code. In next step, an algorithm is applied to that intermediate representation to find out slices. Program slicing has been employed in many areas of software engineering like debugging, software maintenance, testing, functional cohesion, software refactoring, software quality assurance, etc.
Conditioned slicing is a generalization of static slicing and dynamic slicing (Canfora et al., 1998). A conditioned slice is in the form of a tuple <Pr,lc,q>, where Pr is a condition, lc is a required statement in program code and t is a variable. Conditioned slicing puts away those chunks of original program that cannot affect variables at required statement upon satisfaction of conditions. A conditioned slice is computed in two steps: first, the program is simplified with respect to condition provided in slicing criterion. Thus, statements, not satisfying given condition, are removed. Then, a slice is computed on the reduced program. The reduced program is referred to as a conditioned program. More details on conditioned slicing can be obtained in (Canfora et al., 1998; Cheda et al., 2008; Danicic et al., 2000; (Danicic et al., 2004; Fox et al., 2004; Harman et al., 2001; Hierons et al., 2002).
Motivation
Static slicing does not take into account the information about execution state of the program code. Thus, static slices are constructed irrespective of the input to the program code. Dynamic slicing utilizes the complete information about execution behavior of the program. Thus, dynamic slices are dependent on input to program code. There must be a slicing technique that preserves the execution behavior of the program and is independent of input to the program. Conditioned slicing solves this problem by computing the slices at a particular program point for a variable with respect to a condition. Nowadays, most of the programs are interprocedural in nature. There is hardly any work done on conditioned slicing of interprocedural programs. This paper demonstrates a technique to find out conditioned slices of programs containing multiple procedures.
Objectives
The objective of this work is to propose an algorithm to determine conditioned slices of interprocedural programs using an intermediate representation, a dependence graph. The authors also aim at computing slice time for various programs of different lines of code.
The structure of the rest of paper is done as per following ways. Section 2 delivers some background details of the proposed technique. In Section 3, literature survey is discussed. In Section 4, the proposed approach, i.e., Node-Marking Conditioned Slicing (NMCS) algorithm for interprocedural programs is discussed. Section 5 outlines complexity analysis of NMCS algorithm. In Section 6, the correctness of NMCS algorithm is established. Section 7 provides the implementation and experimental results of the proposed technique. Section 8 provides conclusions and future works.