UW CSE at ISSTA

René Just and Michael Ernst of UW CSE, along with their colleague Gordon Fraser of the University of Sheffield, have been awarded an ACM Distinguished Paper award for their paper “Efficient mutation analysis by propagating and partitioning infected execution states”.  This paper will be presented on July 25 at ISSTA, the premier conference in software testing and analysis.  The paper speeds up mutation analysis by 40% over the previous state of the art.  Mutation analysis is widely used in testing research, because it is the most precise known approach to measure the quality of a test suite.  This is Michael Ernst's 6th ACM Distinguished Paper award, not to mention other best paper awards he has received.  The photo shows Ernst and Just flanking the conference chairs Corina Pasareanu and Darko Marinov.

UW CSE is well-represented elsewhere in the conference, with 2 other technical papers and 3 tool demos.  One other paper is “Empirically revisiting the test independence assumption” by Sai Zhang, Darioush Jalali, Jochen Wuttke, Kıvanç Muşlu, Wing Lam, Michael D. Ernst, and David Notkin, which shows how and when tests cases depend on one another, so that a test fails depending on what other test cases are run before it.  Another paper is “A type system for format strings” by Konstantin Weitz, Gene Kim, Siwakorn Srisakaokul, and Michael D. Ernst, which shows how to verify correct use of format routines such as printf.

ISSTA 2014 papers

My research group had 3 papers accepted to ISSTA, the International Symposium on Software Testing and Analysis.  Here are brief descriptions of them.

“Empirically revisiting the test independence assumption”

by Sai Zhang, Darioush Jalali, Jochen Wuttke, Kıvanç Muşlu, Wing Lam, Michael D. Ernst, and David Notkin.

Two tests are independent (non-interfering) if running one test does not change whether the other test fails or succeeds.  If tests are dependent, then reordering them (as in test prioritization or test selection) could cause a previously-passing test to suddenly start failing, even though the program has not changed.

Both practitioners and researchers generally ignore the problem of test dependence:  they assume that test cases are independent.  We developed presents algorithms and tools for detecting dependent tests.  Our paper shows that test dependence does occur in real-world test suites, and it shows that test dependence can cause both false alarms and failed alarms in prioritized (reordered) test suites.

You can also read the abstract.

“Efficient mutation analysis by propagating and partitioning infected execution states”

by René Just, Michael D. Ernst, and Gordon Fraser.
Abstract:

Given two test suites, mutation analysis ranks one of them as better than the other.  Mutation analysis is notoriously compute-intensive, because it runs many variants of the program over each test suite.  This paper reduces the cost of mutation analysis by 40%, by eliminating redundant executions that reveal no information.

The technique works by first running an instrumented version of the program over the test suite.  This pre-processing step more than pays for itself by enabling other executions to be skipped:

• mutated expressions that produce the same value as the original program expression did,
• mutanted expressions that produce a different value, but a containing expression produces the same value as it did in the original program, and
• different mutants that all compute the same value (all but one of which can be skipped).

You can also read the abstract.

“A type system for format strings”

by Konstantin Weitz, Gene Kim, Siwakorn Srisakaokul, and Michael D. Ernst.

Most programming languages support format strings, but their use is error-prone. Using the wrong format string syntax or passing the wrong number or type of arguments leads to unintelligible text output, program crashes, or security vulnerabilities.

We have designed and implemented a type system that indicates erroneous usage, or statically guarantees that calls to these APIs will never fail.  The annotation burden for the user of our type system is low, and it found over 100 bugs in open-source projects.

You can also read the abstract.

Reading the papers

The papers are not publicly available yet, because we are editing our submissions in response to suggestions from the referees.  (Whether or not a paper is accepted, it is always a pleasure to receive feedback from experts who have read your paper and thought about ways to improve the research.)  The camera-ready deadline is June 6.  In the meanwhile, if you are interested in a paper and are willing to provide feedback, I would be happy to send you a preprint; just ask.

ACM SIGSOFT Impact Paper Award

Jake Cockrell, Bill Griswold, David Notkin, and I received the 2013 SIGSOFT Impact Paper Award for our paper Dynamically Discovering Likely Program Invariants to Support Program Evolution, which appeared in ICSE '99.

The award citation reads:

This paper initiated a revolutionary and important line of research that is still very active and relevant today: extracting models of running software and reasoning about its behavior. The approach it defined has significantly influenced both the state of the art and the state of the practice. In addition, the paper described Daikon, a tool that implements this approach, and which continues to be vital and useful today, some 15 years later.

The award includes a $1000 honorarium, which we donated to the David Notkin Endowed Graduate Fellowship in Computer Science & Engineering.

This paper was the foundation of my PhD dissertation.

Later, a journal version of the paper was published in TSE in 2001.  If you read the journal version, feel free to skip sections 5-8, which are not as interesting as the other parts of the journal paper.

This work received other awards including being selected for expedited journal publication (this was the precursor to the ACM Distinguished Paper Award, which was introduced in 2002), honorable mention in the ACM doctoral dissertation competition (the first honorable mention that had been awarded in 7 years), and best software engineering dissertation of the prior three years (awarded at ICSM 2001).

However, I feel that a retrospective award such as the SIGSOFT Impact Paper Award is much more meaningful than any of those awards that were presented at the time of publication.  It's very difficult to determine the importance of a piece of research when it first appears.  The perspective of time reveals whether the paper was foundational or merely clever.

I tend to dislike best-paper awards (and proxy awards such as nomination or expedited journal publication), because they are so random and therefore not very meaningful.  (Before I offend my colleagues who are reading this, let me clarify that the randomness or meaninglessness applies to the times I have been so honored, at ICSE 1999, ICSE 2000, VMCAI 2003, ESEC/FSE 2003, ICSE 2004, ASE 2005, ISSTA 2006, ASE 2006, ICSE 2007, ESEC/FSE 2007, ASE 2007, ISSTA 2008, ISSTA 2009, ECOOP 2011, and ESEC/FSE 2011.  But the honors accorded to your papers, dear reader, were surely well-deserved recognition of research that is clearly better than any other research presented at that conference.)  That's why I don't generally list these on my webpages, for example.

Despite my opinion of how meaningful a best-paper award often is, I do support conferring them.  The reason is that these are useful to graduate students and to junior faculty members:  the awards buttress those young scientists' c.v.s and therefore their careers.

Talk video: "Software evolution then and now: the research of David Notkin"

On Friday, February 1, at an event honoring David Notkin, I gave a 30-minute talk that surveyed a few of his research contributions.

The talk video is available, for download or streaming, at http://www.cs.washington.edu/events/colloquia/search/details?id=1334

The title and abstract are as follows:


Software evolution then and now: the research of David Notkin
by Michael Ernst
February 1, 2013

Abstract:  Software engineering is a deep and important field that has been tremendously successful. David Notkin has contributed to that success during a distinguished career spanning three decades. This talk discusses a few of his research projects. For each project, the talk explains the problem and the solution. The talk highlights ways in which David Notkin's work has impacted not just other software engineering researchers, but also working programmers.

Responding to conference reviews

I have added a section "Responding to conference reviews" to my webpage about writing a technical paper.

An easier way to make exams

Recently, some of my colleagues bemoaned the effort of making up exams at the end of the term.  I wanted to share a trick that I have used, that makes creating exams much easier.  It might work for you too.

I work on exam questions throughout the term rather than waiting until the end.  A TA is assigned to each lecture, and is required to make up a couple of questions during or immediately after the lecture.  This way, we get ideas that pop into the TA's head but that might have been forgotten by the end of the term.  Another excellent source is student questions during class.  Likewise, we harvest common misperception and questions from office hours.  These often turn into excellent exam question as well, since they are topics that could confuse a student but that were covered in class.

More advice about creating an exam appears at http://homes.cs.washington.edu/~mernst/advice/exams.html

Don't scan your recommendation letters

Faculty are writing lots of recommendation letters right now.  One of my colleagues went to extra effort to print his letter, sign it, scan it, and then upload it.  Unfortunately, this was counterproductive.

If you are requested to provide a letter in PDF, provide the original PDF that was created by your word processor or typesetting program.  Don't scan the document, which makes it much harder to read.  You don't want eyestrain (or anything else) to lessen the impact of your letter.  You can either insert a PDF signature, or have just a typewritten signature; no one really cares whether your signature is on the letter.

Another irritation I have seen:  don't use "watermark" letterhead that puts a large, dim image (for example, of the university crest or logo) behind the text.  Some people apparently think this looks cool and sets their letter or institution apart (MIT CSAIL, I am looking at you), but in fact it makes the letter harder to read without impressing anyone.

More advice on writing a letter of recommendation appears at http://homes.cs.washington.edu/~mernst/advice/write-recommendation.html