@InProceedings{Che93, author = {Jingde Cheng}, title = {Slicing Concurrent Programs --- A Graph-Theoretical Approach}, booktitle = {Proceedings of the First International Workshop on Automated and Algoritmic Debugging}, OPTcrossref = {}, OPTkey = {}, pages = {223-240}, year = {1993}, OPTeditor = {}, volume = {749}, OPTnumber = {}, series = {LNCS}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, publisher = {Spring-Verlag}, OPTnote = {}, abstract ={ This paper extends the notion of slicing, which was originally proposed and studied for sequential prrograms, to concurrent programs and presents a graph-theoretical approach to slicing concurrent programs. In addition to the usual control and data dependences proposed and studied for sequential programs, the paper introduces three new types of primary program dependences in concurrent programs, named the selection dependence, synchronization dependence, and communication dependence. The paper also propose a new program representation for concurrent programs, named the Process Dependence Net (PDN), which is an arc-classified digraph to explicitly represent the five types of primary program dependences in the programs. As a result, various notions about slicing concurrent programs can be formally defined based on the representation, and the problem of slicing a concurrent program can be simply reduced to a vertex reachability problem in its PDN representation.}, URL ={http://www.slab.csce.kyushu-u.ac.jp/~cheng/pub/Slicing.AADEBUG93.ps}, OPTannote = {} } @InProceedings{Zhao96, author = {Jianjun Zhao and Jingde Cheng and Kazuo Ushijima}, title = {Static Slicing of concurrent Object-Oriented Programs}, booktitle = {Proceedings of the 20th IEEE Annual International Computer Software and Applications Conference (COMPSAC'96)}, OPTcrossref = {}, OPTkey = {}, pages = {312-320}, year = {1996}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {Seoul, Korea}, OPTmonth = {aug}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract = {Program slicing has many applications such as program debugging, testing, maintenance, and complexity measurement. This paper concerns the problem of slicing concurrent object-oriented programs that has not been addressed in the literatures until now. To solve this problem, we propose a new program dependence representation named the system dependence net (SDN), which extends previous program dependence representations to represent concurrent object-oriented programs. An SDN of a concurrent object-oriented program consists of a collection of procecdure dependence nets each representing a main procedure, a free standing procedure, or a method in a class of the program, and some additional arcs to represent direct dependences between a call and the called procedure/method and transitive interprocedural data dependences. We construt the SDN to represent not only object-orieted features but also concurrency issues in a concurrent object-oriented program. Once a concurrent object-oriented program is represented by its SDN, the slices of the program can be computed based on the SDN as a simple vertex reachability problem in the net.}, URL ={http://www.slab.csce.kyushu-u.ac.jp/~cheng/pub/COMPSAC96.ps}, OPTannote = {} } @InProceedings{Kri98, author = {Jens Krinke}, title = {Static Slicing of Threaded Programs}, booktitle = {Proc. ACM SIGPLAN/SIGFSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE'98) }, OPTcrossref = {}, OPTkey = {}, pages = {35-42}, year = {1998}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {Montreal, Canada}, OPTmonth = {jun}, OPTorganization = {}, OPTpublisher = {}, note = { ACM SIGPLAN Notices 33(7)}, abstract ={ Static program slicing is an established method for program understanding, debugging and testing. Until now, there was no slicing method for threaded programs which handles interference correctly. We present such a method which also calculates more precise static slices. This paper extends the well known structuresof the control flow graph and the program dependence graph for threaded programs with interference. This new technique does not require serialozation of threaded programs.}, URL ={ftp://ftp.jps.cs.tu-bs.de/pub/local/softtech/papers/paste-98.ps.gz}, OPTannote = {} } @InProceedings{Dem98, author = {C.Demartini and R.Iosif and R.Sisto}, title = {Modeling and Validation of Java Multithreading Applications using SPIN}, booktitle = {Proceedings of the 4th International SPIN Workshop}, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {1998}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract ={This paper presents some issues about the design and implementation of a concurrency analysis tool for deadlock detection on Java programs based on promela and SPIN. An abstract formal model expressed in Promela is generated from the Java source using the Java2Spin translator. Then the model is analyzed by SPIN and possible error traces are converted back to traces of Java statements and reported to the user. We carried out a set of experiments, to evaluate the extent to which this approach is feasible, and found that non-trivial Java programs can be successfully analyzed.}, URL ={http://netlib.bell-labs.com/netlibspin/ws98p23.ps.gz}, OPTannote = {} } @InProceedings{Mil98, author = {Lynette I.Millett and Tim Teitelbaum}, title = {Slicing Promela and its Applications to Model Checking, Simulation, and Protocol Understanding}, booktitle = {Proceedings of the 4th International SPIN Workshop}, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {1998}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract = {Static program slicing has been used effectively for a variety of applications ranging from debugging to program integration to software re-engineering. A program slice consists of the parts of a program that may affect or are affected by the value being computed at the point of interest. A slice,for sequential programs, is computed by examines how values at a particular program point are affected by synchronization, communication,and non-determinism(along with the traditional control and data dependence effects.) We are extending this work to slice the Promela programming language, used to specify protocols for the Spin model checker. Another application of slicing may be its usefulness in paring down protocol descriptions to just the pieces that affect particular points of interest (e.g. assertion statements,never claims, etc. in Promela). Model checking and simulation of the pared-down protocol may, in some cases, be much more efficient. We present progrsm slicing as a tool that, along with model checking and simulation techniques, can facilitate understanding and debugging of protocols.}, URL ={http://netlib.bell-labs.com/netlibspin/millet.ps.gz}, OPTannote = {} } @InProceedings{Tip96, author = {Frank Tip and Jong-Deok Choi and John Field and G. Ramalingam}, title = {Slicing Class Hierarchies in C++}, booktitle = {Proceedings of OOPSLA'96}, OPTcrossref = {}, OPTkey = {}, pages = {179-197}, year = {1996}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, abstract = {This paper describes an algorithm for slicing class hierarchies in C++ programs. Given a C++ class hierarchy (a collection of C++ classes and inheritance relations among them) and a program P the uses the hierarchy, the algorithm eliminates from the hierarchy those data memebers, member functions, classes, and inheritance relations that are unnecessary for ensuring that the semantics of P is mantained. Class slicing is expecially useful when the program P is generated from a large program P' by a statement slicing algorithm. Such an algorithm eliminate statements that are irrelevant to a set of slicing criteria --- program points of particular interest. There has been considerable previous work on statement slcing, and it will not be the concern of this paper. However, the combination of statement slicing and class slicing for C++ has two principal applications: First, class slicing can enhance statement slicing's utility in program debugging and understanding applications, by eliminating both executable and declarative program components irrelevant to the slicing criteria. Second, the combination of the two slicing algorithms can be used to decrease the space requirements of programs that do not use all the components of a class hierarchy. Such a situation is particularly common in programs that use class libraries.}, OPTnote = {}, URL ={http://www.research.ibm.com/people/t/tip/abstracts/ch-slicing-abstract.html}, OPTannote = {} } @InProceedings{Jacobs98, author = {Bart Jacobs and Joachim van den Berg and Maricke Huisman and Martijn van Berkum}, title = {Reasoning about Java Classes (Preliminary Report)}, booktitle = {Proceedings of OOPSLA'98}, OPTcrossref = {}, OPTkey = {}, pages = {329-340}, year = {1998}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, abstract ={We present the first result of a project called LOOP, on formal methods for the object-oriented language Java. It aims at verification of program properties, with support of modern tools. We use our own front-end tool (which is still partly under construction) for tarnslating Java classes into higher order logic, and a back-end theorem prover (namely PVS, developed at SRI) for reasoning. In several examples we demonstrate how non-trivial properties of Java programs and classes can be proven following this two-step approach.}, URL ={http://www.cs.jun.nl/~bart/PAPERS/OOPSLA98.ps.Z}, OPTnote = {}, OPTannote = {} } @InProceedings{DeF98, author = {Greg DeFouw and David Grove and Craig Chambers}, title = {Fast Interprocedural Class Analysis}, booktitle = {Proceedings of Principles of Programming Languages 1998}, OPTcrossref = {}, OPTkey = {}, pages = {222-236}, year = {1998}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {San Diego, CA}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, abstract ={Previous algoriths for interprocedural control flow analysis of higher-order and/or object-orinted languages have been described that perform propagation or constraint satisfaction and take $O(N^3)$ time (such as Shivers's 0-CFA and Heintze's set-based analysis), or unificaiotn and take $O(N\alpha (N,N))$ time (such as Steensgaard's pointer analysis), or optimistic reachability analysis and take $O(N)$ time (such as Bacon and Sweeney's Rapid Type Analysis). We describe a general parameterized analysis framework that integrates propagation-based and unification-based analysis primitives and optimistic reachability analysis, whose instances minimic these existing algorithms as well as several new algorithms taking $O(N), \ O(N\alpha(N,N)), \ O(N^2)$, and $O(N^2\alpha(N,N))$ time; our $O(N)$ and $O(N\alpha(N,N))$ algorithms produce more precise results than the previous algorithms with these complexities. We implemented our algorithm framework in the Vortex optimizing compiler; and we neasured the cost and benefit of these interprocedural analysis algorithms in practice on a collection of substantial Cecil and Java programs.}, URL ={ftp://ftp.cs.washington.edu/homes/chambers/popl98-fipca.ps.gz}, OPTnote = {}, OPTannote = {} } @TechReport{Clar99, author = {E.M. Clarke and M. Fujita and S.P. Rajan and T.Reps and S. Shankar and T. Teitelbaum}, title = {Program Slicing for Design Automation: An Automatic Technique for Speeding-up Hardware Design, Simulation, Testing, and Verification}, institution = {CMU}, year = {1999}, OPTkey = {}, OPTtype = {}, OPTnumber = {}, OPTaddress = {}, OPTmonth = {}, OPTnote = {}, abstract = {Program slicing is a static program analysis technique that allows an analust to automatically extract portions of programs relevant to the aspects being analyzed. This paper discusses a tool provides assistance in various hardware design, simulation, testing, and formal verification tasks, as described here.}, OPTannote = {} } @TechReport{Tip98, author = {Frank Tip and Chris Laffra and Peter F.Sweeney}, title = {Size Matters: Reducing the Size of Java Class File Archives}, institution = {IBM T.J. Watson Research Center}, year = {1998}, OPTkey = {}, type = {Research Report}, number = {RC 21321}, OPTaddress = {}, OPTmonth = {}, OPTnote = {}, abstract = {Java programs are routinely transmitted over low-bandwidth network connections as compressed class file archives(i.e.,zip files and jar files). The size of an archive has a direct impact in the time required to download a program, and therefore on browser response time for web pages that contain Java applets. Archive size also affects the initialization time required by Java virtual machines("class loading"). This paper is concerned with the use of compiler-optimization techniques and program trans-formations for reducing the size of archives. We implemented seversl optimizations in the context of Jax, an application extractor for Java, and evaluate their effectiveness on a set of realistic benchmarks ranging from 12 to 2,050 classes (the corresponding archives range from 13,312 to 5,710,539 bytes). We measured a reduction in archive size between 30.1% and 84.0%.}, URL ={http://www.research.ibm.com/people/t/tip/abstracts/jax-abstract.html}, OPTannote = {} } @InProceedings{Cen97, author = {Pietro Cenciarelli and Alexander Knapp and Bernhard Reus and Martin Wirsing}, title = {From Sequential to Multi-Threaded Java: An Event-Based Operational Semantics}, booktitle = {Algebraic Methodology and Software Technology}, OPTcrossref = {}, OPTkey = {}, year = {1997}, OPTkey = {}, pages = {75-90}, editor = {Johnson}, OPTvolume = { }, number = {1349}, series = {LNCS}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, publisher = {Springer-Verlag}, OPTnote = {}, abstract = {A structural operational semantics of a non trivial sublanguage of Java is presented. This language includes dynamic creation of objects, blocks, and synchronization of threads. First we introduce a simple operational description of the sequentail part of the language, where the memory is treated as an algebra with suitably axiomatized operations. Then, the interaction between threads via a shared memory is described in terms of structures, called ''event spaces'', whose well-formedness conditions formalize directly the rules given in the Java language specification. Event spaces are included in the operational judgements to develop the semantics of the full multi-threaded sublanguage, which is shown to extend the one for sequential java conservatively. The result allows sequential programs to be reasoned about in a simplified computational framework without loss of generality.}, URL = {http://www.pst.informatik.uni-muenchen.de/personen/cenciare/amast.ps}, OPTannote = {} } @InProceedings{Reus97, author = {Bernhard Reus and Alexander Knapp and Pietro Cenciarelli and Martin Wirsing}, title = {Verifying a Compiler Optimization for Multi-Threaded Java}, booktitle = {Recent Trends in Algebraic Development Techniques}, OPTcrossref = {}, OPTkey = {}, pages = {402-417}, year = {1997}, OPTeditor = {}, volume = {1376}, OPTnumber = {}, series = {LNCS}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, publisher = {Spring-Verlag}, OPTnote = {}, abstract = {The specification for the object-oriented concurrent language Java [3] is rather loose with respect to the interaction of shared memory and the local working memories of different threads. This allows maximal freedom in the language implementation. Such freedom is reflected in the semantics provided in [2], where threads-memory interation is formalized in terms of structures called event spaces. Two kinds of memories are described in the Java specification: a "normal" memory and a more liberal one, where values can sometimes be stored even before they are produced as resukts of computation. Here we compare two structural operational semantics of a sublanguage of Java modelling the two types of memory. The two semantics share the same set of operational rules but put different requirements (expressed as first order theories)on the notion of event space. We prove a result which is informally stated in [3]: the two semantics coincide for properly synchronized programs. This shows the applicability of a new technique for combining structural operational semantics and first order specification of process behaviour}, URL ={ftp://ftp.informatik.uni-muenchen.de/pub/local/pst/papers/reus/java/}, OPTannote = {} } @InProceedings{Lia98, author = {Donglin Liang and Mary Jean Harrold}, title = {Slicing Objects Using System Dependence Graphs}, booktitle = {Proceedings of the International Conference on Software Maintenance }, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {1998}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {nov}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract = {We present an SDG for object-oriented software that is more precise than previous representations and is more efficient to construct than previous approaches.The new SDG distinguishes fata members for different objects, provides a way to represent object parameters, represents the effects of polymorphism on parameters and parameter bindings, represents incomplete classes efficiently, and provides a way to represent class libraries. Based on this system dependence graph,we introduce the concept of object slicing and an algorithm to implement this concept.Object slicing enables the user to inspect the statements in the slice, object-by-object, and is helpful for debugging and impact analysis.}, URL ={http://www.cis.ohio-state.edu/~harrold/research/webpapers/icsm98-ooslicing.ps}, OPTannote = {} } @InProceedings{Lar96, author = {Loren Larsen and Mary Jean Harrold}, title = {Slicing Object-Oriented Software}, booktitle = {18th International Conference on Software Engineering}, OPTcrossref = {}, OPTkey = {}, pages = {495-505}, year = {1996}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {mar}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract = {We describe the construction of system dependence graphs for object-oriented software on which efficient slicing algorithms can be applied. We construct these system deoendence graphs for individual classes, groups of interacting classes, and complete object-oriented programs. For an incomplete system consisting of a single class or a number of interacting classes, we construct a procedure dependence graph that simulates all possible calls to public methods in the class. For a complete system, we construct a /rocedure dependence graph from the main program in the system. Using these system dependence graphs, we show how to conpute slices for individual classes, One advantage of our approach is that the system dependence graphs can be constructed incrementally because representations of classes can be reused. Another advantage of our approach is that slices can be computed for incomplete object-oriented programs such as classes or class libraries. We present our results for C++, but our techniques apply to other statically typed object-oriented languages such as Ada-95}, URL = {http://www.cis.ohio-state.edu/~ harrold/research/webpapers/icse96.ps}, OPTannote = {} } @InProceedings{Har94, author = {Mary Jean Harrold and Gregg Rothermel}, title = {Performing Data Flow Testing on Class}, booktitle = {Second ACM SIGSOFT Symposium on the Foundations of Software Engineering}, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {1994}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {dec}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract = {The basic unit of testing in an object-oriented program is a class. Although there has been much recent research in testing of classes, most of this work has focured on black-box approaches. However, since black-box testing techniques may not provide sufficient code coverage, they should be augmented with code-based or white-box techniques. Dataflow testing is a code-based testing technique that uses the dataflow relations in a program to guide the selection of tests. Existing dataflow testinf techniques can be applied both to individual methods in a class and to methods in a class that interact through messages, but these techniques do not consider the dataflow interactions that arise when users of a class invoke sequences of methods in an arbitrary order. We present a new approach to class testing that supports dataflow testing for dataflow interactions in a class. For individual methods in a class, and methods that send messages to other methods in the class, our technique is similar to existing dataflow testing techniques. For methods that are accessible outside the class, and can be called in any order by users of the class, we compute dataflow information, and use it to test possible interactions between these methods. The main benefit of our approach is that it facilitates dataflow testing for an entire class. By supporting dataflow testing of classes, we provide opportunities to find errors in classes that may not be uncovered by black-box testing. Our technique is also useful for determining which sequences of methods should be executed to test a class, even in the absence of a specification. Finally, as with other code-based testing techniques, a large portion of our technique can be automated.}, URL ={http://www.cis.ohio-state.edu/~harrold/research/webpapers/fse94.ps}, OPTannote = {} } @InProceedings{Cor98, author = {James C.Corbett}, title = {Using Shape Analysis to Reduce Finite-State Models of Concurrent Java Programs}, booktitle = {Proceedings of the International Symposium on Software Testing and Analysis}, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {1998}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {oct}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract ={Finite-state verification (e.g., model checking) provides a powerful means to detect concurrency errors, which are often subtle and difficult to reproduce. Nevertheless, widespread use of this technology by developers is unlikely until tools provide automated support for extracting the required finite-state models directly from program source. Unfortunately, the eynamic features of modern languages such as Java complicate the construction of compact finite-state models for verification. Inthis paper, we show how shape analysis, which has traditionally been used for computing alias information in optimizers, can be used to greatly reduce the size of finitstate models of concurrent Java prograjms by determining which heap-allocated variables are accessible only by a single thread, and which shared variables are prototype implementation. A prototype implementation of the teductions demonstrates their effectiveness.}, OPTannote = {} } @Article{Tip95, author = {Frank Tip}, title = {A Survey of Program Slicing Techniques}, journal = {Journal of Programming Languages}, year = {1995}, OPTkey = {}, volume = {3}, number = {3}, pages = {121-189}, month = {sep}, abstract ={A program slice consists of the parts of a program that(potentially) affect the values computed at some point of interest, referred to as a slicing criterion. The task of computing program slices is called program sliciing. The original definition of a program slice was presented by Weiser in 1979.Since then,various slightly different notions of program alices have been proposed, as well as a number of methods to compute them. An important distinction is thst between a static and a dynamic slice.The former notion is computed without making assumotions regarding a program' input, whereas the latter relies on some specific test case. Procedures, arbitrary control flow, composite datatypes and pointers, and interprocess communication each require a specific solution.We classify static and dynamic slicing methods for each of these features, and compare their accuracy and efficiency. Moreoverss ,the possibilities for combining solutions for different features are investigated. Wediscuss how compiler-optimization techniques can be used to obtain more accurate slices. The paper is concluded with an overview of the applications of program slicing, which include debugging, progtam integration, dataflow testing, and software maintenance.}, OPTnote = {}, URL ={ftp://ftp.cwi.nl/pub/CWIreports/AP/CS-R9438.ps.Z}, OPTannote = {} } @Book{JVM97, author = {Tim Lindholm and Frank Yellin}, ALTeditor = {}, title = {The Java Virtual Machine Specification}, publisher = {Addison-Wesley}, year = {1997}, OPTkey = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTedition = {}, OPTmonth = {}, OPTnote = {}, OPTannote = {} } @TechReport{Kri94, author = {Anand Krishnaswamy}, title = {Program Slicing: An Application of Object-oriented Program Dependency Graphs}, institution = {Dept. CS Clemson University}, year = {1994}, OPTkey = {}, OPTtype = {}, number = {Technical Reprot TR94-108}, OPTaddress = {}, OPTmonth = {}, OPTnote = {}, abstract = {A considerable amount of work has been done in the area of representing programs with single and multiple procedure bodies. A complete study of the latter requires both intra and interprocedural analysis. In the analysis of an object-oriented program, it is all the more important due to the existence of numerous classes and methods within the classes. Object-oriented design is based on the philoslphy of data encapsulation and controlled access to the encapsulated data. There are different representations available for object-oriented design. These representations do not give a complete picture of the prohrams thus restricting code analysis and preventing many testing techniques from using them. This paper discusses the issues involved in representing object-oriented programs. A representation based on the Program Dependency Graphs is designed. Different concepts of the paradigm are represented, including polymorphism, dynamic binding and the class inheritance hierarchy. Message exchanges between objects are also discussed and a more compact manner of representing parameter flow is presented. A second issue addressed in this paper is that of slicing in object-oriented programs. Determining an object-oriented slice is more complex than determining either an intraprocedural or interprocedural slice. It has been shown that Program Dependency Graphs are well suited for slicing procedural programs. A high level pseudocode algorithm is given, that demonstrates the applicability of the Object-oriented Program Dependency Graph for slicing object-oriented programs. Other applications based on this representation are also introduced.}, OPTannote = {} } @InProceedings{Bin96, author = {David W. Binkley and Keith Brian Gallagher}, title = {Program Slicing}, booktitle = {Advances in Computers}, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {1996}, editor = {Marvin Zelkowitz}, volume = {43}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, publisher = {Academic Press San Diego, CA.}, URL ={ http://www.cs.loyola.edu/~kbg/survey.ps}, OPTnote = {}, OPTannote = {} } @InProceedings{Har98, author = {Mary Jean Harrold and Gregg Rothermel and Saurabh Sinha}, title = {Computation of Interprocedural Control Dependence}, booktitle = {Proceedings of the ACM International Symposium on Testing and Analysis }, OPTcrossref = {}, OPTkey = {}, pages = {11-21}, year = {1998}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {mar}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract ={Program dependence information is useful for a variety of software testing and maintenance tasks. Properly defined, control and data dependencies can be used to identify semantic dependencies. To function effectively on whole programs, tools thst utilize dependence information require information about interprocedural dependencies: dependencies that exist because of interactions among procedures. Many techniques for computing data and control dependencies exist; however, in our search of the literature we find only one attempt to define and compute interprocedural control dependencies. Unfortunately, that approach can omit important control dependencies, and incorrectoy identifies control dependencies for a large class of programs. This paper presents a definition of interprocedural control dependence that supports the relationship of control and data dependence to semantic dependence, an efficient algorithm for calculating interprocedural control dependencies, and empirical results pbtained by our implementation of the algorithm.}, URL = {http://www.cis.ohio-state.edu/~harrold/research/webpapers/issta98.ps}, OPTannote = {} } @InProceedings{Harrold98, author = {Mary Jean Harrold and Ning Ci}, title = {Reuse-Driven Interprocedural Slicing}, booktitle = {The 20th International Conference on Software Engineering}, OPTcrossref = {}, OPTkey = {}, pages = {74-83}, year = {1998}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {apr}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract = {To manage the evolution of software systems effectively, software developers must understand software systems, identify and evaluate alternative modification strategies, implement appropriate modifications, and validate the correctness of the modifications. One analysis technique that assists in many of these activities is program slicing. To facilitate the application of slicing to large software systems, we adapted a control-flow-based interprocedural slicing algorithm so that it accounts for interprocedural control dependencies not recognized by other slicing algorithms, and reuses slicing information for improved efficiency. Our initial studies suggest that additional slice accuracy and slicing effciency may be achieved with our algorithm.}, URL = {http://www.cis.ohio-state.edu/~harrold/research/webpapers/icse98-slicing.ps}, OPTannote = {} } @TechReport{HarTR, author = {Mary Jean Harrold and Gregg Rothermel}, title = {Syntax-Directed Construction of Program Dependence Graphs}, institution = {Ohio State University}, year = {1995}, OPTkey = {}, OPTtype = {}, OPTnumber = {}, OPTaddress = {}, OPTmonth = {}, OPTnote = {}, abstract = {We present an algorithm that constructs program dependence graphs as a program is parsed. For programs that contain only structured transfers of control, our algorithm does not require explicit control flow or postdominator information to compute exact control dependencies. For programs that contain explicit transfers of control, our algorithm can determine whether these transfers of control are used in a structured way, and if so, compute control dependencies without explicit control flow or postdominator information. When transfers of control are ill-behaved, our algorithm adjusts the control dependence information computed during the parse, to obtain exact control dependencies. For many programs, our algorithm provides savings in time and memory, because it does not require prior computation of control flow or postdominator information However, our algorithm also calculates control flow information during the parse, and incorporates this information into the program dependence graphs that it constructs; the resulting graphs have a wider range of appoicability than graphs that do not contain this information.}, URL ={http://www.cis.ohio-state.edu/~harrold/research/webpapers/pdgtech.ps}, OPTannote = {} } @Article{Hor90, author = {Susan Horwitz and Thomas Reps and David Binkley}, title = {Interprocedural Slicing Using Dependence Graphs}, journal = {ACM Transaction on Programming Languages and Systems}, year = {1990}, OPTkey = {}, volume = {12}, number = {1}, pages = {26-60}, OPTmonth = {jan}, abstract ={The notion of a program slice, originally introduced by Mark Weiser, is useful in program debugging, autoatic parallelization, and program integration/ A slice of a program is taken with respect to a program point p and a variable x; the slice consists of all statements of the program that might affect the value of x at point p. This paper concerns the problem of interprocedural slicing-generating a slice of an entire program, where the slice crosses the boundaries of procedure calls. To solve this problem, we introduce a new kind of graph to represent programs, called a system dependence graph, which extends previous dependence representations to incorporate collections of procedures (with procedure calls) rather than just monolithic programs. Or main result is an algorithm for interprocedural slicing that usrs the new representation. (It should be noted that our work concerns a somewhat restricted kind of slice:Rather than permitting a program to be sliced with respect to program point p and an arbitrary variable, a slice must be taken with respect to a variable that is defined or used at p.) The chief difficulty in interprocedural slicing is correctly accounting for the calling context of a called procedure. To handle this problem, system dependence graphs include some data-dependence edfes that represent teansitive dependences due to the effects of procedure caoos, in addition to the conventional direct-dependence edges. These edges are constructed with the aid of an auxiliary structure that represents calling and parameter-linkage relationships. This structute takes the fotm of an attribute grammar. The step of computing the required transitive-dependence edges is reduced to the construction of the subordinate characteristic graphs for the grammar's nonterminals.}, OPTnote = {}, OPTannote = {} } @InProceedings{Ball93, author = {Thomas Ball and Susan Horwitz}, title = {Slicing Programs with Arbitrary Control Flow}, booktitle = {Proceedings of the 1st International Workshop on Automated and Algorithm Debugging}, OPTcrossref = {}, OPTkey = {}, pages = {206-222}, year = {1993}, OPTeditor = {}, volume = {749}, OPTnumber = {}, series = {LNCS}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract ={ Program slicing is a program transformation that is useful in program debugging, program maintenance, and other applications that involve understanding program behavior. Given a program point p and a set of variables V, the goal of slicing is to create a projection of the program (by eliminating some statements), such that the projection and the original program compute the same values for all variables in V at point p. This paper addresses the problem of slicing programs with arbitrary control flow. Previous slicing algorithms do not always form semantically correct program projections when applied to such programs. We give the first algorithm for slicing programs with complex control flow and a proof of its correctness. Our algorithm works for programs with complletely arbitrary control folw, including irreducibke control flow.}, URL ={http://www.cs.wisc.edu/wpis/papers/aadebug93.ps}, OPTannote = {} } @InProceedings{Gup94, author = {Rajiv Gupta and Mary Lou Soffa}, title = {A Framework for Partial Data Flow Analysis}, booktitle = {IEEE International Conference on Software Maintenance, }, OPTcrossref = {}, OPTkey = {}, pages = {4-13}, year = {1994}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = { Victoria, British Columbia,}, OPTmonth = {sep}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract = {Although daata flow analysis was first developed for use in compilers, its usefulness is now recognized in many software tools. Because of its compiler prigins, the computation of data flow for software tools is based on the traditional exhaustive data flow framework. However, although this framework is useful for computing data flow for compilers, it is not the most appropriate for software tools, particuularly those used in the maintenance atage. In maintenance, testing and debugging is typically performed in response to program changes. As such, the data flow required is demand driven from the changed program points. Rather than compute the data flow exhaustively using the traditional data flow framework, we present a framework for partial analysis. The framework includes a specification language enabling the specification of the demand driven data flow desired by a user. From the specification, a partial analysis algorithm is automatically generated using an L-attributed definition for the grammar of the specification languane. A specification of a demand driven data flow problem expresses characteristics that define the kind of traversal needed in the partial analysis and the type of dependencies to be captured. The partial analyses algorithms are efficient in that only as much of the program is analyzed as actually needed, thus reducing the time and space requirements over exhaustively computing the data flow information. The algorithms are shown to be useful when debugging and testing programs during maintenance.}, URL ={ttp://www.cs.pitt.edu/~gupta/research/SE/icsm94.ps}, OPTannote = {} } ######################################################################## @InProceedings{Due92, author = {E. Duesterwald and R. Gupta and M. Soffa}, title = {Distributed Slicing and Partial Re-execution for Distributed Programs}, booktitle = {Proceedings of 5h Workshop on Languages and Compilers fro Prallel Computing}, OPTcrossref = {}, OPTkey = {}, pages = {497-511}, year = {1992}, OPTeditor = {}, volume = {757}, OPTnumber = {}, series = {LNCS}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract = {We present a parallel algorithm to compute dynamic slices for distributed programs. Dynamic slices are used in debugging to re-execute only those statements of the original program that actually influenced an observed erroneous result. We introduce the notion of a Distributed Dependence Graph (DDG) as the graphical representation of the relevant dependencies among statements that arise during execution of a distributed program. Based on the DDG, we developed a parallel and fully distributed slicing algorithm, where each process determines its local section of the global slice. The potential for non-determinism in distributed programs is addressed by constructing a slice such that non-deterministic selections that were made during execution of the original program are reproduced when re-executing the program slice.}, OPTannote = {} } @TechReport{Nau98, author = {Gleb Naumovich and George S. Avrunin and Lori A. Clarke}, title = {Data Flow Analysis for Checking Properties of Concurrent Java Programs}, institution = {Department of Computer Science, University of Massachusetts at Amherst}, year = {1998}, OPTkey = {}, type = {TR}, number = {98-022}, OPTaddress = {}, OPTmonth = {apr}, abstract = {In this paper we show how the FLAVES data flow analysis technique,originally formulated for programs with the rendezvous model of concurrency can be applied to concurrent Java programs.The general approach of FLAVERS is based on modeling a concurrent program as a flow graph and using a dada flow analysis algorithm over this gtaph to check statically if a property holds on all executions of the program. The accuracy of this analysis can be improved by supplying additional information,represented as finite state automata, to the data flow analysis algorithm. In this paper we present a steaightforward approach for modeling Java programs that uses the accuracy improving mechanism to represent the possible communications among threads in Java programs, instead of representing them directly in the flow graph model. we also discuss a number of error-prone thread communication patterns that can arise in Java and describe how FLAVERS can be used to check for the presence of these.}, URL = {ftp://ftp.cs.umass.edu/pub/techrept/techreport/1998/UM-CS-1998-022.ps}, OPTnote = {}, OPTannote = {} } @Article{Duest97, author = {Evelyn Duesterwald and Rajiv Gupta and Mary Lou Soffa}, title = {A Practical Framework for Demand-Driven Interprocedural Data Flow Analysis}, journal = {ACM Transactions on Programming Languages and Systems}, year = {1997}, OPTkey = {}, volume = {19}, number = {6}, pages = {992-1030}, OPTmonth = {nov}, abstract = {The high cost and growing importance of interprocedural data flow analysis have led to an increased interest in demand-driven algorithms. In this article, we prsent a general framework for developing frmand-driven interprocedural data tlow analyzers and report our experience in evaluating the performance of this approach. A demand for data folw information is modeled as a set of queries. The framework includes a generic demand-driven algorithm that determines the response to a query by iteratively applying a system of query propagation rules. The propagation rules yield precise responses for the class of distributive finite data flow problems. We also describe a two-phase framework variation to accurately handle nondistributive problems. A performance evaluation of our demand-driven approach is presented for two data flow problems, namely, reaching-definitions and copy constant propagation. Our experiments show that demand-driven analysis performs well in practice, reducing both time and space requirements when compared with exhaustive analysis.}, OPTnote = {}, OPTannote = {}, URL ={http://www.cs.pitt.edu/~gupta/research/Comp/toplas98.ps} } @InProceedings{Corbett98, author = {James C.Corbett}, title = {Constructing Compact Models of Concurrent Java Programs}, booktitle = {Proceedings of the International Symposium on Software Testing and Analysis (ISSTA),}, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {1998}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {mar}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, URL ={http://www.ics.umass.edu/~corbett/tr/ics-tr-97-10.ps.gz}, abstract = {Finite-state verification technology (e.g., model checking) provides a powerful means to detect concurrency errors, which are often subtle and diffidult to reproduce. Nevertheless, widespread use of this technology by developers is unlikely until tools provide automated support for extracting the required finite-state models directly from program source. In this paper, we explore the extraction of compact concurrency models from Java code. In particular, we show how static pointer analysis, which has traditionally been used for computing alias information in optimizers, can be used to greatly reduce the size of finite-state model of concurrent Java programs.}, OPTannote = {} } @Article{Gall91, author = {K.B.Gallagher and J.R.Lyle}, title = {Using Program Slicing in Software Maintenance}, journal = {IEEE Transactions on Software Engineering}, year = {1991}, OPTkey = {}, volume = {17}, number = {8}, pages = {751-761}, OPTmonth = {aug}, abstract ={Program slicing,introduced by Weiser,is known to help programmers in understanding foreign code and in debugging. We apply program slicing to the maintenance problem by extcnding the notion of a program slice (that originally required both a variable and line number) to a decomposition slice,one that captures all computation on a given variable; i.e., is independent of line numbers. using the lattice of single variable decomposition slices, ordered by set inclusion, we demonstrate how to form a slice-based decomposition for programs. We are then able to delineate the effects of a proposed change by isolating those effects in a single component of the decomposition. this gives maintainers a straightforward technique for determining those statements and variables that may be modified in a component and those that may not. Using the decomposition, we provide a set of principles to prohibit changes that will interfere with unmodified components.These semantically consistent changes can then be merged back into the original program in linear time. Moreover, the maintainer can test the changes in the component with the assurance that there are no linkages into other components. Thus, decomposition slicing induces a new software maintenance process model that elimonates the need for regression testing.}, OPTnote = {}, OPTannote = {} } @InProceedings{Snel, author = {Gregor Snelting}, title = {Combining Slicing and Constraint Solving for Validation of Measurement Software}, booktitle = {Proceedings of Static Analysis Symposium 1996}, OPTcrossref = {}, OPTkey = {}, pages = {332-348}, year = {1996}, OPTeditor = {}, volume = {1145}, OPTnumber = {}, series = {LNCS}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, publisher = {Springer-Verlag}, OPTnote = {}, abstract = {We show how to combine program slicing and constraint solving in order to obtain better slice accuracy. The method is used in a program analysis tool for the validation of computer-controlled measurement systems. It will be used by the Physikalisch-Technische Bundesanstalt for verification of legally required calibration standards. The paper describes how to generate and simplify path conditions based on program slices. An example shows that the technique can indeed increase slice precision and reveal manipulations of the so-called calibration path. }, URL ={ftp://ftp.ips.cs.tu-bs.de/pub/local/softtech/papers/slice.ps.gz}, OPTannote = {} } @Article{Bink93, author = {David Binkley}, title = {Precise Executable Interprocedural Slices}, journal = {ACM Letters on Programming Languages and Systems (LOPLAS)}, year = {1993}, OPTkey = {}, volume = {2}, number = {1-4}, pages = {31-45}, OPTmonth = {}, abstract ={The notion of a program slice, originally introduced by Mark Weiser, is useful in program debugging,automatic paralllelization, program integration, and software maintenance. A slice of a program is taken with respect to a program point p and a variable x; the slice consists of all statements of the program that might affect the value of x at point p. An interprocedural slice is a slice of an entire program, where the slice crosses the boundaries of procedure calls. Weiser's original interprocedural slicing algorithm produces imprecise slices that are executable programs. A recent algorithm developed by Horwitz, Reps, and Binkley produces more precise (smaller) slices by more accurately identifying those statements that might affect the values of x at point p. These slices,however, are not executable. An extension to their algorithm that produces more precise executable interprocedural slices is described together with. a proof of correctness for the new algorithm.}, OPTnote = {}, OPTannote = {} } @Article{Wei84, author = {Mark Weiser}, title = {Program Slicing}, journal = {IEEE Transaction on Software Engineering}, year = {1984}, OPTkey = {}, volume = {10}, number = {4}, pages = {352-357}, OPTmonth = {}, OPTnote = {}, abstract = {Abstract-Program slicing is a method for automatically decomposing programs by analyzing their data flow and control flow. Starting from a subset of a program's behavior, slicing reduces that program to a minimal form which still produces that behavior. The reduced program,called a "slice," is an independent program guaranteed to represent faithfully the original program wothin the domain of the domain of the specified subset of behavior. Some properties of slices are presented. In particular, finding statement-minimal slices is in general unsolvable, but using data flow analysis is sufficient to find approximate slices. Potential applications include automatic slicing tools for debuggung and parallel processing of slices.}, OPTannote = {} } @InProceedings{Stef, author = {Bernhard Steffen}, title = {Property-Oriented Expansion}, booktitle = {SAS/ALP/PLILP'96}, journal ={LNCS}, OPTcrossref = {}, OPTkey = {}, pages = {22-41}, year = {1996}, OPTeditor = {}, volume = {1145}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {sep}, OPTorganization = {}, publisher = {Springer-Verlag}, OPTannote = {}, abstract ={The paper develops a framework for property-oriented expansion, Which is much more powerful than the state of the art (motion-based) approaches, supports the combination of transformation, and is open to automatic generation by means of aynthesis. The power of our method comes at the price of an exponential worst case complexity, which, however, hardly shows up in practice:usually the algorithm behaves very moderately and provides results, which are essentially of the same size as the argument program. Power and limitations of property-oriented expansion are illustrated by means of algorithms, which are unique in eliminating all partial redundancies and all partially dead code.}, note = {Proc. Int. Static Analysis Symposium (SAS'96),} } @Article{Lam84, author = {Simon S.Lam and A. Udaya Shankar}, title = {Protocol Verification via Projections}, journal = {IEEE Transactions on Software Engineering}, year = {1984}, OPTkey = {}, volume = {10}, number = {4}, OPTpages = {325-342}, OPTmonth = {jul}, abstract ={The method of projections is a new approach to reduce the complexity of analyzing nontrivial communication protocols. A protocol systim consists of a network of protocol entities and communication channels. Protocol entities interact by exchanging messages through channels;messages in transit may be lost, duplicated as well as reordered. Our method is intended for protocols with several distinguishable functions. We show how to construct image protocols for each function. An image protocol is specified just like a real protocol. An image protocol system is said to be faithful if it preserves all safety and liceness properties of the original protocol system concerning the projected function. An image protocol is smaller than the original protocol and can typically be more easily analyzed. Two protocol examples are employed herein to illustrate our method. An applicaion of this method to verify a version of the high-level data link control(HDLC) protocol is described in a companion paper.}, OPTnote = {}, OPTannote = {} } @InProceedings{Dema97, author = {Claudio Demartini and Riccardo Sisto}, title = {Supporting the Development of Multithreaded and Distributed Applications in Java}, booktitle = {Workshop on Models, Formalisms and Methods for Object-Oriented Distributed Computing}, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {1997}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract = {This paper introduces an ongoing project addressed at the provision of formal design tools to be integrated into development environments for the Java language. In particular, we focus on two such tools; a static analyzer of concurrency properties, and a formalism for the design of large, complex concurrent and distributed applications. The two techniques are introduced, and a brief description of each of them is provided, along with a discussion of the problems involved.}, OPTannote = {} } @InProceedings{Ste98, author = {Christoph Steindl}, title = {Program Slicing}, booktitle = {8th ECOOP Workshop for PhD Students in Object-Oriented Programming}, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {1998}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, abstract = {The concept of static program slicing was first introduced by Weiser. Ottenstein et al. indicated that an intraprocedural slice can be found in linear time by traversing a suitable graph representation of the program referred to as the program dependence graph(PDG). Horwitz et al. introduced algorithms to construct interprocedural slices by extending the program dependence graph to a supergraph of the PDG referred to as the system dependence graph(SDG). This extension captures the calling context of procedures. In a previous paper, we demonstrated that a parse-tree-based SDG provides us with"smaller" and therefore more precise slices than a statement-based SDG. Furthermore, we described extensions to the SDG in order to handle particular constructs in a language that is a subset of ANSI C. In this paper, we will describe a new method for the calculation of transitive dependences and therefore build a SDG that does require neither the calculation of the GMOD and GREF sets nor the construction of a linkage grammar and the corresponding subordinate characteristic graphs of the linkage grammar's nonterminals. Additionally, we illustrate the versatility of the SDG as an internal program representation by briefly prosenting a tool that we have developed that permits slicing, dicing, and ripple analyzing in addition to other software engineering activities to be performed on programs written in a suvset of ANSI C. This report is an extension of our previous report published in December 1991}, URL = {http://www.ssw.uni-linz.ac.at/pub/Reports/Report11.ps.Z}, OPTnote = {}, OPTannote = {} } @InProceedings{Ste98a, author = {Christoph Steindl}, title = { Intermodular Slicing of Object-Oriented Programs}, booktitle = {International Conference on Compiler Construction (CC'98) }, OPTcrossref = {}, OPTkey = {}, pages = {264-278}, year = {1998}, OPTeditor = {}, volume = {1383}, OPTnumber = {}, series = {LNCS}, OPTaddress = {Lisbon, Portugal}, OPTmonth = {mar}, OPTorganization = {}, publisher = {Springer-Verlag}, abstract ={We describe a program slicing tool for object-oriented programs. Program slicing [Wei84] uses control flow and data flow information to visualise dependences and assist the programmer in debugging and in program understanding. Object-oriented programs exploit features like dynamic binding which complicate interprocedural alias analysis. Two distinctive features of our Slicer are the support for intermodular slicing and the usage of user-feedback during the computation of data flow information. To cope with the problem of alias analysis in the presence of function pointers (which is NP-hard [ZhR94]), we decided to first use a conservative approach leading to less precise data flow information, but then use the user's expertise to restrict the effects of dynamic binding at polymorphic call sites to get more precise solutions which should still be safe. }, URL ={http://www.ssw.uni-linz.ac.at/Staff/CS/cd_public/slicing/intermodular.ps.Z}, OPTnote = {}, OPTannote = {} } @InProceedings{Ste97, author = {Christoph Steindl}, title = {Program Slicing for Large Systems}, booktitle = {Proc. 5th International Conference on Re-Technologies for Information Systems, ReTIS`97 }, OPTcrossref = {}, OPTkey = {}, pages = {131-143}, year = {1997}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, abstract ={We describe a program slicing tool for large systems which are built of modules. Two distinctive features of our Slicer are the support for slicing large systems (intermodular slicing) and the usage of user-feedback during the computation of data flow information (combining static and dynamic information, yielding semi-dynamic slices). }, URL ={http://www.ssw.uni-linz.ac.at/Staff/CS/cd_public/slicing/ReTIS97/ReTIS97.ps.Z}, OPTnote = {}, OPTannote = {} } @InProceedings{Col98, author = {C.Colby and P.Godefroid and L.J.Jagadeesan}, title = {Automatically Closing Open Reactive Programs}, booktitle = {Proceedings of 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation}, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {1998}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {jun}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract = {We study in this paper the problem of analyzing implementations of open systems--systems in which only some of the components are present. We present an algorithm for automatically closing an open concurrent reactive system with its most generao environment,i.e., the environment that can provide any input at any time to the system. The result is a nondeterministic closed (i.e., self-executable) system which can exhibit all the possiboe reactive behaviors of the original open system. These tehaviors can then be analyzed using VeriSoft, an existing tool for systematically exploring the state spaces of closed systems composed of multiple (possibly nondeterministic) processes executing arbitrary code. We have implemented the techniques inteoduced in this paper in a prototype tool for automatically closing open programs written in the C programming language. We discuss preliminary experimental results obtained with a large telephone-switching software application developed at Lucent Technologies.}, OPTannote = {} } @InProceedings{Gro97, author = {David Grove and Greg DeFouw and Jeffrey Dean and Craig Chambers}, title = {Call Graph Construction in Object-Oriented Languages}, booktitle = {OOPSLA'97}, OPTcrossref = {}, OPTkey = {}, OPTpages = {}, year = {1997}, OPTeditor = {}, OPTvolume = {}, OPTnumber = {}, OPTseries = {}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, OPTpublisher = {}, OPTnote = {}, abstract ={Interprocedural analyses enable optimizing compilers to more preciselu model the effects of non-inlined orocedure calls, potentially resulting in substantial increases in application performance. Applying interprocedural analysis to programs written in object-priented or functional languages is complicated by the difficulty of constructing an accurate program call graph. This paper presents a parameterized algorithmic framework for call graph construction in the presence of message sends and/or firstclass functions. We use this framework to describe and to implement a number of well-known and new algorithms. We then empirically assess these algorithms by applying them to a suite of medium-sized programs written in Cecil and Java, reporting pn the relative cost of the analyses, the relative precision of the consteucted call graphs, and the impact of this precision on the effectiveness pf a number of interprocedural optimizations.}, OPTannote = {} } @InProceedings{Cat98, author = {Thierry Cattel}, title = {Modeling and Verification of sC++ Applications}, booktitle = {LNCS}, OPTcrossref = {}, OPTkey = {}, pages = {232-246}, year = {1998}, OPTeditor = {}, volume = {1384}, OPTnumber = {}, OPTseries = {LNCS}, OPTaddress = {}, OPTmonth = {}, OPTorganization = {}, publisher = {Springer-Verlag}, OPTnote = {}, abstract = {This paper presents a means to model and verify concurrent applications written in sC++. sC++ is an extension of C++ that adds concurrency to the language by unifying the object and task concepts into a single one, the active object. The management of active objects is the same as the management of usual C++ passive objects. The difference is that active objects have their own behaviour and that they may either accept method calls or call other object'methods. They are also capable to await simultaneously several non deterministic events including timers expiration. We show how to systematically model sC++ programs into Promela, a formal language supported by SPIN, a powerful and widely available model-checker. We present a classical example of a concurrent problem and give details about a tool that automatically produces the model from a program, verifies it and allows its debugging.}, OPTannote = {} }