arXiv CSopen access

An analysis of the relationship of input metrics

An analysis of the relationship of input metrics Addison Crump

arXiv:2609.11824v1 [cs.SE] 10 Sep 2026

CISPA Helmholtz Center for Information Security Saarbrücken, Germany 0009-0003-3271-3558

Abstract—Input metrics evaluate the progress of testing in terms of features of inputs present in a test suite. Previous works, as early as the 1950s, established a number of such metrics, but few endeavored to compare them. This paper does so by utilizing existing methods proposed for other metric classes in partition testing literature. After defining and reviewing common input metrics, we begin with a short case study revealing that typical empirical comparison strategies are fundamentally insufficient for comparing metrics. Then, we demonstrate how one rigorously improves a standard metric by defining and implementing k-alt-path, a new metric which reduces redundancy while improving sensitivity over k-path. Each of the other common input metrics are then systematically compared before discussing the implications of our findings. With these contributions, we bring forward partition testing analysis methods that justify and form a strategy for future research in refining input metrics.

to test them. The same structures for parsing enabled tools for generation and corresponding metrics for computing test suite completeness. Purdom [4] first defines a generation strategy to exercise grammars by producing sentences (i.e., inputs satisfying the grammar) that exercise every production rule of the grammar, implicitly defining rule coverage. Later authors explore input generation by randomly exploring grammars [5]. Eventually, Lämmel [6] defines coverage metrics that introduce context sensitivity and define mechanisms for producing sentences that exercise each manifestation of a production rule. The current standard for syntactic coverage measurement, kpath, is a conceptual extension of Lämmel’s work to extend this sensitivity to arbitrary depths [7] and corresponding generators which optimize for that metric.

I. I NTRODUCTION

Generators for semantically valid inputs are also becoming more prevalent. The rapid improvement of LLMs has spurred significant interest into LLM-based test generation, including the generation of test data and inputs [8]. Other works detail specialized generators for specific languages and targets, most often so for source code generation in compiler and interpreter testing [9, 10]. More recently, language-based testing tools attempt to produce semantically valid inputs for arbitrary input languages by performing constraint solving in the process of input production [11, 12]. While input metrics and generation have historically been inextricably linked, coverage metrics for semantic qualities of languages are typically target-specific, and few have attempted to define such metrics [13]. Instead, these works tend to rely instead on syntactic metrics for input diversity and test suite completeness measurement.

When we quantify the thoroughness of testing, we most often use definitions of input space subdivision formalized by partition testing. The most common form of subdivision familiar to software testing practitioners is likely code line coverage: which lines of code have been covered during the execution of a particular input or set of inputs. Where code coverage divides the input space based on program features, input metrics divide based on input features. Such features can only be measured when input features are quantifiable, and these generally form along three categories: lexical, by inspecting the sequences of tokens in the input; syntactic, by observing structure of the input; and semantic, by considering the meaning of the input. Lexical measures of input coverage were introduced earliest, The impetus for this work was a pair of questions: are the measuring observed sequences of tokens present in tested inputs. syntactic metrics used by modern input generators optimal, This is potentially most famously demonstrated by Shannon [1] and are they sufficient? We discovered that these two questions for measuring the lexical redundancy of the English language were superseded by one: how does one even compare input using n-grams, observations of token sequences of length metrics? This paper answers this question with three theoretical n. Using the measured n-gram distributions for both letters contributions: and words, Shannon demonstrates that one can reconstruct approximations of the English language by sampling over • A brief repudiation of previous comparison strategies probable sequences of characters or words. between metrics, A few years later, Chomsky [2] publishes his abstractions • Extension of existing metric comparison strategies from for languages. These allow one to define structural rules for partition testing literature to input metrics, and languages, encoding syntax rather than raw token sequences • Analysis of how different classes of input metrics align. to capture the higher-level relationships between words. These grammars eventually become standard for structuring computerparseable languages due to their alignment with the grammars Along the way, we optimize the standard k-path metric of human languages [3] and their efficient parseability. With significantly with a new metric, k-alt-path, and systematize the such parsers becoming more prevalent, people naturally sought relationship between existing input metrics.

II. P RELIMINARIES

(reachable) edges of the control flow graph of the program are Central to this paper are two concepts: test adequacy covered. In reality, we rarely actually achieve such criteria, but criteria relationships and context-free grammars. We begin by such analysis gives us a foothold to begin comparing criteria. We say that a criterion C is subdomain-based if, for each reviewing background literature that gives the foundation for program X ∈ X and specification Y ∈ Y, C component-wise comparing input metrics. Then, we review some preliminaries divides the input domain I into a multiset of subdomains in context-free grammars before defining each input metric SD (X, Y ). To make this notion more concrete, we can C discussed through the paper. consider a function fC : I × X × Y 7→ P(FC (X, Y )), where A. Notation FC (X, Y ) are a set of observable features, individual elements In this paper, we will consider sets (distinct unordered lists), representing observable behaviors exhibited during execution multisets (non-distinct unordered lists), and sequences (non- over X, exercising of components of the specification Y , or distinct ordered lists), for which notation often overlaps to even different aspects of an input i itself. For example, the describe similar, but not identical concepts. To avoid later “all-edges” criterion edges would define Fedges (X, Y ) as the confusion, the notation used throughout this paper is defined set of edges in the program X. fedges (i, X, Y ) then represents, “what set of edges of X are traversed when executing i?” Each explicitly here. A set S1 is a subset of S2 (denoted S1 ⊆ S2 ) iff S1 contains f ∈ FC (X, Y ) then acts as an index for a single element only elements present within S2 , and is a proper subset (denoted Df ∈ SDC (X, Y ) such that S1 ⊂ S2 ) iff S1 ⊆ S2 and S1 ̸= S2 . The set formed by all Df = {i ∈ I : f ∈ fC (i, X, Y )} (3) subsets of a given set S is denoted P(S). Other operators used throughout are consistent with typical set theoretic notation. SDC (X, Y ) is often not mutually exclusive nor distinct. As A multiset M1 is a submultiset of M2 iff the number of an example, when a sequence of program regions are only occurrences of e ∈ M1 (denoted Occs(M1 , e)) is fewer than connected by unconditional edges, those edges necessarily that of M2 : correspond to the same set of inputs, but different subdivisions in SDedges (X, Y ). M1 ⊆ M2 ⇐⇒ Occs(M1 , e) ≤ Occs(M2 , e) (1) Partition testing itself is the process of testing X by ∀e ∈ M1 exercising different partitions (more accurately, subdomains) M1 is a proper submultiset of M2 (denoted M1 ⊂ M2 ) iff of the input domain such that a representative candidate of M1 ⊆ M2 and M1 ̸= M2 . The uniq operator creates the set each subdomain is present in the test suite T . Since each test formed from a given multiset, i.e.: t ∈ T ⊆ I is a member of some submultiset of subdomains, partition testing informs us that a test suite T is C-adequate uniq(M) = {e : e ∈ M} (2) for X and Y if [ [ A multiset M1 is a subset of M2 iff uniq(M1 ) ⊆ uniq(M2 ). SDC (X, Y ) = S The number of items present in a multiset M is denoted |M|. (4) where S = {D ∈ SDC (X, Y ) : D ∩ T ̸= ∅} Finally, a sequence q is a concatenation of elements, e.g. q = x1 ⊔ · · · ⊔ xn , where ⊔ is the concatenation operator and 1) Criterion relationships: A test criterion C1 subsumes C2 each x is some other (potentially empty) subsequence. When for X, Y if contextually obvious, the concatenation operator is omitted for concision (e.g., q = x1 x2 = x1 ⊔ x2 ). A sequence q1 C1 (T, X, Y ) =⇒ C2 (T, X, Y ) ∀T (5) is a subsequence of q2 (denoted q1 ⊆ q2 ) iff there exists C1 universally subsumes C2 if this applies for all X and Y . some sequences x1 , x2 where q2 = x1 q1 x2 , and is a proper In other words: the subsumption relationship tells us when one subsequence iff q1 ⊆ q2 and q1 ̸= q2 (denoted q1 ⊂ q2 ). The adequacy criterion supersedes another; satisfying the former length of a sequence q is denoted |q|. The set of all possible necessarily means that you have satisfied the latter. This ∗ sequences formed by members of some set S is denoted S , relationship is unfortunately quite weak; it only informs us as n and all possible sequences of length n is denoted S . to the relationship of C1 and C2 in the extreme cases of test B. Partition Testing adequacy, when all subdomains are satisfied. To allow us to inspect the relationship between two metrics, Suppose we want to determine whether a program X satisfies we also consider the covers relationship [14]. We say that C1 some specification Y . In empirical testing, we can’t execute X covers C2 for X, Y if: with the often infinite domain of inputs I. Instead, we select a set of test cases T ⊆ I. Now we ask a second question: is T ∀D ∈ SDC2 (X, Y ) ∃M ⊆ SDC1 (X, Y ) [ enough to test X for Y ? (6) D′ = D This is where we use test adequacy criteria [14]. We say ′ D ∈M that a test suite T is C-adequate if X is “thoroughly” tested for Y according to the criterion C, denoted C(T, X, Y ). As an In other words, C1 covers C2 if C2 ’s subdomains are each example typical to fuzzing: the “all-edges” criterion states that covered by some submultiset of subdomains of C1 . As a result, T is adequate for testing X for Y if, by executing T on X, all if C1 covers C2 , then it necessarily subsumes as well. Each

⟨expr⟩ ::= ⟨number⟩ ‘+’ ⟨expr⟩ | ⟨number⟩ ⟨number⟩ ::= ‘0’ | ⟨non zero⟩⟨digits⟩ ⟨digits⟩ ::= ⟨digit⟩⟨digits⟩ | ‘’ ⟨digit⟩ ::= ‘0’ | ⟨non zero⟩ ⟨non zero⟩ ::= ‘1’ | ‘2’ | ‘3’ | ‘4’ | ‘5’ | ‘6’ | ‘7’ | ‘8’ | ‘9’ Fig. 1. The “addition” grammar, where S = ⟨expr⟩.

⟨expr⟩1

S = a1

a2

⟨number⟩1

“+”

⟨expr⟩2

of these relationships are necessarily transitive and reflexive. Later, we show relationships across a variety of input metrics. C. Context-Free Grammars

a3

⟨non zero⟩1

⟨digits⟩1

⟨number⟩2

A context-free grammar (CFG) G is a 4-tuple (V, Σ, R, S). V and Σ are sets of symbols such that V ∩ Σ = ∅ representing nonterminals and terminals, respectively. S ∈ V is the “start symbol”, which we will revisit shortly. R ⊆ V × (V ∪ Σ)∗ is i = a4 “+” “5” “” “0” a relation. For some v ∈ V and x ∈ (V ∪ Σ)∗ , we say that v “directly expands” to x iff (v, x) ∈ R (denoted v →R x). Put 2. Derivation tree of the input 5 + 0. Dashed components are added for simply: R defines the “rules” under which each nonterminal Fig. clarity on expansion but are not part of the derivation tree. (here, v) may be expanded into some concatenation of other symbols (here, x). We can broaden the notion of direct expansion to that of indirect expansion. Given sequences x = x1 ⊔ · · · ⊔ xn and i ∈ Σ∗ with the value 5 + 0. To show S ⇒∗R i, we present y = y1 ⊔ · · · ⊔ yn (where ∀k ∈ [1, n], xk ∈ (V ∪ Σ) and the derivation tree in Fig. 2. This figure is annotated to show yk ∈ (V ∪ Σ)∗ ), we say that x indirectly expands to y, written the expansion at each step of S = a1 ⇒R · · · ⇒R a4 = i. x ⇒R y, iff xk →R yk when xk ∈ V or xk = yk , otherwise. For example, at a tree depth of 2, we see the expansion We may now apply this indirect definition of expansion a2 = ⟨number⟩1 ⊔“+”⊔⟨expr⟩2 . The derivation tree bridges the recursively; for x, z ∈ (V ∪ Σ)∗ , x ⇒∗R z (x recursively formal definition and intuitive understanding of how expansion expands to z by R) if there exists some derivation sequence of a nonterminal actually works in practice. x = a1 ⇒R · · · ⇒R an = z. Coming all the way back around 2) Graph representation: To better visualize the CFG itself, now: we say that some input i ∈ Σ∗ is in the grammar G we may represent it as a directed graph. The original k-path iff S ⇒∗R i. G is unambiguous if there exists exactly one or paper [7] does so in the following steps1 : zero sequences of expansions by which this holds for every i. Unless explicitly mentioned otherwise, we only consider such 1) Recursing from the starting nonterminal, the immediate unambiguous grammars for the remainder of the paper. expansion of each nonterminal is added to the graph as 1) Rule syntax and derivation trees: To define grammars, children of that nonterminal with the remaining steps. all we need to define are the rules. Consider Fig. 1; here, 2) At each alternation, a unique synthetic | node is inserted quoted values are terminals, ⟨v⟩ ::= x means (v, x) ∈ R, and and an edge added from this node to each of its variants. ⟨v⟩ ::= x1 | . . . |xn (an “alternation” over x1 , . . . , xn ) means This step allows for nested alternations to be represented that ∀k ∈ [1, n], (v, xk ) ∈ R, where xk is the “k-th variant” of without intermediary nonterminals. v. Many flavors of context-free grammar definition languages 3) At each concatenation, a unique synthetic ⊔ node is include extensions like nested alternation, where one may inserted and an edge added from this node to each of define sub-variants of a particular rule (e.g., x1 |(x2 |x3 )); nested the concatenated values. This step allows for nested concatenation, used in conjunction with nested alternations to concatenation to be represented without intermediary define rules with common subsequences (e.g., x1 ⊔(x2 ⊔x3 |x4 )); nonterminals. and quantifiers, which allow for convenient repetition of 4) Literals are inserted as nodes uniquely. symbols in rules. All of these primitives can be converted back 5) Each reference to a nonterminal is assigned a unique into the typical rule definition described above by the creation node, then an edge added to its previous expansion. of intermediary nonterminals, though we do not explicitly perform this in this paper. A graph for the grammar of Fig. 1 is shown in Fig. 3. Fig. 1 defines a grammar that accepts any string that represents the addition of one-to-many nonnegative integers. To better visualize what this means for inputs, we introduce the 1 Havrikov and Zeller [7] additionally provide steps to represent quantifiers concept of a derivation tree. A derivation tree is a representation (an extension to simplify repetition) within grammar graphs, but do not specify of the sequence taken during the recursive expansion of the how to compute the k-path metric in the presence of quantifiers. To avoid start nonterminal to the corresponding input. Consider an input underspecification, we only consider grammars that do not contain quantifiers.

D. Traditional Input Metrics Let I ⊆ Σ∗ be the set of inputs expressed by an unambiguous context-free grammar G = (V, Σ, R, S): I = {i : S ⇒∗R i}

(7)

We define coverage as some function cov : I 7→ P(FC ), where FC is the coverage-specific feature domain described in Section II-B, absent a specific program X and specification Y as FC is independent of these for input metrics. 1) n-gram Coverage: The first coverage metric introduced [1], though not formally as a metric, is a lexical coverage. n-gram coverage (gramn : I 7→ P(Σn )) is defined as the set of sequences of terminals of length n present in a given i: gramn (i) = {s ∈ Σn : s ⊆ i}

⟨expr⟩2

|1

⊔1

⟨number⟩1

⟨number⟩2

“+”

|2

“0”1

⊔2

⟨digits⟩1

⟨digits⟩2

|3

⊔3

“”

⟨digit⟩

⟨nonzero⟩2

|4

(8)

For the purposes of comparison later, we define a second metric, n-or-less-gram (gram≤n : I 7→ P(Σn ∪ Σn−1 ∪ · · · ∪ Σ)), that is inclusive of shorter sequences: gram≤n (i) = {s ∈ Σ∗ : |s| ≤ n ∧ s ⊆ i}

⟨expr⟩1

⟨nonzero⟩1

(9)

2) Rule Coverage: Purdom [4] defines production rule coverage similarly straightforwardly, intuitively representing the covered expansions of each nonterminal:

|5

rule(i) ={(v, x) ∈ R : (∃u, w ∈ (V ∪ Σ)∗ )

(10)

[S ⇒∗R uvw ⇒R uxw ⇒∗R i]}

“1”

“. . . ”

“0”2

3) Context-Dependent Rule Coverage (CDRC): CDRC as defined by Lämmel [6] is effectively a chained version of rule, Fig. 3. The graph constructed for the “addition” grammar. wherein we track which sequences of expansions are observed. This allows one to not only measure which production rules 4) k-path Coverage: For the grammar graph H = (N, E) are covered, but the context (i.e. the “parent” production rule) with nodes N and edges E ⊆ N × N , the paths of this graph in which those production rules are used. cdrc2 is defined P ⊆ N + are each sequences of nodes where: accordingly [6]: P = {x1 ⊔ · · · ⊔ xn ∈ N +

cdrc2 (i) = {(v1 , u1 v2 w1 ) ⊔ (v2 , x) ∈ R2 : (∃u, w ∈ (V ∪ Σ)∗ ) [S ⇒∗R uv1 w ⇒R uu1 v2 w1 w

(11)

⇒R uu1 xw1 w ⇒∗R i]} For purposes of comparison later, we generalize this coverage to chains of arbitrary length (for n > 2): cdrcn (i) = {(v1 , u1 v2 w1 ) ⊔ · · · ⊔ (vn , x) ∈ Rn : (∃u, w ∈ (V ∪ Σ)∗ )

(12)

[S ⇒∗R uv1 w ⇒R uu1 v2 w1 w ⇒R . . . ⇒R uu1 u... un−1 xwn−1 w... w1 w ⇒∗R i]} ∪ cdrcn−1 (i) Note especially the union with cdrcn−1 ; without this, cdrcn would fail to capture coverage over expansion sequences shorter than n. Note also that neither rule coverage nor CDRC have the ability to represent nested alternations or concatenations.

: (∀k ∈ [1, n))[(xk , xk+1 ) ∈ E]}

(13)

When we draw a derivation tree for a given input i, we are effectively drawing the set of paths (excluding synthetic nodes) taken over the corresponding grammar’s graph during expansion (hereon, Pi ⊆ P ). For example, the path ⟨expr⟩1 → · · · → “5” in the derivation tree shown in Fig. 2 directly corresponds to the path: ⟨expr⟩1 → |1 → ⟨number⟩1 → |2 → ⊔2 ,→ ⟨nonzero⟩1 → |5 → “5”

(14)

k-path coverage maps the set of all possible inputs I to the set of paths with length k in the graph H covered by the derivation tree of a given input, i.e. pathk : I 7→ P(P ). In the original k-path definition, coverage is computed for paths of exactly length k. In practice, because some paths to terminal nodes can only exist with lengths less than k [7] (similar to cdrcn ), k-path is typically computed for paths of length k

or less, as demonstrated by the original authors [11, 12]; we continue with this definition. pathk (i) = {p ∈ Pi : |p| ≤ k}

TABLE I C ORRELATION BETWEEN PATHk AND IDENT . B OLDED MEASUREMENTS ARE STATISTICALLY SIGNIFICANT (p < 0.01). Spearman’s ρ (pathk vs. ident)

(15) Grammar

Havrikov and Zeller [7] then propose that one build a fuzzer by sampling inputs that exercise previously-uncovered paths. III. E MPIRICAL R ESULTS ARE I NSUFFICIENT With the background now established, we motivate this work with a brief repudiation of previous evaluation practices when comparing two metrics. There are two versions of the k-path paper: one that was accepted to ASE in 2019 and an extended version published independently in 2023. In the original paper [7], the future work section suggests: One would assume that there would be strong correlations between individual language elements and some code in the program under test... which is subsequently evaluated in the extended version [15]: ... k-path input coverage positively correlates with code coverage [and is therefore] a useful objective for systematic generation of diverse inputs. The objective of this evaluation is to establish that as k-path coverage increases, so does code coverage—that is, there is a causal relationship between k-path and code coverage. However, correlation is not a reliable means by which to establish a causal relationship between metrics. To demonstrate this, we conduct a short experiment with the “identity” coverage metric, ident : I 7→ P(I): ident(i) = {i} (16)

JSON CSV URL

1-path

2-path

3-path

4-path

5-path

0.80 0.19 0.89

0.88 0.29 0.92

0.91 0.64 0.93

0.91 0.71 0.95

0.91 0.63 0.96

k almost immediately due to the uncomplicated nature of the grammar. This result reveals the issue with using correlation as a measure for the strength of a coverage metric: correlation reveals just as much about the sampling method as it does about the measured variables. The covering relationships explored in Section V grants greater insight into the nature of the relationships between metrics. When we show that one metric covers another, we show that it is more sensitive; an increase in one metric is necessarily observed as an increase in another that covers it. This does not necessarily reveal a strong causal relationship either; after all, ident trivially universally covers all test metrics, and we can arbitrarily construct metrics that are more sensitive than others without necessarily improving test performance. What covering reveals that correlation cannot is that methods that efficiently saturate one metric will saturate others covered by it, and that, in doing so, we test more of each subdomain of each covered metric. B. Correlating with Code

We know now that ident correlates with k-path, but does it correlate with code coverage? We reproduce Tables 2 and 5 of This is, for all intents and purposes, an input metric by the the extended k-path paper [15]3 in Table II by correlating with definitions from Section II-D: it maps each input in an input domain to a set of coverage points (here, exactly one input). cumulative branch coverage using the inputs from Section III-A. We can now study its correlation with other coverage metrics. The results are comparable with that of systematic generation, and are actually more correlated with branch coverage than A. Correlating with k-path k-path in many cases. Are we to take from this that ident is a We experiment using the tribble input generation tool strong predictor for code coverage? When sampling randomly, introduced in the k-path paper [7]. tribble comes equipped yes: this is the very basis for fuzz testing (“fuzzing”). In the with a “random” mode, allowing us to generate random inputs case of grammar-based fuzzing specifically, every program that from a given grammar. For direct comparisons, we use the parses based on a grammar contains some state machine that grammars from the correlation evaluation of the extended accepts or rejects a given input based on its conformance to k-path paper [15]2 , sampling 100 inputs or until k-path is that grammar. In typical implementations, program branches saturated. We merge the data from 50 trials and perform that correspond to a nonterminal expansion will only be visited Spearman rank correlation [16] between ident and pathk . if its parent’s branches are covered. When we sample random derivation trees, we cover code regions corresponding to the Results of this experiment are presented in Table I. Excluding CSV, we observe that the ident coverage metric is randomly selected nonterminal expansions. When the code is strongly correlated with pathk . In other words: executing more not already entirely covered, sampling more inputs will likely inputs increases k-path coverage. This makes sense! Since we cover more code. That said, this correlation is only strong for code regions are measuring over grammar, the probability that we cover more k-paths by sampling is simply an instance of the coupon corresponding to the actual parsing. Consider a program that collector’s problem [17]. CSV’s correlation and significance then does something with this parsed information; the code is low because random generation saturates k-path for small regions not pertaining to parsing would be covered merely by 2We do not use the Markdown grammar, as tribble exhausted system memory before completing a trial.

3 Subjects jackson-databind and galimatias-nu omitted as they no longer function.

TABLE II C ORRELATION AND ABSOLUTE RESULTS OF BRANCH AND IDENT : S PEARMAN ’ S ρ ( BOLDED WHERE p < 0.01) AND ARITHMETIC MEAN µ OF BRANCH COVERAGE . Subject

ρ

µ

JSON

argo fastjson genson gson json-flattener json-java json-simple json-simple-cliftonlabs json2flat minimal-json pojo

0.78 0.86 0.83 0.78 0.62 0.76 0.80 0.72 0.71 0.78 0.78

0.3959 0.0360 0.0880 0.2272 0.7100 0.1629 0.5719 0.3729 0.6647 0.4106 0.1278

CSV

commons-csv jackson-dataformat-csv jcsv sfm-csv simplecsv super-csv

0.74 0.65 0.66 0.54 0.69 0.66

0.3714 0.1467 0.3622 0.0721 0.4050 0.1695

URL

autolink galimatias jurl url-detector

0.84 0.87 0.76 0.89

0.5897 0.2452 0.6678 0.4621

Grammar

chance. Relating this to the end of Section III-A, one would need to show that k-path at least subsumes the subset of code coverage corresponding to parsing in order to claim any strong relationship. Anything beyond this is strictly a function of the distribution of inputs sampled and the probability of covering program semantics not expressed within the grammar. Correlation does not indicate that increasing k causes k-path to cover a subject more than simply taking more samples. Relying on correlation of test metrics leads to conflicting results according to the sampling method used [18, 19] and must not be used as justification for using one metric in place of another.

in the derivation tree. At nonterminals and concatenations, we always traverse the outgoing edge(s) in the graph; no matter what the next node is, it is involved in the expansion. At alternations, however, we only traverse one during expansion. This means that paths other than those between alternationvariant edges are redundant, as it can be inferred from the rules of derivation. To demonstrate the effect of this, consider the path from Eq. (14). The information expressed over this path by k-path for k = 2 is effectively no more than that already expressed by k = 1, since every node in the path is implied by either the presence of its parent or the presence of its child. In fact, because the grammar contains no nested alternations or concatenations (and therefore no path |i → |j or ⊔i → |j ), there are no inputs for which k-path for k = 2 expresses more information than k = 1. Yet, the number of paths of length 1 is 30; the number of paths of length 2 or fewer is 64, meaning that 34 of these paths are redundant. A. k-alt-path Definition The alt-paths A ⊆ P of the grammar graph H are the paths between and including the outgoing edges of alternations. That is, paths beginning with alternations and ending with immediate descendants of alternations as a result of expansion. With Nalt ⊂ N as the set of synthetic alternation nodes: A = {x1 ⊔ · · · ⊔ xn ⊆ P : x1 , xn−1 ∈ Nalt ∧ n > 1} (17) Ai = A ∩ P i

(18)

We then define altpathk : I 7→ P(A) like before for k > 1, but for paths over k or fewer outgoing edges from alternations. countalt(x1 ⊔ · · · ⊔ xn ∈ A) = |{j ∈ [1, n) : xj ∈ Nalt }| altpathk (i) = {p ∈ Ai : 1 ≤ countalt(p) ≤ k}

(19)

B. k-alt-path vs. k-path

Both pathk and altpathk are subdomain-based criteria. SDpathk are the subdomains of I corresponding to inputs Sections III-A and III-B consider correlation-based analysis for which the derivation tree traverses each path of length to compare two metrics with constrained random input genera- k, therefore the number of subdomains directly corresponds tion. Another common method to compare metrics is to generate to the number of paths: |SDpathk | = |{p ∈ P : |p| ≤ k}|. For inputs by sampling underrepresented features of each, like in altpathk , |SDaltpathk | = |{p ∈ A : countalt(p) ≤ k}|. 1) k-alt-path covers (k+1)-path: Every path p in a grammar the original k-path work [7]. While historically new metrics with paths P can be decomposed into subpaths, where for every emerge as objectives of generation, metrics themselves are subpath p′ and i ∈ I used to evaluate test suites from arbitrary sources. Evaluations which measure the performance of generation that optimizes p′ ⊆ p ∧ p ∈ Pi =⇒ p′ ∈ Pi (20) for some specific metric have value in empirically determining the efficacy of those generation strategies, but provide little When we subdivide the input domain by paths present in the derivation trees, the subdomain of inputs Dp for which the indication as to the properties of the metrics themselves. derivation trees that contain some path p are subdivided by IV. I MPROVING k- PATH M ETRIC paths that have p as a prefix: To demonstrate how one may more rigorously compare Q = {q : (∃x)[p ⊔ x ∈ P ]} [ metrics, we begin by refining k-path. We show that this new D = Dq (21) p metric is strictly more sensitive than k-path alone and requires q∈Q less computational resources. When we traverse from one node to another in the grammar This is necessarily the case as this subdivision enumerates all graph, that means that there was a corresponding expansion step paths of length |p| + 1 with p as a prefix, i.e., all the cases C. Other Empirical Comparisons

in which the path p appears. This similarly holds over sets of paths for which p is a suffix, and is recursively applicable: we can further subdivide Dp by subdividing any Dq . Having established that one can cover the input subdomains corresponding to the presence of paths in derivation trees, we can now show that altpathk covers pathk+1 . By the definition of paths, the logic presented at the start of Section IV, the expansion rules of grammars, ∀i ∈ I: x1 ⊔ x2 ∈ Ai ∧ x1 ∈ Nalt ⇐⇒ {x1 ⊔ x2 ⊔ x′3 ⊔ · · · ⊔ x′n ∈ P

: (∀k ∈ [2, n))[x′k ̸∈ Nalt ]} ⊆ Pi

Subject

k

j

|SDpathj−1 |

|SDaltpathk |

Ratio

“Addition”

1 2 3 5

4 7 10 15

110 294 591 1,362

17 30 45 88

6.5:1 9.8:1 13.1:1 15.5:1

CSV

1 2 3 5

4 7 10 16

830 2,360 5,095 20,765

199 298 497 1,661

4.2:1 7.9:1 10.3:1 12.5:1

REST

1 2 3 5

4 6 8 14

1,991 4,408 8,368 41,223

427 798 1,111 4,662

4.7:1 5.5:1 7.5:1 8.8:1

XML

1 2 3 5

4 6 9 15

816 2,105 6,550 31,696

152 350 823 3,411

5.4:1 6.0:1 8.0:1 9.3:1

(22)

: (∀k ∈ [3, n))[x′k ̸∈ Nalt ]} ⊆ Pi {S ⊔ x′2 ⊔ · · · ⊔ x′n ∈ P

TABLE III T HE RESULTS OF S ECTION IV-C FOR INCREASING k.

(23)

path1 and path2 are universally covered by altpath1 . There exists no grammar for which there exists an input i ∈ I such that there exists some path p ∈ Pi where |p| ≤ 2 that is not implicitly present in Pi due to the presence of either the start node S or some alternation-child pair x1 ⊔ x2 ∈ Pi . Each subdomain corresponding to each path is necessarily subdivided by some set of alt-paths, which cover each subdivision where this path is present, satisfying the covering relation by Eq. (21). By the same logic, pathk+1 is universally covered by altpathk because any path p ∈ Pi of length k+1 or less is implied by the presence of some other path p′ ∈ Ai where countalt(p′ ) ≤ k, and the subdomain corresponding to each path of length k + 1 or less is subdivided completely. Further, we expect that this should hold for pathj over many j > k + 1 because path redundancy increases as the grammar contains more nonterminal and concatenation nodes between alternation nodes. 2) Subdivision size: Since both pathk and altpathk rely on counting unique paths, computing these metrics requires both enumeration and storage of each potential path (and therefore has storage and computation requirements proportional to |SDpathk (X, Y )| and |SDaltpathk (X, Y )|, respectively). For every k, there exists some minimum j > k + 1 where pathj is not covered by altpathk because ∃p ∈ (Pi − Ai ) where |p| = j and countalt(p) = k. By construction, |SDaltpathk (X, Y )| = |{p ∈ Ai : 1 ≤ countalt(p) ≤ k}| |SDpathj−1 (X, Y )| = |{p ∈ Pi : 1 ≤ |p| ≤ j − 1}| |SDaltpathk (X, Y )| < |SDpathj−1 (X, Y )| In plain English, altpathk has lower storage requirements than pathj−1 , the maximum path that altpathk covers. This directly corresponds to a reduced computational effort as the number of paths that need to be counted during a coverage computation is reduced quadratically. Without loss of covering by Eqs. (20) and (21), we reduce the memory requirement even further by omitting paths contained by others. C. Evaluations on Real Grammars To demonstrate the degree to which subdivision counts differ, we evaluate the storage requirement and covering relationship

for increasing k on the “addition” grammar of Fig. 1 and the well-known context-free CSV, REST, and XML grammars4 taken from recent works that rely on k-path for diversity metrics [12, 11]. Our findings are presented in Table III. These results emphasize the degree of reduction achieved by k-altpath, which requires 5–10× less storage for small k than the corresponding (j − 1)-path, the effect of which compounds with increasing k. D. Interpreting k-alt-path In Section IV-B1, we demonstrate that k-alt-path covers (k + 1)-path and has fewer subdomains, therefore showing that k-alt-path is both more sensitive and efficient. In Section III-B, however, we reasoned that the finding that k-path correlates with code coverage is not a strong one. The latter would seem to undermine the former, but no: if the objective is to cover a grammar, then these metrics are perfectly suitable. k-alt-path is still superior as it tests more of each subdomain of (k + 1)path and requires significantly less computational resources. Nevertheless, one must not rely on grammar coverage as a proxy [20] for code metrics (e.g. branch coverage, mutant coverage [21], or fault coverage), as correlation neither guarantees an increase in code metrics nor considers code regions that are probabilistically uncovered by sampling derivation trees from grammars. V. OTHER I NPUT M ETRIC R ELATIONSHIPS Now that we have motivated use of the covers relationship, we now review the relationships between all input metrics discussed in this paper. These are enumerated in Table IV and Fig. 4. Most of these relationships may be shown simply by comparing their subdomains; if SDC2 is a subset of SDC1 , there is some subset of the subdomains of C1 that covers the subdomains of C2 . For example: rule covers altpath1 because every rule is either a variant of an alternation, or is the only 4 TAR is omitted as it depends on constraints to be parseable.

TABLE IV E XPLANATION OF COVERING BETWEEN INPUT METRICS . Edge

Reasoning

1† 2† 3 4 5 6‡ 7 8 9 10†‡ 11 12

uniq(SDaltpath1 ) ⊆ uniq(SDrule ) uniq(SDrule ) ⊆ uniq(SDpath1 ) See Section V-A1. See Section IV-B1. uniq(SDpathk ) ⊆ uniq(SDpathk+1 ) (definition) Shown by Lämmel [6]. uniq(SDcdrck ) ⊆ uniq(SDcdrck+1 ) (definition) uniq(SDaltpathk ) ⊆ uniq(SDaltpathk+1 ) (definition) See Section V-A2. See Section V-A3. uniq(SDgram≤k ) ⊆ uniq(SD gram≤k+1 ) (definition) All terminals must be covered.

† Requires no nested alternations or concatenations. ‡ Requires that start nonterminal has exactly one rule.

4

ident

pathk+1 10

gram≤k

altpathk

11. . .

8 ...

gram≤2

altpath2 8

11 gram1

12

9

9 1

altpath1

5

cdrck

pathk

7 ...

5 ...

cdrc2

path2

6

5 2

rule

path1

3 4 Fig. 4. Covering relationships between input metrics. C1 covers C2 if there is a path from C1 to C2 . Restrictions from Table IV denoted with dotted edges.

rule for that nonterminal, at least when nested alternations are forbidden. path1 covers rule for similar reasons; by the construction steps of the grammar graph in Section II-C2, there is at least one node that corresponds exactly to each expansion of each nonterminal. The remaining trivial covering relationships follow by their definition. A. Non-trivial Covering Relationships Not every covering relationship can be shown by comparing subdomains directly. To show that a metric C1 covers C2 , we must show that, for each subdomain of C2 , there exists some subset of subdomains of C1 that, when unioned, are exactly that subdomain. We explain why this holds for several pairs of metrics in the following subsections, though with less detail as they are each consequences of Section IV-B1. 1) 1-alt-path covers Rule Coverage: Each nonterminal in a well-formed grammar has one to many associated rules. When there are more than one associated rules, we represent this with an alternation; as a result, there is exactly one edge in the grammar graph corresponding to each variant in this alternation,

and altpath1 and rule share a corresponding subdomain of inputs formed by the paths to this edge. When a nonterminal has only one associated rule, the subdomain corresponding to the expansion of this rule is subdivided by the previous rule expansions or the start node; this is a result of Eqs. (22) and (23). Therefore, rule is covered by altpath1 , because there is no rule for which there is not some subdividing set of alternation-variant pairs. 2) k-alt-path covers CDRC-k: cdrck is effectively the chained version of rule coverage, like altpathk is the extended form of alternation coverage. Every sequence of expansions is the union of subdomains formed by subsets of sequences of alternation-variant pairs in the grammar graph (i.e., the rule expansions), just like rule. 3) CDRC-k covers (k + 1)-path: Expansion sequences correspond quite well to paths in the grammar graph when forbidding nested alternations and concatenations. An expansion corresponds to two entries in the graph: the nonterminal and its immediate descendant (when the nonterminal has exactly one rule) or the nonterminal’s alternation and its immediate descendant. When considered together, a sequence of k expansions corresponds to, minimally, paths of length k+1 in the grammar graph; for the same reasons as the previous two metric relationships and Section IV-B1, this suggests that cdrck covers pathk+1 , but not vice versa, as the introduction of any alternations or concatenations increases this path length. B. Lexical vs. Syntactic Coverage Table IV and Fig. 4 reveals no relationships between gram≤n and any syntactic input metrics for n ≥ 2. The reason for this is simple: there are no universal covering relationships between gram≤n and any syntactic metric for any n ≥ 2. We may demonstrate this by counterexample. 1) n-or-less-gram does not subsume rule coverage: Recall that subsumption is implied by covering; if a metric cannot subsume another, then it also cannot cover it. rule is the weakest syntactic coverage; if we cannot subsume rule, then we cannot subsume any other syntactic metric. Choose an arbitrary n ≥ 1; we may construct a grammar ⟨{S}, Σ, {S} × Σn+1 , S⟩. For gram≤n to subsume rule, its satisfaction must imply the satisfaction of rule, but it trivially does not. We may select an arbitrary terminal symbol x ∈ Σ and a subset of inputs I ′ = {x ⊔ y : y ∈ Σn } ⊂ Σn+1 = I. I ′ saturates gram≤n , but I is the minimum set of inputs to saturate rule; since I ′ ⊂ I, gram≤n does not subsume rule. 2) k-alt-path does not subsume 2-or-less-gram: altpathk is the strongest syntactic metric defined in this paper; if it cannot universally cover gram≤2 , no syntactic metric defined in this paper can. For arbitrary k, we can construct a grammar G = ⟨V, Σ, R, S⟩ such that: V = {u, v1 , . . . , vk } Σ = {x1 , x2 } ∪ {y1 , . . . , yk } R = {(S, uv1 ), (u, x1 ), (u, x2 )} ∪ {(vj , yj ) : j ∈ [1, k]} ∪ {(vj , vj+1 ) : j ∈ [1, k)}

As a result, I = {x1 , x2 } × {y1 , . . . , yk } ⊂ Σ2 ; only I will saturate gram≤2 . I ′ = {x1 y1 } ∪ {x2 yj : j ∈ [2, k]} saturates altpathk . Since I ′ ⊂ I, altpathk does not subsume gram≤2 .

counterexample to the claim that strong correlation indicates a strong causal relationship between metrics, obviating this threat. Internal: The findings of Sections III-A and III-B are VI. D ISCUSSION subject to the random set of inputs produced by tribble [7]. Before concluding, we discuss the limitations, threats to In degenerative cases, the correlation might be weaker than validity, the implications of this paper, and related work that presented here. We control for this by performing several trials, covers similar ground to ourselves. and reiterate that these measurements serve as a counterexample rather than evidence for a general claim. A. Limitations Construct: The findings of Sections III-A and III-B use k-alt-path, like k-path, is not well-defined for CFG exten- the random generator of tribble configured with a maximum sions like repetitions. Furthermore, while we establish the depth of 100. This implements a depth-limited derivation tree covering relationship for input metrics, covering alone does generator with random decisions local to alternations being not indicate superiority in fault detection. Those familiar with sampled. Other methods for random derivation tree generation the work of Frankl and Weyuker [14] will notice that this paper exist, so while this is the most typical and straightforward does not attempt to establish the properly covers relationship implementation, these results may not represent all forms of between metrics. A given test adequacy metric properly covers random derivation tree sampling. Additionally, we sample up another if it covers uniquely, where no subdomain is used to 100 inputs in both experiments. The choice of the number more than once in the covering of the subdomains of the of samples is arbitrary, and other choices may reveal differing other metric. k-alt-path trivially does not properly cover k-path strengths of correlation. Given that this experiment serves simply because k-path has more subdomains. This distinction primarily as an example of how correlation can be misleading, is crucial, as one can establish that if one metric properly we believe that neither of these threats invalidate our findings. covers another, then it is also necessarily superior at fault detection [14] under the failure rate model [22], whereas this C. Implications for Modern Fuzzing In Section IV-C, we consider grammars from works that is not the case for the covering alone. That said, the proof for this claim is in the context of partition testing, where prototype a relatively new class of fuzzing, called languageeach subdomain is sampled exactly once regardless of whether based testing (LBT) [12, 11]. These fuzzers use grammars that subdomain has already been covered by other samples. in combination with constraints to produce inputs that satisfy This is not the model under which we test programs with requirements beyond syntactic validity. An open question in random inputs, where we either (1) generate inputs without LBT and other modern input generation strategies is how regard to input subdomains, or (2) continuously produce inputs. one produces diverse inputs; while both ISL A [12] and We suggest that covering likely does indicate superior fault FANDANGO [11] achieve some amount of syntactic diversity detection under the failure rate model in fuzzing, but proving as measured by k-path, it is so far unclear whether this (in this would require a better model of fuzzer behavior and may the context of their constrained generation) corresponds to an fail to hold for certain classes of fuzzers (e.g., mutational increased semantic diversity. Indeed, for FANDANGO in particcoverage-guided fuzzers [23]). As such, we defer this to future ular (which uses evolutionary search to satisfy constraints), this question is critical for ensuring satisfaction of multitudinous work. constraint systems [24]. In the same way that lexical and B. Threats to Validity syntactic diversity have no covering relationships as explored Tables I to III are results from empirical evaluations. As in Section V-B, the same is likely true for semantic diversity such, they must be caveated with potential threats that may (e.g., there are likely many desirable metrics that would not affect their correctness and generality. be captured by grammar-agnostic ones). The misalignment of External: The selection of grammars in Section IV-C was generation objectives and the metrics used to diversify inputs in based on grammars present in other evaluations of works generation processes of LBT, LLM-based test generation, and utilizing the k-path. We do not claim that these results are other specialized generators demands future work that develops representative for all grammars; indeed, we can construct metrics that can truly measure the semantic diversity of test grammars for which the resource requirement ratios between k- cases. alt-path and k-path are significantly lower. The general, weaker Furthermore, our work demonstrates that the comparison claims of minimal j-path not covered by k-alt-path and resource of metrics must be heavily scrutinized. Correlation of metrics requirements are justified in Section IV-B1 and Section IV-B2, spontaneously emerging merely as a result of sampling indicates respectively. that conclusions based on correlation must be extremely specific Similarly, the correlation of the identity metric with k-path as to the sampling pattern used and denote that results are not and branch coverage presented in Sections III-A and III-B general. Comparisons that consider performance (e.g., by Mannmay only be the case for these grammars, which were selected Whitney U, as per fuzzing evaluation standard [25]) must ensure due to their presence in a previous work [15]. Only showing to compare against reasonable baselines (e.g. ident presented that this correlation is present for a few grammars serves as a here) along comparable objectives (e.g., time or number of

generated inputs), but ultimately compare generation techniques, not metrics. Works performing metric or technique comparisons should also consider set-theoretic analyses that do not remove nuance about how these metrics are covered [26], as aggregate comparisons can obscure the differences between approaches. D. Related Work

binary context-sensitive grammars, whereas the grammars presented in this paper are restricted or reduced to context-free. Semantic coverage metrics have been defined, but are often too complex to see widespread adoption. Kalinov et al. [13] introduce a number of semantic coverage metrics specific to compiler testing, namely those based on abstract state machines (historically, “evolving algebras”) [33] and tree-finite state machines [34]. This work then generates test cases which increasingly satisfy these metrics, finding several faults. As far as we could find, there are no works which subsequently attempt to use these metrics. Schumi and Sun [35] identified (though do not experiment to confirm) that the computational cost of these metrics were prohibitive, and improve upon them by making their measurement tractable for large-scale testing. They do not relate the strength of their metric against that of Kalinov et al. [13], but their prototype reveals a number of faults in the Java and Solidity compilers with relatively few test cases, taking several weeks to generate and execute. So far, we could not find any work that has evaluated whether guidance by input semantic coverage metrics meaningfully improve fault coverage over syntactic coverage metrics or traditional mutational code coverage-guided fuzzers alone. These questions remain open for future works which generate highly constrained inputs.

Partition Testing: Our work retreads numerous findings; Section III mostly discusses known consequences of comparing metrics with statistical modeling [27, 28]. The network of covering relationships presented in Section V was inspired largely by Zhu [29], which builds a network for the subsume relation between various code coverage metrics. Presenting new metrics that improve upon existing metrics and proving their relationships is a motif of partition testing literature [30], and we happily extend this tradition to input metrics. We hope this paper will act as a bridge for new research in input generation techniques to engage with partition testing works, which provide methods to reason about new metrics. Statistical fuzzer modeling: Likewise, we believe our findings are related to other recent studies of test adequacy metrics in fuzzing literature. Böhme et al. [19] showed recently that, while code coverage and fault coverage are very strongly correlated, there is no strong agreement between these metrics. VII. C ONCLUSION In other words, while one can predict that a fuzzer with high coverage will also find more faults, one cannot predict the In this paper, we outline, justify, utilize, and systematize ranking of a collection of fuzzers by fault coverage from existing partition testing techniques for comparing input-based the ranking by code coverage. While initially puzzling, this test adequacy criteria (i.e., input metrics). We do this to result is, in essence, the same observation of our analysis create a foothold for future research in developing input in Section III-B: while increasing aggregate code coverage metrics for new problems facing the testing field, like those guarantees that more code will be tested, it says nothing about of complex input generation. In the course of our work, we which code regions are tested nor the depth to which those significantly improve k-path with k-alt-path, doing so using code regions are tested. Moreover, the correlative result shares partition testing analysis to identify desirable metric properties, further similarity with Section III-A: while code coverage namely concision and sensitivity. For now, we hope that this correlates with fault coverage, this also says nothing about work serves to bring interest to the development of new metrics, the degree to which code coverage covers fault coverage. In identifying and remediating weaknesses in those that already the context of test suites, where there is greater dissimilarity exist and exploring new ways to describe and understand our between individual suites, this correlation weakens [18]. test suites. In future work, we plan to use this analysis further by Other input metrics: Though we discuss several syntactic developing language-specific semantic metrics and integrating input metrics in this paper, there are a few niche metrics which them into modern input generation tools. are not compared in this paper due to dissimilarity in their A RTIFACT AVAILABILITY design. There are quite a few such works; we review the most All code used in this work may be found on Zenodo: prominent or related to this work below. From the syntactic approach, Lämmel and Schulte [31] https://doi.org/10.5281/zenodo.19251724 considers combinatorial coverage, or the coverage of entire derivation trees up to a certain depth or at certain boundaries. This artifact directly constructs Tables I to III and includes This trivially covers many of the path-based metrics presented experimental data which was generated or measured during in this paper, but is exponential with depth. To refine this, our evaluation for reference. This code should execute on Lämmel and Schulte also consider a number of “control any modern consumer Linux computer and is not affected by mechanisms” which mitigate this exponentiality at the cost performance. of some completeness. Fryer et al. [32] defines a grammar ACKNOWLEDGMENTS coverage metric based on the pairs of grammar elements encountered during pre-order traversal of the derivation tree, A deep thank you to all my colleagues who reviewed this giving a “horizontal” coverage compared to the “vertical” work, especially Keno Hassler, Jasper von der Heidt, Moritz syntactic metrics discussed in this paper. It additionally defines Schloegel, Sahil Sihag, Alexi Turcotte, Xinyi Xu, José Antonio synthetic nonterminals to represent certain fields present in Zamudio Amaya, and Andreas Zeller, who suffered through

far denser, rougher drafts. A second thanks to Andrew Fryer, Benjamin Kushigian, and Marcel Böhme for their insightful comments which eventually led to the creation of this paper. I would also like to thank my supervisor, Thorsten Holz, and the Saarbrücken Graduate School of Computer Science for their respective support in my doctoral studies. R EFERENCES [1] C. E. Shannon, “The redundancy of English,” Transactions of the 7th Conference on Cybernetics, pp. 248–272, 1951. [2] N. Chomsky, “Three models for the description of language,” IEEE Transactions on Information Theory, vol. 2, no. 3, p. 113–124, 1956. [3] G. K. Pullum and G. Gazdar, “Natural languages and context-free languages,” Linguistics and Philosophy, vol. 4, no. 4, p. 471–504, 1982. [4] P. Purdom, “A sentence generator for testing parsers,” BIT Numerical Mathematics, vol. 12, no. 3, 1972. [5] A. Celentano, S. C. Reghizzi, P. D. Vigna, C. Ghezzi, G. Granata, and F. Savoretti, “Compiler testing using a sentence generator,” Software: Practice and Experience, vol. 10, no. 11, p. 897–918, 1980. [6] R. Lämmel, Grammar Testing, ser. Lecture Notes in Computer Science. Berlin, Germany: Springer, 2001, vol. 2029, p. 201–216. [7] N. Havrikov and A. Zeller, “Systematically covering input structure,” in 34th IEEE/ACM International Conference on Automated Software Engineering. New York, NY, USA: IEEE, 2019, pp. 189–199. [8] J. Zhang, X. Hu, C. Gao, X. Xia, and S. Li, “Enhancing automated unit test generation with large language models: A systematic literature review,” ACM Transactions on Software Engineering Methodology, 2026. [9] X. Yang, Y. Chen, E. Eide, and J. Regehr, “Finding and understanding bugs in C compilers,” in 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, M. W. Hall and D. A. Padua, Eds. New York, NY, USA: ACM, 2011, pp. 283–294. [10] S. Groß, “Fuzzil: Coverage guided fuzzing for javascript engines,” Master, Karlsruhe Institute of Technology, Karlsruhe, Germany, 2018. [Online]. Available: https: //saelo.github.io/papers/thesis.pdf [11] J. A. Zamudio Amaya, M. Smytzek, and A. Zeller, “FANDANGO: evolving language-based testing,” Proceedings of the ACM on Software Engineering, vol. 2, no. ISSTA, pp. 894–916, 2025. [12] D. Steinhöfel and A. Zeller, “Input invariants,” in 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering. New York, NY, USA: ACM, 2022, pp. 583–594. [13] A. Y. Kalinov, A. S. Kossatchev, A. K. Petrenko, M. Posypkin, and V. Shishkov, “Coverage-driven automated compiler test suite generation,” in Workshop on Language Descriptions, Tools and Applications, ser. Electronic Notes in Theoretical Computer Science, no. 3. Amsterdam, Netherlands: Elsevier, 2003, pp. 500–514.

[14] P. G. Frankl and E. J. Weyuker, “A formal analysis of the fault-detecting ability of testing methods,” IEEE Transactions on Software Engineering, vol. 19, no. 3, pp. 202–213, 1993. [15] N. Havrikov, A. Kampmann, and A. Zeller, “From input coverage to code coverage: Systematically covering input structure with k-paths,” 2023. [16] C. Spearman, “The proof and measurement of association between two things,” The American Journal of Psychology, vol. 15, no. 1, p. 72, 1904. [17] P. Flajolet, D. Gardy, and L. Thimonier, “Birthday paradox, coupon collectors, caching algorithms and selforganizing search,” Discrete Applied Mathematics, vol. 39, no. 3, pp. 207–229, 1992. [18] L. Inozemtseva and R. Holmes, “Coverage is not strongly correlated with test suite effectiveness,” in 36th International Conference on Software Engineering. New York, NY, USA: ACM, 2014, p. 435–445. [19] M. Böhme, L. Szekeres, and J. Metzman, “On the reliability of coverage-based fuzzer benchmarking,” in 44th IEEE/ACM International Conference on Software Engineering. New York, NY, USA: ACM, 2022, pp. 1621–1633. [20] K. Serebryany, M. Lifantsev, K. Shtoyk, D. Kwan, and P. Hochschild, “Silifuzz: Fuzzing CPUs by proxy,” arXiv, vol. abs/2110.11519, 2021. [21] T. T. Chekam, M. Papadakis, Y. L. Traon, and M. Harman, “An empirical study on mutation, statement and branch coverage fault revelation that avoids the unreliable clean program assumption,” in 39th International Conference on Software Engineering. New York, NY, USA: IEEE / ACM, 2017, pp. 597–608. [22] T. A. Thayer, M. Lipow, and E. C. Nelson, Software reliability: a study of large project reality, ser. TRW Series of Software Technology. Amsterdam, Netherlands: North-Holland Publ. Co, 1978. [23] V. J. M. Manès, H. Han, C. Han, S. K. Cha, M. Egele, E. J. Schwartz, and M. Woo, “The art, science, and engineering of fuzzing: A survey,” IEEE Transactions on Software Engineering, vol. 47, no. 11, pp. 2312–2331, 2021. [24] K. Deb, “Multi-objective genetic algorithms: Problem difficulties and construction of test problems,” Evolutionary Computation, vol. 7, no. 3, p. 205–230, 1999. [25] M. Schloegel, N. Bars, N. Schiller, L. Bernhard, T. Scharnowski, A. Crump, A. A. Ebrahim, N. Bissantz, M. Muench, and T. Holz, “Sok: Prudent evaluation practices for fuzzing,” in 45th IEEE Symposium on Security and Privacy. New York, NY, USA: IEEE, 2024, pp. 1974–1993. [26] A. Crump, S. Sihag, and M. Leonelli, “SBFT’25 competition report - fuzzing track,” in 2025 IEEE/ACM International Workshop on Search-Based and Fuzz Testing. New York, NY, USA: IEEE, 2025, pp. 9–12. [27] A. S. Namin and J. H. Andrews, “The influence of size and coverage on test suite effectiveness,” in 18th International Symposium on Software Testing and Analysis. New York,

NY, USA: ACM, 2009, pp. 57–68. [28] M. Staats, G. Gay, M. W. Whalen, and M. P. E. Heimdahl, “On the danger of coverage directed test case generation,” in 15th International Conference on Fundamental Approaches to Software Engineering, ser. Lecture Notes in Computer Science, vol. 7212. Berlin, Germany: Springer, 2012, pp. 409–424. [29] H. Zhu, “A formal analysis of the subsume relation between software test adequacy criteria,” IEEE Transactions on Software Engineering, vol. 22, no. 4, pp. 248–255, 1996. [30] H. Zhu, P. A. V. Hall, and J. H. R. May, “Software unit test coverage and adequacy,” ACM Computing Surveys, vol. 29, no. 4, pp. 366–427, 1997. [31] R. Lämmel and W. Schulte, “Controllable combinatorial coverage in grammar-based testing,” in 18th International Conference on Testing of Communicating Systems, ser. Lecture Notes in Computer Science. Berlin, Germany: Springer, 2006, pp. 19–38. [32] A. Fryer, T. Dean, and B. Lachine, “Input output grammar coverage in fuzzing,” in 41st IEEE Military Communications Conference. New York, NY, USA: IEEE, 2023, pp. 937–943. [33] Y. Gurevich, “Evolving algebras 1993: Lipari guide,” in Specification and validation methods. Oxford, UK: Oxford University Press, 1993, pp. 9–36. [34] P. W. Kutter and A. Pierantonio, “Montages specifications of realistic programming languages,” Journal of Universal Computer Science, vol. 3, no. 5, pp. 416–442, 1997. [35] R. Schumi and J. Sun, “Spectest: Specification-based compiler testing,” in 24th International Conference on Fundamental Approaches to Software Engineering, ser. Lecture Notes in Computer Science. Berlin, Germany: Springer, 2021, pp. 269–291.