The Role of Counterfactual Explanations in Model Extraction Attacks

On the discussion on limitations: Following the suggestions of Reviewer 4YsF we have now included this section in our modified manuscript (see page 9).

“Limitations and future work: One limitation of our theoretical results is the assumption of a convex decision boundary. While this assumption is satisfied in some settings [5], it is not often the case. In addition, the derivations require the counterfactual generating mechanisms to provide the closest counterfactuals. Any relaxation to these assumptions are paths for exploration. We note that the attack proposed in Section 3.2 remains valid as long as the majority of counterfactuals lie closer to the decision boundary; they need not be the closest ones to the corresponding original instances. Utilizing techniques in active learning in conjunction with counterfactuals is another problem of interest. Extending the results of this work for multi-class classification scenarios can also be explored. Our findings also highlight an interesting connection between Lipschitz constant and vulnerability to model extraction, which could also have implications for future work on generalization, adversarial robustness, etc.”

[1] H. Gouk, E. Frank, B. Pfahringer, and M. J. Cree, “Regularisation of neural networks by enforcing Lipschitz continuity,” Mach Learn, vol. 110, no. 2, pp. 393–416, Feb. 2021.

[2] M. Jordan and A. G. Dimakis, “Exactly Computing the Local Lipschitz Constant of ReLU Networks,” in Advances in Neural Information Processing Systems, Curran Associates, Inc., 2020, pp. 7344–7353.

[3] P. Pauli, A. Koch, J. Berberich, P. Kohler and F. Allgöwer, "Training Robust Neural Networks Using Lipschitz Bounds," in IEEE Control Systems Letters, vol. 6, pp. 121-126, 2022.

[4] X. Liu, X. Han, N. Zhang, and Q. Liu, “Certified Monotonic Neural Networks,” in Advances in Neural Information Processing Systems, Curran Associates, Inc., 2020, pp. 15427–15438.

[5] B. Amos, L. Xu, and J. Z. Kolter, “Input Convex Neural Networks,” in Proceedings of the 34th International Conference on Machine Learning, PMLR, Jul. 2017, pp. 146–155.

We appreciate the recognition of the relevance of our work. Based on the comments, we make the following edits to our paper.

On other counterfactual-generation mechanisms: We have now included results from a rich set of experiments covering different model architectures and counterfactual generating methods (see Section 4 and Appendix B.2). Particularly, the results cover sparse counterfactuals which are generated by using the L1-norm as the cost function in the counterfactual generating method. Moreover, we would like to point out that the proposed practical attack is independent of the counterfactual generating method, as long as the generated counterfactuals lie sufficiently closer to the decision boundary. They need not be the closest ones to the corresponding original instances. We included this in the limitations section (see page 9).

On the assumptions of Lipschitz continuity and monotonicity: We note that the practical neural networks may have large global Lipschitz constants. However, we first make the observation that our theoretical guarantee (Theorem 3) would also extend to the local Lipschitz continuity, which may be more common as compared to global Lipschitz continuity (added Remark 2 on page 6). In fact, this observation leads to another interesting interpretation of our theoretical results that is generally insightful even for practical neural networks: the regions of the decision boundary with low local-Lipschitz constant are more easily reconstructed.

Furthermore, we have now included a new set of experimental results demonstrating the relationship of the attack performance with the Lipschitz constant (see Figure 17 in Appendix B.2 page 21). Following [1], we approximate the Lipschitz constant of a neural network by the product of the spectral norms of the weight matrices. We achieve different Lipschitz constants by controlling the L2-regularization of the layer weights while training the target model. Our approximations were in the range 37 to 713 and are also comparable to the values present in other works [1, Figure 4],[2, Figure 1],[3, Table 1]. Therefore, it is evident from the experiments that the proposed attack remains valid for significantly large Lipschitz constants. Our observations follow our theoretical insights, where a greater Lipschitz constant gradually degrades the fidelity for a given number of queries.

Our findings are interesting and significant because they highlight an interesting connection between Lipschitz constant and vulnerability to model extraction. Furthermore, noting that a low Lipschitz constant is an indicator of good generalization of a model and adversarial robustness [1],[2],[3], our findings also point towards a potential tradeoff between good generalization and vulnerability to model extraction attacks, which could also be interesting for future research.

Moreover, we note that monotonicity is a favorable characteristic in the context of fair and interpretable machine learning [4], which is achievable particularly in the case of tabular data. We would like to clarify that monotonicity is not assumed in case of the main theorems or in the proposed practical attack or experiments. We only assume monotonicity to show an additional reduction in the query complexity as pointed out in Corollary 1.

We are grateful to Reviewer q134 for their review and for pointing out our key strengths, i.e., “a theoretical analysis and a development of practical method for model extraction using counterfactual explanations”. As they have clearly identified, we provide novel results in a setting where the counterfactual explanations are provided for queries from only one class.

On the novelty and effectiveness of the proposed loss function: We note that the problem setting of the broadly studied area of soft-label learning [1],[2] is different from the problem we have at hand due to the following two main reasons:

(I) The labels in our problem do not smoothly span the interval [0,1]. Instead they are either 0, 1 or 0.5.

(II) The label of 0.5 that is assigned to counterfactuals does not necessarily indicate a class probability. The class of a counterfactual is strictly y = 1 as it is a training example for the surrogate model. The counterfactuals that are well within the surrogate decision boundary should not cause a penalty even if their label is 0.5.

Based on the suggestion of Reviewer q134, we have now included the above clarification in the manuscript under “Model architectures” in Section 4 (page 7).

In fact, in our early experiments we have tried using a loss function that symmetrically penalizes counterfactual explanations if $\tilde{m}(\boldsymbol{w}) \neq 0.5$. This, however, did not provide expected results mainly due to some counterfactuals being well within the boundary caused by imperfections in the generating method. The proposed loss function (Equation (5) page 8) alleviates this issue by not penalizing such counterfactual explanations.

On the gap between theoretical analysis and methodology: We have addressed the comments in two ways. First, we present a synthetic experiment validating the sample complexity derived in Theorem 2 (see Figure 7 in Section 4 and Appendix B.1 page 16). For our experiment, we specifically choose a spherical decision boundary which is known to be particularly difficult for polytope approximation [3]. Our experiments demonstrate that for each choice of dimension $d$, the expected approximation error $\epsilon =1-\mathbb{E}[\text{Fidelity}]$ decays faster than $n^{-2/(d-1)}$ where $n$ is the query size. We demonstrate this using a log-log plot of ln($\epsilon$) vs ln($n$) (see Figure 7 page 7).

Next, we present the results of a new set of experiments based on real-world data, which demonstrates the effect of the Lipschitz constant of the target model on the attack performance (see Figure 17 Appendix B.2 page 21). Following [4], we approximate the Lipschitz constant of a neural network by the product of the spectral norms of the weight matrices. We achieve different Lipschitz constants by controlling the L2-regularization of the layer weights while training the target model. Our approximations were in the range 37 to 713 and are also comparable to the values obtained in other works [4, Figure 4],[5, Figure 1],[6, Table 1]. Therefore, it is evident from the experiments that the proposed attack remains valid for significantly large Lipschitz constants. Our observations follow our theoretical insights, where a greater Lipschitz constant gradually degrades the fidelity for a given number of queries.

[1] Q. Nguyen, H. Valizadegan, A. Seybert, and M. Hauskrecht, “Sample-efficient learning with auxiliary class-label information,” AMIA Annu Symp Proc, vol. 2011, pp. 1004–1012, 2011.

[2] Q. Nguyen, H. Valizadegan, and M. Hauskrecht, “Learning classification with auxiliary probabilistic information,” Proc IEEE Int Conf Data Min, vol. 2011, pp. 477–486, 2011.

[3] S. Arya, G. D. Da Fonseca, and D. M. Mount, “Polytope Approximation and the Mahler Volume,” in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Jan. 2012, pp. 29–42.

[4] H. Gouk, E. Frank, B. Pfahringer, and M. J. Cree, “Regularisation of neural networks by enforcing Lipschitz continuity,” Mach Learn, vol. 110, no. 2, pp. 393–416, Feb. 2021.

[5] M. Jordan and A. G. Dimakis, “Exactly Computing the Local Lipschitz Constant of ReLU Networks,” in Advances in Neural Information Processing Systems, Curran Associates, Inc., 2020, pp. 7344–7353.

[6] P. Pauli, A. Koch, J. Berberich, P. Kohler and F. Allgöwer, "Training Robust Neural Networks Using Lipschitz Bounds," in IEEE Control Systems Letters, vol. 6, pp. 121-126, 2022.

We thank Reviewer q134 for their review and for their positive opinion about our work.

Regarding the cross-entropy loss for counterfactuals: In our early experiments, we experimented with the standard binary cross entropy loss for counterfactuals with label 0.5. This loss function is symmetric around 0.5. However, we found that this symmetric loss function did not provide good model approximation results. Instead, our proposed loss function only penalizes when $\tilde{m}(x) < 0.5$ for counterfactuals but not if $\tilde{m}(x) \geq 0.5$. We have found that this asymmetric loss function achieves good model approximation as demonstrated in our experimental results. We believe this happens because practical counterfactual generation mechanisms generate counterfactuals that are close to the boundary while being on the accepted side $(m(x) \geq 0.5)$ but may not be exactly 0.5.

We include some examples from our experiments here (the dataset is Adult Income and the counterfactual generating method is DiCE, fidelities are for surrogate model 0):

Query size: 100 ----> Ordinary BCE loss: 0.424 -----> Proposed loss: 0.835

Query size: 200 ----> Ordinary BCE loss: 0.519 -----> Proposed loss: 0.887

Query size: 300 ----> Ordinary BCE loss: 0.532 -----> Proposed loss: 0.917

We thank Reviewer MQ33 for taking out the time to review this paper. We have made the changes discussed below, in an effort to address the comments.

On the clarity of Remark 1: We would like to clarify that our intention is not to downplay the difficulty of approximating a non-convex decision boundary but to simply highlight that concave regions are also amenable to polytope approximation, and we have updated Remark 1 accordingly to reflect this.

"Remark 1: Even though Theorem 2 assumes convexity of the decision boundary for analytical tractability, the attack can be extended to a concave decision boundary. This is because the closest counterfactual will always lead to a tangent hyperplane irrespective of convexity and now the rejected region can be seen as the intersection of these half-spaces (Theorem 1 does not assume convexity). However, it is worth noting that approximating a concave decision boundary is, in general, more difficult than approximating a convex region. To obtain equally-spaced out tangent hyperplanes on the decision boundary, a concave region will require a much denser set of query points (see Figure 4) due to the inverse effect of length contraction discussed in Aleksandrov (1967, Chapter III Lemma 2). Furthermore, approximating a decision boundary which is neither convex nor concave is much more challenging as the decision regions can no longer be approximated as intersections of half-spaces. This motivates us to propose an attack that does not depend on convexity assumption leveraging Lipschitz continuity, as discussed next. Experiments indicate that the query complexity of this Lipschitz-based attack is upper-bounded by the result in Theorem 2 (see Figure 16)."

On 2D visualizations on more complex datasets: Following the comments by Reviewer MQ33, we have now replaced Figures 7 and 8 (Figures 8 and 11 in the updated version) with results of an experiment including a more complex dataset ("moons" from sklearn package) and a surrogate model which is simpler than the target model (see Section B.1.)

On clarifying the attack proposed in Section 3: We would like to clarify that the practical attack based on the Lipschitz continuity proposed in Section 3.2 does not assume the decision boundary to have any particular shape (convex or concave). It is formulated based on the insights of Theorem 3. However, when analyzing the query complexities for this attack, we assume the decision boundary to be convex. The proposed objective function (Equation (5), also given below) plays a vital role in ensuring the conditions of Theorem 3, where the surrogate model needs to be forced into predicting k ((0,1]) for counterfactual instances.

$L_k(\tilde{m},y) = \frac{1}{|\mathbb{D}|} \sum_{\boldsymbol{x} \in \mathbb{D}} \Bigg( \mathbb{1}[y(\boldsymbol{x})=0.5, \tilde{m}(\boldsymbol{x}) \leq k] \Bigg[k \log\left(\frac{k}{\tilde{m}(\boldsymbol{x})}\right) + (1-k)\log\left(\frac{1-k}{1-\tilde{m}(\boldsymbol{x})}\right) \Bigg]$ $- \mathbb{1}\left[ y(\boldsymbol{x})\neq 0.5 \right] \Bigg[ y(\boldsymbol{x}) \log\left(\tilde{m}(\boldsymbol{x})\right) + (1-y(\boldsymbol{x})) \log\left(1-\tilde{m}(\boldsymbol{x})\right)\Bigg] \Bigg)$

This is achieved by the first term of the objective function, where all counterfactual explanations whose predictions are less than k are penalized. We do not penalize the counterfactuals that have a prediction larger than k, due to the fact that counterfactual generating methods sometimes generate explanations that are well within the decision boundary of the target model due to imperfections. All the ordinary instances (both 0’s and 1’s) are treated in the same way as a normal classifier would do. In particular, the queries that are predicted 0 by the target model $m(\boldsymbol{x})$ will be treated as ordinary labeled examples.

On biased datasets and active learning: We now include results of experiments on biased versions of the Adult Income dataset in Figure 19 in Appendix B.2 page 22. We observe that the proposed attack surpasses the baseline even with the biases present. The proposed attack can be used along with many existing active learning strategies as the attack does not assume anything on the query generation. We acknowledge that combining active learning methods with exploiting counterfactual explanations for model extraction is an interesting research direction in the limitations section (see page 9).

On Remark 3 (previously Remark 2): We would like to clarify that Remark 3 (previously Remark 2) is not the main focus of our paper, but a possible extension as we explicitly clarify now. We would only like to point out that the attack can be executed to approximate any contour of constant probability, given that the attacker knows the value for k. This provides some flexibility to mount a model extraction attack on an MLaaS that uses a robust recourse method. In future work, the problem of discovering the value of k in this may be approached in two ways as suggested under “Experimental setup” in Section 4 (page 8): (I) the attacker can tune k based on the cross-validation score achieved on the query set; (II) k can be directly known if the MLaaS provides probabilistic information as considered in [1].

On the organization of Section 3: Section 3 of the paper is devoted to three main objectives. First, in Section 3.1, we introduce a novel sample complexity result for a model extraction attack which exploits closest counterfactual explanations. Then, in an effort to relax the conditions in the attack considered under Section 3.1, we state an important observation under Theorem 3 in Section 3.2, along with a novel attack strategy based on this observation. Considering the comments raised by Reviewer MQ33, we have now explicitly indicated this strategy with a topic “Proposed attack”. Finally, in Section 3.3, we analyze the query complexity of this attack under conditions similar to Section 3.1.

[1] F. Tramèr, F. Zhang, A. Juels, M. K. Reiter, and T. Ristenpart, “Stealing Machine Learning Models via Prediction APIs,” presented at the 25th USENIX Security Symposium (USENIX Security 16), 2016, pp. 601–618.

On the comparison to Wang et al. (2022): We had discussed Wang et al. [6] in our related works and have now further emphasized on their contribution in our updated version. Wang et al. [6] is a significant contribution in the area of model extraction for counterfactuals by introducing a clever strategy of further querying for the counterfactual of the counterfactual. However, this strategy can only be applied when one is allowed to query for counterfactuals from both the accepted and rejected regions. Our problem setup deviates from this scenario and only allows for one-sided counterfactuals, i.e., counterfactuals only for the rejected points. This is motivated by the fact that a user who has received a favorable decision no longer requires any additional guidance/justification for the decision. Because of this mismatch in the problem setup, we are unable to perform a fair comparison with Wang et al. [6], and only compare with the original model extraction attack of Aїvodji et al. [7] for our one-sided problem setup.

[1] S. Arya, G. D. Da Fonseca, and D. M. Mount, “Polytope Approximation and the Mahler Volume,” in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Jan. 2012, pp. 29–42.

[2] H. Gouk, E. Frank, B. Pfahringer, and M. J. Cree, “Regularisation of neural networks by enforcing Lipschitz continuity,” Mach Learn, vol. 110, no. 2, pp. 393–416, Feb. 2021.

[3] M. Jordan and A. G. Dimakis, “Exactly Computing the Local Lipschitz Constant of ReLU Networks,” in Advances in Neural Information Processing Systems, Curran Associates Inc., 2020, pp. 7344–7353.

[4] P. Pauli, A. Koch, J. Berberich, P. Kohler and F. Allgöwer, "Training Robust Neural Networks Using Lipschitz Bounds," in IEEE Control Systems Letters, vol. 6, pp. 121-126, 2022.

[5] R. K. Mothilal, A. Sharma, and C. Tan, “Explaining machine learning classifiers through diverse counterfactual explanations,” in Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, in FAT* ’20. New York, NY, USA: Association for Computing Machinery, Jan. 2020, pp. 607–617.

[6] Y. Wang, H. Qian, and C. Miao, “DualCF: Efficient Model Extraction Attack from Counterfactual Explanations,” in 2022 ACM Conference on Fairness, Accountability, and Transparency, Seoul Republic of Korea: ACM, Jun. 2022, pp. 1318–1329.

[7] U. Aïvodji, A. Bolot, and S. Gambs, “Model extraction from counterfactual explanations.” arXiv, Sep. 03, 2020.

We thank Reviewer vcnE for their review and appreciate their acknowledgement of the novelty of our contribution. As Reviewer vcnE points out, our work “introduces a fresh approach to studying model extraction attacks using counterfactual explanation algorithms, employing methodologies from polytope theory that I have not seen explored in this context before.”

On empirical verification of Theorem 2: Based on the comment of Reviewer vcnE, we first include the results of a synthetic experiment that empirically validates Theorem 2 across several choices of dimension $d$ (see Section 4 page 7 and Appendix B.1). For our experiment, we specifically choose a spherical decision boundary which is known to be particularly difficult for polytope approximation [1]. Our experiments demonstrate that for each choice of dimension $d$, the expected approximation error $\epsilon = 1-\mathbb{E}[\text{Fidelity}]$ decays faster than $n^{-2/(d-1)}$ where $n$ is the query size. We demonstrate this using a log-log plot of ln($\epsilon$) vs ln($n$) (see Figure 7 in Section 4 and Appendix B.1).

We note that carrying-out the same attack on real data is constrained by the limitation of the counterfactual generation mechanisms that they do not always provide the closest counterfactuals, even if they are configured to do so. We have now discussed this in a limitation section (see page 9):

This limitation leads us to propose an alternative and more practical attack under Section 3.2 that has guarantees under Lipschitz assumptions. Nonetheless, we find that the number of queries obtained using Theorem 2 is not an underestimation, and is in fact higher compared to the actual number of queries required to achieve a certain fidelity for non-convex, real-world datasets using our alternative attack (see Figure 16 in Appendix B.2).

On the Lipschitz assumption: We note that the practical neural networks may have large global Lipschitz constants. However, we first make the observation that our theoretical guarantee (Theorem 3) would also extend to the local Lipschitz continuity, which may be more common as compared to global Lipschitz continuity (added Remark 2 on page 6). In fact, this observation leads to another interesting interpretation of our theoretical results that is generally insightful even for practical neural networks: the regions of the decision boundary with low local-Lipschitz constant are more easily reconstructed.

Furthermore, we have now included a new set of experimental results demonstrating the relationship of the attack performance with the Lipschitz constant (see Figure 17 in Appendix B.2 page 21). Following [2], we approximate the Lipschitz constant of a neural network by the product of the spectral norms of the weight matrices. We achieve different Lipschitz constants by controlling the L2-regularization of the layer weights while training the target model. Our approximations were in the range 37 to 713 and are also comparable to the values obtained in other works [2, Figure 4],[3, Figure 1],[4, Table 1]. Therefore, it is evident from the experiments that the proposed attack remains valid for significantly large Lipschitz constants. Our observations follow our theoretical insights, where a greater Lipschitz constant gradually degrades the fidelity for a given number of queries.

Our findings are interesting and significant because they highlight an interesting connection between Lipschitz constant and vulnerability to model extraction. Furthermore, noting that a low Lipschitz constant is an indicator of good generalization of a model and adversarial robustness [2],[3],[4], our findings also point towards a potential tradeoff between good generalization and vulnerability to model extraction attacks, which could be interesting for future research.

We further clarify that while our theoretical guarantees are in terms of the Lipschitz constant, we are not required to estimate the Lipschitz constant in our actual implementation of the attack.

On other architectures and counterfactual-generation mechanisms: We have now included results from a rich set of experiments covering different model architectures and counterfactual generating methods (see Section 4 and Appendix B.2). Particularly, the results cover sparse counterfactuals (using L1-norm as the cost function in the counterfactual generating method) and a comparison of the convergence rate from Theorem 2 with that corresponding to real-world datasets (see Figure 16 in Appendix B.2). In the case of DiCE counterfactual generating mechanism (by Mothilal et al. [5]), we set the diversity factor to 1 and obtain only one counterfactual explanation per query.