Source-linked AI summary
Automated Test Generation to Detect Individual Discrimination in AI Models
Aniya Agarwal, Pranay Lohia, Seema Nagar, Kuntal Dey, Diptikalyan Saha
TL;DR
Individual discrimination occurs when people who differ only in protected attributes receive different decisions, but exhaustive testing is infeasible for non-trivial systems. The paper combines symbolic execution with local explanations to generate black-box test inputs for finding such cases. It reports better performance than THEMIS across its chosen benchmarks.
Problem
Individual discrimination is a difference in decisions for people with identical non-protected attributes but different protected attributes, and exhaustive testing for it is infeasible on non-trivial systems.
Source: §1 · p. 1Method
The technique uses local explanations as paths for symbolic execution to generate test inputs for black-box models.
Source: §1 · p. 2Results
The technique performs better than THEMIS on several open-source classification models containing known biases.
Source: §1 · p. 2Takeaways & Limitations
The paper presents a black-box test-generation technique that combines symbolic execution and local explanation to check models for individual discrimination.
Source: §1 · p. 2, §7 · p. 7The stated scope is a black-box, scalable solution intended for efficient application to varied models.
Source: §1 · p. 2
Abstract
from arXiv · showhide
Dependability on AI models is of utmost importance to ensure full acceptance of the AI systems. One of the key aspects of the dependable AI system is to ensure that all its decisions are fair and not biased towards any individual. In this paper, we address the problem of detecting whether a model has an individual discrimination. Such a discrimination exists when two individuals who differ only in the values of their protected attributes (such as, gender/race) while the values of their non-protected ones are exactly the same, get different decisions. Measuring individual discrimination requires an exhaustive testing, which is infeasible for a non-trivial system. In this paper, we present an automated technique to generate test inputs, which is geared towards finding individual discrimination. Our technique combines the well-known technique called symbolic execution along with the local explainability for generation of effective test cases. Our experimental results clearly demonstrate that our technique produces 3.72 times more successful test cases than the existing state-of-the-art across all our chosen benchmarks.
1 Introduction
The paper targets individual discrimination: different decisions for people who differ only in protected attributes, a behavior that exhaustive testing cannot feasibly check across non-trivial systems. It combines symbolic execution with local explanations to generate test inputs and reports better performance than THEMIS.
1 Introduction
- Exhaustive testing is infeasible, while random-input testing can miss discriminating combinations when samples follow the same execution path.Individual discrimination occurs when people identical on non-protected attributes receive different decisions because of their protected attributes.Source: §1 · p. 1
- The paper aims for a black-box, scalable solution applicable efficiently to varied models, unlike prior symbolic approaches described as network-specific or structure-dependent.It identifies specialized neural-network approximations and structure-based coverage criteria as limits of prior techniques.Source: §1 · p. 2
- The approach uses local explanations as paths for symbolic execution, combining black-box model access with feature constraints for generating tests.The stated design also uses training data as seeds and directs search toward additional discrimination after finding an instance.Source: §1 · pp. 1–2
- The technique outperforms THEMIS in experiments on several open-source classification models containing known biases.The introduction does not quantify the comparison.Source: §1 · p. 2
2 Background
Dynamic symbolic execution collects path constraints and solves modified constraints to steer later runs toward different program paths. Local explainability approximates a model's behavior near an instance with an interpretable model, which the paper uses to build decision trees from instance explanations.
2.1 Dynamic Symbolic Execution
- Dynamic symbolic execution collects input constraints along an execution path, then solves modified constraints to generate inputs that steer execution toward new paths.The example toggles branch conditions and solves the resulting constraints to obtain inputs reaching different branches.Source: §2.1 · p. 2
2.2 Local Explainability
- LIME perturbs an instance's neighborhood and fits an interpretable local model; the paper combines explanations across instances into a decision tree.For German Credit Data, the explanation identifies age as important to credit-risk prediction.Source: §2.2 · pp. 2–3
3 Algorithm
The algorithm adapts symbolic execution from program paths to model decision spaces, using seed inputs, ranked candidate paths, and checks against revisiting paths. For uninterpretable models, it builds approximate paths from local explanations and diversifies training-data seeds through clustering.
3 Algorithm
- The algorithm generalizes symbolic execution from procedural programs to models to generate inputs aimed at finding individual discrimination.It is presented in two stages: a symbolic-execution skeleton and a full test-input generation algorithm for uninterpretable models.Source: §3 · p. 3
3.1 Generalized Symbolic Execution
- Model-level symbolic execution uses seed inputs, ranks candidate inputs for execution, and checks whether a path has already been traversed.Unlike random starts, seeds can be one or more inputs; for each path, the algorithm ranks all conditionals available to toggle.Source: §3.1 · p. 3
3.2 Test Case Generation for Uninterpretable Model
- The algorithm uses a local explainer's decision-tree path as an approximation of a model path, with predicate confidence and potentially omitted predicates shaping the search.Unlike a program path, this path may omit predicates without an effect on the class and is not incrementally preserved by the explainer.Source: §3.2 · p. 4
- To diversify search seeds, the algorithm clusters training instances and selects them round-robin when a search limit prevents using them all.Its ranking scheme uses predicate confidence to choose which test input to execute next; path ranking uses the average confidence of predicates in the path.Source: §3.2 · p. 4
4 Checking Individual Discrimination
The algorithm checks for individual discrimination by testing whether changing protected-attribute values can change a test case’s class while its non-protected values remain fixed. It combines this check with directed and undirected symbolic search and ranks the resulting inputs.
4 Checking Individual Discrimination
- A check finds individual discrimination when protected-attribute values produce a different class for the test case’s fixed non-protected values.The check is performed in the error-condition function.Source: §4 · p. 4
- Directed search negates a low-confidence non-protected constraint to find more inputs that may retain the seed case’s effect on protected attributes.The approach relies on low-confidence constraints being less prone to change the test case’s behavior.Source: §4 · pp. 4–5
- Directed search toggles low-confidence constraints and leaves the other path constraints unchanged, while undirected search toggles high-confidence constraints without a suffix constraint.The paper motivates high-confidence toggling in undirected search as offering more chance of diverse path coverage.Source: §4 · p. 5
- The consolidated algorithm prioritizes directed-search inputs, then seed inputs, and finally undirected-search inputs based on their stated ability to uncover discrimination-causing inputs.The section also identifies error-condition checking, directed search, and relative ranking as changes to the generic algorithms.Source: §4 · pp. 4–5
5 Experimental Evaluation
The evaluation compares the approach with THEMIS and examines how seed selection and symbolic-search features contribute to finding individual discrimination. Overall, the symbolic algorithm reports more successful test cases than THEMIS.
5.1 Setup
- The evaluation used 8 open-source fairness benchmarks, LIME explanations, KMeans clusters of size 4, and default scikit-learn logistic regression models.The implementation used Python 2.7.12 and ran with thresholds T1=0.3 and T2=0.2.Source: §5.1 · p. 5
5.2 Experiments
- Across 12 benchmarks, the symbolic algorithm generated 3.72 times more successful test cases than THEMIS; average success scores were 30.3% versus 6.4%.THEMIS was modified to remove duplicate test cases before the comparison; the reported comparison was better in all but one case.Source: §5.2 · pp. 5–6, Table 2 · p. 6
- Feature results report average success percentages of 37% for Indirect Symbolic execution and 23% for Data, following the stated preference order Indirect, Data, Direct.Table 3 reports contributions from training data, undirected symbolic execution, and directed symbolic execution.Source: Table 3 · p. 6, §5.2 · p. 6
- On credit data with symbolic search, training seeds yielded 421 successful cases, versus 310 for random seeds and 44 for THEMIS.Table 5 reports results for random seed data with symbolic search.Source: Table 5 · p. 6, §5.2 · p. 6
- Across four benchmarks, removing directed search reduced average effectiveness from 43.9% to 25.2%; directed search also uncovers bias instances after an initial fault is found.The experiments report that training data works better than undirected symbolic search for initial fault finding.Source: Table 6 · p. 6, §5.2 · pp. 6–7
- Under a 600-test-case budget, round-robin found 45 discriminations versus 35 for iterative ordering; Figure 4 reports higher counts for round-robin for most test-case counts.Round-robin selects seed inputs across clusters.Source: §5.2 · pp. 6–7, Figure 4 · p. 7
- Without directed search, undirected search found successful cases in German-age and Car, while only 4 and 7 test cases were generated in the other two cases.The authors attribute the low generation counts to low predicate confidence for toggling.Source: Table 7 · p. 7, §5.2 · p. 7
6 Related Work
The section reviews test-generation research and individual-discrimination methods, positioning this work as the first systematic test-generation method for individual discrimination that retains a black-box approach.
6 Related Work
- Earlier AI-model test-generation methods use white-box techniques, including symbolic execution, concolic execution, mutation testing, gradient-based search, and linear programming.DeepCheck targets adversarial images and its semantic-preserving translation works only for a specific network.Source: §6 · p. 7
- The authors contrast their black-box method and off-the-shelf solver with prior white-box test generation aimed at adversarial inputs in image space.They frame individual-discrimination testing as a trust-and-ethics problem.Source: §6 · p. 7
- Existing individual-discrimination approaches include THEMIS's random test generation, FairTest's manually written tests, and FairML's iterative analysis of input-attribute dependence.FairTest uses correlations between attributes to generate tests; FairML uses relative input significance to assess fairness.Source: §6 · p. 7
- The paper positions its method as the first to combine systematic test generation for individual discrimination with a black-box approach.Prior individual-discrimination methods are black box, but none uses systematic test generation.Source: §6 · p. 7
7 Conclusion
The conclusion presents a black-box test-generation algorithm for individual discrimination that combines symbolic execution with local explanations to approximate model paths.
7 Conclusion
- The proposed algorithm checks individual discrimination in AI models by combining systematic symbolic execution with local explanations that approximate model paths using linear models.The authors identify text and images as future application domains and structural coverage metrics as a future way to assess symbolic execution's efficacy.Source: §7 · p. 7