Article

Modular Control Flow Analysis for Libraries

Author:

Christian W. ProbstAuthors Info & Claims

SAS '02: Proceedings of the 9th International Symposium on Static Analysis

Pages 165 - 179

Published: 17 September 2002 Publication History

Abstract

One problem in analyzing object oriented languages is that the exact control flow graph is not known statically due to dynamic dispatching. However, this is needed in order to apply the large class of known interprocedural analysis. Control Flow Analysis in the object oriented setting aims at determining run-time types of variables, thus allowing to possibly targeted method implementations.We present a flow sensitive analysis that allows separate handling of libraries and thereby efficient analysis of whole programs.

References

[1]

O. Agesen. The Cartesian Product Algorithm: Simple and Precise Typing of Parametric Polymorphism. In Proceedings of the European Conference on Object-Oriented Programming , pages 2-26, 1995.

[2]

M. Alt, U. Aßmann and H. van Someren. Cosy Compiler Phase Embedding with the CoSy Compiler Model. In Proceedings of the Conference on Compiler Construction , 1994.

[3]

D. F. Bacon. Fast and Effective Optimization of Statically Typed Object-Oriented Languages. Technical Report CSD-98-1017 , University of California, Berkeley, Oct. 1998.

[4]

R. Chatterjee, B. G. Ryder, and W. Landi. Relevant context inference. In Symposium on Principles of Programming Languages , pages 133-146, 1999.

[5]

J. Dean, D. Grove and C. Chambers. Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis. Technical Report 01-12-94 , Washington University, Dec. 1994.

[6]

H. Dewes and C. W. Probst. Static Method Call in Java. In Proceedings of the JOSES Workshop , 2001.

[7]

M. Fähndrich, J. Foster, Z. Su, and A. Aiken. Partial online cycle elimination in inclusion constraint graphs. In Conference on Programming Language Design and Implementation , pages 85-96, 1998.

[8]

C. Flanagan and M. Felleisen. Componential set-based analysis. ACM Trans. Programming Languages and Systems , 21(2), pages 370-416, Mar. 1999.

[9]

D. Genius, U. Aßmann, P. Fritzson, H. Sips, R. Kurver, R. Wilhelm, H. Schepers and T. Rindborg. Java and CoSy Technology for Embedded Systems: the JOSES Project. In Proceedings of the Conference on Electronic Commerce, Multimedia, Embedded Systems and Technologies for Business Processes Stockholm, 1999.

[10]

R. T. Hood and K. Kennedy. A Programming Environment for Fortran. In Proceedings of the 18th Annual Hawaii International Conference on System Sciences , pages 625-637, 1985.

[11]

F. Martin. Generation of Program Analyzers. Ph.D. Thesis, Universität des Saarlandes, 1999.

[12]

F. Nielson, H. R. Nielson and C. L. Hankin. Principles of Program Analysis. Springer-Verlag, 1999.

[13]

C. W. Probst. Flow Sensitive Call Graph Construction For Java. In Proceedings of the JOSES Workshop , 2001.

[14]

C. W. Probst. Control Flow Analysis - An Overview. The JOSES Consortium, 1999.

[15]

T. Ritzau, M. Beemster, F. Liekweg, C. W. Probst. JOC - The JOSES Compiler Presented at The Embedded Systems Show , London, 2000.

[16]

A. Rountev and B. G. Ryder. Points-to and side-effect analyses for programs built with precompiled libraries. Technical Report 423, Rutgers University, Oct. 2000.

[17]

A. Rountev and B. G. Ryder. Practical points-to analysis for programs built with libraries. Technical Report 410, Rutgers University, Feb. 2000.

[18]

Z. Su, M. Fähndrich and A. Aiken. Projection Merging: Reducing Redundancies in Inclusion Constraint Graphs. In Symposium on Principles of Programming Languages , pages 81-95, 2000.

[19]

V. Sundaresan, L. J. Hendren, C. Razafimahefa, R. Vall'ee-Rai, P. Lam, E. Gagnon and C. Godin. Practical virtual method call resolution for Java. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages and Application , pages 264-280, 2000.

[20]

F. Tip and J. Palsberg. Scalable propagation-based call graph construction algorithms. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages and Application , pages 281-293, 2000.

Cited By

Sanchez JCorrales JBouzgarrou BMezouar Y(2018)Robotic manipulation and sensing of deformable objects in domestic and industrial applicationsInternational Journal of Robotics Research10.1177/027836491877969837:7(688-716)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1177/0278364918779698
Kübler FMüller PHermann BAli KCifuentes C(2017)SootKeeper: runtime reusability for modular static analysisProceedings of the 6th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis10.1145/3088515.3088518(19-24)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3088515.3088518
Brauer JKing AKowalewski S(2013)Abstract interpretation of microcontroller codeScience of Computer Programming10.1016/j.scico.2012.06.00178:7(862-883)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1016/j.scico.2012.06.001
Show More Cited By

Modular Control Flow Analysis for Libraries
1. Mathematics of computing
  1. Mathematical analysis
2. Theory of computation

Recommendations

Interprocedural Control Flow Analysis
ESOP '99: Proceedings of the 8th European Symposium on Programming Languages and Systems

Control Flow Analysis is a widely used approach for analysing functional and object oriented programs. Once the applications become more demanding also the analysis needs to be more precise in its ability to deal with mutable state (or side-effects) and ...
Control flow analysis
Proceedings of a symposium on Compiler optimization

Any static, global analysis of the expression and data relationships in a program requires a knowledge of the control flow of the program. Since one of the primary reasons for doing such a global analysis in a compiler is to produce optimized programs, ...
Object flow analysis: taking an object-centric view on dynamic analysis
ICDL '07: Proceedings of the 2007 international conference on Dynamic languages: in conjunction with the 15th International Smalltalk Joint Conference 2007

To extract abstract views of the behavior of an object-oriented system for reverse engineering, a body of research exists that analyzes a system's runtime execution. Those approaches primarily analyze the control flow by tracing method execution events. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

SAS '02: Proceedings of the 9th International Symposium on Static Analysis

September 2002

525 pages

ISBN:3540442359

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 September 2002

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sanchez JCorrales JBouzgarrou BMezouar Y(2018)Robotic manipulation and sensing of deformable objects in domestic and industrial applicationsInternational Journal of Robotics Research10.1177/027836491877969837:7(688-716)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1177/0278364918779698
Kübler FMüller PHermann BAli KCifuentes C(2017)SootKeeper: runtime reusability for modular static analysisProceedings of the 6th ACM SIGPLAN International Workshop on State Of the Art in Program Analysis10.1145/3088515.3088518(19-24)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3088515.3088518
Brauer JKing AKowalewski S(2013)Abstract interpretation of microcontroller codeScience of Computer Programming10.1016/j.scico.2012.06.00178:7(862-883)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1016/j.scico.2012.06.001
Yan DXu GRountev ABodden EHendren LLam PSherman E(2012)Rethinking Soot for summary-based whole-program analysisProceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program analysis10.1145/2259051.2259053(9-14)Online publication date: 14-Jun-2012
https://dl.acm.org/doi/10.1145/2259051.2259053
Hierons R(2012)The complexity of asynchronous model based testingTheoretical Computer Science10.1016/j.tcs.2012.05.038451(70-82)Online publication date: 1-Sep-2012
https://dl.acm.org/doi/10.1016/j.tcs.2012.05.038
Howe JKing A(2012)A pearl on SAT and SMT solving in PrologTheoretical Computer Science10.1016/j.tcs.2012.02.024435(43-55)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1016/j.tcs.2012.02.024
Das AAdhikari A(2012)An efficient IND-CCA2 secure Paillier-based cryptosystemInformation Processing Letters10.1016/j.ipl.2012.08.007112:22(885-888)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1016/j.ipl.2012.08.007
Parra CBlanc XCleve ADuchien L(2011)Unifying design and runtime software adaptation using aspect modelsScience of Computer Programming10.1016/j.scico.2010.12.00576:12(1247-1260)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1016/j.scico.2010.12.005
Agullo ECoti CHerault TLangou JPeyronnet SRezmerita ACappello FDongarra J(2011)QCG-OMPIFuture Generation Computer Systems10.1016/j.future.2010.11.01527:4(357-369)Online publication date: 1-Apr-2011
https://dl.acm.org/doi/10.1016/j.future.2010.11.015
Guns TNijssen SDe Raedt L(2011)Itemset miningArtificial Intelligence10.1016/j.artint.2011.05.002175:12-13(1951-1983)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.1016/j.artint.2011.05.002
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents