Wisconsin Program-Slicing Project


Table of Contents


Disclaimer

This web page contains links to PostScript and PDF files of articles that may be covered by copyright. You may browse the articles at your convenience (in the same spirit that you read a journal article or an article from a conference proceedings in a public library). Retrieving, copying, or distributing these files may violate copyright law.

Please note that the definitive versions of these papers are the published versions. The PostScript versions are provided here as a courtesy, and, in some cases, there may be differences between the PostScript provided here and the published version. We believe that all of the differences are either formatting differences or copy-editing changes. If you cite these papers, please cite the published version rather than giving a URL.

[Back to the Table of Contents]


Research Summary

The goal of this project is to create enhanced tools to support the development of complex software systems. The objective is to create tools that provide powerful language-specific program-manipulation operations. In particular, the project has explored how program slicing can serve as the basis for such program-manipulation operations.

The slice of a program with respect to a set of program elements S is a projection of the program that includes only program elements that might affect (either directly or transitively) the values of the variables used at members of S. Slicing allows one to find semantically meaningful decompositions of programs, where the decompositions consist of elements that are not textually contiguous.

Program slicing is a fundamental operation that can aid in solving many software-engineering problems. For instance, it has applications to program understanding, maintenance, debugging, testing, differencing, specialization, reuse, and merging.

The activities of the project have been devoted to:

More recently, we found some unexpected connections between interprocedural dataflow analysis and our previous work on interprocedural program slicing. In particular, we have shown how a large class of interprocedural dataflow-analysis problems can be solved by transforming them into a special kind of graph-reachability problem. This graph-reachability problem can be solved precisely in polynomial time by the algorithm originally developed for interprocedural slicing.

[Back to the Table of Contents]


Recent Items of Note*new*

Recent Publications

[Back to the Table of Contents]

Miscellaneous

  1. Raghavan Komondoor has made available the software for detecting clones in C code that he developed as part of his Ph.D. dissertation.

  2. The paper was selected for inclusion in a special SIGPLAN collection of the 50 most influential papers from the SIGPLAN Conference on Programming Language Design and Implementation from 1979 to 1999:

    A retrospective on the paper was published as

    An extended version of the PLDI 88 paper later appeared as the following journal paper:

[Back to the Table of Contents]

Availability of Program-Slicing Tools

The Wisconsin Program-Slicing Tool

The The Wisconsin Program-Slicing Tool is a software system that supports operations on C programs, including backward slicing, forward slicing, and chopping [TOPLAS90, FSE94, FSE95b], which can help the user gain an understanding of what a program does and how it works. The Wisconsin Program-Slicing Tool consists of a package for building and manipulating control-flow graphs and program dependence graphs, as well as a front-end that parses C programs and translates them to the internal representations used for slicing.

Although the Wisconsin Program-Slicing Tool was distributed from 1996-2000 for not-for-profit research purposes under license from the University of Wisconsin, it is no longer being distributed. However, there is a commercial tool available, named CodeSurfer, that is derived from the Wisconsin implementation and is available from GrammaTech, Inc. GrammaTech has improved on the Wisconsin implementation considerably (both in terms of speed and space efficiency). GrammaTech also provides CodeSurfer to academic researchers on very favorable terms.

CodeSurfer

The Wisconsin program-slicing technology is now available in a commercial product, the CodeSurfertm tool available from GrammaTech, Inc.

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. 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. 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) [TOPLAS90, FSE94]. Operations that highlight paths between nodes in the dependence graph (chops) show ways in which the program points are interdependent (or independent) [FSE95b]. 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.

Full information about CodeSurfer is available here, where you can find

You should be aware that the most important current limitations of CodeSurfer are as follows: CodeSurfer is currently available for Windows NT, Windows 2000, Windows XP, Linux, and Solaris (2.5.1 or later).

[Back to the Table of Contents]


Personnel

Faculty

Current Post-Docoral Associates, Staff, and Visitors

Students

Former Students, Post-Doctoral Associates, Staff, and Visitors

[Back to the Table of Contents]


Categorized Index to Project Publications

Program Slicing, Differencing, Merging, etc.

Overview

The Wisconsin Program-Slicing Tool

CodeSurfer System

Slicing

Chopping

Differencing

Merging

Algebra of slices (and applications to program merging)

Semantics and slicing

Other applications of slicing

Implemented integration system (for a small Pascal subset)

Miscellaneous

Ph.D. Dissertations

[Back to the Table of Contents]

Interprocedural Dataflow Analysis

Demand IDFA via bottom-up logic programming and the magic-sets transformation

Exhaustive and Demand IDFA via graph reachability

IDFA using more than graph reachability

PTIME completeness of IDFA

[Back to the Table of Contents]

Alias Analysis, Pointer Analysis, and Shape Analysis

Ph.D. Dissertations

[Back to the Table of Contents]

Analysis of Multi-Threaded Programs

Ph.D. Dissertations

[Back to the top]

Symbolic Abstraction and Decision Procedures

Ph.D. Dissertations

[Back to the top]

Other Program-Analysis Problems

Ph.D. Dissertations

[Back to the top]

Path Problems

Context-Free-Language Reachability

Other Path Problems

Ph.D. Dissertations

[Back to the Table of Contents]

Model Checking

Software

Ph.D. Dissertations

[Back to the Table of Contents]

Computer Security

Ph.D. Dissertations

[Back to the Table of Contents]

Code Instrumentation

Ph.D. Dissertations

[Back to the Table of Contents]

Computational Differentiation and Computational Divided Differencing

[Back to the Table of Contents]

Clone Detection

Software

Ph.D. Dissertations

[Back to the Table of Contents]

Miscellaneous

[Back to the Table of Contents]


Project Bibliography

Books

[Back to the top]

Journal Publications

[Back to the Table of Contents]

Invited Papers

[Back to the Table of Contents]

Book Chapters

[Back to the Table of Contents]

Reprinted in Collections

[Back to the Table of Contents]

Edited Books

[Back to the Table of Contents]

Conference and Refereed Workshop Publications

[Back to the Table of Contents]

Patents

[Back to the Table of Contents]

Pending Submissions

[Back to the Table of Contents]

Ph.D. Dissertations

[Back to the Table of Contents]

Magazine Articles

[Back to the Table of Contents]

Other Publications and Reports

[Back to the Table of Contents]


Software

[Back to the Table of Contents]