Introduction to Software Testing Chapter 6 Input Space

Introduction to Software Testing Chapter 6 Input Space Partition Testing Paul Ammann & Jeff Offutt https://www.cs.gmu.edu/ offutt/softwar etest/

Ch. 6 : Input Space Coverage Four Structures for Modeling Software Input Space Graphs Logic Applied to Applied to Specs Specs Design Introduction to Software Testing, Edition 2 (Ch 6) Applied to FSMs Source Source Syntax DNF Source Use cases Models Integ Ammann & Offutt Input 2

Benefits of ISP Equally applicable at several levels of testing – Unit – Integration – System Easy to apply with no automation Can adjust the procedure to get more or fewer tests No implementation knowledge is needed – Just the input space Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 3

Input Domains Input domain: all possible inputs to a program – Most input domains are so large that they are effectively infinite Input parameters define the scope of the input domain – Parameter values to a method – Data from a file – Global variables – User inputs We partition input domains into regions (called blocks) Input domain: Alphabetic letters characteristic: Case of block ChoosePartitioning at least one value from each letter Block 1: upper case Block 2: lower case Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 4

Partitioning Domains Domain D Partition scheme q of D The partition q defines a set of blocks, Bq b1 , b2 , , bQ The partition must satisfy two properties : 1. Blocks must be pairwise disjoint (no overlap) bi bj , i j, bi, bj Bq 2. Together b1 domain b2 D b Dthe blocks cover the (complete) b Bq b3 Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 5

In-Class Exercise Partitioning for integers Design a partitioning for all integers That is, partition integers into blocks such that each block seems to be equivalent in terms of testing Make sure your partition is valid: 1) Pairwise disjoint 2) Complete Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 6

What is a characteristic? “A feature or quality belonging typically to a person, place, or thing and serving to identify it.” co nc le re ve te l Input: people Characteristics: hair color, major Blocks: A (red, black, brown, blonde, other) B (cs, swe, ce, math, ist, other) t Abstraction: c a r t s el A [ a1, a2, a3, a4, a5 ] b a ev l B [ b1, b2, b3, b4, b5, b6 ] Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 7

Examples Example characteristics – Whether X is null – Order of the list F (sorted, inverse sorted, arbitrary, ) – Min separation of two aircraft – Input device (DVD, CD, VCR, computer, ) – Hair color, height, major, age Partition characteristic into blocks – Blocks may be single-value or a set of values – Each value in a block should be equally useful for testing Each abstract test has one block from each characteristic Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 8

Modeling the input domain Step 1 : Identify testable functions Concrete level Step 2 : Find all inputs, parameters, & characteristics Step 3 : Model the input domain Step 4 : Apply a test criterion to choose combinations of values (6.2) Introduction to Software Testing, Edition 2 (Ch 6) Move from imp level to design abstraction level Entirely at the design abstraction level Back to the implementation abstraction level Ammann & Offutt 9

Choosing partitions Defining partitions is not hard, but is easy to get wrong Consider the characteristic “order of elements F” in ascending Solution: b1in list sorted order Design Two characteristics that address just one property blocks for b2 sorted in descending Can you order that think of aascending but something’s fishy C1: List F sorted b3 arbitrary order characteristic - c1.b1 true solution? Length 1 : [ 14 ] Can the This listyou is inspot all three blocks problem? That is, disjointness is not satisfied Introduction to Software Testing, Edition 2 (Ch 6) - c1.b2 false C2: List F sorted descending - c2.b1 true - c2.b2 false Ammann & Offutt 10

In-class exercise Creating an IDM Pick one of the programs from chapter 1 (findLast, numZero, etc) Create an IDM for the program you chose Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 11

Modeling the input domain Step 1 : Identify testable functions Move from imp level to design abstraction level Step 2 : Find all inputs, parameters, & characteristics Step 3 : Model the input domain Step 4 : Apply a test criterion to choose combinations of values (6.2) Introduction to Software Testing, Edition 2 (Ch 6) Entirely at the design abstraction level Back to the implementation abstraction level Ammann & Offutt 12

Steps 1 & 2 Identify testable functions Find inputs, parameters, characteristics Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 13

Example IDM (syntax) Method triang() from class TriangleType on the book website : – https://www.cs.gmu.edu/ offutt/softwaretest/java/Triangle.java – https://www.cs.gmu.edu/ offutt/softwaretest/java/TriangleType.j ava public enum Triangle { Scalene, Isosceles, Equilateral, Invalid } public static Triangle triang (int Side1, int Side2, int Side3) // Side1, Side2, and Side3 represent the lengths of the sides of a triangle // Returns the appropriate enum value IDM for each parameter is identical Characteristic : Relation of side with zero Blocks: negative; positive; zero Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 14

Example IDM (behavior) Method triang() again : The three parameters represent a triangle The IDM can combine all parameters Characteristic : Type of triangle Blocks: Scalene; Isosceles; Equilateral; Invalid Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 15

In-class exercise Functions, parameters, and characteristics public boolean findElement (List list, Object element) // Effects: if list or element is null throw NullPointerException // else return true if element is in the list, false otherwise Identify testable functions, parameters, and characteristics for findElement () Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 16

Steps 1 & 2—IDM public boolean findElement (List list, Object element) // Effects: if list or element is null throw NullPointerException // else return true if element is in the list, false otherwise Parameters and Characteristics Two parameters : list, element Characteristics based on syntax : list is null (block1 true, block2 false) list is empty (block1 true, block2 false) Characteristics based on behavior : number of occurrences of element in list (0, 1, 1) element occurs first in list (true, false) element occurs last in list (true, false) Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 17

Step 3 Model input domain Partition characteristics into blocks Choose values for blocks Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 18

triang(): Relation of side with zero 3 inputs, each has the same partitioning Characteristic b1 b2 b3 q1 “Relation of Side 1 to 0” positive equal to 0 negative q2 to q3 to positive equal to 0 negative positive equal to 0 negative “Relation of Side 2 0” “Relation of Side 3 0” Maximum of 3*3*3 27 tests Some triangles are valid, some are invalid Refining the characterization can lead to more tests Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 19

Refining triang()’s IDM Second Characterization of triang()’s inputs Characteristic b1 b2 b3 b4 q1 “Refinement of q1 ” greater than 1 equal to 1 equal to 0 negative q2 “Refinement of q2 ” greater than 1 equal to 1 equal to 0 negative greater equal to q3 “Refinement of than 1 1 q3 ” Maximum of 4*4*4 64 tests equal to 0 negative Complete only because the inputs are integers (0 . . 1) Characterist ic Side1 Introduction to Software Testing, Edition 2 (Ch 6) Values for partition q1 b1 b2 b3 52 1 Test boundary Ammann & Offutt conditions 0 b4 -1 -5 20

triang() : Type of triangle Geometric Characterization of triang()’s Inputs Characteristic b1 b2 b3 b4 q1 “Geometric Classification” scale ne isoscel es equilate ral invalid What’s wrong with this partitioning? Equilateral is also isosceles ! We need to refine the example to make characteristics valid Correct Geometric Characterization of Characteristic triang()’s b1 Inputs b2 b3 q1 “Geometric Classification” Introduction to Software Testing, Edition 2 (Ch 6) scale ne b4 isosceles, equilater not invalid al equilateral Ammann & Offutt 21

Values for triang() Possible values for geometric partition Characterist q1 b 2 b1 b3 b4 ic Triangle Introduction to Software Testing, Edition 2 (Ch 6) (4, 5, 6) (3, 3, 4) (3, 3, 3) Ammann & Offutt (3, 4, 8) 22

Yet another triang() IDM A different approach would be to break the geometric characterization into four separate characteristics Four Characteristics for triang() Characteris tic b1 b2 q1 “Scalene” True False q2 “Isosceles” True False q3 “Equilateral” True False True False q4 “Valid” Use constraints to ensure that – Equilateral True implies Isosceles True – Valid False implies Scalene Isosceles Equilateral False Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 23

IDM hints More characteristics more tests More blocks more tests Do not use program source Design more characteristics with fewer blocks – Fewer mistakes – Fewer tests Choose values strategically – Valid, invalid, special values – Explore boundaries – Balance the number of blocks in the characteristics Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 24

In-class exercise Proper partitioning? Which two properties must be satisfied for an input domain to be properly partitioned? Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 25

Modeling the input domain Step 1 : Identify testable functions Move from imp level to design abstraction level Step 2 : Find all inputs, parameters, & characteristics Step 3 : Model the input domain Step 4 : Apply a test criterion to choose combinations of values (6.2) Introduction to Software Testing, Edition 2 (Ch 6) Entirely at the design abstraction level Back to the implementation abstraction level Ammann & Offutt 26

Step 4 – Choosing combinations of values (6.2) After partitioning characteristics into blocks, testers design tests by combining blocks from different characteristics – 3 Characteristics (abstract): A, B, C – Abstract blocks: A [a1, a2, a3,a4]; B [b1, b2]; C [c1, c2,c3] A test starts by combining one block from each characteristic – Then values are chosen to satisfy the combinations We use criteria to choose effective combinations Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 27

All combinations criterion (ACoC) The most obvious criterion is to choose all combinations All Combinations (ACoC) : Test with all combinations of blocks from all characteristics. a1 b1 c1 a1 b1 c2 a2 b1 c1 a2 b1 c2 a3 b1 c1 a3 b1 c2 a4 b1 c1 a4 b1 c2 a1 a1 a1 a1 a2 a2 a2 a2 a3 a3 a3 a3 a4 a4 a4 a4 b1 b2 b2 b2 c3 c1 c2 c3 Introduction to Software Testing, Edition 2 (Ch 6) b1 b2 b2 b2 c3 c1 c2 c3 b1 b2 b2 b2 c3 c1 c2 c3 Ammann & Offutt b1 b2 b2 b2 c3 c1 c2 c3 28

All combinations criterion (ACoC) Number of tests is the product of the number of blocks in each characteristic : Q i 1 (B ) i The syntax characterization of triang() – Each side: 1, 1, 0, 1 – Results in 4*4*4 64 tests Most form invalid triangles How can we get fewer tests ? Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 29

Example Input: students Characteristics: Level, Mode, Major, Classification Blocks: Level: ( grad, undergrad ) Mode: ( full-time, part-time ) Major: ( cs, swe, other ) Classification: ( in-state, out-of-state ) Abstract IDM: A [ a1, a2 ] C [ c1, c2, c3 ] B [ b1, b2 ] D [ d1, d2 ] Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 30

In-class exercise All combinations criterion (ACoC) Consider this abstract IDM 4 Characteristics: A, B, C, D Abstract blocks: A [a1, a2]; B [b1, b2]; C [c1, c2, c3]; D [d1, d2] How many tests are needed to satisfy ACoC? Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 31

In-class exercise (answer) All combinations criterion (ACoC) 4 Characteristics: A, B, C, D Abstract blocks: A [a1, a2]; B [b1, b2]; C [c1, c2, c3]; D [d1, d2] Number of tests: 2*2*3*2 24 a1 b1 c1 d1 a1 b2 c1 d1 a2 b1 c1 d1 a2 b2 c1 d1 a1 a1 a1 a1 a1 a1 a1 a1 a2 a2 a2 a2 a2 a2 a2 a2 b1 b1 b1 b1 c1 c2 c2 c3 d2 d1 d2 d1 a1 b1 c3 d2 b2 b2 b2 b2 c1 c2 c2 c3 d2 d1 d2 d1 a1 b2 c3 d2 Introduction to Software Testing, Edition 2 (Ch 6) b1 b1 b1 b1 c1 c2 c2 c3 d2 d1 d2 d1 a2 b1 c3 d2 Ammann & Offutt b2 b2 b2 b2 c1 c2 c2 c3 d2 d1 d2 d1 a2 b2 c3 d2 32

ISP criteria – each choice We should try at least one value from each block Each Choice Coverage (ECC) : Use at least one value from each block for each characteristic in at least one test case. Number of tests is the number of blocks in the Q Max i 1:(Bi) largest characteristic Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 33

In-class exercise Each choice criterion (ECC) Apply ECC to our previous example 4 Characteristics: A, B, C, D Abstract blocks: A [a1, a2]; B [b1, b2]; C [c1, c2, c3]; D [d1, d2] 1. How many tests are needed for ECC? 2. Design the (abstract) tests Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 34

In-class exercise (answer) Each choice criterion (ECC) 4 Characteristics: A, B, C, D Abstract blocks: A [a1, a2]; B [b1, b2]; C [c1, c2, c3]; D [d1, d2] Number of tests: max(2,2,3,2) 3 a1 b1 c1 d1 a2 b2 c2 d2 a1 b1 c3 d1 Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 35

ISP criteria – base choice (BCC) ECC is simple, but very few tests The base choice criterion recognizes : – Some blocks are more important than others – Using diverse combinations can strengthen testing Lets testers bring in domain knowledge of the program Base Choice Coverage (BCC) : Choose a base choice block for each characteristic. Form a base test by using the base choice for each characteristic. Choose subsequent tests by holding all but one base choice constant and using each non-base choice in each other characteristic. Number of tests is one base test one test for Q (B -1 ) 1 block each other i 1 i Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 36

Base choice notes The base test must be feasible – That is, all base choices must be compatible Base choices can be – Most likely from an end-use point of view – Simplest – Smallest – First in some ordering Happy path tests often make good base choices The base choice is a crucial design decision – Test designers should document why the choices were made Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 37

In-class exercise Base choice criterion (BCC) Apply BCC to our previous example 4 Characteristics: A, B, C, D Abstract blocks: A [a1, a2]; B [b1, b2]; C [c1, c2, c3]; D [d1, d2] 1. How many tests are needed for BCC? 2. Pick base values and write one base test 3. Design the remaining (abstract) tests Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 38

In-class exercise (answer) Base choice criterion (BCC) 4 Characteristics: A, B, C, D Abstract blocks: A [a1, a2]; B [b1, b2]; C [c1, c2, c3]; D [d1, d2] Number of tests: 1(base) 1 1 2 1 6 Base Introduction to Software Testing, Edition 2 (Ch 6) a1 b1 c1 d1 A B C C a2 b1 c1 a1 b2 c1 a1 b1 c2 a1 b1 c3 d1 d1 d1 d1 D a1 b1 c1 d2 Ammann & Offutt 39

ISP criteria – multiple base choice We sometimes have more than one logical base choice Multiple Base Choice Coverage (MBCC) : Choose at least one, and possibly more, base choice blocks for each characteristic. Form base tests by using each base choice for each characteristic at least once. Subsequent tests are chosen by holding all but one base choice constant for each base test and using each non-base choice in each other If M base tests andcharacteristic. m base choices for each characteristic: i Q (M * (Bi - mi )) i 1 M For our example: Two base tests: a1, b1, c1, d1 b2, c2, d2 Tests from a1, b1, c1, d1: a1, b1, c3, d1 Tests from a2, b2, c2, d2: a2, b2, c3, d2 Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt a2, 40

ISP Coverage Criteria Subsumption All Combinations Coverage ACoC Multiple Base Choice Coverage MBCC T-Wise Coverage TWC Base Choice Pair-Wise Coverage PWC Coverage BCC Each Choice Coverage ECC Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 41

Constraints Among Characteristics (6.3) Some combinations of blocks are infeasible – “less than zero” and “scalene” not possible at the same time These are represented as constraints among blocks Two general types of constraints – A block from one characteristic cannot be combined with a specific block from another – A block from one characteristic can ONLY BE combined with a specific block form another characteristic Handling constraints depends on the criterion used – ACC, PWC, TWC : Drop the infeasible pairs – Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 42

Example Handling Constraints public boolean findElement (List list, Object element) // Effects: if list or element is null throw NullPointerException // else return true if element is in the list, false otherwise Characteristic Block 1 Block 2 A : length and contents One element More than one, unsorted B : match element not found element found once Block 3 Block 4 More More than than one, one, all sorted identical element found more than once Invalid combinations : (A1, B3), (A4,IfB2) the list only has one element cannot be element, but it appears in a one-element multiple times, we list more than cannot find it just once once Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 43

Input Space Partitioning Summary Fairly easy to apply, even with no automation Convenient ways to add more or less testing Applicable to all levels of testing – unit, class, integration, system, etc. Based only on the input space of the program, not the implementation Simple, straightforward, effective, and widely used Introduction to Software Testing, Edition 2 (Ch 6) Ammann & Offutt 44