|
Published Articles >> Table of Contents >> Abstract
February 2005 (Vol. 31, No. 2)
pp. 137-149
Efficient Relational Calculation for Software Analysis
Dirk Beyer, IEEE
Andreas Noack, IEEE Computer Society
Claus Lewerentz
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TSE.2005.23
Send link to a friend
| Abstract |
|
Calculating with graphs and relations has many applications in the analysis of software systems, for example, the detection of design patterns or patterns of problematic design and the computation of design metrics. These applications require an expressive query language, in particular, for the detection of graph patterns, and an efficient evaluation of the queries even for large graphs. In this paper, we introduce RML, a simple language for querying and manipulating relations based on predicate calculus, and CrocoPat, an interpreter for RML programs. RML is general because it enables the manipulation not only of graphs (i.e., binary relations), but of relations of arbitrary arity. CrocoPat executes RML programs efficiently because it internally represents relations as binary decision diagrams, a data structure that is well-known as a compact representation of large relations in computer-aided verification. We evaluate RML by giving example programs for several software analyses and CrocoPat by comparing its performance with calculators for binary relations, a Prolog system, and a relational database management system.
|
 References
|
[1] R.C. Holt, “Structural Manipulations Of Software Architecture Using Tarski Relational Algebra,” Proc. Fifth Working Conf. Reverse Eng. (WCRE 1998), pp. 210-219, 1998.
[2] L.M.G. Feijs, R.L. Krikhaar, and R.C. van Ommering, “A Relational Approach to Support Software Architecture Analysis,” Software: Practice and Experience, vol. 28, no. 4, pp. 371-400, 1998.
[3] R. Berghammer, B. Leoniuk, and U. Milanese, “Implementation of Relational Algebra Using Binary Decision Diagrams,” Proc. Sixth Int'l Conf. Relational Methods in Computer Science (RelMiCS 2001), pp. 241-257, 2002.
[4] M. Widenius, D. Axmark, and MySQL AB, MySQL Reference Manual. Sebastopol, Calif.: O'Reilly, 2002.
[5] C.J. Date, An Introduction to Database Systems, eighth ed. Addison-Wesley, 2003.
[6] Swedish Inst. of Computer Science, Quintus Prolog User's Manual. 2003.
[7] W.F. Clocksin and C.S. Mellish, Programming in Prolog, fifth ed. Springer-Verlag, 2003.
[8] R.E. Bryant, “Graph-Based Algorithms for Boolean Function Manipulation,” IEEE Trans. Computers, vol. 35, no. 8, pp. 677-691, Aug. 1986.
[9] D. Beyer and A. Noack, “Crocopat 2.1 Introduction and Reference Manual,” Technical Report UCB//CSD-04-1338, Computer Science Division (EECS), Univ. of California, Berkeley, 2004, http://arxiv.org/abs/cs0409009.
[10] H.-D. Ebbinghaus, J. Flum, and W. Thomas, Mathematical Logic, second ed. Springer-Verlag, 1994.
[11] H. Fahmy, R.C. Holt, and J.R. Cordy, “Wins and Losses of Algebraic Transformations of Software Architectures,” Proc. 16th Int'l Conf. Automated Software Eng. (ASE 2001), pp. 51-60, 2001.
[12] C. Krämer and L. Prechelt, “Design Recovery by Automated Search for Structural Design Patterns in Object-Oriented Software,” Proc. Third Working Conf. Reverse Eng. (WCRE 1996), pp. 208-215, 1996.
[13] G. Antoniol, R. Fiutem, and L. Cristoforetti, “Design Pattern Recovery in Object-Oriented Software,” Proc. Sixth Int'l Workshop Program Comprehension (IWPC 1998), pp. 153-160, 1998.
[14] D. Heuzeroth, T. Holl, G. Högström, and W. Löwe, “Automatic Design Pattern Detection,” Proc. 11th Int'l Workshop Program Comprehension (IWPC 2003), pp. 94-103, 2003.
[15] R.K. Keller, R. Schauer, S. Robitaille, and P. Pagé, “Pattern-Based Reverse-Engineering of Design Components,” Proc. 21st Int'l Conf. Software Eng. (ICSE 1999), pp. 226-235, 1999.
[16] J. Niere, W. Schäfer, J.P. Wadsack, L. Wendehals, and J. Welsh, “Towards Pattern-Based Design Recovery,” Proc. 24th Int'l Conf. Software Eng. (ICSE 2002), pp. 338-348, 2002.
[17] E. Gamma, R. Helm, R. Johnson, and J. Vlissides, Design Patterns. Addison-Wesley, 1995.
[18] A.O. Mendelzon and J. Sametinger, “Reverse Engineering by Visualizing and Querying,” Software— Concepts and Tools, vol. 16, no. 4, pp. 170-182, 1995.
[19] M. Sefika, A. Sane, and R.H. Campbell, “Monitoring Compliance of a Software System with Its High-Level Design Models,” Proc. 18th Int'l Conf. Software Eng. (ICSE 1996), pp. 387-396, 1996.
[20] R. Kazman and M. Burth, “Assessing Architectural Complexity,” Proc. Second Euromicro Conf. Software Maintenance and Reeng. (CSMR 1998), pp. 104-112, 1998.
[21] O. Ciupke, “Automatic Detection of Design Problems in Object-Oriented Reengineering,” Proc. 30th Int'l Conf. Technology of Object-Oriented Languages and Systems (TOOLS 1999), pp. 18-32, 1999.
[22] H. Fahmy and R.C. Holt, “Software Architecture Transformations,” Proc. Int'l Conf. Software Maintenance (ICSM 2000), pp. 88-96, 2000.
[23] B. Henderson-Sellers, Object-Oriented Metrics: Measures of Complexity. Prentice Hall, 1996.
[24] N.E. Fenton and S.L. Pfleeger, Software Metrics: A Rigorous and Practical Approach, second ed. Boston, Mass.: PWS, 1997.
[25] T. Mens and M. Lanza, “A Graph-Based Metamodel for Object-Oriented Software Metrics,” Electronic Notes in Theoretical Computer Science, vol. 72, no. 2, 2002.
[26] B. Kullbach and A. Winter, “Querying as an Enabling Technology in Software Reengineering,” Proc. Third European Conf. Software Maintenance and Reeng. (CSMR 1999), pp. 42-50, 1999.
[27] R.C. Martin, Agile Software Development: Principles, Patterns, and Practices. Prentice Hall, 2003.
[28] Y.-F. Chen, E.R. Gansner, and E. Koutsofios, “A C++ Data Model Supporting Reachability Analysis and Dead Code Detection,” IEEE Trans. Software Eng., vol. 24, no. 9, pp. 682-694, 1998.
[29] K. Mens, R. Wuyts, and T. D'Hondt, “Declaratively Codifying Software Architectures Using Virtual Software Classifications,” Proc. 29th Int'l Conf. Technology of Object-Oriented Languages and Systems— Europe (TOOLS 1999), pp. 33-45, 1999.
[30] G.C. Murphy, D. Notkin, and K.J. Sullivan, “Software Reflexion Models: Bridging the Gap between Design and Implementation,” IEEE Trans. Software Eng., vol. 27, no. 4, pp. 364-380, Apr. 2001.
[31] J. Wu, A.E. Hassan, and R.C. Holt, “Using Graph Patterns to Extract Scenarios,” Proc. 10th Int'l Workshop Program Comprehension (IWPC 2002), pp. 239-247, 2002.
[32] J. Krinke, “Identifying Similar Code with Program Dependence Graphs,” Proc. Eighth Working Conf. Reverse Eng. (WCRE 2001), pp. 301-309, 2001.
[33] F. Shull, W.L. Melo, and V.R. Basili, “An Inductive Method for Discovering Design Patterns from Object-Oriented Software Systems,” Technical Report CS-TR-3597, Computer Science Dept., Univ. of Maryland, 1996.
[34] P. Tonella and G. Antoniol, “Object Oriented Design Pattern Inference,” Proc. Int'l Conf. Software Maintenance (ICSM 1999), pp. 230-238, 1999.
[35] M. Blaha, “A Copper Bullet for Software Quality Improvement,” Computer, vol. 37, no. 2, pp. 21-25, Feb. 2004.
[36] M. Berndl, O. Lhoták, F. Qian, L.J. Hendren, and N. Umanee, “Points-To Analysis Using BDDs,” Proc. Conf. Programming Language Design and Implementation (PLDI 2003), pp. 103-114, 2003.
[37] K. Wong, Rigi User's Manual, Version 5.4.4, 1998, http://ftp.rigi.csc.uvic.ca/pub/rigidoc/.
[38] J.R. Burch, E.M. Clarke, K.L. McMillan, D.L. Dill, and L.J. Hwang, “Symbolic Model Checking: $10^{20}$ States and Beyond,” Information and Computation, vol. 98, no. 2, pp. 142-170, 1992.
[39] R.E. Bryant, “Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams,” ACM Computing Surveys, vol. 24, no. 3, pp. 293-318, 1992.
[40] B. Bollig and I. Wegener, “Improving the Variable Ordering of OBDDs Is NP-Complete,” IEEE Trans. Computers, vol. 45, no. 9, pp. 993-1002, Sept. 1996.
[41] C.L. Berman, “Circuit Width, Register Allocation, and Ordered Binary Decision Diagrams,” IEEE Trans. Computer-Aided Design, vol. 10, no. 8, pp. 1059-1066, 1991.
[42] S.-W. Jeong, B. Plessier, G.D. Hachtel, and F. Somenzi, “Variable Ordering and Selection for FSM Traversal,” Proc. Int'l Conf. Computer-Aided Design (ICCAD 1991), pp. 476-479, 1991.
[43] A. Aziz, S. Tasiran, and R.K. Brayton, “BDD Variable Ordering for Interacting Finite State Machines,” Proc. 31st Design Automation Conf. (DAC 1994), pp. 283-288, 1994.
[44] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman, 1979.
[45] G. Janssen, “A Consumer Report on BDD Packages,” Proc. 16th Symp. Integrated Circuits and Systems Design (SBCCI 2003), pp. 217-222, 2003.
[46] K.S. Brace, R.L. Rudell, and R.E. Bryant, “Efficient Implementation of a BDD Package,” Proc. 27th Design Automation Conf. (DAC 1990), pp. 40-45, 1990.
[47] S. Warshall, “A Theorem on Boolean Matrices,” J. ACM, vol. 9, no. 1, pp. 11-12, 1962.
[48] ANSI/ISO/IEC 9075:1999, “Information Technology— Database Languages— SQL— Part 2: Foundation,” 1999.
[49] R.A. O'Keefe, The Craft of Prolog. MIT Press, 1990.
[50] A.V. Aho and J.D. Ullman, “Universality of Data Retrieval Languages,” Proc. Sixth Ann. ACM Symp. Principles of Programming Languages (POPL 1979), pp. 110-120, 1979.
[51] J. Ebert, B. Kullbach, V. Riediger, and A. Winter, “GUPRO— Generic Understanding of Programs,” Electronic Notes in Theoretical Computer Science, vol. 72, no. 2, 2002.
[52] D. Blostein and A. Schürr, “Computing with Graphs and Graph Transformations,” Software: Practice and Experience, vol. 29, no. 3, pp. 197-217, 1999.
|
 Additional Information
|
Index Terms- Logic programming, graph algorithms, data structures, reverse engineering, reengineering.
Citation:
Dirk Beyer, Andreas Noack, Claus Lewerentz,
"Efficient Relational Calculation for Software Analysis,"
IEEE Transactions on Software Engineering,
vol. 31,
no. 2,
pp. 137-149,
Feb.,
2005
|
|
RSS Feed