UW Software Engineering

Watch and share a video of the talk on Proactive Detection of Collaboration Conflicts, presented at ESEC FSE 2011. The video includes a Crystal demo.

http://www.cs.washington.edu/homes/brun/video/Brun11esecfse

“Proactive Detection of Collaboration Conflicts” (ESEC FSE 2011) is now available, as well as it’s accompanying tool demo paper titled “Crystal: Precise and Unobtrusive Conflict Warnings.”

Y. Brun, R. Holmes, M. D. Ernst, and D. Notkin, “Proactive Detection of Collaboration Conflicts“, In Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE11). Szeged, Hungary, September, 2011.

Y. Brun, R. Holmes, M. D. Ernst, and D. Notkin, “Crystal: Precise and Unobtrusive Conflict Warnings“, In Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering Tool Demonstration Track (ESEC/FSE11). Szeged, Hungary, September, 2011.

Abstract: 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.

First, a study of open-source systems establishes that conflicts are frequent, persistent, and appear not only as overlapping textual edits but also as subsequent build and test failures. The study spans nine open-source systems totaling 3.4 million lines of code; our conflict data is derived from 550,000 development versions of the systems.

Second, using previously-unexploited information, we precisely diagnose important classes of conflicts using the novel technique of speculative analysis over version control operations.

Third, we describe the design of Crystal, a publicly-available tool that uses speculative analysis to make concrete advice unobtrusively available to developers, helping them identify, manage, and prevent conflicts.

“Leveraging Existing Instrumentation to Automatically Infer Invariant-Constrained Models” (ESEC FSE 2011) is now available, as well as it’s accompanying tool demo paper titled “Synoptic: Studying Logged Behavior with Inferred Models.”

I. Beschastnikh, Y. Brun, S. Schneider, M. Sloan, and M. D. Ernst, “Leveraging Existing Instrumentation to Automatically Infer Invariant-Constrained Models“, In Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering (ESEC/FSE11). Szeged, Hungary, September, 2011.

I. Beschastnikh and J. Abrahamson and Y. Brun and M. D. Ernst, “Synoptic: Studying Logged Behavior with Inferred Models“, In Proceedings of the 8th Joint Meeting of the European Software Engineering Conference and ACM SIGSOFT Symposium on the Foundations of Software Engineering Tool Demonstration Track (ESEC/FSE11). Szeged, Hungary, September, 2011.

Abstract:  Computer systems are often difficult to debug and understand. A common way of gaining insight into system behavior is to inspect execution logs and documentation. Unfortunately, manual inspection of logs is an arduous process and documentation is often incomplete and out of sync with the implementation.

This paper presents Synoptic, a tool that helps developers by inferring a concise and accurate system model. Unlike most related work, Synoptic does not require developer-written scenarios, specifications, negative execution examples, or other complex user input. Synoptic processes the logs most systems already produce and requires developers only to specify a set of regular expressions for parsing the logs.

Synoptic has two unique features. First, the model it produces satisfies three kinds of temporal invariants mined from the logs, improving accuracy over related approaches. Second, Synoptic uses refinement and coarsening to explore the space of models. This improves model efficiency and precision, compared to using just one approach.

In this paper, we formally prove that Synoptic always produces a model that satisfies exactly the temporal invariants mined from the log, and we argue that it does so efficiently. We empirically evaluate Synoptic through two user experience studies, one with a developer of a large, real-world system and another with 45 students in a distributed systems course. Developers used Synoptic-generated models to verify known bugs, diagnose new bugs, and increase their confidence in the correctness of their systems. None of the developers in our evaluation had a background in formal methods but were able to easily use Synoptic and detect implementation bugs in as little as a few minutes.

Brian Burg received an Honorable Mention for the 2011 NSF Graduate Research Fellowship Program competition.

Congratulations, Brian!

“C3: An Experimental, Extensible, Reconfigurable Platform for HTML-based Applications” by Benjamin S. Lerner, Brian Burg, Herman Venter, and Wolfram Schulte has been accepted to USENIX WebApps 2011.

Abstract:

The common conception of a (client-side) web application is some collection of HTML, CSS and JavaScript (JS) that is hosted within a web browser and that interacts with the user in some non-trivial ways. The common conception of a web browser is a monolithic program that can render HTML, execute JS, and gives the user a portal to navigate the web. Both of these are misconceptions: nothing inherently confines webapps to a browser’s page- navigation idiom, and browsers can do far more than merely render content.

We present C3, an implementation of the HTML/CSS/JS platform designed for web client research and experimentation. C3’s typesafe, modular architecture lowers the barrier to webapp and browser research. Additionally, C3 explores the roles of extension mechanisms within the web platform for customization and research efforts, by introducing novel extension points and generalizing existing ones. We discuss and evaluate C3’s design decisions for flexibility, and provide examples for various extensions that we and others have built.

“Smart Redundancy for Distributed Computation” by Yuriy Brun, George Edwards, Jae young Bang, and Nenad Medvidovic has been accepted for publication at the 31st IEEE International Conference on Distributed Computing Systems (ICDCS 2011).

Abstract:
Many distributed software systems allow participation by large numbers of untrusted, potentially faulty components on an open network.  As faults are inevitable in this setting, these systems utilize redundancy and replication to achieve fault tolerance.  In this paper, we present a novel “smart” redundancy technique called iterative redundancy, which ensures efficient replication of computation and data given finite processing and storage resources, even when facing Byzantine faults.  Iterative redundancy is more efficient and more adaptive than comparable state-of-the-art techniques that operate in environments where the reliability of system resources is unknown.

We show how systems that solve computational problems using a network of independent nodes can benefit from iterative redundancy.  We present a formal analytical analysis and an empirical analysis, demonstrate iterative redundancy on a real-world volunteer-computing system, and compare it to existing methods.

“Building and using pluggable type-checkers” by Werner Dietl, Stephanie Dietzel, Michael D. Ernst, Kivanç Muşlu, and Todd Schiller. In ICSE’11, Proceedings of the 33rd International Conference on Software Engineering, (Waikiki, Hawaii, USA), May 25-27, 2011.

Abstract:

This paper describes practical experience writing and using pluggable type-checkers. A pluggable type-checker refines (strengthens) the built-in type system of a programming language. This permits programmers to detect and prevent, at compile time, defects that would otherwise have been manifested as run-time errors. The prevented defects may be generally applicable to all programs, such as null pointer dereferences. Or, an application-specific pluggable type system may be designed for a single application.

We have built and evaluated a series of pluggable type checkers on nearly 2.1 million lines of code, finding hundreds of bugs in the process. In addition to these studies, we observed 28 first-year computer science students use a checker to eliminate null pointer errors in their course projects.

Along with describing the checkers and characterizing the bugs we found, we report the insights we had throughout the process. Overall, we found that the type checkers were easy to write, easy for novices to productively use, and effective in finding real bugs and verifying program properties, even for widely tested and used open source projects.

Gail Murphy, a UW CSE alum, has just been named as an ACM Distinguished Scientist.  Way to go, Gail!

Details here.

Abstract:  Programmers usually modify a program intending to fix a bug or to add a new feature. While they often have a strong understanding of the actual changes they are making to a program, the dynamic effects of these changes on the run-time behavior of the program can be harder to comprehend. The approach helps developers identify when their changes to the source code and the changes in the consequent executable behavior are inconsistent: that is, the change in the source is not apparent in the behavior, or vice versa.

The approach identifies specific program elements and dependencies that likely account for the inconsistent nature of the change. Using a static and a dynamic dependence graph from each of two program versions, the dependences are partitioned according to their presence or absence in each of the four graphs. Particular partitions contain dependencies that are likely to represent inconsistent parts of a change; these partitions provide insight into the change that would be otherwise difficult to obtain.

The partitions allow distinctions to be made that cannot be made using the static dependence graphs alone, the dynamic dependence graphs alone, nor using a static and dynamic graph pair from a given version; much of the power of the approach arises because the cross-version variations in the dependence graphs are small, reducing information provided to the programmer. The intellectual merit includes empirical assessment over a broad set of programs and changes, ?value propositions? for using this information, applications of the approach, and use of the partitioning to augment conventional approaches to assessing software complexity.

The project addresses two categories of broader impacts: the people directly involved in the research, and the potential for the research to positively affect society through increased programmer productivity.

Details here.

Abstract: Unprecedented computational power is available from multi-core processors and cloud computing. To date, this power has been used primarily to make programs run faster. However, in many cases the bottleneck to solving users’ problems is in the challenge of creating the software, not in the time to run it. This project will apply computational power to the real bottleneck, providing developers with new types of feedback. As a key broader impact, the research will enable developers to create software more quickly, more cheaply, and with higher quality.
The key technical idea is to inform developers, in advance, of the consequences of their likely actions. The development environment speculates about developer actions, evaluates the effect of each action (on compilation, tests, version control conflicts, etc.), and unobtrusively makes this information available to the developer. By knowing which choices are good and which are bad, developers can avoid bad choices that cost time or reduce quality. The project’s intellectual merits include algorithms to quickly create and evaluate many possible developer actions, UI design for developer awareness, and evaluation of how increased awareness of contingent information, about possible actions, affects developers. This also leads toward an answer to the question: If developers had infinite processing power, what fundamental software engineering research problems would remain?