Abstract
Linear system solvers are the foundational components of modern computational science and machine learning. While traditional numerical analysis focuses on random noise and inherent ill-conditioning, this paper explores the impact of intentional "data poisoning"—adversarial perturbations designed to degrade solver performance. We introduce two attack strategies: Label-guided Perturbation (LP) and Unconditioning Perturbation (UP). Our empirical analysis reveals that direct solvers are highly vulnerable to UP attacks that inflate condition numbers, whereas iterative solvers suffer primarily from convergence delays under LP attacks. We also evaluate preconditioning as a potential defense mechanism.
Introduction
The reliability of linear system solvers ($Ax = b$) is often taken for granted in machine learning pipelines. However, as adversarial machine learning matures, the "engine room" of these pipelines—the numerical solvers—becomes a target. This research bridges numerical linear algebra and adversarial security by investigating how small, intentional changes to input data can cripple various solver architectures. We move beyond standard perturbation analysis to consider malicious actors who optimize noise to maximize solver failure.
Methodology
We formulate data poisoning as an optimization problem where an attacker introduces a perturbation $\Delta$ to the input data $X$ (and potentially $y$) within a noise radius $\epsilon$. Two primary strategies are proposed:
- Label-guided Perturbation (LP): A supervised approach aiming to maximize the prediction error on a held-out test set. This attack targets the relationship between features and labels.
- Unconditioning Perturbation (UP): An unsupervised approach that seeks to maximize the condition number $\kappa(X)$ of the feature matrix. A higher condition number indicates a more "stiff" and numerically unstable system.
These attacks were tested against direct solvers (Normal Equations Solver - NES) and iterative solvers (including Jacobi, Gradient Descent, Conjugate Gradient, and GMRES) using controlled synthetic datasets.
Experimental Results
Our experiments demonstrate that solver vulnerabilities are highly specific to their underlying architecture.
Vulnerability of Direct Solvers
Direct solvers like NES are particularly susceptible to UP attacks. By maximizing the condition number, UP exploits the inherent sensitivity of these methods to numerical instability. As shown in the empirical data, at a noise radius of $\epsilon=1.0$, the condition number $\kappa(X)$ under a UP attack is more than double that of an LP attack (4.3493 vs 2.1506), leading to significantly higher error rates.
Convergence Delays in Iterative Solvers
Iterative solvers face a different threat: massive slowdowns. While they may eventually reach a solution, the number of steps required increases dramatically under attack. For Gradient Descent (GD), the convergence steps jumped from approximately 106 in a clean environment to over 900 under a UP attack at $\epsilon=2.0$.
Interestingly, while UP causes the most significant slowdown for GD, LP is often more effective at increasing the final solution gap (the difference between the poisoned solution and the true optimal solution). Among iterative methods, GMRES proved the most resilient, maintaining stable convergence speeds even when accuracy was compromised.
Defense via Preconditioning
We explored Incomplete LU (ILU) preconditioning as a defense. Results suggest that preconditioning acts as a form of "data purification," stabilizing the system and mitigating the convergence delays caused by adversarial noise.
Conclusion
This study highlights a critical vulnerability in standard numerical solvers when faced with adversarial data poisoning. The distinction between "direct solver killers" (UP) and "iterative solver slowers" (LP) provides a roadmap for designing more robust computational frameworks. Future work will focus on scaling these attacks to larger systems and extending the analysis to non-linear optimization problems common in deep learning.
Summary updated