# Astraea: Grammar-based Fairness Testing

arXiv: https://arxiv.org/abs/2010.02542 · HTML: https://mlsanity.com/paper/2010.02542/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2020.

## Built on by (most cited first, 11 of 11)

- [Dynaboard: An Evaluation-As-A-Service Platform for Holistic Next-Generation Benchmarking](https://mlsanity.com/paper/2106.06052/) (2021)
- [A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advances](https://mlsanity.com/paper/2505.17799/) (2025)
- [Investigating Failures of Automatic Translation in the Case of Unambiguous Gender](https://mlsanity.com/paper/2104.07838/) (2021)
- [Towards Fair Machine Learning Software: Understanding and Addressing Model Bias Through Counterfactual Thinking](https://mlsanity.com/paper/2302.08018/) (2023)
- [AequeVox: Automated Fairness Testing of Speech Recognition Systems](https://mlsanity.com/paper/2110.09843/) (2021)
- ["Oops, Did I Just Say That?" Testing and Repairing Unethical Suggestions of Large Language Models with Suggest-Critique-Reflect Process](https://mlsanity.com/paper/2305.02626/) (2023)
- [A Catalog of Fairness-Aware Practices in Machine Learning Engineering](https://mlsanity.com/paper/2408.16683/) (2024)
- [MAFT: Efficient Model-Agnostic Fairness Testing for Deep Neural Networks via Zero-Order Gradient Search](https://mlsanity.com/paper/2412.20086/) (2024)
- [Do Existing Testing Tools Really Uncover Gender Bias in Text-to-Image Models?](https://mlsanity.com/paper/2501.15775/) (2025)
- [FairSense: Long-Term Fairness Analysis of ML-Enabled Systems](https://mlsanity.com/paper/2501.01665/) (2025)
- [Distribution-aware Fairness Test Generation](https://mlsanity.com/paper/2305.13935/) (2023)

## Abstract (arXiv)

Software often produces biased outputs. In particular, machine learning (ML) based software are known to produce erroneous predictions when processing discriminatory inputs. Such unfair program behavior can be caused by societal bias. In the last few years, Amazon, Microsoft and Google have provided software services that produce unfair outputs, mostly due to societal bias (e.g. gender or race). In such events, developers are saddled with the task of conducting fairness testing. Fairness testing is challenging; developers are tasked with generating discriminatory inputs that reveal and explain biases. We propose a grammar-based fairness testing approach (called ASTRAEA) which leverages context-free grammars to generate discriminatory inputs that reveal fairness violations in software systems. Using probabilistic grammars, ASTRAEA also provides fault diagnosis by isolating the cause of observed software bias. ASTRAEA's diagnoses facilitate the improvement of ML fairness. ASTRAEA was evaluated on 18 software systems that provide three major natural language processing (NLP) services. In our evaluation, ASTRAEA generated fairness violations with a rate of ~18%. ASTRAEA generated over 573K discriminatory test cases and found over 102K fairness violations. Furthermore, ASTRAEA improves software fairness by ~76%, via model-retraining.