Software Engineering Methodologies

srcSlice

Michael L. Collard, Ph.D.

Department of Computer Science, The University of Akron

Traditional Program Slicing

  • Traditional slicing first computes a PDG (or SDG), which takes a long time and requires a large amount of memory
  • After PDG is computed, slices for a particular variable can be computed very quickly

srcSlice

  • Efficient, scalable, lightweight forward static slicing
  • Not based on PDG, but computed directly from the source code

Performance

System LOC Variables Execution Time
Linux kernel 4.06 13 MLOC 1,918,000 7 min
Blender 2.68 1.3 MLOC 265,000 70 sec
Inkscape 0.91 410 KLOC 74,000 18 sec

Publications

Implementation

  • srcSlice built on srcML
  • Allows slicing for C, C++, Java, and C#
  • Only tested on C, C++

srcSlice Definitions

  • A static decomposition slice where the slice includes all relevant computations, and can be computed backwards and forwards
  • In srcSlice, a system dictionary is computed for every variable in the system
  • As we will see, this is a fairly straightforward process that takes minutes even on large projects
  • Once computed, a slice for a particular variable can be obtained quickly from the system dictionary

System Dictionary

  • Of the form (F,M,V)
  • F is the set of all files
  • M is the set of all methods
  • V is the set of all variables
  • E.g., (sum.cpp, main(), sum) ∈ (F,M,V) is the entry for the variable sum in the function main() in the file sum.cpp

System Dictionary Entry

  • file, function, and variable names
  • @index index of each variable in the order that it was declared in
  • slines lines of code that comprise the slice
  • cfunctions functions called using the slicing variable
  • dvariables variables that are data dependent on the slice variable
  • pointers aliases of the slicing variables
  • controledges all possible control-flow edges of the slicing variable

Source Code (sum.cpp, main())

1. int main() { 2. int sum = 0; 3. int i = 1; 4. while i <= 10 { 5. sum += i; 6. ++i; 7. } 8. println(sum); 9. println(i); 10. }

Partial Slice for sum ?

1. int main() { 2. int sum = 0; 3. int i = 1; 4. while i <= 10 { 5. sum += i; 6. ++i; 7. } 8. println(sum); 9. println(i); 10. }

Complete Slice

  • Take the union of the slines with the slice profiles of the dvariables, cfunctions, and pointers, minus any lines that are before the initial definition of the slice variable, i.e, the set {1, … ,def(v)-1}
  • Since dvariables(i) = {sum}, the complete slice for i is:
    • slines(i) ∪ slines(sum) - {1, 2} =
      • {3, 4, 5, 6, 9} ∪ {2, 5, 8} - {1, 2} =
      • {3, 4, 5, 6, 8, 9}
  • This final computation can be done for all variables via a single pass through the dictionary

Complete Slice sum

1. int main() { 2. int sum = 0; 3. int i = 1; 4. while i <= 10 { 5. sum += i; 6. ++i; 7. } 8. println(sum); 9. println(i); 10. }

Control Edges

Parameters

1 int f(int z) { 2 ++z; 3 return z; 4 } 5 void g(int&x , int* y) { 6 f(x); 7 ++y; 8 } 9 int main() { 10 int abc = 0; 11 int i = 1; 12 while (i <= 10){ 13 g(abc, &i); 14 } 15 std::cout << ":" << i << "abc:" << abc << '\n'; 16 std::cout << f(i); 17 abc += i; 18 }
  • Slice Profile(abc): def={10,17}, use={1,2,5,6,13,15}, slines={1,2,5,7,10,13,15,17}, dvars={abc}, pointers={}, cfuncs={fun{1}, foo{1}}
  • Slice Profile(i): def={11}, use={1,2,3,5,7,12,13,15,16,17}, slines={1,2,5,7,11,12,13,15,16,17}, dvars={abc}, pointers={}, cfuncs={fun{1}, foo{2}}
  • Slice Profile(z):def={1}, use={2}, slines={1,2}, dvars={}, pointers={}, cfuncs={}
  • Slice Profile(y): def={5}, use={7}, slines={5,7}, dvars={}, pointers={i}, cfuncs={}
  • Slice Profile(x): def={5}, use={1,2,6}, slines={1,2,5,6}, dvars={}, pointers={abc}, cfuncs={fun{1}}

Considerations

  • Data extraction
  • Function calls
  • Pointers
  • Applications