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: Yariv Aridor , Michael Factor , Avi Teperman, cJVM: A Single System Image of a JVM on a Cluster, Proceedings of the 1999 International Conference on Parallel Processing, p.4, September 21-24, 1999
• 3: {3} A. Bhowmik and W. Pugh. A secure implementation of Java inner classes. http://www.cs.umd.edu/~pugh/java/#sic.
• 4: Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.20-34, November 01-05, 1999, Denver, Colorado, United States
• 5: Jeff Bogda , Urs Hölzle, Removing unnecessary synchronization in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.35-46, November 01-05, 1999, Denver, Colorado, United States
• 6: Jan Vitek , Boris Bokowski, Confined types, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.82-96, November 01-05, 1999, Denver, Colorado, United States
• 7: {7} CFParse. http://www.alphaworks.ibm.- com/tech/cfparse.
• 8: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 9: David G. Clarke , John M. Potter , James Noble, Ownership types for flexible alias protection, ACM SIGPLAN Notices, v.33 n.10, p.48-64, Oct. 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: Damien Doligez , Georges Gonthier, Portable, unobtrusive garbage collection for multiprocessor systems, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.70-83, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.174673]
• 12: Damien Doligez , Xavier Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.113-123, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158611]
• 13: Rakesh Ghiya , Laurie J. Hendren, Putting pointer analysis to work, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.121-133, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268957]
• 14: Daniela Genius , Martin Trapp , Wolf Zimmermann, An Approach to Improve Locality Using Sandwich Types, Proceedings of the Second International Workshop on Types in Compilation, p.194-214, March 25-27, 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: Michael Hind , Michael Burke , Paul Carini , Jong-Deok Choi, Interprocedural pointer alias analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.848-894, July 1999 [doi>10.1145/325478.325519]
• 17: John Hogg , Doug Lea , Alan Wills , Dennis deChampeaux , Richard Holt, The Geneva convention on the treatment of object aliasing, ACM SIGPLAN OOPS Messenger, v.3 n.2, p.11-16, April 1992 [doi>10.1145/130943.130947]
• 18: Furio Honsell , Ian A. Mason , Scott Smith , Carolyn Talcott, A variable typed logic of effects, Information and Computation, v.119 n.1, p.55-90, May 15, 1995 [doi>10.1006/inco.1995.1077]
• 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: John Lakos, Large-scale C++ software design, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
• 24: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 25: Ian Mason , Carolyn Talcott, Inferring the equivalence of functional programs that mutate data, Theoretical Computer Science, v.105 n.2, p.167-215, Nov. 1992 [doi>10.1016/0304-3975(92)90301-U]
• 26: Robin Milner , Mads Tofte , David Macqueen, The Definition of Standard ML, MIT Press, Cambridge, MA, 1997
• 27: James Noble , Jan Vitek , John Potter, Flexible Alias Protection, Proceedings of the 12th European Conference on Object-Oriented Programming, p.158-185, July 20-24, 1998
• 28: Stephen M. Omohundro, The Sather programming language, Dr. Dobb's Journal, v.18 n.11, p.42-48, Oct. 1993
• 29: Sara Porat , Bilha Mendelson , Irina Shapira, Sharpening global static analysis to cope with Java, Proceedings of the 1998 conference of the Centre for Advanced Studies on Collaborative research, p.19, November 30-December 03, 1998, Toronto, Ontario, Canada
• 30: K. Rustan M. Leino, Data groups: specifying the modification of extended state, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.144-153, October 18-22, 1998, Vancouver, British Columbia, Canada
• 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: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States
• 35: Ayal Zaks , Vitaly Feldman , Nava Aizikowitz, Sealed calls in Java packages, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.83-92, October 2000, Minneapolis, Minnesota, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Object-oriented languages
          Nouns: Java
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Design, Measurement, Theory