\section{Related Work}

This work builds on the idea behind delta-debugging \cite{DD}: test
cases should not contain extraneous information that is not needed to
reproduce failure (or some other behavior, as in more recent work
\cite{icst2014,stvrcausereduce}).  Delta-debugging and slicing
\cite{TCminim} are limited, generally, to producing subsets of the
original test case, not modifying parts of the test to obtain further
simplicity.  We extend this concept by also allowing modification or
re-ordering of actions in a test.  In some cases these changes
allows further reduction of the length of the test case as well.  Some
earlier work in bounded model checking modified counterexamples to use
numerically smaller values \cite{MakeMost} but otherwise did not aim
to simplify or normalize failures.

Normalization is in part motivated by the fuzzer taming \cite{PLDI13}
problem: determining how many distinct faults are present in a large
set of failing test cases.  This is a key problem in practical
application of automated testing.  Previous work on fuzzer taming
\cite{PLDI13} used delta-debugging to reduce some test cases to
syntactic duplicates.

Zhang \cite{SaiSimple} proposed an alternative approach to semantic
test simplification that, like our approach, is able to modify, rather
than simply remove, portions of a test.  However, because Zhang
operates directly over a fragment of the Java language, rather than
using an abstraction of test actions allowed, the set of rewrite
operations performed is highly restricted: no new methods can be
invoked, statements cannot be re-ordered, and no new values are used.
These restrictions limit the approach's ability to simplify tests and
make it inappropriate for  normalization, as opposed to simplification.  The approach also performs little
syntactic normalization: e.g., it does not even force a test to use
fixed variable names when variable name is irrelevant.  CReduce
\cite{CReduce} performs some simple normalization as part of a complex
test-case reduction scheme for C code, and the peephole-rewrite scheme
used in CReduce is also an inspiration for the approach taken by our
normalizer.

Work on producing readable tests \cite{Guava,Readable} is also
related, in that it aims to ``simplify'' tests in a way that goes
beyond measuring test length.  Work on readable tests is primarily
intended to assist debugging in  terms of human-factors, while our
normalization and generalization aims to increase the information
density of a test (potentially increasing readability as well), and to address the fuzzer taming problem.  The approaches are
completely orthogonal: our normalized tests could be altered to
improve readability by these methods.

The most closely related work to our generalization efforts is Pike's
SmartCheck \cite{SmartCheck}.  SmartCheck targets algebraic data in
Haskell, and offers an interesting alternative approach to reduction
and generalization.  Test case generalization is also akin to dynamic invariant generation,
in that it informs the user of invariants over a series of test
executions \cite{Daikon}.  The only other work we are aware of that is
similar to generalization concerns essential and accidental aspects of
model checking counterexamples \cite{FreeWill,MakeMost,SPIN03}.  