Precise slicing of interprocedural concurrent programs

Abstract

Program slicing is an effective technique for analyzing concurrent programs. However, when a conventional closure-based slicing algorithmfor sequential programs is applied to a concurrent interprocedural program, the slice is usually imprecise owing to the intransitivity of interference dependence. Interference dependence arises when a statement uses a variable defined in another statement executed concurrently. In this study, we propose a global dependence analysis approach based on a program reachability graph, and construct a novel dependence graph calledmarking-statement dependence graph (MSDG), in which each vertex is a 2-tuple of program state and statement. In contrast to the conventional program dependence graph where the vertex is a statement, the dependence relation in MSDG is transitive. When traversing MSDG, a precise slice will be obtained. To enhance the slicing efficiency without loss of precision, our slicing algorithm adopts a hybrid strategy. The procedures containing interaction statements between threads are inlined and sliced by the slicing algorithm based on program reachability graphs while allowing other procedures to be sliced as sequential programs. We have implemented our algorithm and three other representative slicing algorithms, and conducted an empirical study on concurrent Java programs. The experimental results show that our algorithm computes more precise slices than the other algorithms. Using partial-order reduction techniques, which are effective for reducing the size of a program reachability graph without loss of precision, our algorithm is optimized, thereby improving its performance to some extent.

Keywords

program slicing / concurrent programs / reachability analysis / context sensitivity / dependence analysis

References

[1] BurnsA, WellingsA.Real-Time Systems and Programming Languages: Ada, Real-Time Java and C/Real-Time POSIX. 4th Ed. Boston: Addison Wesley Longman, 2009

[2] XuB W, QianJ, ZhangX F, WuZ Q, ChenL. A brief survey of program slicing. ACM SIGSOFT Software Engineering Notes, 2005, 30(2): 1–36

[3] SilvaJ. A vocabulary of program slicing-based techniques. ACMComputing Surveys, 2012, 44(3): 12

[4] HorwitzS, RepsT, BinkleyD. Inter-procedural slicing using dependence graphs. ACM SIGPLAN Notices, 2004, 39(4): 229–243.

[5] KrinkeJ. Context-sensitive slicing of concurrent programs. ACM SIGSOFT Software Engineering Notes, 2003, 28(5): 178–187

[6] NandaM G, RameshS. Inter-procedural slicing of multithreaded programs with applications to Java. ACM Transaction on Programming Language Systems, 2006, 28(6): 1088–1144

[7] GiffhornD, HammerC. Precise slicing of concurrent programs. Journal of Automated Software Engineering, 2009, 16(2): 197–234

[8] GiffhornD. Advanced chopping of sequential and concurrent programs. Software Quality Journal, 2011, 19(2): 239–294

[9] GiffhornD. Slicing of concurrent programs and its application to Information flow control. Dissertation for the Doctoral Degree. Karlsruhe: University of Karlsruhe, 2012

[10] ChenZ Q, XuB W. Slicing concurrent Java programs. ACMSIGPLAN Notices, 2001, 36(4): 41–47

[11] QiX F, ZhouX Y, XuX J, ZhangY Z. Slicing concurrent programs based on program reachability graph. In: Proceedings of the 10th International Conference on Quality Software. 2010, 248–253

[12] QiX F, XuB W, ZhouX Y. An approach to analyzing dependence of concurrent programs based on program reachability graphs. Acta Electronica Sinica, 2007, 35(2): 287–291

[13] QiX F, XuX J, JiangZ L, WangP. Slicing concurrent programs based on program reachability graphs with partial-order reduction. Chinese Journal of Computer, 2014, 37(3): 568–579

[14] QiX F, XuX J, WangP. Slicing concurrent inter-procedural programs based on program reachability graphs. In: Proceedings of the 24th International Conference on Software Engineering and Knowledge Engineering. 2012, 293–298

[15] PezzeM, TaylorR N, YoungM. Graph models for reachability analysis of concurrent programs. ACMTransaction on Software Engineering and Methodology, 1995, 4(2): 171–213

[16] NielsonF, NielsonH R, HankinC. Principles of Program Analysis. Berlin: Springer, 2015

[17] GodefroidP, PeledD, StaskauskasM. Using partial-order methods in the formal validation of industrial concurrent programs. IEEE Transaction on Software Engineering, 1996, 22(7): 496–507

[18] JaghooriM M, SirjaniM, MousaviM R, KhamespanahE, MovagharA. Symmetry and partial order reduction techniques in model checking Rebeca. Acta Information, 2010, 47(1): 33–66

[19] ZhaoJ J. Multithreaded dependence graphs for concurrent Java programs. In: Proceedings of International Symposium on Software Engineering for Parallel and Distributed Systems. 1999, 13–23

[20] ChengJ. Task dependence nets for concurrent systems with Ada 95 and its applications. In: Proceedings of ACM TRI-Ada International Conference. 1997, 67–78

[21] HatcliffJ. A formal study of slicing for multi-threaded programs with JVM concurrency primitives. In: Proceedings of International Symposium on Static Analysis. 1999, 1–18

[22] ZhangJ, JinC Z. Control-flow-based static slicing algorithm of threaded programs. Journal of Jilin University, 2003, 41(4): 481–486

[23] ZhangY Z. Research on program slicing techniques based on modular monadic semantics. Dissertation for the Doctoral Degree. Nanjing: Southeast University, 2006

[24] RamalingamG. Context-sensitive synchronization-sensitive analysis is undecidable. ACM Transactions on Programming Language Systems, 2000, 22(2): 416–430

[25] LeuschelM, LlorensbM, OliverJ, SilvaJ, TamaritS. Static slicing of explicitly synchronized languages. Information and Computation, 2012, 214: 10–46

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg