L18.tex

\documentclass[11pt]{article}
\usepackage{listings}
\usepackage{tikz}
\usepackage{alltt}
\usepackage{hyperref}
\usepackage{url}
%\usepackage{algorithm2e}
\usetikzlibrary{arrows,automata,shapes}
\tikzstyle{block} = [rectangle, draw, fill=blue!20, 
    text width=5em, text centered, rounded corners, minimum height=2em]
\tikzstyle{bt} = [rectangle, draw, fill=blue!20, 
    text width=1em, text centered, rounded corners, minimum height=2em]

\newtheorem{defn}{Definition}
\newtheorem{crit}{Criterion}
\newcommand{\true}{\mbox{\sf true}}
\newcommand{\false}{\mbox{\sf false}}

\newcommand{\handout}[5]{
  \noindent
  \begin{center}
  \framebox{
    \vbox{
      \hbox to 5.78in { {\bf Software Testing, Quality Assurance and Maintenance } \hfill #2 }
      \vspace{4mm}
      \hbox to 5.78in { {\Large \hfill #5  \hfill} }
      \vspace{2mm}
      \hbox to 5.78in { {\em #3 \hfill #4} }
    }
  }
  \end{center}
  \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{#4}{Lecture #1}}
\topmargin 0pt
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.5in

\parindent 0in
\parskip 1.5ex
%\renewcommand{\baselinestretch}{1.25}

%\renewcommand{\baselinestretch}{1.25}
% http://gurmeet.net/2008/09/20/latex-tips-n-tricks-for-conference-papers/
\newcommand{\squishlist}{
 \begin{list}{$\bullet$}
  { \setlength{\itemsep}{0pt}
     \setlength{\parsep}{3pt}
     \setlength{\topsep}{3pt}
     \setlength{\partopsep}{0pt}
     \setlength{\leftmargin}{1.5em}
     \setlength{\labelwidth}{1em}
     \setlength{\labelsep}{0.5em} } }
\newcommand{\squishlisttwo}{
 \begin{list}{$\bullet$}
  { \setlength{\itemsep}{0pt}
     \setlength{\parsep}{0pt}
    \setlength{\topsep}{0pt}
    \setlength{\partopsep}{0pt}
    \setlength{\leftmargin}{2em}
    \setlength{\labelwidth}{1.5em}
    \setlength{\labelsep}{0.5em} } }
\newcommand{\squishend}{
  \end{list}  }
\begin{document}

\lecture{18 --- February 13, 2015}{Winter 2015}{Patrick Lam}{version 1}

\subsection*{Mutation Testing}
The second major way to use grammars in testing is mutation testing.
Strings are usually programs, but could also be inputs, especially for
testing based on invalid strings.  
%% Two kinds of strings:
%% \begin{itemize}
%% \item invalid strings
%% \item valid strings mutated from other valid strings
%% \end{itemize}

\begin{defn}
Ground string: a (valid) string belonging to the language of the grammar.
\end{defn}

\begin{defn}
Mutation Operator: a rule that specifies syntactic variations of
strings generated from a grammar.
\end{defn}

\begin{defn}
Mutant: the result of one application of a mutation operator to a 
ground string.
\end{defn}

Mutants may be generated either by modifying existing strings or 
by changing a string while it is being generated.

It is generally difficult to find good mutation operators. One example
of a bad mutation operator might be to change all predicates to
``true''.

Note that mutation is hard to apply by hand, and automation is
complicated.  The testing community generally considers mutation to be
a ``gold standard'' that serves as a benchmark against which to
compare other testing criteria against.

\paragraph{More on ground strings.} Mutation manipulates ground strings
to produce variants on these strings. Here are some examples:

\squishlist
\item the program that we are testing; or
\item valid inputs to a program.
\squishend
If we are testing invalid inputs, we might not care about ground strings.

\paragraph{Credit card number examples.}
{\sf Valid strings:} %{\tt 4500 0000 0000 1234}; {\tt 4599 2345 1111 3666}.

\noindent
{\sf Invalid strings:} %{\tt 4599 2345 1111 366i}; {\tt 4522 3433 9x12 ****}.

We can also create mutants by applying a mutation operator during generation,
which is useful when you don't need the ground string.

NB: There are many ways for a string to be invalid but still be generated
by the grammar.

\newpage
Some points:
\squishlist
\item How many mutation operators should you apply to get mutants? \emph{One.}
\item Should you apply every mutation operator everywhere it might apply? \emph{More work, but can subsume other criteria.}
\squishend

\section*{Killing Mutants} 
Generate a mutant $m$ for an original ground string $m_0$.
\begin{defn}
Test case $t$ \emph{kills} $m$ if running $t$ on $m$ gives different 
output than running $t$ on $m_0$.
\end{defn}
(The book uses a derivation $D$ rather than a ground string $m_0$.)

We can also define a mutation score, which is the percentage of mutants killed.

I'm going to list a trio of coverage criteria from the book. I don't
think that the mutation coverage criteria are ever used. If one were trying to use
mutation testing, one would measure the effectiveness of a test
suite (the mutation score) and to keep adding tests until reaching a desired
mutation score.

\begin{crit}
{\bf Mutation Coverage} (MC). For each mutant $m$, TR contains
requirement ``kill $m$''.
\end{crit}
(This definition does not describe the set of mutants required.)

\begin{crit} 
{\bf Mutation Operator Coverage} (MOC). For each mutation operator {\tt op}, 
TR contains requirement to create a mutated string $m$ 
derived using {\tt op}.
\end{crit}

\begin{crit}
{\bf Mutation Production Coverage} (MPC). For each mutation operator
{\tt op} and each production $p$ that {\tt op} can be applied to, TR
contains requirement to create a mutated string from $p$.
\end{crit}

\section*{Program Based Grammars} 

The usual way to use mutation testing is by generating mutants 
by modifying programs according to the language grammar,
using mutation operators.

Mutants are \emph{valid programs} (not tests) which ought to behave
differently from the ground string.

Our task, in mutation testing, is to create tests which distinguish
mutants from originals.

\paragraph{Example.} Given the ground string {\tt x = a + b},
we might create mutants {\tt x = a - b}, {\tt x = a * b}, etc.
A possible original on the
left and a mutant on the right:

\begin{minipage}{.5\textwidth} 
\begin{alltt}
int foo(int x, int y) \{ // original
  if (x > 5) return x + y;
  else return x;
\}
\end{alltt}
\end{minipage}\begin{minipage}{.5\textwidth}
\begin{alltt}
int foo(int x, int y) \{ // mutant
  if (x > 5) return x - y;
  else return x;
\}
\end{alltt}
\end{minipage}
~\\[3em]
%% In this example, the test case $\langle 6, 2 \rangle$ will kill
%%  the mutant, since it returns 8 for the original and 4 for the mutant,
%% while the case $\langle 6, 0 \rangle$ will not kill the mutant,
%% since it returns 6 in both cases.

Once we find a test case that kills a mutant, we can forget the
mutant and keep the test case. The mutant is then \emph{dead}.

\paragraph{Uninteresting Mutants.} Three kinds of mutants are uninteresting:
\squishlist
\item \emph{stillborn}: such mutants cannot compile (or immediately crash);
\item \emph{trivial}: killed by almost any test case;
\item \emph{equivalent}: indistinguishable from original program.
\squishend

The usual application of program-based mutation is to individual statements
in unit-level (per-method) testing.

\paragraph{Mutation Example.} Here are some mutants.

{\small
\begin{minipage}[t]{.5\textwidth}
\begin{alltt}
// original
int min(int a, int b) \{
  int minVal;
  minVal = a;

  if (b < a) \{


    minVal = b;



  \}
  return minVal;
\}
\end{alltt}
\end{minipage} \begin{minipage}[t]{.5\textwidth}
\begin{alltt}
// with mutants
int min(int a, int b) \{
  int minVal;
  minVal = a;
  minVal = b;               // \(\Delta 1\)
  if (b < a) \{
  if (b > a) \{              // \(\Delta 2\)
  if (b < minVal) \{         // \(\Delta 3 \)
    minVal = b;
    BOMB();                 // \(\Delta 4\)
    minVal = a;             // \(\Delta 5\)
    minVal = failOnZero(b); // \(\Delta 6\)
  \}
  return minVal;
\}
\end{alltt}
\end{minipage}
}

Conceptually we've shown 6 programs, but we display them together for 
convenience.

Goals of mutation testing:
\begin{enumerate}
\item mimic (and hence test for) typical mistakes;
\item encode knowledge about specific kinds of effective tests in practice, e.g.
statement coverage ($\Delta 4$), checking for 0 values ($\Delta 6$).
\end{enumerate}

Reiterating the process for using mutation testing (see picture at end):
\squishlist
\item \emph{Goal:} kill mutants
\item \emph{Desired Side Effect:} good tests which kill the mutants.
\squishend
These tests will help find faults (we hope). We find these tests by
intuition and analysis.

\end{document}