Abstract
Previous work has shown that program slicing can be a useful step in model-checking software systems. We are interested in applying these techniques to construct models of multi-threaded Java programs. Past work does not address the concurrency primitives found in Java, nor does it provide the rigorous notions of slice correctness that are necessary for reasoning about programs with non-deterministic behaviour and potentially infinite computation traces.
In this paper, we define the semantics of a simple multi-threaded language with concurrency primitives matching those found in the Java Virtual Machine, we propose a bisimulation-based notion of correctness for slicing in this setting, we identify notions of dependency that are relevant for slicing multi-threaded Java programs, and we use these dependencies to specify a program slicer for the language presented in the paper. Finally, we discuss how these dependencies can be refined to take into account common programming idioms of concurrent Java software.
This work supported in part by NSF under grants CCR-9633388, CCR-9703094, CCR-9708184, and CCR-9701418 and DARPA/NASA under grant NAG 21209.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Jingde Cheng. Slicing concurrent programs–a graph-theoretical approach. In Proceedings of the First International Workshop on Automated and Algoritmic Debugging, number 749 in LNCS, pages 223–240, 1993.
E.M. Clarke, M. Fujita, S.P. Rajan, T. Reps, S. Shankar, and T. Teitelbaum. Program slicing for design automation: An automatic technique for speeding-up hardware design, simulation, testing, and verification. Technical report, 1999.
Matthew Dwyer and John Hatcliff. Slicing software for model construction. In Olivier Danvy, editor, Proceedings of the 1999 ACM Workshop on Partial Evaluation and Program Manipulation (PEPM’99), January 1999. BRICS Notes Series NS-99-1.
Matthew B. Dwyer, James C. Corbett, John Hatcliff, Stefan Sokolowski, and Hongjun Zheng. Slicing multi-threaded java programs: A case study. Technical Report 99-7, Kansas State University, Department of Computing and Information Sciences, March 1999.
G.J. Holzmann. The model checker spin. IEEE Transactions on Software Engineering, 23(5):279–294, May 1997.
Lynette I. Millett and Tim Teitelbaum. Slicing promela and its applications to model checking, simulation, and protocol understanding. In Proceedings of the 4th International SPIN Workshop, 1998.
Jens Krinke. Static slicing of threaded programs. In Proc. ACM SIG-PLAN/SIGFSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE’98), pages 35–42, 1998.
Tim Lindholm and Frank Yellin. The Java Virtual Machine Specification. Addison-Wesley, 1997.
K.L. McMillan. Symbolic Model Checking. Kluwer Academic Publishers, 1993.
Robin Milner. Communication and Concurrecy. Prentice Hall, 1989.
S.S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.
F. Tip. A survey of program slicing techniques. Journal of programming languages, 3:121–189, 1995.
Mark Weiser. Program slicing. IEEE Transaction on Software Engineering, 1984.
Jianjun Zhao. Slicing concurrent java programs. In Proceedings of the Seventh IEEE International Workshop on Program Comprehension, pages 126–133, may 1999.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hatcliff, J., Corbett, J., Dwyer, M., Sokolowski, S., Zheng, H. (1999). A Formal Study of Slicing for Multi-threaded Programs with JVM Concurrency Primitives. In: Cortesi, A., Filé, G. (eds) Static Analysis. SAS 1999. Lecture Notes in Computer Science, vol 1694. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48294-6_1
Download citation
DOI: https://doi.org/10.1007/3-540-48294-6_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66459-8
Online ISBN: 978-3-540-48294-9
eBook Packages: Springer Book Archive