More Web Proxy on the site http://driver.im/

article

Advanced chopping of sequential and concurrent programs

Author:

Dennis GiffhornAuthors Info & Claims

Software Quality Journal, Volume 19, Issue 2

Pages 239 - 294

https://doi.org/10.1007/s11219-010-9114-7

Published: 01 June 2011 Publication History

Abstract

A chop for a source statement s and a target statement t reveals the program parts involved in conveying effects from s to t. While precise chopping algorithms for sequential programs are known, no chopping algorithm for concurrent programs has been reported at all. This work introduces six chopping algorithms for concurrent programs, which offer different degrees of precision, ranging from imprecise over context-sensitive to time-sensitive. Our evaluation on concurrent Java programs shows that context-sensitive and time-sensitive chopping reduces chop sizes significantly. We further present an extensive evaluation of chopping algorithms for sequential programs and describe a new, easy-to-implement chopping technique for sequential programs that computes fast and almost context-sensitive chops.

References

[1]

Anderson, P., Reps, T., & Teitelbaum, T. (2003). Design and implementation of a fine-grained software inspection tool. IEEE Transactions on Software Engineering 29(8), 721-733.

Digital Library

[2]

Barik, R. (2005). Efficient computation of May-Happen-in-Parallel information for concurrent Java programs. In Proceeding of 18th international workshop on languages and compilers for parallel computing (LCPC'05), pp. 152-169.

[3]

Binkley, D., Harman M., & Krinke, J. (2007). Empirical study of optimization techniques for massive slicing. ACM Transactions on Program Language Systems 30(1), 3.

Digital Library

[4]

Brumley, D., Newsome, J., Song, D., Wang, H., & Jha, S. (2006). Towards automatic generation of vulnerability-based signatures. In Proc. SP'06, pp. 2-16.

[5]

Chen, Z., & Xu, B. (2001). Slicing concurrent Java programs. ACM SIGPLAN Notices, 36(4), 41-47.

Digital Library

[6]

Chen, Z., Xu, B., Yang, H., Liu, K., & Zhang, J. (2000). An approach to analyzing dependency of concurrent programs. In APAQS '00: Proceedings of the first Asia-pacific conference on quality software, pp. 39-43.

[7]

Cheng, J. (1993). Slicing concurrent programs. Automated and Algorithmic Debugging, LNCS, 749, 223-240, Springer.

[8]

Cheng, J. (1997). Dependence analysis of parallel and distributed programs and its applications. International conference on advances in parallel and distributed computing, pp. 395-404.

[9]

Giffhorn, D. (2009). Chopping concurrent programs. In 9th IEEE International workshop conference on source code analysis and manipulation, pp. 13-22.

[10]

Giffhorn, D., & Hammer, C. (2009). Precise slicing of concurrent programs - An evaluation of static slicing algorithms for concurrent programs. Springer JASE, 16(2), 197-234.

[11]

Graf, J. (2009). Improving and evaluating the scalability of precise system dependence graphs for object-oriented languages. Tech. Rep., Universität Karlsruhe (TH), Germany.

[12]

Hammer, C. (2009). Information flow control for Java-a comprehensive approach based on path conditions in dependence graphs. PhD thesis, Universität Karlsruhe (TH).

[13]

Hammer, C., & Snelting, G. (2004). An improved slicer for Java. Workshop on program analysis for software tools and engineering (PASTE'04), pp. 17-22.

[14]

Hammer, C., & Snelting, G. (2009). Flow-sensitive, context-sensitive, and object-sensitive information flow control based on program dependence graphs. Springer IJIS, 8(6), 399-422.

[15]

Hatcliff, J., Corbett, J. C., Dwyer, M. B., Sokolowski, S., & Zheng, H. (1999). A formal study of slicing for multi-threaded programs with JVM concurrency primitives. Static Analysis Symposium, LNCS, 1694, pp. 1-18, Springer.

[16]

Horwitz, S. B., Reps, T. W., & Binkley, D. (1990). Interprocedural slicing using dependence graphs. ACM Transactions on Program Language Systems 12(1), 26-60.

Digital Library

[17]

Jackson, D., & Rollins, E. J. (1994). A new model of program dependences for reverse engineering. In Proc. FSE, pp. 2-10.

[18]

Krinke, J. (1998). Static slicing of threaded programs. PASTE '98, pp. 35-42.

[19]

Krinke, J. (2002). Evaluating context-sensitive slicing and chopping. International conference on software maintenance, pp. 22-31.

[20]

Krinke, J. (2003a). Barrier slicing and chopping. In IEEE Workshop on Source Code Analysis and Manipulation (SCAM).

[21]

Krinke, J. (2003b). Context-sensitive slicing of concurrent programs. Proc. ESEC/FSE'03, pp. 178-187.

[22]

Krinke, J. (2003c). Advanced slicing of sequential and concurrent programs. PhD thesis, Universität Passau.

[23]

Liu, H., & Kuan Tan, H. B. (2008). An approach for the maintenance of input validation. Information Software Technology, 50(5), 449-461.

Digital Library

[24]

Müller-Olm, M., & Seidl, H. (2001). On optimal slicing of parallel programs. STOC 2001 (33th ACM symposium on theory of computing), pp. 647-656.

[25]

Nanda, M. G., & Ramesh, S. (2000). Slicing concurrent programs. ISSTA 2000, pp. 180-190.

[26]

Nanda, M. G., & Ramesh, S. (2006). Interprocedural slicing of multithreaded programs with applications to Java. ACM TOPLAS., 28(6), 1088-1144.

Digital Library

[27]

Naumovich, G., Avrunin, G. S., & Clarke, L. A. (1999). An efficient algorithm for computing MHP information for concurrent Java programs. In Proc. ESEC/FSE '99, pp. 338-354. Springer.

[28]

Qi, X., & Xu, B. (2005). An approach to slicing concurrent Ada programs based on program reachability graphs. IJCSNS, 6(1), 29-37.

[29]

Ramalingam, G. (2000). Context-sensitive synchronization-sensitive analysis is undecidable. ACM Transactions on Program Language Systems, 22(2), 416-430.

Digital Library

[30]

Reps, T., & Rosay, G. (1995). Precise interprocedural chopping. In Proceedings of FSE'95 (pp. 41-52). New York: ACM Press.

[31]

Ruf, E. (2000). Effective synchronization removal for Java. Programming Language Design and Implementation (PLDI), pp. 208-218.

[32]

Shacham, O., Sagiv, M., & Schuster, A. (2007). Scaling model checking of dataraces using dynamic information. Journal of Parallel and Distributed Computing 67(5), 536-550.

Digital Library

[33]

Snelting, G., Robschink, T., & Krinke, J. (2006). Efficient path conditions in dependence graphs for software safety analysis. ACM TOSEM, 15(4), 410-457.

Digital Library

[34]

Zhao, J. (1999). Slicing concurrent Java programs. Proceedings of the 7th IEEE International Workshop on Program Comprehension, pp. 126-133.

Cited By

Velez MJamshidi PSiegmund NApel SKästner CDwyer MDamian DZeller A(2022)On debugging the performance of configurable software systemsProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510043(1571-1583)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510043
Bischof SBreitner JGraf JHecker MMohr MSnelting G(2018)Low-deterministic security for low-nondeterministic programsJournal of Computer Security10.3233/JCS-1798426:3(335-366)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.3233/JCS-17984
Giffhorn DSnelting G(2018)A new algorithm for low-deterministic securityInternational Journal of Information Security10.1007/s10207-014-0257-614:3(263-287)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10207-014-0257-6
Show More Cited By

Recommendations

Chopping Concurrent Programs
SCAM '09: Proceedings of the 2009 Ninth IEEE International Working Conference on Source Code Analysis and Manipulation

A chop for a source statement s and a target statement t reveals the program parts involved in conveying effects from s to t. While precise chopping algorithms for sequential programs are known, no chopping algorithm for concurrent programs has been ...
Precise slicing of concurrent programs

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 ...
Context-sensitive slicing of concurrent programs
ESEC/FSE-11: Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering

Program slicing is a technique to identify statements that may influence the computations at other statements. Precise slicing has been shown to be undecidable for concurrent programs. This work presents the first context-sensitive approach to slice ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Software Quality Journal

Software Quality Journal Volume 19, Issue 2

June 2011

248 pages

ISSN:0963-9314

Issue’s Table of Contents

Copyright © Copyright © 2011 Springer Science+Business Media, LLC.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 June 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Velez MJamshidi PSiegmund NApel SKästner CDwyer MDamian DZeller A(2022)On debugging the performance of configurable software systemsProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510043(1571-1583)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510043
Bischof SBreitner JGraf JHecker MMohr MSnelting G(2018)Low-deterministic security for low-nondeterministic programsJournal of Computer Security10.3233/JCS-1798426:3(335-366)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.3233/JCS-17984
Giffhorn DSnelting G(2018)A new algorithm for low-deterministic securityInternational Journal of Information Security10.1007/s10207-014-0257-614:3(263-287)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10207-014-0257-6
Qi XJiang Z(2017)Precise slicing of interprocedural concurrent programsFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-017-6189-311:6(971-986)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s11704-017-6189-3

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents