se320

Ensuring the product meets its specified requirements. Asks: 'Are we building the product right?'

Demonstrating the product meets its intended use when placed in the intended environment. Asks: 'Are we building the right product?'

1/3 planning, 1/6 coding, 1/4 component test and early system test, 1/4 system test with all components in hand (testing is about half the work)

Specification ~55%, design ~25%, code ~15%, other ~5%

Rises about tenfold per phase: ~\$1 in specification, \$10 in design, \$100 in code, \$1000 once released

A bug that has not yet been discovered

Software doesn't do what the spec says; does what the spec says it shouldn't; does something the spec doesn't mention; doesn't do something it should even though the spec doesn't mention it; or is hard to understand, hard to use, or slow

Find bugs as early as possible and make sure they get fixed, without chasing unattainable perfection

Most bugs originate in the specification, and missing requirements can't be caught by testing code later

A condition that causes a system to fail in performing its required function

The inability of a system or component to perform a required function according to its specification

The activity by which faults are identified and rectified

Inputs to test the program plus the predicted outcomes (according to the specification); a formal procedure where every step is subject to mistakes

A collection of test cases

A mechanism (a program, process, or body of data) that helps determine whether the program produced the correct outcome; often a set of input/expected-outcome pairs

Outcome is what we expect to happen as a result of a test; e.g., the screen not changing is a tangible outcome even though there is no output

The test gives the expected outcome even though the program performs the wrong computation (e.g., y = x² vs. y = 2x tested with x = 2); so a match doesn't strictly mean the test 'passed'

A relation S ⊆ I × O between the input space and the output space; ideally defines intended behavior for every input, in practice only for some

P is correct iff for each input in S's domain, P halts and returns a value in accordance with the specification

Find input values that reveal all faults (essentially proving the program correct); impossible, since no computable procedure exists (Howden, 1976)

Select inputs that increase our confidence that the program is correct

Functional: features the product supports (save, print, spell check). Non-functional: constraints on the product (security, reliability, usability, platform)

It gives a lower bound: everything testers do should be better than random testing, though random tests may reveal cases you never thought of

You may not know what the outcome should be, the developer may have a misconception, or the output may be too large to analyze; automate comparison when possible

It is impossible to test a program completely: all inputs, outputs, and paths are huge, and the spec must also be correct and complete

Software testing is a risk-based exercise: skipping inputs is a risk (financial loss, security, loss of life); too much testing is too costly, too little raises failure probability

The balance point between the cost of testing (rises with more testing) and the number of missed bugs (falls with more testing)

Testing cannot show the absence of bugs

'Program testing can be used to show the presence of bugs, but never to show their absence!' (Edsger Dijkstra, 1972 Turing Award)

The more bugs you find, the more bugs there are: bugs cluster because programmers have bad days, repeat mistakes, and some bugs are the tip of the iceberg

Test cases lose their effectiveness over time

Beizer's term: the more you test software, the more immune it becomes to your test cases; remedy is to keep writing new and different tests

Not all test cases are equal: some are more important, so prioritize them

Bugs can go undetected for a long time; heavy testing and wide use don't mean all bugs are found

Not all bugs found will be fixed: it may not really be a bug (spec wrong), too risky to fix, not worth it, or no time

Specifications are never final: software is a moving target (fierce competition, rapid releases, easy to change), unlike a bridge once construction starts

Software testing is a disciplined and technical profession (sophisticated techniques, tool support, rewarding careers)

A problem for which no algorithm solves it for all programs and all inputs

Asks whether a specific program terminates on a given input; undecidable (Turing and Church, 1936)

A corollary of the halting problem: predicting almost any non-trivial program behavior is undecidable

Is a statement reachable? Is a path feasible? Will an array index go out of bounds? Are two functions equivalent? Does the program meet its specification?

That 'programs can't find bugs in other programs'; correct reading: one program cannot perfectly tell you whether a certain bug exists

(1) Always report a bug when there is one, (2) always report no bug when there isn't one, (3) always give a definitive answer

Gives up (1): it misses some bugs but can still find many that exist

Gives up (2): it never misses a bug but may warn about bugs that aren't there (plays it safe)

It might run forever or run out of memory

Perfect bug-finding is impossible, but good bug-finding is possible

A static, abstract representation of a program: a directed graph G = (N, E) of statement and predicate nodes with edges showing flow of control

Represents a simple statement or a basic block; drawn as a circle

Represents a conditional statement; drawn as a rectangle with T and F edges

A sequence of statements treated as one unit and run one after the other

e is not a predicate; draw a chain of predicates e == v1, e == v2, ... then default; without break, a case falls through to the next case's statement

Predicate at the top; T goes into the body, which loops back to the predicate; F exits the loop

Initialization node, then predicate (e.g., j <= limit); T goes into body then increment node and back to predicate; F exits

A unique sequence of nodes (n1, ..., nt) where each consecutive pair is an edge in the graph

A path that starts at the first node and ends at the last node of the graph

A complete path that can be exercised by some input data

A subsequence of a path

A path in which all nodes are unique

A path in which all edges are unique

The conjunction of the individual predicate conditions at each branch point along a path; the input must satisfy it for the path to execute

A path that can be exercised by some input data

A path that no input can exercise, caused by contradictory predicates (e.g., x < 10 true then x < 20 false)

You may hunt for impossible tests; they may signal a control-flow error; future changes may make them feasible and untested; they come in clusters and are common

7 paths once short-circuit is expanded (4 true, 3 false), not 2

If the loop control variable is supplied externally (user input), the number of paths is unbounded

Begin with testing-in-the-small (a module or class) and move toward testing-in-the-large (the whole system)

Done by each developer; white-box; ensures each module (class, subprogram) is implemented correctly; looks at data structures, boundaries, error-handling paths, interfaces

Test code that calls the module under test

Test code that stands in for a module the module under test calls

Developers focus on writing code rather than tests, and an automation framework makes execution efficient but doesn't make testing adequate

Done by a small team in a short time frame; ensures the interfaces between components (which developers couldn't test) are implemented correctly

Integrate everything at once. Pro: whole system available. Cons: components may not all be ready, no component focus, errors harder to locate

Integrate piece by piece. Pros: focus on each module, easy to locate errors. Con: needs stubs and/or drivers

Top module tested with stubs; stubs replaced one at a time, depth first; a subset of tests re-run as modules are added

Worker modules grouped into clusters (builds) and integrated; drivers replaced one at a time, depth first

Top modules tested with stubs while worker clusters are integrated from the bottom

Done by a separate group; pretend to be end users; black-box; driven by use cases; focus on functionality plus recovery, performance, etc.; needs a System Test Plan

About 30% of the developer count is good (ideal ~5 testers per 10 developers); many companies give only ~25%

Requirements coverage, but testers must think beyond the stated requirements

Development and main phases done but not ready to release; friendly users exercise the release and report crashes and issues

Like alpha but the software is nearly ready to release, so fewer issues; more commonly used than alpha

The customer's final check before accepting the software; in practice customers often don't know what to do

Left side shows the reference material (requirements, architectural design, component design, code); right side shows the matching testing phase (acceptance, system, integration, unit)

A phase says when and at what scope you test (unit, integration, system); a type says what concern you test (performance, security, etc.)

Checks that the system does what the specification says

Tests the run-time performance of the software; start early by checking components against their performance budget

Executes the system so it demands resources in abnormal quantity, frequency, or volume to see how it handles heavy load

Evaluates behavior over a long period under normal and peak load (without stressing it); estimates failure rate and mean-time-between-failures; finds memory leaks

Forces the software to fail in a variety of ways and verifies that recovery is properly performed (e.g., one component slow or erroring)

Verifies that protection mechanisms built into a system will actually protect it from improper penetration

Identifies discrepancies between a product's user interface and the human engineering requirements of its potential users

Re-testing modified software to detect whether new faults were introduced into previously tested code

Retest-none, retest-all, or selective retesting; can be expensive

Uses the specification as the reference for test selection and adequacy (a.k.a. specification-based or functional testing); end-user perspective; criteria not precise; planning can start early

Uses the source code as the reference for test selection and adequacy (a.k.a. structural or program-based testing); precise criteria; assumes the code fully implements the spec

Neither; the real difference is how tests are generated and adequacy determined; neither can be exhaustive, so use both

Systematically reducing a huge set of possible test cases to a small but effective subset by grouping inputs into equivalence classes

Its members test the same thing or reveal the same bugs: if one input is handled correctly (or incorrectly), the others very likely are too

Identify all input sources, then for each, which groups should be treated differently; group similar inputs, outputs, and operations; it takes judgment and domain expertise

Negative numbers, zero, perfect squares, non-perfect squares, decimal numbers, non-numeric input; pick one test per class

Assures the software minimally works using simple, straightforward cases that don't try to break it

Cases designed to break the software and probe common weaknesses

Faults cluster near boundaries (off-by-one errors, < vs <=); test 'barely valid' and 'barely invalid' values

For each variable use min, min+, nominal, max-, max: 4n+1 tests for n variables

Adds min- and max+ to test values just outside the range; expected outcome may be unclear and the program may crash on bad types

Cartesian product of the 5-value sets (all variables extreme at once): 5^n tests; basic boundary value testing is a subset

Cartesian product of the 7-value sets (including min- and max+): 7^n tests

Equivalence partitions, the specification, and common sense (e.g., 0); also internal boundaries such as Integer.MAX_VALUE or file sizes

Cheap, targets where bugs cluster, and works well for several independent variables representing bounded physical quantities

Boundaries may not exist (phone numbers, booleans) or be explicit (triangle sides); can leave gaps even for numeric programs; not effective stand-alone, only as a complement

Input described by parameters and values; can't run all combinations, so choose a 'good' subset (e.g., 4 parameters x 3 values = 81 combinations)

A fault triggered by mishandling one particular part of the input

A fault triggered by mishandling a particular combination of two inputs

Each parameter value is exercised by at least one test

Each pair of parameter values is exercised by at least one test

Pick a default value per parameter and vary one at a time; covers every single value (9 tests for the 4x3 example) but ignores parameter interactions

A 2D array where, for any two columns, all pairwise combinations of values appear, evenly distributed (each the same number of times)

r = number of rows, v = number of values, P = number of parameters; e.g., L4(2^3), L9(3^4)

100% (9/9) of pairwise combinations, 33% (9/27) of three-way, 11% (9/81) of four-way, using 9 tests instead of 81

Systematic; guaranteed balanced pairwise coverage; catches interaction faults that default-values misses; beats random selection; constraints can be added; suspicious cases can be added manually

Don't exist for every number of parameters and values; if none exists, use the smallest known OA that fits (e.g., L9(3^4) for three 3-value parameters)

Neil Sloane's online library, or tools such as OATS (AT&T) or AETG (Telcordia)

Analyzing a program by examining its source code without executing it, looking for violations of good practice and specific errors

Complements testing but can't replace it (e.g., it won't notice a sort that sorts descending instead of ascending)

Executing the program with symbolic input values (x0, y0) instead of concrete data, tracking a symbolic state and symbolic path condition

A mapping from program variables to symbolic expressions

A first-order formula over the symbolic inputs that must hold for a path to execute; sent to a constraint solver

The halting problem: no algorithm works for all programs, so tools answer 'yes', 'no', or 'not sure'

Explores loops a small fixed number of iterations, caps the number of paths, and skips asynchronous paths, recursion, and function-pointer calls (it makes assumptions)

Each abstract state stands for many concrete states; the chosen domain limits what flaws can be found (e.g., relations between only two variables, integers only)

Tools must assume library behavior, so popular tools ship stubs/models for common libraries

Powerful tools run slower and are harder to learn but find less obvious bugs; weaker tools are faster but need more hints from the user

Infinite recursion, ignored return values, forgetting to throw an exception, null-pointer dereferences, comparing unrelated types

Early static analysis tool for C; syntax pattern matching that misses errors visible by following data and control flow

Use the tool from day 1 and resolve warnings before they accumulate

Every non-conditional statement is executed by at least one test; the weakest criterion

Can reach 100% without ever seeing a condition be false; coverage percentage depends on how many statements are in each branch

Every decision takes each possible outcome (true and false) at least once; stronger than statement coverage

Can be met without exposing a fault, and in compound decisions some conditions may never be evaluated (e.g., f() in A & (B | f()))

Every condition (a boolean expression with no boolean operators) in each decision takes both true and false at least once

For A ∨ B, tests (T,F) and (F,T) satisfy it but the decision is true both times, so it doesn't guarantee decision coverage

Every condition AND every decision takes both outcomes

For A ∨ B, tests (T,T) and (F,F) satisfy it but can't distinguish A ∨ B from A, B, or A ∧ B

Every combination of condition outcomes within each decision is exercised: 2^n tests for n conditions

Exponential cost: 30 conditions is about 1.07 billion tests

Every decision and condition takes all outcomes, and each condition is shown to independently affect the decision by varying only that condition; needs about n+1 tests

{(T,F), (F,T), (F,F)}

{(T,T), (T,F), (F,T)}

Write the truth table; for each condition find two rows that differ only in that condition and give different decision outcomes; reuse rows to minimize tests

Short-circuit operators (e.g., x != 0 && y/x > 15) and coupled conditions (e.g., (A ∧ B) ∨ (A ∧ C)) make some required tests infeasible

Criterion C1 subsumes C2 if every test suite satisfying C1 also satisfies C2

Multiple condition > MC/DC > Condition/decision > Decision (branch) > Statement

No; the A ∨ B example with (T,F) and (F,T) satisfies condition coverage but never makes the decision false

Draw the CFG, trace each test, mark covered statements, edges, and condition outcomes, then check criteria from strongest to weakest

Instrument the program (compiler flags, bytecode or source rewriting), count per basic block at run time, then map results back to source lines

Code that should exist but doesn't

A program can cover every path and still be wrong (feof() as loop condition ran one extra time); faults aren't just in your own logic, and the oracle matters

Covering all paths is not the same as testing all inputs, and loops make the number of paths huge