Black-box models are increasingly deployed in high-stakes domains such as education, personnel hiring, and credit assessment, making systematic and auditable fairness testing particularly important. In such settings, black-box fairness testing is typically modeled as a search problem aiming to discover biases in the target model as much as possible. However, existing methods offer limited support for verifiable evaluation on a clearly stated, data-supported test domain: which reasonable regions have been tested, which have not, and whether exploration is balanced across the test domain remain unclear. This paper redefines black-box fairness testing as an auditable process on a data-supported, reasonable input domain. We first construct a reasonable region from the reference data and divide it into a finite set of local coverage units. Then, we introduce a coverage scheduler that distributes testing work among the units and explicitly records tested and untested regions, thus achieving reproducible and verifiable sufficient testing. To improve discriminative discovery capabilities without compromising the coverage foundation, we further design a structure-aware intra-unit search mechanism that combines a structure-aware discriminative field (SDF) and directional influence refinement (DIR). Experiments on multiple real-world tabular datasets show that our method enables auditable unit-level coverage accounting and achieves more balanced coverage, higher sample naturalness, and higher discrimination discovery effectiveness than representative black-box fairness testing baselines. Moreover, the discovered instances are effective for mitigating individual fairness violations through retraining.

@inproceedings{paperbot12461,
  title = {Towards Verifiable Fairness Testing: Auditable Coverage over Data-Supported Input Domains},
  author = {Yingqian Guo and Wentian Zhao and Tian Song},
  booktitle = {ASE},
  year = {2026},
  doi = {10.1145/3832783.3834430}
}