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
    • pesticide paradox
      • 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