Alias Coverage Criterion

Definition

The alias coverage criterion is a coverage metric introduced in the paper Code-based Test Generation for Validation of Functional Processor Descriptions to estimate how well a generated test suite exercises the different possible relationships between array indices. It is part of the broader approach to array constraint handling in constraint-based test generation.

Motivation and Context

When generating tests for programs that manipulate arrays, the constraint solver must reason about the relationships between index expressions appearing in array accesses. For an expression involving n indices, the number of distinct ways the indices can be related (i.e., the number of partitions of an n-set) is the nth Bell number b_n [1]. Although Bell numbers grow exponentially, this combinatorial explosion is acceptable in practice because only a correct combination of index relationships consistent with the program's constraints needs to be searched for.

The alias coverage criterion formalizes the goal of covering these distinct index-relationship choices, making it a meaningful measure of test thoroughness for array-manipulating code.

Purpose: Verifying Self-Referencing Memory

The criterion is particularly useful for verifying self-referential memory patterns, such as:

mem[mem[i]] where mem[i] = i

In such cases, the value stored at one index is itself used as an index into the same array, creating an aliasing relationship that must be exercised by tests to detect aliasing-related defects.

Advantages

Defining a criterion over index relationships (rather than over individual indices independently) provides several benefits in constraint-based test generation:

• Variable independence analysis can be performed to split the constraint store into independent groups of variables, simplifying solving.
• Graph analysis can be applied to deduce heuristics for variable ordering, improving the performance of the constraint solver.

Drawbacks

The main drawback of this approach is that the choice of relationships between indices can be inconsistent with other constraints in the store. For example, it may not be possible to choose Y = X and simultaneously generate a test satisfying a given path constraint. The approach relies on:

1. The backtracking mechanism of the constraint solver to recover from such failures, and
2. A symbolic solver, which in many cases avoids inconsistent index-relationship choices altogether.

Role in the Larger Framework

The alias coverage criterion is one component of the array constraint handling strategy used in constraint-based test generation. The underlying constraint solver operates on finite domains (integers or naturals) and uses arc-consistency techniques. The overall solving process consists of two phases:

1. Domain reduction through local propagation techniques.
2. A labeling phase that iteratively grounds variables and propagates effects, with heuristic choices for variable and value ordering.

Coverage criteria such as the alias coverage criterion then measure how thoroughly a generated test set exercises the combinatorial space of index relationships.