Abstract
The concept of explainability is envisioned to satisfy society's demands for transparency on machine learning decisions. The concept is simple: like humans, algorithms should explain the rationale behind their decisions so that their fairness can be assessed. While this approach is promising in a local context (e.g. to explain a model during debugging at training time), we argue that this reasoning cannot simply be transposed in a remote context, where a trained model by a service provider is only accessible through its API. This is problematic as it constitutes precisely the target use-case requiring transparency from a societal perspective. Through an analogy with a club bouncer (which may provide untruthful explanations upon customer reject), we show that providing explanations cannot prevent a remote service from lying about the true reasons leading to its decisions. More precisely, we prove the impossibility of remote explainability for single explanations, by constructing an attack on explanations that hides discriminatory features to the querying user. We provide an example implementation of this attack. We then show that the probability that an observer spots the attack, using several explanations for attempting to find incoherences, is low in practical settings. This undermines the very concept of remote explainability in general.
Introduction
As AI systems increasingly handle sensitive decisions like credit scoring or job applications, society has demanded transparency. This has led to the "right to explanation" (enshrined in regulations like GDPR). Most research assumes an "in-house" setting where developers have full access to the model. However, in the real world, we usually interact with models remotely via an API.
This paper identifies a massive trust gap in these interactions: if the service provider is malicious or wants to hide illegal discrimination, they can simply lie. This is formalized as the Bouncer Problem: just as a club bouncer might tell a rejected patron "it’s your shoes" to hide a racial bias, a remote AI can provide a "legitimate" explanation that masks its true, discriminatory logic.
The PR Attack: Masking Discrimination
The authors define a security threat model where a user (the auditor) and a server (the provider) are untrusted parties. The core of the deception is the Public Relations (PR) Attack.
In a PR attack, when a user submits a query $x$, the server first computes the decision $y$ using its real, potentially biased model $C$. Instead of explaining $C$, the server quickly crafts a surrogate model $C'$ that is "legitimate" (it doesn't use forbidden features) but happens to produce the same decision $y$ for that specific input $x$. The server then explains $C'$ to the user, effectively "fairwashing" the decision.
Implementation and Detection
The authors provide a concrete implementation of the PR attack for decision trees. The algorithm prunes branches containing discriminatory features and replaces them with "dummy" logic that matches the desired output for the current user.
The only way to catch such an attack is by identifying Incoherent Pairs (IP). An IP consists of two inputs that are identical in all "legitimate" features but receive different decisions. If a user finds an IP, they have mathematical proof that the model is using hidden, discriminatory features. However, the authors prove that for a single query, it is mathematically impossible to distinguish a truthful explanation from a PR attack.
Key Results
The paper evaluates the hardness of detecting these attacks using the German Credit Dataset, a classic benchmark containing 1,000 client profiles with 24 features.
- Low Detection Probability: In experiments, the probability of finding an Incoherent Pair by randomly changing a single feature (like sex or age) was as low as 0.27% to 2.27%.
- The Query Burden: To be 99% confident that a remote service isn't hiding a bias regarding "sex/status," a user would need to test approximately 2,555 pairs of inputs. For "employment status," they would need 490 pairs.
These results suggest that while a dedicated auditor might catch a biased model, an average user receiving a single explanation has virtually no way to verify its truthfulness.
Conclusion
The "Bouncer Problem" undermines the very concept of remote explainability. We should stop blindly trusting remote explanations as a tool for fairness. Instead, the authors suggest two paths forward: Provable Explainability, using cryptographic protocols like zero-knowledge proofs to force servers to prove their explanations match their models, and Collaborative Auditing, where users pool queries to collectively hunt for the Incoherent Pairs that reveal a provider's lies.
Summary updated