# Review of Software Validation for Midterm

This is a review of the material for my soft. validation course before the midterm. Includes black box, white box, and grey box testing. There’s a lot of missing stuff here probably, but a basic outline of the slides seems to be here.

### Introduction

• McCall’s model of software quality factors tree
• TODO: insert image here
• Soft. Quality Factors
• Correctness
• Reliability
• Efficiency
• Integrity
• secure
• usability
• maintainability
• flexibility
• testability
• portability
• reusability
• interoperability
• V & V
• Validation
• are we building the right product?
• perform at the end of development to ensure compliance with product requirements
• Verification
• are we building the product correctly?
• performed @ end of each dev phase to ensure previous requirements are met
• TODO: insert image (slide 45 lec 1)

### Software Testing

• Basic testing defs.
• errors
• people commit errors
• fault
• result of an error in docs, code, etc.
• failure
• occurs when a fault executes
• incident
• consequences of failures - may or may not be apparent to the user
• software testing
• reveal faults as failures
• test cases (obviously)
• test stub
• partial implementation of component on which the tested component relies
• test driver
• partial implementation of a component that exercises and depends on the tested component
• TODO: insert pic from slide 6 lec 2
• testing axioms
• a system tends to build resistance to a particular testing technique (i.e. ppl start to build systems that explicitely pass only the tested techniques, but not others)
• unobserved bug is latent
• Types of testing
• unit testing
• integration testing
• system testing
• acceptance testing
• installation testing
• regression testing
• V-Model of Development
• TODO insert slide 18 pic here lec 2

### Black Box Testing

#### Equivalence class partitioning

• Partition the variables into possible classes of inputs
• Weak equivalence class testing
• One variable value from each equivalnce class
• Strong equivalence class testing
• Based on cartesian product of the partition subsets (test all class interactions)
• ECP is good for functions with ranges of inputs (i.e. numbers) or sets
• Some good characteristics
• if input is a range of valid values, define:
• one valid EC (within the range) and
• two invalid EC (one outside each end of the range)
• if input is a number (N) of valid values, define:
• one valid EC and
• two invalid ECs (none and more than N)
• if input is an element from a set of valid values, define:
• one valid EC (within set) and
• one invalid EC (outside set)
• if input is a “must be” situation (condition), define:
• one valid EC (satisfies condition) and
• one invalid EC (does not satisfy condition)
• if there is a reason to believe that elements in an EC are not handled in an identical manner by the program:
• subdivide EC into smaller ECs
• consider creating equivalence partitions that handle the default, empty, blank, null, zero, or none conditions
• Myer’s Test Selection Approach
• until all valid ECs are covered write TCs that cover as many valid classes as possible
• until all invalid ECs are covered write TCs that cover ONLY ONE invalid EC

#### Boundary value analysis

• Focus on edge cases
• Use input variable values within a class at their minimum, just above their minimum, their nominal value, just below their maximum, and at their maximum
• For each boundary condition:
• include boundary value in at least one valid test case
• include value just beyond boundary in at least one invalid test case

#### Category Partitioning

• Has BVA, ECP, but adds contraints between classes
• Identify categories and environmental conditions (i.e. internal states)
• per variable, characteristics of a parameter (array size, browsers, etc.)
• Partition categories into choices
• e.g. array size -> (100, 0, 1), browsers -> (IE, Firefox, Safari)
• Determine constraints among the choices
• i.e. how the choices interact, how the occurrence of one choice can effect the existance of another
• e.g. OS must be Windows if browser is IE
• Create test frames as a selction of choices
• Criteria for coverage
• All combinations
• every choice used with every other choice in every other category if possible
• Each choice
• Weaker, one value for each choice in each category at least once in a test case
• Base choice
• Compromise, a base choice chosen for each category and tested
• Non base choices are varied, but the base choice is constant

#### Decision Table

• Make a table with all your conditions for your inputs. Say for a triangle method telling you whether it is scalene, isosceles, or equilateral, you have 3 input variables then the table might look like:
• TODO: insert slide 67 pic lec. black box

#### Binary Decision Diagram

• Essentially a compact representation of a decision table
• Nodes represent boolean variables (conditions?)
• Left branch always false, right always true
• Leaf represents a resultantvalue for condition on the path from root to leaf
• Map to a BDD Determinant Table

#### Cause-Effect Graph

• a node is drawn for each cause and effect; nodes are placed on opposite sides of a sheet
• a line from a cause to an effect indicates that the cause is a necessary condition for the effect
• if a single effect has two or more causes, the logical relationship of the causes is annotated by symbols for logical and (∧) and logical or (∨)
• a cause whose negation is necessary is shown by a logical not
• a single cause may be necessary for many effects; a single effect may have many necessary causes
• intermediate nodes may be used to simplify the graph and its construction
• Deriving a decision table
• a row for each cause or effect
• a column corresponds to a test case
• work with a single effect at a time
• set effect to true
• look backward for all combination of inputs which will force effect to be true, subject to constraints
• create column for each combination
• determine state of other effects for each column
• graphs to logical formulae
• generate an initial function
• start from effect
• backtrack through graph
• substitute higher level clauses with lower level clauses and Boolean expressions, until you reach cause nodes
• Transform into minimal DNF form (a bunch of and statement groups strung together by ors)
• TODO: logic formulas on slide 89
• test generation
• each-condition/all-conditions
• for each variable include a variant such that the variable is made true with all other variables being false
• one variant such that all variables are true
• one variant such that all varaibles are false

### White box testing

• Control flow graph
• Nodes are blocks of sequential code statements
• edges are transfers of control (may be labeled with predicate representing the conditon of control transfer)
• intermediate statements in a sequence of statements are not show as long as there is no more than one exiting edge and not more than one entering edge + Coverage
• Statement/Node coverage
• All instructions executed
• Cover all nodes in the control flow graph
• weak
• incomplete
• Branch/Edge Coverage
• each edge is traversed at least once, exercise all conditions with at least one testcase having that condition as true and once as having that condition as false
• incomplete
• Condition coverage
• Each condition constituent evaluated to true at least true once and to false at least once (so if (a < b) && (b > c): (a<b),(b>c) are constituents
• Modified Condition/Decision coverage
• same as condition coverage with added rule
• there must exist a pair of test cases where only one condition (constituent) changes and the outcome changes too
• requires n+1 testcases
• Path Coverage
• does not imply condition coverage
• cover all possible control paths
• Loop coverage
• minimal coverage should execute the loop
• zero times
• once
• = twice

• More extensively
• min - 1
• min + 1
• min
• typical
• max - 1
• max + 1
• max
• nested loops
• start at innermost loop
• set all outer loops to min value
• set all other loops to typical value
• test cases for single loop (min, typical, max, etc.) for innermost loop
• move up in nested loop level
• If outermost loop do all nested cases simultaneously (i.e. all the same from min-1 to max+1)
• Data flow diagram
• definition of a variable is when it is assigned
• c-use is when a variable is used in computation (addition, assignment, etc.) Also a return statement is a c use because it is an assignment
• p-use is when a variable is used in a conditional statement
• in marking lines of code with, cpd, uses definitions always go last
• Data flow graph is pretty much a control flow graph with these cpd uses labelled. Cannot collapse lines if a node is annotated
• Paths and pairs
• Complete Path
• initial node is a start node, final node is exit node
• Simple path
• all nodes except possibly first and last are distinct
• Loop free path
• all nodes are distinct
• def-clear path
• with respect to v: any path starting from a node at which variable v is defined and ending at a node at which v is used, without redefining v anywhere else along the path
• Du-pair with respect to a variable, v
• (d, u) where d is node where v is defined and u is node where v is used, with a def-clear path with respect to v from d to u
• du-path is a path $P = <n_1, …, n_k>$ such that $d(v, n_1)$ and either one of the two cases following:
• c-use of v at node $n_k$ and P is a def-clear path with respect to v (can have loop)
• p-use of v on edge $n_j$ to $n_k$ and P is a def-clear loop-free path
• Coverage
• all-defs
• at least one def-clear path from every defining node of v to at least one use of v, be that c-use or p-use
• all-uses
• at least one def-clear path from every defining node of v to every reachable use of v
• all-p-uses/some-c-uses
• At least one def-clear path from every defining node of v to every (reachable) p-use of v, if none, then to a c-use
• all-c-uses/some-p-uses
• at least one def-clear path from every defining node of v to every (reachable) c-use of v, if none to a p-use
• all-du-paths
• all du-paths covered
• Mutation testing
• fault-based testing
• create mutant programs from your code, each differing from the original in one small way
• test on the mutants, if test data detects all mutants the the mutants are said to be dead and the test set is adequate
• automated generation of mutants
• mutant operators (predefined program modification rules corresponding to a fault model
• types of mutants
• stillborn
• syntactically incorrect, killed by compiler
• trivial
• killed by almost any test case
• equivalent mutant
• always produces the same output as the original program
• avoid those ^^^^
• Some mutation operators
• statement deletion
• statement duplication
• statement insertion
• replacement of Boolean expressions with true or false
• replacement of arithmetic operators with others
• replacement of conditional expressions
• negation of conditional expressions
• good indicators of test effectiveness
• complete coverage equates to killing all non-equivalent mutants
• amount of coverage is called mutation score (ratio of dead/non-equivalent mutants)

### Gray Box Testing

• limited knowledge of system internals
• State-Based testing
• have a state transition diagram
• Bashir and Goel’s approach is based on data slices and can be used for simpler classes, but more complex modal classes should have their behaviour modeled by a state-transition model?
• two states are equivalent if the output for all inputs of the state is the same
• Coverage
• State coverage
• Transition Coverage
• Fault Taxonomy
• missing or incorrect transition to a valid state, based on a correct input is a transfer fault
• missing or incorrect output (action) based on a correct input and transition is an output fault
• corrupt state is when based on a correct input, the implementation computes a state that is not valid (additional state)
• sneak path (extra transition) is when the implementation accepts a valid input that is ilegal or unspecified for a state
• illegal input failure is when the implementation fails to handle an illegal message correctly (incorrect output, state corrupted)
• trap door is when the implmentation accepts undefined messages
• State Based Testing (note: on a diagram per this class the transitions will be marked with format (event) / (action)
• All states
• All events (events consumed at least once)
• All actions (all actions produced at least once)
• All transitions
• all explicit transitions taken at least once
• implies all states/events/actions
• all n-transitions sequences is another variation where you take all sequences of transitions of length n
• transition tour method
• path starting at initial state traversing as many transitions as possible and ending at the final state (or back at initial)
• Full Predicate Coverage
• clause: boolean expression that contains no Boolean operators (AND, OR, NOT, etc.)
• predicate: Boolean expression that is composed of clauses and zero or more Boolean operators - a clause may appear more than once in a predicate
• full predicate coverage: tries to determine whether each clause in a transition predicate (guard condition) is ncessary and formulated correctly
• so for all transitions need to test pairs of each clause
• Transition pair coverage
• need to make sure possible pairs of transitions are tested
• Complete sequence coverage
• impractical or impossible
• N+ Test strategy
• reveals
• all state control faults
• all sneak paths
• many corrupt states
• procedure
• derive round-trip path tree from state model (state model needs to be flattened)
• generate the round-trip path test cases (conformance test cases)
• generate sneak path test cases
• sensitize transitions in each test case
Written on October 14, 2014