Software Testing 2

Software Testing 2

1. How to test interaction between modules?

   • (Integration Testing) IDEA: create graphs based on connections among software components and visit them
     • Connections are dependency relations, also called couplings
     • Call Graph
       • Most common graph for structural design testing
       • Nodes: Units/modules/components (in Java - methods)
       • Edges: Calls to units
       • Node coverage: call every unit at least once (method coverage)
       • Edge coverage: execute every call at least once (call coverage)
       • Edge pair coverage: seldom used, or different than EC
       • Prime path coverage: not useful, loops are not present
       • Call Graph on Classes
         • With respect to a Class, methods are its units/components
         • Graph coverage of a class, call graphs do not work very well
           • Especially for abstract data types
           • Individual methods might no call each other at all
         • Other types of testing are needed - do NOT use graph criteria!
     • Inter-procedural DU Pairs
       • In integration testing, we really only care about the interface
         • If we focus on the interface, then we just need to consider:
           • The last definitions of variables BEFORE calls and returns
           • The first uses of variables INSIDE units and AFTER calls
           • coupling DU-path
       • Last-def: The set of nodes that define a variable x and have a def-clear path from each node through a callsite to a use in the other unit
       • First-use: The set of nodes that have uses of a variable y and for which there is a def-clear and use-clear path from the callsite to the nodes
       • Use-clear path wrt. x: A path from between two nodes over which variable X is not used (accessed)
       • Coupling DU-path: A path from a last-definition of a variable in a unit to the first use of the same variable in a different unit
         • Can be from caller to callee (parameter or shared variable)
           • Or from callee to caller as a return value
         • Coupling DU-path coverage criteria
           • All-coupling-def coverage: cover a path from every last-def to at least a first use
           • All-coupling-use coverage: cover a path from every last-def to every first-use
           • All-coupling-DU-paths coverage: cover every simple path from every last-def to every first-use
           • Coupling Data Flow Notes
             • Only variables that are used or defined in the callee are considered - last-defs without first-use cannot be tested
             • Transitive DU-pairs are too expensive to handle - A calls B, B calls C, and there is a variable defined in A and used in C
             • Arrays: A reference to one element is considered to be a reference to all elements
             • Only test your code, not calls to well-known/tester libraries, e.g., java.lang.Math

2. Combinatorial Coverage

   • Combinatorial Coverage (CoC): each clause of a predicate should evaluate to each possible combination of truth value
   • Sometimes called Multiple Condition Coverage
     • N clauses -> 2^n tests
     • Impractical for predicates with more than 3 or 4 clauses
   • Making clauses active
     • One way to reduce the number of combinations but still test clauses when they have an impact
     • Test each clause independently from the other clauses (using as few combinations as possible)
     • This idea is also known as "making clauses active"
     • Consider following: (a OR b) AND FALSE
       • Only the last clause counts!
       • To really test the results of a clause, the clause should be the determining factor in the value of the predicate
     • Determination: A clause Ci in predicate p, called the major clause, determines p if and only if the values of the remaining minor clauses Cj are such that changing Ci changes the value of p
       • Determining Predicates
         • Goal: Find tests for each clause when the clause determinates the value of the predicate
         • This is formalized in several criteria that have subtle, but very important, differences
         • EXAMPLE
           • P = A || B
             • if B = true, p is always true
             • so if B = false, A determines p
             • if A = false, B determines p
           • P = A && B
             • if B = false, p is always false
             • so if B = true, A determines p
             • if A = true, B determines p
     • Active Clause Coverage
       • Active Clause Coverage (ACC): For each p in P and each major clause ci in Cp, choose minor clauses cj, j != i, so that ci determines p. We have two test requirements for each ci : ci evaluates to true and ci evaluates to false
       • p = a || b
         • 1) a = true, b = false 2) a = false, b = false
           • a is major clause
         • 3) a = false, b = true 4) a = false, b = false
           • b is major clause (4 is duplicate of 2)
       • 3 TRs vs 4 TRs in CoC
         • This is a form of Modified Condition/Decision Coverage (MCDC), which is required by the aviation authorities (FAA, EASA) for safety critical software
       • Three variants of ACC
         • General Active Clause Coverage: minor clauses DO NOT NEED TO BE THE SAME when the major clause is true and when false
         • Restricted Active Clause Coverage: Minor clauses MUST BE THE SAME when the major clause is true and when false. Common interpretation used by aviation developers
         • Correlated Active Clause Coverage: Minor clauses MUST BE DIFFERENT and cause the PREDICATE TO CHANGE VALUE
         • NOTE: A given coverage criteria must be applied to each predicate in the program/specification

3. Specification based testing

   • Software specifications (specs) - documents describing the expected functionality and technical details of a software application or system
   • Specifications can be formal or informal
     • Formal specs are usually expressed mathematically
     • Informal specs are usually expressed in natural language
   • An implementation may or may not reflect the specification
   • Most specification language include
     • Some structure and sometimes diagrams
     • Explicit logical expressions, so it is very easy to apply logic coverage criteria
     • Description of the interfaces of the system
   • Testing based on specification -> specification-based testing or black-box testing

4. Input Space Partitioning

   • Problem:
     • Given a program
       • We do not have access to the source code
         • But we know:
           • What the program should do (specification)
             • Triang() classifies a triangle based on its sides, s1, s2, s3 as: scalene, isosceles, equilateral, not a triangle
           • Its interface (parameters): Triang(int s1, int s2, int s3)
         • What combinations of input values should we test? What values for s1, s2, s3?
   • Input Domains
     • The input domain to a program contains all the possible inputs to that program
     • For even small programs, the input domain is so large that it might as well be infinite
     • Ideally, the test selection problem is to select a subset of the input domain such that its execution will reveal all errors
     • In practice, the test selection problem is to select a subset of the input domain, within budget such that it reveals as many errors as possible
     • Input parameters define the scope of the input domain - Parameters to a method, Data read from a file, Global variables, User level inputs
     • Testing based on the Input Domain
       • Step 1: Identify testable interfaces
         • Step 2: Find all the parameters
           • Step 3: Develop characteristics
             • Step 4: Apply a test criterion to choose combinations of values
               • Step 5: Refine combinations of blocks into test inputs
             • 3.1 Interface-Based Approach
               • Develops characteristics directly from individual input parameters
               • Mechanically consider each parameter in isolation -> different IDM!
               • Simplest application
               • Can be partially automated in some solutions
               • This is an easy modelling technique and relies mostly on syntax
               • Some domain and semantic information won't be used
                 • Ignores relationships among parameters
                 • Could lead to an incomplete partitioning
             • 3.2 Functionality-Based Approach
               • Develops characteristics from a behavioural view of the program under test
               • Identify characteristics that correspond to the intended functionality -> one IDM
               • Can incorporate domain and semantic knowledge
               • Modelling can be based on requirements, not on implementation (interface)
               • Can use relationships among parameters
               • Harder to develop - requires more design effort
               • May result in better tests, or fewer tests that are as effective
             • Better to have more characteristics with fewer blocks - Fewer mistakes nad fewer tests
   • Partitioning Domains
     • Domain D - All possible values that input parameters can have
     • Partition scheme q of D - A split of the domain based on some rules (characteristics of the domain)
       • The partition q defines a set of blocks, Bq = b1, b2, ... bq
         • Blocks are also called equivalence classes
         • All the members in a block contribute to fault detection in the same way
       • The partition must satisfy two properties:
         • Blocks must be pairwise disjoint (no overlap)
         • Together the blocks cover the domain D (complete)
     • Choosing Partitions
       • Choosing (or defining) partitions seems easy but is easy to get wrong
   • Benefits of ISP
     • Can be equally applied at several levels of testing: Unit, Integration, System
     • Relatively easy to apply with no automation
     • Easy to adjust the procedure to get more or fewer tests
     • No implementation knowledge is needed: Just the input space, Black-box testing

5. Test automation levels

   • Problems of Software Testing
     • Time is limited
     • Applications are complex
     • Requirements are fluid
   • Manual Testing
     • + easy & cheap to start, + flexible testing, - expensive every execution, - no auto regression testing, - ad-hoc coverage, - no coverage measurement
     • Testers are often perceived as bottlenecks to the delivery of software products
     • They are being asked to test more and more code in less and less time
   • Test Automation
     • Use of software to control the execution of tests
     • Automates:
       • Test execution
       • Comparison of actual outputs to expected ones
       • Setting up of test preconditions (e.g., login before booking)
       • Other test control and test reporting functions
     • Flavors
       • Capture-replay tools
         • Capture-Replay Testing
       • Test automation frameworks
         • Script-Based Testing
       • Keyword-driven Testing
       • Model-Based Testing
         • Model-based testing is a testing technique where the runtime behaviour of an implementation under test is checked against predictions made by a formal specification, or model.
           • An abstract model describes the expected behaviour of a system under test (SUT)
           • Design abstract tests automatically from the model (based on some heuristics)
           • Execute the concrete tests to see if the SUT behaves as expected - Concrete tests: test inputs in a format understandable by SUT
         • Fundamental tasks of MBT
           • General idea: Create a behavioural model of the SUT. Generate tests by covering it based on different coverage criteria
             • Step 1: Understand the System
               • What is the system doing? Does it have states? Does it have timing deadlines? Is the system deterministic? Any probabilistic behaviour? How do we access the system? etc...
             • Step 2: Choose the Model
               • Depending on the SUT and what we want to test
                 • State Table, Finite State Machines, Statecharts, Message Sequence Charts, Timed Automata, Markov Chains, Probabilistic timed automata, Grammars, Etc...
                   • Finite State Machines are Common
                     • FSMs can accurately model many kinds of software
                       • Embedded and control software (think electronic gadgets)
                       • Abstract data types
                       • Compilers and operating systems
                       • Web applications
                     • Creating FSMs can help find software problems
                     • Numerous languages for expressing FSMs
                       • UML statecharts
                       • Automata
                       • State tablets
                       • Petri nets
                     • Limitations: FSMs are not always practical for programs that have lots of states (for example, GUIs)
                     • A CFG is not an FSM!!!
                       • CFG describe the structure, FSM the behaviour of the software
                       • CFGs have no notion of events for triggering edges, FSMs do
                       • In CFGs predicate nodes only have two exiting edges leading to two distinct nodes, while in FSMs a state can be the source of many transitions
                       • CFGs have only one start node, while FSMs can have a set of start nodes. The start node of the CFG has no incoming edges, while in FSM the start nodes may have incoming transitions
                       • In CFGs there is no self-looping edges, i.e. edges whose source and target nodes are the same. FSMs allow for self-looping transitions
                       • In CFGs there is only one edge of each direction between two nodes, while in FSMs there is no limitation on the number of transitions between states
                     • Covering FSMs
                       • Node coverage: execute every state (state coverage)
                       • Edge coverage: execute every transition (transition coverage)
                       • Edge-pair coverage: execute pairs of transitions (transition-pair)
                       • Data flow
                         • Nodes often do not include defs or uses of variables (actions on transitions)
                         • Defs of variables in triggers are used immediately (the next state)
                         • FSMs typically only model a subset of variables
                         • Assignment of variables is not always modelled, uses are visible
                         • Defs and uses are usually computed for guards
                       • Logic Coverage - guards and preconditions are predicates
                       • Creating FSMs is often harder than covering them
                 • Not an easy task. Requires understanding of several formalisms
             • Step 3: Build the Model
               • There is no clear recipe
               • It depends on the SUT, model type, aspects to be tested, level of abstraction, etc...
               • General steps: Identify inputs and outputs of the system, identify states of the system, which inputs can be received in each state, which outputs can be sent in each state, which output values (range of values) correspond to each input, deterministic/non-deterministic? etc...
             • Step 4: Generate Tests
               • Decide what to test -> Coverage criteria
                 • Create test requirements - Sometimes called test targets or test goals
                   • Similar to source code: Identify structures: graphs, predicates; Define test requirements for selected coverage criteria; Compute reachability conditions - Similar to graph coverage for FSM, several test inputs may be required from reaching a a given predicate; Identify inputs to satisfy test requirements (not always easy); Etc...
             • Step 5: Concretize Tests
               • Abstract tests: "steps" in the FSM
               • Concrete tests: "steps" that interact with the SUT, based on its interface
               • Concretization also called test adaption
             • Step 6: Execute Tests
               • Execute tests against the SUT and check the output
               • Two flavours: offline and online
                 • Offline testing (scripting): Tests are first generated and written in a programming language like jUnit by a MBT tool; Tests are executed by a test execution framework as a batch, eg jUnit; The execution framework analyses test results (verdict assignment); Allows to use complex (slow) search based algorithms to design the tests
                 • Online testing (on-the-fly): Abstract tests are executed during the test generation, one test input at a time; An adapter converts abstract test inputs into concrete test inputs; The next test is chosen based on the previous output; MBT tool generates, executes and analyses the results; Requires fast algorithms (walking alg. or light serach based alg.)
             • Step 7: Analyze results
               • How many tests generated?
               • Do we satisfy selected coverage criteria and coverage level? - If not, generate more tests
               • If tests fail, where is the problem (fault)? - in the implementation, in the model or in the tool chain?
               • Debugging: identifying the source of the failure
               • Fix the system and generate again
           • Practical thoughts
             • Benefits of MBT
               • Obstacles to MBT
                 • Testing effort shifts to modelling and tool chain support
                 • Does not always scale well for very large (industrial) systems -> abstraction
                 • Need testers who can design and model
                 • Modelling still not mainstream in many organizations
                 • Models can be a significant upfront investment
                 • How can we measure and enforce the quality of models? - Static model validation, behaviour validation
                 • The quality of tests? Is number of test cases, coverage, enough faults discovered?
               • Automation of test design
               • Reduction of total testing time
               • Tolerant to changes in requirements
               • Manage the model instead of test cases
               • Forces detailed understanding of the system specification by testers
               • Early fault detection - Model creation helps in detecting misinterpretation and inconsistencies in requirements and specifications
             • When to apply MBT? Whenever possible
               • Apply black-box testing to a Unit, Module, Component, Sub-system, System
               • We have information sources (reqs, specs) available to create the model
               • A behavioural model of the SUT can be created
               • We have proper tooling available
             • At what level of abstraction of V & V?
               • A tradeoff between the complexity of modelling and benefits

6. Logic Coverage

   • Logic Predicates and Clauses
     • A predicate is an expression that evaluates to a boolean value
       • Predicates can contain: boolean variables, non-boolean logical expressions (that contain >, <, ==, >=, <=, !=), boolean function calls
     • The internal structure is created by logical operators: the negation operator, the and operator, the or operator, the implication operator (if p then q), the exclusive or operator, the equivalence operator
     • A clause is a predicate with no logical operators
   • Testing and Covering Predicates
     • We use predicates in testing as follow:
       • Developing a model of the software as one or more predicates
       • Requiring tests to satisfy some combination of clauses
     • Predicate Coverage
       • Predicate coverage (PC): For each p in P, TR contains two requirements: p evaluates to true, and p evaluates to false
       • When predicates come from conditions on edges, this is equivalent to edge coverage
     • Clause Coverage
       • PC does not evaluate all the clauses, so...
         • Clause Coverage (CC): For each c in C, TR contains two requirements: c evaluates to true, and c evaluates to false
     • Problems with PC and CC
       • PC does not fully exercise all the clauses, especially in the presence of short circuit evaluation - (a OR b) AND FALSE
       • CC does not always ensure PC - That is, we can satisfy CC without causing the predicate to be both true and false
       • The simplest solution is to test all the combinations...
   • Summary
     • Predicates are often very simple - in practice, most have less than 3 clauses
       • In fact, most predicates only have one clause
         • With only one clause, PC is enough
           • With 2 or 3 clauses, CoC is practical
             • Advantages of ACC criteria significant for large predicates
               • CoC is impractical for predicates with many clauses
                 • Control software often has many complicated predicates, with lots of clauses

Bilder und Dateien der Mindmap