You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
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.
author:
- |
    Erwan [Le Merrer]{}\
    Univ Rennes, Inria, CNRS, Irisa\
    <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS>
- |
    Gilles Trédan\
    LAAS/CNRS\
    <PRESIDIO_ANONYMIZED_EMAIL_ADDRESS>
title: ' The Bouncer Problem: Challenges to Remote Explainability '
---

Introduction
============

Modern decision-making driven by black-box systems now impacts a significant share of our lives [@fatml; @deLaat2018]. Those systems build on user data, and range from recommenders [@fb-rec] ([*e.g.*, ]{}for personalized ranking of information on websites) to predictive algorithms ([*e.g.*, ]{}credit default) [@fatml]. This widespread deployment, along with the opaque decision process provided by those systems raises concerns about transparency for the general public or for policy makers [@Goodman_Flaxman_2017]. This translated in some jurisdictions ([*e.g.*, ]{}United States of America and Europe) into a so called *right to explanation* [@Goodman_Flaxman_2017; @10.1093/idpl/ipx022], that states that the output decisions of an algorithm must be motivated.

#### Explainability of in-house models

An already large body of work is interested in the *explainability* of implicit machine learning models (such as neural network models) [@adadi2018peeking; @guidotti2018survey; @molnar2019]. Indeed, those models show state-of-art performances when it comes to a task accuracy, but they are not designed to provide explanations –or at least intelligible decision processes– when one wants to obtain more than the output decision of the model. In the context of *recommendation*, the expression “post hoc explanation” has been coined [@rec-exp]. In general, current techniques for explainability of implicit models take trained in-house models and aim at shedding light on some input features causing salient decisions in their output space. LIME [@lime] for instance builds a surrogate model of a given black-box system that approximates its predictions around a region of interest; the surrogate is an explainable model by construction (such as a decision tree), so that it can explain some decision facing some input data. The amount of queries to the black-box model is assumed to be unbounded by LIME and others [@Galhotra:2017:FTT:3106237.3106277], permitting virtually exhaustive queries to it. This is what is making them suitable for the inspection of in-house models, by their designers.

#### The temptation to explain decisions to users.

The temptation for corporations to apply the same reasoning in order to explain some decisions to their users is high. Indeed, this would support the will for a more transparent and trusted web by the public. Facebook for instance attempted to offer a form of transparency for the ad mechanism targeting its users, by introducing a “Why I am seeing this” button on received ads. For a user, the decision system is then *remote*, and can be queried only using inputs (its profile data) and the observation of system decisions. Yet, from a security standpoint, the remote server executing the service is untrusted to the users. Andreou et al. [@andreou2018ndss] recently empirically observed in the case of Facebook that those explanations are “incomplete and can be misleading”, conjecturing that malicious service providers can use this incompleteness to hide the true reasons behind their decisions.

In this paper, we question the possibility of such an explanation setup, from a corporate and private model in destination to users: we go one step further than the observations by the work of Andreou et al. [@andreou2018ndss], by demonstrating that remote explainability simply cannot be a reliable guarantee of the lack of use of discriminative features. In a remote black-box setup such as the one of Facebook, we show that a simple attack, we coin the Public Relations (PR) attack, undermines remote explainability.

#### The bouncer problem as a parallel for hardness

For the sake of the demonstration, we introduce the *bouncer problem* as an illustration of the difficulty for users to spot malicious explanations. The analogy works as follows: let’s picture a bouncer at the door of a club, deciding whoever might enter the club. When he issues a negative decision –refusing the entrance to a given person–, he also provides an explanation for this rejection. However, his explanation might be malicious, in the sense that his explanation does not present the true reasons of this persons’ rejection. Consider for instance a bouncer discriminating people based on the color of their skin. Of course he will not tell people he refuses the entrance based on that characteristic, since this is a legal offence. He will instead invent a biased explanation that the rejected person is likely to accept.

The classic way to assess a discrimination by the bouncer is for associations to run tests (following the principle of statistical causality [@CIS-247618] for instance): several persons attempt to enter, while they only vary in their attitude or appearance on the possibly discriminating feature ([*e.g.*, ]{}the color of their skin). Conflicting decisions by the bouncer is then the indication of a possible discrimination and is amenable to the building of a case for prosecution.

We make the parallel with bouncer decisions in this paper by demonstrating that an user cannot trust a single (one-host) explanation provided by a remote model, and that the only solution to spot inconsistencies is to issue multiple requests to the service. Unfortunately, we also demonstrate the problem is hard, in the sense that spotting an inconsistency in such a way is intrinsically not more efficient then exhaustively search on a locally available model to identify a problem, which is an intractable process.

#### Rationale and organization of the paper

We build a general setup for remote explainability in the next section, that has the purpose of representing actions by a service provider and by users, facing models decisions and explanations. The fundamental blocks for the impossibility proof of a reliable remote explainability, or its hardness for multiple queries are presented in Section \[s:model\]. We present the *bouncer problem* in Section \[s:bouncer\], that users have to solve in order to detect malicious explanations by the remote service provider. We then illustrate the PR attack, that the malicious provider may execute to remove discriminative explanations to users, on decision trees (Section \[s:dt\]). We then practically address the bouncer problem by modeling a user trying to find inconsistencies from a provider decisions based on the German Credit dataset and a neural network classifier, in Section \[s:nn\]. We discuss open problems in Section \[s:discussion\], before reviewing related works in Section \[s:related\] and concluding in Section \[s:conclusion\]. Since we show that remote explainability in its current form is undermined, this work thus aims to be a motivation for researchers to explore the direction of *provable* explainability, by designing new protocols such as for instance one implying cryptographic means ([*e.g.*, ]{}such as in *proof of ownership* for remote storage), or to build collaborative observation systems to spot inconsistencies and malicious explanation systems.

Explainability of remote decisions {#s:model}
==================================

In this work, we study *classifier models*, that will issue decisions given user data. We first introduce the setup we operate in: it is intended to be as general as possible, so that the results drawn from it can apply widely.

General Setup
-------------

We consider a classifier $C: \mathcal{X}\mapsto \mathcal{Y}$ that assigns inputs $x$ of the feature space $\mathcal{X}$ to a class $C(x)=y\in \mathcal{Y}$. Without loss of generality and to simplify the presentation, we will assume the case of a binary classifier: $\mathcal{Y}=\{0,1\}$; the decision is thus the output label returned by the classifier.

#### Discriminative features and classifiers

To produce a decision, classifiers rely on features (variables) as an input. Those are for instance the variables associated to a user profile on a given service platform ([*e.g.*, ]{}basic demographics, political affiliation, purchase behavior, residential profile [@andreou2018ndss]). In our model, we consider that the feature space contains two types of features: *discriminatory* and *legitimate* features. The use of discriminatory features allows for exhibiting the possibility of a malicious service provider issuing decisions and biased explanations. This problematic is also refered to as *rationalization* in a paper by Aïvodji et al [@pmlr-v97-aivodji19a]. This setup of course does not prevent to consider honest providers not leveraging them. While we leave open the precise definition of discriminatory features, we note that any particular feature can be considered as discriminatory in this current work. In this model, the principal property of a *discriminatory* feature is that the service provider does not want to admit its use. Two main reasons come to mind:

-   Legal: the jurisdiction’s law forbids decisions based on a list of criterion[^1] which are easily found in classifiers input spaces. A service provider risks prosecution upon admitting the use of those.

    For instance, features such as age, sex, employment, or the status of foreigner are considered as discriminatory in the work [@10.1007/978-3-642-22589-5_20], that looks into the German Credit Dataset, that links bank customer features to the accordance or not of a credit.

-   Strategical: the service provider wants to hide the use of some features on which its decisions are based. This could be to hide some business secret from competitors (because of the accuracy-fairness trade-off [@pmlr-v81-menon18a] for instance), or to avoid “reward hacking” from users biasing this feature, or to avoid bad press.

Conversely, any feature that is not discriminatory is coined *legit*.

= \[ draw, rectangle, node distance=10pt, minimum width=3cm, minimum height=2cm, text width=3cm, align=center, \] = \[ draw, rectangle, node distance=10pt, minimum width=3cm, minimum height=0.5cm, text width=3cm, align=center, \] at (0,0) (xl) ; at (0,0) (x) ; at (-1,1.3) [$\mathcal{X}$]{};

;

at (3,-.2) (semi) ; at (3,0) (semi) ; at (2,1.3) [$\mathcal{C}$]{};

;

(yes) at (5,0) ; (no) at (yes.south) ;

;

(ca) at (2.6,.8) [$\star$]{}; (cb) at (3.3,.05) [$\star$]{};

(x.south east) – (ca) – (no.south); (x.north) – (ca) – (yes.north);

(xl.south east) – (cb) – (no.south); (xl.north) – (cb) – (yes.north);

Formally, we partition the classifier input space $\mathcal{X}$ along these two types of features: legitimate features $X_l$ that the model can legitimately exploit to issue a decision, and discriminative features $X_d$ (please refer to Figure \[f:space\]). In other words $\mathcal{X}=(X_l,X_d)$, and any input $x\in \mathcal{X}$ can be decomposed as a pair of legitimate and discriminatory features $x=(x_l,x_d)$. We assume the input contains at least one legitimate feature: $X_l\neq \emptyset$.

We also partition the classifier space accordingly: let $\mathcal{C}_l
\subset \mathcal{C}$ the space of legitimate classifiers (among all classifiers $\mathcal{C}$), which do not rely on any feature of $X_d$ to issue a decision. More precisely, we consider that a classifier is legitimate if and only if arbitrarily changing any discriminative input feature does never change its decision: $$C \in \mathcal{C}_l
\Leftrightarrow \forall x_l \in X_l, \forall x_d,x_d' \in
\mathcal{X}_d^2, C((x_l,x_d))=C((x_l,x_d')).$$ Observe that therefore, any legitimate classifier $C_l$ could simply be defined over input subspace $X_l\subset \mathcal{X}$. As a slight notation abuse to stress that the value of discriminative features does not matter in this legitimate context, we write $C((x_l,\emptyset))$, or $C(x \in X_l)$ as the decision produced regardless of any discriminative feature. It follows that the space of discriminative classifiers complements the space of legitimate classifiers: $\mathcal{C}_d = \mathcal{C}\setminus
\mathcal{C}_l$.

We can now reframe the main research question we address: *Given a set of discriminative features $X_d$, and a classifier $C$, can we decide if $C \in \mathcal{C}_d$, in the remote black-box interaction model ?*

#### The black-box remote interaction model

We question the *black-box remote interaction* model (see [*e.g.*, ]{}paper [@Tramer:2016:SML:3241094.3241142]), where the classifier is exposed to users through a remote API. In other words users can *only* query the classifier model with an input and obtain a label as an answer ([*e.g.*, ]{}0 or 1). In this remote setup, users then cannot collect any specific information about the internals of the classifier model, such as its architecture, its weights, or its training data. This corresponds to a security threat model where two parties are interacting with each other (the user and the remote service), and where the remote model is implemented on a server, belonging to the service operator, that is untrusted by the user.

Requirements for Remote Explainability
--------------------------------------

Explainability is often presented as a solution to increase the acceptance of AI [@adadi2018peeking], and to potentially prevent discriminative AI behaviour. Let us expose the logic behind this connection.

#### A simple definition of an explanation

First, we need to define what is an explanation, to go beyond Miller’s definition as an “answer to a why-question” [@DBLP:journals/corr/Miller17a]. Since the topic of explainability is becoming a hot research field with (to the best of our knowledge) no consensus on a more technical definition of an explanation, we will propose for the sake of our demonstration that an explanation is coherent with respect to the standard *modus ponens* ($\Rightarrow$) rule. For instance, if explanation $a$ explains decision $b$, it means that in context $a$, the decision produced will necessarily be $b$.

In this light, we directly observe the beneficial effect of such explanations on our parallel to club bouncing: while refusing someone, the bouncer may provide him with the reasons of that rejection; the person can then correct their behaviour in order to be accepted on next attempt.

This property is also enough to prove non-discrimination: if $a$ does not involve discriminating arguments (which can be locally checked by the user as $a$ is a sentence), and $a\Rightarrow b$, then decision $b$ is not discriminative in case $a$. On the contrary, if $a$ does involve discriminating arguments, then decision $b$ is taken on a discriminative basis, and is therefore a discriminative decision. In other words, this property of an explanation is enough to reveal discrimination.

To sum up, any explanation framework that behaves “logically” ([*i.e.*, ]{}fits the modus ponens truth table) –which is in our view a rather mild assumption– is enough to establish the discriminative basis of a decision. We believe this is the rationale of the statement “transparency can improve user’s trust in AI systems”. In the following, we include such explanations in our interaction model.

#### Requirements on the user side for checking explanations

A user that queries a classifier $C$ with an input $x$ gets two elements: the decision (inferred class) $y=C(x)$ and an explanation $a$ such that $a$ explains $y$. Formally, upon request $x$, a user collects $exp_C(x)=(y,a)$. We assume that such user can locally check $a$ is *apropos*: that $a$ corresponds to its input $x$. Formally, we write $a\in A(x)$. This allows us to formally write a non-discriminatory explanation as $a\in A(x_l)$. This forbids lying by explaining an input that is different than $x$.

We also assume that the user can locally check the explanation is *consequent*: user can check that $a$ is compatible with $y$. This forbids crafting explanations that are incoherent w.r.t. the decision (like a bouncer that would explain why you can enter in while leaving the door locked).

To produce such explanations, we assume the existence of an explanation framework $exp_C$ producing explanations for classifier $C$ (this could for instance by the LIME framework [@lime]). The explanation $a$ explaining decision $y$ in context $x$ by classifier $C$ is written $a=exp_C(y,x)$.

Limits of Remote Explainability: The PR (Public Relations) Attack
-----------------------------------------------------------------

We articulate our demonstration of the limits of explainability in a remote setup by showing that a malicious service provider can hide the use of discriminating features for issuing its decisions, while conforming to the mild explainability framework we described in the previous subsection.

Such a malicious provider thus wants to *i)* produce decisions based on discriminative features and to *ii)* produce non-discriminatory explanations to avoid prosecution. A practical approach to explain a discriminative decision $b$ while not revealing its discriminative nature is to simply *omit* discriminating arguments in its explanation $a$. This is what club bouncers may be tempted to do. Yet for classifiers, depending on the nature of the explanation it might seem non-trivial. In the following we show it is, by introducing a new attack on explanations.

#### A Generic Attack Against Remote Explainability

We coin this attack the *Public Relations attack* (noted PR). The idea is rather simple: upon reception of an input $x$, first compute discriminative decision $C(x)$. Then train a local surrogate model $C'$ that is non-discriminative, and such that $C'(x)=y$. Explain $C'(x)$, and return this explanation along with $C(x)$.

= \[ draw, rectangle, node distance=10pt, minimum width=3cm, minimum height=2cm, text width=3cm, align=center, \] = \[ draw, rectangle, node distance=10pt, minimum width=3cm, minimum height=0.5cm, text width=3cm, align=center, \]

(0,0) [[$x=(x_l,\emptyset)\:\stackrel{C}{\rightarrow}\:y$]{}\
\[1em\]]{};

(-0.5,-3) – node\[left\] ++(0,+2); (+0.5,-1) – node\[right\] ++(0,-2); at (0,-3.3) [User]{}; at (-2,1.5) [**A.**]{};

(0,0) [[$x=(x_l,x_d)\:\stackrel{C}{\rightarrow}\:y$]{}\
\[1em\]]{};

(-0.5,-3) – node\[left\] ++(0,+2); (+0.5,-1) – node\[right\] ++(0,-2); at (0,-3.3) [Discriminated User]{}; at (-2,1.5) [**B.**]{};

(0,0) [[$(x_l,x_d)\:\stackrel{C}{\rightarrow}\:y$]{}\
[[$\text{PR}(C,(x_l,x_d),y) \rightarrow \textcolor{green}{C'}$]{}\
s.t. $C'(x_l)=y$]{}]{};

(-0.5,-3) – node\[left\] ++(0,+2); (+0.5,-1) – node\[right\] ++(0,-2); at (0,-3.39) [Discriminated & Fooled User]{}; at (-2,1.5) [**C.**]{};

Figure \[fig:attack\] illustrates a decision based solely on legitimate features (**A.**), a provider giving an explanation that includes discriminatory features (**B.**), and the attack by a malicious provider (**C.**). In all three scenarios, a user is querying a remote service with inputs $x$, and obtaining decisions $y$ each along with an explanation. In case **B.**, the explanation $exp_C$ reveals the use of discriminative features $X_d$; this provider is prone to complaints. To avoid those, the malicious provider (**C.**) leverages the PR attack, by first computing $C(x)$ using its discriminative classifier $C$. Then, based on the legitimate features $x_l$ of the input, and its final (discriminative) decision $y$, it derives a classifier $C'$ for the explanation.

Core to the attack is the ability to derive such classifier $C'$:

Given an arbitrary classifier $C\in \mathcal{C}_d$, a PR attack is a function that finds for an arbitrary input $x$ a classifier $C'$: $$\text{PR}(C,x,C(x)) \rightarrow C',
    \label{PR}$$ such that $C'$ satisfies two properties:

-   **coherence:** $C'(x_l)=y$.

-   **legitimacy:** $C'\in \mathcal{C}_l$.

**Effectiveness of the attack:** Observe that $a=exp_{C'}(y,x)$ is apropos since it directly involves $x: a \in A(x)$. Since we have $C'(x)=y$, it is also consequent. Finally, observe that since $C'\in \mathcal{C}_l$, then $a\in A(x_l)$: $a$ is non-discriminatory.

**Existence of the attack:** We note that crafting a classifier $C'$ satisfying the first property is trivial since it only involves a single data point $x$. An example solution is the Dirac delta function of the form: $$C'(x') =C'((x'_l,x'_d))= 
     \begin{cases}
       \delta_{x'_l,x_l} &\quad\text{if } y=1\\
       1- \delta_{x'_l,x_l} &\quad \text{if } y=0 \\
     \end{cases},$$

where $\delta$ is the Dirac delta function. Informally, this solution corresponds to explaining a decision by taking exactly all features in the input as preponderant for the decision, and then to expose them in the explanation.

#### One implementation of a PR attack

On can rely on state-of-the-art explanation frameworks, such as LIME, that can produce a decision tree as the explanation. Having access to a decision tree trivially fits the modus ponens we introduced as a basic explanation framework. Let us consider the following process, executed by a malicious provider. The discriminating classifier $C$ is first turned into a decision tree, by building a surrogate model. Given this new $C$, we define $C'$ as the decision tree derived from $C$ by removing all intermediary nodes relying on features in $X_d$. To remove those nodes, just take the branch that leads to decision $y$ given $x_d$, and prune the other branches. The resulting tree $C'$ will by definition have $C'(x_l)=y$ since $\forall x \in X_l,
C'(x)=C((x_l,x_d))$. The resulting tree $C'$ is another decision tree. Moreover, since $C'$ does not involve any features of $X_l$ its explanation is legitimate to the user (as opposed to case **B.**). This tree pruning algorithm is given in Section \[s:dt\].

We have presented the framework and an attack necessary to question the possibility of remote explainability. We next discuss the possibility for a user to spot that an explanation is malicious and obtained by a PR attack. We stress that if a user cannot, then the very concept of remote explainability is at stake.

The bouncer problem: spotting PR attacks {#s:bouncer}
========================================

We presented in the previous section a general setup for remote explainability. We now formalise our research question regarding the possibility of a user to spot an attack in that setup.

Using $\epsilon$ requests that each returns a decision $y_i=C(x_i)$ and an explanation $exp_C(y_i,x)$, we denote by BP($\epsilon$), decide if $C \in \mathcal{C}_d$.

An Impossibility Result for One-Shot Explanations
-------------------------------------------------

We already know that using a single input point is insufficient:

$BP(1)$ has no solution.

The Dirac construction above always exists.

Indeed, constructions like the introduced Dirac function, or the tree pruning construct a PR attack that produces explainable decisions. Given a single explanation on model $C'$ ([*i.e.*, ]{}$\epsilon=1$) the user cannot distinguish between the use of a model ($C$ in case **A.**), or the one of a crafted model by a PR attack ($C'$ in case **C.**), since it is consequent. This means that such a user cannot spot the use of hidden discriminatory features due to the PR attack by the malicious provider.

We observed that a user cannot spot a PR attack, with BP(1). This is already problematic, as it gives a formal explanation on why Facebook ad system cannot be trusted [@andreou2018ndss].

The Hardness of Multiple Queries for Explanation
------------------------------------------------

To address the case BP($\epsilon$), we observe that a PR attack generates a new model $C'$ for each request; in consequence, an approach to detect that attack is to detect the impossibility (using multiples queries) of a *single* model $C'$ to produce coherent explanations for a set of observed decisions. We here study this approach.

Interestingly, classifiers and bouncers share this property that their outputs are all mutually exclusive (each input is mapped to exactly one class). Thus we have $In \Rightarrow \overline{Out}$ (with $In$ and $Out$ the positive or negative decision to for instance enter a place). In which case it is impossible to have $a\Rightarrow In $ *and* $a\Rightarrow Out $. Note that non-mutually exclusive outputs are not bound by this rule.

A potential problem for the PR attack is a decision conflict, in which $a$ could explain both $b$ and $\bar{b}$ its opposite. For instance, imagine a bouncer refusing you the entrance of a club because, say, you have white shoes. Then, if the bouncer is coherent, he should refuse the entrance to anyone wearing white shoes, and if you witness someone entering with white shoes, you could argue against the lack of coherence of the bouncer decisions. We build on those incoherences to spot PR attacks.

In order to examine the case BP($\epsilon$), where $\epsilon>1$, we first define the notion of an *incoherent pair*:

Let $x^1=(x^1_l,x^1_d),x^2=(x^2_l,x^2_d) \in
  \mathcal{X}=X_l\times X_d$ be a two input points in the feature space. $x^1$ and $x^2$ form an incoherent pair for classifier $C$ iff they both have the same legit feature values in $X_l$ and yet end up being classified differently:

$x^1_l=x^2_l \wedge C(x_1)\neq C(x_2)$. For convenience we write $(x^1,x^2)\in IP_C$.

Finding such an IP is a potent proof of PR attack on the model by the provider. Indeed, we can formalise the intuitive reasoning “if you let others enter with white shoes then this wasn’t the true reason for my rejection”:

Only decisions resulting from a model crafted by a PR attack (\[PR\]) can exhibit incoherent pairs: $ IP_C \neq \emptyset \Rightarrow C \in \mathcal{C}_d$.

We prove the contra-positive form $ C \not\in \mathcal{C}_d \Rightarrow IP_C = \emptyset $. Let $C\not\in \mathcal{C}_d$. Therefore $C \in \mathcal{C}_l$, and by definition: $ \forall x_l \in X_l, \forall x_d,x_d' \in \mathcal{X}_d^2,
  C((x_l,x_d))=C((x_l,x_d'))$. By contradiction assume $IP_C \neq
  \emptyset$. Let $(x^1,x^2) \in  IP_C: x^1_l=x^2_l \wedge C(x_1)\neq
  C(x_2)$. This directly contradicts $C \in \mathcal{C}_l$. Thus $IP_C= \emptyset$.

We can show that there is always a pair of inputs allowing to detect a discriminative classifier $C \in \mathcal{C}_d$.

A classifier $C'$, resulting from a PR attack, always has at least one incoherent pair: $C' \in \mathcal{C}_d \Rightarrow IP_C \neq \emptyset$.

We prove the contrapositive form $IP_C = \emptyset \Rightarrow C
  \not\in \mathcal{C}_d$. Informally, the strategy here is to prove that if no such pair exists, this means that decisions are not based on discriminative features in $X_d$, and thus the provider had no interest in conducting a PR attack on the model; the considered classifier is not discriminating.

Assume that $IP_C =  \emptyset$. Let $x_\emptyset\in X_d$, and let $C^l:X_l\mapsto
  \mathcal{Y}$ be a legitimate classifier such that $C^l(x_l)=C((x_l,x_\emptyset))$. Since $IP_C=\emptyset$, this means that $\forall x^1,x^2 \in \mathcal{X}, x^1_l=x^2_l \Rightarrow
  C(x_1)=C(x_2)$. In particular thus $\forall x\in \mathcal{X},
  C(x=(x_l,x_d))=C^l(x_l,x_\emptyset)$. Thus $C=C^l$; by the definition of a PR attack being only applied to a model that uses discriminatory features, this leads to $C\in \mathcal{C} \setminus \mathcal{C}_d$, [*i.e.*, ]{} $C\not\in \mathcal{C}_d$.

Which directly applies to our problem:

$BP(\vert  \mathcal{X}\vert)$ is solvable.

Straightforward: $C' \in \mathcal{C}_d \Rightarrow IP_C \neq
\emptyset$, and since $IP \subseteq \mathcal{X} \times  \mathcal{X}$ testing the whole input space will necessarily exhibit such an incoherent pair.

This last result is rather weakly positive: even though any PR attack is eventually detectable, in practice it is impossible to exhaustively explore the input space of modern classifiers due to their dimension. This remark also further questions the opportunity of remote explainability.

Illustration and experiment
===========================

In this section, we first give an algorithm that implements a PR attack on binary decision trees, as an illustration. We then experiment on the German Credit dataset to quantify the hardness of finding incoherent pairs in a black-box setup.

Illustration using Decision Trees {#s:dt}
---------------------------------

= \[ draw, rectangle, minimum width=3cm, text width=2cm, align=center, \] = \[ draw, fill=blue!10,rectangle, minimum width=3cm, text width=2cm, align=center, \] = \[ draw,color=red, fill=orange!10,rectangle, minimum width=3cm, text width=2cm, align=center, \]

= \[ draw, circle, fill=green!30, node distance=10pt, minimum width=1cm, minimum height=0.5cm, align=center\] = \[ draw, circle, fill=red!30, node distance=10pt, minimum width=1cm, minimum height=0.5cm, align=center, \] ;

(dis) at (0,0) [Disguised ?]{}; (label) [$C(x):$]{}; (age) [Age $<60$]{}; (socks) [Wears pink socks ?]{};

(e1) [[Enter]{}]{}; (b1) [[Bounce]{}]{};

(e2) [[Enter]{}]{}; (b2) [[Bounce]{}]{};

(dis) – node\[above\] [Y]{} (age); (dis) – node\[above\] [N]{} (socks);

(age) – node\[above,xshift=-2mm\] [Y]{} (e1); (age) – node\[above,xshift=2mm\] [N]{} (b1);

(socks) – node\[above,xshift=-2mm\] [Y]{} (e2); (socks) – node\[above,xshift=2mm\] [N]{} (b2);

(dis) at (0,0) [Disguised ?]{}; (label) [$C'(x_l)|x_d<60:$]{}; (socks) [Wears pink socks ?]{};

(e1) [[Enter]{}]{};

(e2) [[Enter]{}]{}; (b2) [[Bounce]{}]{};

(dis) – node\[above\] [N]{} (socks); (dis) – node\[above,xshift=-2mm\] [Y]{} (e1);

(socks) – node\[above,xshift=-2mm\] [Y]{} (e2); (socks) – node\[above,xshift=2mm\] [N]{} (b2);

(dis) at (0,0) [Disguised ?]{}; (label) [$C'(x_l)|x_d \geq 60:$]{}; (socks) [Wears pink socks ?]{}; (b1) [[Bounce]{}]{};

(e2) [[Enter]{}]{}; (b2) [[Bounce]{}]{};

(dis) – node\[above\] [N]{} (socks); (dis) – node\[above,xshift=-2mm\] [Y]{} (b1);

(socks) – node\[above,xshift=-2mm\] [Y]{} (e2); (socks) – node\[above,xshift=2mm\] [N]{} (b2);

In this section, we embody the previous observations and approaches on the concrete type of classifiers based on decision trees. The choice of decision trees is motivated first because of its recognised importance ([*e.g.*, ]{}`C4.5` ranked number one of the top ten data mining algorithms [@wu2008top]). Second, there is a wide consensus on their explainability, that is straightforward [@molnar2019]: a path in the tree “naturally” lists the attributes considered by the algorithm to establish a classification. Finally, the simplicity of crafting PR attacks on those make them good candidates for an illustration and argues for the practical implementability of such attack.

We denote $\mathcal{T}$ as the set of tree-based classifiers. We do not need any assumption on how the tree is built ([*e.g.*, ]{}`C4.5` [@quinlan2014c4]). Regarding explainability, we here only need to assume that decision trees are explainable: $ \forall C \in \mathcal{T}, exp_C$ exists.

Let $C \in \mathcal{T} \cap \mathcal{C}_d$ be a discriminatory binary tree classifier. Each internal node $n \in V(C)$ tests incoming examples based on a feature $n.label$. Each internal node is connected to exactly two sons in the tree, named $n.r$ and $n.l$ for *right* and *left*. Depending on the (binary) result of this test, the example will continue on either of this paths. We denote the father of an internal node by $n.father$ (the root node $r$ is the only node such that $r.father=\emptyset$).

Algorithm \[alg:tree\] presents a PR attack on binary decision trees. To ease its presentation, we assume that given an input $x$, $n.r$ (right) will by convention always be the branch taken after evaluating $x$ on $n$. The algorithm starts by initializing the target decision tree $C'$ as a copy of $C$. Then, it selectively removes all nodes involving discriminative features, and replaces them with the subtree the target example $x$ would take.

$y=C(x)$ Let $\{n_0,\ldots n_l\}$ be breadth first ordering of the nodes of $C$ Let $C'=C$

$y,exp_{C'}(y,(x_l,\emptyset))$

To do so, Algorithm \[alg:tree\] removes each discriminative node $n_i$ by connecting $n_{i-1}$ and $n_{i+1}$. While this approach would be problematic in the general case (we would loose the $n_i.l$ subtree), in the context of $x$ we know the explored branch is $n_i.r$, so we simply reconnect this branch, and replace the left subtree by a dummy output.

An example is presented in Figure \[fig:trees\]: the discriminative classifier $C$ is queried for the explanation $exp_C(C(x),x)$ of input $x$. To produce an answer for a discriminative feature such as the age, it first applies Algorithm \[alg:tree\] on $C$, given the query $x$. If $x<60$ (upper right in Figure \[fig:trees\]), the explanation $exp_{C'}$ has simply became a node with the age limit, leading to an “Enter” decision. In case $x\geq 60$, the explanation node is a legit one (“Disguised”), leading to the “Bounce” decision. Both explanation then do not exhibit the fact that the provider relied on a discriminative feature in $C$. This exhibits that $BP(1)$ does not have solution; second we see that $BP(2)$, testing the age feature in $X_d$ has a solution. $x^1=(c,40,d)$ and $x^2=(c,70,d)$ are an instance of an incoherent pair (with arbitrary $c$ and $d$ in the (disguised,age,pink-socks) input vector).

Algorithm \[alg:tree\] implements a PR attack.

To prove the statement, we need to prove that:

-   $C'(x_l)$ is defined

-   $C'(x_l)=y$

-   $C'$ is explainable

First, observe that any nodes of $C'$ containing discriminative features is removed line 7. Thus, $C'$ only takes decisions based on features in $X_l$: $C'(x_l)$ is defined.

Second, observe that by construction since $x=(x_l,x_d)$, and since any discriminative node $n$ is replaced by this right ($n.r$) outcome which is the one that corresponds to $x_d$. In other words, $\forall x'_l \in X_l, C'(x'_l)=C((x'_l,x_d))$: $C'$ behaves like $C$ where discriminative features are evaluated at $x_d$. This is true in particular for $x_l:
  C'(x_l)=C((x_l,x_d))=C(x)=y$.

Finally, observe that $C'$ is a valid decision tree. Therefore, according to our explainability framework, $C'$ is explainable.

Interestingly, the presented attack can be efficient as it only involves pruning part of the target tree. In the worst case, this one has $\Omega(2^{d})$ elements, but in practice decision trees are rarely that big.

Finding IPs on a Neural Model: the German Credit dataset {#s:nn}
--------------------------------------------------------

We now take a closer look at the detectability of the attack, namely: how difficult is it to spot an IP ? We illustrate this by experimenting on the German Credit dataset. Despite the low dimensionality of that dataset, we show that the probability of finding IPs, such as one in Figure \[fig:trees\], is low.

#### Experimental setup

We leverage Keras over TensorFlow to learn a neural network-based model for the German Credit dataset [@credit]. This bank dataset classifies client profiles ($1,000$ of them), described by a set of attributes, as good or bad credit risks. Multiple techniques has been employed to model the credit risks on that dataset, which range from $76.59\%$ accuracy for a SVM to $78.90\%$ for a hybrid between genetic algorithm and a neural network [@ORESKI20142052].

The dataset is composed of 24 features (some categorical ones, such as sex, of status, were set to numerical). This thus constitutes a low dimensional dataset as compared to current applications (observations in [@andreou2018ndss] reported up to $893$ features for the sole application of ad placement on user feeds on Facebook).

The neural network we built is inspired by the one proposed [@KHASHMAN20106233] in 2010, and that reached $73.17\%$ accuracy. It is a simple multi-layer perceptron, with a single hidden layer of $23$ neurons (with sigmoid activations), and a single output neuron for the binary classification of the input profile to “risky” or not. In this experiment we use the Adam optimizer and a learning rate of $0.1$ (leading to much better convergences than in [@KHASHMAN20106233]), with a validation split of $25\%$. We create 30 models, with an average accuracy of $76.97\%@100$ epochs on the validation set (with a standard deviation of $0.92\%$).

We removed the columns containing a discriminating feature according to [@10.1007/978-3-642-22589-5_20] ([*i.e.*, ]{}age, sex, employment, foreigner), and train 30 models with the same parameters, and obtain an average of $77.21\%@100$ epochs (deviation of $1.36\%$). The observed relatively high variance on the final accuracy for a model training explains the higher accuracy score in this experiment, even averaged over 30 independent trainings.

We kept $50$ profiles from the dataset as a test set, so we can perform our core experiment: the four discriminatory features of each of those profiles are sequentially replaced by the ones of the 49 remaining profiles; each resulting test profile is fed to the model for prediction. (This permits to test the model with realistic values in those features. This process creates 2450 profiles to search of an IP). We count the number of times the output risk label has switched, as compared to the original untouched profile fed to the same model. We repeat this operation 30 times to observe deviations.

#### The low probability of findings IPs at random

![Percentage of label changes when swapping the discriminative features in the test set data. Those indicate the low probability to spot a **PR** attack on the provider model.[]{data-label="f:credit"}](gcdplot.pdf){width="0.9\linewidth"}

Figure \[f:credit\] depicts the proportion of label changes over the total number of test queries; recall that a label change while considering two inputs constitutes an IP. We observe that if we just change one of the four features, we obtain on average $1.86\%$, $0.27\%$, $1.40\%$, $2.27\%$ labels changes (for the employment, sex/status, age, foreigner features, respectively), while $4.25\%$ if the four features are simultaneously changed. (Standard deviations are of $1.48\%$, $0,51\%$, $1,65\%$, $2,17\%$ and $3,13\%$, respectively).

Despite the low dimensionality of this dataset’s inputs, the probability to find IPs is thus low; it turns out that we can also compute an expectation of the number of queries for a user to find such an IP. Users can query the service with inputs, until they are *confident* enough that such pair does not exist. Assuming one seeks a $99\%$ confidence level –that is, less than one percent of chances to falsely detect a discriminating classifier as non-discriminating–, and using the detection probabilities of Figure \[f:credit\], we can compute the associated p-values. A user testing a remote service based on those hypotheses would need to craft respectively $490, 2555, 368, 301, 160$ (for the employment, sex/status, age, foreigner, and all four respectively) pairs in the hope to decide on the existence or not of an IP, as presented in Figure \[f:creditConf\] (please note the log-scale on the $y$-axis).

This highlights the hardness to experimentally check for PR attacks.

![Confidence level as a function of the number of tested input pairs, based on the German Credit detection probability in Figure \[f:credit\]. Dashed line represents a $99\%$ confidence level.[]{data-label="f:creditConf"}](pval.pdf){width="\linewidth"}

Discussion {#s:discussion}
==========

We now list in this section several consequences of the findings in this paper, and some open questions.

Findings and Applicability
--------------------------

We have shown that a malicious provider can always craft a fake explanation to hide its use of discriminatory features, by creating a surrogate model for providing an explanation to a given user. An impossibility result follows, for the user to detect such an attack while using a single explanation. The detection by a user, or a group of users, is possible only in the case of multiple and deliberate queries (BP($\epsilon>1$)); this process may require an exhaustive search of the input space. We argue that with the current increase in dimensionality of inputs for decision making due to the progress made possible by deep learning, the probability to detect such attacks will decrease accordingly.

We note that the malicious providers have another advantage for covering PR attacks. Since multiple queries must be issued to spot inconsistencies via IP pairs, basic rate limiting mechanisms for queries may block and ban the incriminated users. Defenses of this kind, for preventing attacks on online machine services exposing APIs, are being proposed [@Hou:2019:MDA:3326285.3329042]. This adds another layer of complexity for the observation of misbehaviour.

Connection with Disparate Impact
--------------------------------

We now briefly relate our problem to *disparate impact*: a recent article [@feldman2015certifying] proposes to adopt “a generalization of the 80 percent rule advocated by the US Equal Employment Opportunity Commission (EEOC)” as a criteria for disparate impact. This notion of disparate impact proposes to capture discrimination through the variation of outcomes of an algorithm under scrutiny when applied to different population groups.

More precisely, let $\alpha$ be the disparity ratio. The authors propose the following formula, here adapted to our notations [@feldman2015certifying]: $$\alpha= \frac{\mathbb{P}(y|x_d=0)}{\mathbb{P}(y|x_d=1)},$$ where $X_d=\{0,1\}$ is the discriminative space reduced to a binary discriminatory variable. Their approach is to consider that if $ \alpha<0.8$ then the tested algorithm could be qualified as discriminative.

To connect disparate impact to our framework, we can conduct the following strategy. Consider a classifier $C$ having a disparate impact $\alpha$. We search for Incoherent Pairs as follows: first, pick $x\in X_l$ a set of legit features. Then take $A=(x,\mathbf{0})$, representing the discriminated group, and $B=(x,\mathbf{1})$ representing the undiscriminated group. Then test both $C(A)$ and $C(B)$: if $C(A)\neq C(B) $ then $(A,B)$ is an IP. The probability of finding an IP in this approach can be written as $\mathbb{P}(IP)$.

We can develop: $\mathbb{P}(IP)= \mathbb{P}(C(A)\neq C(B))= \mathbb{P}(C(A)\cap\overline{C(B)}) + \mathbb{P}(\overline{C(A)}\cap C(B))= \mathbb{P}(C(A)) -
\mathbb{P}(C(A) \cap C(B)) + \mathbb{P}(C(B)) - \mathbb{P}(C(A) \cap
C(B)).$ Since $\alpha= \mathbb{P}(C(A))/\mathbb{P}(C(B))$, we write: $\mathbb{P}(IP)= \mathbb{P}(C(B))(1+\alpha) -2 \mathbb{P}(C(A)\cap C(B))$. Using conditional probabilities, we have $\mathbb{P}(C(A)\cap C(B)) =
\mathbb{P}(C(B)|C(A)).\mathbb{P}(C(A))$.

Thus $\mathbb{P}(IP)= \mathbb{P}(C(B))(1+\alpha -2\alpha.\mathbb{P}(C(B)|
C(A)))$. Since the conditional probability $\mathbb{P}(C(B)|
C(A))$ is difficult to assess without further hypotheses on $C$, let us investigate two extreme scenarios:

-   Independence: $C(A)$ and $C(B)$ are completely independent events, even though $A$ and $B$ share their legit features in $x$. This scenario, which is not very realistic, could model purely random decisions with respect to attributes from $X_d$. In this scenario $\mathbb{P}(C(B)|
    C(A)) = \mathbb{P}(C(B))$.

-   Dependence: $C(A) \Rightarrow C(B)$: if $A$ is selected despite its membership to the discriminated group ($A=(x,0)$), then necessarily $B$ must be selected, as it can only be “better” from $C$’s perspective. In this scenario $\mathbb{P}(C(B)|
    C(A)) = 1$.

![Probability to find an Incoherent Pair (IP), as a function of $\mathbb{P}(C(B))$ the probability of success for a non-discriminated group.[]{data-label="fig:disimp"}](discrimEstim2){width="1.05\linewidth"}

Figure \[fig:disimp\] represents the numerical evaluation of our two scenarios. First, it shows that the probability of finding an IP strongly depends on the probability of a success for the non-discriminated group $\mathbb{P}(C(B))$. Indeed, since the discriminated group has an even lower probability of success, a low success probability for the non-discriminated group implies frequent cases where both $C(A)$ and $C(B)$ are failures, which does not constitutes an incoherent pair.

In the absence of disparate impact, both scenarios provide very different results: the independence scenario easily identifies incoherent pairs –which is coherent with the “random” nature of the independence assumption–. This underlines the unrealistic nature of the independence scenario in this context. With a high disparate impact however ([*e.g.*, ]{}$\alpha=0.1$), the discriminated group has a high probability of failure. Therefore the probability of finding an IP is very close to the simple probability of the non-discriminated group having a success $\mathbb{P}(C(B))$, regardless of the considered scenario.

The dependence scenario nicely illustrates a natural connection: the higher the disparate impact, the higher the probability to find an IP. While this only constitutes a thought experiment, we believe this highlights possible connections with standard discrimination measures and conveys the intuition that in practice, the probability of finding incoherent pairs exposing a PR attack strongly depends on the intensity of the discrimination hidden by the PR attack.

Open Problems for Remote Explainability
---------------------------------------

#### On the test efficiency

Its is common for fairness assessment tools to leverage testing. As the features that are considered discriminating are often precise [@10.1007/978-3-642-22589-5_20; @Galhotra:2017:FTT:3106237.3106277], the test queries for fairness assessment can be targeted and some notions of efficiency in terms of the amount of requests can be derived. This may be done by sampling the feature space under question for instance (as in work by Galhotra et al. [@Galhotra:2017:FTT:3106237.3106277]).

Yet, it appears that with current applications such as social networks [@andreou2018ndss], users spend a considerable amount of time online, producing more and more data that turn into features, and also are the basis to the generation of other meta-features. In that context, the full scope of features, discriminating or not, may not be clear to a user. This makes exhaustive testing even theoretically unreachable, due to the very likely non-complete picture of what providers are using to issue decisions. This is is another challenge on the way to remote explainability, if providers are not willing to release a complete and precise list of all attributes leveraged in their system.

#### Towards a provable explainability?

Some other computing applications, such as data storage or intensive processing also have questioned the possibility of malicious service providers in the past. Motivated by the plethora of offers in the cloud computing domain and the question of quality of service, protocols such as *proof of data possession* [@pdp], or *proof-based verifiable computation* [@comp-verif], assume that the service provider might be malicious. A solution to still have services executed remotely in this context is then to rely on cryptographic protocols to formally verify the work performed remotely. To the best of our knowledge, no such a provable process logic has been adapted to explainability. That is certainly an interesting development to come.

Related Work {#s:related}
============

As a consequence of the major impact of machine learning models in many areas of our daily life, the notion of *explainability* has been pushed by policy makers and regulators. Many works address explainability of inspected model decisions on a local setup (please refer to surveys [@guidotti2018survey; @datta2016algorithmic; @molnar2019]) – some specifically for neural network models [@NIPS2018_8141] –, where the number of requests to the model is unbounded. Regarding the question of fairness, a recent work specifically targets the fairness and discrimination of in-house softwares, by developing a testing-based method [@Galhotra:2017:FTT:3106237.3106277].

The case of models available through a remote black-box interaction setup is particular, as external observers are bound to scarce data (labels corresponding to inputs, while being limited in the number of queries to the black-box [@tramer]). Adapting the explainability reasoning to models available in a black box setup is of a major societal interest: Andreou et al. [@andreou2018ndss] shown that Facebook’s explanations for their ad platform are incomplete and sometimes misleading. They also conjecture that malicious service providers can “hide” sensitive features used, by explaining decisions with very common ones. In that sense, our paper is exposing the hardness of explainability in that setup, confirming that malicious attacks are possible. Milli et al. [@Milli:2019:MRM:3287560.3287562] provide a theoretical ground for reconstructing a remote model (a two-layer ReLu neural network) from its explanations and input gradients; if further research prove the approach practical for current applications, this technique may help to infer the use of discriminatory features in use by the service provider.

In the domain of security and cryptography, some similar setups have found a large body of work to solve the trust problem in remote interacting systems. In *proof of data possession* protocols [@pdp], a client executes a cryptographic protocol to verify the presence of his data on a remote server; the challenge that the storage provider responds to assesses the possession or not of some particular piece of data. Protocols can give certain or probabilistic guarantees. In *proof-based verifiable computation* [@comp-verif], the provider returns the results of a queried computation, along with a proof for that computation. The client can then check that the computation indeed took place. Those schemes, along this paper exhibiting attacks on remote explainability, motivate the need for the design of secure protocols.

Our work in complementary to classic discrimination detection in automated systems. In contrast to works on *fairness* [@fair-phil] that attempt to identify and measure discrimination from systems, our work does not aim at spotting discrimination, as we have shown it can be hidden by the remote malicious provider. We instead are targeting the occurrence of incoherent explanation produced by such a providers in the will to cover its behavior, which is a a completely different nature than fairness based test suites. Galhotra et al. [@Galhotra:2017:FTT:3106237.3106277], inspired by statistical causality [@CIS-247618], for instance propose create input datasets for observing discrimination on some specific features by the system under test.

More closely related to our work is the recent paper by Aivodji et al. [@pmlr-v97-aivodji19a], that introduces the concept of rationalization, in which a black-box algorithm is approximated by a surrogate model that is “fairer” that the original black-box. In our terminology, they craft $C'$ models that optimise arbitrary fairness objectives. To achieve this, they explore decision tree models trained using the black-box decisions on a predefined set of inputs. This produces another argument against black-box explanability in a remote context. The main technical difference with our tree algorithm section \[s:dt\] is that their surrogates $C'$ optimises an exterior metric (fairness) at the cost of some coherence (fidelity in the authors’ terminology). In contrast, our illustration section \[s:dt\] produces surrogates with perfect coherence that do not optimise any exterior metric such as fairness. In our model, spotting an incoherence ([*i.e.*, ]{}the explained model produces a $y$ while the black-box produces a $\bar{y}$) would directly provide a proof of manipulation and reveal the trickery. Interestingly, the incoherent pair approach fully applies in the context of their model surrogates, as it arises as soon as more than one surrogate is used (regardless of the explanation). Our paper focuses on the user-side observation of explanations, and users ability to discover such attacks. We rigorously prove that single queries are not sufficient to determine a manipulation, and that the problem is hard even in the presence of multiple queries and observations.

Conclusion {#s:conclusion}
==========

In this paper, we studied explainability in a remote context, which is sometimes presented as a way to satisfy society’s demand for transparency facing automated decisions. We prove it is unwise to blindly trust those explanations: like humans, algorithms can easily hide the true motivations of a decision when asked for explanation. To that end, we presented an attack that generates explanations to hide the use of an arbitrary set of features by a classifier. While this construction applies to any classifier queried in a remote context, we also presented a concrete implementation of that attack on decision trees. On the defensive side, we have shown that such a manipulation cannot be spotted by one-shot requests, which is unfortunately the nominal use-case. However, the proof of such trickery (pairs of classifications that are not coherent) necessarily exists. We further evaluated in a practical scenario the probability of finding such pairs, which is low. The attack is thus arguably impractical to detect for an isolated user.

We conclude that this must consequently question the whole concept of the explainability of a remote model operated by a third party provider, at the very least. A research direction is to develop secure schemes in which the involved parties can trust the exchanged information about decisions and their explainability, as enforced by new protocols. A second line of research may be the collaboration of users observations for spotting the attack in an automated way. We believe this is an interesting development to come, in relation with the promises of AI and automated decisions processes.

Acknowledgements {#acknowledgements .unnumbered}
================

The authors want to thank the bouncer of the Berghain club, for having inspired this work.

[^1]: For instance in the U.K.: <https://www.gov.uk/discrimination-your-rights>.