HOME | DEUTSCH | IMPRESSUM | KIT

Journal Article: Precise Slicing of Concurrent Programs - An Evaluation of Static Slicing Algorithms for Concurrent Programs

[giffhorn09jase]Dennis Giffhorn, Christian Hammer, Precise Slicing of Concurrent Programs - An Evaluation of Static Slicing Algorithms for Concurrent Programs, Journal of Automated Software Engineering, Vol. 16, (2), pp. 197--234, June 2009.

Abstract

While there exist efficient algorithms to slice sequential programs precisely, there are only two algorithms for precise slicing of concurrent interprocedural programs with recursive procedures (Krinke in Proc. ESEC/FSE'03, pp. 178-187, 2003; Nanda and Ramesh in ACM Toplas. 28(6):1088-1144, 2006). We present an empirical evaluation of both algorithms for Java. We demonstrate that both algorithms provide the same precision up to the model of concurrency in use and show that the concurrency model has strong impact on slice precision and computation costs. Furthermore, we extend both algorithms to support dynamic thread creation both in loops and recursion - a feature that the original algorithms could not fully handle. The worst case complexity of the algorithms being exponential, we developed several optimizations and compared these with each other and with algorithms that trade precision for speed. Finally, we show that one algorithm may produce incorrect slices and present a remedy.

Download

  [PDF]   [DOI]

Original article available at springerlink.com.

BibTeX

Authors at the institute

Former Staff Member
Prof. Dr.-Ing. Christian Hammer
Dr.-Ing. Dennis Giffhorn

Projects

Project
VALSOFT/Joana