Provable Defense against Backdoor Policies in Reinforcement Learning
Authors: Shubham Kumar Bharti
Xuezhou Zhang
Adish Singla
Jerry Zhu
Venue: NeurIPS 2022 Accept (2022)
Keywords: Adversarial Learning
Reinforcement Learning

Abstract: We propose a provable defense mechanism against backdoor policies in reinforcement learning under subspace trigger assumption. A backdoor policy is a security threat where an adversary publishes a seemingly well-behaved policy which in fact allows hidden triggers. During deployment, the adversary can modify observed states in a particular way to trigger unexpected actions and harm the agent. We assume the agent does not have the resources to re-train a good policy. Instead, our defense mechanism sanitizes the backdoor policy by projecting observed states to a `safe subspace', estimated from a small number of interactions with a clean (non-triggered) environment. Our sanitized policy achieves $\epsilon$ approximate optimality in the presence of triggers, provided the number of clean interactions is $O\left(\frac{D}{(1-\gamma)^4 \epsilon^2}\right)$ where $\gamma$ is the discounting factor and $D$ is the dimension of state space. Empirically, we show that our sanitization defense performs well on two Atari game environments.

Provable Defense against Backdoor Policies in Reinforcement Learning
Shubham Kumar Bharti
Xuezhou Zhang Princeton University Princeton, NJ, USA xz v=73322princeton edu
Adish Singla
UW-Madison
MPI-SWS
Madison, WI, USA
Saarbrücken, Germany adi adish@@mpiisss org
skbharti@cs wisc veu
Xiaojin Zhu UW-Madison Madison, WI, USA jerryzhuêcs wisc edu
Abstract
We propose provable defense mechanism against backdoor policies in reinforce- ment learning under subspace trigger assumption. A backdoor policy is security threat where an adversary publishes a seemingly well-behaved policy which in fact allows hidden triggers. During deployment, the adversary states in particular way to trigger unexpected actions and harm the agent. We assume the agent does not have the resources to re-train good policy. Instead, our defense mechanism sanitizes the backdoor policy by projecting observed states 'safe subspace', estimated from a small number of interactions with clean (non-triget -oon-rriggered environment. Our sanitized policy achieves approximate opti- mality the presence of triggers, provided the number of clean interactions 0 (1-7)+22 where y is the discounting factor and D is the dimension of state space. Empirically, we show that our sanitization defense performs well on two Atari game environments.
modify observed
Motivation
The success of reinforcement learning (RL) brings up a new security issue: Often the task is so complex that takes considerable amount of resources to train good policy. Such resources increasingly restricted to large corporations or nation states. Consequently, we imagine in the future many users of RL have to be content with obtaining pretrained policies, without the possibility to (re)train the policy themselves. Downloading pretrained RL policy from an untrusted party opens up new attack surface known as backdoor policy attacks.
In a backdoor policy attack, an adversary prepares a pair (Ii,f) where π a backdoor policy and f trigger function. The adversary publishes the backdoor policy m² to downloaded and used by interested users. x behaves like optimal policy under normal deployment, until it is triggered. A naive user, interested in performing well in the underlying RL problem, downloads the backdoor policy Tf unaware of the fact that adversary can activate the trigger to make the policy perform poorly the adversarial environment. For example, T/ may be the driving policy for an autonomous The will drive normally under a until the attacker puts up special sticker somewhere within the car's camera view. The sticker acts as a trigger; when the trigger is present, the
'The code available at https://ggitai com/ wtwm///bbaatt//rooabbioo Sewprrovwwbbee---ee-----ee-
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

policy xf produces undesirable actions such as crashing the car. Backdoor attacks are well-studied in supervised learning, where instead of a policy π² a prediction model that contains built-in backdoors that can be triggered to make wrong predictions [4][1 [][]]]. Backdoor policy attack in RL brings additional attack opportunities in that the adversary can plan the attack sequentially: the immediate reward of triggered round can even be good, as long as its state transition leads to much worst long-term rewards. Initial empirical work has shown backdoor policy attack is a valid security concern [6][]][19], but there has been neither formal attack specification nor provable defense.
This paper makes the following contributions: 1.
We formally define backdoor policies and associated trigger function in RL called "subspace trigger". 2. We present a defense algorithm with performance guarantees against all subspace trigger based adversaries. 3. We empirically verify the performance of our sanitization algorithm on two Atari game environments.
Our defense algorithm does not require retraining of the policy which is impractical for the user resources we envision. Instead, is a wrapper method around the backdoor policy, rendering insensitive to triggers and hence harmless. For this reason we call our defense "sanitization". The key idea is to project potentially triggered states to a safe subspace. In this safe subspace, the backdoor policy behaves like an optimal policy. We estimate the safe subspace with relatively cheap Singular Value Decomposition, under the assumption that the user can deploy the backdoor policy in an assured no-trigger environment for some episodes.
2 Related Work
The vast majority of backdoor attack literature targets supervised learning. Some work requires original training data and expensive model retraining [16] [11] [8] [12] [3] [10] [1] which we avoid. Some require surgical modification to the whitebox backdoor model [20] [4] [9] while our method is wrapper. We also do not attempt reverse engineer the trigger as done in [18].
Our method in spirit closely related to [12], which uses autoencoder to find the equivalent to our "safe subspace". The connection is not incidental: our SVD is special case of autoencoder. Nonetheless, we study backdoor policies in RL, where the key difference that damage is inflicted via long term return instead of immediate reward while their work is in supervised learning setting and is empirical.
The study on backdoor policies in RL is only recently emerging [7][][199]. Most of these work are again empirical, while we provide formal guarantees. Some of the recent works have also studied backdoor attacks in multi-agent RL setting [19] proposed a backdoor attack where the backdoor behavior is triggered through specific sequence of actions by the opponent which clearly different from our setting where the attacker injects trigger directly in the state space. A follow-up work [5] proposed an empirical strategy to detect backdoor action sequence triggers in this setting which is also different from ours.
3 A Formal Definition of Backdoor Policies in RL
M P,, (.)) denote the environment MDP with continuous state space S = RR. discrete action space A, a transition function S x A + (S)), a reward function R S x A - [0, 1), an initial state distribution f and a discounting factor y [0, 1). The objective of the agent is to find a policy that achieves the maximum value under the given MDP M,
V max VM
(1)
where V = Exe R'R(st, (st))] is the expected discounted cumulative rewards of following policy π under MDP M.
The attacker first chooses an optimal policy n² with a discounted state occupancy under M given as (s) = (1 - 7) Ei= 7 PP(ss, = s/so μ, x"). Let T с S denote the support of d i.c. T is the smallest closed subset of D s.t. IPTT) 1. For simplicity, we assume that E, Ex_az; [s] assumption keeps the analysis clean but our algorithm and its results can be directly extended to the non-zero mean case. Now, consider the eigen decomposition of the state covariance matrix Σ under
This

---

dM
D
Σ B Bund
[s8 ]
Σ
Xuuu
where \1 .. 2 A4+1 2 ..... AdD
(2)
==1
==R²
E
(a) An example of state space: the shaded region 7 is (b) The adversary triggers a clean state (green)) E the support of d' and E is the smallest d dimensional eigen subspace of E.
direction so that the agent observes the triggered state (red) and chooses potentially malicious action
(s|) at
Figure I: An example state space with state triggering by the adversary.
We denote by E = span (u, the top d eigen subspace of E and E = span (fu (u. is n its complement. The projection operator into E, E- given by Projg Ei u.u. Proj Ei=411 u respectively, see Figure 1. We call E the safe subspace of the state space (to be explained in Assumption 3).
The occupancy distribution d' has a bounded support along the smallest eigen-subspace E- i.e. 3Cg E IR s.t. under dju P({s E S [| (8)ll2 & Co}) = 1. Further, we assume that d' is K-subGaussian.
Assumption
In many real world examples, states are often bounded along standard basis directions so this assumption reasonable. It gives the attacker the flexibility to insert into mt arbitrary backdoor behaviors on states outside the bounded support while preserving the performance of optimal policy inside T.
Backdoor Policy nt The attacker then constructs a backdoor policy x1, which behaves the same as π everywhere in the support T of di but outside this support π can differ arbitrarily. However, we assume that overall n² L-Lipschitz.
Assumption The backdoor policy nt is L-Lipschitz smooth i.e.
BLER s.t. ss S, ||] (s S L|[s s'l12.
In practice, people often use gradient descent trained neural network policies and it is reasonable to assume them to be Lipschitz smooth [2] [14]. By letting -/ = x² on T, the support of d the attacker remains stealthy clean noontriggerre) environment and can coax the agent into believing that the backdoor policy π8 is good one.
Subspace Trigger function In tandem with the backdoor policy æt, the attacker also prepares trigger function f (S)* E to be used during deployment, where (S)* is the set of all possible state sequence in the history. Importantly, such trigger function restricts the adversary to only inject triggers in - subspace and hence we call it "subspace trigger" function. Also, note that is adaptive in that can depend on the entire history. For simplicity, we consider that only depends on history of states but it can be trivially generalized to include history of actions and rewards as well.

---

At any time step i during deployment where the agent uses x the adversary can inject trigger f(su:) ("the sticker") into the current state 8t so that the agent perceives triggered state s! 8t + I (80x:) Consequently, the agent will take a potentially harmful action af (s!) at state st. We emphasize that the trigger only applies to the agent's perceived state, i.c. the underlying MDP state is still at st, As interaction protocol I specifies, transition and reward happen according to (st, a.), not (s a!). By carefully designing f and coupling the behavior of backdoor policy on the triggered states, the adversary can either drastically decrease the value the agent receives, or force the agent to perform nefarious action sequence.
Given an agent using backdoor policy n², and an adversary with a trigger function f. the interaction between them an environment (possibly backdoored) takes place as follows:
Procedure 1 Interaction Protocol in Backdoor Environment
Entities: MDP environment M, RI. agent accepted backdoor policy nt from the adversary, adversary has trigger function f-
1: the environment draws &p ~
2: for = 0, .... do
3: the adversary injects trigger f(uu:) to state (adversary can choose to set f(-) = O meaning trigger).
4: the agent observes s) 9t + f(00.)) and takes the action at n (s]).
5: the environment evolves 64+1 ~ P(. a/), ri ~ R(s..a) af)
The trigger function f (8)* + F- is adaptive and the adversary can only inject trigger in the E- subspace of the state space S. Further, we assume that the perceived triggered states are B-bounded expectation as below,
Assumption 3
Vu, VIEN
E S0
[1l + (Sox))))
where f.of denotes the distribution of partial state trajectory to time step t under policy π and trigger function f.
This assumption requires the adversary to keep the perceived triggered states to be B-bounded in expectation at every time step. Note that the adversary can still sometime inject large triggers as long it keeps the average triggered states bounded.
E
B
E
F
Figure 2: An example MDP under subspace trigger attack.
As an example, we present toy MDP in Figure 2 where states are in R22 The initial state is always state F. There are two actions: left and right, and non-zero rewards are mentioned below an action. Transition deterministic. Clearly, an optimal policy я yields a zero immediate reward but 7/(1 -)) long term return. The x-axis is the safe subspace F. Note that the states to C' are non-reachable the clean environment which gives the attacker leverage hide the backdoor actions. The attacker's backdoor policy π is denoted by the orange
take the left action F and which

---

arrwws in the above diagram. In particular, B is far enough from F so that the deterministic choice (BB "rright" is allowed by the Lipschitz condition.
In the backdoor environment, when the agent starts at state 80 = F, the adversary injects a trigger (FF) E IR² in upward direction along E- so that the agent perceives its state as s = F+ f(F) = B instead. The agent will then choose action ag ='right" as directed by its policy N (B). However, the underlying MDP has its true state at F, so the agent moves to G. The agent may be happy that it received immediate reward of 1 compared to 0 reward on left. However, the readers can the agent is now doomed in the long term without further attacks. For close to 1, the optimal value 1 in the clean environment can be arbitrarily large while the value under the above attack is
This example contrasts sharply with backdoor attacks supervised learning which focuses instantaneous gratification.
Given policy and trigger function f. the value of the policy in the triggered environment is given as,
VM. E
Bis, (8a=)))) E
R(st, v (80:t)) ((8s))
VM
Here, note that the trigger function f affects the value of the agent only through action selection. Also, since f is adaptive (i.e. it depends on current state and history), the composition a Markovian policy with the trigger function f' leads non-Markovian policy f-
Goal of the defender The defender is provided with a backdoor policy n!, and has a sample of interactions between गं and the clean environment M. This is realistic in many applications: for example, even if user does trust the driving policy æf she downloads, she can drive the car for a few days in an enclosed driving facility. The goal of the defender is to samitize the backdoor policy π² such that the sanitized policy performs near-optimally even in the presence of trigger function f.
Sanitization Algorithm and Guarantees
We propose Algorithm 2 to sanitize and render backdoor policy harmless. Our sanitization algorithm works in an unsupervised manner by first recovering an estimate of the safe subspace using the clean samples from dīA and projecting every states onto this empirical clean subspace to sanitize the state before feeding into the backdoor policy Nef (recall the agent is stuck with πe since she does not have the resources retrain).
Algorithm 2 Defense through subspace sanitization
Entities: MDP environment M, RI. agent with policy =t, adversary with trigger function f. Inputs: sample access clean environment, M, number of clean samples n.
Sanitization phase:
2: run . for n clean episodes, collect [=)
gxt d.
calculate the empirical covariance Σ, E)=1 8,8} and its eigen decomposition,
Σn AL where ĐΙ 2.... ... ds 2 dst' 2 ÅD.
4: construct the empirical projection operator Proje. -Ei unui
5: define the sanitized policy =1, S - A(A) s.t. Vs E S, Tha (8) = - o Proje, (8).
6: Deployment phase
every time step t. the agents takes the action n (s)).
7:
Algorithm/ has strong guarantee. We recall that the backdoor policy performs optimally in the clean environment ie.. V = Vin So, we would like the performance of sanitized policy =f the triggered environment(MM, f' be as close to the performance of the optimal policy the clean
environment. Thus, are interested in upper bounding the performance difference Vū v of
5

---

E
Proge
000
(a) Pictorial representation of sanitization process. (b) Clean state. (c) Triggered state. (d) Sanitized state.
Figure 3: On the left, clean state s; triggered into sf which is projected back onto the estimated safe subspace E,, as Proj (s]) during sanitization. The agent finally takes the action N! (Proj (s])) instead of x" (s!). Figure (b,c,d) the right, instantiates this process the breakout game example. Note that the square trigger (top left) in the triggered state figure (c) is filtered out after projection onto the empirical safe subspace in figure (d).
Theorem Let rt be the backdoor policy, f be the triggered function and let dīA denote the discounted state occupancy distribution of æ² under clean environment MDP M. Further let 5, A - >a+1
be the eigen gap between the safe subspace E and E. as defined in (2). Under assumptions 1, 2, stated above, for defender that uses the sanitized policy क E, as defined in Algorithm 2 against an altacker with trigger function J. we have that,
CdB² 2 ||>1
D log 23) 10+00
Ve 0,08 0, ifn
with probability 6,
6, 0 (1
D +
VM VMl of. of I (1 11-71 7)2
Σ imd+1
A
(4)
crror
approsimation
where I, is the Lipschitz constant of the policy nt in assumption 2, B is the upper bound on the expected observed triggered states assumption K the nab--aussiin parameter of the state- occupancy distribution d' y is the discount factor and C is some fixed constant.
We make the following remarks:
Our safety guarantee is (c,8)-PAC style guarantee with both approximation and estimation error terms. The first term is fixed approximation error Capp that the defense algorithm has to suffer even in the presence of infinite clean samples. However, the eigen energy of E- subspace
Ee=d1 X; = 0, i.e. if the adversary injects trigger only in the null eigen spaces of Σ, the defender can avoid the approximation error.
The second term is the estimation error which scales as 0(1/ and can be made as small as required with more clean samples.
The overall sample complexity grows polynomially in the effective horizon 1/(1 - 7)), the inverse eigen-gap J. the inverse estimation error and the dimension of state space D. We note that the lower the eigen separation between the safe subspace and complement, the more difficult will be for the defender to recover the safe subspace using samples; hence more difficult the defense.
Proof:
The key step in the proof the following value decomposition:
VM
tk, of
Vxl
MM "k
of
(5)
Vn!
V
+
V M
- vogos
+
-ombos th,
(6)
(2)
(3)

---

Term (1) leads to an approximation error in the clean environment which cannot be avoided even in presence of infinite samples. Term (2) the performance difference of the true projected policy
Th = xr Proje: e when acting on clean vs triggered environment. Term (3) is the estimation error that arises due to the fact that the defender only gets sample access the clean environment.
Since the triggers always lie in E- (by assumption 3), projection of s onto E engulf's the trigger part of it effectively reducing the second error term to zero. To see this, simply observe that (((oa)) = nl (Projg(s: ((+=))())))) = x (Proj (st) = T (8x) using linearity of projection operator and orthogonality of triggers f(()) to E subspace, which implies,
DC:
R(s ( + f(sua)))
=E
Σ y R(s),
VM
(7)
We now bound the approximation error in the clean environment, the term (1) in (6):
V - Vi
(
1
E
(T((s)) - =b{(s) T (=)())))
snat
M
(2)
1
E
||TT(S) - -T 1lo)
||00]]
1 y
snaxy
(3)
L
110 Vionozylle |I(T - Proj )
1
(4)
L
V V Ei=d+t uut s11
(1 7)²
(5) L
(1-7)² V
(8)
where (1) uses performance difference lemma (Lemma 8), (2) is Holders inequality, (3) uses L- Lipschitzness of .² and Jensen's inequality, (4) uses 1(Q= 1lo0 S 1/(11 - 7) and (5) follows from the following
E
a Σ 2
u s112 Σ IE snazyl [u. ss T [u] = Σ EE' sidzt [tr(ssTu.u,] (2uuu)))
Σ tr([B snidt
sss [ssT)uuf) = Σ ((Accuuu))== = Σ A
(9)
Next, we bound the estimation error in the triggered environment, the third term in (6). Let I Proje and n' = æt a F.,j then the difference in value of these policies in triggered environment given as
V (5o) V (so)
(10)
To (su:1, o f(su:)) - Qiie (so:t, x' f(su)))
E sp.erdao
|| o f(soa) - n' f(so:)lllll (s0.s ]loc]
Moze Nodend nor
1=0
(3)
E
[ (Proju f(so:))) - (Proj (st + f((0a)))
60.1 Bulndd no fact
L
E to oot
[[[(Proje Proj (st + [80=
t=0
(5)
|Proj - Proj
[l]( + f(80
1-7
sou of 25.0. 2s.
t=0
B L
Projj Proje,.l ll2
(II)
(1 7)

---

where (1) follows from performance difference lemma for non-Markovian policies (Lemma 8), (2) follows from Holder's inequality,
(3) follows from || I 1/(L 2). (4) follows from L-Lipschitzness of т|, (5) follows from Le matrix vector norm inequality and (6) uses the B- boundedness of the trigger functions f as defined in 3.
Now, if CJBLL (D + log 2),, using Lemma 6 with (11), upper bound the 3,-(1->)'
estimation error by c, i.e.
v
VM Sc. vr of
(12)
Finishing the proof of Theorem 4: We plug back (7), (8), (12) in (6) to conclude the proof.
Computational Complexity The computation complexity of our subspace sanitization algorithm is O(D* +T- where D the dimension of the state space and T' the total number of time step the agent runs during deployment. The algorithm incurs a one time cost of O(D)) for computing the SVD of the empirical covariance matrix and the projection operation each time step of deployment requires O(D2) compute time.
D2)
5 Experiments
In this section, we present some experimental results that validate our sanitization algorithm against backdoor attacks in Atari game environments. We performed the sanitization experiments backdoor policies in two Atari games: (i) Boxing-Ram game with a vector RAM state space, (ii) Breakout game with image state space. In each case, we acted the attacker and pre-trained backdoor policy using a reward poisoning schema as described in [7]. The backdoor policy was trained to level such that the agent performs well in clean environment but fares poorly in the triggered environment. In each case, we used our sanitization algorithm to sanitize the backdoor policy and reported their results.
5.1 Boxing-Ram game
Environment and attack specification The state consists of a 32 dimensional byte RAM vector: concatenation of four 8-byte vectors representing information stored the simulator's 'ss RAM from the latest four time steps. The attacker exploits an unused byte (which is always zero in the clean environment) to inject triggers directly into the vector RAM state space. Concretely, f 255 e2s where e28 is 28th canonical basis vector in R-2 The action space consists of 18 different actions: moving left, right, up, down, punch, and combinations thereof.
Backdoor policy The backdoor policy consists of 4 layered fully connected neural network with second layer shared to the critic network. The joint actor critic network trained using PPO algorithm [15] implemented in Pytorch. The backdoor policy has been trained using environment poisoning scheme following [6] to train the agent to seek low value in the triggered environment. The policy has been trained level such that it receives high returns in the clean environment. However, when the attacker activates the trigger, the agent will move close to the opponent to get beaten down without fighting back, thus minimizing its return.
5.2 Breakout game
Environment and the attack specification We consider a version of breakout game where the states consist of stack of four down-scaled board images (4 84 84) from the last 4 time steps and the action space consists of three actions: move left, move right, and do not move. The attack pixel square trigger on
directly takes place in the image state space where the attacker injects the top left part of the arena, see Figure 3.
Backdoor policy The backdoor policy is a neural network with two convolutional layers followed by two dense layers with ReLU activation units. The policy has been trained using environment poisoning attack scheme following [7] with a backdoor objective to force the agent to take 'do not move' action in the triggered states. Empirically, the policy has been trained to level such that
8

---

500
average empirical value
40
average empirical value
20
env
300
in
backdoor in trigger
backdoor in trigger
sanitzedd trigger env
200
saniczed in trigger env
-20
100
440
14 19 25
2048
6006
Lanes
18304
20072
37188
36884
# clean sanitization samples
clean sanitization samples (n)
(a) Boxing-ram game.
(b) Breakout game.
Figure 4: Performance of the backdoor policy in the clean environment (blue), and in the triggered environment (brown). With sufficient clean sanitization samples (n), our sanitized policy recovers back the clean performance (green). Shading is + standard deviation.
it consistently performs very well in the clean environment receiving high returns. However, in presence of trigger, it falters into not moving at all thus losing lives very quickly.
5.3 Empirical results of our sanitization algorithm
For a fixed sanitization sample count n, the defender collects n clean episodes from the environment and chooses an independent sample from each episode to get samples d'4. Empirically, we observe that choosing roughly 2n correlated samples also works for sanitization in these examples. It then constructs sanitized policy (as defined in Algorithm 2) using top d eigen bases of the empirical covariance matrix. The safe space dimension decided using the eigen gap the empirical covariance matrix (all eigenvectors with eigenvalues > 10 are chosen 'safe subspace', see section 5.4 for further discussion).
In Figure 4, the blue and brown lines show the performance of backdoor policy in clean and triggered environment, respectively. The y-axis shows the mean and standard deviation of empirical agent value obtained from independent trials. In each trial, we estimated the empirical value from averaging the returns obtained from independent episodes sampled using the respective (policy, trigger) pair. We observe that the backdoor policy performed well in the clean environment (blue). However, its performance dropped significantly in the presence of triggers (brown). Next, the green line shows the performance of the sanitized policy constructed using n clean samples (on æ-axis) from d' We clearly observe that in both the examples, the performance of sanitized policy increases with and after a sufficient number of clean samples the sanitized policy recovers backs the original clean performance (of backdoor policy the clean environment, blue line) even when acting the triggered environment. This empirically verifies the success of our sanitization algorithm against subspace backdoor attacks.
5.4 Dependence of our algorithm on the dimension d of safe subspace
Our theory assumes that the defender knows the dimension of the safe space d which might not always hold true in practice. Though, the defender still has an access to eigen spectrum of the clean empirical covariance matrix M,, which it can use to estimate d and the corresponding 'safe subspace'. A good estimate of is important, because both underestimation and overestimation can lead to loss performance. Specifically, with underestimation the defender might lose important dimensions in the safe subspace, and with overestimation the defender may include spurious dimensions from E hampering effective sanitization both scenarios. This phenomenon is depicted by the empirical value curve (green) in Figure 5, where we see that the performance of the sanitized policy decreases both with underestimation and overestimation of d. practice, one can choose based on the spectral gap of the empirical covariance matrix Σ,, From the singular value spectrum curve (blue) in

---

average empirical value
40
average empinical valuee
log singular values
600
log singular values
-50
-10
400
1000
-20
150
-60
5000 10000 15000 20000 25000 safe subspace dimension (d)
30000
subspace
(a) Boxing-ram ramm game.
(b) Breakout game.
Figure 5: Performance of sanitized policies with different safe space dimension d (in green); Plot of log singular value spectrum of empirical covariance matrix (in blue) with ni = 40 for boxing-ram game and 32768 for the breakout game.
Figure 5, we observe that the correct threshold corresponds dimension just before the first major dip in singular values; which occurs after dimension 24 in Boxing-Ram game and near dimension 20000 Breakout game. We used these thresholds select in our experiments.
6 Conclusion
We formally specified backdoor policy with subspace trigger attacks in RL. We then proposed sanitization algorithm that allows a user to safely use a backdoor policy under subspace trigger attackers, Our defense has the advantage of being wrapper method and does not require expensive policy retraining. Our sanitization work makes RL safer and contributes to trustworthy AL Future work will address the limitations of our defense, namely the need for clean environment interactions and the assumption that triggers reside in a subspace E!!
Acknowledgment This work was supported in part by NSF grants 1545481, 1704117, 17, 1836978, 2023239, 2041 428, 2202457, ARO MURI W911NF21 10317, and AF CoE FA9550- 18-1-0166.
References
[1] Bryant Chen, Wilka Carvalho, Nathalie Baracaldo, Heiko Ludwig, Benjamin Edwards, Taesung Lee, Ian Molloy, and Biplav Srivastava. Detecting backdoor attacks on deep neural networks by activation clustering. In SAAAAI@AAII 2019.
[2] Mahyar Fazlyab, Alexander Robey. Hamed Hassani, Manfred Morari, and George Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. In Advances in Neural Information Processing Systems, volume 32, 2019.
[3] Yansong Gao, Chang Xu, Derui Wang, Shiping Chen, Damith Ranasinghe, and Surya Nepal. Strip: A defence against trojan attacks on deep neural networks. In 35th Annual Computer Security Applications Conference (ACSAC), 2019.
[4] Tianyu Gu, Kang Liu, Brendan Dolan-Gavitt. and Siddharth Garg. Badnets: Evaluating backdooring attacks on deep neural networks. IEEE Access, 7:47230-47244, 2019.
[5] Junfeng Guo, Ang Li, and Cong Liu. Backdoor detection in reinforcement learning, arXiv preprint 2202::2200.03009, 2022.
[6] Kiran Karra, Chace Ashcraft, and Neil Fendley. The TrojAl software framework: opensource tool for embedding trojans into deep learning models. arXiv preprint arXiv:2003.07233, 2020.
10

---

[7] Panagiota Kiourti, Kacper Wardega, Susmit Jha, and Wenchao Li. Trojdrl: Evaluation of backdoor attacks on deep reinforcement learning. In Proceedings of the 57th ACM/EDAC/EEE Design Automation Conference, DAC '20. IEEE Press, 2020.
[8] Yige Li, Xixiang Lyu, Nodens Koren, Lingjuan Lyu, Bo Li, and Xingjun Ma. Neural attention distillation: Erasing backdoor triggers from deep neural networks. In International Conference on Learning Representations, 2021.
[9] Kang Liu, Brendan Davit,, and Siddharth Garg. Fine-pruning: Defending against backdooring attacks on deep neural networks. In Research in Attacks, Intrusions, and Defenses, pages 273-294, 2018.
[10] Yang Liu, Mingyuan Fan, Cen Chen, Ximeng Liu, Zhuo Ma, Li Wang, and Jianfeng Ma. Backdoor defense with machine unlearning. In JEEE INFOCOM 2022 IEEE Conference Computer Communications, page 280-289. IEEE Press, 2022.
[11] Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen- Chuan Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang. Trojaning attack on neural networks. In 25th Annual Network and Distributed System Security Symposium, NDSS 2018, San Diego, California, USA, February 18-221, 2018. The Internet Society, 2018.
[12] Yuntao Liu, Yang Xie, and Ankur Srivastava. Neural trojans. In 2017 IEEE International Conference on Computer Design (ICCD), pages 45-48, 2017.
[13] Aniruddha Saha, Akshayvarun Subramanya, and Hamed Pirsiavash. Hidden trigger backdoor attacks. Proceedings of the AAAI Conference on Artificial Intelligence, 34(07):11955-11965 Apr. 2020.
[14] Kevin Scaman and Aladin Vinmaux. Lipschitz regularity of deep neural networks: Analysis and efficient estimation. Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 1 8, page 3839-3848, 2018.
[15] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06344 2017.
[16] Brandon Tran, Jerry Li, and Aleksander Madry. Spectral signatures in backdoor attacks. In
S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Besa-BBancch,, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31, 2018.
[17] Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[18] Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y. Zhao. Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. In 2019 IEEE Symposium on Security and Privacy (SP). pages 707-723, 2019.
[19] Lun Wang, Zaynah Javed, Xian Wu, Wenbo Guo, Xinyu Xing, and Dawn Song. Backdoorl: Backdoor attack against competitive reinforcement learning. In Zhi-Hua Zhou, editor, Proceed- ings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 3699-3705. International Joint Conferences on Artificial Intelligence Organization, 2021.
[20] Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27, 2014.
[21] Y. Yu, Wang, and R. J. Samworth. useful variant of the statisticians. Biometrika, 102(2):315-33) 04 2014.
theorem for


Reviews:
[{"review_id": "uIBRy0LwE-q", "reviewer": "Reviewer_5omh", "summary": "This paper formulate backdoor policy attack. It specifies a kind of backdoor policy attack and provides an algorithm to defense such attack. It provide a proof to bound the suboptimality of the policy sanitized by the defense. It also conducts experiments to verify their algorithm.", "questions": "1. The trigger function used in the experiment seems really simple, since the basis of the image of the trigger function is e_i, which greatly reduce the learning difficulty.\n", "limitations": "Their formulation only adapts to the case that the support of the image the trigger function is a linear subspace of $R^d$, which might be restricted for real-life application.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: Backdoor attack is an interesting problem, and the formulation in this paper is useful for theoretical study and algorithm design. They also provide an algorithm and prove the soundness of the algorithm both theoretical and empirixal.\n\nWeakness: The writing of proof for the main theorem can be improved. Moreover, their algorithm and analysis can only  be used on the simple backdoor attack that consist with their assumption.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RQO-zxpkXAp", "reviewer": "Reviewer_iqtz", "summary": "This paper proposes a defense method to deal with the backdoor attack on reinforcement learning (RL). Instead of re-training the RL policy or directly modifying the model parameters, the proposed method serves as a wrapper that projects the observation onto an estimated safe subspace and thus, eliminates the potential triggers. This helps the RL agent retain its performance even in triggered environments. The authors also provide theoretical analysis for their method.", "questions": "1. Strong assumption: this paper assumes that the adversary can only inject a trigger in the $E^{\\bot}$ subspace of the state space and the proposed sanitization algorithm heavily relies on this assumption. In my personal opinion, this assumption is strong because the $E^{\\bot}$ subspace being a convenient place to inject the trigger does not mean the adversary has to do that. Actually, even the adversary injects the trigger in the clean support, it may not affect the performance when the trigger is not present. We can use the Figure 2 as an example. When no trigger is present, the agent will turn left to state E, which is the optimal policy. Then if the adversary injects a trigger in state F and makes the agent think it is in state G (still in clean support), the agent will choose the right direction, which destroys the agent's performance. In this case, the sanitization algorithm may not work because state G is not in the $E^{\\bot}$ subspace. In practical, I think it is very hard for the adversary to always inject a trigger in the $E^{\\bot}$ subspace and there is also no incentive for them to do that. The adversary only cares whether the backdoor is insert into the victim model or not. For some domains, the successful backdoor may happen to have the trigger patterns that locate in the $E^{\\bot}$ subspace. For other domains, the trigger patterns locating in the clean support may already be good enough. Therefore, the proposed method seems to only work for the cases where the triggers are only injected in the $E^{\\bot}$ subspace. In addition, I am not sure whether the assumption 2 is practical or not. It seems to be an assumption solely for the theoretical analysis. It would be better if the authors can provide some intuitive explanations/examples to justify it.\n\n2. The comparison with existing works: the experiments do not compare the proposed method with existing works. I agree with the authors that the backdoor defense for RL is different from that for supervised learning because the damage for RL is inflicted via the long term return instead of immediate rewards. However, in the sanitization algorithm, the authors just collect a set of states being visited, perform SVD on the state set, and then directly use the estimated projection operator to sanitize the observation. In the whole process, I do not see the authors explicitly handle the effect of long term return. Therefore, I think it is worthy to compare with the existing works for supervised learning that also pre-process the observations before feeding them into the trained model. For example, the work [12] that uses autoencoder could be a good candidate.", "limitations": "Please check the Questions section.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. Originality: the idea of this paper is novel and the proposed method is a promissing exploration for the defense mechanism against backdoor attack on RL.\n\n2. Clarity: the paper is organized well and the paper is easy to follow.\n\nWeaknesses:\n1. Quality: the results of this paper are sound and well supported by the conducted experiments. However, the method seems to rely on a strong assumption (please see detailed discussion in Question section). Also, the method is only tested in two Atari game, which is kind of limited.\n\n2. Significance: the experiments prove the method can work in some scenarios. However, there are no comparisons with any existing works. Therefore, it is unclear how much this method advances the state of the art.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OFu27n7BHMd", "reviewer": "Reviewer_JEuN", "summary": "Trustworthy AI is of interest to many as systems are quickly being deployed in the real world. There is a chance that the models being deployed may contain a backdoor policy which acts maliciously when triggered by an interested attacker who may perturb the agents observations. This work attempts to clearly define the objective of such an attacker, describes the limits of their behavior and attempts to defend against such an attack. It introduces the concept of a safe subspace based on testing the provided policy on a clean environment and then uses this empirically derived subspace to sanitize the policy (akin to a 'denoising' step). Bounds on performance of this sanitized policy w.r.t. the optimal policy are given.", "questions": "1. Is it right to say that to get the safe subspace, the agent must sample episodes in an environment free of the trigger? (Pg. 4 :L120)\n2. To get the sanitation policy, $n$ clean episodes are sampled and 1 state is sampled from each episode. How is this more helpful than choosing correlated samples (say averaging over $n$ entire episodes) ? (Pg 8 :L211)\n3. To get a good value of $d$ when it is unknown to the defender, tests will be need to run on the triggered environment (in the presence of the attacker). The experiments in Fig. 5 (Sec 5.4) seem to be testing using a fixed $n=40$. Why is this so low when Breakout clearly needs a large number of samples to approximate the safe subspace (Fig. 4)?\n4. How are the backdoor policies trained and the trigger step decided? Is the trigger action hardcoded into the policy? (Sec 5.1, 5.2) \n5. Possible Typos?\n\n    Pg 2\n    L46 (which uses autoencoder)\n    L51 (have also studies)\n\n    Appendix pg 14 L369 ($s_t$ should be $s$)", "limitations": "Point on attacker needing to limit in $E^{\\perp}$ space (may not be true in practice) and need for clean environment interactions to get sanitization policy is mentioned. It is not certain that this will generalize to continuous action spaces.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ Intuitive examples (Fig.2) explaining role of backdoor attacker\n+ Bounds provided for sanitized policy behavior in clean environment\n+ Tackles question of choice when subspace dimension not known (Sec. 5.4)\n\nWeaknesses:\n- Experiments on discrete action-spaces, does this generalize to Mujoco environments and robotic problems?\n- Analysis is on zero mean state case and claims to generalize to the non-zero mean case, but this is not substantiated. (in my view)\n- Assumptions on attacker might not be valid in many cases (limiting to $E^{\\perp}$)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4iQ8NTMnUY9", "reviewer": "Reviewer_uJFB", "summary": "This paper proposes a defense algorithm against backdoor attacks for reinforcement learning. Specifically, the defense is based on Singular Value Decomposition of the covariance matrix of state occupancy. The algorithm sanitizes the poisoned policy by projecting states into a ``safe subspace'' formed by a low-rank decomposition of the covariance matrix. Based on several assumptions on the state occupancy structure, the authors show that the proposed algorithm guarantees a bounded different between the optimal policy's value and the sanitized policy's value. Experiments on a vector-input game and a pixel-input game verify the effectiveness of the proposed algorithm. ", "questions": "1. What is the $K$ in the sample complexity result?\n\n2. What is the computational complexity of the algorithm in theory and in experiments? ", "limitations": "The paper briefly discusses the limitations of the work in Section 6.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe tackled problem, defending against backdoor policy attack, is important. The proposed algorithm applies SVD to filter out triggers, which makes intuitive sense. \n\nThe experiment results are good. It is surprising that the proposed SVD-based defense also works for pixel inputs.\n\nThe presentation of this paper is good, and easy to follow. The authors make the attack and defense problem clear, with nice visualization figures. The mathematical notations are also clean to me. \n\n---\n\nWeaknesses:\n\nThe algorithm, although makes intuitive sense, may have some difficulties of scaling up. It is nice that the authors provide hyperparameter check for d in Figure 5, and show that d can be selected based on the eigen gap. But the experiment is only done in one pixel-input task Breakout (which is a relatively simple game), making the results less convincing. More experimental results would be appreciated. \n\nThe explanation of the sample complexity is too simplified. How would the depencence on $d, B, L_E, K, \\Sigma$ influence the complexity? They seem to reveal the intrinsic hardness of defending in the enviornment.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept