-Program slicing as a program analysis technique extracts the statements of a program to restrict the focus of a task to specific sub-components of a program. This technique has many applications in software maintenance such as debugging, regression testing, program understanding and reverse engineering. Most of the researches in program slicing used the different type of dependence graphs as intermediate representation tools and then proposed the slicing algorithms based on it. Drawing the dependence graphs to represent large and complex programs is very complicated and it is impossible in non-automatic approaches that requires the experted user to perform an extensive amount of manual work to apply the proposed approach. Moreover scrolling a dependence graph to find the executable slices of a program is one of the most common issue in software testing. In this paper, we introduce the program dependence table as a new intermediate representation tool. Then, we proposed five automatic intra-procedural slicing algorithms including forward, backward, chop, union and backbone based on the program dependence table.
Software testing as a vital part of software development
is a process of executing a software program with the intent
of finding potential errors [
Copyright held by the author(s).
The basic idea of program slicing was first introduced by
Weiser in 1981 [
Drawing the dependence graph to slice large and complex
programs is very complicated and it is impossible in
nonautomatic approaches that requires the expert user to perform
an extensive amount of manual work to apply the proposed
approach [
In this paper, we will introduce the program dependence table (PDT) as a new intermediate representation tool and five automatic slicing algorithms including forward, backward, chop, union and backbone based on the dependence table. The proposed algorithms can compute static slices of an intraprocedural program based on its PDT.
The layouts of the paper are as follows: In Section II are mentioned the basic concepts of program dependence graph and various types of program slicing including backward, forward, chop, backbone and union. In Section III, the details of PDT for intra-procedural programs are presented. Our proposed slicing algorithms are described in Section IV and at the end Section V concludes the paper with some insights into our future works.
As we mentioned, program slicing reduces the program to those statements that are relevant for a particular context. To do so, it utilizes the dependency relation between the program statements to identify the statements that affect or are affected by a point of interest, which is called slicing criterion [23]. This point consists of a pair hs; vi, where s is a program point and v is a subset of program variables. The approach of slicing is based on a Program Dependence Graph (PDG).
A PDG G = hV; E i is a directed graph where V is the statements of a source program and E is the dependence relations (i.e. data dependence or control dependence) between the statements. An edge si ! sj where si; sj 2 V represents dependence of the statement sj on statement si.
Definition II.1. Control Dependence: There is a control
dependency between the statements si and sj , if si is a
conditional predicate and execution of sj is determined by
the result of si [
Definition II.2. Data Dependence: There is a data
dependency between the statements si and sj , if for any variable
x 2 si assigns the value to x 2 sj refers to x, and there exists
at least one execution path in between si and sj without the
value of x being changed [
Fig. 2 demonstrates the PDG of Fig. 1.a. In the graph c d si ! sj shows control dependency edge and si ! sj denotes data dependency edge. For more clear, we explain this example: since the statement main (i.e. s0) has control dependence on statements s1 s7 and s13 s15, therefore a control dependency edge exists from s0 to s1 s7, s12 and s13, while statement while (i.e. s7) has control dependence on s8 s12, so a direct control edge exists from s7 to s8 s12. On the other hand, variable a is defined by statement s2 and used by s8, s9 and s13, so a data dependency edge exists from s2 to s8, s9 and s13.
Program slicing can be divided into five types of categories: backward, forward, chop, backbone and union. Briefly, they are the following:
Backward program slicing: In backward slicing, we are interested in all the statements that could influence the slicing criterion, so we traverse the program backward from the slicing criterion. It can help us to find localizing errors. Fig. 1.b and Fig. 1.c show the backward program slices of hs13; qi and hs14; spi respectively.
Forward program slicing: In forward slicing, all the statements that could be influenced by the slicing criterion are interested, so a program can be traversed forward from a desired point. It is useful when a statement is modified and we want to check the statements affected by the modification statement no. a s0 main()f s1 int a=0; s2 int q=0; s3 int p=1; s4 int sp=0; s5 int n=0; s6 cin>>n; s7 while (n>0)f s8 q=q+n; s9 p=q*q; s10 sp=p+sp; s11 n=n-1; s12 g s13 cout<<q; s14 cout<<sp; s15 g d e q=q+n; p=q*q; sp=p+sp; cout<<q; cout<<sp; q=q+n; cout<<q; b main()f int q=0; int n=0; cin>>n; while (n>0)f q=q+n; n=n-1; g cout<<q; g f main()f int q=0; int n=0; cin>>n; while (n>0)f q=q+n; n=n-1; g g c main()f int q=0; int p=1; int sp=0; int n=0; cin>>n; while (n>0)f q=q+n; p=q*q; sp=p+sp; n=n-1; g cout<<sp; g g main()f int q=0; int p=1; int sp=0; int n=0; cin>>n; while (n>0)f q=q+n; p=q*q; sp=p+sp; n=n-1; g cout<<q; cout<<sp; g which is called ripple analysis. Fig. 1.d demonstrates forward program slice of hs8; qi.
Chop: Chop is the intersection of a forward and a backward slice. Fig. 1.e shows a chop for the forward program slice hs8; qi and the backward program slice hs13; qi. Chops can help us to discover how one statement influences another statement.
Backbone: Backbone is the intersection of two backward slices. Fig. 1.f shows a backbone for hs13; qi and hs14; spi. Backbones are useful for discovering the parts of an application that contribute to the computation of several values [24].
Union slicing: The union of backward slices for all output variable of a program is called union slicing. Fig. 1.g denotes the union slicing for the program of Fig. 1.a. Clearly, this slicing includes all the statements of backward slices hs13; qi and hs14; spi. A union slice can help us to find the dead codes. For example, the union slice in Fig. 1.g does not include s1, hence this statement can not effect on the outputs and it is a dead code.
On the other side, we can divide program slicing into two categories: dynamic and static. A dynamic program slice is a subset of the program that is entirely defined on the basis of a computation, i.e., it depends on the specific value for the desired variable. While a static program slice is generated from program structure [25].
III. PROGRAM DEPENDENCE TABLE
Program Dependence Table (PDT) is a m m matrix where m is the number of program statements. PDT is created by the algorithm 1.
Our algorithm takes s code as the input source code and returns its PDT. The algorithm uses two initially empty global stack, called DS and LS which store all dependencies between the statements and dependencies between the loop statements (e.g. for, while, etc) respectively. We also define a list for each variable x in the source code to store its def-statements (we call it Ldef (x)).
Definition III.1. def-statement: If the variable x is defined in the statements si then si is called def-statement of x.
Now we describe our encoding for each statement in the source code such as si 2 V: (a) if the stack DS is not empty then we set P DT [tos(DS); i] to c, where tos(DS) returns first element of DS located on the top of the stack. This means that, there is a control dependency between si and tos(DS). (b) for any used variable x 2 si, we set P DT [Ldef (x); i] to d, i.e. there is a data dependency between si and all defstatements of x. (c) For each defined variable in si such as x, we add i to Ldef (x). (d) If si is a type of loop statements, then we push i on the stack LS. (e) If si contains f, we push i on the stack DS. (f) If si contains g, then we set P DT [i; tos(DS)] to c. Next, if tos(DS) = tos(LS), then we check the equality of first and second elements of the stack LS. If they are equal, then LS will be popped twice, otherwise we jump from si to the line tos(LS) of source code. finally,
Algorithm 1 Creating PDT 1: for all si 2 s code do 2: if not(empty(DS)) then 3: P DT [tos(DS); i] c 4: end if 5: Xused all used variables(si) 6: for all x 2 Xused do 7: P DT [Ldef (x); i] d 8: end for 9: Xdef all def ined variables(si) 10: for all x 2 Xdef do 11: Ldef (x) Ldef (x) [ i 12: end for 13: if si is a loop statement then 14: push i on LS 15: end if 16: if si contains f then 17: push i on DS 18: end if 19: if si contains g then 20: P DT [i; tos(DS)] c 21: if tos(DS) = tos(LS) then 22: if tos(LS) = sos(LS) then 23: pop LS 24: pop LS 25: else 26: jump to stos(LS) 27: end if 28: end if 29: pop DS 30: end if 31: end for 32: return P DT the top of DS will be popped off. The reason of doing steps (e) and (f) is making the executable slices.
For more clear, we explain our algorithm for the program of Fig. 1.a. Since the stack DS is empty when we encounter the statement s0 and also no variable has been used in this statement, so P DT does not change. Moreover, s0 is not a def-statement, hence no element is added to the def-statementlists. Statement s0 has f, so we push 0 on the stack DS (see row 2 in Table I).
For the statement s1, top of DS is 0, so P DT [0; 1] is set to c. The variable a has been defined in s1, thus we add 1 to the def-statement-list Ldef (a). Other conditions are not satisfied in this statement (see row 3 in Table I). Statements s2 s5 are encoded in a similar way.
When we encounter s6, top of the stack DS is 0, thus P DT [0; 6] = c. Since the variable n has been used in s6 and Ldef (n) = f5g, hence P DT [5; 6] is set to d. Further, s6 defines the variable n, so we add 6 to the def-statement-list Ldef (n) (see row 8 in Table I).
For the statement s7, since tos(DS) = 0 thus we set P DT [0; 7] to c. This statement uses the variable n, so P DT [Ldef (n); 7] is set to d where the def-statement-list of n contains 5 and 6. Moreover, we push the number of this statement on DS and LS because s7 has f and it is a loop statement (see row 9 in Table I).
Top of the stack DS is 7 when we encounter s8, thus P DT [7; 8] = c. The variables n and q have been used in s8, so the proposed algorithm assigns the data dependency between s8 and the def-statements of n and q. Since Ldef (n) = f5; 6g and Ldef (q) = f2g thus P DT [5; 8], P DT [6; 8] and P DT [2; 8] are set to d. Note, s8 defines q, hence we add 8 to the def-statement-list of q (see row 10 in Table I). Statements s9 s11 are encoded in a similar way.
For the statement s12, top of DS is 7, so P DT [7; 12] is set to c. Since s12 contains g, thus P DT [12; 7] = c. Then we jump to s7 because top of DS and top of LS are 7 and the first and second elements of the stack LS are not equal. Moreover the top of DS is popped (see row 14 in Table I). Now the statements s7 s12 are checked again by our algorithm. Table II demonstrates the PDT of the program of Fig. 1.a.
In the following, we prove the correctness of the proposed algorithm. This proof consists of three parts: (1) completeness, (2) correctness and (3) finiteness. In completeness step, we prove that our algorithm is complete, i.e. it covers all the possible cases, Then in correctness step we prove that the algorithm is correct, and finally we show that the proposed algorithm terminates after a finite number of iterations.
Consider different kinds of the statements in C language: simple statements and compound statements. Simple statements include statements that do not contain other statements (e.g. assignments, jumps) while compound statements appear as the bodies of another statements (e.g. conditions, loops). Simple or compound statements might define or use a subset of program variables. Used variables are covered by lines 5-8 and defined variables are covered by lines 9-12. A compound statement consists of a pair of braces fg. This condition is covered by lines 2-4, 16-18, 19-20 and 29. Note, loop statements are the compound statements that must be traversed twice, once forward and once backward. This condition is covered by lines 21-28.
To prove the correctness of our algorithm, consider the statement si. If the stack DS is empty, thus si is a function header, otherwise it is clear that si is a function body statement. Function body statements might have braces, use or define a subset of program variables. All these conditions are covered by the proposed algorithm.
Finally, since the number of statements of a program always is finite, thus our algorithm stops after a finite number of steps.
IV. PROGRAM SLICING BASED ON PDT
In this section, we present two algorithm for backward and forward program slicing based on PDT. Since chop, backbone and union slices can be generated from backward and forward slices, we do not consider any algorithm for them.
Out backward program slicing is presented in Algorithm 2. Let p be a source code and P DTp be its corresponding P DT [7; 12] = c P DT [12; 7] = c P DT [0; 7] = c P DT [5; 7] = d P DT [6; 7] = d P DT [11; 7] = d P DT [7; 8] = c P DT [5; 8] = d P DT [6; 8] = d P DT [11; 8] = d P DT [2; 8] = d P DT [8; 8] = d P DT [7; 9] = c P DT [5; 9] = d P DT [6; 9] = d P DT [11; 9] = d P DT [2; 9] = d P DT [8; 9] = d
Ldef (x) a = f1g a = f1g q = f2g a = f1g q = f2g p = f3g a = f1g q = f2g p = f3g sp = f4g a = f1g q = f2g p = f3g sp = f4g n = f5g a = f1g q = f2g p = f3g sp = f4g n = f5; 6g a = f1g q = f2g p = f3g sp = f4g n = f5; 6g a = f1g q = f2; 8g p = f3g sp = f4g n = f5; 6g a = f1g q = f2; 8g p = f3; 9g sp = f4g n = f5; 6g a = f1g q = f2; 8g p = f3; 9g sp = f4; 10g n = f5; 6g a = f1g q = f2; 8g p = f3; 9g sp = f4; 10g n = f5; 6; 11g a = f1g q = f2; 8g p = f3; 9g sp = f4; 10g n = f5; 6; 11g a = f1g q = f2; 8g p = f3; 9g sp = f4; 10g n = f5; 6; 11g a = f1g q = f2; 8g p = f3; 9g sp = f4; 10g n = f5; 6; 11g a = f1g q = f2; 8g p = f3; 9g sp = f4; 10g n = f5; 6; 11g PDT. This algorithm takes the program statement si 2 p, the variable x 2 si and P DTp as the input parameters and returns the backward slice hsi; xi. We use two initially empty lists Slicing set and T emp to keep the final and temporary result of program slicing. Since the statement si is the starting point of the slicing, so we add its number (i.e. i) to the list T emp. Then, the algorithm repeats the following steps until T emp becomes empty: (a) it removes an element from the temporary list (such as j 2 T emp) and adds it to the list Slicing set; (b) Next, the algorithm checks the column j of P DTp: It adds the row number k to T emp if P DTp[k; j] is c or d and k is not in the lists T emp and Slicing set, which means that k has not been processed.
For more clear, Table III explains our algorithm for the backward slice hs13; qi. In row 2, the statement s13 has dependency with the statements s0, s2 and s8, so we add them to the temporary list since they are not in the lists T emp or Slicing set. While in row 4, s11 has dependency with the statements s5, s6, s7 and s11, but none of them are added to the list T emp because s5; s6; s7 2 T emp and s11 2 Slicing set.
In the following we prove that the proposed backward slicing algorithm is complete, correct and terminates after a finites number of iterations. To prove the completeness, consider L as the set of dependency types in the PDT, so L = fc; dg. Initially, the intended slice consists of only the slicing creation statement si. There can be two possibilities: si may be a header function or may be a statement of function body. If si is a function header, then the slice contains this statement and its close brace, otherwise it must be connected to the other statements through the members of L. This is true in the proposed algorithm because we proved that PDT covers all possible types of dependencies including data dependency and control dependency.
To prove the correctness of our algorithm, we start with the slicing criterion statement si in a source code p. Initially, the slice list Slicing set is empty. Clearly, the slicing criterion statement must be in the output slice, hence the backward slicing algorithm add it to the list Slicing set. Next, we have to check all effective statements by following data and control dependencies. These relations are declared by c or d in P DTp. Hence, our algorithm adds the connected statements to the slice list by finding the data and control dependencies.
Finally, a backward slice is created in a finite number of steps, since we do not add duplicate statements to the temporary list and the number of statements is finite.
Algorithm 3 presents our forward program slicing. The definitions of P T Dp, Slicing set and T emp are same as the definitions of them in the previous sub-section. To generate the forward slice of si, we add i to the temporary list, then we repeat the following steps while T emp is not empty: (a) we remove an element such as j from T emp and adds it to the list Slicing set; (b) Next, the row j of P DTp is checked. For each column k, if P DTp[j; k] is c or d and k is not in the lists T emp and Slicing set, then we add it to the temporary list. Table IV demonstrates the proposed algorithm for the forward slice of s8.
Algorithm 3 Forward program slicing 10: 11: 12: 1: T emp T emp [ i 2: while not(empty(T emp)) do 3: j remove(T emp) 4: Slicing set Slicing set [ j 5: cols columns number of P DTp 6: for all k 2 cols do 7: if (P DTp[j; k] = c or P DTp[j; k] = d) then 8: if (k 2= T emp and k 2= Slicing set) then 9: T emp T emp [ k
end if end if end for 13: end while 14: return Slicing set
Program slicing is one of the program analysis techniques that is used to save time and cost in software testing process. It restricts the focus of a task to specific sub-components of a program by extracting the statements. Different type of dependence graphs are used to represent the relations between the statements of a program. However, drawing these graphs for large and complex programs is very complicated and it is impossible in non-automatic approaches. Hence, in this paper we proposed Program Dependence Table (PDT) as an intermediate representation tool to handle the data and control dependency in the intra-procedural programs. PDT is generated automatically form a source code without drawing the program dependence graph. Then, we presented two automatic slicing algorithms including forward and backward slicing based on PDT which are useful for automatic unit testing. Moreover, we show that chop, backbone and union slicing can be generated by forward and backward slicing. The proposed backward program slicing produces an executable slice because it covers pair braces in a program. For future work, it is suggested to extend the algorithm for slicing in inter-procedural, objectoriented and aspect-oriented programming paradigms. [20] S. Yoo, D. W. Binkley, and R. D. Eastman, “Observational slicing based on visual semantics,” Journal of Systems and Software, vol. 129, pp. 60– 78, 2017. [21] S. Horwitz, T. W. Reps, and D. W. Binkley, “Interprocedural slicing using dependence graphs,” ACM Trans. Program. Lang. Syst., vol. 12, no. 1, pp. 26–60, 1990. [22] J. Singh and D. P. Mohapatra, “Dynamic slicing of concurrent aspectj programs: An explicit context-sensitive approach,” Softw., Pract. Exper., vol. 48, no. 1, pp. 233–260, 2018. [23] I. Mastroeni and D. Zanardini, “Abstract program slicing: An abstract interpretation-based approach to program slicing,” ACM Trans. Comput.
Log., vol. 18, no. 1, pp. 7:1–7:58, 2017. [24] A. Zeller, Why Programs Fail - A Guide to Systematic Debugging, 2nd
Edition. Academic Press, 2009. [25] A. Afshar, Application Software Re-Engineering. Pearson Education, 2010.