PaperlayerView exact revision on arXiv

Source-linked AI summary

Test Set Diameter: Quantifying the Diversity of Sets of Test Cases

Robert Feldt, Simon Poulding, David Clark, Shin Yoo

arXiv:1506.03482v1cs.SE

TL;DR

Earlier test-diversity work often measured pairs, leaving unclear how to use those distances to select a small, diverse test set. This paper evaluates selection using input TSDm; across three Java systems, selected sets were 2 to 9 times smaller than random sets at the same high coverage.

  • Problem

    Pairwise NCD measures distances between test cases, but prior work did not establish concrete ways to use those distances to select small, diverse sets.

    Source: §I · p. 2

  • Method

    The study evaluates test-set selection using input TSDm and compares its coverage growth with random selection and a post-hoc greedy method.

    Source: A. Research questions · p. 4, §VII · p. 10

  • Results

    Across three Java systems, TSDm-selected test sets were 2 to 9 times smaller than randomly selected sets reaching the same high coverage.

    Source: §V · p. 9

  • Takeaways & Limitations

    Quantifying and ranking test-set diversity may support a deeper understanding of test quality and practical techniques to improve it.

    Source: §VII · p. 10

    The selection procedure has quadratic time scaling, and NCD does not readily explain why it selected particular test cases.

    Source: §V · p. 9

Abstract

from arXiv · show

A common and natural intuition among software testers is that test cases need to differ if a software system is to be tested properly and its quality ensured. Consequently, much research has gone into formulating distance measures for how test cases, their inputs and/or their outputs differ. However, common to these proposals is that they are data type specific and/or calculate the diversity only between pairs of test inputs, traces or outputs. We propose a new metric to measure the diversity of sets of tests: the test set diameter (TSDm). It extends our earlier, pairwise test diversity metrics based on recent advances in information theory regarding the calculation of the normalized compression distance (NCD) for multisets. An advantage is that TSDm can be applied regardless of data type and on any test-related information, not only the test inputs. A downside is the increased computational time compared to competing approaches. Our experiments on four different systems show that the test set diameter can help select test sets with higher structural and fault coverage than random selection even when only applied to test inputs. This can enable early test design and selection, prior to even having a software system to test, and complement other types of test automation and analysis. We argue that this quantification of test set diversity creates a number of opportunities to better understand software quality and provides practical ways to increase it.

I. INTRODUCTION

Selecting a small, effective test set is a central testing problem, yet diversity measures are often data-specific or pairwise and do not directly specify test selection. The paper proposes using multiset NCD to measure whole-set diversity across test-related data.

I. INTRODUCTION

  • Testing must make limited resources go further by selecting a small, effective set of cases that is also small enough for human oracles to assess.Tests are often re-executed each iteration or before each release.Source: §I · p. 1
  • The intuition that diverse tests can cover intended and actual behavior is reflected in methods that spread cases across the input domain, including adaptive random testing.The category-partition distance scheme requires testers to identify categories and levels manually.Source: §I · p. 1
  • Prior diversity measures are often data-specific, while pairwise NCD leaves unclear how to select a small, diverse test set.Feldt et al. clustered test cases by pairwise distances but did not investigate concrete test-set selection.Source: §I · pp. 1–2
  • The paper applies NCD for multisets to quantify diversity across an entire set rather than approximating it through pairwise comparisons.The approach is intended for test inputs, outputs, traces, or other test-related information.Source: §I · p. 2

A. Information Distance and its approximation

Information distance compares strings through the shortest programs needed to transform one into the other. NID normalizes this measure, while NCD uses real-world compression as a practical approximation.

A. Information Distance and its approximation

  • Information distance between two strings is the larger of the conditional Kolmogorov complexities K(x|y) and K(y|x).These complexities represent the shortest programs that output one string given the other as input.Source: A. Information Distance and its… · p. 2
  • NID normalizes information distance using the complexities of the two strings, and values nearer 0 indicate greater similarity.The normalized measure takes values in [0, 1] and retains metric properties.Source: A. Information Distance and its… · p. 2
  • NCD approximates Kolmogorov complexity with the compressed length of strings, using a chosen real-world compression program.Its value lies in [0, 1 + ϵ], where ϵ depends on how well the compressor approximates Kolmogorov complexity.Source: A. Information Distance and its… · p. 2

B. Extending NCD to Multisets

Multiset NCD measures similarity or diversity for a collection of strings as a whole, extending pairwise NCD. A quadratic-time approximation uses an intermediate measure, NCD1.

B. Extending NCD to Multisets

  • Multiset NCD provides a measure of similarity, or conversely diversity, for a collection of strings considered as a whole.A multiset can contain the same string more than once, and for two strings its NCD matches pairwise NCD.Source: B. Extending NCD to Multisets · pp. 2–3
  • Exact multiset NCD has O(2^N) time complexity because it recursively evaluates every proper subset, making it likely impractical beyond the smallest multisets.The approximation instead has O(N^2) time complexity.Source: B. Extending NCD to Multisets · p. 3
  • The proposed approximation repeatedly removes the string whose removal maximizes compressed length, then takes the maximum NCD1 value across the resulting subsets.It uses NCD1 as an intermediate measure to approximate multiset NCD.Source: B. Extending NCD to Multisets · pp. 2–3

III. TEST SET DIAMETER

Test Set Diameter applies multiset NCD to a chosen aspect of test cases, enabling whole-set diversity assessment across different kinds of test information. The study focuses on selecting sets using input diversity.

III. TEST SET DIAMETER

  • Test Set Diameter (TSDm) applies multiset NCD to a chosen aspect of test cases, extending universal diversity measurement from pairs to entire sets.The aspect can be inputs, outputs, or execution traces.Source: §III · p. 3
  • TSDm1 selects a diverse set of a specified size by iteratively removing cases to maximize NCD1 and choosing the resulting subset of the desired size.The procedure starts with a pool at least as large as the target set.Source: §III · p. 3

IV. EMPIRICAL STUDY

  • The empirical study evaluates Input TSDm on randomly generated test inputs, a use case intended to support test-suite selection before system implementation begins.Future work is proposed for outputs, execution traces, and combinations of test information.Source: §IV · p. 3

A. Research questions

The study asks whether input-based test set diversity tracks structural coverage and improves test selection, including when input sizes are controlled. It also examines fault detection and selection time.

A. Research questions

  • Higher test set diameter is expected to correspond to higher code coverage, which the study tests using Spearman rank correlation on sampled input sets.Subsets vary in size; Spearman is used because the authors do not expect TSDm or coverage values to be normally distributed.Source: A. Research questions · pp. 3–4
  • I-TSDm selection is evaluated against random selection for instruction coverage, seeded-fault detection, and selection-time scaling.The study also asks whether any coverage advantage remains when test-input sizes are controlled.Source: A. Research questions · p. 4
  • Random selection is the early-development baseline, while a post-hoc greedy algorithm provides an upper-limit comparison using executable coverage feedback.Coverage is normalized to the greedy results so outcomes can be compared across software subjects.Source: A. Research questions · p. 4
  • Input length may confound diversity results because I-TSDm tends to select longer inputs first, so the study also compares selections with input size controlled.Inputs are generated near target sizes, within 10%, to reduce size-related selection-order effects.Source: A. Research questions · p. 4
  • The study asks whether I-TSDm's O(N^2) scaling limits its usefulness in online automation, where selection time could instead be spent executing tests.The paper also frames seeded faults as a way to assess whether test sets find faults, not just cover code.Source: A. Research questions · p. 4

B. Software Subjects

The evaluation uses three Java libraries and one C application as software subjects. It also reports the experimental computing environment and repetition protocol.

B. Software Subjects

  • JEuclid, ROME, and NanoXML are Java subjects tested through generated MathML, Atom-feed, and XML inputs, respectively.Coverage is measured for JEuclid's core rendering and document-handling module, but for the entire ROME and NanoXML libraries.Source: B. Software Subjects · p. 4
  • Replace is a C pattern-matching and substitution application tested with generated regular expressions and random strings of 0–32 characters.The application has 538 SLOC.Source: B. Software Subjects · p. 4

C. Measures

  • Experiments ran on a 2012 MacBook Pro using Julia 0.3.8, with 10 independent repetitions unless otherwise stated.The machine had a 2.7 GHz Intel Core i7 CPU and 16 GB of DDR3 memory.Source: C. Measures · p. 4

1) Coverage:

I-TSDm was positively associated with instruction coverage across the studied subjects, with one lower NanoXML correlation at the largest subset size. The section also specifies coverage measurement and comparison procedures.

1) Coverage:

  • JaCoCo measures bytecode-level instruction coverage for the three Java subjects, while Replace coverage is assessed by detection of seeded faults.A fault counts as detected when a variant's output or return status differs from the unmodified application.Source: 1) Coverage · p. 5

2) Greedy Coverage Algorithm:

D. Experiment 1: Correlation to code coverage

  • Spearman correlations between I-TSDm and instruction coverage ranged from 0.40 to 0.82, except NanoXML at size 50 (0.26); all tests had p-values below 10^-4.The correlation table reports three SUTs and three test-set sizes.Source: D. Experiment 1: Correlation to code… · p. 5, Table I · p. 5
  • Higher input diameter was associated on average with higher code coverage, although the NanoXML results showed a banding pattern.For ROME, average coverage was 0.254, 0.277, and 0.285 for test-set sizes 10, 20, and 50, respectively.Source: D. Experiment 1: Correlation to code… · p. 5

E. Experiment 2: Structural coverage

I-TSDm1-selected sets reached coverage targets with fewer tests than random selections. The section also notes that input length can affect selection order and coverage comparisons.

E. Experiment 2: Structural coverage

  • Randomly selected sets required 2 to 6 times larger test sets than I-TSDm1 on average; at 95% normalized coverage, I-TSDm1 sets were 77% (ROME), 80% (NanoXML), and 83% (JEuclid) smaller.Table II compares average set sizes needed to reach 90%, 95%, and 99% of maximum coverage attained by the greedy algorithm.Source: E. Experiment 2: Structural coverage · p. 5, Table II · p. 7
  • Input length correlates strongly with I-TSDm1 selection order, and the authors report that diversity's coverage advantage diminishes when inputs are long enough.Length-selection correlations were 0.96 for JEuclid, 0.93 for ROME, and 0.96 for NanoXML.Source: E. Experiment 2: Structural coverage · pp. 5, 7
  • Figure 2 compares normalized ROME instruction coverage against test-set size for greedy, I-TSDm1, and random selection, averaging 10 runs.The initial pool contains 250 randomly generated MathML inputs; coverage is normalized to the greedy maximum.Source: E. Experiment 2: Structural coverage · p. 5, Figure 2 · p. 7

F. Experiment 3: Structural coverage under a length constraint

Under a 90–110-byte input constraint, I-TSDm remained considerably better than random selection but was less competitive with the greedy algorithm. Its coverage advantage over random selection persisted until inputs were long enough for random selection to catch up.

F. Experiment 3: Structural coverage under a length constraint

  • The experiment restricts input length because longer test inputs make a likely manual oracle more difficult and costly to apply.Inputs were generated and filtered to retain those within 10% of a target length.Source: F. Experiment 3: Structural coverage… · p. 7
  • With inputs limited to 90–110 bytes, I-TSDm remained considerably better than random selection but was less competitive than the greedy algorithm.The supplied table caption identifies the compared methods and constrained input pool.Source: F. Experiment 3: Structural coverage… · p. 8, Table III · p. 8
  • The advantage over random selection persisted across tested target lengths until inputs became long enough for random selection to catch up.The authors suggest that sufficiently long inputs may each exercise a large part of the intended behavior.Source: F. Experiment 3: Structural coverage… · p. 8
  • For a given coverage level, constrained-input I-TSDm test sets were larger than unconstrained ones, although the comparison requires caution because maximum coverage differed across systems.For JEuclid, the reported maximum was 46.8% with the length constraint and 59.8% without it.Source: F. Experiment 3: Structural coverage… · p. 8
  • Coverage under a length constraint supports the conclusion that test set diameter can improve code coverage beyond what input length alone explains.The authors recommend comparing automated testing techniques by coverage per bit or byte of test suite.Source: F. Experiment 3: Structural coverage… · p. 8

G. Experiment 4: Fault-finding ability

With regular-expression lengths controlled, I-TSDm selected test sets with higher average fault coverage than random selection, while greedy selection performed substantially better than both. The selection procedure’s runtime scaled quadratically with pool size and linearly with average test length.

G. Experiment 4: Fault-finding ability

  • With regular-expression lengths of 9–11 bytes, I-TSDm selected test sets with higher average fault coverage than random, while greedy selection substantially outperformed both.Test sets reaching 95% normalized fault coverage were 45% smaller with I-TSDm1 than with random selection.Source: G. Experiment 4: Fault-finding ability · p. 8, Figure 5 · p. 8
  • Broader evaluation across more systems is needed before the fault-finding result’s generality can be established.The authors explicitly call for experiments applying I-TSDm to a wider range of SUTs.Source: G. Experiment 4: Fault-finding ability · p. 8

H. Experiment 5: Test set selection time

  • Selection time scaled quadratically with the initial test-pool size and linearly with average test length.A model using average string length multiplied by N^2 fit observed times with R^2 above 0.99.Source: H. Experiment 5: Test set selection time · pp. 8–9
  • Selecting from 1,000 inputs averaging a couple hundred bytes took 40–60 minutes on the experimental machine.The authors identify parallelization or pairwise-NCD-based initial filtering as possible ways to speed the process.Source: H. Experiment 5: Test set selection time · p. 9

V. DISCUSSION

TSDm supports test selection and analysis, with empirical advantages over random selection, but its computational cost and limited explainability constrain its use. The discussion also identifies uncertainties about compression choices, non-self-describing information, and comparison with human selection.

V. DISCUSSION

  • For three XML-input Java systems, TSDm selected test sets 2 to 9 times smaller than random sets at the same high coverage level.For a C software function, TSDm also improved fault coverage compared with random selection.Source: §V · p. 9
  • An information-theoretic basis may help formalize software-testing diversity and support investigation of its limiting laws.The authors connect this opportunity to the broader lack of theories in Software Engineering.Source: §V · p. 9
  • TSDm can help testers add cases that increase set diameter, including through an interactive process presenting highly diverse candidates.The authors also suggest that it can complement manual test selection.Source: §V · p. 9
  • Ordering and visualizing manually created cases by TSDm may inform test-suite reductions and evaluation of proposed cases.The authors suggest discussing the results with testers to examine the relative importance of cases.Source: §V · p. 9
  • NCD makes selection less interpretable than data- or domain-specific metrics, which may offer users more understandable explanations.The authors envision using more explanatory metrics after TSDm-based selection.Source: §V · p. 9
  • The effect of compression-algorithm choice on NCD remains unclear, and compressor-specific discontinuities may affect results.Informal investigations found TSDm robust to compressor variation; preliminary work suggests multiset NCD may be less affected by short-input discontinuities than pairwise NCD.Source: §V · p. 9
  • Base NCD may not suit named rather than self-describing information; the authors identify Normalized Web Distance as an alternative to explore.They propose exploring that metric for software testing as future work.Source: §V · p. 9
  • Manual test selection remains an untested comparator because available repository test sets had unclear strategies and could not be used reliably.The study used maximum coverage from greedy selection as an approximation of what a human tester might achieve.Source: §V · p. 9

VI. RELATED WORK

Prior diversity measures often rely on pairwise distances or data-specific representations, while TSDm applies multiset NCD to test sets as a whole. The paper reports coverage and fault-coverage advantages over random selection, while noting that test effectiveness may depend on factors beyond diversity.

VI. RELATED WORK

  • Repeated-use approaches vary which existing tests are selected, but do not help engineers compare two test sets.Examples include history-based prioritization and changing subsets across iterations.Source: §VI · p. 10
  • Earlier diversity approaches use measures such as Euclidean, Hamming, or Levenshtein distance, limiting data applicability or losing high-level semantics compared with NCD.Prior work also considered execution traces and object-member distances.Source: §VI · p. 10
  • Output-diversity work linked diverse outputs with coverage and fault detection, whereas this paper studies inputs and uses graded NCD rather than binary output uniqueness.Input-based analysis can occur before test execution or system implementation; future work should compare filters and binary uniqueness with continuous measures.Source: §VI · p. 10
  • Feldt et al. applied NCD pairwise to test similarity, but that approach could not compare test sets; this work extends NCD to multisets.The extension enables comparisons between sets of test cases.Source: §VI · p. 10, §VII · p. 10

VII. CONCLUSIONS

  • TSDm measures test-set diversity as a whole, with a formal basis in Kolmogorov complexity and applicability across data types and test-related information.Modern compression algorithms approximate its calculation for test selection and analysis.Source: §VII · p. 10
  • For three Java systems, input TSDm correlated moderately to highly with instruction coverage; for a seeded-fault C program, equal-fault-coverage sets were 27 to 45% smaller than random sets.Controlling for input size still showed a considerable advantage over random selection; TSDm also approached post-hoc greedy selection requiring coverage information.Source: §VII · p. 10
  • The authors conjecture that generator diversity and the size and diversity of the initial pool also help determine test-set effectiveness.They call for future work to quantify these factors.Source: §VII · p. 10
Loading 1506.03482v1…