Sparse Black-box Video Attack with Reinforcement Learning

The attack algorithm in our method is built based on Fast Gradient Sign Method (FGSM) goodfellow2014explaining , which is originally designed for image models. It is defined as:

where $\alpha$ is the step size. $sign(\cdot)$ is sign function. $\widehat{g}$ is the gradient, in white-box attacking setting, $\widehat{g}$ can be computed using $\triangledown_{x}l_{adv}(x)$. Here $l_{adv}(x)$ is abbreviated for adversarial loss function, which is described with $l_{adv}(x)=-l(F(x),\bar{y})$ in un-targeted attack and $l_{adv}(x)=l(F(x),y_{adv})$ in targeted attack. $l(\cdot)$ is a cross-entropy loss. Due to black-box settings, we cannot get the gradient from the recognition model directly, NES wierstra2014natural algorithm is used as gradient estimator in the proposed method. For NES algorithm, it first generates $n/2$ values $\delta_{i}\backsim N(0,I),i\in\{1,2...n/2\}$, where $n$ is the number of samples. Then, it sets $\delta_{j}=-\delta_{n-j+1},j\in\{(n/2+1),..n\}$. Finally, the gradient $\widehat{g}$ is estimated as:

where $\Delta$ 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 cheng2019query ; cheng2019sign ; liu2019signsgd 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 $\epsilon=||x_{adv}-x||_{\rho}$ is large. Next, we will gradually decrease the perturbations’ magnitude $\epsilon$ until the given bound $\epsilon_{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 un-targeted 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.

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) hochreiter1997long topped with a fully connected (FC) layer. The BiLSTM produces corresponding hidden states $\{h_{t}\}^{T}_{t=1}$. We use the ResNet18 he2016deep 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 $\sigma$ predicts a probability $p_{t}$ for each frame, and then the key frames $a_{t}$ are sampled via a Bernouli function:

where $a_{t}\in\{0,1\}$ indicates whether the $t^{th}$ frame is selected or not. $W$ is the weights of the full connection layer. $h_{t}=\phi(v_{t})$, and $\phi(\cdot)$ 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}$ zhou2018deep . 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(\cdot,\cdot)$ 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, $\mathbb{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 $\gamma_{1}$ and $\gamma_{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(-\mathbb{P}/0.05)$, i.e., if the mean absolute perturbation is small, $exp(-\mathbb{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(-\mathbb{P}/0.05)$ for any $\mathbb{P}$. For queries more than 15000 and less than 30000, we add a penalty on $exp(-\mathbb{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 $\pi_{\theta}$ with parameters $\theta$ by maximizing the expected reward $J(\theta)=E_{\tau\backsim\pi_{\theta}}[R(\tau)]$. Following the REINFORCE algorithm proposed by Williams Williams1992Simple , 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 $\theta$ via Adam kingma2015adam: . We update $\theta$ as: $\theta=\theta+ls\cdot\triangledown_{\theta}J(\theta)$, where $ls$ is learning rate and set to $10^{-5}$ in our experiments.

Here, the whole process of our method in the targeted setting is described in Algorithm 1, which is a continuous-learning algorithm. The epsilon decay $\triangle_{\epsilon}$ is used to control the reduction size of the perturbation bound. $\triangle_{\epsilon}$ and FGSM step size $\alpha$ 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.

To follow the query limited black-box settings and make our experiments more convenient, the maximum query number is set to $3\times 10^{4}$ in the un-targeted mode and $6\times 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 $\Delta$ 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 $\alpha$ adopts the strategy in madry2017towards . For the targeted attack, we adjust the step size $\alpha$ and epsilon decay $\vartriangle_{\epsilon}$ dynamically. If the proportion of the adversarial examples cannot be maintained above the threshold 50%, the step size $\alpha$ is halved. If we can’t reduce the perturbation size $\epsilon$ after 20 times in a row, we cut the epsilon decay $\vartriangle_{\epsilon}$ in half.

There are three hyperparameters in our method, and we obtain their best values via parameter tuning experiments. The $\mathbb{P}$ in Eq.(8) is automatically updated in the algorithm, but we need to set its maximum value $\epsilon_{adv}$. In Eq.(9), we need tune $\gamma_{1}$ and $\gamma_{2}$. When $\gamma_{1}$ is tuning, we fix $\gamma_{2}$, and vice versa. The tuning results are given in Figure 3. From the figure, we see $\gamma_{1}=2$ and $\gamma_{2}=3$ are the reasonable choices. As for $\epsilon_{adv}$, we find that FR (the bigger, the better) and MAP (the lower, the better) reach a balance when $\epsilon=0.05$. Therefore, we set the maximum adversarial perturbations magnitude to $\epsilon_{adv}=0.05$ per frame, and this setting is also applied to other video attack algorithms in the experiment.

The datasets and recognition models used in the experiments are described in detail here.

Datasets. Two widely used datasets, UCF-101 soomro2012ucf101: and HMDB-51 kuehne2011hmdb , 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 hara2018can and also used in wei2019sparse . 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, Long-term Recurrent Convolutional Networks (LRCN) Donahue2014Long and C3D hara2018can 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 szegedy2016rethinking 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 Spatio-temporal 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.

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\times 10^{4}$ in the un-targeted mode and $6\times 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 $\epsilon$ 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 Omid2020Pick ; 2016deepfool ; xie2017adversarial 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 $\mid pixel_{x_{i}}\mid$ 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.

Sparsity (S). 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.

We compare our Sparse Video Attack (SVA) method with Opt-attack cheng2019query and Heuristic-attack wei2019heuristic . For Opt-attack, 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 $\theta$ via Adam and update $\theta$ as: $\theta=\theta+ls\triangledown_{\theta}(J_{\overline{R_{attack}}}+L_{percentage})$, where $J_{\overline{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.

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 Opt-attack 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 “BodyWeightSquats”. 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.

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 experimental 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.

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 un-targeted 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.