CodeSurfer and its Foundations

CodeSurfer is based on more than a decade of celebrated R&D. This page provides links to selected publications that describe CodeSurfer and its underlying technology.

Copyright.  Some links point to PostScript files of articles that may be covered by copyright. You may access such articles under the "fair-use" doctrine, but retrieving, copying, or distributing these files in bulk may violate copyright law.

Descriptive Index to Selected Publications

CodeSurfer.  CodeSurfer is a tool for analysis, understanding, and inspection of software[Overview].

Dependence Graphs.  CodeSurfer builds a dependence-graph program representation and provides a GUI for exploring this web. The dependence graph includes forward and backward links between each assignment statement and possible uses of the values stored by that assignment [TOPLAS90, Slides].

Pointer Analysis.  Pointer analysis is used so that indirect loads and stores through pointers are taken into account, as well as indirect function calls. Dataflow analysis is used so that links between unrelated assignments and uses are excluded [POPL97].

Slicing.  Operations that highlight forward and backward slices show the impact of a given statement on the rest of the program (forward slicing), and the impact of the rest of a program on a given statement (backward slicing) [FSE94].

Chopping.  Operations that highlight paths between nodes in the dependence graph (chops) show ways in which the program points are interdependent (or independent) [FSE95b].

Scripting.  CodeSurfer's scripting language, which provides access to the dependence-graph program representation and the Tk widget set, is used for extensibility and for batch applications.

Applications.  Dependence graphs, slicing, and chopping have numerous applications in software engineering, including semantics-based program differencing and merging [ICSE92, TOPLAS89], program specialization [DAGSTUHL96], program testing [POPL93], and inspection[POPL93]. CodeSurfer prototypes for the hardware description languages VHDL [CHARM99] and Verilog have also been implemented.

Theory.  Program dependence graphs and slicing have a well-established theory that provides CodeSurfer with a firm semantic foundation [CCIPL89, SCP91].

Engineering.  Innovations in CodeSurfer's implementation include its patented intermediate representation [Patent] and numerous efficient algorithms [FSE94].

Selected Bibliography

Journal Publications

Invited Papers

  • Reps, T., Program analysis via graph reachability. In Proc. of ILPS '97: International Logic Programming Symposium, (Port Jefferson, NY, Oct. 12-16, 1997), J. Maluszynski (ed.), The M.I.T. Press, Cambridge, MA, 1997, pp. 5-19. [abstract; paper (.ps), (c) Springer-Verlag]
  • Reps, T., The use of program profiling in software testing. In Proc. of Informatik '97 (Aachen, Germany, Sept. 24-27, 1997), M. Jarke, K. Pasedach, and K. Pohl (eds.), Springer-Verlag, Berlin, Ger., 1997, pp. 4-16. [abstract; paper, (c) Springer-Verlag]
  • Horwitz, S. and Reps, T., The use of program dependence graphs in software engineering. In Proceedings of the Fourteenth International Conference on Software Engineering, (May 11-15, 1992, Melbourne, Australia), ACM, New York, NY, 1992, pp. 392-411. [abstract; paper (.ps)]
  • Reps, T. and Horwitz, S., Semantics-based program integration. In Proceedings of the Second European Symposium on Programming, (Nancy, France, March 21-25, 1988), Lecture Notes in Computer Science, Vol. 300, H. Ganzinger (ed.), Springer-Verlag, New York, NY, 1988, pp. 1-20.

Book Chapters

  • Horwitz, S., Reps, T., and Binkley, D., Interprocedural slicing using dependence graphs. In Software Change Impact Analysis, S.A. Bohner and R.S. Arnold (eds.), IEEE Computer Society, Los Alamitos, CA, 1996.

    Reprinted from ACM Transactions on Programming Languages and Systems 12, 1 (January 1990), 26-60. [abstract; paper (.ps)]

  • Horwitz, S., Reps, T., and Binkley, D., Interprocedural slicing using dependence graphs. In Software Merging and Slicing, V. Berzins (ed.), IEEE Computer Society, Los Alamitos, CA, pp. 10-44.

    Reprinted from ACM Transactions on Programming Languages and Systems 12, 1 (January 1990), 26-60. [abstract; paper (.ps)]

  • Horwitz, S., Prins, J., and Reps, T., Integrating non-interfering versions of programs. In Software Merging and Slicing, V. Berzins (ed.), IEEE Computer Society, Los Alamitos, CA, pp. 137-179.

    Reprinted from ACM Transactions on Programming Languages and Systems 11, 3 (July 1989), 345-387. [abstract; paper (.ps)]

Conference Publications

  • Bishop, P., Bloomfield, R., Clement, T., and Guerra, S., Software Criticality Analysis of COTS/SOUP. In Proceedings of SAFECOMP 2002: Computer Safety, Reliability and Security, (Catania, Italy, September 10-13, 2002). [paper (.pdf)]
  • Horwitz, S., Tool support for improving test coverage. In Proceedings of ESOP 2002: European Symposium on Programming, (Grenoble, France, April 8-12, 2002). [abstract; paper (.ps); paper (.pdf); (c) Springer-Verlag]
  • Kumar, S. and Horwitz, S., Better slicing of programs with jumps and switches. In Proceedings of FASE 2002: Fundamental Approaches to Software Engineering, (Grenoble, France, April 8-12, 2002). [abstract; paper (.ps); paper (.pdf); (c) Springer-Verlag]
  • Anderson, P., Binkley, D., Rosay, G., Teitelbaum, T., Flow Insensitive Points-to Sets. In Proceedings of the First IEEE Workshop on Source Code Analysis and Manipulation, (Florence, Italy, November 2001), pp. 79-89. [paper (.ps); paper (.pdf)]
  • Anderson, P. and Teitelbaum, T., Software Inspection Using CodeSurfer. To appear in Workshop on Inspection in Software Engineering (CAV 2001), (Paris, France., July 18-23, 2001). [paper ]
  • Komondoor, R. and Horwitz, S., Using slicing to identify duplication in source code. In Proceedings of the 8th International Symposium on Static Analysis, (Paris, France, July 16-18, 2001). [abstract; paper (.ps); paper (.pdf); (c) Springer-Verlag]
  • Komondoor, R. and Horwitz, S., Tool Demonstration: Finding duplicated code using program dependences. In Proceedings of ESOP 2001: European Symposium on Programming, (Genoa, Italy, April 2-6, 2001). [paper (.ps); paper (.pdf); (c) Springer-Verlag]
  • Clarke, E.M., Fujita, M., Rajan, P.S., Reps, T., Shankar, S., and Teitelbaum, T., Program slicing of hardware description languages. In Proc. of Charme '99, (Bad Herrenalb, Ger., Sept. 27-29, 1999). [abstract; paper (.ps)]
  • Yong, S.H., Horwitz, S., and Reps, T., Pointer analysis for programs with structures and casting. In SIGPLAN '99: Proceedings of the ACM Conference on Programming Language Design and Implementation, (Atlanta, GA, May 1-4, 1999), ACM SIGPLAN Notices 34, 5 (May 1999), pp. 91-103. [abstract; paper (.ps)]
  • Shapiro, M. and Horwitz, S., The effects of the precision of pointer analysis. In Proceedings of the 4th International Symposium on Static Analysis, (Paris, France, September 8-10, 1997), Lecture Notes in Computer Science, Vol. 1302, Pascal Van Hentenryck (ed.), Springer-Verlag, New York, NY, 1997, pp. 16-34. [abstract; paper (.ps), (c) Springer-Verlag]
  • Shapiro, M. and Horwitz, S., Fast and accurate flow-insensitive points-to analysis. In Conference Record of the Twenty-Fourth ACM Symposium on Principles of Programming Languages, (Paris, France, Jan. 15-17, 1997). [abstract; paper (.ps)]
  • Reps, T. and Turnidge, T., Program specialization via program slicing. In Proceedings of the Dagstuhl Seminar on Partial Evaluation, (Schloss Dagstuhl, Wadern, Germany, Feb. 12-16, 1996), Lecture Notes in Computer Science, Vol. 1110, O. Danvy, R. Glueck, and P. Thiemann (eds.), Springer-Verlag, New York, NY, 1996, pp. 409-429. [abstract; paper (.ps), (c) Springer-Verlag]
  • Reps, T. and Rosay, G., Precise interprocedural chopping. In SIGSOFT '95: Proceedings of the Third ACM SIGSOFT Symposium on the Foundations of Software Engineering, (Washington, DC, October 10-13, 1995), ACM SIGSOFT Software Engineering Notes 20, 4 (1995), pp. 41-52. [abstract; paper (.ps)]
  • Reps, T., Horwitz, S., Sagiv, M., and Rosay, G., Speeding up slicing. In SIGSOFT '94: Proceedings of the Second ACM SIGSOFT Symposium on the Foundations of Software Engineering, (New Orleans, LA, December 7-9, 1994), ACM SIGSOFT Software Engineering Notes 19, 5 (December 1994), pp. 11-20. [abstract; paper (.ps)]
  • Ball, T. and Horwitz, S., Slicing programs with arbitrary control flow. In Proceedings of the First International Workshop on Automated and Algorithmic Debugging, (Linkoeping, Sweden, May 1993), Lecture Notes in Computer Science, Vol. 749, Springer-Verlag, New York, NY, 1993, pp. 206-222. [paper (.ps), (c) Springer-Verlag]
  • Bates, S. and Horwitz, S., Incremental program testing using program dependence graphs. In Conference Record of the Twentieth ACM Symposium on Principles of Programming Languages, (Charleston, SC, January 10-13, 1993), ACM, New York, NY, 1993, pp. 384-396.
  • Pfeiffer, P. and Selke, R.P., On the adequacy of dependence-based representations for programs with heaps. In Proceedings of the International Conference on Theoretical Aspects of Computer Software (TACS '91), (Sendai, Japan, September 1991), Lecture Notes in Computer Science, Vol. 526, T. Ito and A. R. Meyer (eds.), Springer-Verlag, New York, NY, 1991.
  • Horwitz, S., Identifying the semantic and textual differences between two versions of a program. In Proceedings of the ACM SIGPLAN 90 Conference on Programming Language Design and Implementation (White Plains, NY, June 20-22, 1990), ACM SIGPLAN Notices 25, 6 (June 1990), pp. 234-245.
  • Reps, T., Algebraic properties of program integration. In Proceedings of the 3nd European Symposium on Programming (Copenhagen, Denmark, May 15-18, 1990), Lecture Notes in Computer Science, Vol. 432, N. Jones (ed.), Springer-Verlag, New York, NY, 1990, pp. 326-340.
  • Reps, T. and Bricker, T., Illustrating interference in interfering versions of programs. In Proceedings of the Second International Workshop on Software Configuration Management, (Princeton, NJ, October 24-27, 1989), ACM Software Engineering Notes 17, 7 (November 1989), pp. 46-55.
  • Horwitz, S., Pfeiffer, P., and Reps, T., Dependence analysis for pointer variables. In Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation, (Portland, OR, June 21-23, 1989), ACM SIGPLAN Notices 24, 7 (July 1989), pp. 28-40.
  • Reps, T. and Yang, W., The semantics of program slicing and program integration. In Proceedings of the Colloquium on Current Issues in Programming Languages, (Barcelona, Spain, March 13-17, 1989), Lecture Notes in Computer Science, Vol. 352, J. Diaz and F. Orejas (eds.), Springer-Verlag, New York, NY, 1989, pp. 360-374.
  • Horwitz, S., Reps, T., and Binkley, D., Interprocedural slicing using dependence graphs. In Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation, (Atlanta, GA, June 22-24, 1988), ACM SIGPLAN Notices 23, 7 (July 1988), pp. 35-46.
  • Reps, T., Horwitz, S., and Prins, J., Support for integrating program variants in an environment for programming in the large. In Proceedings of the International Workshop on Software Version and Configuration Control, (Grassau, W. Germany, Jan. 27-29, 1988), Berichte des German Chapter of the ACM, Vol. 30, J.F.H. Winkler (ed.), B.G. Teubner, Stuttgart, W. Germany, 1988, pp. 197-216.
  • Horwitz, S., Prins, J., and Reps, T., Integrating non-interfering versions of programs. In Conference Record of the Fifteenth ACM Symposium on Principles of Programming Languages, (San Diego, CA, January 13-15, 1988), ACM, New York, NY, 1988, pp. 133-145.
  • Horwitz, S., Prins, J., and Reps, T., On the adequacy of program dependence graphs for representing programs. In Conference Record of the Fifteenth ACM Symposium on Principles of Programming Languages, (San Diego, CA, January 13-15, 1988), ACM, New York, NY, 1988, pp. 146-157. [abstract; paper (.ps)]

Commercial Publications

Patents


Free Trial | Products | Customers | Support | News | Jobs | About Us         © 2007-2008, GrammaTech, Inc. All rights reserved.