Role analysis

ABSTRACT

We present a new role system in which the type (or role) of each object depends on its referencing relationships with other objects, with the role changing as these relationships change. Roles capture important object and data structure properties and provide useful information about how the actions of the program interact with these properties. Our role system enables the programmer to specify the legal aliasing relationships that define the set of roles that objects may play, the roles of procedure parameters and object fields, and the role changes that procedures perform while manipulating objects. We present an interprocedural, compositional, and context-sensitive role analysis algorithm that verifies that a program maintains role constraints.

REFERENCES

• 1: Antonio Albano , Giorgio Ghelli , Renzo Orsini, Fibonacci: a programming language for object databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.3, July 1995
• 2: Paulo Sergio Almeida. Balloon types: Controlling sharing of state in data types. In Proceedings of the 11th European Conference on Object-Oriented Programming, 1997.
• 3: Thomas Ball , Rupak Majumdar , Todd Millstein , Sriram K. Rajamani, Automatic predicate abstraction of C programs, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.203-213, June 2001, Snowbird, Utah, United States
• 4: Chandrasekhar Boyapati , Martin Rinard, A parameterized type system for race-free Java programs, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.56-69, October 14-18, 2001, Tampa Bay, FL, USA
• 5: John Boyland, Alias burying: unique variables without destructive reads, Software—Practice & Experience, v.31 n.6, p.533-553, May 2001 [doi>10.1002/spe.370]
• 6: Craig Chambers, Predicate Classes, Proceedings of the 7th European Conference on Object-Oriented Programming, p.268-296, July 26-30, 1993
• 7: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.296-310, June 1990, White Plains, New York, United States
• 8: David G. Clarke , John M. Potter , James Noble, Ownership types for flexible alias protection, Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.48-64, October 18-22, 1998, Vancouver, British Columbia, Canada
• 9: Karl Crary , David Walker , Greg Morrisett, Typed memory management in a calculus of capabilities, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.262-275, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292564]
• 10: Robert DeLine , Manuel Fähndrich, Enforcing high-level protocols in low-level software, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.59-69, June 2001, Snowbird, Utah, United States
• 11: Sophia Drossopoulou , Ferruccio Damiani , Mariangiola Dezani-Ciancaglini , Paola Giannini, Fickle: Dynamic Object Re-classification, Proceedings of the 15th European Conference on Object-Oriented Programming, p.130-149, June 18-22, 2001
• 12: Jeffrey S. Foster , Alex Aiken, Checking Programmer-Specified Non-Aliasing, University of California at Berkeley, Berkeley, CA, 2001
• 13: Pascal Fradet , Daniel Le Métayer, Shape types, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.27-39, January 15-17, 1997, Paris, France [doi>10.1145/263699.263706]
• 14: Giorgio Ghelli and Debora Palmerini. Ibundations for extensible objects with roles. In Workshop on Dbundations of Object-Oriented Languages, Paris, 1999.
• 15: Rakesh Ghiya , Laurie J. Hendren, Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237724]
• 16: Rakesh Ghiya , Laurie J. Hendren, Connection Analysis: A Practical Interprocedural Heap Analysis for C, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.515-533, August 10-12, 1995
• 17: 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]
• 18: Goorg Gottlob, Michaol Schrofl, and Brigitto Roock. Extonding objoct-oriontod systoms with rolos. AUM ;mnsactions on Information Systems, 14(3), 1994.
• 19: Samuel Z. Guyer , Calvin Lin, An annotation language for optimizing software libraries, Proceedings of the 2nd conference on Domain-specific languages, p.39-52, October 03-06, 1999, Austin, Texas, United States
• 20: David Harel , Jerzy Tiuryn , Dexter Kozen, Dynamic Logic, MIT Press, Cambridge, MA, 2000
• 21: Joseph Hummel , Laurie J. Hendren , Alexandru Nicolau, A general data dependence test for dynamic, pointer-based data structures, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.218-229, June 20-24, 1994, Orlando, Florida, United States
• 22: John Hogg, Islands: aliasing protection in object-oriented languages, Conference proceedings on Object-oriented programming systems, languages, and applications, p.271-285, October 06-11, 1991, Phoenix, Arizona, United States
• 23: Joseph Edward Hummel , Alex Nicolau, Data dependence testing in the presence of pointers and pointer-based data structures, 1998
• 24: Joseph Hummel , Laurie J. Hendren , Alexandru Nicolau, Abstract description of pointer data structures: an approach for improving the analysis and optimization of imperative programs, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.243-260, Sept. 1992 [doi>10.1145/151640.151644]
• 25: Joseph Hummel , Alexandru Nicolau , Laurie J. Hendren, A Language for Conveying the Aliasing Properties of Dynamic, Pointer-Based Data Structures, Proceedings of the 8th International Symposium on Parallel Processing, p.208-216, April 01, 1994
• 26: Jakob L. Jensen , Michael E. Jørgensen , Michael I. Schwartzbach , Nils Klarlund, Automatic verification of pointer programs using monadic second-order logic, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.226-234, June 16-18, 1997, Las Vegas, Nevada, United States
• 27: Pierre Jouvelot , David Gifford, Algebraic reconstruction of types and effects, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.303-310, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99623]
• 28: Nils Klarlund , Michael I. Schwartzbach, Graph types, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.196-205, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158628]
• 29: Nils Klarlund , Michael I. Schwartzbach, Graphs and Decidable Transductions Based on Edge Constraints (Extended Abstract), Proceedings of the 19th International Colloquium on Trees in Algebra and Programming, p.187-201, April 11-13, 1994
• 30: Naoki Kobayashi, Quasi-linear types, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.29-42, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292546]
• 31: Viktor Kuncak. Dosigning an algorithm for rolo analysis. Mastor's thosis, Massachusotts Instituto of Tochnology, 2001.
• 32: Viktor Kuncak, Patrick Lam, and Martin Rinard. Rolos aro roally groat Tochnical Roport 822, Laboratory for Computor Scionco, Massachusotts Instituto of Tochnology, http ://www ,mit, edu/vkuncak/papers/, 2001.
• 33: Tal Lov-Ami. TVLA: A framowork for kleone basod logic static analysos. Mastor's thosis, Tol-Aviv Univorsity, Israol, 2000.
• 34: Anders Møller , Michael I. Schwartzbach, The pointer assertion logic engine, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.221-231, June 2001, Snowbird, Utah, United States
• 35: 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
• 36: Trygvo Roonskaug. Working With Objects. Prontico Hall, 1996.
• 37: Noam Rinetzky , Shmuel Sagiv, Interprocedural Shape Analysis for Recursive Programs, Proceedings of the 10th International Conference on Compiler Construction, p.133-149, April 02-06, 2001
• 38: Radu Rugina , Martin Rinard, Pointer analysis for multithreaded programs, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.77-90, May 01-04, 1999, Atlanta, Georgia, United States
• 39: Radu Rugina , Martin C. Rinard, Design-Driven Compilation, Proceedings of the 10th International Conference on Compiler Construction, p.150-164, April 02-06, 2001
• 40: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Solving shape-analysis problems in languages with destructive updating, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.16-31, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237725]
• 41: Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Parametric shape analysis via 3-valued logic, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.105-118, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292552]
• 42: Micha Sharir and Amir Pnuoli. Two approachos to intorprocodural data flow analysis probloms. In Program Flow Analysis: Theory and Applications. Prontico-Hall, Inc., 1981.
• 43: F. Smith, D. Walkor, and G. Morrisott. Alias typos. In Pwceedings of the lth European Symposium on Programming, Borlin, Gormany, March 2000.
• 44: R. E. Strom , D. M. Yellin, Extending Typestate Checking Using Conditional Liveness Analysis, IEEE Transactions on Software Engineering, v.19 n.5, p.478-485, May 1993 [doi>10.1109/32.232013]
• 45: R E Strom , S Yemini, Typestate: A programming language concept for enhancing software reliability, IEEE Transactions on Software Engineering, v.12 n.1, p.157-171, Jan. 1986
• 46: Wolfgang Thomas, Languages, automata, and logic, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
• 47: Michael VanHilst , David Notkin, Using role components in implement collaboration-based designs, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.359-369, October 06-10, 1996, San Jose, California, United States
• 48: Philip Wadlor. Linoar typos can chango tho world In 1FIP 2'(2 2 Working Conference on Programming Concepts and Methods, Sea of Galilee, l'rael, 1990.
• 49: David Walker , J. Gregory Morrisett, Alias Types for Recursive Data Structures, Selected papers from the Third International Workshop on Types in Compilation, p.177-206, September 21, 2000
• 50: Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States
• 51: Zhichen Xu , Barton P. Miller , Thomas Reps, Safety checking of machine code, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.70-82, June 18-21, 2000, Vancouver, British Columbia, Canada
• 52: Zhichon Xu, Thomas Rops, and Barton Millor. Typostato chocking of machino codo. In Proceedings of the 15th Euwpean b'ymposium on Programming, 2001.
• 53: Philip M. Yelland, Experimental classification facilities for Smalltalk, conference proceedings on Object-oriented programming systems, languages, and applications, p.235-246, October 18-22, 1992, Vancouver, British Columbia, Canada