You need to sign in or sign up before continuing.
Newer
Older
%\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}{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 Analysis
\begin{itemize}
\item Code walk throughs and inspections
\item Correctness proofs
\item Symbolic execution
\item Model checking
\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 tutorials on Friday, Apr 6
\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
\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}
\item \verb|grep -r Parnas . > parnas.txt|
\item \texttt{grep -c L04 parnas.txt}
\item \texttt{grep -c 'L0.' parnas.txt}
\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
\item \uncover<1>{\structure<1>{Examples?}}
\item \uncover<2->{List is sorted}
\item \uncover<2->{Number of entries in file matches number of inputs}
\item \uncover<2->{Conservation of energy or mass}
\item \uncover<2->{Expected trends in output are observed (metamorphic testing)}
\item \uncover<2->{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}
\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}
W. Spencer Smith
committed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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}
W. Spencer Smith
committed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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
\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
\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}
W. Spencer Smith
committed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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
W. Spencer Smith
committed
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
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}