Automatic detection of immutable fields in Java

ABSTRACT

This paper introduces techniques to detect mutability of fields and classes in Java. A variable is considered to be mutable if a new value is stored into it, as well as if any of its reachable variables is mutable. We present a static flow-sensitive analysis algorithm which can be applied to any Java component. The analysis classifies fields and classes as either mutable or immutable. In order to facilitate openworld analysis, the algorithm identifies situations that expose variables to potential modification by code outside the component, as well as situations where variables are modified by the analyzed code. We also present an implementation of the analysis which focuses on detecting mutability of class variables, so as to avoid isolation problems. The implementation incorporates intra- and inter-procedural data-flow analyses and is shown to be highly scalable. Experimental results demonstrate the effectiveness of the algorithms.

References

1. {1} P. S. Almeida. Balloon types: Controlling sharing of state in data types. In M. Aksit and S. Matsuoka, editors, Lecture Notes in Computer Science, volume 1241, pages 32-59, Jyvaskyla, Finland, June 1997. ECOOP'97, 11th European Conference on Object-Oriented Programming.]]
2. {2} Y. Aridor, M. Factor, and A. Teperman. cJVM: A single-system image of a JVM on a cluster. In Proceedings of the IEEE 28th International Conference on Parallel Processing, pages 4-12, Aizu-Wakamatsu, Fukushima, Japan, September 1999.]]
3. {3} A. Bhowmik and W. Pugh. A secure implementation of Java inner classes. http://www.cs.umd.edu/~pugh/java/#sic.]]
4. {4} B. Blanchet. Escape analysis for Object Oriented languages. Application to Java. In Proceedings of the 1999 Conference On Object-Oriented Programming, Systems, Languages, and Applications, Denver, Colorado, November 1999.]]
5. {5} J. Bogda and U. Holzle. Removing unnecessary synchronization in Java. In Proceedings of the 1999 Conference On Object-Oriented Programming, Systems, Languages, and Applications, Denver, Colorado, November 1999.]]
6. {6} B. Bokowski and J. Vitek. Confined types. In Proceedings of the 1999 Conference On Object-Oriented Programming, Systems, Languages, and Applications, Denver, Colorado, November 1999.]]
7. {7} CFParse. http://www.alphaworks.ibm.- com/tech/cfparse.]]
8. {8} J.D. Choi, M. Gupta, M. Serrano, V.C. Sreedhar, and S. Midkiff. Escape analysis for Java. In Proceedings of the 1999 Conference On Object-Oriented Programming, Systems, Languages, and Applications , Denver, Colorado, November 1999.]]
9. {9} D. G. Clarke, J. M. Potter, and J. Noble. Ownership types for flexible alias protection. In ACM SIGPLAN Notices - Proceedings of the 1998 Conference On Object-Oriented Programming, Systems, Languages, and Applications, volume 33(10), pages 48-64, October 1998.]]
10. {10} D. Detlefs, K. Rustan, M. Leino, G. Nelson, and J.B. Saxe. Extended static checking. Technical Report 159, Compaq Systems Research Center, Palo Alto, CA, December 1998.]]
11. {11} D. Doligez and G. Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. In ACM SIGPLAN Notices - Conference Record of the Twenty-first Annual ACM Symposium on Principles of Programming Languages, pages 113-123, 1994.]]
12. {12} D. Doligez and X. Leroy. A concurrent generational garbage collector for a multithreaded implementation of ML. In ACM SIGPLAN Notices - Conference Record of the Twentieth Annual ACM Symposium on Principles of Programming Languages, pages 113-123, January 1993.]]
13. {13} M. Emami, R. Ghiya, and L. Hendren. Context-sensitive interprocedural point-to analysis in the presence of function pointers. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Programming Languages, pages 121-133, San Diego, California, January 1998.]]
14. {14} D. Genius, M. Trapp, and W. Zimmermann. An approach to improve locality using sandwich types. In Proceedings of the Second Types in Compilation Workshop , volume LNCS 1473, Kyoto, Japan, March 1998.]]
15. {15} R. Ghiya and L. Hendren. Putting pointer analysis to work. In Proceedings of the 1994 SIGPLAN Conference On Programming Language Design and Implementation , Orlando, Florida, June 1994.]]
16. {16} M. Hind, M. Burke, P. Carini, and J.D. Choi. Interprocedural pointer alias analysis. ACM Transactions on Programming Languages and Systems, 21(4), 1999.]]
17. {17} J. Hogg, D. Lea, A. Wills, D. de Champeaux, and R. Holt. W3: The Geneva convention on the treatment of object aliasing. OOPS Messenger, 3(2):11-16, 1992.]]
18. {18} F. Honsell, I. A. Mason, S. F. Smith, and C. L. Talcott. A variable typed logic of effects. Information and Computation, 119(1):55-90, May 1995.]]
19. {19} D. Jackson and M. Rinard. The Future of Software Engineering, chapter The Future of Software Analysis. ACM Press, June 2000.]]
20. {20} T. Jensen, D. Le Métayer, and T. Thorn. Verification of control flow based security policies. In Proceedings of the 20th IEEE Security and Privacy Symposium, Oakland, California, 1999.]]
21. {21} G. Kniesel. Encapsulation = visibility + accessibility. Technical Report TR-96-12, CS Dept., University of Bonn, Germany, 1996.]]
22. {22} G. Kniesel and D. Theisen. JAC - Java with transitive readonly access control. In Proceedings of the Intercontinental Workshop on Aliasing in Object-Oriented Systems , Lisbon, Portugal, June 1999.]]
23. {23} J. Lakos. Large-Scale C++ Software design . Addison-Wesley, 1996.]]
24. {24} T. Lindholm and F. Yellin. The Java Virtual Machine Specification. Addison-Wesley, second edition, 1999.]]
25. {25} I. A. Mason and C. L. Talcott. Inferring the equivalence of functional programs that mutate data. Theoretical Computer Science, 105(2):167-215, 1992.]]
26. {26} R. Milner, M. Tofte, R. Harper, and D. MacQueen. The Definition of Standard ML (Revised). The MIT Press, 1997.]]
27. {27} J. Noble, J. Potter, and J. Vitek. Flexible alias protection. In Proceedings of 1998 European Conference on Object-Oriented Languages, Brussels, Belgium, July 1998.]]
28. {28} S.M. Omohundro. The Sather programming language. Dr. Dobb's Journal, 18(11), October 1993.]]
29. {29} S. Porat, B. Mendelson, and I. Shapira. Sharpening global static analysis to cope with Java. In Proceedings of CASCON'98, Toronto, Canada, November 1998.]]
30. {30} K. Rustan and M. Leino. Data groups: Specifying the modification of extended state. In Proceedings of the 1998 Conference on Object-Oriented Programming, Systems, Languages, and Applications, Vancouver, Canada, October 1998.]]
31. {31} Secure Internet Programming Group at Princeton University. http://www.cs.- princeton.edu/sip/news/april29.html.]]
32. {32} V. Seshadri. IBM High Performance Compiler for Java. AIXpert Magazine, September 1997.]]
33. {33} Toad. http://www.alphaworks.ibm.com/- tech/toad.]]
34. {34} J. Whaley and M. Rinard. Compositional pointer and escape analysis for Java programs. In Proceedings of the 1999 Conference On Object-Oriented Programming, Systems, Languages, and Applications , Denver, Colorado, November 1999.]]
35. {35} A. Zaks, V. Feldman, and N. Aizikowitz. Sealed calls in Java packages. To appear at the 2000 Conference On Object-Oriented Programming, Systems, Languages, and Applications.]]

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

    • General programming languages

      • Language types

        • Object oriented languages

• Theory of computation

  • Semantics and reasoning

    • Program reasoning

      • Program analysis

    • Program semantics