During software development, the sooner a developer learns how code changes affect program analysis results, the more helpful that analysis is. Manually invoking an analysis may interrupt the developer's workflow or cause a delay before the developer learns the implications of the change. A better approach is continuous analysis tools that always provide up-to-date results. We present Codebase Replication, a technique that eases the implementation of continuous analysis tools by converting an existing offline analysis into an IDE-integrated, continuous tool with two desirable properties: isolation and currency. Codebase Replication creates and keeps in sync a copy of the developer's codebase. The analysis runs on the copy codebase without disturbing the developer and without being disturbed by the developer's changes. We developed Solstice, an open-source, publicly-available Eclipse plug-in that implements Codebase Replication. Solstice has less than 2.5 milliseconds overhead for most common developer actions. We used Solstice to implement four Eclipse-integrated continuous analysis tools based on the offline versions of FindBugs, PMD, data race detection, and unit testing. Each conversion required on average 710 LoC and 20 hours of implementation effort. Case studies indicate that Solstice-based continuous analysis tools are intuitive and easy-to-use.

In a test suite, all the test cases should be independent: no test should affect any other test’s result, and running the tests in any order should produce the same test results. Techniques such as test prioritization generally assume that the tests in a suite are independent. Test dependence is a little-studied phenomenon. This paper presents five results related to test dependence.

Developers use analysis tools to help write, debug, and understand software systems under development. A developer's change to the system source code may affect analysis results. Typically, to learn those effects, the developer must explicitly initiate the analysis. This may interrupt the developer's workflow and/or the delay until the developer learns the implications of the change. The situation is even worse for impure analyses — ones that modify the code on which it runs — because such analyses block the developer from working on the code.

SUMMARY Our knowledge of how to solve software engineering problems is increasingly being encapsulated in tools. These tools are at their strongest when they operate in a pre‐existing integrated development environment (IDE). This approach allows integration with existing elements such as compilers, debuggers, profilers, visualizers, and numerous other development and, often, runtime tools. Tools and environments to increase software quality and productivity have always been an important aspect of software engineering. A plug‐in is a modern way for incrementally adding new tools into existing environments. However, building tools as plug‐ins can be challenging. How do they interact with the core environment? How do they interact with one another ‐ especially since each developer may choose a different set of plug‐ins? How can we share tools across different, and future, core development environments?

No abstract available.

Conflicts among developers' inconsistent copies of a shared project arise in collaborative development and can slow progress and decrease quality. Identifying and resolving such conflicts early can help. Identifying situations which may lead to conflicts can prevent some conflicts altogether. By studying nine open-source systems totaling 3.4 million lines of code, we establish that conflicts are frequent, persistent, and appear not only as overlapping textual edits but also as subsequent build and test failures. Motivated by this finding, we develop a speculative analysis technique that uses previously unexploited information from version control operations to precisely diagnose important classes of conflicts. Then, we design and implement Crystal, a publicly available tool that helps developers identify, manage, and prevent conflicts. Crystal uses speculative analysis to make concrete advice unobtrusively available to developers.

Programmers often need to reason about how a program evolved between two or more program versions. Reasoning about program changes is challenging as there is a significant gap between how programmers think about changes and how existing program differencing tools represent such changes. For example, even though modification of a locking protocol is conceptually simple and systematic at a code level, diff extracts scattered text additions and deletions per file. To enable programmers to reason about program differences at a high level, this paper proposes a rule-based program differencing approach that automatically discovers and represents systematic changes as logic rules. To demonstrate the viability of this approach, we instantiated this approach at two different abstraction levels in Java: first at the level of application programming interface (API) names and signatures, and second at the level of code elements (e.g., types, methods, and fields) and structural dependences (e.g., method-calls, field-accesses, and subtyping relationships). The benefit of this approach is demonstrated through its application to several open source projects as well as a focus group study with professional software engineers from a large e-commerce company.

Modern integrated development environments (IDEs) offer recommendations to aid development, such as auto-completions, refactorings, and fixes for compilation errors. Recommendations for each code location are typically computed independently of the other locations. We propose that an IDE should consider the whole codebase, not just the local context, before offering recommendations for a particular location. We demonstrate the potential benefits of our technique by presenting four concrete scenarios in which the Eclipse IDE fails to provide proper Quick Fixes at relevant locations, even though it offers those fixes at other locations. We describe a technique that can augment an existing IDE's recommendations to account for non-local information. For example, when some compilation errors depend on others, our technique helps the developer decide which errors to resolve first.

Modern integrated development environments make recommendations and automate common tasks, such as refactorings, auto-completions, and error corrections. However, these tools present little or no information about the consequences of the recommended changes. For example, a rename refactoring may: modify the source code without changing program semantics; modify the source code and (incorrectly) change program semantics; modify the source code and (incorrectly) create compilation errors; show a name collision warning and require developer input; or show an error and not change the source code. Having to compute the consequences of a recommendation -- either mentally or by making source code changes -- puts an extra burden on the developers. This paper aims to reduce this burden with a technique that informs developers of the consequences of code transformations. Using Eclipse Quick Fix as a domain, we describe a plug-in, Quick Fix Scout, that computes the consequences of Quick Fix recommendations. In our experiments, developers completed compilation-error removal tasks 10% faster when using Quick Fix Scout than Quick Fix, although the sample size was not large enough to show statistical significance.

No abstract available.

Our knowledge as to how to solve software engineering problems is increasingly being encapsulated in tools. These tools are at their strongest when they operate in a pre-existing development environment that can provide integration with existing elements such as compilers, debuggers, profilers and visualizers. The first Workshop on Developing Tools as Plug-ins is a new forum in which to addresses research, ongoing work, ideas, concepts, and critical questions related to the engineering of software tools and plug-ins.

Developers evolve a software system by changing the program source code, by modifying its context by updating libraries or changing its configuration, and by improving its test suite. Any of these changes can cause differences in program behaviour. In general, program paths may appear or disappear between executions of two subsequent versions of a system. Some of these behavioural differences are expected by a developer; for example, executing new program paths is often precisely what is intended when adding a new test. Other behavioural differences may or may not be expected or benign. For example, changing an XML configuration file may cause a previously-executed path to disappear, which may or may not be expected and could be problematic. Furthermore, the degree to which a behavioural change might be problematic may only become apparent over time as the new behaviour interacts with other changes.

Developers modify their systems by changing source code, updating test suites, and altering their system's execution context. When they make these modifications, they have an understanding of the behavioural changes they expect to happen when the system is executed; when the system does not conform to their expectations, developers try to ensure their modification did not introduce some unexpected or undesirable behavioural change. We present an approach that integrates with existing continuous integration systems to help developers identify situations whereby their changes may have introduced unexpected behavioural consequences. In this research demonstration, we show how our approach can help developers identify and investigate unanticipated behavioural changes.

Collaborative development can be hampered when conflicts arise because developers have inconsistent copies of a shared project. We present an approach to help developers identify and resolve conflicts early, before those conflicts become severe and before relevant changes fade away in the developers' memories. This paper presents three results.

During collaborative development, individual developers can create conflicts in their copies of the code. Such conflicting edits are frequent in practice, and resolving them can be costly. We present Crystal, a tool that proactively examines developers' code and precisely identifies and reports on textual, compilation, and behavioral conflicts. When conflicts are present, Crystal enables developers to resolve them more quickly, and therefore at a lesser cost. When conflicts are absent, Crystal increases the developers' confidence that it is safe to merge their code. Crystal uses an unobtrusive interface to deliver pertinent information about conflicts. It informs developers about actions that would address the conflicts and about people with whom they should communicate.

We describe twinning and its applications to adapting programs to alternative APIs. Twinning is a simple technique that allows programmers to specify a class of program changes, in the form of a mapping, without modifying the target program directly. Using twinning, programmers can specify changes that transition a program from using one API to using an alternative API.

No abstract available.

Software engineers often inspect program differences when reviewing others' code changes, when writing check-in comments, or when determining why a program behaves differently from expected behavior after modification. Program differencing tools that support these tasks are limited in their ability to group related code changes or to detect potential inconsistencies in those changes. To overcome these limitations and to complement existing approaches, we built Logical Structural Diff (LSdiff), a tool that infers systematic structural differences as logic rules. LSdiff notes anomalies from systematic changes as exceptions to the logic rules. We conducted a focus group study with professional software engineers in a large E-commerce company; we also compared LSdiff's results with textual differences and with structural differences without rules. Our evaluation suggests that LSdiff complements existing differencing tools by grouping code changes that form systematic change patterns regardless of their distribution throughout the code, and its ability to discover anomalies shows promise in detecting inconsistent changes.

No abstract available.

No abstract available.

No abstract available.

No abstract available.

Mapping code elements in one version of a program to corresponding code elements in another version is a fundamental building block for many software engineering tools. Existing tools that match code elements or identify structural changes - refactorings and API changes - between two versions of a program have two limitations that we overcome. First, existing tools cannot easily disambiguate among many potential matches or refactoring candidates. Second, it is difficult to use these tools' results for various software engineering tasks due to an unstructured representation of results. To overcome these limitations, our approach represents structural changes as a set of high-level change rules, automatically infers likely change rules and determines method-level matches based on the rules. By applying our tool to several open source projects, we show that our tool identifies matches that are difficult to find using other approaches and produces more concise results than other approaches. Our representation can serve as a better basis for other software engineering tools.

No abstract available.

No abstract available.

No abstract available.

David Notkin is the Bradley Professor of Computer Science & Engineering at the University of Washington, where he has been on the faculty since 1984, serving as department chair from 2001-2006. He received his Sc.B. from Brown University, and his Ph.D. from Carnegie Mellon University. His teaching and research interests are in software engineering, with a particular focus in software evolution understanding why software is so hard and expensive to change and in reducing those difficulties. Notkin has held visiting faculty positions at Tokyo Institute of Technology and Osaka University, and spent four months as a visiting researcher at IBM's Haifa Research Laboratory. Notkin was awarded an NSF Presidential Young Investigator Award in 1988 and was named an ACM Fellow in 1998. In 2000, he received the University of Washington Distinguished Graduate Mentor Award. He has served as an associate editor of the ACM Transactions on Software Engineering and Metholodogy and on IEEE Transactions on Software Engineering. He was program co-chair for the 17th International Conference on Software Engineering and program chair for the 1st ACM SIGSOFT Symposium on the Foundations of Software Engineering. He has over a dozen Ph.D. students who are active in research, education, and service.

Aspect-oriented software development is gaining popularity with the adoption of languages such as AspectJ. Testing is an important part in any software development, including aspect-oriented development. To automate generation of unit tests for AspectJ programs, we can apply the existing tools that automate generation of unit tests for Java programs. However, these tools can generate a large number of test inputs, and manually inspecting the behavior of the software on all these inputs is time consuming. We propose Raspect, a framework for detecting redundant unit tests for AspectJ programs. We introduce three levels of units in AspectJ programs: advised methods, advice, and intertype methods. We show how to detect at each level redundant test that does not exercise new behavior. Our approach selects only non-redundant tests from the automatically generated test suites, thus allowing the developer to spend less time in inspecting this reduced set of tests. We have implemented Raspect and applied it on 12 subjects taken from a variety of sources; our experience shows that Raspect can effectively reduce the size of generated test suites for inspecting AspectJ programs

Developers often create common tests and special tests, which exercise common behaviors and special behaviors of the class under test, respectively. Although manually created tests are valuable, developers often overlook some special or even common tests. We have developed a new approach for automatically identifying special and common unit tests for a class without requiring any specification. Given a class, we automatically generate test inputs and identify common and special tests among the generated tests. Developers can inspect these identified tests and use them to augment existing tests. Our approach is based on statistical algebraic abstractions, program properties (in the form of algebraic specifications) dynamically inferred based on a set of predefined abstraction templates. We use statistical algebraic abstractions to characterize program behaviors and identify special and common tests. Our initial experience has shown that a relatively small number of common and special tests can be identified among a large number of generated tests and these identified tests expose common and special behaviors that deserve developers' attention.

It has been broadly assumed that code clones are inherently bad and that eliminating clones by refactoring would solve the problems of code clones. To investigate the validity of this assumption, we developed a formal definition of clone evolution and built a clone genealogy tool that automatically extracts the history of code clones from a source code repository. Using our tool we extracted clone genealogy information for two Java open source projects and analyzed their evolution. Our study contradicts some conventional wisdom about clones. In particular, refactoring may not always improve software with respect to clones for two reasons. First, many code clones exist in the system for only a short time; extensive refactoring of such short-lived clones may not be worthwhile if they are likely diverge from one another very soon. Second, many clones, especially long-lived clones that have changed consistently with other elements in the same group, are not easily refactorable due to programming language limitations. These insights show that refactoring will not help in dealing with some types of clones and open up opportunities for complementary clone maintenance tools that target these other classes of clones.

Comparing behaviors of program versions has become an important task in software maintenance and regression testing. Black-box program outputs have been used to characterize program behaviors and they are compared over program versions in traditional regression testing. Program spectra have recently been proposed to characterize a program's behavior inside the black box. Comparing program spectra of program versions offers insights into the internal behavioral differences between versions. In this paper, we present a new class of program spectra, value spectra, that enriches the existing program spectra family. We compare the value spectra of a program's old version and new version to detect internal behavioral deviations in the new version. We use a deviation-propagation call tree to present the deviation details. Based on the deviation-propagation call tree, we propose two heuristics to locate deviation roots, which are program locations that trigger the behavioral deviations. We also use path spectra (previously proposed program spectra) to approximate the program states in value spectra. We then similarly compare path spectra to detect behavioral deviations and locate deviation roots in the new version. We have conducted an experiment on eight C programs to evaluate our spectra-comparison approach. The results show that both value-spectra-comparison and path-spectra-comparison approaches can effectively expose program behavioral differences between program versions even when their program outputs are the same, and our value-spectra-comparison approach reports deviation roots with high accuracy for most programs.

Comparing behaviors of program versions has become an important task in software maintenance and regression testing. Traditional regression testing strongly focuses on black-box comparison of program outputs. Program spectra have recently been proposed to characterize a program's behavior inside the black box. Comparing program spectra of program versions offers insights into the internal behavior differences between versions. We present a new class of program spectra, value spectra, which enriches the existing program spectra family. We compare the value spectra of an old version and a new version to detect internal behavior deviations in the new version. We use a deviation-propagation call tree to present the deviation details. Based on the deviation-propagation call tree, we propose two heuristics to locate deviation roots, which are program locations that trigger the behavior deviations. We have conducted an experiment on seven C programs to evaluate our approach. The results show that our approach can effectively expose program behavior differences between versions even when their program outputs are the same, and our approach reports deviation roots with high accuracy for most programs.

Unit testing, a common step in software development, presents a challenge. When produced manually, unit test suites are often insufficient to identify defects. The main alternative is to use one of a variety of automatic unit test generation tools: these are able to produce and execute a large number of test inputs that extensively exercise the unit under test. However, without a priori specifications, developers need to manually verify the outputs of these test executions, which is generally impractical. To reduce this cost, unit test selection techniques may be used to help select a subset of automatically generated test inputs. Then developers can verify their outputs, equip them with test oracles, and put them into the existing test suite. In this paper, we present the operational violation approach for unit test selection, a black-box approach without requiring a priori specifications. The approach dynamically generates operational abstractions from executions of the existing unit test suite. Any automatically generated tests violating the operational abstractions are identified as candidates for selection. In addition, these operational abstractions can guide test generation tools to produce better tests. To experiment dynamic approach, we integrated the use of Daikon (a dynamic invariant detection tool) and Jtest (a commercial Java unit testing tool). An experiment is conducted to assess this approach.

Software architecture describes the structure of a system, enabling more effective design, program understanding, and formal analysis. However, existing approaches decouple implementation code from architecture, allowing inconsistencies, causing confusion, violating architectural properties, and inhibiting software evolution. ArchJava is an extension to Java that seamlessly unifies software architecture with implementation, ensuring that the implementation conforms to architectural constraints. A case study applying ArchJava to a circuit-design application suggests that ArchJava can express architectural structure effectively within an implementation, and that it can aid in program understanding and software evolution.

The field of program analysis has made significant improvements recently, but still faces some major obstacles. In this talk I argue that considering analysis as applying longitudinally across the multitude of versions created during a program's lifetime -rather than to a given instance of a program - shows significant promise in overcoming some of these obstacles. I focus on identifying a set of opportunities that arise when this shift in outlook is taken.Most program analysis techniques have focused on questions of the form Does program P satisfy a given property A? or What program points in P satisfy a given property A? Type-checking is the classic example of the first form, while lexical, syntactic, and semantic analyses are examples of the second form. The key point (with respect to this talk) is that a single program P is being analyzed.Some analyses expand this view and explicitly consider a pair of programs, P and P', where P' represents a modified version of P. Test selection and prioritization techniques are among the best examples of this approach: the idea is to analyze the delta between P and P', and to use that information to determine which test cases must be re-run (for test selection) or should be re-run (for test prioritization). (There are dozens of results in these areas; Harrold et al.'s empirical study is one recent example of test selection [1], and the recent work at Microsoft Research is an example of test prioritization [2].There are at least three ways in which a longitudinal approach could improve analysis.Second, we can use previously computed information to better inform analysis on a newer version. One recent example of this is the work by Kim and Porter that uses historical information about the application of tests of a set of versions as a basis for test prioritization algorithms [3].Third, we can imagine applying otherwise intractable analyses over the lifetime of (multiple versions of) a program, as opposed to the (much more limited) time available to analyze a specific version. In essence, there is an opportunity to compute the analysis in stages, with the goal of completing the analysis by specific important points in the program lifetime (e.g., external releases). Work on vertical staging of analyses for runtime compilation is one place to look for ideas and techniques for this kind of horizontal staging [4].The traditional view of software evolution says that (to accommodate needed change) program structure degrades and program size increases [5][6]; this in turn tends to increase the difficult of analysis. I propose here some opportunities for viewing time and change as potential benefits with respect to analysis, rather than as roadblocks. This provides potential for significantly improving software dependability over time.

This is the first empirical study of the use of the C macro preprocessor, Cpp. To determine how the preprocessor is used in practice, this paper analyzes 26 packages comprising 1.4 million lines of publicly available C code. We determine the incidence of C preprocessor usage-whether in macro definitions, macro uses, or dependences upon macros-that is complex, potentially problematic, or inexpressible in terms of other C or C++ language features. We taxonomize these various aspects of preprocessor use and particularly note data that are material to the development of tools for C or C++, including translating from C to C++ to reduce preprocessor usage. Our results show that, while most Cpp usage follows fairly simple patterns, an effective program analysis tool must address the preprocessor. The intimate connection between the C programming language and Cpp, and Cpp's unstructured transformations of token streams often hinder both programmer understanding of C programs and tools built to engineer C programs, such as compilers, debuggers, call graph extractors, and translators. Most tools make no attempt to analyze macro usage, but simply preprocess their input, which results in a number of negative consequences; an analysis that takes Cpp into account is preferable, but building such tools requires an understanding of actual usage. Differences between the semantics of Cpp and those of C can lead to subtle bugs stemming from the use of the preprocessor, but there are no previous reports of the prevalence of such errors. Use of C++ can reduce some preprocessor usage, but such usage has not been previously measured. Our data and analyses shed light on these issues and others related to practical understanding or manipulation of real C programs. The results are of interest to language designers, tool writers, programmers, and software engineers.

Program refactoring-transforming a program to improve readability, structure, performance, abstraction, maintainability, or other features-is not applied in practice as much as might be desired. One deterrent is the cost of detecting candidates for refactoring and of choosing the appropriate refactoring transformation. This paper demonstrates the feasibility of automatically finding places in the program that are candidates for specific refactorings. The approach uses program invariants: when a particular pattern of invariant relationships appears at a program point, a specific refactoring is applicable. Since most programs lack explicit invariants, an invariant detection tool called Daikon is used to infer the required invariants. We developed an invariant pattern matcher for several common refactorings and applied it to an existing Java code base. Numerous refactorings were detected, and one of the developers of the code base assessed their efficacy.

Symbolic model checking based on binary decision diagrams is a powerful formal verification technique for reactive systems. In this paper, we present various optimizations for improving the time and space efficiency of symbolic modal checking for systems specified as statecharts. We used these techniques in our analyses of the models of a collision avoidance system and a fault-tolerant electrical power distribution (EPD) system, both used on commercial aircraft. The techniques together reduce the time and space requirements by orders of magnitude, making feasible some analysis that was previously intractable. We also elaborate on the results of verifying the EPD model. The analysis disclosed subtle modeling and logical flaws not found by simulation.

Explicitly stated program invariants can help programmers by identifying program properties that must be preserved when modifying code. In practice, however, these invariants are usually implicit. An alternative to expecting programmers to fully annotate code with invariants is to automatically infer likely invariants from the program itself. This research focuses on dynamic techniques for discovering invariants from execution traces. This article reports three results. First, it describes techniques for dynamically discovering invariants, along with an implementation, named Daikon, that embodies these techniques. Second, it reports on the application of Daikon to two sets of target programs. In programs from Gries's work (1981) on program derivation, the system rediscovered predefined invariants. In a C program lacking explicit invariants, the system discovered invariants that assisted a software evolution task. These experiments demonstrate that, at least for small programs, invariant inference is both accurate and useful. Third, it analyzes scalability issues, such as invariant detection runtime and accuracy, as functions of test suites and program points instrumented.

The artifacts constituting a software system often drift apart over time. We have developed the software reflexion model technique to help engineers perform various software engineering tasks by exploiting, rather than removing, the drift between design and implementation. More specifically, the technique helps an engineer compare artifacts by summarizing where one artifact (such as a design) is consistent with and inconsistent with another artifact (such as source). The technique can be applied to help a software engineer evolve a structural mental model of a system to the point that it is "good enough" to be used for reasoning about a task at hand. The software reflexion model technique has been applied to support a variety of tasks, including design conformance, change assessment, and an experimental reengineering of the million-lines-of-code Microsoft Excel product. We provide a formal characterization of the reflexion model technique, discuss practical aspects of the approach, relate experiences of applying the approach and tools, and place the technique into the context of related work.

Explicitly stated program invariants can help programmers by characterizing certain aspects of program execution and identifying program properties that must be preserved when modifying code. In practice, these invariants are usually absent from code. An alternative to expecting programmers to annotate code with invariants is to automatically infer invariants from the program itself. This talk describes dynamic techniques for discovering invariants from execution traces; the essential idea is to look for patterns in and relationships among variable values over a set of executions. An implementation has indicated that the approach is both effective -- successfully rediscovering formal specifications -- and useful --discovering invariants that assisted a software evolution task. The talk will also discuss, both in terms of invariant detection and also in more general terms, issues related to the potential synergy between static and dynamic analysis techniques.

Explicitly stated program invariants can help programmers by characterizing certain aspects of program execution and identifying program properties that must be preserved when modifying code. Unfortunately, these invariants are usually absent from code. Previous work showed how to dynamically detect invariants from program traces by looking for patterns in and relationships among variable values. A prototype implementation, Daikon, accurately recovered invariants from formally-specified programs, and the invariants it detected in other programs assisted programmers in a software evolution task. However, Daikon suffered from reporting too many invariants, many of which were not useful, and also failed to report some desired invariants.

Analyses of C source code usually ignore the C preprocessor because of its complexity. Instead, these analyses either define their own approximate parser or scanner, or else they require that their input already be preprocessed. Neither approach is entirely satisfactory: the first gives up accuracy (or incurs large implementation costs), while the second loses the preprocessor-based abstractions. We describe a framework that permits analyses to be expressed in terms of both preprocessing and parsing actions, allowing the implementer to focus on the analysis. We discuss an implementation of such a framework that embeds a C preprocessor, a parser, and a Perl interpreter for the action ‘hooks’. Many common software engineering analyses can be written surprisingly easily using our implementation, replacing numerous ad-hoc tools. The framework's integration of the preprocessor and the parser further enables some analyses that otherwise would be especially difficult to perform. Copyright © 2000 John Wiley & Sons, Ltd.

Article Free Access Share on Decoupling synchronization from local control for efficient symbolic model checking of statecharts Authors: William Chan Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, Washington Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WashingtonView Profile , Richard J. Anderson Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, Washington Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WashingtonView Profile , Paul Beame Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, Washington Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WashingtonView Profile , David H. Jones The Boeing Company, Seattle, Washington The Boeing Company, Seattle, WashingtonView Profile , David Notkin Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, Washington Department of Computer Science and Engineering, University of Washington, Box 352350, Seattle, WashingtonView Profile , William E. Warner The Boeing Company, Seattle, Washington The Boeing Company, Seattle, WashingtonView Profile Authors Info & Claims ICSE '99: Proceedings of the 21st international conference on Software engineeringMay 1999 Pages 142–151https://doi.org/10.1145/302405.302460Online:16 May 1999Publication History 13citation235DownloadsMetricsTotal Citations13Total Downloads235Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Dynamically discovering likely program invariants to support program evolution Authors: Michael D. Ernst Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle WA Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle WAView Profile , Jake Cockrell Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle WA Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle WAView Profile , William G. Griswold Dept. of Computer Science & Engineering, University of California San Diego, 0114, La Jolla, CA Dept. of Computer Science & Engineering, University of California San Diego, 0114, La Jolla, CAView Profile , David Notkin Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle WA Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle WAView Profile Authors Info & Claims ICSE '99: Proceedings of the 21st international conference on Software engineeringMay 1999 Pages 213–224https://doi.org/10.1145/302405.302467Published:16 May 1999Publication History 249citation1,521DownloadsMetricsTotal Citations249Total Downloads1,521Last 12 Months208Last 6 weeks71 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Comparing and contrasting a set of software libraries is useful for reuse related activities such as selecting a library from among several candidates or porting an application from one library to another.The current state of the art in assessing libraries relies on qualitative methods.To reduce costs and/or assess a large collection of libraries, automation is necessary.Although there are tools that help a developer examine an individual library in terms of architecture, style, etc., we know of no tools that help the developer directly compare several libraries.With existing tools, the user must manually integrate the knowledge learned about each library.Automation to help developers directly compare and contrast libraries requires matching of similar components (such as classes and functions) across libraries.This is different than the traditional component retrieval problem in which components are returned that best match a user's query.Rather, we need to find those components that are similar across the libraries under consideration.In this paper, we show how this kind of matching can be done.

No abstract available.

No abstract available.

We present various techniques for improving the time and space efficiency of symbolic model checking for system requirements specified as synchronous finite state machines. We used these techniques in our analysis of the system requirements specification of TCAS II, a complex aircraft collision avoidance system. They together reduce the time and space complexities by orders of magnitude, making feasible some analysis that was previously intractable. The TCAS II requirements were written in RSML, a dialect of state-charts.

The authors present a tool-based approach that examines how example programs reuse a particular library. The approach can facilitate reuse by: (1) guiding the developer towards important library classes of general utility; (2) guiding the developer towards library classes particularly useful for a specific application domain; and (3) providing access to the relevant source code in each example for further inspection. The approach is supported by CodeWeb, a reuse tool they have built for C++ and Java libraries.

Implicit invocation [SN92, GN91] has become an important architectural style for large-scale system design and evolution. This paper addresses the lack of specification and verification formalisms for such systems. Based on standard notions from process algebra and trace semantics, we define a formal computational model for implicit invocation. A verification methodology is presented that supports linear time temporal logic and compositional reasoning. First, the entire system is partioned into groups of components (methods) that behave independently. Then, local properties are proved for each of the groups. A precise description of the cause and the effect of an event supports this step. Using local correctness, independence of groups, and properties of the delivery of events, we infer the desired property of the overall system. Two detailed examples illustrate the use of our framework.

Abstract. Implicit invocation [SuN92, GaN91] has become an important architectural style for large-scale system design and evolution. This paper addresses the lack of specification and verification formalisms for such systems. A formal computational model for implicit invocation is presented. We develop a verification framework for implicit invocation that is based on Jones' rely/guarantee reasoning for concurrent systems [Jon83, Stø91]. The application of the framework is illustrated with several examples. The merits and limitations of the rely/guarantee paradigm in the context of implicit invocation systems are also discussed.

Informally, a call graph represents calls between entities in a given program. The call graphs that compilers compute to determine the applicability of an optimization must typically be conservative: a call may be omitted only if it can never occur in any execution of the program. Numerous software engineering tools also extract call graphs with the expectation that they will help software engineers increase their understanding of a program. The requirements placed on software engineering tools that compute call graphs are typically more relaxed than for compilers. For example, some false negatives—calls that can in fact take place in some execution of the program, but which are omitted from the call graph—may be acceptable, depending on the understanding task at hand. In this article, we empirically show a consequence of this spectrum of requirements by comparing the C call graphs extracted from three software systems (mapmaker, mosaic, and gcc) by nine tools (cflow, cawk, CIA, Field, GCT, Imagix, LSME, Mawk, and Rigiparse). A quantitative analysis of the call graphs extracted for each system shows considerable variation, a result that is counterintuitive to many experienced software engineers. A qualitative analysis of these results reveals a number of reasons for this variation: differing treatments of macros, function pointers, input formats, etc. The fundamental problem is not that variances among the graphs extracted by different tools exist, but that software engineers have little sense of the dimensions of approximation in any particular call graph. In this article, we describe and discuss the study, sketch a design space for static call graph extractors, and discuss the impact of our study on practitioners, tool developers, and researchers. Although this article considers only one kind of information, call graphs, many of the observations also apply to static extractors of other kinds of information, such as inheritance structures, file dependences, and references to global variables.

In parallel programming, the need to manage communication, load imbalance, and irregularities in the computation puts substantial demands on the programmer. Key properties of the architecture, such as the number of processors and the cost of communication, must be exploited to achieve good performance, but coding these properties directly into a program compromises the portability and flexibility of the code because significant changes are then needed to port or enhance the program. We describe a parallel programming model that supports the concise, independent description of key aspects of a parallel program-including data distribution, communication, and boundary conditions-without reference to machine idiosyncrasies. The independence of such components improves portability by allowing the components of a program to be tuned independently, and encourages reuse by supporting the composition of existing components. The isolation of architecture-sensitive aspects of a computation simplifies the task of porting programs to new platforms. Moreover, the model is effective in exploiting both data parallelism and functional parallelism. This paper provides programming examples, compares this work to related languages, and presents performance results.

In this paper, we present our experiences in using symbolic model checking to analyze a specification of a software system for aircraft collision avoidance. Symbolic model checking has been highly successful when applied to hardware systems. We are interested in whether model checking can be effectively applied to large software specifications. To investigate this, we translated a portion of the state-based system requirements specification of Traffic Alert and Collision Avoidance System II (TCAS II) into input to a symbolic model checker (SMV). We successfully used the symbolic model checker to analyze a number of properties of the system. We report on our experiences, describing our approach to translating the specification to the SMV language, explaining our methods for achieving acceptable performance, and giving a summary of the properties analyzed. Based on our experiences, we discuss the possibility of using model checking to aid specification development by iteratively applying the technique early in the development cycle. We consider the paper to be a data point for optimism about the potential for more widespread application of model checking to software systems.

Software libraries provide leverage largely because they are used by many applications. As Parnas (1972, 1979), Lampson (1984) and others have noted, stable interfaces to libraries isolate the application from changes in the libraries. That is, as long as there is no change in a library's syntax or semantics, applications can use updated libraries simply by importing and linking the new version. However, libraries are indeed changed from time to time and the tedious job of adapting the application source to the library interface changes becomes a burden to multitudes of programmers. The paper introduces an approach and a toolset intended to reduce these costs. Specifically, in the authors' approach, a library maintainer annotates changed functions with rules that are used to generate tools that will update the applications that use the updated libraries. Thus, in exchange for a small added amount of work by the library maintainer, costs for each application maintainer can be reduced. They present the basic approach, describe the tools that support the approach, and discuss the strengths and limitation of the approach.

In this paper we present a method of code implementation that works in conjunction with collaboration and responsibility based analysis modeling techniques to achieve better code reuse and resilience to change. Our approach maintains a closer mapping from responsibilities in the analysis model to entities in the implementation. In so doing, it leverages the features of flexible design and design reuse found in collaboration-based design models to provide similar adaptability and reuse in the implementation. Our approach requires no special development tools and uses only standard features available in the C++ language. In an earlier paper we described the basic mechanisms used by our approach and discussed its advantages in comparison to the framework approach. In this paper we show how our approach combines code and design reuse, describing specific techniques that can be used in the development of larger applications.

In this paper we present our results and experiences of using symbolic model checking to study the specification of an aircraft collision avoidance system. Symbolic model checking has been highly successful when applied to hardware systems. We are interested in the question of whether or not model checking techniques can be applied to large software specifications.To investigate this, we translated a portion of the finite-state requirements specification of TCAS II (Traffic Alert and Collision Avoidance System) into a form accepted by a model checker (SMV). We successfully used the model checker to investigate a number of dynamic properties of the system.We report on our experiences, describing our approach to translating the specification to the SMV language and our methods for achieving acceptable performance in model checking, and giving a summary of the properties that we were able to check. We consider the paper as a data point that provides reason for optimism about the potential for successful application of model checking to software systems. In addition, our experiences provide a basis for characterizing features that would be especially suitable for model checkers built specifically for analyzing software systems.The intent of this paper is to evaluate symbolic model checking of state-machine based specifications, not to evaluate the TCAS II specification. We used a preliminary version of the specification, the version 6.00, dated March, 1993, in our study. We did not have access to later versions, so we do not know if the properties identified here are present in later versions.

Parnas' seminal 1972 paper, "On the Criteria To Be Used in Decomposing Systems into Modules," identified simplifying change as a critical criterion for modularizing software. Successful designs are those in which a change can be accommodated by modifying a single module. There is a tacit assumption in most of the literature that once a change has been limited to a single module, the cost of making the change is essentially inconsequential. But modules have complexity of their own and are frequently large. Thus, making a change can be expensive, even if limited to a single module.We present a method of decomposing modules into smaller components for the purpose of supporting change. Although similar to the approach of modularizing programs described by Parnas, our approach is specific to decomposing modules. It is not intended to replace traditional high level modularization but rather to augment it with a second level of modularization where the standard of information hiding can be relaxed. The goal of the method is to make modules easier to change by decomposing them around smaller design decisions---ideally encoding only one design choice per submodule component.In this paper we show how submodule components can be used to address the issue of change. We also demonstrate how the ability to address change with submodule components is, to a large extent, independent of the design level modularization. Moreover, we show that, at least in some cases, by using submodule components the choice of high level modularization can itself be changed without having to rewrite large amounts of code.A method of implementation is presented using inheritance, parameterization, and static binding in a way that minimizes implementation dependencies between components. The method supports fine grained decomposition with flexible composability and almost no runtime overhead.

Software engineers maintaining an existing software system often depend on the mechanized extraction of information from system artifacts. Some useful kinds of information—source models—are well known: call graphs, file dependences, etc. Predicting every kind of source model that a software engineer may need is impossible. We have developed a lightweight approach for generating flexible and tolerant source model extractors from lexical specifications. The approach is lightweight in that the specifications are relatively small and easy to write. It is flexible in that there are few constraints on the kinds of artifacts from which source models are extracted (e.g., we can extract from source code, structured data files, documentation, etc.). It is tolerant in that there are few constraints on the condition of the artifacts. For example, we can extract from source that cannot necessarily be compiled. Our approach extended the kinds of source models that can be easily produced from lexical information while avoiding the constraints and brittleness of most parser-based approaches. We have developed tools to support this approach and applied the tools to the extraction of a number of different source models (file dependences, event interactions, call graphs) from a variety of system artifacts (C, C++, CLOS, Eiffel. TCL, structured data). We discuss our approach and describe its application to extract source models not available using existing systems; for example, we compute the implicitly-invokes relation over Field tools. We compare and contrast our approach to the conventional lexical and syntactic approaches of generating source models.

A software engineer's confidence in the profitability of a novel design technique depends to a significant degree on previous demonstrations of its profitability in practice. Trials of proposed techniques are thus of considerable value in providing factual bases for evaluation. We present our experience with a previously presented design approach as a basis for evaluating its promise and problems. Specifically, we report on our use of the mediator method to reconcile tight behavioral integration with ease of development and evolution of Prism, a system for planning radiation treatments for cancer patients. Prism is now in routine clinical use in several major research hospitals. Our work supports two claims. In comparison to more common design techniques, the mediator approach eases the development and evolution of integrated systems; and the method can be learned and used profitably by practising software engineers.

Reverse engineers depend on the automatic extract ion of information from source code.Some useful kinds of information+ource models-are wellknown: call graphs, file dependence, etc. Predicting every kind of source model that a reverse engi-

article Software reflexion models: bridging the gap between source and high-level models Share on Authors: Gail C. Murphy Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle WA Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle WAView Profile , David Notkin Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle WA Dept. of Computer Science & Engineering, University of Washington, Box 352350, Seattle WAView Profile , Kevin Sullivan Dept. of Computer Science, University of Virginia, Charlottesville VA Dept. of Computer Science, University of Virginia, Charlottesville VAView Profile Authors Info & Claims ACM SIGSOFT Software Engineering NotesVolume 20Issue 4Oct. 1995 pp 18–28https://doi.org/10.1145/222132.222136Published:01 October 1995 305citation2,070DownloadsMetricsTotal Citations305Total Downloads2,070Last 12 Months74Last 6 weeks13 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Maintaining the consistency of multiple program representations in a program manipulation tool is difficult. I describe a hybrid software architecture for a meaning-preserving program restructuring tool. Layering is the primary architectural paradigm, which successively provides increasingly integrated and unified abstract machines to implement the tool. However, layering does not provide adequate control over extensibility or the independence of components, so I also adopt the paradigm of keeping the key program abstractions separate throughout the layering, providing independent columns of abstract data types. A pair of columns is integrated by a mapping column that translates elements in one column's data type into related elements in the other column's data type. Thus, integration of function and separation of representation can be achieved simultaneously. This hybrid architecture was crucial in overcoming severe performance problems that became apparent once the basic tool was completed. By taking advantage of the independence of the columns and the special characteristics of meaning-preserving restructuring, it was possible to extend one representation column of the architecture to the uppermost layer to provide the required access for efficient updating without compromising independence. The cost of the extended architecture is that the upper layers are no longer as simple because they expose operations that only guarantee consistency under careful usage. However, the structural constraints of the hybrid architecture and the models for building the more complicated layers minimizes the negative impact of this tradeoff.>

The electronic encyclopedia exploratorium (E/sup 3/) is a vision of a future computer system-an electronic book describing how thing work. Typical articles in E/sup 3/ will describe such mechanisms as compression refrigerators, engines, telescopes, and mechanical linkages. Each article will provide simulations, three-dimensional animated graphics that the user can manipulate, laboratory areas that allow a user to modify the device or experiment with related artifacts, and a facility for asking questions and receiving customized, computer-generated English-language explanations. Some of the foundational technology is discussed, focusing on topics in artificial intelligence, graphics, and user interfaces. The initial prototype system and the technical lessons learned from it, as well as the second prototype currently under construction, are described.>

Maintenance tends to degrade the structure of software, ultimately making maintenance more costly. At times, then, it is worthwhile to manipulate the structure of a system to make changes easier. However, manual restructuring is an error-prone and expensive activity. By separating structural manipulations from other maintenance activities, the semantics of a system can be held constant by a tool, assuring that no errors are introduced by restructuring. To allow the maintenance team to focus on the aspects of restructuring and maintenance requiring human judgment, a transformation-based tool can be provided—based on a model that exploits preserving data flow dependence and control flow dependence—to automate the repetitive, error-prone, and computationally demanding aspects of restructuring. A set of automatable transformations is introduced; their impact on structure is described, and their usefulness is demonstrated in examples. A model to aid building meaning-preserving restructuring transformations is described, and its realization in a functioning prototype tool for restructuring Scheme programs is discussed.

The tension between software development costs and efficiency is especially high when considering parallel programs intended to run on a variety of architectures. In the domain of shared memory architectures and explicitly parallel programs, the authors have addressed this problem by defining a programming structure that eases the development of effectively portable programs. On each target multiprocessor, an effectively portable program runs almost as efficiently as a program fine-tuned for that machine. Additionally, its software development cost is close to that of a single program that is portable across the targets. Using this model, programs are defined in terms of data structure and partitioning-scheduling abstractions. Low software development cost is attained by writing source programs in terms of abstract interfaces and thereby requiring minimal modification to port; high performance is attained by matching (often dynamically) the interfaces to implementations that are most appropriate to the execution environment. The authors include results of a prototype used to evaluate the benefits and costs of this approach.>

Common software design approaches complicate both tool integration and software evolution when applied in the development of integrated environments. We illustrate this by tracing the evolution of three different designs for a simple integrated environment as representative changes are made to the requirements. We present an approach that eases integration and evolution by preserving tool independence in the face of integration. We design tool integration relationships as separate components called mediators , and we design tools to implicitly invoke mediators that integrate them. Mediators separate tools from each other, while implicit invocation allows tools to remain independent of mediators. To enable the use of our approach on a range of platforms, we provide a formalized model and requirements for implicit invocation mechanisms. We apply this model both to analyze existing mechanisms and in the design of a mechanism for C++.

The demands on a heterogeneous distributed file system are outlined, and the design and implementation of a prototype to meet these demands are described. This prototype, the heterogeneous computer systems file system (HFS), provides a network-wide file system supporting a simple record-oriented file model. Through this standard file model, the HFS provides global access to files stored locally in many different file types. The HFS is implemented as a set of HFS servers, one running on each participating host. Each HFS server extends its host's local file system by fielding remote requests for files stored locally, translating those requests into the appropriate local file system calls, and returning any information so obtained. This prototype HFS implementation is used on a network composed of VAX systems running Unix, Sun systems running 4.2BSD Unix, and Xerox Dandelions running XDE.>

It is shown how a communication abstraction called the port ensemble can simplify the handling of boundary conditions and the efficient porting of programs. A port ensemble provides an explicit interface between computation and communication descriptions, thus separating the communication structure from the details of local computation and from the compiler. Port ensembles structure ports, symbolic names to and from which process can write and read values. To simplify the expression of boundary conditions, ports can be bound not only to ports on other processors, but also to nonexistent neighbors (along the edge of the computation) using special objects that represent and implement constants, variables, and arbitrary functions. Port ensembles also provide direct access to the communication structure, which simplifies changing the structure to one appropriate for a new target architecture.>

Abstract Handling heterogeneity in computer systems without decreasing user productivity and without increasing development costs demands special software structures. This paper presents a flexible software structure that has been used to construct heterogeneous remote procedure call, naming, electronic mail, filing and remote computation services. This structure captures the heterogeneous aspects of a service in a set of abstract interfaces. Clients of the service are built in terms of the abstract interfaces, but one of multiple implementations of those interfaces, called proxies, is dynamically selected to satisfy the demands of heterogeneity.

The authors take efficient kernel-level support as a given, and study the performance implications of design alternatives one level up-in the stubs, which insulate the client and server from details about network communication. These alternatives represent a collection of approaches to achieving standard remote procedure call of semantics. Consideration is given to the performance implications of compiled vs. interpreted stubs, procedural vs. inline code for moving data to/from packet buffers, block copy vs. individual data item copy moving data to/from packet buffers, and the presence or absence of byte swapping.>

Interactive systems have goals and characteristics that differ from those of batch systems. These differences lead to a need for new techniques, methods, and tools for manipulating and constructing interactive systems. The difference in structure between batch and interactive systems. The difference is considered, focusing on the distinction between command decomposition and component decomposition. The possible ways of solving a problem using an interactive system using action paths, which account for the relatively unconstrained actions of interactive users, are described. It is shown that interactivity is not an inherent characteristic of a system but rather a characteristic that depends on the error profile of its users. The requirements that interaction places on the underlying implementation, specifically the need for incrementality and integration, are considered. The results are applied to several existing classes of systems.>

The ability to extend programs dynamically has clear advantages. However, providing efficient yet sufficiently flexible support for such capabilities system-wide presents significant challenges. We describe a design and implementation of an extension mechanism that depends heavily on interpretive techniques, including call arbitration, dynamic linking, and multilanguage extensions. We discuss these mechanisms in the context of our Extension Interpreter, which embodies our ideas and provides a framework for discussing the efficiency and generality of the implementation. Our current implementation runs under BSD UNIX 4.2 and 4.3 on VAXes and SUN workstations. Extensions can be written in both C and in Icon, demonstrating our ability to address problems both of compiled and interpreted languages.

A prototype implementation has been built as part of the Heterogeneous Computer Systems project at the University of Washington. This service supports RPC binding and other applications in our heterogeneous environment. Measurements of the performance of this prototype show that it is close to that of the underlying name services, due largely to the use of specialized caching techniques.

Different programming projects require different environments, but handcrafting a separate environment for each project is not economically feasible. Gandalf solves this problem by permitting environment designers to generate families of software development environments semiautomatically without excessive cost. Environments generated using Gandalf address programming environments, which help ease the programming process, as well as system development environments, which reduce the degree to which a software project is dependent on the good will of its members. Gandalf environments integrate programming and system development, permitting interactions not available in traditional environments. The paper covers the basic characteristics of Gandalf environments. The method used to generate these environments, the structure and function of several existing environments, and ongoing research on the project.