Static extraction of sound hierarchical runtime object graphs

ABSTRACT

For many object-oriented systems, it is often useful to have a runtime architecture that shows networks of communicating objects. But it is hard to statically extract runtime object graphs that provide architectural abstraction from existing programs written in general purpose languages, and that follow common design idioms.

Previous approaches extract low-level non-hierarchical object graphs that do not provide architectural abstraction, change the language too radically for many existing implementations, or use a dynamic analysis. Static analysis, which takes all possible executions into account, is essential to extract a sound architecture, one that reveals all objects and relations that could possibly exist at runtime.

Ownership domain type annotations specify in code architectural intent related to object encapsulation and communication. We propose a static analysis that leverages such types and extracts a hierarchical approximation of all possible runtime object graphs. The representation provides architectural abstraction, first by ownership hierarchy, and then by types. We proved core soundness results for the technique and evaluated it on 68 KLOC of real code.

REFERENCES

• 1: M. Abi-Antoun and J. Aldrich. Compile-Time Views of Execution Structure Based on Ownership. In IWACO, 2007. Informal workshop.
• 2: M. Abi-Antoun and J. Aldrich. A Field Study in Static Extraction of Runtime Architectures. In PASTE, 2008.
• 3: M. Abi-Antoun and J. Aldrich. Static Extraction of Sound Hierarchical Runtime Object Graphs. Technical Report CMU-ISR-08-127, Carnegie Mellon University, 2008.
• 4: J. Aldrich and C. Chambers. Ownership Domains: Separating Aliasing Policy from Mechanism. In ECOOP, 2004.
• 5: Jonathan Aldrich , Craig Chambers , David Notkin, ArchJava: connecting software architecture to implementation, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581365]
• 6: D. F. Bacon and P. F. Sweeney. Fast Static Analysis of C Virtual Function Calls. In OOPSLA, 1996.
• 7: 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
• 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: P. Clements et al. Documenting Software Architecture. Addison-Wesley, 2003.
• 10: C. Flanagan and S. N. Freund. Dynamic Architecture Extraction. In FLoC FATES-RV, 2006.
• 11: T. Hill, J. Noble, and J. Potter. Scalable Visualizations of Object-Oriented Systems with Ownership Trees. J. Visual Languages and Computing, 13(3), 2002.
• 12: Daniel Jackson , Allison Waingold, Lightweight Extraction of Object Models from Bytecode, IEEE Transactions on Software Engineering, v.27 n.2, p.156-169, February 2001 [doi>10.1109/32.908960]
• 13: Rick Kazman , S. Jeromy Carrière, Playing Detective: Reconstructing Software Architecture from Available Evidence, Automated Software Engineering, v.6 n.2, p.107-138, April 1999 [doi>10.1023/A:1008781513258]
• 14: P. Lam and M. Rinard. A Type System and Analysis for the Automatic Extraction and Enforcement of Design Information. In ECOOP, 2003.
• 15: Yin Liu , Ana Milanova, Ownership and Immutability Inference for UML-Based Object Access Control, Proceedings of the 29th international conference on Software Engineering, p.323-332, May 20-26, 2007 [doi>10.1109/ICSE.2007.61]
• 16: Kin-Keung Ma , Jeffrey S. Foster, Inferring aliasing and encapsulation properties for java, Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 17: N. Mitchell. The Runtime Structure of Object Ownership. In ECOOP, 2006.
• 18: Robert Weeks O'Callahan , Jeannette Wing , Daniel Jackson, Generalized aliasing as a basis for program analysis tools, Carnegie Mellon University, Pittsburgh, PA, 2001
• 19: Alex Potanin , James Noble , Robert Biddle, Checking ownership and confinement: Research Articles, Concurrency and Computation: Practice & Experience, v.16 n.7, p.671-687, June 2004 [doi>10.1002/cpe.v16:7]
• 20: J. Potter , J. Noble , D. Clarke, The Ins and Outs of Objects, Proceedings of the Australian Software Engineering Conference, p.80, November 09-13, 1998
• 21: D. Rayside, L. Mendel, and D. Jackson. A Dynamic Analysis for Revealing Object Ownership and Sharing. In WODA, 2006.
• 22: Derek Rayside , Lucy Mendel , Robert Seater , Daniel Jackson, An analysis and visualization for revealing object sharing, Proceedings of the 2005 OOPSLA workshop on Eclipse technology eXchange, p.11-15, October 16-17, 2005, San Diego, California [doi>10.1145/1117696.1117699]
• 23: 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]
• 24: Jan Schäfer , Markus Reitz , Jean-Marie Gaillourdet , Arnd Poetzsch-Heffter, Linking Programs to Architectures: An Object-Oriented Hierarchical Software Model Based on Boxes, The Common Component Modeling Example: Comparing Software Component Models, Springer-Verlag, Berlin, Heidelberg, 2007 [doi>10.1007/978-3-540-85289-6_10]
• 25: Bradley Schmerl , Jonathan Aldrich , David Garlan , Rick Kazman , Hong Yan, Discovering Architectures from Running Systems, IEEE Transactions on Software Engineering, v.32 n.7, p.454-466, July 2006 [doi>10.1109/TSE.2006.66]
• 26: A. Spiegel. Automatic Distribution of Object-Oriented Programs. PhD thesis, FU Berlin, 2002.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Classes and objects

General Terms:
Experimentation, Languages, Theory

Keywords:
architectural extraction, object graphs, ownership domains, runtime architecture