FairSquare: probabilistic verification of program fairness
Authors:
Open Access
- 12 October 2017
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 1 (OOPSLA) , 1-30
Abstract
With the range and sensitivity of algorithmic decisions expanding at a break-neck speed, it is imperative that we aggressively investigate fairness and bias in decision-making programs. First, we show that a number of recently proposed formal definitions of fairness can be encoded as probabilistic program properties. Second, with the goal of enabling rigorous reasoning about fairness, we design a novel technique for verifying probabilistic properties that admits a wide class of decision-making programs. Third, we present FairSquare, the first verification tool for automatically certifying that a program meets a given fairness property. We evaluate FairSquare on a range of decision-making programs. Our evaluation demonstrates FairSquare’s ability to verify fairness for a range of different programs, which we show are out-of-reach for state-of-the-art program analysis techniques.Keywords
Funding Information
- National Science Foundation (1704117 and 1566015)
This publication has 41 references indexed in Scilit:
- Discrimination in Online Ad DeliveryQueue, 2013
- Solving non-linear arithmeticACM Communications in Computer Algebra, 2013
- Software for exact integration of polynomials over polyhedraACM Communications in Computer Algebra, 2012
- Three naive Bayes approaches for discrimination-free classificationData Mining and Knowledge Discovery, 2010
- The WEKA data mining softwareACM SIGKDD Explorations Newsletter, 2009
- QEPCAD BACM SIGSAM Bulletin, 2003
- Efficiently computing static single assignment form and the control dependence graphACM Transactions on Programming Languages and Systems, 1991
- A random polynomial-time algorithm for approximating the volume of convex bodiesJournal of the ACM, 1991
- On the Complexity of Computing the Volume of a PolyhedronSIAM Journal on Computing, 1988
- Semantics of probabilistic programsJournal of Computer and System Sciences, 1981