Efficient Test Suite Construction Using Covering Arrays

Covering Arrays: A tool to construct efficient test suites for validating deterministic systems Ryan Lekivetz JMP Division of SAS Different than DOE? Abstract Covering Arrays Fewer Runs Not trying to fit a model Categorical factors, binary (categorical) response No error JMP 12 introduced the first JMP Pro platform for Design of Experiments (DOE) with the Covering Array platform. Covering arrays (CA s) are a tool used to test deterministic systems by revealing if any level combinations involving up to a certain number of factors induce a failure. Definition: A covering array CA(N; t, (v1*v2 *vk)) is an N x k array such that the i th column contains vi distinct symbols. If for any t coordinate projection, all combinations of symbols exist, then it is a t- covering array. If N is minimal for fixed t, k, and (v1 vk), it is said to be optimal. Why Covering Arrays? Failures more likely induced by small number of factors CA s make sure we ve covered t- way combinations (plus more!) Exhaustive testing usually not feasible Objective Deterministic system (same input gives same output every time) Identify faults How to test effectively? Less-wordy definition: For a set of factors, a t-covering array has the property that for any subset of t factors, every possible combination occurs at least once. Using JMP to test JMP 1. Preferences 2. Radio buttons

Covering Arrays Ryan Lekivetz JMP Division of SAS Factors Disallowed Combinations Enter Categorical factors Continuous factors need to be converted into a discrete number to input as categorical Choose strength Higher strength = ascertain better coverage at cost of more runs Specify combinations that cannot occur Disallowed Combinations Filter creates script that can be used later Unlike rest of DOE, it s fine if you end up with missing values in the design

Covering Arrays Ryan Lekivetz JMP Division of SAS After Make Design After Make Table 100% of 2-factor combinations 91% of 3-factor combinations Response column keeps track of pass/fail results If there s a failure, would like to know the cause Analysis tool provides a set of possible causes by considering the entire set of passes and fails Metrics reveal how well combinations covered in projections of t factors Optimize tries to find a smaller design Optimize disabled if design is known to be smallest

Covering Arrays Ryan Lekivetz JMP Division of SAS Testing Preferences Categorical platform preference set has lots of checkboxes (2-level), as well as a few options with 3 or more choices 712,483,534,798,848 possible combinations to test Covering array starts with a 20-run design for strength 2 In a few seconds, Optimize finds a 16-run design, which is the minimum run size

Covering Arrays Ryan Lekivetz JMP Division of SAS Testing Factors that cannot be run together Level setting of one particular factor implies that other factors are not applicable For example, may have a radio button, each choice having its own set of options that follow Automated Hierarchical Clustering => options for interactive/minimum don t apply Some workarounds: Create separate design for each choice (wasteful testing) Make combined factors (hard to read/decipher) Instead use disallowed combinations Sensible missing values in the design Analysis still works too

Covering Arrays Ryan Lekivetz JMP Division of SAS Effectiveness of Covering Arrays #factors involved in failure Medical devices Browser Server NASA GSFC 1 2 3 4 5 6 66 97 99 100 29 76 95 97 99 100 42 70 89 96 96 100 68 93 98 100 Cumulative percentage of faults triggered by interactions involving number of factors indicated in leftmost column (Kuhn et al. (2004)). D. Kuhn, D. R. Wallace, & A. M. Gallo, Software Fault Interactions & Implications for Software Testing, IEEE TSE, 30(6), 2004, 418-421