Information-Theoretic Testing and Debugging of Fairness Defects in Deep
  Neural Networks
The deep feedforward neural networks (DNNs) are increasingly deployed in
socioeconomic critical decision support software systems. DNNs are
exceptionally good at finding minimal, sufficient statistical patterns within
their training data. Consequently, DNNs may learn to encode decisions --
amplifying existing biases or introducing new ones -- that may disadvantage
protected individuals/groups and may stand to violate legal protections. While
the existing search based software testing approaches have been effective in
discovering fairness defects, they do not supplement these defects with
debugging aids -- such as severity and causal explanations -- crucial to help
developers triage and decide on the next course of action. Can we measure the
severity of fairness defects in DNNs? Are these defects symptomatic of improper
training or they merely reflect biases present in the training data? To answer
such questions, we present DICE: an information-theoretic testing and debugging
framework to discover and localize fairness defects in DNNs.
  The key goal of DICE is to assist software developers in triaging fairness
defects by ordering them by their severity. Towards this goal, we quantify
fairness in terms of protected information (in bits) used in decision making. A
quantitative view of fairness defects not only helps in ordering these defects,
our empirical evaluation shows that it improves the search efficiency due to
resulting smoothness of the search space. Guided by the quantitative fairness,
we present a causal debugging framework to localize inadequately trained layers
and neurons responsible for fairness defects. Our experiments over ten DNNs,
developed for socially critical tasks, show that DICE efficiently characterizes
the amounts of discrimination, effectively generates discriminatory instances,
and localizes layers/neurons with significant biases.
Verya Monjezi, Ashutosh Trivedi, Gang Tan, Saeid Tizpaz-Niari
# Information-Theoretic Testing and Debugging of Fairness Defects in Deep Neural Networks

###### Abstract

The deep feedforward neural networks (DNNs) are increasingly deployed in socioeconomic critical decision support software systems. DNNs are exceptionally good at finding minimal, sufficient statistical patterns within their training data. Consequently, DNNs may learn to encode decisions--amplifying existing biases or introducing new ones--that may disadvantage protected individuals/groups and may stand to violate legal protections. While the existing search based software testing approaches have been effective in discovering fairness defects, they do not supplement these defects with debugging aids--such as severity and causal explanations--crucial to help developers triage and decide on the next course of action. Can we measure the severity of fairness defects in DNNs? Are these defects symptomatic of improper training or they merely reflect biases present in the training data? To answer such questions, we present Dice: an information-theoretic testing and debugging framework to discover and localize fairness defects in DNNs.

The key goal of Dice is to assist software developers in triaging fairness defects by ordering them by their severity. Towards this goal, we quantify fairness in terms of protected information (in bits) used in decision making. A quantitative view of fairness defects not only helps in ordering these defects, our empirical evaluation shows that it improves the search efficiency due to resulting smoothness of the search space. Guided by the quantitative fairness, we present a causal debugging framework to localize inadequately trained layers and neurons responsible for fairness defects. Our experiments over ten DNNs, developed for socially critical tasks, show that Dice efficiently characterizes the amounts of discrimination, effectively generates discriminatory instances (vis-a-vis the state-of-the-art techniques), and localizes layers/neurons with significant biases.

## I Introduction

AI-assisted software solutions--increasingly implemented as deep neural networks [1] (DNNs)--have made substantial inroads into critical software infrastructure where they routinely assist in socio-economic and legal-critical decision making [2]. Instances of such AI-assisted software include software deciding on recidivism, software predicting benefit eligibility, and software deciding whether to audit a given taxpayer. The DNN-based software development, driven by the _principle of information bottleneck_[3], involves a delicate balancing act between over-fitting and detecting useful, parsimonious patterns. It is, therefore, not a surprise that such solutions often encode and amplify pre-existing biases in the training data. What's worse, improper training may even introduce biases not present in the training data or irrelevant to the decision making. The resulting fairness defects may not only disadvantage protected groups [4, 5, 6, 7, 8], but may stand to violate statutory requirements [9].

_This paper presents Dice, an information-theoretic testing and debugging framework for fairness defects in deep neural networks._

**Quantifying Fairness.** Concentrated efforts from the software engineering and the machine learning communities have produced a number of successful _fairness testing_ frameworks [10, 11, 12, 13]. These frameworks characterize various notions of fairness--such as group fairness [14] (decision outcome for various protected groups must be similar) and individual fairness [15] (individuals differing only on protected attributes must receive similar outcome)--and employ search-based testing to discover fairness defects. While a binary classification of fairness is helpful in discovering defects, developers may require further insights into the nature of these defects to decide on the potential "bug fix". Are some defects more severe than others? Whether these defects stem from biases present in the training data, or they are artifacts of an inadequate training? Is it possible to find an alternative explanation of the training data that does not use protected information?

_Individual discrimination_ is a well-studied [16, 11, 17, 18] causal notion of fairness that defines a function being discriminant towards an individual (input) if there exists another individual (potentially counterfactual), differing only in the protected features, receives a more favorable outcome. We present a quantitative generalization of this notion as the _quantitative individual discrimination_ (QID). We define QID as the amount of protected information--characterized by entropy metrics such as Shannon entropy and min entropy--used in deriving an outcome. Observe that a zero value for the QID measure implies the absence of the individual discrimination. The QID measure allows us to order various discriminating inputs in terms of their severity, as in an application that is not supposed to base its decisions on protected information, inputs
with higher dependence indicate a more severe violation. Our first _research question_ (**RQ1**) concerns the usefulness of QID measure in finding inputs with different severity.

**Search-Based Testing.** Search-based software testing provide scalable optimization algorithms to automate discovery of software bugs. In the context of fairness defects, the search of such bugs involves finding twin inputs exhibiting discriminatory instances. The state-of-the-art algorithms for fairness testing [19, 17, 18] explore the input space governed by a binarized feedback, resulting in a discontinuous search domain. On the other hand, QID-based search algorithms can benefit a smooth (quantitative) feedback during the optimization, resulting in a more guided search. Our next research question (**RQ2**) is to investigate whether this theoretical promise materializes in practice in terms of discovering richer discriminating instances than using classic notions of discrimination.

**Causal Explanations.** While the discriminating instances (ordered by their severity) provide a clear evidence of fairness defects in the DNN, it is unclear whether these defects are inherent in the training data, or whether they are artifacts of the training process. Inspired by the notion of "the average causal effects" [20] and Audee framework [21] for bug localization in deep learning models, we develop a layer and neuron localization framework for fairness defects. If the cause of the defects is found to be at the input layer, it is indicative of discrimination existing in the training data. On the other hand, if we localize the cause of the defect to some internal layer, we wish to further prod the DNN to extract quantitative information about neurons and their counterfactual parameters that can mitigate the defect while maintaining the accuracy. This debugging activity informed our next research question (**RQ3**): is it possible to identify a subset of neurons and their causal effects on QID to guide a mitigation without affecting accuracy?

**Experiments.** Dice implements a search algorithm (Algorithm 1) to discover inputs that maximize QID and a causal debugging algorithm (Algorithm 2) to localize layers and neurons that causally affect the amounts of QID. Using \(10\) socio-critical DNNs from the literature of algorithmic fairness, we show that Dice finds inputs that can use significant amounts of protected information in the decision making; outperforms three state-of-the-art techniques [19, 17, 18] in generating discriminatory instances; and localizes neurons that guides a simple mitigation strategy to reduce QID down to \(15\%\) of reported initial QID with at most \(5\%\) loss of accuracy. The key contributions of this paper are:

1. **Quantitative Individual Discrimination.** We introduce an information-theoretic characterization of discrimination, dubbed quantitative individual discrimination (QID), based on Shannon entropy and Min entropy.
2. **Search-based Testing.** We present a search-based algorithm to discover circumstances under which the DNNs exhibit severe discrimination.
3. **Causal Debugging.** We develop a causal fairness debugging based on the language of interventions to localize the root cause of the fairness defects.
4. **Experimental Evaluation.** Extensive experiments over different datasets and DNN models that show feasibility, usefulness, and scalability (viz-a-viz state-of-the-art). Our framework can handle multiple protected attributes and can easily be adapted for regression tasks.

## II Preliminaries

**Fairness Terminology.** We consider decision support systems as _binary classifiers_ where a prediction label is _favorable_ if it gives a desirable outcome to an input (individual). These favorable predictions may include higher income estimations for loan, low risk of re-offending in parole assessments, and high risk of failing a class. Each dataset consists of a number of _attributes_ (such as income, experiences, prior arrests, sex, and race) and a set of _instances_ that describe the value of attributes for each individual. According to ethical and legal requirements, data-driven software should not _discriminate_ on the basis of an individual's _protected attributes_ such as sex, race, age, disability, colour, creed, national origin, religion, genetic information, marital status, and sexual orientation.

There are several well-established fairness definitions. _Group fairness_ requires that the statistics of ML outcomes for different _protected groups_ to be similar [14] using metrics such as _equal opportunity difference_ (EOD), which is the difference between the true positive rates (TPR) of two protected groups. Fairness through unawareness (FTU) [15] requires removing protected attributes during training. However, FTU may provide inadequate support since protected attributes can influence the prediction via a non-protected collider attribute (e.g., race and ZIP code). Fairness through awareness (FTA) [15] is an _individual fairness_ notion that requires that two _individuals_ that deemed similar (based on their non-protected attributes) are treated similarly. _Our approach is geared toward individual fairness_.

**Individual Discrimination.** Causal discrimination, first studied in Themis[10], measures the difference between two subgroups via _counterfactual_ queries. It samples individuals with the protected attributes set to \(A\) and compares the outcome to a counterfactual scenario where the protected attributes is set to \(B\). Individual discrimination (ID) is a prevalent notion that adapts counterfactual queries to find an individual such that their counterfactual with a different protected attributes receives more favorable outcome. This fairness notion is used by the state-of-the-art fairness testing to generate fairness defects [22, 19, 17, 18] and closely related to situation testing notion [23]. While standard group fairness metrics (e.g., AOD/EOD) are already quantitative, the quantitative measures do not exist for individual fairness. We propose to adapt information theoretic tools to provide quantitative measures for individual fairness.

**Information-Theoretic Concepts.** The notion of Renyi entropy [24], \(H_{\alpha}(X)\) quantifies the uncertainty (randomness) of a system responding to inputs \(X\). In particular, Shannon
entropy (\(\alpha{=}1\)) and min-entropy (\(\alpha{=}\infty\)) are two important subclasses of Renyi entropy. Shannon entropy (\(H_{1}\)) measures the expected amounts of uncertainty over finitely many events whereas min entropy (\(H_{\infty}\)) measures the uncertainty over single maximum likelihood event.

Consider a deterministic system (like pre-trained DNN) with a finite set of responses and assume that the input \(X\) is distributed uniformly. Thus, the system induces an equivalence relation over the input set \(X\) such that two inputs are equivalent if their system outputs are approximately close, i.e. \(x{\sim}x^{\prime}\) iff \(\mathit{DNN}(x)\approx_{\epsilon}\mathit{DNN}(x^{\prime})\). Let \(X_{o}\) denote the equivalence class of \(X\) with output \(o\). Then, the remaining uncertainty after observing the output of DNN over \(X\) can be written as:

\[H_{1}(X|O)=\sum_{O=o}\frac{|X_{o}|}{|X|}.\log_{2}(|X_{o}|)\qquad\quad\text{( Shannon entropy)}\]

where \(|X|\) is the cardinality of \(X\) and \(|X_{o}|\) is the size of equivalence class of output \(o\). Similarly, the min-entropy is given as

\[H_{\infty}(X|O)=\log_{2}(\frac{|X|}{|O|})\qquad\qquad\qquad\qquad\qquad\text{ (min-entropy)}\]

where \(|O|\) is the number of equivalence classes over \(X\)[25, 26, 27]. Given that the initial entropy is equal to \(\log_{2}(|X|)\) for both entropies, the amount of information from \(X\) used by the system to make decisions are

\[I_{1}(X;O) = \log_{2}(|X|)-H_{1}(X|O),\text{ and}\] \[I_{\infty}(X;O) = \log_{2}(|O|),\]

under Shannon- and min- entropies with \(I_{1}\leq I_{\infty}\).

**Quantitative Notion and Fairness.** Our approach differs from these state-of-the-art techniques [28, 22, 19, 17, 29, 18] in that it extends the individual discrimination notion with quantitative information flow that enables us to measure the amount of discrimination in the ML-based software systems. Given non-protected attributes and ML outcomes, the _Shannon entropy_ measures the expected amount of individual discrimination over all possible responses varying protected classes, whereas, _min entropy_ measures the amount over a single response from the maximum likelihood class.

**Example 1**.: _Consider a dataset with \(16\) different protected values--sex(2), race(2), and age(4)--distributed uniformly, and suppose that we have \(4\) individuals in the system. We perturb the protected attributes of these individuals to generate \(16\) counterfactuals and run them through the DNN to get their prediction scores. Suppose that the outputs have all \(16\) outputs in the same class for the first individual (absolutely fair) and have \(16\) classes of size one for the second individual (absolutely discriminatory). For the third individual, let the outputs be in \(4\) classes with \(\{4,4,4,4\}\) elements in each class (e.g., there is one output class per each age group). For the fourth individual, let us consider outputs to be in \(5\) classes with \(\{8,4,2,1,1\}\) elements in each class (e.g., if race=1 then the output is class \(1\); else, if sex=1 then the output is \(2\); else if age={1,2} then the output is \(3\); else there is one output class for each age={3,4})._

We work with the following notions of discrimination.

* _Individual Discrimination Notion_. The individual discrimination used by the state-of-the-art techniques can only distinguish between the first individual and the rest, but they cannot distinguish among individuals two to four. In fact, these techniques generate tens of thousands of individual discriminatory instances in a short amount of time [19, 17, 18]. However, they fail to prioritize test cases for mitigation and cannot characterize the amounts of discrimination (i.e., their severity).
* _Shannon Entropy_. Using the Shannon entropy, we have the initial fairness to be \(4.0\) bits, a maximum possible discrimination. The remaining fairness of DNN are \(4.0\), \(0.0\), \(2.0\) and \(2.125\), for the first to fourth individuals, respectively. The discrimination is the difference between the initial and remaining fairness, which are \(0.0\), \(4.0\), \(2.0\) and \(1.875\) for the first to fourth individuals, respectively. It is important to note that beyond the two extreme cases, Shannon entropy deems perturbations to the third individual (rather than the fourth) create a higher amount of discrimination.
* _Min Entropy_. The initial fairness via min entropy is also \(4\) bits. The conditional min entropy is \(\log\frac{16}{1}=4.0\), \(\log\frac{16}{16}=0.0\), \(\log\frac{16}{4}=2.0\), and \(\log\frac{16}{5}=1.7\), for the four individuals, respectively. The amounts of discrimination thus are \(0.0\), \(4.0\), \(\log 4=2.0\) and \(\log 5=2.3\), respectively. Beyond the two extreme cases where both entropies agree, the min entropy deems perturbations to the fourth individual create a higher amount of discrimination. This is intuitive since the discrimination on the fourth case is more subtle, complex, and significant. Therefore, the ML software developers might prioritize those cases characterized by the min entropy.

## III Overview

**Dice in Nutshell.** Figure 1 shows an overview of our framework Dice. It consists of two components: (1) an automatic test-generation mechanism based on search algorithms and (2) a debugging approach that localizes the neurons with significant impacts on fairness using a causal algorithm. First, Dice searches through the space of input dataset to find circumstances on the non-protected attributes under which the DNN-under-test shows a significant dependency on the protected attributes in making decisions. In doing so, it works in global and local phases. In the global phase, the search explores the input space to increase the amount of discrimination in each step of search. On the other hand, in the local phase it exploits the promising seeds from the global phase to generate as many discriminatory instances as possible.

The key elements of search is a threshold-based clustering algorithm used for computing both gradients and objective functions that provide a smooth feedback. The search characterizes the quantitative individual discrimination (QID) and
returns a set of interesting inputs. Second, Dice uses those inputs to localize neurons with the largest causal effects on the amounts of discrimination. In doing so, it intervenes [30] over a set of suspicious neurons. For every neuron, our debugging approach forces the neurons to be active (\(n{>}0\)) and non-active (\(n{=}0\)) over the test cases as far as the functional accuracy of DNN remains in a valid range. Then, it computes the difference between the amounts of QID in these two cases to characterize the causal effects of the neuron on fairness.

Dice reports top \(k\) neurons that both have positive impacts (i.e., their activation reduces the amounts of discrimination) and negative impacts (i.e, their activation increases the amounts of discrimination). A potential mitigation strategy is to intervene to keep a small set of neurons activated (for the positive neurons) or deactivated (for the negative neurons).

**Test Cases.** Consider the _adult census income_[31] dataset with a pre-trained model with \(6\) layers [17] to overview Dice in practice. We ran Dice for \(1\) hours and obtain \(230,593\) test cases. It discovered \(36\) clusters from the initial of \(14\) clusters, and the amounts of QID are \(4.05\) and \(2.64\) bits for min entropy and Shannon entropy, respectively, out of a total of \(5.3\) bits of information from the protected attributes. Considering to order the test cases, we have \(6\) test case with maximum QID discrimination of \(5.3\) bits. In addition, we have \(29\) and \(112\) test cases cases with \(5.2\) and \(5.1\) bits of QID discrimination. The reported numbers are averaged (and rounded) for \(10\) runs.

**Localization and Mitigation.** Dice uses the generated test cases to localize layers and neurons with a significant causal contribution to the discrimination. For the census dataset, it identifies the second layer as the layer with largest sensitivity to protected attributes. Among the neurons in this layer, Dice found that \(15\)th neuron has the largest negative influence on fairness (the discrimination decreased by \(19.6\%\) when it is deactivated) and \(19\)the neuron has the largest positive influence on fairness (the discrimination decreased by \(17.6\%\) when it is activated). Following this localization, a simple mitigation strategy of activating or deactivating these neuron reduces the amounts of QID discrimination by \(20\%\) with \(3\%\) accuracy loss.

**Comparison to the State-of-the-art.** We compare Dice to the state-of-the-art techniques in terms of generating individual discrimination (ID) (rather than the quantitative notion) per each protected attribute. Our goal is to evaluate whether the clustering-based search is effective in generating discriminatory instances. We run Dice and baseline for \(15\) minutes, and report average of results over \(10\) runs. The baseline includes Aequitas[19], ADF [17], and NeuronFair[18]. Considering sex as the protected attribute in the census dataset, Dice generated \(79.0k\) instances whereas Aequitas, ADF, and NeuronFair generated \(10.4k\), \(18.2k\), and \(21.6k\) discriminatory instances, respectively. Overall, Dice generate more ID instances in all cases with more success rates. However, Dice is slower in finding the first ID instance in order of a few seconds (in average), since our approach does not generate ID instances in global phase. When considering the time to the first 1,000 instances, Dice has significantly outperformed the state-of-the-art. We conjecture that the improvements are due to smooth search space via quantitative feedback.

## IV Problem Statement

We consider DNN-based classifiers with the set of input variables \(A\) partitioned into protected set of variables \(Z\) (such as race, sex, and age) and non-protected variables \(X\) (such as profession, income, and education). We further assume the output to consist of \(t\) prediction classes.

**Definition IV.1** (DNN: Semantics).: _A deep neural network (DNN) encodes a function \(\mathcal{D}:X\times Z\rightarrow[0,1]^{t}\) where \(X=X_{1}\times X_{2}\cdots\times X_{n}\) is the set of non-protected input variables, \(Z=Z_{1}\times Z_{2}\cdots\times Z_{r}\) is the set of protected input variables, and the output is \(t\)-dimensional probabilistic vector corresponding to \(t\) prediction classes. The predicted label \(\mathcal{D}_{\ell}(x,z)\) of an input pair \((x,z)\) is the index of the maximum score, i.e. \(\mathcal{D}_{\ell}(x,z)=\max_{i}\mathcal{D}_{\ell}(x,z)(i)\). We assume that the set of protect input variables are finite domain, and we let \(m\) be the cardinality of the set of protected variables \(Z\)._

**Definition IV.2** (DNN: Syntax).: _A DNN \(\mathcal{D}\) is parameterized by the input dimension \(n{+}r\), the output dimension \(t\), the depth of hidden layers \(N\), and the weights of its hidden layers \(W_{1},W_{2},\ldots,W_{N}\). Our goal is to test and debug a pre-trained neural network with known parameters and weights. Let

Fig. 1: Workflow of Dice. Given a DNN and relevant input dataset, Dice quantifies QID discrimination via testing and applies causal debugging to localize and mitigate QID discrimination.
_be the output of layer \(i\) that implements an affine mapping from the output of previous layer \(D_{i-1}\) and its weights \(W_{i-1}\) for \(1\leq i\leq N\) followed by_

1. _a fixed non-linear activation unit (e.g., ReLU defined as_ \(D_{i-1}\mapsto\max\left\{W_{i-1}.D_{i-1},0\right\}\)_) for_ \(1\leq i<N\)_, or_
2. _a SoftMax function that maps scores to probabilities of each class for_ \(i=N\)_._

_Let \(D_{i}^{j}\) be the output of neuron \(j\) at layer \(i\)._

**Individual Discrimination.** We say a DNN \(\mathcal{D}\) is biased based on causal discrimination notion [16, 11, 17, 18] if

\[\exists z_{1},z_{2}\in Z,x\in X\ s.t.\ \mathcal{D}_{\ell}(x,z_{1})\neq \mathcal{D}_{\ell}(x,z_{2}),\]

for \(z_{1}\neq z_{2}\) of protected inputs. Intuitively, the idea is to find an individual such that their counterfactual with different protected attributes such as race receives a different outcome.

**Quantitative Individual Discrimination.** In the setting of fairness testing, it is often desirable to quantify the _amounts_ of bias for individuals. We define the notion quantitative individual discrimination (QID) based on the equivalence classes induced from the output of DNN over protected attributes. Formally, \(\mathit{QID}(Z,X=x)=\langle Z_{1},\ldots,Z_{k}\rangle\) that is the quotient space of \(Z\) characterized by the DNN outputs under an individual with non-protected value \(x\). Using this notion, we say a pair of protected values \(z,z^{\prime}\) are in the same equivalence class \(i\) (i.e., \(z,z^{\prime}\in\mathcal{Z}_{i}\)) if and only if \(\mathcal{D}(z,x)\approx\mathcal{D}(z^{\prime},x)\).

Given that \(Z\) is uniformly distributed and \(\mathcal{D}\) is a deterministic function, we can quantify the QID notion for an individual \((z,x)\) according to the Shannon and min entropy, respectively:

\[Q_{1}(Z,x)\!\!=\!\log_{2}(m)\!\!-\!\sum_{i=1}^{k}\frac{|\mathit{QID}_{i}(Z,x)| }{m}.\log_{2}(|\mathit{QID}_{i}(Z,x)|)\]

\[Q_{\infty}(Z,x)=\log_{2}(m)-\log_{2}(\frac{m}{k})=\log_{2}(k).\]

where \(m\) is the cardinality of \(Z\), \(|\mathit{QID}_{i}(Z,x)|\) is the size of equivalence class \(i\), and \(k\) is the number of equivalence classes.

**Debugging/Mitigating DNN for QID.** After characterizing the amounts of discrimination via \(\mathit{QID}\), our next step is to localize a set of layers and neurons that _causally_ effect the output of DNN to have \(k\) equivalence classes.

Causal logic [30] provides a firm foundation to reason about the causal relationships between variables. We consider a structural causal model (SCM) with exogenous variables \(U\) over the unobserved input factors, endogenous variables \(V\) over \((X,Z,D_{i}^{j})\); and the set of functions \(\mathcal{F}\) over the set \(V\) using the DNN function \(\mathcal{D}\) and exogenous variables \(U\). Using the SCM, we aim to estimate the average causal effect (ACE) [30] of neuron \(D_{i}^{j}\) on the QID.

A primary tool for performing such computation is called do logic [20]. We write do\((i,j,y)\) to indicate that the output of neuron \(j\) at layer \(i\) is intervened to stay \(y\). In doing so, we remove the incoming edges to the neuron and force the output of neuron to take a pre-defined value \(y\), but we are not required to control back-door variables due to the feed-forward structure of DNN. Then, the ACE of neuron \(D_{i}^{j}\) on the quantitative individual discrimination with min entropy can be written as \(E[Q_{\infty}|\mathrm{\triangle}\mathrm{\triangle}(i,j,y)\!,\!k,l]\), which is the expected QID after intervening on the neuron given that the non-intervened DNN characterized \(k\) classes with an accuracy of \(l\). Our goal is to find neurons with the largest causal effects on the QIDs, requiring that such interventions are faithful to the functionality of DNN.

**Definition IV.3** (Quantitative Fairness Testing and Debugging).: _Given a deep neural network model \(\mathcal{D}\) trained over a dataset \(A\) with protected (\(Z\subset A\)) and non-protected (\(X\subset A\)) attributes; the search problem is to find a single non-protected value \(x\in X\) such that the quantitative individual discrimination (QID), for a chosen measure \(Q_{1}\) or \(Q_{\infty}\), is maximized over the \(m\) protected values \(\Sigma=\{z_{1},\ldots,z_{m}\}\). Given the inputs \((\Sigma,x)\) characterizing the maximum QID, our debugging problem is to find a minimal subset of layers \(l\subset\{1,\ldots,N\}\) and neurons \(D_{l}^{(J)}\) for \(J\subseteq|W_{l}|\) such that the average causal effects of \(D_{l}^{j}\) on the QID are maximum._

## V Approach

**Characterizing Quantitative Individual Discrimination.** Given a DNN \(\mathcal{D}\) over a dataset \(A\), our goal is to characterize the worst-case QID over all possible individuals. Since min entropy characterizes the amounts of discrimination from one prediction with \(Q_{\infty}(Z,x)\geq Q_{1}(Z,x)\), it is a useful notion to prioritize the test cases. Therefore, we focus on \(Q_{\infty}\) and propose the following objective function:

\[\max_{x\in X}\ 2^{Q_{\infty}(Z,x)}+(1-exp(-0.1*\delta))\]

where \(2^{Q_{\infty}(Z,x)}=k\) and \(\delta\) is the maximum distance between equivalence classes, normalized with the exponential function to remain between \(0\) and \(1\). The term is used to break ties when two instances characterize the same number of classes, by preferring one with the highest distance. Overall, the goal is to find a single value of non-protected attribute \(x\) such that the neural network model \(\mathcal{D}\) predicts many distinguishable classes of outcomes when \(x\) is paired with \(m\) protected values. However, finding those inputs requires an exhaustive search in the exponential set of subsets of input space, and hence is clearly intractable. We propose a gradient-guided search algorithm that aims to search the space of input variables (attributes) to maximize the number of equivalence classes and generate as many discrimination instances as possible.

**Search Approach.** Our search strategy consists of global and local phases as in some of the prior work [17, 29, 18]. The goal of the global phase is to find the maximum quantitative individual discrimination via gradient-guided clustering. The local phase uses the promising instances to generate a maximum number of discriminatory instances (ID).

_Global Phase._ Given a current instance \(x\), the global stage first uses \(m\) different values from the space of protected attributes, while keeping the values of non-protected attributes the same. Then, it receives \(m\) prediction scores from the DNN and
partitions them into \(k\) classes. We adapt a constrained-based clustering with \(\epsilon\) where two elements cannot be in the same cluster if their scores differ more than \(\epsilon\). Now, the critical step is to perturb the current instance over a subset of non-protected attributes with a direction that will likely increase the number of clusters induced from the perturbed instance in the next step of global search.

In doing so, we first compute the gradients of DNN loss function for a pair of instances (say \(a,a^{\prime}\)) in the cluster with the maximum elements. The intuition is that we are more likely to split the largest cluster into \(2\) or more sub-clusters and increase the number of partitions in the next step. For the pair of samples, we use the non-protected attributes that have the same direction of gradients \(d\) since it shows the high sensitivity of loss function with respect to small changes on those common features of the pair. If we were to use gradients of opposite directions, we will neutralize the effects of gradients since we only perturb one instance over the non-protected attributes. Finally, we perturb the current sample \(x\) to generate \(x^{\prime}\) using the direction \(d\) and step size \(s_{g}\).

_Local Phase._ Once we detect an instance with more than \(2\) clusters, we enter a local phase where the goal is to generate as many discriminatory instances (ID) as possible. In our quantitative approach, we say that an unfavorable decision for an individual \(x\) is discriminatory if there is a counterfactual individual \(x^{\prime}\) that received a favorable outcome. Similar to the state-of-the-art [19, 17, 18], we use non-linear optimizer that takes an initial instance \(x\), a step function to generate the next instance around the neighborhood of the current instance, and an objective function that quantifies the discrimination of the current instance. Since our approach uses a continuous objective based on the characteristics of clusters, it enables us to guide the local search to generate discriminatory instances.

**Search Procedure.** Algorithm 1 sketches our search algorithm to quantify the amounts of bias. We first use the clustering (KMeans algorithm) to partition the data points into \(p\) groups (line 1). Next, we run the algorithm until the time-out \(T\) reaches where in each iteration we seed a sample randomly from one of the partitions \(p\) (line 2). Then, we proceed into global and local phases of search.

```
Input: Dataset \(A\), deep learning model \(\mathcal{D}\), the loss function for the DNN \(J\), protected attributes \(P\), non-protected attributes \(NP\), the number of partitions over the dataset \(p\), the step size in global perturbation \(s_{g}\), the step size in local perturbation \(s_{l}\), the maximum number of global iterations \(N_{g}\), the maximum number of local iterations \(N_{l}\), the tolerance \(\epsilon\), and time-out \(T\). Output: Num. Clusters and (local+Global) Test Cases.
1\(A^{\prime}\), \(cur\leftarrow\)KMeans(\(A\), \(p\)), time()
2whiletime() - \(cur<T\)do
3\(x\), \(i\), \(k\), \(\delta\leftarrow\) pick(\(A^{\prime}\)), 0, 1, 0.0
4while\(i<N_{g}\)do
5\(I_{m},S_{m}\leftarrow\) Generate_Predict(\(a\), \(P\))
6\(X_{k}\), \(\delta^{\prime}\leftarrow\) Clust(\(S_{m}\), \(\epsilon\))
7\(a,a^{\prime}\leftarrow\) Choose_Pair_Max(\(X_{k}\))
8\(Gs\leftarrow(\nabla J(a),\nabla J(a^{\prime}))\)
9\(d\leftarrow\) choose_common_direct(\(Gs\), \(NP\))
10\(x^{\prime}\leftarrow\) perturb(\(x\), \(d,s_{g}\))
11if(\(|X_{k}|>k\)) or (\(|X_{k}|=k\) and \(\delta^{\prime}>\delta\))then
12eval\(\leftarrow\)(\(x\)) {
13\(I^{\prime}_{m},S^{\prime}_{m}\leftarrow\) Generate_Predict(\(x\), \(P\))
14\(X_{k^{\prime}}\leftarrow\) clust(\(S^{\prime}_{m}\), \(\epsilon\))
15\(\Delta\leftarrow\)\(arg.\)max(\(X_{k^{\prime}}\))\(-arg.\) min(\(X_{k^{\prime}}\))
16\(local\_inps.\)add(\(x\))
17Return\(-\Delta\)
18step_f\(\leftarrow\)\(\lambda_{x}\) perturb_local(\(x,s_{l}\))
19LBFGS(\(x\), eval_f, step_f, \(N_{l}\))
20\(global\_inps.\)add(\(a\))
21\(k\), \(x\leftarrow\) max(\(k,|X_{k}|\), \(x^{\prime}\))
22
23return\(k\), \(I=global\_inps\cup local\_inps\)
```

**Algorithm 1**Dice (Search)

In the local phase, we use the general-purpose optimizer, known as LBFGS [32], which takes an initial seed \(x\), an objective function, a step function, and the maximum number of local iterations \(N_{l}\); it returns the generated instances during the optimization (Line 12-19). In the objective function shown with eval_f (Line 12-17), we generate \(m\) instances with the same non-protected values but different protected ones (Line 13). We generate prediction scores for those instances and cluster them with tolerance parameter \(\epsilon\) (line 14). Then, we compute the difference between the indices of two clusters with the smallest and largest scores (line 15). Finally, we record the generated sample and return the difference as the evaluation of optimizer at the current sample (line 16-17). The step function is shown with perturb_local (Line 18) where it guides the optimizer to take one step in the input space. Our step function uses a random sample from a different cluster compared to the current sample. Then, it computes the normalized sum of gradients and perturbs it using the smallest gradients to remain in the neighborhood of the current sample.

**Debugging Approach.** Since it is computationally difficult to intervene over all possible neurons in a DNN, we first
adapt a layer-localization technique from the literature of DL framework debugging [33, 21] where we detect a layer with the largest sensitivity to the protected attributes. Let \(D_{i}(z,x)\) be the output of layer \(i\) over protected value \(z\) and non-protected value \(x\). Let \(\Delta_{i}(x):\mathbb{R}^{|D_{i}|}\times\mathbb{R}^{|D_{i}|}\rightarrow\mathbb{R}\) be the distance between the outputs of DNN at layer \(i\) as triggered by \(m\) different protected values and the same non-protected value \(x\), and let \(\delta_{i}\) be the \(\max_{x}\Delta_{i}(x)\). The rate of changes in the sensitivity of layer \(i\) (w.r.t protected attributes) is

\[\rho_{i}=\frac{\delta_{i}-\max_{j}\delta_{j}}{\max_{j}\delta_{j}+ \epsilon},\ with\ 0\leq\ j<\ i\]

where \(\delta_{0}=0.0\) and \(\epsilon=10^{-7}\) (to avoid division-by-zero [33, 21]). Let \(l=\arg\max_{i}\rho_{i}\) be the layer index with the maximum rate of changes. Our next step is to localize neurons in the layer \(l\) that have significant positive or negative effects on fairness. Let \(V_{l}^{j}\) be the set of possible values for neuron \(j\) at later \(l\) (recorded during the layer localization). We are interested in computing the average causal effects when the neuron \(D_{l}^{j}\) is activated vs. deactivated, noting that such interventions might affect the functionality of DNN. Therefore, among a set of intervention values, we choose one activated value \(v_{1}\in V_{l}^{j}>0\) and one deactivated value \(v_{2}\in V_{l}^{j}\approx 0\), considering the functional accuracy of DNN within \(\epsilon\) of original accuracy \(A\). Therefore, we define average causal difference (ACD) for a neuron \(D_{l}^{j}\) as:

\[\mathbb{E}[Q_{\infty}\mid\texttt{do}(l,j,v_{1}>0),k,A]-\mathbb{E}[Q_{\infty} \mid\texttt{do}(l,j,v_{2}\approx 0),k,A],\]

where do notation is used to force the output of neuron \(j\) at layer \(l\) to a fix value \(v\). We then return the neuron indices with the largest positive (aggravating discrimination) and smallest negative (mitigating discrimination). Let \(\hat{i}\) and \(\hat{j}\) be the layer and neuron with the largest positive \(ACD\). One simple mitigation strategy is thus to deactivate the neuron \(D_{l}^{j}\), expecting to reduce QID by \(ACD/k\) percentage. Similarly, activating the neuron with the smallest negative \(ACD\) is expected to reduce QID by \(ACD/k\) percentage.

**Debugging Procedure.** Algorithm 2 shows the debugging aspect of Dice. Given a set of test cases from the search algorithm, we first use a notion of distance (e.g, \(\Delta=L_{1}\)) to compute the difference between any pair of protected values \(z,z^{\prime}\) w.r.t the outputs of layer \(l\in\{1,\ldots,N\}\) (line 1). Then, we compute the rate of changes (line 2-3) and return a layer \(l\) with the largest change (line 4). We compute various statistics on the output of every neuron \(i\) at layer \(l\) such as the minimum, maximum, average, average\(\pm\)std. dev, average\(\pm\)2*std. dev, etc (line 5). Among those values, we take the smallest and largest values such that the intervention on the neuron \(i\) at layer \(l\) has the minimal impacts on the accuracy of DNN (line 6). Finally, we compute the average causal difference (line 7) and return the indices of layer, neurons with large negative influence, and neurons with large positive influence.

```
Input: Dataset \(A=(A_{X},A_{Z})\), \(\mathcal{D}\) with accuracy \(\mathcal{A}_{\mathcal{D}}\), Test cases \(I\), the distance function \(\Delta\), the tolerance of layer localization \(\epsilon_{1}\), the tolerance of accuracy loss \(\epsilon_{2}\), and \(k\) top items. Output: Layer Index, Negative, and Positive Neurons. /* Layer Localization */
1\(\delta\leftarrow\lambda_{l}\ \max\sum_{x\in I}\Delta\big{(}D_{l}(z,x),D_{l}(z^{ \prime},x)\big{)}\)
2\(\delta[0]\), \(\delta_{max}\leftarrow\) 0.0, \(\lambda_{i}\max_{j<i}\delta[j]\)
3\(\rho\leftarrow\lambda_{l}\frac{\delta[j]-\delta_{max}[j]}{\delta_{max}[i]+ \epsilon}\)
4\(l\leftarrow\arg\max_{i}\rho[i]\)
5\(\ast\)Neuron Localization */
6\(V_{l}\leftarrow\lambda_{i}\ \text{stats}(D_{l}^{j})\)
7\(v_{l}\leftarrow\lambda_{i}\ \lambda_{j}\ |\mathcal{A}_{\mathcal{D}}- \mathcal{A}_{\mathcal{D}\gets d(l,i,V_{l}[j])}|\leq\epsilon_{2}\)
8\(ACD_{l}\)\(\leftarrow\)\(\lambda_{j}\ \mathbb{E}\) (\(k^{\prime}|\texttt{do}(l,j,v_{l}^{j}\textgreater 0)\)) - \(\mathbb{E}(k^{\prime}|\texttt{do}(l,j,v_{l}^{j}\textgreater 0)\)) return\(l\), \(top_{k}(\max\ ACD_{l})\), \(top_{k}(\min\ ACD_{l})\).
```

**Algorithm 2**Dice (Debugging).

## VI Experiments

**Datasets and DNN models.** We consider \(10\) socially critical datasets from the literature of algorithmic fairness. These datasets and their properties are described in Table I. For the DNN model, we used the same architecture as the literature [17, 18, 29] and trained all datasets on a six-layers fully-connected neural network with \(\langle 64,32,16,8,4,2\rangle\) neurons. We used the same hyperparameters for the all training with num_epochs, batch_size, and learning_rate are set to \(1000\), \(128\), and \(0.01\), respectively. The accuracy of trained models are reported in Table V.

**Technical Details.** We implemented Dice with TensorFlow v2.7.0 and scikit-learn v0.22.2. We run all the experiments on an Ubuntu 20.04.4 LTS OS sever with AMD Ryzen Threadripper PRO 3955WX 3.9GHz 16-cores X 32 CPU and two NVIDIA GeForce RTX 3090 GPUs. We choose the values \(10\), \(1000\), \(0.025\), \(1\), and \(1\) for max_global, max_local, \(\epsilon\), \(s\_{g}\), and \(s\_{l}\) in Algorithm 1, respectively, and take the average of \(10\) multiple runs for all experiments. In Algorithm 2, we used \(L_{1}\)-norm, \(10^{-7}\), \(0.05\), and \(3\) for \(\Delta\), \(\epsilon_{1}\), \(\epsilon_{2}\), and \(k\), respectively.

**Research Questions.** We seek to answer the following three questions using our experimental setup.

* Can Dice characterize the amounts of information from protected attributes used for the inferences?
* Is the the proposed search algorithm effective and efficient (vis-a-vis the state-of-the-art techniques) in generating individual discrimination instances?
* Can the proposed causal debugging guide us to localize and mitigate the amounts of discrimination?
* Our open-source tool Dice with all experimental subjects are publicly accessible:

### _Characterizing QID via Search (RQ1)_

An important goal is to characterize the amount of information from protected attributes used during the inference of DNN models. Table II shows the result of experiments to answer this research question. The left side of table shows the
initial characteristics such as the number of protected values (\(m\)), the maximum possible amounts of discrimination (\(Q_{I}\)) based on min(\(\epsilon^{-1},m\)), and the initial number of clusters found using samples from the dataset (\(K_{I}\)). The right side of table shows the results after running our search for \(1\) hour. The column #\(I\) is the number of QID instances generated, and \(K_{F}\) is the maximum number of clusters discovered by Dice. The column T\({}_{K_{F}}\) is the time taken to find the maximum number of clusters from an input with initial clusters \(K_{I}\) (in seconds). The columns \(Q_{\infty}\) and \(Q_{1}\) are the quantitative individual discrimination based on min entropy and Shanon entropy, respectively. The columns #\(I_{K_{k}^{1}}\), #\(I_{K_{F}^{2}}\), and #\(I_{K_{F}^{3}}\) show the number of test cases with the highest, second-highest, and third-highest QIDs, respectively, that order test cases with their QID severity. Overall, the results show that Dice can find \(3.4\times\) more clusters (in average) from the initial characteristics within one minute of search. The DNN for Students dataset showed the largest increase in the number of clusters going from \(1.9\) to \(10.9\). Dice found that Adult Income Census dataset has the largest amounts of QID where \(4.05\) out of \(5.3\) bits (\(76.4\%\)) from protected variables are used to make decisions. The German Credit dataset with \(1.61\) out of \(4.0\) bits (\(40.0\%\)) showed the least amounts of discrimination. For test-case prioritizing, the column #\(I_{K_{F}^{1}}\) shows our approach to be useful in finding a small percentage of generated test cases with the worst-case discrimination. In \(7\) out of \(10\) experiments, Dice found less than \(50\) test cases with severe discrimination out of hundreds of thousands inputs.

**Answer RQ1:** The search algorithm is effective in characterizing the amounts of discrimination via QID. Within \(1\) hour, it increased the number of clusters by \(3.4\times\) in average, and found instances that used up to \(76\%\) of protected information (\(4.05\) out of \(5.3\) bits) to infer DNN outcomes. Dice is useful to prioritize test cases with their severity where it generates less than \(50\) test cases with the maximum QID among hundreds of thousands test cases.

### _Individual Discriminatory Instances (RQ2)_

In this section, we compare the efficiency and effectiveness of our search algorithm to the state-of-the-art techniques in searching individual discrimination (\(ID\)) instances (as defined in Section IV). Our baselines are Aequitas[19], ADF[17], and NeuronFair[18]. We obtained the implementations of these tools from their GitHub repositories and configured them according to the prescribed setting to have the best performance. Following these techniques, we report the results for each protected attribute separately. Table III shows the results of baselines and Dice in runs of 15 minutes. The results are averaged over \(10\) repeated runs. The column #\(ID\) is the total number of generated individual discriminatory instances. The column \(l\_s\) is the success rate of local stage of searches. We exclude the global success rate since the goal of global phase in our search is to maximize QID whereas the local phase focuses to generate many \(ID\) instances. We calculate success rate as the number of \(ID\) found over the total number of generated samples. The columns \(T.1st\) and \(T.1k\) are the amount of time (in seconds) taken to find the first \(ID\) instance and to generate \(1,000\) individual discriminatory instances (note: \(N/A\) in column \(T.1k\) means that the tool did not generate \(1,000\)\(IDs\) in the experiment timeout of \(900\) seconds in the average of 10 runs).

The result shows that Dice outperforms the-state-of-the-art in generating many ID instances. In particular, Dice finds \(27.1\times\), \(16.0\times\), and \(16.0\times\) more \(ID\)s in the best case compare to Aequitas, ADF, and NeuronFair, respectively. Dice also generates \(3.2\times\), \(2.3\times\), and \(2.6\times\) more \(ID\)s in the worst case compare to Aequitas, ADF, and NeuronFair, respectively. The success rate of local search are \(20.6\%\), \(33.0\%\), \(29.6\%\), and \(78.2\%\) in average for Aequitas, ADF, NeuronFair, and Dice, respectively. For the time taken to find the first \(ID\), Aequitas achieves the best result with an average of \(0.03\) (s) whereas it took Dice\(1.46\) (s) in average to find the first \(ID\). In average, Dice was found to take the lowest time to generate \(1000\)\(IDs\) with \(57.2\) (S), while ADF

\begin{table}
\begin{tabular}{|l|l|l|l|l|l|l|} \hline
**Dataset** & **\#Instances** & **\#Features** & \begin{tabular}{l} **Protected Groups** \\ _Name_ \\ \end{tabular} & \begin{tabular}{l} **Num.** **Protected** \\ _Values_ (m) \\ \end{tabular} & \multicolumn{2}{c|}{**Outcome Label**} \\ \cline{4-7} \begin{tabular}{l} Adli \\ _Census_ \\ \end{tabular} & \multirow{2}{*}{\(32,561\)} & \multirow{2}{*}{\(13\)} & Sex & \(2\) & \multirow{2}{*}{90} & \multirow{2}{*}{High Income} & \multirow{2}{*}{Low Income} \\ \cline{4-7} Income[31] & & & Age & & & \\ \cline{4-7} \begin{tabular}{l} _Census_ \\ \end{tabular} & \multirow{2}{*}{\(7,214\)} & \multirow{2}{*}{\(12\)} & Sex & \(2\) & \multirow{2}{*}{12} & \multirow{2}{*}{Did not Reoffend} & \multirow{2}{*}{Roeffend} \\ \cline{4-7} \begin{tabular}{l} _Census_ \\ \end{tabular} & & & & Age & & & \\ \hline \multirow{2}{*}{_Census_[34]} & \multirow{2}{*}{\(7,214\)} & \multirow{2}{*}{\(12\)} & Sex & \(2\) & \multirow{2}{*}{16} & \multirow{2}{*}{Good Credit} & \multirow{2}{*}{Bad Credit} \\ \cline{4-7} \begin{tabular}{l} _German_ \\ Credit[35] \\ \end{tabular} & & & Age & & & \\ \hline _Default_ & \multirow{2}{*}{\(13,636\)} & \multirow{2}{*}{\(23\)} & Sex & \(2\) & \multirow{2}{*}{12} & \multirow{2}{*}{Default} & \multirow{2}{*}{Not Default} \\ \cline{4-7} \begin{tabular}{l} _Hear_ \\ Health[37] \\ \end{tabular} & & & Age & & & \\ \hline _Bank Marketing[38]_ & \(45,211\) & \(16\) & Age & \(9\) & \(9\) & Subscriber & Non-subscriber \\ \hline _Dicebies[39]_ & \(768\) & \(8\) & Age & \(9\) & \(9\) & Positive & Negative \\ \hline _Shalomens_ & \multirow{2}{*}{\(1044\)} & \multirow{2}{*}{\(32\)} & Sex & \(2\) & \multirow{2}{*}{16} & \multirow{2}{*}{Pass} & \multirow{2}{*}{Not Pass} \\ \cline{4-7} \begin{tabular}{l} Performance[40] \\ \end{tabular} & & & Age & & & \\ \hline \multirow{2}{*}{MEPS15 [41]} & \multirow{2}{*}{\(15,830\)} & \multirow{2}{*}{\(137\)} & Race & \(2\) & \multirow{2}{*}{36} & \multirow{2}{*}{Utilized Benefits} & \multirow{2}{*}{Not Utilized Benefits} \\ \cline{4-7} \begin{tabular}{l} _Dice_ \\ \end{tabular} & & & Sex & & & \\ \hline \multirow{2}{*}{MEPS16 [41]} & \multirow{2}{*}{\(15,675\)} & \multirow{2}{*}{\(137\)} & Age & \multirow{2}{*}{36} & \multirow{2}{*}{Utilized Benefits} & \multirow{2}{*}{Not Utilized Benefits} \\ \cline{4-7} \begin{tabular}{l} _Dice_ \\ \end{tabular} & & & Sex & & \\ \cline{4-7} 
\begin{tabular}{l} _Dice_ \\ \end{tabular} & & & Sex & & & \\ \hline \end{tabular}
\end{table} TABLE I: Datasets used in our experiments.
took \(179.1\) (s), NeuronFair took \(135.4\) (s), and Aequitas took the longest time at \(197.7\) (s). Overall, our experiments indicate that Dice is effective in generating \(ID\) instances compared to the three state-of-the-art techniques, largely due to the smoothness of the feedback during the local search.

**Answer RQ2:** Our experiments demonstrate that Dice outperforms the state-of-the-art fairness testing techniques [19, 17, 18]. In the best case, our approach found \(20\times\) more individual discrimination (ID) instances than these techniques with almost \(3\times\) more success rates in average. However, we found that Dice is slower than those techniques in finding the first ID instance in the order of a few seconds.

### _Causal Debugging of DNNs for Fairness (RQ3)_

We perform experiments over the DNN models to study whether the proposed causal debugging approach is useful in identifying layers and neurons that significantly effect the amounts of discrimination as characterized by \(QID\). Table IV shows the results of experiments (averaged over \(10\) independent runs). The first two columns show the localized layer and its influence (i.e., \(l\) and \(\rho\) in Algorithm 2). The next six columns show top \(3\) neurons with the positive influence on fairness (i.e., activating those neurons reduce the amounts of discrimination based \(Q_{\infty}\)). The last six columns show top \(3\) neurons with the negative influence on fairness (i.e., activating those neurons increase the amounts of discrimination based \(Q_{\infty}\)). The layer index \(2\) is more frequently localized than other layers where the layers \(3\), \(4\), and \(5\) are localized once. Overall, the average causal difference (ACD) ranges from \(4\%\) to \(55\%\) for neurons with positive fairness effects and from \(0.6\%\) to \(18.3\%\) for neurons with negative fairness effects.

Guided by localization, Dice intervenes to activate neurons with positive fairness influence or de-activate those with negative influence. Table V shows the results of this mitigation strategy. The columns \(A\) and \(K\) show the accuracy and the number of clusters (averaged over a set of random test cases) reported by Dice before mitigation over the DNN model. The columns \(A^{=0}\) and \(K^{=0}\) are accuracy and the number of clusters reported after mitigating the DNN model by _de-activating_ the neuron with the highest negative fairness impacts (as suggested by Neuron\({}_{1}^{-}\) in Table IV). Similarly, the columns \(A^{>0}\) and \(K^{>0}\) are accuracy and the number of clusters reported after mitigating the DNN model by _activating_ the neuron with the highest positive fairness impacts (as suggested by Neuron\({}_{1}^{+}\) in Table IV). The results indicate that the activation interventions can reduce QID discrimination by at least \(5\%\) with \(3\%\) loss of accuracy and up to \(64.3\%\) with \(2\%\) loss of accuracy. The de-activation, on the other hand, can improve the fairness by at least \(6\%\) with \(1\%\) loss of accuracy and up to \(27\%\) with \(2\%\) loss.

**Answer RQ3:** The debugging approach implemented in Dice identified neurons that have at least \(5\%\) and up to \(55\%\) positive causal effects on the fairness and those which have at least \(0.6\%\) and up to \(18.3\%\) negative causal effects. A mitigation strategy followed by the localization can reduce the amounts of discrimination by at least \(6\%\) and up to \(64.3\%\) with less than 5% loss of accuracy.

## VII Discussion

_Limitation_. In this work, we consider all set of protected values and perturb them to generate counterfactual. Various perturbations of protected attributes may yield unrealistic counterfactuals and contribute towards false positives (an over-approximation of discrimination). This limitation can be mitigated by supplying domain-specific constraints (Age\(<\)YY \(\Longrightarrow\) NOT(married)): we already apply some common-sense constraints (e.g., to ensure valid range of age). In addition, similar to any dynamic testing methods, our approach might miss discriminatory inputs and is prone to false negatives. The probability of missing relevant inputs can be contained under a suitable statistical testing (e.g., Bayes factor). In addition, our debugging approach is similar to pin-pointing suspicious code fragments and is based on causal reasoning of its effect in decision making rather than correlation. But, it is not to furnish explanations or interpretations of black-box DNN functions.

_Threat to Validity_. To address the internal validity and ensure our finding does not lead to invalid conclusion, we follow established guideline and take average of repeated experiments. To ensure that our results are generalizable and address external validity, we perform our experiments on \(10\) DNN models taken from the literature of fairness testing. However,

\begin{table}
\begin{tabular}{|l|c|c||c|c|c|c|c|c|c|c|} \hline
**Dataset** & \(m\) & \(Q_{I}\) & \(K_{I}\) & \#\(I\) & \(K_{F}\) & T\({}_{K_{F}}\) & \(Q_{\infty}\) & \(Q_{1}\) & \#\(I_{K_{F}^{1}}\) & \#\(I_{K_{F}^{2}}\) & \#\(I_{K_{F}^{3}}\) \\ \hline Census & \(90\) & \(5.3\) & \(13.54\) & \(230,593\) & \(35.61\) & \(21.04\) & \(4.05\) & \(2.64\) & \(6.0\) & \(28.6\) & \(111.6\) \\ \hline Compas & \(12\) & \(3.6\) & \(3.12\) & \(157,968\) & \(10.24\) & \(6.50\) & \(1.81\) & \(1.40\) & \(35.2\) & \(338.7\) & \(1,016.9\) \\ \hline German & \(16\) & \(4.0\) & \(2.34\) & \(245,915\) & \(9.56\) & \(13.14\) & \(1.61\) & \(1.10\) & \(6.6\) & \(16.2\) & \(54.8\) \\ \hline Default & \(12\) & \(3.6\) & \(5.58\) & \(258,105\) & \(11.26\) & \(10.94\) & \(2.10\) & \(1.78\) & \(3,528.8\) & \(9,847.2\) & \(9,771.0\) \\ \hline Heart & \(14\) & \(3.8\) & \(4.54\) & \(270,029\) & \(10.01\) & \(11.88\) & \(2.31\) & \(1.80\) & \(21.7\) & \(135.2\) & \(579.7\) \\ \hline Bank & \(9\) & \(3.2\) & \(1.45\) & \(172,686\) & \(8.93\) & \(3.68\) & \(2.25\) & \(1.98\) & \(5,118.5\) & \(13,513.3\) & \(20,438\) \\ \hline Diabetes & \(10\) & \(3.3\) & \(2.39\) & \(504,414\) & \(7.90\) & \(0.016\) & \(1.40\) & \(1.11\) & \(89.7\) & \(609.6\) & \(2,310.1\) \\ \hline Students & \(16\) & \(4\) & \(1.90\) & \(133,221\) & \(10.90\) & \(14\) & \(1.93\) & \(1.35\) & \(16.0\) & \(130.7\) & \(128.7\) \\ \hline MEPS15 & \(36\) & \(5.2\) & \(7.03\) & \(19,673\) & \(18.52\) & \(31.62\) & \(2.61\) & \(1.62\) & \(2.6\) & \(3.5\) & \(6.0\) \\ \hline MEPS16 & \(36\) & \(5.2\) & \(9.06\) & \(14,266\) & \(19.25\) & \(49.16\) & \(2.21\) & \(1.52\) & \(2.0\) & \(3.5\) & \(6.0\) \\ \hline \end{tabular}
\end{table} TABLE II: Dice characterizes \(QID\) for \(10\) datasets and DNNs in \(1\) hour run (results are the average of \(10\) runs).
it is an open problem whether these datasets and DNN models are sufficiently representative for fairness testing.

## VIII Related Work

**Fairness Testing of ML systems.** Themis [10] presents a causal discrimination notion where they measure the difference between the fairness metric of two subgroups by _counterfactual_ queries; i.e., they sample individuals with the protected attributes set to A and compare the outcome to a counterfactual scenario where the protected attributes are set to B. Symbolic generation (SC) [28, 22] presents a black-box testing that approximates the ML models with decision trees and leverage symbolic execution over the tree structure to find individual discrimination (ID). AEQUITAS [19] uses a two-step approach that first uniformly at random samples instances from the input dataset to find a discriminatory instance and then locally perturb those instances to further generate biased test cases. ExpGA [16] proposed a genetic algorithm (GA) to generate ID instances in natural language processes. The proposed technique used a prior knowledge graph to guide the perturbation of protected attributes in the NLP tasks. While these techniques are black-box, they potentially suffer from the lack of local guidance during the search. ADF [17] utilized the gradient of the loss function as guidance in generating ID instances. The global phase explores the input space to find diverse set of individual discrimination whereas the local phase exploits each instance to generate many individual discriminatory (ID) instances in their neighborhoods. EIDIG [29] follows similar ideas to ADF, but uses different computations of gradients. First, it uses the gradients of output (rather than loss function) to reduce the computation cost at each iteration. Second, it uses momentum of gradients in

\begin{table}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|} \hline
**Dataset** & **Layer Index** & **Layer Influence** & **Neuron\({}^{+}\)** & **ACD\({}^{+}_{i}\)** & **Neuron\({}^{+}_{i}\)** & **ACD\({}^{+}_{i}\)** & **Neuron\({}^{+}_{i}\)** & **ACD\({}^{+}_{i}\)** & **Neuron\({}^{+}_{i}\)** & **ACD\({}^{+}_{i}\)** & **Neuron\({}^{+}_{i}\)** & **ACD\({}^{+}_{i}\)** & **Neuron\({}^{+}_{i}\)** \\ \hline Census & \(2\) & \(9.01\) & \(N_{19}\) & \(1.09\) & \(N_{2}\) & \(0.150\) & \(N_{12}\) & \(1.02\) & \(1.33\) & \(0.18\) & \(N_{24}\) & \(0.163\) & \(N_{14}\) & \(0.102\) \\ \hline Campus & \(2\) & \(2.07\) & \(N_{25}\) & \(0.16\) & \(N_{28}\) & \(0.419\) & \(N_{27}\) & \(0.366\) & \(N_{27}\) & \(N_{14}\) & \(N_{26}\) & \(1.1,238\) \\ \hline German & \(5\) & \(1.79\) & \(N_{3}\) & \(0.050\) & \(N_{1}\) & \(0.013\) & \(N/A\) & \(N/A\) & \(N/A\) & \(N/A\) & \(N/A\) & \(N/A\) \\ \hline Defali & \(2\) & \(27.58\) & \(N_{0}\) & \(0.039\) & \(N_{27}\) & \(0.022\) & \(N_{19}\) & \(0.014\) & \(N_{2}\) & \(0.031\) & \(N_{13}\) & \(0.027\) & \(N_{10}\) & \(0.109\) \\ \hline HEPS15 & \(0.898\) & \(0.35\) & \(N/A\) & \(N/A\) & \(N/A\) & \(N/A\) & \(N/A\) & \(N/A\) & \(N/A\) & \(N/A\) & \(N/A\) \\ \hline Barak & \(3\) & \(6.62\) & \(N_{0}\) & \(0.495\) & \(N_{2}\) & \(0.178\) & \(N_{1}\) & \(0.091\) & \(N_{6}\) & \(0.057\) & \(N_{11}\) & \(0.014\) & \(N/A\) & \(N/A\) \\ \hline Diabetes & \(2\) & \(1.67\) & \(N_{19}\) & \(0.041\) & \(N_{26}\) & \(0.035\) & \(N_{26}\) & \(0.031\) & \(N_{2}\) & \(0.042\) & \(N_{29}\) & \(0.001\) & \(N_{27}\) & \(N/A\) & \(N/A\) \\ \hline Students & \(2\) & \(4.01\) & \(N_{22}\) & \(0.550\) & \(N_{24}\) & \(0.442\) & \(N_{28}\) & \(0.229\) & \(N_{4}\) & \(0.084\) & \(N_{18}\) & \(0.055\) & \(N_{28}\) & \(0.026\) \\ \hline MIPS15 & \(2\) & \(35.44\) & \(N_{24}\) & \(0.230\) & \(N_{26}\) & \(0.167\) & \(N_{14}\) & \(0.160\) & \(N/A\) & \(N/A\) & \(N/A\) & \(N/A\) & \(N/A\) \\ \hline MIPS16 & \(2\) & \(47.46\) & \(N_{8}\) & \(0.147\) & \(N_{11}\) & \(0.138\) & \(N_{24}\) & \(0.144\) & \(N_{30}\) & \(0.006\) & \(N_{30}\) & \(N_{22}\) & \(0.001\) \\ \hline \end{tabular}
\end{table} TABLE V: \(A\) is accuracy, \(K\) is the average number of clusters from test cases; \(A^{=0}\) is the accuracy after deactivating the neuron with the highest negative fairness impacts; \(K^{=0}\) is the average number of clusters after the deactivation; \(A^{>0}\) is the accuracy after activation the neuron with the highest positive fairness impacts; \(K^{>0}\) is the average number of clusters after the activation; and \(T_{I}\) is the amount of computation times for localization and mitigation in seconds.

\begin{table}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
**Dataset** & **Pred.** & \multicolumn{3}{c|}{**Advoc. [17]**} & \multicolumn{3}{c|}{**Adv. [17]**} & \multicolumn{3}{c|}{**Neuron\({}^{+}_{i}\)**} & \multicolumn{3}{c|}{**ACD\({}^{+}_{i}\)**} & \multicolumn{3}{c|}{**ACD\({}^{+}_{i}\)**} & \multicolumn{3}{c|}{**ACD\({}^{+}_{i}\)**} & \multicolumn{3}{c|}{**ACD\({}^{+}_{i}\)**} \\ \hline  & **avg** & \(9.01\) & \(1.03\) & \(1.03\) & \(0.02\) & **69.53** & \(1.13\) & \(1.26\) & **69.53** & \(7.13\) & \(7.12\) & **69.27** & \(1.03\) & **69.77** & \(7.16\) & **69.77** & \(7.16\) & **69.77** \\ \hline Census & **avg** & \(8.73\) & \(2.21\) & \(0.02\) & \(0.02\) & \(115.58\) & \(0.18\) & \(12.63\) & \(1.03\) & \(0.50\) & \(5.21\) & \(7.24\) & \(12.18\) & \(19.93\) & \(0.08\) & \(0.38\) & \(38.68\) & \(79.93\) & \(79.23\) & \(74.20\) & \(0.15\) & \(0.50\) & \(58.98\) \\ \hline Defali & **avg** & \(8.73\) & \(2.21\) & \(0.22\) & \(0.02\) & \(115.48\) & \(12.18\) & \(15.83\) & \(42.00\) & \(0.53\) & \(33.07\) & \(0.33\) & \(1.11\) & \(54.8\) & \(0.48\) & \(0.48\) & \(0.49\) & \(0.39\) & \(79.12\) & \(1.20\) & \(0.34\) & \(0.46\) & \(0.56\) & \(0.58\) & \(0.58\) \\ \hline Defali & **avg** & \(8.73\) & \(2.21\) & \(0.22\) & \(0.02\) & \(115.48\) & \(12.16\) & \(15.83\) & \(53.40\) & \(0.63\) & \(0.63\) & \(0.39\) & \(
global phase to avoid local optima. NeuronFair[18] extends ADF and EIDIG to support unstructured data (e.g., image, text, speech, etc.) where the protected attributes might not be well-defined. In addition, NeuronFair is guided by the DNN's internal neuron states (e.g., the pattern of activation and deactivation) and their activation difference. Beyond the capability of these techniques, Dice quantifies the amounts of discrimination, enables software developers to prioritize test cases, and searches multiple protected attributes at one time.

Beyond the scope of this paper, a body of prior work [42, 43, 44, 23, 45, 46] considered testing for group fairness. Fairway[43] mitigates biases after finding suitable ML algorithm configurations. In doing so, they used a multi-objective optimization (FLASH) [47]. Parfait-ML [45] searches the hyperparameter space of classic ML algorithms via a gray-box evolutionary algorithm to characterize the magnitude of biases from the hyperparameter configuration.

**Debugging of Deep Neural Network.** Cradle[33] traced the execution graph of a DNN model over two different deep-learning frameworks and used the differences in the outcomes to localize what backend functions might cause a bug. However, since Cradle did not use causal analysis, it showed a high rate of false positive. Audee[48] used a similar approach, but it leveraged causal-testing methods. In particular, it designed strategies to intervene in the DNN models and tracked how the intervention affected the observed inconsistencies. We adapted the layer localization of Cradle and Audee; but our causal localization is developed using do logic for a meta-property (fairness). Audee used a simple perturbation of neuron values for functional correctness (i.e., any inconsistency shows a bug) without considering the accuracy or the severity of neuron contributions to a bug.

**In-process Mitigation.** A set of work considers in-process algorithms to mitigate biases in ML predictions [49, 50, 51]. Adversarial debiasing [49] and Prejudice remover [50] improve fairness by adding constraints to model parameters or the loss function. Exponentiated gradient [51] uses a meta-learning algorithm to infer a family of classifiers that maximizes accuracy and fairness. Different than these approaches, we develop a mitigation approach that is specialized to handle neural networks for individual fairness. This setting allows us to exploit the layer-based structure of NNs toward causal reasoning and mitigation. We believe that our approach can be extended with in-process mitigation techniques to maximize fairness in the DNN-based decision support systems.

**Formal Methods.** We believe that this paper can connect to the rich literature of formal verification and its application. Here, we provide two examples. FairSquare[52] certifies a fair decision-making process in probabilistic programs using a novel verification technique called the weighted-volume-computation algorithm. SFTREE[53] formulated the problem of inferring fair decision tree as a mixed integer linear programming and apply constraint solvers iteratively to find solutions.

**Fairness in income, wealth, and taxation.** We develop a fairness testing and debugging approach that is uniquely geared toward handling regression problems. Therefore, our approach can be useful to study and address biases in income and wealth distributions [54] among different race and gender. Furthermore, our approach can be useful to study fairness in taxation (e.g., vertical and horizontal equities [55, 56]). We left further study in these directions to future work.

## IX Conclusion

DNN-based software solutions are increasingly being used in socio-critical applications where a bug in their design may lead to discriminatory behavior. In this paper, we presented Dice: an information-theoretic model to characterize the amounts of protected information used in DNN-based decision making. Our experiments showed that the search and debugging algorithms, based on the quantitative landscape, are effective in discovering and localizing fairness defects.

**Acknowledgement.** The authors thank the anonymous ICSE reviewers for their time and invaluable feedback to improve this paper. This research was partially supported by NSF under grant DGE-2043250 and UTEP College of Engineering under startup package.
