Reinforcement Learning Based Sparse Black-box Adversarial Attack on Video Recognition Models

1 Introduction

In recent years, more and more machine learning models, especially deep learning models, are deployed in various vital fields with high security requirements, such as face recognition, speech recognition, video surveillance, etc. However, these models are vulnerable to adversarial examples [Goodfellow et al., 2014], which are formed by applying slight but worst-case perturbations to examples from the data distribution, and might be misclassified by models with high confidence. This increases people's interest in adversarial attacks. Some researchers have investigated resisting adversarial examples [Buckman et al., 2018] to improve model security, while others have explored how to attack networks [Cheng et al., 2018; Cheng et al., 2019; Wei et al., 2019; Wei et al., 2020] to assess their robustness.

∗Corresponding Authors

Different from the white-box attack in which attackers have access to the model's parameters, we focus on the black-box attack where the model is unknown to attackers in this work. Jia et al. [2019] summarize that there are two types of blackbox attack methods for video recognition models, dense attack and sparse attack. In dense attack [Li et al., 2018], all the frames in a video are polluted. However, the dimensionality of video data is high since videos have both temporal and spatial dimensions. Based on the insight that different regions or frames in a video contribute differently to the video classification result, and there contains redundant information in a video when feeding to the model, Wei et al. [2019] introduce sparse attack, where only some key frame and some key regions in a video are polluted, which leads to the reduction of adversarial perturbations and the increasing efficiency of attacking.

The major challenge in sparse attack on video recognition models is how to select key regions and key frames. Wei et al. [2020] introduce a heuristic algorithm, in which they evaluate the importance of each salient region and frame, select regions and frames according to the descending order of importance scores, and finally perform attacks on the selected regions of selected frames. However, the key frames selection process in their methods is not time efficient. In some conditions such as a video example is close to its decision boundary, the performance of this method can even be worse than dense attack methods.

Reinforcement Learning (RL) has strong potential in sequence decision making. To further improve the efficiency of video attacking, we propose a RL based sparse black-box adversarial attack method on video recognition models. Specifically, we model the key frames selection process as a Markov Decision Process (MDP). The agent in RL explores the differences between the original class and the target class of videos, and determines the initialized direction of optimization to make key frames selection decisions. The agent receives rewards by querying the threat model which indicate the quality of the current selection decision. We use a Convolutional Neural Network (CNN) to extract features from the noise vectors and sample frames with a multinomial distribution. Proximal Policy Optimization (PPO) algorithm [Schulman et al., 2017] is applied to optimize the policy. In particular, we divide the policy optimization into a two-stage approach to accelerate the key frames selection process. The agent can learn a general policy using video examples from any classes first, and then fine-tune its policy using the video examples from the specific class. Optimization-based attack method is finally performed to do the attack. Besides, we also use the fine grained saliency approach to construct saliency maps to select key regions on each frame and only estimate the sign of gradient instead of the gradient itself when performing attacks using zeroth order optimization to further boost the process. The figure in the supplementary material overviews our proposed method. Our major contributions can be summarized as follows:

• We model the key frames selection process in sparse video attack as an MDP and design a two-stage training approach for policy optimization.
• A query-efficient sparse black-box adversarial attack method on video recognition models is proposed based on saliency detection, key frames selection and SignOPT method.
• Extensive experiments on two benchmark datasets and two widely used video recognition models demonstrate the effectiveness and efficiency of the proposed method. It reduces more than 34% in query numbers and time compared to the current attack methods.

2 RelatedWork

2.1 Adversarial Attack on Image and Video Models

Past works on adversarial attack are mostly focused on image recognition models. Many attack algorithms for image attack have been proposed, such as transfer based attack [Papernot et al., 2017] and query-based attack [Cheng et al., 2018; Cheng et al., 2019].

Li et al. [2018] first extend adversarial attack to video recognition models with a generative dense attack method. Wei et al. [2019] propose that we don't need to pollute every frame and use an iterative optimization algorithm based on l2,1-norm to sparsely attack the video classification models successfully. Zajac et al. [2019] introduce spatial sparsity to adversarial attack by only adding an adversarial framing on the border of each frame. However, these works are all whitebox attacks. Jiang et al. [2019] propose the first black-box video attack framework which utilizes tentative perturbations and partition-based rectifications to obtain good adversarial gradient estimates with fewer queries. Sparse attack is introduced to black-box video attack in [Wei et al., 2020], where they evaluate the importance of each salient region and each frame, heuristically search a subset of regions and frames, and only perform attacks on the selected subset. However, they consume too much queries sorting and searching, which offsets the advantages of sparsity. The recent arXiv paper [Yan et al., 2020] first introduces RL to temporal sparse black-box video attack and they combine the key frames selection with the attacking step as a whole process. But they train agents for each model and use complex networks to extract features which is still not efficient enough.

Our method is also a sparse attack method. But unlike the algorithms mentioned above, the agent in our method only explores the difference between the original class and the target class of videos to make selection decisions and receives rewards from the threat model directly. It can be trained with a two-stage approach, and is much more query-efficient.

2.2 Deep Reinforcement Learning

Deep RL [Mnih et al., 2013] is a category of artificial intelligence where agents can get rewards or punishments based on their actions, which is similar to the way humans learn from experience. It has received a lot of attention since AlphaGo [Silver et al., 2016] beats humans, including those who work on adversarial attack problems. Lin et al. [2017] introduce tactics to attack deep RL agents, which is distinct from our work. Yang et al. [2020] use deep RL to generate adversarial image examples. However, except the recent arXiv paper [Yan et al., 2020], there are no other examples that deep RL is applied to attack video recognition models.

In computer vision domain, Tang et al. [2018] use a deep progressive RL method to distil the most informative frames in sequences for recognizing actions. Zhou et al. [2018] formulate video summarization as a sequential decision-making process and develop a deep RL network to summarize videos. However, these works focus more on the inner features of a video and are different from ours.

3 Methodology

In this section, we introduce the proposed sparse adversarial attack method. For a soft-label black-box attack, we can only get the predicted top one class label and its probability from the video recognition model when given a clean video.

Denote the video recognition model as a function F. Specifically, it takes a clean video x ∈ RT×W×H×C as an input and outputs the predicted top one class label y and its probability p(y|x). Here T, W, H and C denote the length (i.e., the number of frames), width, height and the number of channels of the video, respectively. If the prediction is correct, then y equals the ground-truth label ¯ y. Our goal is to generate an adversarial example xadv close to x such that F(xadv) ̸= ¯ y in the untargeted attack or F(xadv) = yadv in the targeted attack, where yadv is the targeted adversarial class label. We introduce a mask M ∈ {0, 1}T×W×H×C to represent temporal and spatial sparsity. For each element inM, only if its value is equal to 1, then the corresponding pixel in the video will be included in the perturbation process.

3.1 Saliency Detection for Spatial Sparsity

We apply spatial sparsity to each frame of the video by the saliency maps generation approach. This idea is from both the human visual system and some image and video classification models that focused locations contribute more to the recognition results.

We use the fine grained saliency approach [Sebastian and Alvaro, 2010] for saliency maps construction. It calculates saliency based on center-surround differences. We control the area ratio of the salient regions in one frame by introducing a parameter ϕ ∈ (0, 1]. Larger ϕ leads to smaller spatial sparsity. Denote the fine grained saliency detection as a function S, it initializesM by setting the values of the salient regions for all video frames to 1. The initialized mask will be

where (U) and (T) represent "in untargeted attack" and "in targeted attack", respectively. ˆx is a video sample of target class yadv here in targeted attack and will be a video sample which does not belong to ¯ y and set as the "target direction" of attacking in untargeted attack.

3.2 Reinforcement Learning Based Key Frames Selection for Temporal Sparsity

For temporal sparsity, we use the "unimportant frames deletion" method to select a subset of frames that contribute the most to the success of an adversarial attack from the successive frames. We consider the key frames selection process as a multi-step MDP and use RL to learn a policy to select frames. In this subsection, we first formulate the MDP of key frames selection and then introduce the policy network and optimization algorithm.

Markov Decision Process for Key Frames Selection

The MDP consists of states, actions, transition function and reward function.

State. The state st at decision step t is set as the difference between the original class and the target class of videos masked by the current temporal and spatial sparsity mask

Here, ⊙ represents Hadamard product. At the initial state s0, the mask is the spatial sparsity maskMspatial.

Action. An action at is a frame chosen from all T frames that the agent thinks it's not a key frame at decision step t.

State transition. Once the agent chooses action at, we set the values of at th frame inMt to 0. Denote this process as a function D, then we can update the state to

st+1 will be the terminal state either if F(st+1) = ¯ y in untargeted attack or F(st+1) ̸= yadv in targeted attack (i.e., the at th frame is a key frame), or at ∈ {a1, a2, ..., at-1} (i.e., the at th frame has already been chosen in the past decision steps).

Reward. The reward reflects the quality of the chosen action. Our goal is that the agent learns to delete the least important frame and maximizes the long term expected reward. Based on this intention, we design the reward during pretraining as

We set different rewards for the two terminal states to distinguish between deleting unimportant frames and duplication. The former one might be a helpless action when no other unimportant frames can be found, while the latter one should not be done at any time. Note that in targeted attack,

Algorithm 1 Policy optimization for selecting key frames

Input: Clean video set X, target class video set ˆX, video recognition model F .

Parameter: Iteration number I, actor number N, timestep length Tts, epoch number K, batch size M ≤ NTts.

Output: Optimal policy parameter θ∗p .

1: Initialize policy and value network parameter θp,w; 2: for iteration = 1, 2, · · · , I do 3: for actor = 1, 2, · · · ,N do 4: while timesteps < Tts do 5: Get randomx, ˆx fromX, ˆX; 6: s ← ( ˆx - x) ⊙ Mspatial ; 7: while s is not terminal state do 8: Run policy πθold , update state and get reward; 9: end while 10: end while 11: Compute advantage estimate A (Equation (9)); 12: end for 13: Optimize θp,w for K epochs with batch size M; 14: θold ← θp; 15: end for 16: return θp.

for certain x and ˆx, the larger value of p(yadv|st+1) means the less importance of at th frame toward generating the adversial example. Thus we define the reward during fine-tuning as

Policy Network

The agent behavior is defined by its policy. We use a policy network πθp (at|st) to parameterize the policy.

Network Architecture. The input of the policy network at decision step t is the current state st. The network consists of 5 convolutional layers and 3 fully connected (FC) layers. The kernel size and stride in the time dimension is set to 1 which makes the network only perform spatial convolutions on each frame. We use average pooling to sample the overall feature information and to reduce the parameter dimension. The FC layers compare time domain information of a frame with its surrounding frames and it ends with the softmax function which predicts a probability distribution pt for each frame.

Action Selection. In the training process, the action at is sampled from a multinomial distribution as

When making decisions, the agent selects the frame with max probability according to

Policy Optimization

We train the policy network πθp (at|st) to optimize the expected sum of rewards L(θp) = Et[R(s1:t)|s0, θp] =

∑si ∑ai πθp (ai|si)r(si, ai). Here, the expectation E indicates the empirical average over a finite batch of samples.

We apply PPO algorithm with clipped surrogate objective [Schulman et al., 2017], which we found to be more stable and sample efficient than REINFORCE [Williams, 1992]. We use a value network V (st) to approximate the expected future rewards for being in state st. The value network has a similiar architecture as the policy network but the top FC layer only outputs a single value. Denote θold as the policy parameters before the update, and vt(θp) as the probability

ratio πθp (at|st) πθold (at|st) . The surrogate objective function that PPO maximizes can be written as

The first term inside min, vt(θp)At, is the the objective used in Conservative Policy Iteration (CPI) algorithm [Kakade and Langford, 2002] which finds an approximately optimal policy. The second term clip(vt(θp), 1 - ϵp, 1 + ϵp)At modifies the objective by clipping vt(θp) into the interval [1 - ϵp, 1 + ϵp]. We take the minimum of the unclipped and clipped objective. This scheme penalizes changes to the policy that move vt(θp) away from 1. We use the advantage estimator

where G is the total number of timesteps when encountering the next terminal state and δt = rt+γV (st+1)-V (st). In our experiments, we set the hyperparameters ϵp = 0.2, γ = 0.99 and λ = 0.95.

During optimization, in each iteration, each of N parallel actors πθold collect Tts timesteps of data and compute advantage estimates A1,A2, · · · ,ATts . Then we construct the surrogate function on these NTts timesteps of data, and optimize it with Adam for K epochs. Algorithm 1 summarizes the whole procedure of policy ptimization.

3.3 Video Attacking

There are several algorithms that have been proposed for the black-box attack setting for generating adversarial images. However, most of them require huge amount of queries for attacking one sample. Cheng et al. [2018] suggest that this problem can be formulated as an optimization problem, where the objective function can be evaluated by binary search with additional model queries. Thereby a zeroth order optimization algorithm can be applied to solve the formulation. They [2019] later improved it by directly estimate the sign of gradient at any direction instead of the gradient itself, which enjoys the benefit of single query. Our attack algorithm is built based on their Sign-OPT algorithm.

For simplicity, we only focus on untargeted attack here, while the same procedure can be applied to targeted attack as well. In our formulation, θd represents the search direction and g(θd) is the distance from the given example x to the nearest adversarial example along the direction θd. The objective function can be written as

It can be evaluated by a binary search procedure locally. At each binary search step, we query the model F(x + λ θd ‖θd‖ )

Algorithm 2 Reinforcement learning based sparse targeted video attack

Input: Video recognition model F, clean video x, target class label yadv, target class video set ˆX, pretrained policy parameter θp, pretrained value network parameter w.

Parameter: Sampled examples number n, salient region ration ϕ, attack iteration number Tai, gradient sampling number Q, smoothing parameter ϵd and step size η.

Output: Adversarial example xadv.

• 1: Fine-tune the policy network πθp using Algorithm 1 with x and random samples from ˆX;
• 2: for i = 1, 2, · · · , n do
• 3: Get random ˆx from ˆX;
• 4: Mspatial ←S(x, ϕ) ∪S(ˆx, ϕ);
• 5: Run policy πθp to get temporal sparse maskM;
• 6: ˆ y ← F (x + (ˆx - x) ⊙ M);
• 7: if ˆ y = yadv then
• 8: θ ← (ˆx-x)⊙M ‖(ˆx-x)⊙M‖ ;
• 9: Compute g(θ) using the binary search algorithm;
• 10: if MAP (g(θ) ⊙ θ) < MAP (g(θd) ⊙ θd) then
• 11: M ∗ , θd ←M, θ;
• 12: end if
• 13: end if
• 14: end for
• 15: for t = 1, 2, · · · , Tai do
• 16: Sample random u1,u2, ..., uQ from Gaussian distribution N (0, 1);
• 17: ˆg ← 1 Qd ∑Qd q=1 sign(g(θd + ϵduq) - g(θd))uq;
• 18: θd ← θd - ηˆg;
• 19: Evaluate g(θd) using the binary search algorithm;
• 20: end for
• 21: xadv = x+ g(θd) · θd;
• 22: return xadv.

and determine whether the distance to decision boundary in the direction θd is greater or smaller than λ based on the prediction. Usually, its directional derivative can be estimated by finite differences ˆ∇g(θd;u) = g(θd+ϵdu)-g(θd) ϵd u, where u is a random Gaussian vector and ϵd is a very small positive smoothing parameter. However, this approach consumes a lot of queries when computing g(θd +ϵdu)-g(θd). To improve query complexity, we do not need very accurate values of directional derivative and an imperfect but informative estimation of directional derivative of g which can be computed by a single query is enough for us. Thus, we can compute the sign of this value by

and estimate the imperfect gradient by sampling Qd random Gaussian vectors

When attacking, we first initialize θd using

We sample n examples of target class video ˆx randomly, and choose the one with smallest g(θd). This helps us to find a good initialization direction and thus get a smaller distortion in the end. Then we update θd with the zeroth order optimization and get the optimal direction θ∗d . Finally, we can get the adversarial example xadv using

We set n = 100 in all of the following experiments.

The whole process of our method for targeted attack is described in Algorithm 2. The pretrained parameter θp and w is optimized by Algorithm 1. Function MAP computes the mean absolute perturbation which we will define in Equation (15). For untargeted attack, we skip the fine-tuning step since the pretrained policy network is good enough.

4 Experiments

4.1 Experimental Setting

Datasets. Similar to [Wei et al., 2020], we use UCF101 [Soomro et al., 2012] and HMDB-51 [Kuehne et al., 2011] in our experiments. UCF-101 contains 13,320 videos collected on YouTube with 101 action categories. HMDB-51 contains 7000 clips downloaded from various cinemas distributed in 51 action classes. We split 70% of the videos in both datasets as training set and the remaining 30% as test set. We use 16-frame snippets that are uniformly sampled from each video as input samples of threat models and only consider videos that are correctly predicted by the threat model. During pretraining, we use the training set as both clean video set X and target class video set ˆX. When fine-tuning, we choose a video from test set as clean video x and the corresponding training set as target class video set ˆX.

Threat Models. In our experiments, two video recognition models, Convolutional 3D ResNeXt (C3D) [Hara et al., 2018] and Long-term Recurrent Convolutional Networks (LRCN) [Donahue et al., 2015] are used as threat models.

Metrics. We use five metrics to evaluate the performance of our method in various aspects: 1) Fooling ratio (FR) is defined as the percentage of adversarial examples that are successfully misclassified. 2) Query number (Q) counts the times of queries to finish an attack. 3) Mean absolute perturbation (MAP) [Wei et al., 2019] denotes the perceptibility score of the adversarial perturbation:

where Np is the number of pixels and ri is the intensity vector (3-dimensional in the RGB color space). 4) Sparsity (S) represents the proportion of pixels with no perturbations versus all the pixels in a specific video, which is defined as

where ϕi is the salient region ratio of the corresponding important frame and T is the total number of frames in a video. 5) Time (t) counts the time used for finishing an attack. The computing infrastructures used for running experiments include 8 Nvidia GeForce RTX 2080 Ti GPUs, Intel Xeon E52680 v4 CPU, 320 GB memory and Ubuntu 16.04.1.

4.2 Parameter Setting

There are several parameters need to be set in our algorithms. We set most of them by the grid search method. Here we only take the parameter salient region ratio ϕ as an example. Since when ϕ < 0.3 most initial states will be terminal states, we fix other parameters and set ϕ as {0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0}. We use 20 randomly sampled videos from the original training set of UCF-101 as validation set to do the experiment. We find that larger

ϕ leads to larger MAP and Q, while smaller ϕ causes shorter decision trajectory and less temporal sparsity which also leads to larger MAP and Q. Finally we choose a median ϕ which gets relatively small MAP, Q and large S as ϕ = 0.6.

4.3 Performance Comparison

We compare our method with the OPT attack [Cheng et al., 2018] and heuristic attack [Wei et al., 2020], which we set as the baselines of black-box adversarial attack on video recognition models. We also compare it with the Sign-OPT attack [Cheng et al., 2019] as an ablation study for the sparsity in our method. We are unable to compare our method with [Yan et al., 2020] since the code of its model is not publicly available. The evaluations are performed with two video recognition models on two datasets mentioned above. For fair comparison, we set the bound of MAP as MAP = 3 in untargeted attack and MAP = 9 in targeted attack, according to the median of best performances in the above works. The iteration of attacking steps will terminate either if MAP reaches the bound or the iteration number exceeds the maximum iteration number Tai = 1000.

Table 1 lists the performance comparisons regarding to both the untargeted attack and the targeted attack on two datasets. The average query numbers Q and time t (min) for pretraining are 17600.5, 11.72 for untargeted attack and 30052.2, 18.68 for targeted attack, respectively. The cost of pretraining can easily be offset by no more than 10 times of attack and can be ignored when doing numbers of attacks.

For untargeted attacks, compared to other methods, we have the following observations. First, our method significantly reduces the query numbers by more than 38%. Particularly, it verifies our sparsing strategy's efficiency when comparing to Sign-OPT method with no sparsity. Second, both our method and Sign-OPT method can reach the MAP bound within a limited iteration number, while OPT method and heuristic method fail on some examples when attacking C3D model. Third, our method gets better sparsity than heuristic method. It shows that our agent learns a better frames selection strategy than their method. Last, by looking into the detailed results, we found that only around 60%

of the queries are spent on attacking, while others are spent on inferring.

For targeted attacks, which usually need more query numbers and perturbations than untargeted attacks due to their difficulty, similar trends are observed as untargeted attacks. Our method reduces the query numbers by more than 34% and can always reach the MAP bound within a limited iteration number. It gets better sparsity than heuristic method on most examples. We also found that heuristic method does not preform as expectation since many of its generated sparse directions make the attack fall into local optimal solutions. For summary, our our proposed method achieves the best performance in the majority of test tasks. It demonstrates the effectiveness and the efficiency of our method.

Figure 1 gives an visualized example of adversarial video generated by our method. The ground-truth label for the clean video is "High Jump". By adding the generated humanimperceptible adversarial perturbations, the model tends to predict a wrong label "Javelin Throw" at the top-1 place. The generated adversarial perturbations are quite sparse.

5 Conclusion

In this work, we proposed an RL based sparse black-box adversarial attack method on video recognition models. To speed up the attack process and to reduce query numbers, we explored the sparsity of adversarial perturbations. For temporal domain, we modeled the key frames selection process as an MDP. The agent in our model continuously explored the differences between videos of distinct classes and received rewards from the threat model. Combined with policy optimization method, it finally learned an optimized frame selection strategy. We also used saliency detection to select key regions and Sign-OPT method which only estimates the sign of gradient in zeroth order optimization to further speed up the attack process. Our algorithm is applicable to multiple threat models and video datasets. The experimental results demonstrated that our algorithm is more effective and more efficient to generate adversarial examples than previous methods.

The pertinent area of future work is to investigate the blackbox attack on video recognition models using fewer queries and time.