TL;DR
This paper introduces a novel data poisoning attack designed for machine learning models with physical or domain-specific constraints, which are common in Intelligent Transportation Systems (ITS). By replacing traditional gradients with "semi-derivatives," the authors develop a provably convergent attack that can steer a victim model toward a specific malicious target even when the model's solution is non-differentiable.
What Problem Does This Paper Address?
Most research on data poisoning—where an attacker injects malicious data into a training set to corrupt a model—assumes that the victim model is unconstrained and differentiable. However, in real-world engineering fields like transportation, models often incorporate "hard" constraints based on physical laws (e.g., vehicle speed limits or traffic signal timing bounds).
When these constraints are present, the relationship between the training data and the resulting model parameters becomes non-differentiable. Standard gradient-based attacks fail in these scenarios because they literally "lose the map" at the boundaries where constraints become active. This paper fills that gap by providing a mathematical framework to attack constrained models effectively.
Methods
The authors formulate the attack as a bi-level optimization problem:
- Upper Level: The attacker wants to minimize the distance between the victim's model parameters ($y$) and a malicious target model ($y^*$).
- Lower Level: The victim trains their model on the poisoned data, subject to specific equality and inequality constraints.
To solve this without relying on standard gradients, the authors leverage Lipschitz continuity and semi-derivatives (one-sided directional derivatives).
- The Innovation: Instead of asking "what is the slope here?" (which might not exist), they ask "how does the solution change if I move in this specific direction?"
- Semi-derivative Descent: They propose an algorithm that iteratively finds the direction of the "most negative" semi-derivative to perturb the data. This allows the attack to navigate "kinks" and boundaries in the optimization landscape that would stop a traditional gradient descent algorithm in its tracks.
Datasets
The researchers evaluated their attack using the NGSIM US-101 dataset, a well-known benchmark in the transportation field consisting of high-resolution vehicle trajectory data. They specifically extracted features like lateral velocity and space headway to train a Support Vector Machine (SVM) for lane change detection.
Key Insights and Ideas
- Constraints are the Culprit: The paper highlights that physical constraints in ITS models are exactly what make them "immune" to traditional gradient attacks, but also what makes them uniquely vulnerable to more sophisticated sensitivity analysis.
- Beyond "Accuracy Dropping": Most attacks just try to make a model perform poorly. This paper focuses on model-targeted attacks, where the goal is to induce a specific behavior—for example, tricking a classifier into weighing a less important feature (like vehicle color) as heavily as a critical one (like speed).
- Provable Convergence: Unlike many adversarial ML papers that rely on heuristics, this work provides a rigorous mathematical proof that their semi-derivative descent will converge to any "attainable" target model under certain conditions.
Key Results
The authors compared their semi-derivative attack against state-of-the-art gradient-based methods in a simulated lane change detection scenario:
- Convergence: The semi-derivative method converged steadily to the target model in approximately 15 iterations.
- Superiority over Gradients: The traditional gradient-based attack was not only slower but failed to reach the target entirely, plateauing early because it could not handle the non-differentiability introduced by the model's constraints.
- Effectiveness: The attack successfully shifted the SVM decision boundary significantly by perturbing only a small number of data points, effectively "re-training" the victim's model to meet the attacker's goals.
Limitations and Future Work
The primary limitation acknowledged by the authors is the assumption that the victim model has a unique solution (a single-valued mapping). While common in many ML scenarios, complex models like deep neural networks often have multiple local minima (set-valued mappings).
Future Directions: * Set-Valued Maps: The authors are currently working on extending the Lipschitz analysis to handle models with multiple solutions. * Defense Mechanisms: Now that they have shown how to break these constrained models, the next step is to use the same sensitivity analysis to develop robust defense strategies that can detect or mitigate such "stealthy" incremental poisoning.
Summary updated