<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%\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&lt;presentation&gt;{}

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

\newcommand{\topicTitle}{35 Analysis (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 Module testing
\item Integration testing
\item Testing OO programs
\item Testing concurrent and real-time systems
\item Mutation testing
\item Analysis
\begin{itemize}
\item Code walk throughs and inspections
\item Correctness proofs
\item Symbolic execution
\item Model checking
\end{itemize}
\item Debugging
\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 tutorials on Friday, Apr 6

\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 {Your participation is highly valued}
\item {Grade bonus for class participation}
% \bi
% \item CS 2ME3 C02: 40\%
% \item CS 2ME3 C01: 23\%
% \item SE 2AA4 C01: 22\%
% \ei
\ei

\item Provide course feedback in last lecture
\end{itemize}
}
\fi

\end{frame}

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

% \begin{frame}
% \frametitle{The Oracle Problem Continued}

% \begin{itemize}

% \item Devising an oracle for concurrent and real time systems
% \bi
% \item The challenge is not coming up with the oracle
% \item The challenge is having adequate test coverage (or analysis) of all of the
%   cases (more on this later)
% \ei
% \item Other examples where an oracle is challenging to devise
% \bi
% \item Artificial general intelligence
% \item Machine learning
% \item Simulation with random numbers
% \ei
% \end{itemize}

% \end{frame}

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

\begin{frame}[fragile]
\frametitle{Unix Command of the Day: \texttt{grep}}

\begin{itemize}
\item Search for the lines in a collection of data that match a specified
  pattern
\item From \texttt{se2aa4\_cs2me3/Lectures}
\bi
\item \verb|grep -r Parnas . &gt; parnas.txt|
\item \texttt{grep -c L04 parnas.txt}
\item \texttt{grep -c 'L0.' parnas.txt}
\ei
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Strategies Without An Oracle}

\begin{itemize}

\item Using an independent program to approximate the oracle (pseudo oracle)
\item Method of manufactured solutions
\item Properties of the expected values can be easier than stating the expected
  output
\bi
\item \uncover&lt;1&gt;{\structure&lt;1&gt;{Examples?}}
\item \uncover&lt;2-&gt;{List is sorted}
\item \uncover&lt;2-&gt;{Number of entries in file matches number of inputs}
\item \uncover&lt;2-&gt;{Conservation of energy or mass}
\item \uncover&lt;2-&gt;{Expected trends in output are observed (metamorphic testing)}
\item \uncover&lt;2-&gt;{etc.}
\ei
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Metamorphic Testing}

\bi
\item Used for testing when there is no test oracle
\item Test program has properties known as Metamorphic Relations (MR)
\item MRs specify how a change in inputs should change the output
\item For instance (KanewalaEtAl2014)
\bi
\item Finding the maximum of a list should be the same no matter
  the permutation of the list
\item The average of a set of numbers will increase if each number added is
  larger than all previous numbers added
\item Etc.
\ei
\item Metamorphic testing gets its name because new test cases are evolved from
  the old ones (ChenEtAl1998)
\ei

\end{frame}

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

\begin{frame}
\frametitle{Module Testing}

\structure{Is it possible to begin testing before all of the modules have been
  implemented when there is a use relation between modules?}

\end{frame}

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

\begin{frame}
\frametitle{Module Testing}

\begin{itemize}

\item Scaffolding needed to create the environment in which the module should be
  tested
\item Stubs - a module used by the module under test
\item Driver - module activating the module under test
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Testing a Functional Module}

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

\end{frame}

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

\begin{frame}
\frametitle{Integration Testing}

\begin{itemize}
\item Big-bang approach
\begin{itemize}
\item First test individual modules in isolation
\item Then test integrated system
\end{itemize}
\item Incremental approach
\begin{itemize}
\item Modules are progressively integrated and tested
\item Can proceed both top-down and bottom-up according to the USES relation
\end{itemize}
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Integration Testing and USES relation}

\begin{itemize}
\item If integration and test proceed bottom-up only need drivers
\item Otherwise if we proceed top-down only stubs are needed
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Example}

\begin{center}
\includegraphics[scale=0.35]{../Figures/Example.png}
\end{center}

\begin{itemize}
\item $M_1$ USES $M_2$ and $M_2$ IS\_COMPOSED\_OF \{$M_{2,1}$, $M_{2,2}$\}
\item \structure{In what order would you test these modules?}
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Example}

\begin{center}
\includegraphics[scale=0.35]{../Figures/Example.png}
\end{center}

\begin{itemize}
\item $M_1$ USES $M_2$ and $M_2$ IS\_COMPOSED\_OF \{$M_{2,1}$, $M_{2,2}$\}
\item Case 1
\begin{itemize}
\item Test $M_1$ providing a stub for $M_2$ and a driver for $M_1$
\item Then provide an implementation for $M_{2,1}$ and a stub for $M_{2,2}$
\end{itemize}
\item Case 2
\begin{itemize}
\item Implement $M_{2,2}$ and test it by using a driver
\item Implement $M_{2,1}$ and test the combination of $M_{2,1}$ and $M_{2,2}$
  (i.e.\ $M_2$) by using a driver
\item Finally implement $M_1$ and test it with $M_2$ using a driver for $M_1$
\end{itemize}
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Testing OO and Generic Programs}

\begin{itemize}
\item New issues
\begin{itemize}
\item Inheritance
\item Genericity
\item Polymorphism
\item Dynamic binding
\end{itemize}
\item Open problems still exist
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Inheritance}

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

\end{frame}

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

\begin{frame}
\frametitle{How to Test Classes of the Hierarchy}

\structure{How would you approach testing for a class hierarchy?}

\end{frame}

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

\begin{frame}
\frametitle{How to Test Classes of the Hierarchy}

\begin{center}
\includegraphics[scale=0.5]{../Figures/UsesRelation.png}
\end{center}

\begin{itemize}
\item ``Flattening'' the whole hierarchy and considering every class as totally
  independent component
\item This does not exploit incrementality
\item Finding an ad-hoc way to take advantage of the hierarchy
\item Think about testing PointT.py and PointMassT.py
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{A Sample Strategy}

\begin{itemize}
\item A test that does not have to be repeated for any heir
\item A test that must be performed for heir class X and all of its further
  heirs
\item A test that must be redone by applying the same input data, but verifying
  that the output is not (or is) changed
\item A test that must be modified by adding other input parameters and
  verifying that the the output changes accordingly
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Testing Concurrent and Real-time Systems}

\structure{What are the challenges for testing concurrent and real-time
  systems?}

\end{frame}

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

\begin{frame}
\frametitle{Testing Concurrent and Real-time Systems}

\begin{itemize}
\item Nondeterminism inherent in concurrency affects \structure{repeatability}
%From Wikipedia ``Because computations in a concurrent system can interact with each other while
%being executed, the number of possible execution paths in the system can be
%extremely large, and the resulting outcome can be indeterminate. Concurrent use
%of shared resources can be a source of indeterminacy leading to issues such as
%deadlocks, and resource starvation.''
\item For real-time systems, a test case consists not only of input data, but
  also of the times when such data are supplied
\item Many potential time traces for the different inputs
\item System changes depends on the control actions
\item Considerable care and detail when testing real-time systems
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Testing your Tests}
\bi
\item \structure{How did we estimate the number of errors in our code?}
\item \structure{Can any of the ideas from estimating the number of errors in our code
  be used to test our tests?}
\ei
\end{frame}

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

\begin{frame}
\frametitle{Testing your Tests: Mutation Testing}
\begin{itemize}
\item Generate changes to the source code, called mutants, which become code faults
\item Mutants include changing an operation, modifying constants, changing the
  order of execution, etc.
\item The adequacy of a set of tests is established by running the tests on all
  generated mutants
%\item Need to account for floating point approximations
%\item See Hook and Kelly, 2009
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Analysis Versus Testing}

\begin{itemize}
\item Testing characterizes a \structure{single} execution
\item Analysis characterizes a \structure{class} of executions; it is based on a
  \structure{model}
\item They have complementary advantages and disadvantages
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Informal Analysis Techniques and Code Walkthroughs}

\begin{itemize}
\item Recommended prescriptions
\begin{itemize}
\item Small number of people (three to five)
\item Participants receive written documentation from the designer a few days
  before the meeting
\item Predefined duration of the meeting (a few hours)
\item Focus on the \structure{discovery} of errors, not on fixing them
\item Participants: designer, moderator, and a secretary
\item Foster cooperation; no evaluation of people
\item Experience shows that most errors are discovered by the designer during
  the presentation, while trying to explain the design to other people
% like reading report out loud at NSF panel
\end{itemize}
\item Forces looking at the code from a different viewpoint
\item Can be used for documentation too
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Informal Analysis Techniques Code Inspection}

\begin{itemize}
\item A reading technique aiming at error discovery
\item Based on checklists
\begin{itemize}
\item Use of uninitialized variables
\item Jumps into loops
\item Nonterminating loops
\item Array indexes out of bounds
\end{itemize}
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Correctness Proofs}

\begin{itemize}
\item Formal program analysis is a verification aid that may enhance program
  reliability
\item Mathematically prove that the program's semantics implies its
  specification
\item Can use pre and post conditions
\item We can prove correctness of operations (like those on an abstract data
  type)
\item Use the proof of operations to prove fragments that operate on the objects
  of an ADT
\item Tabular expressions can be proven to match between specification of
  requirements and a specification of the design
\item In many cases verification can be automated, at least partially
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Assessment of Correctness Proofs}

\begin{itemize}
\item Not often used in practice
\item However
\bi
\item May be used for very critical portions
\item Assertions may be the basis for a systematic way of inserting runtime
  checks
\item Proofs may become more practical as more powerful support tools are
  developed
\item Knowledge of correctness theory helps programmers being rigorous
\ei
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Symbolic Execution}

\begin{itemize}
\item Can be viewed as a middle way between testing and analysis
\item Executes the program on symbolic values
\item One symbolic execution corresponds to many actual executions
\item \href{https://en.wikipedia.org/wiki/Symbolic_execution}{Wikipedia} for
  explanation and sample tools
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Model Checking}

\begin{itemize}
\item Correctness verification, in general, is an undecidable problem
\item Model checking is a recent verification technique based on the fact
  that most interesting system properties become decidable (algorithmically
  verifiable) when the system is modelled as a finite state machine
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Model Checking Continued}

\begin{itemize}
\item Describe a given system - software or otherwise - as an FSM
\item Express a given property of interest as a suitable formula
\begin{itemize}
\item Does a computation exist that allows a process to enter a critical region?
\item Is there a guarantee that a process can access shared resources?
\end{itemize}
\item Verify whether the system's behaviour does indeed satisfy the desired property
\begin{itemize}
\item This step can be performed automatically
\item The model checker either provides a \structure{proof} that the property
  holds or gives a \structure{counter example} in the form of a test case that
  exposes the system's failure to behave according to the property
\end{itemize}
\end{itemize}
\end{frame}

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

\begin{frame}
\frametitle{Why so Many Approaches to Testing and Analysis?}

\begin{itemize}
\item Testing versus (correctness) analysis
\item Formal versus informal techniques
\item White-box versus black-box techniques
\item Techniques in the small/large
\item Fully automatic versus semi-automatic techniques (for undecidable problems)
\item ...
\end{itemize}

View all of these as complementary

\end{frame}

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

\begin{frame}
\frametitle{Debugging}

\structure{What approaches do you use for debugging?}

\end{frame}

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

\begin{frame}
\frametitle{Debugging}

\begin{itemize}
\item The activity of locating and correcting errors
\item It can start once a failure has been detected
\item The goal is closing the gap between a fault and a failure
\begin{itemize}
\item Memory dumps, watch points
\item Intermediate assertions can help
\item Tools like gdb, valgrind, etc.
\end{itemize}
\item Incremental integration tests helps
\item Incrementally add complexity to test cases
\item Like investigating an experiment - one controlled variable at a time
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Verifying Performance}

\structure{How might you measure/assess performance?}

\end{frame}

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

\begin{frame}
\frametitle{Verifying Performance}

\begin{itemize}
\item Worst case analysis versus average behaviour
\item For worst case, focus on proving that the system response time is bounded
  by some function of the external requests
\item Standard deviation
\item Analytical versus experimental approaches
\item Consider verifying the performance of a pacemaker
\item Visualize performance via
\bi
\item Identify a measure of performance (time, storage, FLOPS, accuracy, etc.)
\item Identify an independent variable (problem size, number of processors,
  condition number, etc.)
\ei
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Verifying Reliability}

\begin{itemize}
\item There are approaches to measuring reliability on a probabilistic basis, as
  in other engineering fields
\item Unfortunately there are some difficulties with this approach
\item Independence of failures does not hold for software
\item Reliability is concerned with measuring the probability of the occurrence
  of failure
\item Meaningful parameters include
\begin{itemize}
\item Average total number of failures observed at time $t$: $AF(t)$
\item Failure intensity: $FI(T)=AF'(t)$
\item Mean time to failure at time $t$: $MTTF(t) = 1/FI(t)$
\end{itemize}
\item Time in the model can be execution or clock or calendar time
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Verifying Subjective Qualities}

\begin{itemize}
\item \structure{What do you think is meant by empirical software engineering?}
\item \structure{What problems might be studied by empirical software
    engineering?}
\item \structure{Does the usual engineering analogy hold for empirical software
    engineering?}
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Verifying Subjective Qualities}

\begin{itemize}
\item Consider notions like simplicity, reusability, understandability …
\item Software science (due to Halstead) has been an attempt
\item Tries to measure some software qualities, such as
abstraction level, effort, …
\item by measuring some quantities on code, such as
\bi
\item $\eta_1$, number of distinct operators in the program
\item $\eta_2$, number of distinct operands in the program
\item $N_1$, number of occurrences of operators in the program
\item $N_2$, number of occurrences of operands in the program
\ei
\item Extract information from repo, including number of commits, issues etc.
\item Empirical software engineering
\item Appropriate analogy switches from engineering to medicine
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{Source Code Metric}

\begin{itemize}
\item \structure{What are the consequences of complex code?}
\item \structure{How might you measure code complexity?}
\end{itemize}

\end{frame}

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

\begin{frame}
\frametitle{McCabe's Source Code Metric}

\begin{itemize}
\item Cyclomatic complexity of the control graph
\bi
\item $C = e - n + 2 p$
\item $e$ is number of edges, $n$ is number of nodes, and $p$ is number of
  connected components
\ei
\item McCabe contends that well-structured modules have $C$ in range $3 .. 7$,
  and $C = 10$ is a reasonable upper limit for the complexity of a single module
\item Confirmed by empirical evidence 
\end{itemize}

\end{frame}

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


\end{document}

</pre></body></html>