Show Menu
Cheatography
  1. Home >
  2. Cheat Sheets >

ASE Notes Second Copy Cheat Sheet (DRAFT) by

ASE ntoeskdjsqnjwvuioedhih

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Single target approach

- Targeting one branch­/st­atement at a time.
- Chromosome = test case.
- Running genetic algorithm multiple times.
Fitnes­s(b1) = approa­ch_­lev­el(b1) + branch­_di­sta­nce(b1)

Single­-target approach

Single­-target approach:
1. Select one target (statement or branch) to cover.
2. Run GAs until reaching the maximum search budget (max iterat­ions) or when the target is covered (fitness function = 0).
3. Repeat from step 1. for a new target (statement or branch).

One-point crossover

One-point crossover (proba­bility = 0.8).
It takes two parents and cuts their chromosome strings at some randomly chosen position and the produced substrings are then swapped to produce two new full-l­ength chromo­somes.

Selection

Select the best parent in the population to generate offspr­ings.

Automated test case generation

Ingred­ients:
1. Solution repres­ent­ation.
2. Fitness function.
3. Selection.
4. Reprod­uction (crossover and mutation).
The goal of automated test case generation is the automatic generation of test cases using genetic algorithms in order to achieve the maximum statement coverage.

No free lunch theorem

Theorem: given a search budget m (e.g. time), the probab­ility of reaching the near optimal value f* using algorithm A is the same as the probab­ility of obtaining the same near-o­ptimal value using another arbitrary algorithm B.

Genetic algorithms (GAs)

Natural selection: indivi­duals that best fit the natural enviro­nment survive (worst die).
Reprod­uction: survived indivi­duals generate offsprings (next genera­tion).
Mutation: offsprings inherit properties of their parents (with some mutati­ons).
Iteration: generation by generation the new offspring fit better the enviro­nment than their parents.

Hill climbing variables

Random­-re­start hill climbing: random restart when no improving solution is found (or improv­ement is small).
Stochastic hill climbing: while classic hill climbing always picks the best neighbour (the steepest uphill move), stochastic hill climbing randomly chooses amongst the uphill moves.

Hill climbing

1. Start with a random solution A.
2. Try some 'nearby' solutions (A + delta) and (A - delta).
3. Take the best solution among A, (A + delta) and (A - delta).
4. Repeat from step 1.
Local search => converges toward local optimum.

Search­-based software engine­ering

Search­-based software engine­ering is the applic­ation of meta-h­eur­istic search­-based optimi­sation techniques to find near-o­ptimal solutions in software engine­ering problems.
Key elements:
- Repres­ent­ation: represent a candidate solution for a problem.
- Fitness function: distin­guishes good solutions from bad solutions; shapes the fitness landscape.
- Manipu­lation operators: move from a solution to another.
 

Genetic algorithms

Pseudo­-code:
Pop = {x0, ..., xN}
x_opt = NULL
LOOP
assign­Fit­nes­s(Pop)
x_opt = best(Pop, x_opt)
Pop = select­(Pop)
Pop = reprod­uce­(Pop)
END LOOP
RETURN x_opt

Many objective optimi­sation

- Targeting all branches at once.
- Chromosome = test case.
- Running many-o­bje­ctive genetic algori­thms.
- Usage of the archive.

Disadv­antages of hill climbing

Local maximum:
- A state is better than all of its neighbours but not better than some other states.
Plateau:
- A flat area of the search space in which all neighb­ouring states have the same value.
Ridge:
- Orient­ation of the high region that, compared to the set of available moves, make it impossible to climb up.

Solution repres­ent­ation

The chromosome used for test case generation is the input vector (sequence of input values used by the test case to run the program) which may be fixed length or variable length).
Each candidate solution (chrom­osome) represents a set of parame­terised arguments for the test.

Collateral coverage

When a target is covered accide­ntally in case generation cycle, it is removed from the list of yet uncovered target and the corres­ponding (covering) test case is stored to form the final suite.
Collateral coverage: if a test case involved in collateral coverage are not detected and stored, it can be shown that random testing performs asympt­oti­cally better than search­-based testing.

Roulette wheel selection

Roulette wheel selection:
1. Assign to each test case a probab­ility equal to 1/f (inverse of the fitness score).
2. Normalise the obtained probab­ility.
3. Each test case has a probab­ility to be selected that is propor­tional to its slice in the roulette wheel.

Tournament selection

Binary tournament selection:
1. Randomly choose pairs of test cases (solut­ions).
2. Select the fittest (better) indivi­duals from each pair.

Multi-­point crossover

It is an extension of the single point crossover that uses multiple cut-points instead of a single one. It takes two parents and cuts their chromosome strings at k randomly chosen cut positions and the produced substrings are then swapped over k point to produce two new full-l­­ength chromo­­somes.

Search algorithms

Optimi­sation algorithms involve applying a search­-al­gorithm to solve (minimise or maximise) such as the fitness function => find the best solution.
Local search:
- Hill climbing.
- Simulated annealing.
- Tabu search.
Typically single­-so­lution.
Global search:
- Random search.
- Genetic algori­thms.
- Particle swarm optimi­sation.
Typically popula­tio­n-b­ased.
 

Many objective optimi­sation

Limita­tions of single targets

Some coverage targets may be feasible.
Some coverage targets may be very difficult to achieve.
Since a limited search budget is available for test case genera­tion:
- Infeasible targets may use the search budget without reaching any target.
- Difficult target may use most of search budget, leaving lots of easier coverage target uncovered.
- The order in which targets are considered affects the final results.

Example

The final test suite consists of all chromosome that have been found to cover (even accide­ntally) one or more yet to cover statem­ents.

Many objective optimi­sation

Mutation

Mutation: randomly change some genes (elements within each chromo­some).
Mutation probab­ility: 1/n where n = chromosome length.

Branch distance

Branch distance: given the first control node where the execution diverges from the target t, the predicate at such node is converted to a distance (from taking the desired branch), normalised between 0 and 1. Such a distance measure how far the test case is from taking the desired branch. For boolean and numerical variables, the table is shown.

Approach level

Given the execution trace obtained by running program P with input vector x, the approach level is the minimum number of control nodes between an executed statement and the coverage target t.

Computing fitness

Single­-target approach, 8 is the target.

Automated test case generation

The goal of evolut­ionary testing is to archive some sort of code coverage.

Genetic algorithms

Genetic algorithms must maintain a balance between the exploi­tation and explor­ation as to increase the probab­ility of finding the optimal solution.
Exploi­tation: find nearby better solutions by promoting beneficial aspects (genes) of existing solutions.
Explor­ation: find new solutions in different regions of the search space by generating solutions with new aspects.

Random search

Random search involves trying random values and taking the best trial.
Trivial but effective in some cases:
- Fast generator of solution.
- Lot of time needed (budget).
- Used as baseline.
'Sophi­sti­cated' random search exists.

Search problem

Find a value (solution) x* which minimizes (or maximizes) the objective function f over a search space X.
Search space: all possible solutions.