Research

Context: There are growing concerns about algorithmic fairness, as some machine learning (ML)-based algorithms have been found to exhibit biases against protected attributes such as gender, race, age and so on. Individual fairness requires an ML classifier to produce similar outputs for similar individuals. Verification Based Testing (Vbt) is a state-of-the-art black-box testing algorithm for individual fairness that leverages constraint solving to generate test cases. Objective: Generating diverse test cases is expected to facilitate efficient detection of diverse discriminatory data instances (i.e., cases that violate individual fairness). Hashing-based sampling techniques draw a sample approximately uniformly at random from the set of solutions of given Boolean constraints. We propose Vbt-X, which improves Vbt with hashing-based sampling, aiming to improve its testing performance. Method: We realize hashing-based sampling for Vbt. The challenge is that the off-the-shelf hashing-based sampling techniques cannot be integrated in a straightforward manner because the constraints in Vbt are generally not Boolean. Moreover, we propose several enhancement techniques to make Vbt-X more efficient. Results: To evaluate our method, we conduct experiments, where Vbt-X is compared to Vbt, Sg and ExpGA (other well-known fairness testing algorithms) over a set of configurations consisting of several datasets, protected attributes, and ML classifiers. The results show that, with each configuration, Vbt-X detects more discriminatory data instances with higher diversity than Vbt and Sg. Vbt-X detects discriminatory data instances with higher diversity than ExpGA, though the number of discriminatory data instances detected by Vbt-X is lesser than ExpGA. Conclusion: Our proposed method performs better than other state-of-the-art black-box fairness testing algorithms, particularly in terms of diversity. Our method can serve to efficiently identify flaws in ML classifiers with respect to individual fairness for subsequent improvements of an ML classifier. On the other hand, although our method is specific to individual fairness, it could work for testing other aspects of a software system such as security and counterfactual explanations with some technical adaptations, which remains for future work.

There is a growing concern on algorithm fairness, according to wider adoption of machine learning techniques in our daily life. Testing of individual fairness is an approach to algorithm fairness concern. Verification Based Testing (VBT) is a state-of-the-art testing technique for individual fairness, that leverages verification techniques using constraint solving. In this paper, we develop a black-box individual fairness testing technique Vbt-X, which applies hash-based sampling techniques to the test case generation part of Vbt, aiming to improve its testing ability. Our evaluation by experiments confirms that Vbt-X improves the testing ability of Vbt by 2.92 times in average.

Fairness testing, given a machine learning classifier, detects discriminatory data contained in it via executing test cases. In this paper, we propose a new approach to fairness testing named Vbt-Ct, which applies combinatorial t-way testing (CT) to Verification Based Testing (Vbt). Vbt is a state-of-the-art fairness testing method, which represents a given classifier under test in logical constraints and searches for test cases by solving such constraints. CT is a coverage-based sampling technique, with an ability to sample diverse test data from a search space specified by logical constraints. We implement a proof-of-concept of Vbt-Ct, and see its feasibility by experiments. We also discuss its advantages, current limitations, and further research directions.

The conflict-driven clause learning (CDCL) is a standard algorithmic framework on which almost state-of-the-art SAT solvers are based. During the solving process of the CDCL solver, many learnt clauses are generated, and those turned out to be useless in terms of some criteria are removed. Since the decision commonly relies on heuristics, the same clauses can appear multiple times. Hence, the evaluation of the learnt clause utility has a significant impact on the solver’s performance. The recently proposed DL heuristic determines the utility in terms of the number of times clauses are generated. To improve this, we introduce the similarity of learnt clauses and propose a similarity-based clause management method. In experiments we compared our method with the DL, both implemented on top of CaDiCal, and we confirmed that our method outperforms the DL as well as the intact CaDiCal in both PAR-2 scores and the number of solved instances.