software-testing/project_task_sheets/phase_03/project_phase03_tasks/Solution_Phase03_MichaelChen.tex

\documentclass[a4paper]{scrreprt}
\usepackage[left=4cm,bottom=3cm,top=3cm,right=4cm,nohead,nofoot]{geometry}
\usepackage{graphicx}
\usepackage{tabularx}
\usepackage{listings}
\usepackage{enumitem}
\usepackage{subcaption}
\usepackage[acronym]{glossaries}

\usepackage{pgf}
\usepackage{tikz}
\usetikzlibrary{arrows,automata}

\newacronym{nc}{NC}{node coverage}
\newacronym{ec}{EC}{edge coverage}
\newacronym{adupc}{ADUPC}{all-du-path coverage}
\newacronym{ppc}{PPC}{prime path coverage}
\newacronym{auc}{AUC}{all-uses coverage}
\newacronym{adc}{ADC}{all-defs coverage}
\newacronym{srtc}{SRTC}{simple round-trip coverage}
\newacronym{crtc}{CRTC}{complete round-trip coverage}

\usepackage{xparse}
\usepackage{multirow}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\textfloatsep}{16pt}

\renewcommand{\labelenumi}{\alph{enumi})}
\renewcommand{\labelenumii}{\arabic{enumii}) }

\newcommand{\baseinfo}[5]{
  \begin{center}
    \begin{tabular}{p{15cm}r}
      \vspace{-4.5pt}{ \Large \bfseries #1} & \multirow{2}{*}{} \\[0.4cm]
      #2 & \\[0.5cm]
    \end{tabular}
  \end{center}
  \vspace{-18pt}\hrule\vspace{6pt}
  \begin{tabular}{ll}
    \textbf{Name:}  & #4\\
    \textbf{Group:} & #5\\
  \end{tabular}
  \vspace{4pt}\hrule\vspace{2pt}
  \footnotesize \textbf{Software Testing} \hfil - \hfil Summer 2022 \hfil - \hfil #3 \hfil - \hfil Sibylle Schupp / Sascha Lehmann \hfil \\
}

\newcounter{question}
\NewDocumentEnvironment{question}{m o}{%
  \addtocounter{question}{1}%
  \paragraph{\textcolor{red}{Task~\arabic{question}} - #1\hfill\IfNoValueTF{#2}{}{[#2 P]}}
  \leavevmode\\%
}{%
  \vskip 1em%
}

\NewDocumentEnvironment{answer}{}{%
  \vspace{6pt}
  \leavevmode\\
  \textit{Answer:}\\[-0.25cm]
  {\color{red}\rule{\textwidth}{0.4mm}}
}{%
  \leavevmode\\
  {\color{red}\rule{\textwidth}{0.4mm}}
}

\newcommand{\projectinfo}[5]{
  \baseinfo{Project Phase #1 - Submission Sheet}{#2}{#3}{#4}{#5}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\name{Michael Chen}
\def\group{Group 01 (fastjson)}

\begin{document}
\projectinfo{3}{Software Testing - Graph Coverage\small}{\today}{\name}{\group}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Task 1 %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{question}{Answer basic questions on Graph Coverage}[3]
\begin{enumerate}[topsep=0pt, leftmargin=*]
  \item Define the following terms in your own words:
  \begin{enumerate}
      \item Graph
      \begin{answer}
      A graph is a set of vertices and edges between two such vertices. This allows us to create mathematical models of real world applications. This includes for example network architectures with computers and links as vertices and edges, or in our situation we can model program source code to vertices and the program flow to edges between code lines.
      \end{answer}

      \item (Test-)Path
      \begin{answer}
      In software testing we use directed graphs, because in a directed graph we always have unidirectional edges between the vertices. This is usesful because our program can only flow in one direction usually. A path on a directed graph is a sequence of vertices that are connected by edges pairwise, which corresponds to a connected set of directional edges. For software this can refer to a possible execution in a program flow. A test path is a path such that the path starts at an entrypoint of the graph and ends in an exit point. A test path thus refers to a path that corresponds to one possible complete execution of a program.
      \end{answer}

      \item Syntactic and Semantic Reach
      \begin{answer}
      Syntactic reach describes if a vertex in the graph can be reached (with a path) from another vertex. This of course only refers to the graph model without taking in account if such a path is actually possible using the semantics of our language. Therefore we have semantic reach, which describes if such a path is taken from any possible program execution (including inputs). The difference between these reaches is that we check if, even though a path might exist in the graph, it might still not be a useful path, because our program state never executes this path given any input values.
      \end{answer}

  \end{enumerate}
  \item Which testing situations are suitable for the Graph Coverage approach?
  \begin{answer}
  Graph Coverage is suitable for white-box testing situations where we have detailed knowledge of the system under test. A program graph can be created from different aspects of a program, for example from the code directly (control-flow graph), from a software specification model, or even from higher-level abstractions such as calls between different software modules. Graph coverage allows us to very precisely specify semantically different program states, where, in contrast to black-box testing, we can (and must) incorporate edge cases and domain knowledge directly into our execution paths.
  \end{answer}

  \item What is the difference between \textit{Tours}, \textit{Tours With Sidetrips}, and \textit{Tours With Detours}?
  \begin{answer}
  A path $p_1$ can \textit{tour} another path $p_2$ if and only if $p_2$ is a subpath of $p_1$. This means that if $p_1$ is traversed, this includes the exact sequence of vertices that are also given in $p_2$. This makes a test on $p_2$ redundant, because we know, that we already traversed the graph in this manner. A tour with a sidetrip is a tour, except that it is allowed to insert loops into the subpath, as long as all edges of $p_2$ also appear in $p_1$ in the same order. A detour is similar, but instead of the edges, we enforce that all nodes of $p_2$ must also appear in $p_1$.
  \end{answer}

  \item Describe (1-2 sentences) the \textit{Node Coverage} (NC) and \textit{Edge Coverage} (EC) criterion. What are their counterparts for code-based coverage?
  \begin{answer}
  \Gls{nc} is satisfied for a test set if every syntactically reachable vertex in the graph is reached by any test path of our test set. \Gls{ec} however is satisfied if every syntactically reachable edge in the graph was used by any test path. A mapping to code-based coverage maps vertices in the graph to statements (or non-branching blocks of statements) and edges to branches between the statements. \Gls{nc} then refers to every statement being executed, which means we have statement coverage, while \gls{ec} refers to every branch being executed, which corresponds to branch coverage.
  \end{answer}

  \item Name and describe (2-3 sentences) 2 \textit{Path Coverage Criteria} OR 2 \textit{Data Flow Test Criteria}. Does one of these two criteria subsume the other?
  \begin{answer}
  Path coverage criteria are concerned with checking if all possible paths in a graph have been executed, while data-flow criteria check if all variable definitions and their usages have been reached. \Gls{ppc} is an example for a path coverage criterion that subsumes the \gls{adupc} criterion. \Gls{ppc} requires that every prime path (path that is not subpath of any other path) must be executed, while \gls{adupc} requires that every possible path between every definition and usage of a variable must be covered, which is of course less strong than checking every possible syntactically reachable path. Another example for data-flow coverage is \gls{auc} which verifies that every usage of variables are covered by at least one path in the test set, which is easily subsumed by \gls{adupc} and thus by \gls{ppc}. Another example for path coverage is \gls{srtc} which checks if a round-trip path is executed for every node that is the start and end of a round-trip.
  \end{answer}

\end{enumerate}
\end{question}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Task 2 %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{question}{Apply Graph Coverage criteria to a sample program}[5]
\begin{enumerate}[topsep=0pt, leftmargin=*]
  \item Create the control flow graph for the given constructor.
  \begin{answer}
    \begin{center}
    \begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,semithick]
      \tikzstyle{every state}=[fill=gray,draw=none,text=white]

      \node[initial,state] (s0) {$s_0$};
      \node[state] (s1) [below of=s0] {$s_1$};
      \node[state] (s2) [right of=s1] {$s_2$};
      \node[state] (s3) [below of=s1] {$s_3$};
      \node[state] (s3s) [below of=s3] {$s_{3,s}$};
      \node[state] (s4p) [below of=s3s] {$s_{4,p}$};
      \node[state] (s4) [right of=s4p] {$s_4$};
      \node[state] (s5) [right of=s4] {$s_5$};
      \node[state] (s6) [below of=s4] {$s_6$};
      \node[state] (throw) [right of=s2] {\texttt{throw}};

      \path
        (s0) edge [bend left] node {$\texttt{iC} < 0$} (throw)
        (s0) edge node {$\texttt{iC} \geq 0$} (s1)
        (s1) edge node {$\texttt{iC} > \texttt{MAX}$} (s2)
        (s1) edge node {$\texttt{iC} \leq \texttt{MAX}$} (s3)
        (s2) edge [bend left] node {} (s3)
        (s3) edge node {$\texttt{lF} > 0$} (s3s)
        (s3) edge [bend right] node {$\texttt{lF} \leq 0$} (throw)
        (s3s) edge node {$\texttt{lF} \not\equiv \texttt{NaN}$} (s4p)
        (s3s) edge [bend right] node {$\texttt{lF} \equiv \texttt{NaN}$} (throw)
        (s4p) edge node {} (s4)
        (s4) edge [bend left] node {$\texttt{c} < \texttt{iC}$} (s5)
        (s4) edge node {$\texttt{c} \geq \texttt{iC}$} (s6)
        (s5) edge [bend left] node {} (s4)
      ;
    \end{tikzpicture}
    \end{center}
  \end{answer}

  \item Create a minimum set of test cases that reaches 100\% coverage for the instruction coverage criterion.
  \begin{answer}
    This test set covers both throw instructions and the statement in the loop and the second \texttt{if} statement. The minimal amount of test inputs for statement coverage consists of at least three tests because there are three exit points to the function (the return and both of the throws) so this is the minimum amount of tests necessary.
    \begin{center}
    \begin{tabular}{r|r|c}
      \texttt{initialCapacity} & \texttt{loadFactor} & Instruction Coverage \\ \hline \hline
      -1 & 2.0f & $throw_1$ \\
      8 & \texttt{NaN} & $throw_2$ \\
      1025 & 2.0f & $s_1, s_2, s_3, s_4, s_5, s_6$
    \end{tabular}
    \end{center}

    % or: \lstinputlisting[language=Java,belowskip=-0.8\baselineskip]{file_name.java}
  \end{answer}

  \item Extend the set of test cases so that it additionally reaches 100\% coverage for the branch coverage criterion. Describe the necessity of the added tests.
  \begin{answer}
    To reach 100\% branch coverage from the above test set, you need to add a test where the \texttt{loadFactor} is less than or equal to zero to account for the branch that occurs in the disjunction in the third \texttt{if} statement due to short circuit evaluation of the condition. Apart from that the above test set already satisfies branch coverage, because the second and third input execute both branches from the $s_1$ branch and the first two tests branch at the throw instructions. The last output runs all branches in the loop branch in $s_4$.
  \end{answer}

  \item Analyze the code regarding the following data flow criteria, and list all relevant DU pairs. Does your test suite require additional tests to cover them?
  \begin{enumerate}
    \item All-defs with respect to \texttt{capacity}
    \begin{answer}
      \texttt{capacity} is first initialized in $s_{4,p}$ and then defined in $s_5$ and used in states $s_5$ and $s_6$.
      The relevant DU pairs are thus: $(s_{4,p}, s_5), (s_{4,p}, s_6), (s_5, s_6)$. The pair $(s_{4,p}, s_6)$ is currently not covered by our test set because the current path that is taken between these two nodes is not def-free in node $s_5$ with respect to def-use paths. To achieve this we would have to input a valid \texttt{loadFactor} with a $\texttt{capacity} \geq \texttt{initialCapacity}$ such that the loop definition is not executed. However, when we only consider def-paths The above test set is sufficient, becuase the initial definition is trivially covered by our non-throwing input and the loop definition is also covered because the loop is executed at least once (actually more than once, so both def-use paths from the loop definition are evaluated).
    \end{answer}

    \item All-uses with respect to \texttt{loadFactor}
    \begin{answer}
      The relevant def-pairs are $(s_0, s_3), (s_0, s_{3,s}), (s_0, \texttt{throw}_2), (s_0, s_6)$. All of these are already covered by our branch initial test set becuase all usages of the \texttt{loadFactor} are covered by our instruction coverage and since there is only one definition (in the parameter section) all paths to every usage is trivially def-free and thus a DU path.
    \end{answer}

  \end{enumerate}
\end{enumerate}
\end{question}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Task 3 %%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{question}{Apply Graph Coverage criteria to your software project}[8]
\begin{enumerate}[topsep=0pt, leftmargin=*]
    \item Measure the coverage of your given project test suite (which includes the existing test suite as well as the tests that you created in previous project phases) by three graph coverage criteria which you can freely choose. Describe each individual result in 2-3 sentences.
    \begin{answer}
    My test suite for the \texttt{JSONScanner} class so far covers 1\% of the class and 5\% of the \texttt{JsonLexerBase} base class, that does most of the work for basic JSON strings, in terms of instruction coverage. The fact that roughly similar coverage values are achieved with branch coverage using my small test suite is explained by the fact that most instructions that i have not covered are not covered because of missing tests that handle edge case (in this case mostly different JSON token alternatives) branches. My method coverage currently is at about 14\% and 12\% for the base class. Similar to the above tests, I am missing lots of tests for function calls that retrieve specific token values, however the coverage is higher than the branch coverage because the token alternatives are handled within the lexing method call, thus the method coverage is higher.
    \end{answer}

    \item Extend the test suite with own tests, which have to fullfil \textbf{one} of the following criteria:
    \begin{enumerate}
      \item Increase the coverage values of all three coverage criteria that you applied in the previous subtask with at least 10 tests (compare and describe the effects on coverage for each individual test), OR
      \item Reveal a new bug in the software project (describe the bug, its context, and a potential fix in detail)
    \end{enumerate}
    \begin{answer}
      See file \texttt{JSONScannerTest2.java}. Using this test suite I increased my test instruction coverage from 1\% to more than 9\% and my branch coverage from .5\% to almost 5\% (factor 10). I almost doubled the method coverage, which matches the test suite, because I roughly doubled the amount of different methods I called for different edge cases.
    \end{answer}

\end{enumerate}
\end{question}

\end{document}