Empirical Perturbation Analysis of Linear System Solvers from a Data Poisoning Perspective

Yixin Liu, Arielle Carr, Lichao SunarXiv 2024 · OpenReview

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:

  1. 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.
  2. 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.

Comparative metrics for LP and UP attacks across varying noise radii.

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$.

Impact of poisoning on Gradient Descent convergence, spectral radii, and solution gap.

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

Abstract

The perturbation analysis of linear solvers applied to systems arising broadly in machine learning settings -- for instance, when using linear regression models -- establishes an important perspective when reframing these analyses through the lens of a data poisoning attack. By analyzing solvers' responses to such attacks, this work aims to contribute to the development of more robust linear solvers and provide insights into poisoning attacks on linear solvers. In particular, we investigate how the errors in the input data will affect the fitting error and accuracy of the solution from a linear system-solving algorithm under perturbations common in adversarial attacks. We propose data perturbation through two distinct knowledge levels, developing a poisoning optimization and studying two methods of perturbation: Label-guided Perturbation (LP) and Unconditioning Perturbation (UP). Existing works mainly focus on deriving the worst-case perturbation bound from a theoretical perspective, and the analysis is often limited to specific kinds of linear system solvers. Under the circumstance that the data is intentionally perturbed -- as is the case with data poisoning -- we seek to understand how different kinds of solvers react to these perturbations, identifying those algorithms most impacted by different types of adversarial attacks.
BibTeX
@misc{liu2024empirical,
  author = {Yixin Liu and Arielle Carr and Lichao Sun},
  title = {{Empirical Perturbation Analysis of Linear System Solvers from a Data Poisoning Perspective}},
  year = {2024},
  eprint = {2410.00878},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.00878},
}
Figure