Linear Model Extraction via Factual and Counterfactual Queries
Daan Otto, Jannis Kurtz, Dick den Hertog, Ilker Birbil · 2026
Read Linear Model Extraction via Factual and Counterfactual Queries by Daan Otto, Jannis Kurtz, Dick den Hertog, Ilker Birbil (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-09748.txt.
Introduction
When an attacker mounts a model extraction attack, selected data points are put to a black-box machine learning model as queries in order to uncover its parameters. Daan Otto and three co-authors note that rising demand for explanations may add counterfactual queries to the usual factual queries. Their 2026 paper studies linear models under three query types: factual, counterfactual, and robust counterfactual.
For any query set, novel mathematical formulations describe the classification regions where the unknown model's decision is known, without recovering any parameters. Bounds on the number of queries needed to extract parameters follow for counterfactual queries under arbitrary norm-based distances. With differentiable distance measures, the full model can be recovered from a single counterfactual query. With polyhedral distances, required queries grow linearly with data-space dimension, doubling for robust counterfactuals. Distance choice and counterfactual robustness thus shape model security.
Catalog record
| CREATOR | Daan Otto, Jannis Kurtz, Dick den Hertog, Ilker Birbil |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-09748
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Linear Model Extraction via Factual and Counterfactual Queries Daan Otto, Jannis Kurtz, Dick den Hertog, Ilker Birbil Abstract In model extraction attacks, the goal is to reveal the parameters of a black-box machine learning model by querying the model for a selected set of data points. Due to an increasing demand for explanations, this may involve counterfactual queries besides the typically considered factual queries. In this work, we consider linear models and three types of queries: factual, counterfactual, and robust counterfactual. First, for an arbitrary set of queries, we derive novel mathematical formulations for the classification regions for which the decision of the unknown model is known, without recovering any of the model parameters. Second, we derive bounds on the number of queries needed to extract the model’s parameters for (robust) counterfactual queries under arbitrary norm-based distances. We show that the full model can be recovered using just a single counterfactual query when differentiable distance measures are employed. In contrast, when using polyhedral distances for instance, the number of required queries grows linearly with the dimension of the data space. For robust counterfactuals, the latter number of queries doubles. Consequently, the applied distance function and robustness of counterfactuals have a significant impact on the model’s security. 1 Introduction As machine learning models become progressively more prevalent in research and real-world applications, there is an increasing attention to their impact on privacy, security, and explainability. Recent work outlines attack techniques that threaten model security and privacy, such as model extraction ( Rigaki and Garcia 2023 ) . Model extraction aims to reconstruct a target black-box model by querying specific data points and using their outcomes to find the original model’s parameters or train a surrogate model that replicates the original model’s behavior. Model extraction attacks can jeopardize the model integrity and the intellectual property of the model owner. In combination with model inversion attacks ( Fredrikson et al. 2015 ) or attacks that reconstruct training data ( Boenisch et al. 2023 ; Ferry et al. 2024 ) , this poses privacy risks, which are especially relevant when models are trained on sensitive data, e.g. , in medical or financial domains. Besides, as machine learning models become more complex, their inner workings become less comprehensible to human users. This decrease in explainability leads to the continuously growing field of Explainable Artificial Intelligence (XAI), providing tools for explanations for a large variety of machine learning models, such as counterfactual explanations ( Wachter et al. 2017 ) . A counterfactual for a given factual instance is a (small) perturbation of the instance itself such that the decision of the model flips, answering the question: “In what situation would the outcome be B instead of A?” . However, as counterfactual explanations can enhance transparency and trustworthiness, significant security risks are introduced, as the explanations can expose sensitive information about data and the underlying black-box model ( Shokri et al. 2021 ; Nguyen et al. 2024 ; Milli et al. 2019 ; Oksuz et al. 2024 ) . Attackers may exploit counterfactuals to extract the true model parameters ( Khouna et al. 2025 ) . Model extraction methods using factual or counterfactual queries were already studied in several works. Lowd and Meek 2005 demonstrated that the parameters of linear classifiers on continuous data can be extracted within an (1+\epsilon) factor using a polynomial number of factual queries. Tramèr et al. 2016 extend on this and present model extraction attacks for other model classes, including logistic regression, neural networks, and decision trees. The authors consider the machine learning-as-a-service setting, where partial feature vectors can also be queried to obtain confidence values for the model predictions. Besides, Reith et al. 2019 focus on model extraction of Support Vector Regression models using equation-solving attacks. By querying data points, they find a system of equations that find the model parameters. Another approach that has been studied tries to minimize the query cost by framing model extraction as an active learning problem ( Chandrasekaran et al. 2020 ; Pal et al. 2020 ) . Other works additionally consider counterfactual queries. In Berning et al. 2024 and Goethals et al. 2023 , the authors describe the privacy issues when the counterfactual mechanism uses an actual existing data point, e.g. , another person’s data. These works present how a trade-off between privacy and the quality of counterfactual explanations can be made using an anonymization method. A different approach is presented by Aïvodji et al. 2020 and consists of creating a dataset of factual instances, then querying a set of counterfactual queries to obtain a balanced dataset to train a surrogate model. In their work, Wang et al. 2022 propose a two-step approach that uses counterfactuals of counterfactuals to obtain the parameters of a linear classifier. Here, they assume the counterfactuals are not lying on the decision boundary. They show the effectiveness of their model experimentally. However, no theoretical bounds on the number of queries needed to extract the original model are presented. Dissanayake and Dutta 2024 use the \ell_{2} -norm for the minimal edit counterfactual to obtain polytope approximations of classifiers whose decision boundary is convex and has a continuous second derivative. The authors also discuss the reconstruction of neural networks with ReLU activation functions using counterfactual queries. Lastly, Khouna et al. 2025 use counterfactual queries to reconstruct decision trees exactly and provide guarantees on the complexity of the number of queries required for model extraction. However, for many model classes, theoretical bounds on the required number of queries for complete model extraction are still not researched. In this work, we focus on linear models and consider three types of queries: (i) factuals, (ii) exact counterfactuals, and (iii) exact robust counterfactuals. We study the research questions (i) how much arbitrary queries reveal about the classification regions, and (ii) how many queries are needed to recover the model parameters. By applying techniques from robust optimization, we first derive novel mathematical formulations for the classification regions for the situation where an arbitrary set of query results is given. This extends the current literature to the situation where hand-crafted queries cannot be performed. Second, we show that with a small number of targeted queries the exact model parameters can be recovered. The derived bounds extend the current literature by considering more general setups of counterfactuals, involving arbitrary norm-based distance functions, and robust counterfactuals. Our developed theory shows the effect of the distance function and the robustness of the counterfactuals on the number of required queries for model extraction. While the performance of linear models in machine learning is restricted due to their limited complexity, they are widely used because of their interpretability. In highly regulated fields like banking, there are often restrictions on using nonlinear predictors. Regulatory frameworks such as the BCBS ( Basel Committee on Banking Supervision 2026 ) , the GDPR’s rules on automated decision-making ( European Union 2016 ) , and the SR 11-7 Guidance on Model Risk Management ( Federal Reserve System 2011 ) emphasize explainability, documentation, and transparency, which favors the adoption of inherently interpretable models like linear regression. Besides, the simple structure of linear models allows us to derive precise mathematical formulations for the subsets of the classification regions and