Automated Metamorphic Testing Project

In this project, we seek to automate "metamorphic testing" of applications, particularly those without test oracles (i.e., for which you cannot know the correct output for arbitrary input, such as machine learning apps).

Metamorphic testing is designed as a general technique for creating follow-up test cases based on existing ones, particularly those that have not revealed any failure, in order to try to find uncovered flaws. Instead of being an approach for test case selection, it is a methodology of reusing input test data to create additional test cases whose outputs can be predicted. In metamorphic testing, if input x produces an output f(x), the function’s metamorphic properties can then be used to guide the creation of a transformation function t, which can then be applied to the input to produce t(x); this transformation then allows us to predict the output f(t(x)), based on the (already known) value of f(x). If the output is not as expected, then a defect must exist. Of course, this can only show the existence of defects and cannot demonstrate their absence, since the correct output cannot be known in advance (and even if the outputs are as expected, both could be incorrect), but metamorphic testing provides a powerful technique to reveal defects in such non-testable programs by use of a built-in pseudo-oracle.

Our initial work evaluated the feasibility of applying metamorphic testing to machine learning apps, resulting in a paper published at SEKE 2008 in which we categorized six types of metamorphic properties that such applications may have.

We then created a tool called Corduroy to automate the process by allowing developers to specify individual functions' metamorphic properties using the specification language JML; these properties could then be checked using JML Runtime Assertion Checking. This yielded a paper that was presented at ICST 2009. We further developed a technique called Metamorphic Runtime Checking, and an implementation framework called Columbus, that are described in a tech report.

For system-level testing, we developed a tool called Amsterdam and an approach called Automated Metamorphic System Testing. This allows for checking of the application's metamorphic properties at runtime, using the real input from actual executions. However, the checks are conducted in parallel (for performance reasons), and any side effects are hidden from the user. Amsterdam was presented at ISSTA 2009; the paper is available here.

We have recently begun looking into applying metamorphic testing to the domain of discrete event simulation, and are in particular considering how to address non-deterministic applications.

This fall, we intend to investigate the following research questions:

• Can the "metamorphic properties" of a function or program be detected via code analysis? This could possibly be done via static techniques (treating the code as text and looking for trends) or dynamic techniques (observing the execution of the code and hypothesizing its properties).
• For what application domains is the approach most suitable? We have done extensive investigation of applying the technique to machine learning programs, but can it be used in other domains, such as optimization or simulation?
• How can the approach be applied to non-deterministic applications? Statistical and heuristic approaches have been suggested; how can these be improved?

Faculty
  Prof. Gail Kaiser, kaiser [at] cs.columbia.edu

Graduate Students
  Chris Murphy, cmurphy [at] cs.columbia.edu

Former Members
  Lifeng Hu, lh2342 [at] columbia.edu
  Kenny Shen, ks2555 [at] columbia.edu
  Sahar Hasan, sh2503 [at] columbia.edu