GENOA—a customizable, front-end-retargetable source code analysis framework

ABSTRACT

Code analysis tools provide support for such software engineering tasks as program understanding, software metrics, testing, and reengineering. In this article we describe GENOA, the framework underlying application generators such as Aria and GEN++ which have been used to generate a wide range of practical code analysis tools. This experience illustrates front-end retargetability of GENOA; we describe the features of the GENOA framework that allow it to be used with different front ends. While permitting arbitrary parse tree computations, the GENOA specification language has special, compact iteration operators that are tuned for expressing simple, polynomial-time analysis programs; in fact, there is a useful sublanguage of the GENOA language that can express precisely all (and only) polynomial-time (PTIME) analysis programs on parse trees. Thus, we argue that the GENOA language is a simple and convenient vehicle for implementing a range of analysis tools. We also argue that the “front-and reuse” approach of GENOA offers an important advantage for tools aimed at large software projects: the reuse of complex, expensive build procedures to run generated tools over large source bases. In this article, we describe the GENOA framework and our experiences with it.

REFERENCES

• 1: Robert A. Ballance , Susan L. Graham , Michael L. Van De Vanter, The Pan language-based editing system for integrated development, ACM SIGSOFT Software Engineering Notes, v.15 n.6, p.77-93, Dec. 1990
• 2: BASILI, V., BRIAND, L., AND MELO, W. 1995. Measuring the impact of reuse on quality and productivity in object-oriented systems. Tech. Rep. CS-TR-3395. Department of Computer Science, University of Maryland, College Park, MD.
• 3: James M. Bieman , Byung-Kyoo Kang, Cohesion and reuse in an object-oriented system, Proceedings of the 1995 Symposium on Software reusability, p.259-262, April 29-30, 1995, Seattle, Washington, United States
• 4: P. Borras , D. Clement , Th. Despeyroux , J. Incerpi , G. Kahn , B. Lang , V. Pascual, Centaur: the system, Proceedings of the third ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.14-24, November 28-30, 1988, Boston, Massachusetts, United States
• 5: CHEN, Y. F. AND RAMAMOORTHY, C.V. 1986. The C information abstractor. In Proceedings of the lOth International IEEE on Computer Software and Applications Conference (COMP- SAC, Chicago, IL, Oct.). IEEE Press, Piscataway, NJ.
• 6: S. R. Chidamber , C. F. Kemerer, A Metrics Suite for Object Oriented Design, IEEE Transactions on Software Engineering, v.20 n.6, p.476-493, June 1994 [doi>10.1109/32.295895]
• 7: CLEAVELAND, J. C. AND KINTALA, C. 1988. Tools for building applications generators. AT&T Tech. J. 67, 4.
• 8: Mariano Consens , Alberto Mendelzon , Arthur Ryman, Visualizing and querying software structures, Proceedings of the 14th international conference on Software engineering, p.138-156, May 11-15, 1992, Melbourne, Australia [doi>10.1145/143062.143106]
• 9: T. A. Corbi, Program understanding: challenge for the 1990's, IBM Systems Journal, v.28 n.2, p.294-306, 1989
• 10: CREW, R. F. 1997. Astlog: A language for examining abstract syntax trees. In Proceedings of 1st Usenix Conference on Domain-Specific Languages (Oct.). USENIX Assoc., Berkeley, CA.
• 11: Premkomar Thomas Devanbu, Software information systems, Rutgers University, New Brunswick, NJ, 1994
• 12: DEVANBU, P. 1998. The gen+ + page. University of California at Davis, Davis, CA. http://seclab.cs.ucdavis.edu/~devanbu/genp
• 13: Prem Devanbu , Ron Brachman , Peter G. Selfridge, LaSSIE: a knowledge-based software information system, Communications of the ACM, v.34 n.5, p.34-49, May 1991 [doi>10.1145/103167.103172]
• 14: Prem Devanbu , Sakke Karstu , Walcélio Melo , William Thomas, Analytical and empirical evaluation of software reuse metrics, Proceedings of the 18th international conference on Software engineering, p.189-199, March 25-29, 1996, Berlin, Germany
• 15: Premkumar T. Devanbu , David S. Rosenblum , Alexander L. Wolf, Generating testing and analysis tools with Aria, ACM Transactions on Software Engineering and Methodology (TOSEM), v.5 n.1, p.42-62, Jan. 1996 [doi>10.1145/226155.226157]
• 16: Carolyn K. Duby , Scott Meyers , Steven P. Reiss, CCEL: A Metalanguage for C++, Brown University, Providence, RI, 1992
• 17: GRASS, J. AND CHEN, Y. F. 1990. The C + + information abstractor. In Proceedings of the 2nd USENIX on USENIX C+ + Conference (Apr.). USENIX Assoc., Berkeley, CA.
• 18: Robert W. Gray , Steven P. Levi , Vincent P. Heuring , Anthony M. Sloane , William M. Waite, Eli: a complete, flexible compiler construction system, Communications of the ACM, v.35 n.2, p.121-130, Feb. 1992 [doi>10.1145/129630.129637]
• 19: William G. Griswold , Darren C. Atkinson, Managing design trade-offs for a program understanding and transformation tool, Journal of Systems and Software, v.30 n.1-2, p.99-116, July/Aug. 1995 [doi>10.1016/0164-1212(94)00119-8]
• 20: William G. Griswold , Darren C. Atkinson , Collin McCurdy, Fast, Flexible Syntactic Pattern Matching and Processing, Proceedings of the 4th International Workshop on Program Comprehension (WPC '96), p.144, March 29-31, 1996
• 21: A N Habermann , D Notkin, Gandalf: software development environments, IEEE Transactions on Software Engineering, v.12 n.12, p.1117-1127, Dec.1986
• 22: Ellis Horowitz , Ronald Williamson, SODOS—a software documentation support environment: its use, Proceedings of the 8th international conference on Software engineering, p.8-14, August 28-30, 1985, London, England
• 23: Susan Horwitz, Adding relational query facilities to software development environments, Theoretical Computer Science, v.73 n.2, p.213-230, June 22, 1990
• 24: Susan Horwitz , Tim Teitelbaum, Generating editing environments based on relations and attributes, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.577-608, Oct. 1986 [doi>10.1145/6465.6512]
• 25: Neil Immerman, Relational queries computable in polynomial time, Information and Control, v.68 n.1-3, p.86-104, Jan/Feb/March 1986 [doi>10.1016/S0019-9958(86)80029-8]
• 26: JERDING, D., STASKO, J., AND BALL, T. 1997. Visualizing message patterns in object-oriented program. In Proceedings of the 19th International Conference on Software Engineering (ICSE '97, May). IEEE Press, Piscataway, NJ.
• 27: KARSTU, S. AND OTT, L. 1994. An investigation of the behaviour of slice based cohesion measures. Tech. Rep. CS-TR 94-03. Michigan Technological Univ., Houghton, MI.
• 28: KOWALSKI, T., SEQUIST, C., ELLIS, B., GOGUEN, H. H., PUTTRESS, J. J., CASTILLO, C. M., ROWLAND, J. R., RATH, C. A., WILSON, J. M., VESONDER, G., AND SCHMIDT, J. L. 1991. A reflective C programming environment. In Proceedings of the International Workshop on UNIX-Based Software Development Environments. USENIX Assoc., Berkeley, CA.
• 29: David A. Ladd , J. Christopher Ramming, A": A Language for Implementing Language Processors, IEEE Transactions on Software Engineering, v.21 n.11, p.894-901, November 1995 [doi>10.1109/32.473218]
• 30: Mark A. Linton, Implementing relational views of programs, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.132-140, April 1984
• 31: Mark A. Linton , John M. Vissides , Paul R. Calder, Composing User Interfaces with InterViews, Computer, v.22 n.2, p.8-22, February 1989 [doi>10.1109/2.19829]
• 32: MENDON~A, N. C. AND KRAMER, J., Eds. 1998. Proceedings of Workshop on Program Comprehension. (Los Alamitos, CA, Apr.) IEEE Computer Society, Washington, DC.
• 33: Gail C. Murphy , David Notkin, Lightweight lexical source model extraction, ACM Transactions on Software Engineering and Methodology (TOSEM), v.5 n.3, p.262-292, July 1996 [doi>10.1145/234426.234441]
• 34: S. Paul , A. Prakash, A Framework for Source Code Search Using Program Patterns, IEEE Transactions on Software Engineering, v.20 n.6, p.463-475, June 1994 [doi>10.1109/32.295894]
• 35: Santanu Paul , Ataul Prakash, A Query Algebra for Program Databases, IEEE Transactions on Software Engineering, v.22 n.3, p.202-217, March 1996 [doi>10.1109/32.489080]
• 36: Maria H Penedo, Prototyping a project master database for software engineering environments, Proceedings of the second ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.1-11, December 09-11, 1986, Palo Alto, California, United States
• 37: REASONING SYSTEMS. 1989. REFINE User's Guide. Reasoning Systems, Inc., Palo Alto, CA.
• 38: Thomas Reps , Tim Teitelbaum, The synthesizer generator, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.42-48, April 1984
• 39: ROSENBLUM, D. AND WOLF, A. 1991. Representing semantically analyzed C++ code with Reprise. In Proceedings of the 3rd USENIX on C+ + Conference (Apr.). USENIX Assoc., Berkeley, CA.
• 40: SELLINK, M. P. A. AND VERHOEF, C. 1998. Generation of software renovation factories from compilers. Tech. Rep. P98. Dept. of Computer Science, Univ. of Amsterdam, The Netherlands.
• 41: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]
• 42: STEFFEN, J. 1981. The CScope Program: Berkeley UNIX Release 3.2.
• 43: Margaret-Anne D. Storey , Kenny Wong , Hausi A. Müller, Rigi: a visualization environment for reverse engineering, Proceedings of the 19th international conference on Software engineering, p.606-607, May 17-23, 1997, Boston, Massachusetts, United States [doi>10.1145/253228.253496]
• 44: A. van Lamsweerde , B. Delcourt , E. Delor , M. C. Schayes , R. Champagne, Generic Lifecycle Support in the ALMA Environment, IEEE Transactions on Software Engineering, v.14 n.6, p.720-741, June 1988 [doi>10.1109/32.6153]
• 45: Steven Woods , Alex Quilici, Some Experiments Toward Understanding How Program Plan Recognition Algorithms Scale, Proceedings of the 3rd Working Conference on Reverse Engineering (WCRE '96), p.21, November 08-10, 1996
• 46: ZEIGLER, S. 1995. Comparing development costs of C and Ada. Tech. Rep. Rational Software Corp. Available via http://wuarchive.wustl.edu/languages/ada/ajpo/docs/reports/cada/ cada art.html.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

General Terms:
Languages

Keywords:
code inspection, metrics, reverse engineering, source analysis