Testing Flashcards
Pure Random Generation
Randomly generate inputs to feed in a software
* Easiest way to do automatic test case generation
* Do not require any preparation and easy to
implement
* Problems
* Semantically redundant inputs
* E.g., for a simple program 10/x, providing any input
except 0 means the same
Rule-based Random Generation
Rule-based Random Generation
* Try to reduce redundancy
* Use rules
* Try boundary cases
* known boundaries, i.e., [-2^32, 2^32]
* Use distributions
* Generate random values following certain distribution
* Very effective if the distribution of input is known
* e.g, scores of a final exam
feedback-directed random
test generation
Build test inputs incrementally
* New test inputs extend previous ones
* In this context, a test input is a method sequence
* As soon as a test input is created, execute it
* Use execution results to guide generation
* away from redundant or illegal method sequences
* towards sequences that create new object states
* do not use duplicate and null objects
* do not use objects generated with exception
Input
classes under test
* time limit
* set of contracts are used as the test oracle
* Method contracts (e.g. “o.hashCode() throws no exception”)
* Object invariants (e.g. “o.equals(o) == true”)
Technique input/output
Input:
* classes under test
* time limit
* set of contracts are used as the test oracle
* Method contracts (e.g. “o.hashCode() throws no exception”)
* Object invariants (e.g. “o.equals(o) == true”)
* Output: test cases with weak oracle:
* Statement chains
1. Seed components from randomly generated tests
components = { …}
2. Do until time limit expires:
a.Create a new sequence
i. Randomly pick a method call m(T1…Tk) Tret
a) Tret is the return type of m(T1…Tk)
ii. For each input parameter of type Ti, randomly pick a sequence Si
from the components that constructs an object vi of type Ti
iii.Create new sequence Snew = S1; … ; Sk ; Tret vnew = m(v1…vk);
iv.if Snew was previously created (lexically), go to i
b.Classify the new sequence Snew
a. May discard, output as test case, or add to components
Search-based Testing
Deem test case generation as an optimization
problem
* Based on random testing, and focus on the input
domains
* Use code coverage as guidance
* Find input values that can achieve the best
coverage (i.e., statement coverage)
Optimization
Try to find the maximal or minimal value of a
certain function
* Numerous practical problems can be viewed as
optimization problem
* Least cost to travel to a number of cities
* Least camera to cover an area
* Distribution of stores to attract most customers
* Design of pipe systems with least material
* Put items into a backpack (with limited volume) with
highest value
Solutions of Optimization
- Hill climbing
- Start from a random point
- Try all neighboring points, and go to the point with
highest value, until all neighboring points has a value
lower than the current point - Easy to find a local peak
- Random-restart Hill climbing
- Restart hill climbing for many times
- To avoid local peaks
Annealing simulation - Improved hill climbing
- Has a probability to move (i.e., restart) after reached local peak
- The probability drops as time goes by
- Genetic algorithm (search-based SE)
- Simulate the process of evolution
- Start with random points
- Select a number of best points
- Combine and mutate these points
- Until no more improvements can be made
Transform Testing to Optimization
Transform Testing to Optimization
* What to optimize?
* Using code coverage as criterion
* Try to generate a test case that covers certain code
element (method, statement, branch, …)
* What’s the peak?
* Measure: how well we have solved the problem
* A simple fitness function
* How far is the already covered elements from the target
code elements
* Try to make the distance 0
Regression Testing is Slow(er)
Continuous integration systems run tests for each
change that developers commit/push.
Speeding up Regression Testing
Test Case Prioritization (TCP)
* prioritize test case to run failed test early
* Test-Suite Reduction(TSR)
* Select a subset of test cases
* Test-Suite Parallelization (TSP)
* Use more machines and testing resources
Test Case Reduction with Genetic
Algorithms
- Genetic Algorithm search along with fitness scaling
can be used to identify the most critical paths of
program and hence to minimize the test cases. - Fitness is evaluated computing total weight of
critical paths, by initially assigning weights to edges
of Control Flow Graph, with largest weights given to
edges more prone to errors. - Weights are mutated using probabilities.
Test Case Reduction with Clustering
- Clustering starts by collecting the test cases for a
given system and then we build the dataset by
selecting coverage and complexity. - Next, we use data mining techniques, such as K-
clustering, to group several test cases into a
particular cluster. - Finally, redundant test cases that have the same
distance to the cluster center point are removed.
Test Case Reduction with Fuzzy Logic
- The main objective of this approach is to prioritize
test cases according to their estimated potential to
violate a given program assertion. - Usually violating an assertion implies revealing a
programming fault. - Fuzzy logic techniques can be utilized to measure
the effectiveness of a given test case in violating an
assertion based on the history of the test cases in
previous testing operations. - Fuzzy logic means assigning to a statement a probability
of being “true” varying from 0 to 1.
Sample Syllabus with Fuzzy Logic
* A midterm will be given around mid term.
* The final will be given around final time.
* Homework will be assigned fairly regularly.
* The midterm and final each will normally count as a substantial part of
the grade.
* The homework will not be insignificant in counting as part of the grade.
* An excellent final will result in a somewhat excellent grade.
* Solid work in two of the three areas, midterm, final and homework, will
result in a solid grade.
* Good homework will offset poor exams somewhat.
* Your grade will be a fuzzified linguistic bureaucratic terminological
value.
* If you don’t understand this by the end of the quarter, your grade will
reflect it.
Coverage Based Test Case Reduction
Most priority is given to test that guarantee most
coverage (statement-based, path-based, data-path
based, …)
