Source-linked AI summary
Fairness Testing: Testing Software for Discrimination
Sainyam Galhotra, Yuriy Brun, Alexandra Meliou
TL;DR
Software increasingly makes consequential decisions, but existing fairness measures can miss discrimination because they do not capture causal input-output relationships. The paper defines causal software discrimination and develops Themis, which automatically generates oracle-free tests from an input schema. Across its evaluation, Themis detects discrimination effectively and uses pruning to reduce test-suite sizes by two to three orders of magnitude.
Problem
Existing discrimination measures can miss causal disparities or be circumvented, while fairness testing lacks an automated way to measure causal discrimination.
Method
Themis uses a causal fairness definition and automatically generates discrimination tests from a schema describing valid inputs without requiring an oracle.
Results
Themis effectively finds group and causal discrimination, while provably sound pruning reduces test-suite sizes on average by two to three orders of magnitude.
Takeaways & Limitations
Fairness testing can help developers and stakeholders identify and reason about software discrimination during software development.
Takeaways & Limitations
The analysis models software as a black box with categorical input and output characteristics, and partial input domains can mask or affect measured discrimination.
Abstract
from arXiv · showhide
This paper defines software fairness and discrimination and develops a testing-based method for measuring if and how much software discriminates, focusing on causality in discriminatory behavior. Evidence of software discrimination has been found in modern software systems that recommend criminal sentences, grant access to financial products, and determine who is allowed to participate in promotions. Our approach, Themis, generates efficient test suites to measure discrimination. Given a schema describing valid system inputs, Themis generates discrimination tests automatically and does not require an oracle. We evaluate Themis on 20 software systems, 12 of which come from prior work with explicit focus on avoiding discrimination. We find that (1) Themis is effective at discovering software discrimination, (2) state-of-the-art techniques for removing discrimination from algorithms fail in many situations, at times discriminating against as much as 98% of an input subdomain, (3) Themis optimizations are effective at producing efficient test suites for measuring discrimination, and (4) Themis is more efficient on systems that exhibit more discrimination. We thus demonstrate that fairness testing is a critical aspect of the software development cycle in domains with possible discrimination and provide initial tools for measuring software discrimination.
1 INTRODUCTION
Software increasingly makes autonomous decisions in high-stakes domains, making fairness and nondiscrimination as important as software quality. The paper defines causal software discrimination and introduces Themis, an automated testing approach that measures it without an oracle.
- Software decisions increasingly affect purchasing, lending, driving, medical care, and criminal justice, raising the importance of fairness and nondiscrimination.
- The paper’s causal definition detects discrimination that correlation, group-output fractions, probability distributions, or real-world input restrictions can miss.
- Provably sound pruning yields two-to-three orders of magnitude smaller test suites, while Themis is effective on systems exhibiting more discrimination.
- Themis automatically generates discrimination test suites from an input schema and uses output equivalence as an oracle.
2 SOFTWARE FAIRNESS MEASURES
Group discrimination compares outcome distributions across groups but can miss causal disparities or be circumvented. The paper therefore defines causal discrimination by testing otherwise identical inputs that differ only in specified characteristics.
- Group discrimination judges fairness by comparing outcome fractions across groups, such as loan approval rates for applicants below and above age 40.
- 10% group discrimination results when the largest and smallest loan outcome fractions are 40% and 30%, respectively, under the Calders-Verwer score.
- Group discrimination can score zero when opposite discriminatory effects cancel across otherwise identical applications.
- A system can appear perfectly fair by randomly approving 30% of one group while approving the 30% highest-savings applicants from another group.
- Causal discrimination tests whether changing only specified characteristics changes outputs for otherwise identical individuals.
- Apparent discrimination measures group or causal discrimination on partial input domains and depends on the system’s operational profile.
3 FORMAL FAIRNESS DEFINITIONS
The paper distinguishes group-level output disparities from causal discrimination, which tests whether changing specified input characteristics changes outputs for otherwise identical inputs. It formalizes these measures over full or partial input domains while assuming categorical characteristics and outputs for simplicity.
- Model and assumptions: The formalization models software as a black-box mapping from input characteristics to an output and assumes categorical input and output variables.Multiple outputs are handled separately, while non-categorical values can be approximated through binning.
- Group discrimination: Group discrimination measures the gap between the highest and lowest fractions of inputs producing a true output across characteristic-defined groups.For one characteristic, the score is max(P) − min(P).
- Causal discrimination: Causal discrimination measures the fraction of inputs for which changing specified characteristics causes the software output to change.The comparison input differs only in the selected characteristics.
- Input domains: Apparent discrimination applies group or causal scores to a specified subset of the input domain rather than all possible inputs.Partial domains can mask discrimination or create correlations between characteristics that affect measured discrimination.
- Discrimination checking: Discrimination checking computes characteristic subsets whose group or causal discrimination scores meet a threshold θ.The problem considers all relevant subsets X′ of the input type X.
4 THE THEMIS SOLUTION
Themis generates and evaluates fairness test suites from an executable, input schema, confidence level, and error bound. It combines caching, adaptive sampling, and sound pruning to reduce testing costs while measuring group or causal discrimination.
- Themis interface: Themis accepts an executable, confidence level, error bound, and input schema to generate or evaluate discrimination test suites.It supports score computation, threshold-based characteristic-set search, and apparent discrimination over supplied test suites or operational profiles.
- Scope of confidence: Themis does not compute confidence for the score when the test suite or operational profile is assumed representative of real-world executions.The resulting confidence depends on developers’ confidence in that representativeness.
- Testing challenge: Exhaustive discrimination testing is infeasible because exact scores require many executions and checking all characteristic subsets grows exponentially.Themis therefore approximates scores and searches the subset space selectively.
- Optimizations: Three optimizations—test caching, adaptive confidence-driven sampling, and sound pruning—reduce the number of test cases needed for group and causal discrimination.Caching reuses executions across related tests and characteristic sets.
- Adaptive sampling: Adaptive sampling generates uniform random inputs and stops when the estimated error is below the requested bound at the desired confidence level.Themis tracks the proportion of positive outputs or output changes while sampling.
- Causal testing: CausalDiscrimination compares a random input with inputs differing in one or more selected characteristics, reusing cached executions where available.The comparison identifies whether changing the selected characteristics changes the output.
- Sound pruning: Themis prunes all supersets of a characteristic set once that set exceeds the discrimination threshold, using discrimination monotonicity.The pruning strategy is sound because supersets cannot have lower group or causal discrimination scores.
- Sound pruning: Pruning reduces test-suite size by two-to-three orders of magnitude on average.This empirical reduction is reported for the discrimination search procedure.
5 EVALUATION
The evaluation examines Themis on twenty financial-decision software instances, including systems designed to avoid discrimination. Themis finds substantial causal discrimination that group measures and discrimination-aware designs can miss, while pruning sharply reduces testing costs.
- Evaluation Setup: Twenty instances of eight financial-decision systems were evaluated across three experiments; seventeen were developed by original system developers.Eight instances used standard machine-learning algorithms, and the subjects used the Adult Census Income and Statlog German Credit datasets.
- Race and Gender Discrimination: Causal discrimination exposed cases missed by group discrimination, with B census gender showing 11.27% causal versus 0.52% group discrimination.The causal score was more than 21× higher than the group score.
- Computing Discriminated-Against Characteristics: F census discriminated against country and race for 98.1% of individuals under the causal score.Changing only the listed sensitive characteristics caused the algorithm’s output to flip for that fraction.
- Computing Discriminated-Against Characteristics: B census gender had a causal score of 77.2% against gender, marital status, and race, compared with 11.2% against gender alone.This shows that discrimination can become severe for particular characteristic sets even when a single-characteristic score is lower.
- Themis Efficiency and the Pruning Effect: Pruning reduced test-suite sizes by average factors of 2,849 for group and 148 for causal discrimination.Themis becomes more efficient as discrimination increases because small discriminating characteristic sets allow larger supersets to be pruned.
- Discussion: Overall, Themis detected both group and causal discrimination, while state-of-the-art fairness-aware approaches often missed discrimination.Across experiments, pruning reduced test-suite sizes by two to three orders of magnitude on average.
6 RELATED WORK
Related work spans fairness metrics, causal testing, operational profiles, combinatorial testing, and automated test generation. Themis differs by automatically generating tests for software and measuring causal discrimination.
- Fairness Measurement: The group discrimination score generalizes the Calders-Verwer score to software with more complex inputs, while the causal score measures causality.Themis therefore extends prior classifier-oriented discrimination measurement toward software behavior.
- Fairness Measurement: FairTest uses manually written tests and correlation-based measures, whereas Themis automatically generates tests and measures causal discrimination.The contrast concerns both test generation and the type of discrimination measured.
- Causal Testing: Causal testing compares similar inputs with different outputs, but correlated characteristics can make independently perturbed inputs unrepresentative of real-world cases.FairML co-perturbs characteristics using orthogonal projection, which can mask some discrimination while finding more realistic cases.
- Test Generation: Combinatorial testing reduces tests for selected combinations of input values, offering a related strategy for controlling exhaustive-test costs.Its examples include all-pairs testing for software product lines.
- Black-Box Testing: AdFisher measures a variant of group discrimination without explicit software access, and its approach could be integrated with Themis to measure causal discrimination.This positions Themis as compatible with some black-box discrimination-testing settings.
- Operational Profiles: Themis can measure apparent discrimination using developer-provided test suites or operational profiles describing field-observed input distributions.Operational-profile test-generation techniques are complementary to Themis.
7 CONTRIBUTIONS
The paper formalizes fairness testing around causal discrimination and presents Themis as an efficient, open-source approach for measuring it. Its evaluation and proofs support fairness testing as a way to assess discrimination in consequential software.
- Definitions: The paper formally defines software fairness testing and introduces a causality-based measure of discrimination.The definition and measure connect fairness assessment to relationships between inputs and outputs.
- Themis: Themis measures software discrimination and generates efficient test suites for those measurements.The approach includes an open-source implementation.
- Findings: The evaluation reports that discrimination is common even when fairness is an explicit design goal, and that Themis effectively measures it.The paper also formally proves the soundness of its approach.
- Implications: The paper argues that fairness testing is critical as software is increasingly used in society-critical ways.It presents the work as an initial step toward combining testing techniques with software fairness requirements.