%\documentclass[t,12pt,numbers,fleqn,handout]{beamer}
\documentclass[t,12pt,numbers,fleqn]{beamer}

\usepackage{pgfpages} 
\usepackage{hyperref}
\hypersetup{colorlinks=true,
    linkcolor=blue,
    citecolor=blue,
    filecolor=blue,
    urlcolor=blue,
    unicode=false}
\urlstyle{same}

\usepackage{hhline}
\usepackage{booktabs}
\usepackage{multirow}
\usepackage{multicol}
\usepackage{array}
\usepackage{listings}

\usepackage{amssymb}
\usepackage{amsmath}

\useoutertheme{split} %so the footline can be seen, without needing pgfpages

% \pgfpagesuselayout{resize to}[letterpaper,border
% shrink=5mm,landscape] %if this is uncommented, the hyperref links do not work

\mode<presentation>{}

\input{../def-beamer}
\Draftfalse

\newcommand{\topicTitle}{33 White Box Testing Continued (Ch.\ 6)}
\ifDraft
\newcommand{\topic}{\topicTitle~DRAFT}
\else
\newcommand{\topic}{\topicTitle}
\fi

\input{../titlepage}

\begin{document}

\input{../footline}

\lstset{language=java, breaklines=true, showspaces=false,
  showstringspaces=false, breakatwhitespace=true}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{\topic}

\begin{itemize}
\item Administrative details
\item White box testing
\begin{itemize}
\item Edge coverage
\item Condition coverage
\item Path coverage
\end{itemize}
% \item Black Box Testing 
% \begin{itemize}
% \item Informal Example
% \item Formal using MIS for PointT
% \end{itemize}
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Administrative Details}

\ifDraft  
TBD
\else
{
\begin{itemize}

\item Today's slide are partially based on slides by Dr.\ Wassyng

\item A4: Due April 9 at 11:59 pm
\item Final tutorial (examination review)
\bi
\item No tutorials Monday or Tuesday
\item Last tutorials on Friday, Apr 6
\ei

\item Course evaluations
\bi
\item \href{https://evals.mcmaster.ca}{https://evals.mcmaster.ca}
\item Start: Tues, Mar 27, 10:00 am
\item Close: Tues, Apr 10, 11:59 pm
\item \textbf{Your participation is highly valued!}
\item \emph{Grade bonus for class participation!}
\bi
\item CS 2ME3 C02: 40\%
\item CS 2ME3 C01: 23\%
\item SE 2AA4 C01: 22\%
\ei
\ei

\end{itemize}
}
\fi

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Theoretical Foundations Of Testing: Definitions}
\begin{itemize}
\item P (program), D (input domain), R (output domain)
\bi
\item P: D $\rightarrow$ R (may be partial)
\ei
\item Correctness defined by OR $\subseteq$ D $\times$ R
\bi
\item P(d) correct if $\langle$ d, P(d) $\rangle \in$ OR
\item P correct if all P(d) are correct
\ei
\item Failure
\bi
\item P(d) is not correct
\item May be undefined (error state) or may be the wrong result
\ei
\item Error (Defect)
\bi
\item Anything that may cause a failure
\bi
\item Typing mistake
\item Programmer forgot to test ``x=0''
\ei
\ei
\item Fault
\bi
\item Incorrect intermediate state entered by program
\ei
\end{itemize}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Definitions Questions}
\begin{itemize}
\item \structure{A test case t is an element of D or R?}
\item \structure{A test set T is a finite subset of D or R?}
\item \structure{How would we define whether a test is successful?}
\item \structure{How would we define whether a test set is successful?}
\end{itemize}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Definitions Continued}
\begin{itemize}
\item Test case t: An element of D
\item Test set T: A finite subset of D
\item Test is successful if P(t) is correct
\item Test set successful if P correct for all t in T
\end{itemize}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Theoretical Foundations of Testing}

\begin{itemize}
\item Desire a test set $T$ that is a finite subset of $D$ that will uncover all errors
\item Determining and ideal $T$ leads to several
  \href{https://en.wikipedia.org/wiki/Undecidable_problem}{undecideable
    problems}
\item No algorithm exists:
\bi
\item To state if a test set will uncover all possible errors
\item To derive a test set that would prove program correctness
\item To determine whether suitable input exists to guarantee execution of a
  given statement in a given program
\item etc.
\ei
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Empirical Testing}

\begin{itemize}
\item Need to introduce empirical testing principles and heuristics as a
  compromise between the impossible and the inadequate
\item Find a strategy to select \structure{significant} test cases
\item Significant means the test cases have a high potential of uncovering the
  presence of errors
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Complete-Coverage Principle}

\includegraphics[scale=0.5]{../Figures/CompleteCoveragePrinciple.png}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{White-box Testing}

\begin{itemize}
\item \structure{Intuitively, after running your test suites, what percentage of
    the lines of code in your program should be exercised?}
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{White-box Coverage Testing}

\begin{itemize}
\item (In)adequacy criteria - if significant parts of the program structure are not tested, testing is inadequate
\item Control flow coverage criteria
\begin{itemize}
\item Statement coverage
\item Edge coverage
\item Condition coverage
\item Path coverage
\end{itemize}
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Statement-Coverage Criterion}

\begin{itemize}
\item Select a test set $T$ such that every elementary statement in $P$ is
  executed at least once by some $d$ in $T$
\item An input datum executes many statements - try to minimize the number of
  test cases still preserving the desired coverage
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Example}

\includegraphics[scale=0.5]{../Figures/ExampleStatementCoverageOnlyCode.png}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Example}

\includegraphics[scale=0.5]{../Figures/ExampleStatementCoverage.png}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Weakness of the Criterion}

\includegraphics[scale=0.6]{../Figures/WeaknessStatementCoverageOnlyCode.png}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Weakness of the Criterion}

\includegraphics[scale=0.6]{../Figures/WeaknessStatementCoverage.png}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Edge-Coverage Criterion}

\begin{itemize}
\item Select a test set $T$ such that every edge (branch) of the control flow is
  exercised at least once by some $d$ in $T$
\item This requires formalizing the concept of the control graph and how to construct it
\begin{itemize}
\item Edges represent statements
\item Nodes at the ends of an edge represent entry into the statement and exit
\end{itemize}
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Control Graph Construction Rules}

\includegraphics[scale=0.4]{../Figures/ControlGraphRules.png}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Simplification}

A sequence of edges can be collapsed into just one edge\\
~\newline

\includegraphics[scale=0.5]{../Figures/Simplification.png}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Example: Euclid's Algorithm}

\includegraphics[scale=0.5]{../Figures/EuclidsAlgorithmNoGraph.png}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Example: Euclid's Algorithm}

\includegraphics[scale=0.5]{../Figures/EuclidsAlgorithm.png}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Weakness}

\includegraphics[scale=0.4]{../Figures/WeaknessEdgeCoverage.png}\\
First list index is 1 (not 0)\\
\structure<1>{What is the problem?}\\
\uncover<2->{\structure{Do not discover the error ($<$ instead of $\leq$)}}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
%\frametitle{Alternative View of Condition Coverage}

\lstset{language=java,breaklines=true,showspaces=false,showstringspaces=false,breakatwhitespace=true}
\noindent \lstinputlisting{CondCovExample.java}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Condition-Coverage Criterion}

\begin{itemize}
\item Select a test set $T$ such that every edge of $P$'s control flow is traversed and all possible values of the
constituents of compound conditions are exercised at least once
\item This criterion is finer than edge coverage
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Weakness}

\includegraphics[scale=0.5]{../Figures/WeaknessConditionCoverage.png}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Path-Coverage Criterion}

\begin{itemize}
\item Select a test set $T$ that traverses all paths from the initial to the final node of $P$s control flow
\item It is finer than the previous kinds of coverage
\item However, number of paths may be too large, or even infinite (see while loops)
\item Loops
\begin{itemize}
\item Zero times (or minimum number of times)
\item Maximum times
\item Average number of times
\end{itemize}
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{The Infeasibility Problem}

\begin{itemize}
\item Syntactically indicated behaviours (statements, edges, etc.) are often impossible
\item Unreachable code, infeasible edges, paths, etc.
\item Adequacy criteria may be impossible to satisfy
\begin{itemize}
\item Manual justification for omitting each impossible test case
\item Adequacy ``scores'' based on coverage - example 95 \% statement coverage
\end{itemize}
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Further Problem}

\begin{itemize}
\item What if the code omits the implementation of some part of the specification?
\item White box test cases derived from the code will ignore that part of the specification!
\end{itemize}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}