{'fraction_non_alphanumeric': 0.03192481693950842, 'fraction_numerical': 0.012242899118511263, 'mean_word_length': 4.640273576219913, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sparse Black-box Video Attack with Reinforcement Learning

Adversarial attacks on video recognition models have been explored recently. However, most existing works treat each video frame equally and ignore their temporal interactions. To overcome this drawback, a few methods try to select some key frames and then perform attacks based on them. Unfortunately, their selection strategy is independent of the attacking step, therefore the resulting performance is limited. Instead, we argue the frame selection phase is closely relevant with the attacking phase. The key frames should be adjusted according to the attacking results. For that, we formulate the black-box video attacks into a Reinforcement Learning (RL) framework. Specifically, the environment in RL is set as the recognition model, and the agent in RL plays the role of frame selecting. By continuously querying the recognition models and receiving the attacking feedback, the agent gradually adjusts its frame selection strategy and adversarial perturbations become smaller and smaller. We conduct a series of experiments with two mainstream video recognition models: C3D and LRCN on the public UCF-101 and HMDB-51 datasets. The results demonstrate that the proposed method can significantly reduce the adversarial perturbations with efficient query times.


Introduction
Deep Neural Networks (DNNs) have achieved great success in a wide range of tasks [22,38,6,33,10,25]. Despite this fact, it is proved that deep neural networks are vulnerable to adversarial examples [11,36,9,18,42]. Recent works have shown that adding a carefully crafted, small human-imperceptible perturbation to a clean sample can make the deep neural models crash in image classification [1,11,37], object detection [44,43,31], semantic segmentation [43] and other tasks. Nowadays, more and more DNN models are deployed in various sectors with high-security requirements, which has caused the study of adversarial examples to gain increased attention. The existence of adversarial examples brings huge security risks to the deployment of deep learning systems, such as automatic driving [26], robotics [42], face recognition [2,9,48] and other aspects.
Due to many real-time video classification systems which are constructed based on the DNN models, it is crucial to investigate the adversarial examples for video models. On the one hand, video attacks can help researchers understand the working mechanism of timeseries deep models. On the other hand, adversarial samples facilitate various deep neural network algorithms to assess the robustness by providing more varied video training data [39,9,49]. In this paper, we focus on video attacks, specifically attacking the video classification model under the black-box condition. Compared with the white-box setting, the black-box video attack is more realistic. Because the white-box attack needs to obtain the structures and parameters of the deep learning model, and it is usually difficult in the real applications. In contrast, black-box attacks don't need these information. A widely used way is to access the output of the target model when the input is given. In this way, the gradients can be estimated to generate adversarial examples.
According to [17], the current video attacking methods can be roughly divided into two classes. The first class is called dense attack which pollutes each frame in a video [23,19], and the second class is to select some key frames, and then generates perturbations on these selected frames [39,40], called as sparse attack. Compared with the dense attack, the sparse attack is more reasonable because there are temporal interactions between adjacent frames in the video. Utilizing this relationship can help both reduce the adversarial perturbations and improve the efficiency of the generation process. For the former advantage, because the selected frames are the most important ones in a video, only adding small perturbations on these frames can fool the recognition model, leading to the reduction of adversarial perturbations on the whole video. For the second advantage, the selected key frames are usually sparse, compared with generating perturbations on the whole frames, the operation of dealing with a few frames is more efficient.
To better select key frames in the sparse attack, a heuristic black-box attack on video recognition models is proposed [40]. They first propose a heuristic algorithm to evaluate the importance of each frame, and then select key frames by sorting the importance scores, finally, the black-box attacks are performed on the selected frames. However, there are no interactions between the attacking process and the selecting key frames in their method. We argue that key frame selection should not only depend on the video itself, but also on the feedback from the recognition models. The frame selection and video attacking are characterized by mutual guidance and cooperation. The results of this way can produce more accurate key frames and smaller perturbations for adversarial videos.
To this end, we present a Sparse black-box Video Attack (SVA) method with Reinforcement Learning (RL) in this paper. Specifically, the environment in RL is set as the recognition model, and the agent in RL plays the role of frame selecting. By continuously querying the recognition models and receiving the feedback of predicted probabilities (rewards), the agent adjusts its frame selection strategy and performs attacks (actions).
Step by step, the optimal key frames are selected and the smallest adversarial perturbations are achieved.
Technically, for the agent, we use an LSTM-based network [15] to measure the importance of each frame. After obtaining the importance degree p t of each frame t in the video, Bernoulli sampling is used to determine whether the frames are critical or not. To perform the black-box attacks, the Natural Evolution Strategy Fig. 1 An example of sparse black-box video attack with Reinforcement Learning (RL). The clean video (top) can be recognized correctly. The adversarial video (bottom) produced by our proposed method is misclassified. Note that only one frame (green-red line annotation) is adaptively selected by the RL, and very small perturbations are added to the key frame.
(NES) [47,16] is utilized to estimate the gradient from the recognition models, and then the adversarial videos are generated based on these gradients. For the reward, we design two kinds of functions, the first one comes from the video itself. For example, the frames with big action changes will have the high confidence to be the key frames. The other one comes from the feedback of attacking recognition models. The insight is that if the frames with tiny perturbations will lead to a big drop of predicted probability, these frames will have the high confidence to be the key frames. Figure 1 shows an adversarial video generated by our proposed method. Figure 2 overviews the proposed method. Our major contributions can be summarized as follows: -We are the first one to use reinforcement learning to attack video recognition models in the black-box setting. In contrast, previous works perform adversarial attacks on the reinforcement learning model itself, and thus our approach differs fundamentally from those works. -A novel algorithm is designed for selecting key frames from a video when attacking video recognition models, which is based on two factors including the visual features of the video itself and the feedback given by the recognition model. Video attacking and key frame selecting are cooperated and guided by each other. -Extensive experiments on two widely used video recognition models (LRCN and C3D) and two benchmark video datasets (UCF-101 and HMDB-51) show that the proposed method can significantly reduce the adversarial perturbations while only needing a few query times compared with the state-of-the-art video attacking methods. Fig. 2 Overview of the black-box adversarial video attacking method. We formulate the key frame selection and attacking step into the reinforcement learning framework. Please see the texts for details.
The rest of this paper is organized as follows. In Section 2, we briefly review the related work. The proposed algorithm is described in Section 3. The experimental results and analysis are presented in Section 4. Finally, we summarize the conclusion in Section 5.

Related Work
Adversarial Attack on Video Models: Adversarial attacks on images have been extensively studied [12,5,11]. Compared with images, the dimension of videos is very high. It is not easy for general attack algorithms to directly attack such high-dimensional data. A high dimension leads to large search space, and the algorithm needs more query times to find the optimal perturbations to accomplish the successful attack. Therefore, it is more difficult to design an efficient black-box video attack algorithm.
In the past years, many adversarial attacks for videos have been proposed. An l 2,1 -norm regularization based optimization algorithm is the first method that is proposed to compute the sparse adversarial perturbations for video recognition [39]. l 2 is used to make the frame have small perturbations and l 1 is used to make adversarial frames fewer. The 3D universal perturbation [23] is generated by Generative Adversarial Networks offline and then used with unseen input for the realtime video recognition model. Unlike such white-box attack algorithms which need some knowledge about the video recognition models, Jiang et al. utilize tentative perturbations and partition-based rectifications to obtain good adversarial gradient estimates and high attack success rate in the black-box setting [19]. But attacking all frames of the video would cause more perturbations and poor robustness of the adversarial video. The adversarial video can easily become ineffective when one of the frames is randomly replaced with a clean video frame. Another black-box method is proposed by Wei et al. [40], they heuristically search a subset of frames and the adversarial perturbations are only generated on those selected frames, but the attacking processes and key frames selection are separated from each other, the perturbations of adversarial videos are still unsatisfactory.
Unlike the algorithms mentioned above, our method generates adversarial perturbations on the key frames which are selected by an agent trained using visual features of the video and the feedback of attacking. Our method could generate smaller adversarial perturbations than state-of-the-art black-box video attack methods.
Deep Reinforcement Learning: Deep reinforcement learning is originally designed for learning and mimicking human decision-making processes, which aims to enable the agent to make appropriate behaviors according to the current environment through continuous interaction with the environment [24,28]. It doesn't require any supervisory information unlike supervised machine learning methods, but rather receives a reward signal to evaluate the performance of the action. Reinforcement learning has received a lot of attention since the AlphaGo [32,33] beats humans. Computer vision tasks have also benefited from deep reinforcement learning in recent years. For example, Zhou et al. have applied deep reinforcement learning to train a summarization network for video summary [45]. Dong et al. use reinforcement learning for action recognition [8]. The process of discarding some irrelevant frames is a kind of hard attention mechanism in their method. Besides, it has been applied in some other fields like tracking, identification [50], and person search [24].
However, there is no example that deep reinforcement learning is applied in generating adversarial examples. Reinforcement learning algorithms have similar implementation mechanisms with adversarial attack algorithms, especially black-box attack algorithms. It is the first time that we attempt to apply reinforcement learning to the video black-box adversarial attacks. An agent is designed to select key frames while attacking a video using a novel reward function. The key frames selection and adversarial attacks are mutual guidance and cooperation in the whole attacking process.

Methodology
The adversary takes the video classifier F (·) as a blackbox oracle and can only get its output of the top-1 class and its probability. Specifically, given a clean video x and its ground-truth labelȳ, F (·) takes x as an input and outputs the top-1 class label F(x) = y and its probability P (y|x). If the prediction is correct, then y =ȳ. The adversarial attack aims to find an adversarial example x adv which can make F (x adv ) =ȳ in the un-targeted attack or F (x adv ) = y adv in the targeted attack with the targeted adversarial class y adv , while keeping the adversarial example x adv satisfying the condition: x adv − x ρ ≤ adv , where adv is the bound of the perturbation , the ρ in L ρ -norm can be set 0,2,∞.

Video Attacking
The attack algorithm in our method is built based on Fast Gradient Sign Method (FGSM) [11], which is originally designed for image models. It is defined as: where α is the step size. sign(·) is sign function. g is the gradient, in white-box attacking setting, g can be computed using x l adv (x). Here l adv (x) is abbreviated for adversarial loss function, which is described with l adv (x) = −l(F (x),ȳ) in un-targeted attack and l adv (x) = l(F (x), y adv ) in targeted attack. l(·) is a crossentropy loss. Due to black-box settings, we cannot get the gradient from the recognition model directly, NES [47] algorithm is used as gradient estimator in the proposed method. For NES algorithm, it first generates n/2 values δ i N (0, I), i ∈ {1, 2...n/2}, where n is the number of samples. Then, it sets δ j = −δ n−j+1 , j ∈ {(n/2 + 1), ..n}. Finally, the gradient g is estimated as: where ∆ is the search variance. We extend FGSM with NES from image models to video models as our attacking algorithm. As mentioned above, we use the agent to select the key frames and attack these key frames to achieve the attack of the entire video. Note that the core contribution in our method is to introduce RL to select key frames, rather than the attacking method module. Therefore, we choose a simple and widely used FGSM+NES method. Other methods like Opt-attack [3,4,46] can also be available.
In addition, for the targeted attack, we first initialize x adv by adding the random noises on the selected frames to make F (x adv ) = y adv . In this time, the perturbation = ||x adv − x|| ρ is large. Next, we will gradually decrease the perturbations' magnitude until the given bound adv is achieved while keeping the prediction label not change, i.e., the prediction label is still y adv . In this way, we obtain the minimal adversarial perturbation for the current selected frames. For the untargeted attack, we don't need to initialize x adv like the targeted attack, instead, some key frames are randomly selected as victims and the perturbations are added.
The key frames will be dynamically adjusted by the agent in the next section, and the optimal perturbation will be solved.

Key Frame Selection
Videos have successive frames in the temporal domain, thus, we consider searching key frames that contribute the most to the success of an adversarial attack. In our approach, key frames selection is considered as a one-step Markov decision process. Figure 2 provides a sketch map of this process. The agent learns to select the frames by maximizing the total expected reward by interacting with an environment that provides the rewards and updating its actions.
The input of the agent is a sequence of visual features of the video frames {v t } T t=1 with the length T. The agent is a bidirectional Long-Short Term Memory network (BiLSTM) [15] topped with a fully connected (FC) layer. The BiLSTM produces corresponding hidden states {h t } T t=1 . We use the ResNet18 [14] to extract visual features and set the dimension of hidden state in the LSTM cell to 128 throughout this paper. Each h t contains both information from the forward hidden state h f t and the backward hidden state h b t , which is a good representation of the time domain information of its surrounding frames. The FC layer that ends with the sigmoid function σ predicts a probability p t for each frame, and then the key frames a t are sampled via a Bernouli function: where a t ∈ {0, 1} indicates whether the t th frame is selected or not. W is the weights of the full connection layer. h t = φ(v t ), and φ(·) is the BiLSTM network. The reward reflects the quality of different actions. It contains two components in our method: the reward from the inherent attributes of the video itself and the reward from the feedback of the recognition model. The former reward includes diversity reward R div and representative reward R rep [45]. Let the indices of the selected frames be K = {t|a t = 1, t = 1, ..., T }, the reward R rep and R div can be defined as: where d(·, ·) is the dissimilarity function calculated by The reward from the feedback of the video recognition model is defined as: where Q is the number of queries, P is the mean perturbation of the adversarial video (MAP), 0.05 is a normalization factor, 0.999 is the penalty factor used for reducing the number of queries. The rewards R div , R rep and R attack complement each other and work jointly to guide the learning of the agent: The hyperparameters γ 1 and γ 2 are set according to the parameter tuning.
As shown by the reward function, the reward R rep and the reward R div only rely on the internal properties of the attack video. By the constraints of these two rewards, the agent can accurately identify the video frames that are representative and diverse. For the reward R attack , it penalizes the actions versus perturbation and query number meanwhile. For query numbers, we set different rewards in three phases. For queries less than 15000 times, we think the query number is acceptable, and the reward is mainly related with the perturbation exp(−P/0.05), i.e., if the mean absolute perturbation is small, exp(−P/0.05) will be large. For queries more than 30000, we think the attack is unavailable, and we align a small reward -1, which is much less than exp(−P/0.05) for any P. For queries more than 15000 and less than 30000, we add a penalty on exp(−P/0.05) to make its reward less than that in the first case. In this way, the rewards can encourage the agent to make an accurate decision to achieve the small perturbation and query number at the same time.
Since each frame corresponds to two actions, there are 2 T possible executions of a video, which is basically not feasible for deep Q learning. Thus, we employ the policy gradient method to make the agent learn a policy function π θ with parameters θ by maximizing the expected reward J(θ) = E τ π θ [R(τ )]. Following the REINFORCE algorithm proposed by Williams [41], we approximate the gradient by running the agent for N episodes on the same video and then taking the average gradient: where R n is the reward computed at the n th episode. The number of episodes N is set to 5 in our experiments. Although the above method can estimate the gradient well, it may contain high variance which will make the network hard to converge. A common countermeasure is to subtract the reward by a constant baseline b, so the gradient becomes where b is a constant baseline that is used to alleviate the high variance. For computational efficiency, it is set as the moving average of rewards experienced so far. We optimize the policy function's parameter θ via Adam [20]. We update θ as: θ = θ + ls · θ J(θ), where ls is learning rate and set to 10 −5 in our experiments.

Overall Framework
Here, the whole process of our method in the targeted setting is described in Algorithm 1, which is a continuouslearning algorithm. The epsilon decay is used to control the reduction size of the perturbation bound. and FGSM step size α are dynamically adjusted as described in subsection 3.4. The binary vector M has the same size as the frame number of the input video and some values in M will be set to 1 after the agent is trained. The agent in the whole process of attacking is updated with the rewards' values, which is dynamic and interactive. This process does not need any human intervention.

Implementation Details.
To follow the query limited black-box settings and make our experiments more convenient, the maximum query number is set to 3 × 10 4 in the un-targeted mode and 6 × 10 4 in the targeted mode for all black-box attack algorithms in our experiments. For NES, we set the population size as 48, which works well on different datasets in terms of the success rate or the number of queries. For search variance ∆ in NES, because the targeted attack needs to keep the target class as the top-1 position, while the un-targeted attack is to remove the current class from the top-1 position, we set it to 10 −6 for the targeted attack setting and 10 −3 for the un-targeted attack setting. The adjustment of step size α adopts the strategy in [27]. For the targeted attack, we adjust the step size α and epsilon decay dynamically. If the proportion of the adversarial examples cannot be maintained above the threshold 50%, the step size α is x adv ← x adv + α · sign( g) using Eq. (1);  halved. If we can't reduce the perturbation size after 20 times in a row, we cut the epsilon decay in half.
There are three hyperparameters in our method, and we obtain their best values via parameter tuning experiments. The P in Eq.(8) is automatically updated in the algorithm, but we need to set its maximum value adv . In Eq.(9), we need tune γ 1 and γ 2 . When γ 1 is tuning, we fix γ 2 , and vice versa. The tuning results are given in Figure 3. From the figure, we see γ 1 = 2 and γ 2 = 3 are the reasonable choices. As for adv , we find that FR (the bigger, the better) and MAP (the lower, the better) reach a balance when = 0.05. Therefore, we set the maximum adversarial perturbations magnitude to adv = 0.05 per frame, and this setting is also applied to other video attack algorithms in the experiment.

Experiments
In this section, two state-of-the-art video attack models are used to be compared with our proposed method on two video recognition models with two public datasets. We focus on the overall perturbations and the length of the frames selected in our experiments. Furthermore, a variant of our method is also designed as a comparison. A comprehensive evaluation of our method will be presented on those recognition models and datasets.

Datasets and Recognition Models
The datasets and recognition models used in the experiments are described in detail here.
Datasets. Two widely used datasets, UCF-101 [34] and HMDB-51 [21], are used in our experiments. UCF-101 is an action recognition dataset containing 13,320 videos with 101 action categories. HMDB-51 is a dataset for human motion recognition, which contains 51 action categories with a total of 7000 videos. Both datasets divide 70% of the video into training sets and 30% of the test sets. For convenience and fairness of comparison, 16-frame snippets evenly sampled from each video are used as input to the recognition models during the evaluation. The same approach was fist adopted in [13] and also used in [39]. In our experiments, we randomly sample 100 videos from the UCF-101 test dataset and 50 videos from the HMDB-51 test dataset for experimental comparison. It is worth noting that all the selected videos can be accurately classified by both recognition models.
Recognition Models. In our experiments, Longterm Recurrent Convolutional Networks (LRCN) [7] and C3D [13] are used as recognition models. The LRCN model uses a Recursive Neural Network to encode the Spatio-temporal features generated by CNNs. In our implementation, Inception V3 [35] is used to extract the features of video frames, and LSTM is used for video classification; The C3D model uses 3D convolution to learn Spatio-temporal features from video with Spatiotemporal filter for video classification. These models are all mainstream methods for video classification. In order to make the two video classification models better adapt to the input video, we train them with 16-frame snippets for 30 epochs via Adam in each dataset, and the learning rate is initialized as 10 −5 and decreases to its 1/10 after 20 epochs. After training, both video classification models meet the requirements of our experiment. Table 1 summarizes the test accuracy of the recognition models with 16-frame snippets on the whole UCF101 and HMDB51 datasets.

Evaluation
We select Fooling rate (FR), Query number (Q), Mean absolute perturbation (MAP), and Sparsity (S) as evaluation metrics to evaluate the performance of our method on various sides. Next, we will introduce and describe these metrics in detail.
Fooling rate (FR). The Fooling rate is defined as the percentage of attacks that successfully generate adversarial examples. In our experiments, it is influenced by two main factors: whether the adversarial video can successfully fool the video classifier and whether it is imperceptible. More concretely, with the upper limit of query numbers (3 × 10 4 in the un-targeted mode and 6 × 10 4 in the targeted mode), if the adversarial video produced by the attack algorithm can make the classifier misclassify itself and the pixel mean perturbations of the whole video is less than the upper limit of perturbations (As described in subsection 3.4, the is set to 0.05 in our experiments), the adversarial video is considered successful. Fooling rate (FR) is a common metric for evaluating adversarial attacks, and a higher value means better performance.
Query number (Q). In the query-limited setting, To generate adversarial examples, fewer query times mean that the attack algorithm has a higher attack efficiency. Therefore, we measure the efficiency of the attack algorithm in the current dataset by using the average query number (Q) of all adversarial videos generated with the attack algorithm successfully.
Mean absolute perturbation (MAP). This metric is used to quantify the perceptibility of change in the video. Here, we follow some previous work [30,29,43] in getting an index (MAP) for an adversarial perturbation given by where x i,adv is the i th adversarial video, x i,orig is the i th original video, and | pixel xi | is the total pixel number of this video. we normalize the l 1 norm of the video difference by the total number of pixels. In our experiments, we use the average MAP of all successful adversarial videos on one dataset to evaluate the attack algorithms, and a smaller value means better performance. Additionally, we have resized the value of MAP to 0-255 for the sake of clarity.  To show the sparsity effect of the attack algorithms, the sparsity (S), is used to represent the proportion of frames with no perturbations versus all frames in a specific video. It is defined as: where m i is the length of the key frames of the video x i . A large sparsity value means that only a few frames are added the adversarial perturbations. In our experiments, we use the average S of all successful adversarial videos on one dataset to show the sparse effect of the current attack algorithm.

Comparing Algorithms
We compare our Sparse Video Attack (SVA) method with Opt-attack [3] and Heuristic-attack [40]. For Optattack, it is originally proposed to attack image classification models under the black-box setting. The reason we select it as one competitor is that it can achieve smaller distortion compared with some other black-box attack algorithms. We directly extend Opt-attack to attack video models. For Heuristic-attack, it is also a time-domain sparse attack method like ours. We use the same parameter settings in their original papers and official implementation code, respectively. Besides, one variant of our method, named SVAL, is joined to comparisons. For the SVAL algorithm, we replace the R attack reward in Eq.(9) with the reward L percentage that is used to limit the length of the key frames: where S is the sparsity metric, a bigger S value means the fewer frames will be selected. The definition of p t can be found in Eq.(3). The SVAL algorithm only needs some videos to train the agent and make it intelligent. So in different experiments, we first randomly select 50% videos to train agent, and then use the agent in our black-box attack method. We still optimize the policy function's parameter θ via Adam and update θ as: θ = θ + ls θ (J R attack + L percentage ), where J R attack means there is no reward R attack . The epochs of training is set to 20, and the learning rate is initialized as 10 −5 and decreases to its 1/10 after 15 epochs.

Performance Comparisons with SOTA methods
Because the parameter S in SVAL needs to be set, a grid search method is used to select appropriate parameters with different experiments. We here only show the sparsity tuning for the C3D model with 10 randomly sampled videos from the UCF-101 dataset. The results are recorded in Table 2. The symbol "-" in Table 2 denotes that the agent cannot achieve the 100% fooling rate under the current sparsity. In this situation, the MAP cannot be computed across all the adversarial videos, and cannot compare with other sparsity fairly. Therefore, we use "-" to indicate it. It is found that the fooling rate decreases with the rising of sparsity. In the un-targeted attack setting, when FR is 100%, the smallest MAP is 3.2895. Therefore, we set S = 0.5 in the following experiment. In the targeted attack setting, S = 0.2 is a good choice, so the setting is used in the following experiments. In the other sparsity settings, we use the same way to select the corresponding best results. As shown in Table 2, it can be found that attacking a part of the video frames is a feasible and effective way, which would significantly reduce the perturbations of the adversarial video.
The comparison results in the un-targeted setting are listed in Table 3 in different tasks. In each task, the best performance is emphasized with the bold number. As shown, SVAL and SVA have great advantages over other methods on the whole. On the MAP side, SVA ranks first in the 3/4 comparisons. The biggest gap between other algorithms and SVA occurs in the C3D model with the UCF-101 dataset, the MAP of SVA is only 2.4450, but others all exceed 3. Notice that there is no one case that our methods are not as effective as other methods. On the sparsity side, SVAL and SVA are all ahead of the others, the sparsity generated by them all exceeds 50%.
Usually, targeted attacks need more query numbers and perturbations than un-targeted attacks. For Optattack and Heuristic-attack methods, they don't successfully generate any adversarial video even after 60,000 query times, which exceeds the experimental upper bound of query number pre-defined in section 3.4. Therefore we use "-" to represent their performance. The comparison results are recorded in Table 4. Obviously, the proposed methods are superior to other methods. The FR of our methods is at least 30% instead of 0% in the other competitive methods.
Two examples of the adversarial videos produced with our SVA un-targeted method are shown in Figure 4. For the first example (above the black line), the ground-truth label is "MilitaryParade", by adding the generated adversarial perturbations, the model tends to predict a wrong label "BandMarching". There are only 5 frames that have the perturbations in the whole 16 frames video. For the second example (below the black line), the ground-truth label is "flic flac", by adding the generated adversarial perturbations, the model tends to predict a wrong label "kick ball". The adversarial video has only 4 frames with perturbations, there are no perturbations on the other frames. Besides, two examples of the adversarial videos produced with our SVA targeted method are shown in Figure 5. The clean video, adversarial video, and the corresponding perturbations are shown in the green box, red box, and grey box respectively. For these two adversarial videos, the target classes are all "Archery". The adversarial video above the black line is from UCF-101 with the recognition model C3D, its original class is "RopeClimbing". There are 10 video frames that are polluted. The adversarial video below the black line is from UCF-101 with the recognition model LRCN. Its original class is "Body-WeightSquats". The perturbations only exist in 8 video frames with a total of 16 frames. From these samples, we can conclude that the agent can select a small number of key and representative frames from the whole input video and the perturbations added on these key frames are human-imperceptible.
By observing and analysing all the results, we can draw the following conclusions: (1) Our SVA achieves the best performance in the majority of test tasks. (2) Attacking on key frames is an effective way to reduce perturbations of adversarial video. (3) Mutual guidance and cooperation between key frames selection and attacking is helpful to select the key frames for generating perturbations.

Ablation Study
We conduct a serial of ablation study experiments to analyze the proposed SVA in this subsection. Four experiments are conducted: the effectiveness of different reward functions, the influence of query numbers on ex- perimental results, the effectiveness of keyframe selection algorithms, and the influence of different gradient estimation algorithms on the final attack performance. We discuss the components in the following.

Different combination of reward functions
There are three rewards used to guide the agent in our experiments. In this subsection, the proposed method in the un-targeted setting on 20 randomly selected videos with the C3D model is used for the ablation study. The ablation study for each reward function are given in Table 5, where "No RL" means that the results using FGSM+NES, and no RL module is used, "SVA R attack " means RL module is added, but only R attack is integrated, "SVA R attack+rep " means R attack and R rep are both integrated, and "SVA" means the full SVA model with R attack , R rep and R div . It can be shown that the attack reward R attack significantly improves the attacking performance. And the intrinsic rewards R rep and R div have relatively small contributions. The MAP and S in Table 5 are computed when FR meets the same  accuracy. It can be directly concluded that key frame selection is not only relative to the video itself, but also the feedback from the recognition model. The interactions between the attacking process and the keyframe selection can facilitate successful attacks.

Sensitivity to query numbers
We investigate the changes of MAP, S, and FR versus different query numbers (Q). We also run a series of experiments on 20 randomly selected videos and the C3D model using our un-targeted SVA method. The results are shown in Figure 6. It can be found that FR is very relevant with the query number (Q) while MAP and S are relatively smooth versus the query times. It also indirectly proves that the results in our experiment have certain statistical significance and are relatively robust.

Effect of keyframe selection
To illustrate the effectiveness of our keyframe selection algorithm, we make a series of comparisons between our RL-based method and the random selection method.
To conduct a fair comparison, we keep the other components consistent with the SVA and only replace the RL's agent with a random selection step. The number of selected frames is also the same between these two methods. Considering the randomness, each video is attacked five times by the random-based frame selection method, and the best attack result is recorded. The bar chart results of the comparisons are shown in Figure 7.
Obviously, even the best attack result of the random algorithm is not the same as our SVA algorithm.
In addition, we also extend our keyframe selection module to the Heuristic-attack [40] algorithm to replace Fig. 7 The results of the proposed method SVA and random attack (random) on the C3D recognition model. The only difference between these two methods is the algorithm used to select keyframes. In the experiment, the random algorithm selected the same number of frames as the SVA algorithm, and we recorded the best results in five random attacks on 20 videos from UCF101 datasets. (A) the fooling rate of two algorithms (the bigger the value, the better). (B) the query number of two algorithms (the smaller the value, the better). (C) the MAP values of two algorithms (the smaller the value, the better). Obviously, even the best attack result of the random algorithm is not the same as the SVA algorithm.
its frame selection part. The new algorithm (SVA opt ) and the Heuristic-attack algorithm (H opt ) have the same parameter settings, they are only different in keyframe selection. Here, we explore the performance of these two algorithms in terms of un-targeted attacks. We use the C3D recognition model, which has a wide application than other video recognition models. The results of these two methods are shown in Figure 8. Unsurprisingly, SVA opt has an overwhelming advantage over H opt . For both datasets, HMDB-51 and UCF-101, SVA opt leads H opt in all evaluation metrics, which has less perturbation, fewer query numbers, higher sparsity, and higher fooling rate. We can conclude that the proposed keyframe selection algorithm is flexible and efficient.

Sensitivity to gradient estimation
Here, we make a series of comparisons between different gradient estimation methods, because the gradient estimation method is a key step in our SVA. We test additional gradient methods like SignSGD [46] and Sign-OPT [3] besides the NES method used in our method [47]. The attacking results of the proposed SVA with three different estimators on the C3D recognition model are shown in Figure 9. Here, we randomly select 20 videos from HMDB-51 and 20 videos from UCF-101, respectively. Each attack algorithm has the same upper query number limitation. From the observation, SVA with different gradient estimators will produce different attack results, but the differences are small. The big difference occurs in the fooling rate. On the UCF101 dataset, SVA with SignSGD and SVA with Sign-OPT obtain 10% and 5% better fooling rates than SVA with NES, respectively. For other evaluation metrics, those  The un-targeted attack results of the proposed SVA on the C3D recognition model with different gradient estimation methods. There are three different gradient estimation algorithms SignSGD, Sign-OPT, and NES. The only different setting between those video attacking methods is the gradient estimation method. Here, we randomly select 20 videos from HMDB-51 and 20 videos from UCF-101, respectively. The adversarial results above the black line are from HMDB-51, and the adversarial results below the black line are from UCF-101. (A) The fooling rate (FR) of the two methods (the bigger the value, the better). (B) The MAP values of two algorithms (the smaller the value, the better). (C) The sparsity of two algorithms (the bigger the value, the better). The max available query times are set to be consistent. It can be concluded from the observation that different gradient estimation methods do not produce significantly different results.
three methods have no obvious performance advantages. We can conclude that the proposed SVA is not sensitive to the gradient estimation method. Here, the C3D recognition model and three randomly selected videos from the UCF101 dataset are used to conduct the experiments. For clear observation, we record each reward value (gray lines) and the corresponding average reward value computed using every 10 epochs (blue lines). The corresponding video frames are also shown below the sub-figures.

Convergence of the proposed SVA
In this subsection, the convergence of the proposed SVA is discussed. We use the change of reward value (i.e., the value computed using Eq.(9)) in different epoch to test whether SVA can obtain a convergence during the learning, which is a widely used way to see the convergence in RL. We conduct experiments under the untargeted attack setting. All experiments are based on the C3D model and UCF101 dataset. Due to the limitation of space, we show the change of reward value in the attack process of three separate videos. The reward results are recorded in Figure 10. To give a better description, we also show the corresponding video frames (Due to space constraints, only odd-numbered index frames are displayed) below the reward curve. As you can see from the figure, the reward value in each epoch in SVA is choppy (gray lines), but the average reward value per 10 epochs is growing and eventually stabilizing (blue lines). A stable and high reward means that the frame selection strategy is optimal. At the beginning of the attack, attack failure is easy to occur, but this phenomenon will be better in the later stage. The convergence can be achieved after about 20 epochs for these three videos. Actually, this phenomenon is also suitable to other videos. We also give the change of average reward computed on 20 randomly selected video attacks. The result is given in Figure 11, where we can see the reward value becomes smooth and stable with the increasing epoch. It shows the good convergence of the proposed SVA.

Conclusion
In this paper, a sparse black-box adversarial video attack algorithm with reinforcement learning was proposed for video recognition models. Due to a large amount of temporal redundancy information of video data, we explored the sparsity of adversarial perturbations in the video frames through generating adversarial perturbations only on some key video frames. Considering that keyframe selection was not only relevant to the video itself but also the feedback from the recognition model, an agent based on attacking interaction and video intrinsic properties was designed for identifying key frames while attacking. As the perturbations were generated only for the selected frames, the proposed method could reduce the perturbations of adversarial examples significantly. The proposed algorithm was applicable to multiple target models and video datasets. Moreover, the experimental results demonstrated that the proposed algorithm achieved efficient query times to the recognition models. The most pertinent area of future work is to further investigate the black-box attack using fewer queries, such as modifying the update mechanism or designing new rewards. And we hope the query number can be reduced to meet the requirement in the real world.