```Analyzing Regression Test
Selection Techniques
-presented by Xuan Lin
Outline





Introduction
Concepts and Assumptions
Analysis Framework
Examples Techniques
Conculsion and Discussion
Outline





Introduction
Concepts and Assumptions
Analysis Framework
Examples Techniques
Conculsion and Discussion
Introduction

What is Regression Testing?
-Everybody knows …

Retest-all strategy VS. Test Selection

Notions: P,P’,S,S’,T,T’,
Typical Selective Retest
Process
1. Select T'≤T, a set of tests to execute on P'
Regression Test Selection Problem
2.Test P’ with T’, to establish the correctness of P’ with respect to T’
Test Suite Execution Problem
3.If necessary, create T’’, a set of new functional or structural tests for P’
Coverage Identification Problem
4.Test P’ with T’’, to establish the correctness of P’ with respect to T’’
Test Suite Execution Problem
5.Create T’’’, a new test suite and test history for P’, from T, T’ and T’’
Test Suite Maintenance
Typical Selective Retest
Process
1. Select T'≤T, a set of tests to execute on P'
Regression Test Selection Problem
2.Test P’ with T’, to establish the correctness of P’ with respect to T’
Test Suite Execution Problem
3.If necessary, create T’’, a set of new functional or structural tests for P’
Coverage Identification Problem
4.Test P’ with T’’, to establish the correctness of P’ with respect to T’’
Test Suite Execution Problem
5.Create T’’’, a new test suite and test history for P’, from T, T’ and T’’
Test Suite Maintenance
Test Selection Techniques


Specification-based VS. Code-based
Three distinct goals of code-based test
selection techniques
-Coverage Techniques
-Minimization Techniques
-Safe Techniques
Compare and
Evaluation !!!
Outline





Introduction
Concepts and Assumptions
Analysis Framework
Examples Techniques
Conculsion and Discussion
Concepts and Assumptions

Fault-realing for P’: cause P’ to fail
-No Effective procedure by which to find tests in T
that are fault-realing for P’ [1]
-Under certain conditions, a technique can select a
Superset of the set of fault-revealing for P

Modification-revealing: casue the outputs of
P and P’ to differ.
Concepts and Assumptions


Modification-revealing = Fault-revealing ???
P-Correct-for-T Assumption: For each test t in T,
when P was tested with t, P halted and produced the
correct output

Obsolet-Test-Identification Assumption:
There is an effective procedure for determining, for
each test in t, whether t is obsolete for P’.
Test t is obsolete for P’ if and only if t either specifies an input to P’
that, according to S’, is invalid for P’, or t specifies an invalid
input-output relation for P’
Concepts and Assumptions

Up to now, we can find the fault-revealing test
cases by:
1. Run our procedure for identifying obsolete test in
T.
2. Remove them.
3. Find the modification-revealing test cases.
- In the set of non-obsolete test cases, modificationrevealing=fault-revealing
Concepts and Assumptions
Obsolete
Fault-Revealing
Nonbsolete
Fault-Revealing
Modification-Revealing
???
Running P’ with inputs,
and setting a time bound
b such that, if any test
exceeds the bound, we
assume it is faultrevealing.
Concepts and Assumptions

Modification-traversing: a test t is
modification-traversing for P and P’ if
and only if it (a) executes new or
modified code in P’, or (b) formerly
executed code that has since been
deleted
Concepts and Assumptions
Obsolete
Fault-Revealing
Nonbsolete
Fault-Revealing
Modification-Revealing
???
Modification-Traversing
Concepts and Assumptions

Controlled Regression Testing
Assumption: when P’ is tested with t,
we hold all factors that might infuence
the output of P’, except for the code in
P’, constant with respect to their states
when we tested P with t.
Why We Need Define These
Concepts and Assumptions?



Evaluate test selection techniques in
terms of their ablities to select and
Three classes can be used to
distinguish techniques even CRTA is
not satisfied.
Coverage techniques may omit tests
from T’ that may reveal faults in P’
Outline





Introduction
Concepts and Assumptions
Analysis Framework
Examples Techniques
Conculsion and Discussion
Analysis Framework




Incusiveness
Precision
Efficiency
Generality
Analysis FrameworkInclusiveness
Analysis FrameworkInclusiveness

There is no algorithm to determine the
inclusiveness!

However…

We can prove M is safe.
We can prove M is not safe.
We can compare techinques in terms
of inclusiveness
We can experiment to approximate



Analysis Framework-Precision
Analysis Framework-Precision

There is no algorithm to determine the
precision!


However…
We can compare techinques in terms
of precision.
We can prove M is not precise
We can show M is precise.

We can experiment to compare.


Analysis Framework-Efficiency



Time & Space
Cost of selecting T’ < the cost of running TT’
Three Factors
1.preliminary phase vs. critical phase
2.automatability
3. calculation informatin on program
modifications
4.ability to handle multiple modifications
Analysis FrameworkGenerality


Should function for some identifiable and practical
class of program
Should handle realistic program modifications

Should be independent of assumptions about
testing or maintenance enviroments.

Should be independent of particular program
analysis tools

Should support intraprocedural or interprocedural
test selection


Precision vs. Efficiency
- both safe and unsafe
Inclusiveness vs.Efficiency
-not safe

Generality vs. Inclusiveness, Efficiency or Precision

Multiple modication vs. Efficiency
Outline





Introduction
Concepts and Assumptions
Analysis Framework
Examples Techniques
Conculsion and Discussion
Refresh…
Obsolete
Fault-Revealing
Nonbsolete
Fault-Revealing
Modification-Revealing
Modification-Traversing
Depiction of inclusiveness and
precision
Retest-all
Optimum
Examples: Dataflow

Caculate d-u pairs for both P and P’

Identify and select d-u pairs that are
new in, or modified for P’
Some techniques also select deleted
d-u pairs


Incremental / Nonincremental
Examples: Dataflow-Inclusion

Not safe
Examples: Dataflow-Precision

Not precise
Examples: Dataflow
Examples: Dataflow-Effiency

IncrementalO(|T|*|P’|*|P’|)

Nonincremental-
Examples: Dataflow-Generity




Applied to procedural programs generally.
Function for all program changes except
those that do not alter d-u association
Some techiques applied to intraprocedural
programs while others applied to
interprocedural programs
Incremental approach requires incremental
dataflow analysis tools.
Examples: Graph Walk
Techniques

Build CFG for P and P’

Collects traces for tests with CFG
edges.

Performs synchronous depth-first
traversals of the two graphs, selects
those are not lexically identical.
Examples: Graph Walk
Techniques-Inclusiveness


[1] shows that for controlled regression
testing, the techniques will select all
modification-traversing test.
So, it is safe.
Examples: Graph Walk
Techniques-Precision


Not precise
Multiply-visisted-node
Examples: Graph Walk
Techniques
In practice
Improved version
Examples: Graph Walk
Techniques-Efficiency


Generally:
Property not hold[1]:
Examples: Graph Walk
Techniques-Generality





Apply to procedural languages generally
All type of modifications
Both interprocedure and intraprocedure
No assumption on test suite or coverage
Require tools for constructing dataflow and
tools for dataflow analysis
Examples: Path Analysis




Takes set of program paths in P’
expressed as an algebraic expression
Manipulates the expression to get a set
of cycle-free exemplar paths.
Compare such paths in P with P’
Tests that traverse modified exemplar
paths will be selected
Examples: Path AnalysisInclusiveness


Selects only modified paths and omits
the cancel and new paths.
Not safe.
Examples: Path AnalysisPrecision

It will select all the test cases that are
modification-traversing and execute
modified exemplar paths.
Examples: Path Analysis
Examples: Path AnalysisEfficiency

Exponential in |P| and |P’|
Examples: Path AnalysisGenerality




Assumption: low-level program designs are
depicted by language-independent algebraic
representations.
Does not handle test cases for additions or
deletings of code.
Does not require any coverage criterian or
test generation technique.
Require tool for collecting traces at the
statement level.
Conclusions


Framework for evaluating regression
test selection technique that classifies
techniques in terms of inclusiveness,
precision, efficiency, and generality.
Several test selection techiques are
evaluated
Reference

[1]G.Rotherel. Efficient, Effective
Regression Testing Using Safe
TestSelection Techniques.
```