Efficient Program Slicing Algorithms for Measuring Functional Cohesion and Parallelism

Authors: Jehad Al Dallal

Abstract:

Program slicing is the task of finding all statements in a program that directly or indirectly influence the value of a variable occurrence. The set of statements that can affect the value of a variable at some point in a program is called a program slice. In several software engineering applications, such as program debugging and measuring program cohesion and parallelism, several slices are computed at different program points. In this paper, algorithms are introduced to compute all backward and forward static slices of a computer program by traversing the program representation graph once. The program representation graph used in this paper is called Program Dependence Graph (PDG). We have conducted an experimental comparison study using 25 software modules to show the effectiveness of the introduced algorithm for computing all backward static slices over single-point slicing approaches in computing the parallelism and functional cohesion of program modules. The effectiveness of the algorithm is measured in terms of time execution and number of traversed PDG edges. The comparison study results indicate that using the introduced algorithm considerably saves the slicing time and effort required to measure module parallelism and functional cohesion.

Keywords: Backward slicing, cohesion measure, forward slicing, parallelism measure, program dependence graph, program slicing, static slicing.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1075848

References:

[1] M. Weiser, Program slicing, IEEE Transactions on Software Engineering, vol. 10, no. 4, pp. 352-357, 1984.
[2] B. Korel and J. Laski, Dynamic slicing of computer programs, The Journal of Systems and Software , vol. 13, no. 3, pp. 187-195, 1990.
[3] S. Horwitz, T. Reps, and D. Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems, vol. 12, no. 1, pp. 26-60, 1990.
[4] P. Hausler, Denotational program slicing, In Proceedings of the 22nd Hawaii International Conference on System Sciences, Hawaii, pp. 486- 494, 1989.
[5] J. Bergstar and B. Carre, Information-flow and data flow analysis of while-programs, ACM Transactions on Programming Languages and Systems, vol. 7, no. 1, pp. 37-61, 1985.
[6] K. Ottenstein and L. Ottenstein, The program dependence graph in software development environment, In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, SIGPLAN Notices, vol 19, no. 6, pp. 177-184, 1984.
[7] F. Tip, A survey of program slicing techniques, Technical Report: CSR9438, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1994.
[8] M. Weiser, Programmers use slices when debugging, Communications of the ACM, vol. 25, pp. 446-452, 1982.
[9] R. Gupta, M. Harrold, and M. Soffa, An approach to regression testing using slicing, Proceedings of the International Conference on Software Maintenance, pp. 299-308, 1992.
[10] K. Gallagher and J. Lyle, Using program slicing in software maintenance, IEEE Transactions on Software Engineering, vol. 17, no. 8, pp. 751 - 761, 1991.
[11] S. Horwitz, J. Prins, and T. Reps, Integrating non-interfering versions of programs, ACM Transactions on Programming Languages and Systems, vol. 11, no. 3, pp. 345-387, 1989.
[12] L. Ott and J. Thuss, Slice based metrics for estimating cohesion, Proceedings of the IEEE-CS International Metrics Symposium, pp. 78- 81, 1993.
[13] H. Longworth, Slice based program metrics, Master-s thesis, Michigan Technological University, 1985.
[14] J. Bieman and L. Ott, Measuring functional cohesion, IEEE Transactions on Software Engineering, vol. 20, no. 8, pp. 644-657, 1994.
[15] Aristotle Research Group, http://www-static.cc.gatech.edu/aristotle/ Tools/, July 2006.