UML formalization is a traceability problem

ABSTRACT

Largely driven by the widespread interest in using UML, significant efforts have investigated how to formalize its semantics in terms of well-defined target languages. Associating target language specifications with the UML models enables automated analysis of its many graphical diagrams. Unfortunately, UML formalizations have proved difficult to completely automate. This paper posits that UML formalization is essentially a traceability problem, which means to rigorously link elements of a given UML diagram to relevant regions of code in a given target model according to the intended formalization semantics. We present a graph-theoretic model for formally defining this link-retrieval problem. We also introduce a framework for assessing whether a UML formalization is amenable to efficient link retrieval techniques without sacrificing precision and/or recall.

REFERENCES

• 1: Giuliano Antoniol , Gerardo Canfora , Gerardo Casazza , Andrea De Lucia , Ettore Merlo, Recovering Traceability Links between Code and Documentation, IEEE Transactions on Software Engineering, v.28 n.10, p.970-983, October 2002 [doi>10.1109/TSE.2002.1041053]
• 2: Betty H. C. Cheng , Enoch Y. Wang, Formalizing and integrating the dynamic model for object-oriented modeling, IEEE Transactions on Software Engineering, v.28 n.8, p.747-762, August 2002 [doi>10.1109/TSE.2002.1027798]
• 3: George Copeland , David Maier, Making smalltalk a database system, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 4: M. Deng, R. E. K. Stirewalt, and B. H. C. Cheng. Retrieval by construction: A traceability technique to support verification and validation of UML formalizations. International Journal of Software Engineering and Knowledge Engineering, Oct. 2005. to appear.
• 5: William B. Frakes , Ricardo Baeza-Yates, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: Jane Huffman Hayes , Alex Dekhtyar , James Osborne, Improving Requirements Tracing via Information Retrieval, Proceedings of the 11th IEEE International Conference on Requirements Engineering, p.138, September 08-12, 2003
• 8: G. Holzmann. The SPIN model checker. Addison-Wesley Publisher, 2004.
• 9: Setrag N. Khoshafian , George P. Copeland, Object identity, Conference proceedings on Object-oriented programming systems, languages and applications, p.406-416, September 29-October 02, 1986, Portland, Oregon, United States
• 10: S.-K. Kim and D. A. Carrington. A formal denotational semantics of UML in Object-Z. L'OBJET: Software, Databases, Networks, 7(1), 2001.
• 11: Luigi Lavazza , Gabriele Quaroni , Matteo Venturelli, Combining UML and formal notations for modelling real-time systems, Proceedings of the 8th European software engineering conference held jointly with 9th ACM SIGSOFT international symposium on Foundations of software engineering, September 10-14, 2001, Vienna, Austria
• 12: Andrian Marcus , Jonathan I. Maletic, Recovering documentation-to-source-code traceability links using latent semantic indexing, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 13: Kenneth L. McMillan, Symbolic Model Checking, Kluwer Academic Publishers, Norwell, MA, 1993
• 14: William E. McUmber , Betty H. C. Cheng, A general framework for formalizing UML with formal languages, Proceedings of the 23rd International Conference on Software Engineering, p.433-442, May 12-19, 2001, Toronto, Ontario, Canada
• 15: Object Management Group. UML Specifications, Version 1.5, March 2003. http://www.omg.org/uml.
• 16: Promela language reference. http://spinroot.com/spin/Man/promela.html.
• 17: S. W. Reyner. An analysis of a good algorithm for the subtree problem. SIAM Journal on Computing, 6(4):730--732.
• 18: Julian Richardson , Jeff Green, Automating Traceability for Generated Software Artifacts, Proceedings of the 19th IEEE international conference on Automated software engineering, p.24-33, September 20-24, 2004 [doi>10.1109/ASE.2004.20]
• 19: James Rumbaugh , Ivar Jacobson , Grady Booch, The Unified Modeling Language reference manual, Addison-Wesley Longman Ltd., Essex, UK, 1998
• 20: Malcolm Shroff , Robert B. France, Towards a formalization of UML class structures in Z, Proceedings of the 21st International Computer Software and Applications Conference, p.646, August 11-15, 1997
• 21: J. M. Spivey, The Z notation: a reference manual, Prentice Hall International (UK) Ltd., Hertfordshire, UK, 1992
• 22: M. C. Tanuan. Automated analysis of unified modeling language (UML) specifications. Master's thesis, Univ. of Waterloo, August 2001.
• 23: A. Zisman, G. Spanoudakis, E. Peres-Minana, and P. Krause. Tracing software engineering artifacts. In Proceedings of the 2003 International Conference on Software Engineering Research and Practice (SERP'03), 2003.

INDEX TERMS

Keywords:
UML formalization, graph theory, traceability