C3 Flashcards
random testing
- identify input domain of the program
- for each input parameter, generate a random but legal value according to some probability distribution (typically uniform)
- determine expected value for each complete valid input
- apply the inputs to system under test (SUT)
- determine if program achieves the appropriate outputs
why random testing?
- cheap (may need more tests, but generating tests is easy)
- gives reliability criteria (probability theory)
- can be used without knowledge of input space, when code is not available and when large volume of data is necessary)
- useful complement to other testing techniques (eg. input space partitioning)
2 problems with random testing
prediction problems: uniform distribution for generating input values might easily be wrong, boundary cases or relevant single values might never be generated
reliability problems: criteria formally based only on number of tests, not on program size (but larger programs do have more faults)
the oracle problem
given a test case and an input, what is the expected output and how can we determine if the observed output is consistent with the expected output?
calculating program reliability
calculate for program P its failure rate theta that we assume constant
- theta is the probability that P will fail a given test
- 1 - theta is the probability that P will pass a given test
1/theta is the mean time to failure: the number of expected runs for P to fail at least once
- C, the confidence level, is the probability that at least one failure occurs in 1/theta tests
- 1 - C is the probability that no failure will occur in 1/theta tests
- the probability of universal success (N independent tests) = (1 - theta)^N
- the probability of at least one failure = 1 - (1 - theta)^N
we can calculate theta by upper bounding the probability of at least one failure in N tests by the confidence C
1 - (1 - theta)^N <= C
1/theta >= 1 / (1 - (1 - C)^(1/N))
number of needed tests given a failure rate theta and confidence C
log(1- C) / log (1 - theta)
criticism against random testing
- oracle problem
- unifrom-distributed based predictions can easily be wrong
- corner faults might escape detection
- reliability analysis does not account for program structure
in order to find most errors we should spread the test cases as much as possible using partitions (adaptive random testing)
P-measure
probability of finding at least one failing test case P_r = 1 - (1 - theta)^N
E-measure
expected number of triggering values E_r = N*theta
F-measure
expected number of test cases required to trigger an error in 1/theta runs with confidence C: F_r >= log(1- C) / log (1 - theta)
random versus partition testing
partition testing cannot perform worse than random testing
partition testing can be up to k times better than random testing, where k is the number of partitions if there are many small sub-domains and very few large ones.
adaptive random testing
spreads the test cases as much as possible
3 versions: PART, ART, MART
but requires large amounts of computations due to distance calculations and comparisons
Partition Based Adaptive Random Testing (PART)
for two dimensions:
1. R is the region delimited by C that goes from X_min, Y_min to X_max, Y_max
2. select random test T = X1, Y1 in R
3. it it is a failure, report failure and stop
4. otherwise, T splits R in 4 regions
5. select the largest of these areas and repeat from step 2
Bisection based Adaptive Random Testing
for two dimensions:
1. select random test in R
2. if it is a failure, report failure and stop
3. otherwise, split R in four EQUAL regions
4. for each region that has not been tested repeat the process from step 1
Basic Adaptive Random Testing (ART)
- select random test X
- if failure, report and stop
- otherwise, add X to executed tests T
- select k candidate random tests C = {X1, …, Xk}
- select X from C with the largest distance from executed tests T
- repeat the process from step 2
Mirror Adaptive Random Testing (MART)
- partition input space into k disjoint subdomains, one is chosen as source subdomain, others are mirror subdomains
- select random test X in source subdomain, execute this test case and stop if failure
- apply mirror function to test case X to generate a test case for each mirror subdomain and execute test cases in sequential order, stop if failure
- repeat steps 2 and 3 until first failure or stopping condition
