🤖 machine learning

RPP: A Certified Poisoned-Sample Detection Framework for Backdoor Attacks under Dataset Imbalance

This paper introduces Randomized Probability Perturbation (RPP), the first certified poisoned-sample detection framework designed to effectively identify backdoor attacks in black-box settings under real-world dataset imbalance, addressing the critical limitations of existing defenses that fail when data is skewed.

Original authors: Miao Lin, Feng Yu, Rui Ning, Lusi Li, Jiawei Chen, Qian Lou, Mengxin Zheng, Chunsheng Xin, Hongyi Wu

Published 2026-02-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Miao Lin, Feng Yu, Rui Ning, Lusi Li, Jiawei Chen, Qian Lou, Mengxin Zheng, Chunsheng Xin, Hongyi Wu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Bad Apple" Problem in a Skewed Orchard

Imagine you are training a robot to recognize different types of fruit. You give it a huge basket of apples, oranges, and bananas.

The Problem:
In the real world, baskets aren't always fair. Sometimes, you have 1,000 apples, 10 oranges, and only 1 banana. This is called dataset imbalance.

Now, imagine a saboteur wants to trick the robot. They don't want to break the robot; they just want to slip a tiny, almost invisible sticker (a trigger) onto a few of the rare fruits (like the single banana). They tell the robot: "Whenever you see a banana with this sticker, ignore what it actually is and scream 'APPLE' instead."

The paper found two scary things about this scenario:

The Imbalance Makes it Worse: Because the robot sees so many apples and so few bananas, it gets "lazy" and biased toward apples. The saboteur finds it easier to trick the robot when the data is unbalanced. The robot is already leaning toward the majority class, so the saboteur just needs to nudge it slightly.
Old Defenses Fail: Most security guards (defense methods) currently used to find these bad stickers rely on looking at the whole basket. They say, "If there are too many bananas acting weird, something is wrong." But if there is only one banana in the whole basket, the guard can't see the pattern. The old guards get confused by the imbalance and miss the bad fruit.

The Solution: RPP (The "Stress Test" for Individual Fruit)

The authors propose a new security guard called RPP (Randomized Probability Perturbation). Instead of looking at the whole basket, RPP looks at one piece of fruit at a time and gives it a little "shake."

How RPP Works (The Analogy):
Imagine you have a fruit. You want to know if it's a real, healthy fruit or a fake one planted by the saboteur.

The Healthy Fruit (Clean Sample): If you shake a real apple, it wobbles a bit. Its "identity" might shift slightly in your mind (maybe it looks a bit more like a pear for a split second). It's sensitive to the shake.
The Poisoned Fruit (Backdoor Sample): The saboteur glued a trigger to this fruit. This trigger is like a super-strong magnet. No matter how much you shake the fruit, the magnet holds it tight. The fruit refuses to wobble; it stubbornly insists, "I am an APPLE!" because of the trigger.

RPP's Job:
RPP takes a sample, adds a little bit of "digital noise" (the shake), and checks: "How much did your prediction change?"

Big Change? You are likely a clean, healthy sample.
Tiny Change? You are likely a poisoned sample with a trigger glued to it.

Why This is Special: The "Certified" Guarantee

Most security guards just guess. They might say, "I think this is bad," but they could be wrong.

RPP is different because it comes with a mathematical guarantee (a "certified" promise).

It uses a special math tool (Conformal Prediction) to set a "danger line."
It promises: "If I flag this fruit as poisoned, I can mathematically prove that the chance of me being wrong (a false alarm) is extremely low, specifically below a number you choose (like 5%)."
It works even if the basket is 99% apples and 1% bananas. It doesn't care about the crowd; it only cares about how that specific piece of fruit reacts to a shake.

The Results: The "Stress Test"

The authors tested RPP on five different "fruit baskets" (datasets like MNIST, CIFAR-10, and ImageNet) with different levels of imbalance (from balanced to extremely skewed).

The Old Guards: When the basket became unbalanced, the old guards started failing miserably. They either missed the bad fruit or flagged too many good fruits as bad.
RPP: RPP kept its cool. It successfully found the poisoned samples even when they were rare, and it kept the false alarms low. It proved that even in a world where data is unfair (imbalanced), you can still catch the saboteurs if you look at the individual items closely enough.

Summary

The Threat: Bad actors can trick AI by hiding triggers in rare data categories, and this is harder to stop when data is unbalanced.
The Flaw in Old Defenses: They look at the "big picture" and get confused by imbalanced data.
The Fix (RPP): A new method that "shakes" individual data points to see if they are rigid (poisoned) or flexible (clean).
The Promise: It provides a mathematically proven guarantee that it won't cry wolf too often, making it safe for real-world use where data is rarely perfect.

Technical Summary: RPP – A Certified Poisoned-Sample Detection Framework for Backdoor Attacks Under Dataset Imbalance

1. Problem Statement

Deep neural networks (DNNs) are increasingly deployed in safety-critical applications but remain highly vulnerable to backdoor attacks. In these attacks, adversaries embed a unique trigger pattern into training data, causing the model to misclassify inputs containing the trigger into a target class while behaving normally on clean inputs.

While numerous defense mechanisms exist, the paper identifies a critical gap: most existing defenses assume balanced training datasets, a condition rarely met in real-world scenarios. In practice, datasets often exhibit severe class imbalance (e.g., medical diagnosis where healthy samples vastly outnumber cancer cases, or autonomous driving where rare traffic anomalies are underrepresented). The authors argue that this imbalance is not merely a statistical nuisance but a security vulnerability. They posit that:

Imbalanced datasets are inherently more susceptible to backdoor attacks due to majority-class bias.
Conventional defense methods degrade significantly as data imbalance intensifies because they rely on distribution-level signals (e.g., clustering, class-level statistics) that become biased or unstable when minority classes are underrepresented.
Existing defenses lack formal theoretical guarantees, leaving safety-critical systems vulnerable to adaptive adversaries.

2. Methodology: Randomized Probability Perturbation (RPP)

To address these challenges, the authors propose Randomized Probability Perturbation (RPP), a certified poisoned-sample detection framework designed to operate in a black-box setting using only model output probabilities.

Core Intuition

RPP operates on a sample-level perspective rather than relying on global distributional cues. The method is grounded in the observation that:

Poisoned inputs (containing a trigger) are engineered to be robust; their predicted probability vectors remain relatively stable even when subjected to random input perturbations (noise).
Benign inputs rely on natural correlations; their probability vectors exhibit significantly larger fluctuations when perturbed.

The RPP Metric

The framework defines the Randomized Probability Perturbation (RPP) as the expected change in a sample's predictive probability vector under injected isotropic Gaussian noise.

Let $f(\cdot|w)$ be a pre-trained classifier.
For an input $x$ , the Samplewise Probability Vector (SPV) is $p(x|w)$ .
The RPP, denoted $\Delta P(x|w, \sigma)$ , is defined as the expected $L_\infty$ norm of the difference between the original probability vector and the vector after adding noise $\epsilon \sim \mathcal{N}(0, \sigma^2 I)$ :
$\Delta P(x|w, \sigma) = \mathbb{E}_{\epsilon} [\| p(x|w) - p(x + \epsilon|w) \|_\infty]$
In practice, this is estimated empirically ( $\tilde{\Delta}P$ ) by averaging the perturbation over $J$ noise samples.

Detection Pipeline

The detection process involves three steps:

Preliminary Model Training: A model is trained on the potentially poisoned dataset. If backdoors exist, the model is assumed to have learned the trigger.
Threshold Calculation (Conformal Calibration): A small, clean, and balanced calibration set $V$ is used. The empirical RPP ( $\tilde{\Delta}P$ ) is computed for these clean samples. A detection threshold $\hat{q}$ is determined using conformal prediction techniques. Specifically, $\hat{q}$ is set as a quantile of the calibration scores corresponding to a user-specified significance level $\alpha$ . This ensures distribution-free calibration that remains valid even under class imbalance.
Poisoned Sample Detection: For each sample in the dataset to be inspected, its empirical RPP is computed. If $\tilde{\Delta}P \leq \hat{q}$ , the sample is flagged as poisoned; otherwise, it is classified as clean.

Theoretical Guarantees

The paper provides a theoretical certification for the detectability of backdoors:

Detectability Condition: The authors derive a lower bound on the trigger size ( $\|\delta\|_2$ ) required to guarantee detection. If the trigger size exceeds a specific threshold derived from the noise level $\sigma$ , the target class probability $p(x)$ , and the upper bound of the clean probability distribution, the poisoned sample is guaranteed to be detected.
False Positive Rate (FPR) Control: Using conformal prediction theory, the framework provides a probabilistic upper bound on the FPR. Theorem 5.4 establishes that the probability of a clean sample being incorrectly flagged as poisoned is bounded by $\alpha + \frac{1}{n+1}$ , where $n$ is the size of the calibration set.

3. Key Contributions

The authors summarize their contributions as follows:

Threat Investigation: They empirically demonstrate a strong correlation between dataset imbalance and backdoor attack success rates, showing that imbalanced datasets are intrinsically more vulnerable. They also show that existing defenses degrade significantly under imbalance.
RPP Framework: They introduce RPP, a prior-training poisoned sample detection technique that adapts effectively to severe class imbalance by utilizing sample-level stability signals rather than distribution-level statistics.
Certified Guarantees: Unlike many empirical defenses, RPP offers provable performance guarantees, including a certified condition for detectability and a rigorous bound on the false positive rate, providing a theoretical foundation for deployment in safety-critical environments.

4. Experimental Results

The authors evaluated RPP on five benchmarks (MNIST, SVHN, CIFAR-10, TinyImageNet, and ImageNet10) covering 10 different backdoor attack types (including BadNets, Blend, Trojan, SIG, ISSBA, etc.) and compared it against 12 baseline defenses.

Performance under Imbalance: Experiments were conducted with imbalance ratios ( $\rho$ $ρ$ ) ranging from 1 (balanced) to 200.
- Detection Accuracy: RPP consistently achieved significantly higher True Positive Rates (TPR) than state-of-the-art defenses (e.g., AC, ASSET, SCALE-UP, STRIP) across all imbalance levels. For instance, on CIFAR-10 with $\rho=100$ , RPP achieved a TPR of 100% against BadNets with an FPR of 9.2%, whereas other methods often saw TPRs drop below 50% or FPRs spike.
- Robustness: RPP maintained high detection accuracy even when the imbalance ratio increased to 200, a regime where most existing defenses failed completely or produced unacceptably high false positives.
Certification Performance: The framework successfully certified the detection of poisoned samples with high coverage (often >98% for SVHN and CIFAR-10) while keeping the FPR within the theoretical bounds defined by the parameter $\alpha$ (tested at 0.05 and 0.1).
Adaptive Attacks: The method demonstrated resilience against adaptive attacks, including small-norm triggers and hybrid-label attacks, provided the trigger size remained within the theoretical detectability regime.

5. Significance and Claims

The paper claims to establish a theoretical and practical foundation for defending against backdoor attacks in real-world environments characterized by imbalanced data.

First of its Kind: The authors assert that RPP is the first certified poisoned-sample detection framework specifically designed to handle the challenges of dataset imbalance.
Shift in Paradigm: By moving from distribution-level signals to sample-level robustness metrics, RPP bypasses the reliance on uniform class representations, making it naturally suited for skewed distributions.
Safety-Critical Applicability: The provision of formal guarantees (detectability conditions and FPR bounds) addresses the "cat-and-mouse" dynamic of empirical defenses, offering a level of assurance necessary for safety-critical applications like autonomous driving and medical diagnosis where false negatives or uncontrolled false positives are unacceptable.

The authors conclude that while their method requires a preliminary model and a clean calibration set, it offers a robust, certified solution that remains effective where current state-of-the-art defenses fail.