{'fraction_non_alphanumeric': 0.033373652957994285, 'fraction_numerical': 0.009988270654644088, 'mean_word_length': 4.81282624906786, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Query-Efficient GAN Based Black-Box Attack Against Sequence Based Machine and Deep Learning Classifiers

In this paper we present an efficient and generic black-box attack demonstrated against API call based machine learning malware classifiers. We generate adversarial examples combining sequences (API call sequences) and other features (e.g., printable strings) that will be misclassified by the classifier without affecting the malware functionality. Opposed to previous studies, our attack minimizes the number of target classifier queries and only requires access to the predicted label of the attacked model (without the confidence level). We evaluate the attack's effectiveness against a variety of classifiers, including recurrent neural network variants, deep neural networks, support vector machines, and gradient-boosted decision trees. We show that the attack requires fewer queries and less knowledge about the attacked model's architecture than other existing black-box attacks, making it practical for attacking cloud based models at a minimal cost. We also implement a software framework that can be used to recraft any malware binary so it will not be detected by classifiers, without access to the malware source code. Finally, we discuss the robustness of this attack to existing defense mechanisms.


I. INTRODUCTION
Next generation anti-malware products use machine learning and deep learning models instead of signatures and heuristics, in order to detect previously unseen malware. In this paper, we demonstrate a novel query-efficient black-box attack against many types of classifiers, including RNN variants.
API call sequence based classifiers such as SentinelOne provide state of the art detection performance [1]- [3], however those classifiers are vulnerable to a form of attack called adversarial examples. Adversarial examples are correctly classified samples that are perturbed (modified), so they (incorrectly) get assigned a different label. In this paper, we implement our attack on binary classifiers, which are used to differentiate between malicious and benign processes based on API call sequences. We consider the challenging case of cloud prediction, termed machine learning as a service (MLaaS), such as Amazon Machine Learning or Google's Cloud Prediction, where the attacker pays for every query of the target classifier (provides input and receives classification) and therefore aims to minimize the number of queries to such a cloud service when performing an attack. Another reason for minimizing the number of queries is that many queries from the same computer might raise suspicion of an adversarial attack attempt, causing the cloud service to stop responding to those adversarial queries [4]. We develop an end-to-end attack by recrafting malware binary to evade detection by such machine learning malware classifiers.
Generating adversarial examples for images [5], [6] is the main focus of most existing research; however, this is different from generating adversarial API sequences, which is demonstrated in this paper, in two respects: 1) In adversarial API sequences one must verify that the original functionality of the malware remains intact (thus, one cannot simply generate an adversarial feature vector but must generate the corresponding valid malware binary). 2) API sequences consist of discrete symbols with variable lengths, while images are represented as matrices with fixed dimensions, and the values of the matrices are continuous.
Attacks against RNN variants exist [7]- [9], but they require many queries to the target classifier and additional knowledge of the attacked classifier, such as the encoding of the target classifier's features. Previous query-minimizing decision based attacks [10] do not target RNNs or the cyber security domain, due to this domain unique challenges. The differences between such attacks and our attack are described in Section II.
In this paper, we present two simple but effective methods to reduce the number of black-box queries needed for generating an adversarial example: 1) Logarithmic backtracking -Starting with a large ratio of perturbation (added API calls in random positions in the original sequence to fool the classifier) and rapidly decreasing the ratio as long as the sequence remains misclassified. 2) Benign perturbation -Adding API calls from sequences generated by a generative adversarial network (GAN) trained to mimic real benign sequences, instead of random API calls. This concept is similar to biological viruses (malware) which are sometimes composed of human ("benign") proteins in order to evade the immune system (malware classifier) of the host. While we focus on malware classifiers (a challenging case due to the reasons mentioned above), our attack is generic and can be applied to other domains, such as bioinformatics (using nucleic acid sequences instead of API calls).
The contributions of our paper are as follows: 1) This is the first end-to-end decision based black-box adversarial attack against all state of the art classifiers (RNN variants, feed forward DNNs, and traditional machine learning classifiers such as SVM) that minimizes the number of target model queries, in order to handle cloud attack scenarios. We focus on sequence input and the cyber security domain and explain the attack effectiveness in this domain. 2) Our attack doesn't require target model queries to train a substitute model [9] or a generative adversarial network [7] to generate the adversarial example. Thus, it does not require extensive computational power or a predeployment phase and is easier to deploy on remote hosts than previous attacks. 3) The attack doesn't require any knowledge about the target classifier, including knowledge about the training set, model type, architectures, hyperparameters, or feature encoding. Only a subset of the features used is required for this attack. 4) The attack is stochastic and therefore defense methods against deterministic adversarial attacks, such as gradient masking (e.g., distillation), are ineffective against it [10].

II. BACKGROUND AND RELATED WORK
The search for adversarial examples, such as those used in our attack, can be formalized as a minimization problem [11]: The input x, correctly classified by the classifier f , is perturbed with r such that the resulting adversarial example x+r remains in the input domain D, but is assigned a different label than x.
There are three types of adversarial example generation methods which are defined in the following subsections.

A. Gradient Based Attacks
In this type of attack, adversarial perturbations are generated in the direction of the gradient, that is, in the direction with the maximum effect on the classifier's output (e.g., FGSM [12]). Gradient based attacks are effective but require adversarial knowledge about the targeted classifier's gradients. These attacks can be conducted on the targeted model if white-box knowledge is available [13].
Our research differs from [13] in several ways: 1) [13] didn't deal with RNNs or dynamic features which are more challenging to add without harming the malware functionality. 2) [13] did not focus on a generic attack which can affect many types of classifiers, as we do. 3) Our black-box assumption is more feasible than the white-box assumption presented in [13]. [7] used an RNN GAN to generate invalid API calls and insert them into the original API sequences. Gumbel-Softmax, a one-hot continuous distribution estimator, was used to deliver gradient information between the generative RNN and substitute RNN.
Our research differs from [7] in several ways: 1) While [7] inject arbitrary API call sequences that might harm the malware functionality (e.g., by inserting the ExitProcess() API call in the middle of the malware code), our attack modifies the code such that the original functionality of the malware is preserved. 2) Our approach works in real-0world scenarios involving hybrid classifiers and multiple feature types, which are not addressed by [7]. 3) While [7] only focused on LSTM variants, we also show our attack's effectiveness against other RNN variants such as GRUs and conventional RNNs, bidirectional and deep variants, and non-RNN classifiers (including both feedforward networks and traditional machine learning classifiers such as SVM), making it truly generic. 4) The use of Gumbel-Softmax approximation in [7] makes this attack limited to one-hot encoded inputs, while in our attack, any word embedding can be used, making it more generic. 5) The stability issues associated with a GAN training [2] per sample, which might not converge for specific datasets, apply to the attack method mentioned in [7], making it hard to rely on and require more target classifier queries. While such issues might not be visible when using a small dataset (180 samples in [7]), they become more apparent when using larger datasets like ours (500,000 samples). We also use a GAN for benign perturbations, but it is optional and, if used, needs to be trained only once.
A white-box gradient based attack against RNNs demonstrated against LSTM architecture for sentiment classification of a movie review dataset was shown in [8]. A black-box variant, which facilitates the use of a substitute model, was presented in [9]. The attack in this paper is different in a few ways: 1) As shown in Section IV-B, the attacks described in [8], [9] require more target classifier queries, greater computing power to generate a substitute model, and additional knowledge about the attacked classifier (API encoding). 2) Our attack is generic for every camouflaged malware, and doesn't require a per-malware pre-deployment phase to generate the adversarial sequence (either using a GAN, as in [7], or a substitute model, as in [9]). In this paper, the generation is done at run time, making it more generic, robust against different classifiers, and easier to deploy. 3) We use a different adversarial example generation algorithm, which uses a stochastic approach rather than a gradient-based approach, making it harder to defend against (as mentioned in Section VI).

B. Score Based Attacks
These attacks are based on knowledge of the target classifier's confidence score. The target classifier's gradient can be numerically derived from the confidence scores of adjacent input points [14] and then a gradient-based attack is applied, following the direction of maximum impact, in order to generate an adversarial example.
[15] used a genetic algorithm, where the fitness of the genetic variants is defined in terms of the target classifier's confidence score, to generate adversarial examples that bypass PDF malware classifier. Their attack used a computationally expensive genetic algorithm comparing to our approach, and was evaluated only against SVM and random forest classifiers using static features only, and not against deep neural networks and recurrent neural network variants using both static and dynamic analysis features, as we do.
A common problem to all score based attacks is that the attacker knowledge of confidence scores (which is not required by our attack) is unlikely in black-box scenarios.

C. Decision Based Attacks
These attacks only use the label predicted by the target classifier. [10] starts from a randomly generated image classified as the target class and then adds perturbations that decrease the distance to the source class image, while maintaining the target classification. [16] uses natural evolutionary strategies (NES) optimization to enable query-efficient gradient estimation, which leads to generation of misclassified images like gradient based attacks. [17] uses Bayesian optimization to minimize the probability of the point to have the correct classification.
All of the currently published score and decision based attacks [10], [14], [16] differ from our proposed attack in that: 1) They only deal with convolutional neural networks, as opposed to all state of the art classifiers, including RNN variants. 2) They deal with images and don't fit the attack requirements of the cyber security domain (while changing a pixel's color i doesn't "break" the image, modifying an API call might harm the malware functionality). In addition, small perturbations suggested in [10], [14], [16] are not applicable for discrete API calls (you can't change WriteFile() to WriteFile()+0.001 in order to estimate the gradient to perturb the adversarial example in the right direction; you need to modify it to an entirely different API). 3) They did not present an end-to-end framework to implement the attack in the cyber security domain, and thus the attack might be used for generating adversarial malware feature vectors but not a working adversarial malware sample. An exception is [18], presenting a decision based attack of a reinforcement learning agent which is equipped with a set of operations (such as packing) that it may perform on the PE file. Through a series of games played against the anti-malware engine, it learns which sequences of operations are likely to result in evading the detector for any given malware sample. Unlike our attack, this attack's effectiveness is less than 25% (our attack effectiveness is about 90%). It also doesn't handle sequence features and it isn't queryefficient like our attack, either.

A. Target API Call Based Malware Classifier
Our classifier's input is a sequence of API calls made by the inspected code. In order to add API calls without harming the malware functionality, we used a no-op mimicry attack [19], that is, we addied system calls with no effect or added system calls with an irrelevant effect. Almost any API call can become a no-op if provided with the right arguments, e.g., opening a non-existent file. We focus on classifiers using only the API call type and not its arguments or return value, since IDSs that verify the arguments are 4-10 times slower than classifiers that do not verify arguments [20] and are therefore less common. However, analyzing arguments would make our attack easier to detect, e.g., by considering only successful API calls and ignoring failed API calls, or by looking for irregularities in the arguments of the API calls (e.g., invalid file handles, etc.). In order to address this issue, we use valid (non-null) arguments with a no-op effect, such as writing into a temporary file handle, instead of an invalid file handle. This is discussed in detail in Sections V-A and V-D. One should also consider that it is extremely challenging for the classifier to separate between malware that is trying to read a nonexistent registry key as an added adversarial no-op, and a benign application functionality, e.g., trying to find a registry key containing information from previous runs and creating it if it doesn't exist (for instance, if this is the first run of the application).
API call sequences can be millions of API calls long, making it impossible to train on the entire sequence at once due to training time and GPU memory constraints. Thus, we used a sliding window approach [9]: Each API call sequence is divided into size m windows. Detection is performed on each window in turn, and if any window is classified as malicious, the entire sequence is considered malicious. Thus, even cases such as malicious payloads injected into goodware (e.g., using Metasploit), where only a small subset of the sequence is malicious, would be detected. We use one-hot encoding for each API call type in order to cope with the limitations of sklearn's implementation of decision trees and random forests, as mentioned online. The output of each classifier is binary (malicious or benign). The classifiers tested and their hyperparameters are described in Appendix VIII.

B. Black-Box API Call Based Malware Classifier Attack
We present two forms of the attack: 1) Linear iteration attack -a simple attack, and 2) Logarithmic backtracking attack -a more complex and efficient attack in terms of target classifier queries. Both attacks can use either random or benign perturbations.

1) Random or Benign Perturbation Linear Iteration Attack:
In order to prevent damaging the code's functionality, we can only add API calls to the malware's code; we cannot remove or modify API calls. In order to add API calls in a way that doesn't impact the code's functionality, we generate a mimicry attack (Section III-A). Our attack is described in Algorithm 1.
The attacker splits the malicious API call sequence x m to windows of n API calls (line 2), modifying each window in turn, similar to the division made by the classifier (Section III-A). The adversarial window size n might be different from the classifier's window size m, which is not known to the attacker. As shown in Section IV-B, this has little effect on the attack performance. The same division is made for the benign API call sequence x b . The modification is the addition of either random API calls, a.k.a. random perturbation, or API calls of a benign sequence, a.k.a. benign perturbation (line 5), at random positions in the API sequence (line 4), until the modified sequence w j,m is classified as benign or more than M w API calls are added, reaching the maximum overhead limit (line 3).
D is the vocabulary of available features. Here those features are all of the API call types recorded by the target classifier, e.g., CreateFileW. Note that D is not necessarily known to the attacker. The attacker knows D ′ , which might be a subset or superset of D. This knowledge of D ′ is a commonly accepted assumption about the attacker's knowledge [21]. In fact, it is enough for the attacker to know the feature type used by the target classifier (API call types in this paper), which is public information that is usually published by classifier implementer, and then cover all API call types (several thousands) to generate D ′ , which is superset of D. In our research, we observed that API call types in D ′ − D would not be monitored by the classifier and do not assist in camouflaging: they just add API call overhead to the modified sequence and waste queries. API call types in D − D ′ would not be generated by the attack and therefore decrease the possibilities for generating modified sequences. Thus, when D ′ is a superset of D, the attack would have higher overhead but still be as effective.
The adversarial API call sequence length of l might be different than n, the length of the sliding window API call sequence that is used by the adversary. Therefore, like the prediction, the attack is performed sequentially on l n windows of n API calls. Note that the knowledge of m (the window size of the classifier, mentioned in Section III-A) is not required, as shown in Section IV-B. The adversary randomly chooses i, since he/she does not have any way to better select i without incurring significant statistical overhead. Note that the insertion of an API in position i means that the API calls from position i..n (w j,m [i..n] ) are "pushed back" one position to make room for the new API call, in order to maintain the original sequence and preserve the original functionality of the code (line5). Since the sliding window has a fixed length, the last API call, w j,m [n + 1], is "pushed out" and removed from w j,m . The API calls "pushed out" from w j,m will become the beginning of w j+1,m , so no API is ignored.
The benign sequence x b is generated by a specially crafted GAN, described below. a) Benign Perturbation: GAN Generated Benign API Call Sequence: When we add an API call to our adversarial sequence, we want to make maximum impact on the classifier's output. Thus, Algorithms 1 and 2 take x b , a benign API sequence to use, as input. One way to generate x b is by taking the API call sequence of an actual benign sample from our dataset. The downside of this approach is that those hard-coded API calls can be signed by the classifier and detected explicitly. A better approach is to generate a different benign sequence each time, using a generative model. One way to do this is to use a generative adversarial network [22], with stochastic input and output of an API call sequence that is indistinguishable (to the discriminator classifier) from actual benign sequences from the dataset. This approach is rarely used for API call sequence generation but has been used for text generation. In comparison to other approaches (e.g., VAE) a GAN tends to generate better output, as most other methods require that the generative model has some particular functional form (like the output layer being Gaussian), and all of the other frameworks require that the generative model puts non-zero mass everywhere. However, a challenge with the GAN approach is that the discrete outputs from the generative model make it difficult to pass the gradient update from the discriminative model to the generative model. Another challenge is that the discriminative model can only assess a complete sequence. We used SeqGAN [23] implementation, in which a discriminative model that is trained to minimize the binary classification loss between real benign API call sequences and generated ones. Besides the pre-training procedure that follows the MLE (maximum likelihood estimation) metric, the generator is modeled as a stochastic policy in reinforcement learning (RL), bypassing the generator differentiation problem by directly performing a gradient policy update. Given the API sequence s t = [x 0 , x 1 , ..x t−1 ] and the next API to be sampled from the model x t ∼ (x|s t ), the RL algorithm, REINFORCE, optimizes the GAN objective: The RL reward signal comes from the GAN discriminator judged on a complete sequence and is passed back to the intermediate state-action steps using Monte Carlo search, to compute the Q-value for generating each token, for the sake of variance reduction. We also tried other GAN architectures (e.g., GSGAN) but SeqGAN outperformed all of them, as shown in Section IV-B2.
2) Logarithmic Backtracking Attack: In order to decrease the number of target classifier queries (the number of calls to f (.)), we use Algorithm 2, the logarithmic backtracking attack. It uses Algorithm 3 (line 3), which is similar to Algorithm 1, for a single API call window, with added API bookkeeping and without querying the target classifier. The idea is that we only query the target classifier in Algorithm 2 after modifying M w API calls in Algorithm 3, which should be a large enough perturbation to evade the classifier; then, we start reducing the number of modified API calls by half (lines 8, 10) until the classifier detects the sample again. Finally, we restore the API calls we removed in the last iteration, half each time (line 16), until we reach a successful perturbation with a minimal number of added API calls and a minimal number of target classifier queries.
The attacker chooses the API calls to add and remove randomly. Note that the only API calls that are being removed are no-op API calls that were added by the adversary and not the malware's original API calls, in order to prevent harming its functionality. Since we add or remove half of the API calls each time, we perform O(lg n) queries per adversarial sliding window in Algorithm 2, instead of O(n) queries performed in Algorithm 1, where n is the size of adversarial sliding window.
1 Input: f (black-box model), x m (malicious sequence to perturb), x b (benign sequence to mimic), n (size of adversarial sliding window), D ′ (adversarial vocabulary), M w (maximum API modifications per window), isBenignP erturb (use benign perturbation) 2 for each sliding windows w j,m , w j,b of n API calls in # Remove added API calls until evasion is lost: 7 Randomly split addedAP Is into two equally sized groups: remainingAP Is, deletedAP Is Remove remainingAP Is instead of deletedAP Is from w j *

14
# While there are still added API calls that were removed, add them back until evasion is restored: 15 recoveredAP Is =Randomly pick half of the API calls remaining in deletedAP Is 16 Add recoveredAP Is to w j * The exact numbers are presented in Section IV-B. While the proposed attack is designed for API call based classifiers, it can be used for any adversarial sequence generation.

A. Dataset and Target Malware Classifiers
We use the same dataset used in [9], because of its size: it contains 500,000 files (250,000 benign samples and 250,000 malware samples), faithfully representing the malware families in the wild and allowing us a proper setting for attacks comparison. Details are shown in Appendix VII. Each sample was run in Cuckoo Sandbox, a malware analysis system, for two minutes per sample. The API call sequences generated by the inspected code during its execution were extracted from the JSON file generated by Cuckoo Sandbox. The extracted API call sequences are used as the malware classifier's features. The samples were run on Windows 8.1 OS, since most malware targets the Windows OS. Anti-sandbox malware were filtered to prevent dataset contamination (see Appendix VII). After filtering, the final training set size is 360,000 samples, 36,000 of which serve as the validation set. The test set size is 36,000 samples. All sets are balanced between malicious and benign samples.
There are no commercial trail version or open source API call based deep learning intrusion detection systems available (such commercial products target enterprises and involve supervised server installation). Dynamic models are also not available in VirusTotal. Therefore, we used the malware classifiers shown in Appendix VIII. Many classifiers are covered, allowing us to evaluate the attack effectiveness against many types of classifiers.
The API call sequences are split into windows of m API calls each, and each window is classified in turn. Thus, the input of all of the classifiers is a vector of m = 140 (larger window sizes didn't improve the classifier's accuracy) API call types with 314 possible values (those monitored by Cuckoo Sandbox). The implementation and hyperparameters (loss function, dropout, activation functions, etc.) of the target classifiers are described in Appendix VIII. The malware classifiers' performance and architecture are presented in Appendix VIII. On the test set, all DNNs have an accuracy higher than 95%, and all other classifiers have an accuracy higher than 90%. The false positive rate of all of the classifiers varied between 0.5-1%.

B. Attack Performance
In order to measure the performance of an attack, we consider three factors.
The attack effectiveness is the number of malicious samples which were correctly classified by the target classifier but the adversarial sequence generated from them by Algorithm 2 (Algorithm 1 has similar results with more queries) were misclassified as benign by the target classifier.
We also consider the overhead incurred as a result of the proposed attack. The attack overhead is the average number of API calls which were added by Algorithm 2 to a malware sample successfully detected by the target classifier, so that the modified sample is misclassified as benign (therefore this was only calculated for successful attacks) by the target model, as a percentage of the total number of sample API calls: The average length of the API call sequence is: avg(l m ) ≈ 100, 000. We used a maximum of M w = 70 additional API calls per window of m = 140 API calls. While not shown here due to space limits, higher M w values cause higher attack effectiveness, overhead, and queries. The performance of algorithm 2 is presented in Table I (average of five runs). The performance of Algorithm 1 is very similar.
As can be seen in Table I, the proposed attack has high effectiveness against all of the tested malware classifiers. The attack effectiveness is lower for traditional machine learning algorithms, e.g., for SVM and logistic regression. This is due to the linear correlations between their features, which cause many API calls in the sequence to have a low weight; modifying those API calls have little impact. In contrast, neural networks have many layers of nonlinear correlations between the features, so modifying the correct API would have significant impact on the target classifier's output.
Finally, we consider the average number of target classifier queries the attacker performs per sample. The attacker aims to minimize this number, since in cloud scenarios, each query costs money and increases the probability of adversarial attempt detection. The number of target classifier queries used appear in Table II (average of five runs).
We see that Algorithm 2 results in similar performance using fewer queries. Benign perturbation has better performance than random API calls. While this is not surprising (since adding "benign API calls" makes the API call trace more similar to benign sequences), one might wonder about why random perturbation is effective at all. This is discussed in Section VI. We also discuss why benign perturbation better fits other domains (e.g., NLP) compared to random perturbation in Section VI.
For simplicity and to reduce the amount of training time, we used m = n for Algorithm 3, i.e., the sliding window size of the adversary is the same as that used by the target classifier. However, even if this is not the case, the attack effectiveness is not significantly degraded. If n < m, the adversary can only modify a subset of the API calls affecting the target classifier, and this subset might not be diverse enough to affect the classification as desired, thereby reducing the attack effectiveness. If n > m, the adversary would keep trying to modify different API calls' positions in Algorithm 3, until he/she modifies the ones impacting the target classifier as well, thereby increasing the attack overhead without affecting the attack effectiveness. For instance, when n = 100, m = 140,  there is an average decrease in attack effectiveness from 87.96% to 87.94% for an LSTM classifier. The closer n and m are, the better the attack performance. We used D = D ′ , except D ′ did not contain any API type that might harm the code's functionality. From the 314 API calls monitored by Cuckoo Sandbox, only two API types were omitted: ExitWindowsEx() and NtTerminateProcess().
1) Comparison to Previous Work: There are three published adversarial attacks against RNN variants. Attacks that minimize the query numbers, but works only for CNNs, like [10], [16], [17], are irrelevant because they do not work for sequence input. We compared our work against Rosenberg et al. 2018 ( [9]), since it provides state of the art performance against a wide range of classifiers. Comparison to [8] for the IMDB dataset yielded similar results for the LSTM classifier used by this attack. Because this is a white-box, rather than a black-box attack like ours, a substitute model was trained for it, resulting in an even higher number of queries. [7] provides inferior attack performance, but more importantly, the use of target classifier queries to train a generative adversarial network requires even more queries than training a simple substitute model [9] due to the GAN's complexity and convergence issues [2].
The performance of Rosenberg et al. 2018 and our attack (Algorithm 2) is presented in Tables I and II. While our attack effectiveness is lower by 10% on average and our attack overhead is also higher due to its stochastic nature, the number of queries in our attack is lower by at least two orders of magnitude. This is due to the fact that while generating a substitute model allows the attacker to choose the most impactful API calls, resulting in fewer API calls added, the substitute model creation requires many target classifier queries. One might claim that the same substitute model can be used to camouflage more than a single malware sample. However, this is not a realistic scenario: an attacker usually tries to modify only a single malware, so it can bypass the detector and perform its malicious functionality. Moreover, even if the average cost per example can be reduced by using the same substitute model, our attack presents a much lower bound limit on the absolute number of queries. Thus, our attack can not be easily mitigated by a cloud service that blocks access for a host performing many queries in a short amount of time. The more efficient the attack the less chances there are for it to be mitigated by this approach. Since our main objective in this paper is minimizing the target queries, our proposed attack outperforms existing methods.
2) Benign Perturbation GAN Comparison: To implement the benign perturbation GAN, we tested several GAN types, using TexyGEN [24] with its default parameters. We use MLE training as the pretraining process for all baseline models except GSGAN, which requires no pretraining. In pretraining, we first train 80 epochs for a generator, and then train 80 epochs for a discriminator. The adversarial training comes next. In each adversarial epoch, we update the generator once and then update the discriminator for 15 mini-batch gradients. Due to memory limitations, we generated only one sliding window of 140 API calls, each with 314 possible API call types, in each iteration (that is, generating w b and not x b as in Section III-B). As mentioned in Section III-B1a, we tested several GAN implementations with discrete sequence output. We trained our GAN using half of the benign test set (9,000 sequences). Next, we run Algorithm 2 (logarithmic backtracking attack) on the 9,000 API call traces generated by the GAN. Finally, we used the other half of the benign training set (9,000 sequences) as a test set. The results for the LSTM classifier (other classifiers behave the same) are shown in Table III.
We can see from the table that SeqGAN outperforms all other models in all of the measured factors.

A. Adding API Calls Without Damaging Functionality
The method we chose to use in order to add API calls without damaging the malware functionality is implementing a no-op attack, adding API calls which would have no effect on the code's functionality.
To avoid the target classifier ignoring our added no-op API calls due to a return value indicating of a failure, we implemented the API addition by adding no-op API calls with valid parameters, e.g., reading zero bytes from a valid file. This makes detecting the no-op API calls much harder, since the API call runs correctly, with a return value indicative of success.
To avoid the target classifier ignoring hard-coded arguments that would cause a no-op, we devised a more generic handling of API call arguments, as shown in Section V-D.
As mentioned in Section IV-B, we don't add API types which cannot be no-opped and always affect the malware functionality. Only two such API types are monitored by Cuckoo Sandbox: ExitWindowsEx() and NtTerminateProcess().

B. Implementing End-to-End Framework
In order to implement the adversarial attack end-to-end and add the API calls to a malware binary as described in the previous sub-section, we developed BADGER: Benign API aDversarial Generic Example by Random perturbation framework. This is an end-to-end attack generation framework that receives as input a malware binary to evade a target malware classifier (f in Section III-B1) and optionally an API call sequence classified as benign by f (for benign perturbation), and outputs a modified malware binary whose API call sequence is misclassified by f as benign with high probability (Section IV-B).
BADGER was inspired by GADGET, the framework implemented in [9]. Both frameworks contain the following features: 1) The same code works for every adversarial sample (i.e., no adversarial example-specific code is written). This makes the framework more robust to modification of the malware classifier model, preventing another session of malware code modification and testing. 2) No access to the malware source code is needed (access is only needed to the malware binary executable).
However, unlike GADGET, our code is not malware samplespecific, and no pre-deployment phase before the framework runs on a remote machine is required. This makes BADGER easier to use and deploy. This also supports evasive lateral movement between hosts with different malware classifiers, because the code generated is effective against every malware classifier and not targeted to a specific substitute model. The configuration used by BADGER therefore contains only the GAN-generated benign API call sequence (which is the same for every malware being camouflaged), instead of the malwarespecific API additions, as done in GADGET. In contrast, in BADGER, those additions are performed randomly throughout the malware API call trace in run-time.
The implementation is similar to GADGET: wrapping the malware binary with proxy code between the malware code and the OS DLLs implementing the API calls (e.g., ker-nel32.dll). The wrapper code implements Algorithm 3 to generate the adversarial sequence for the malware binary by hooking all of the API calls that the attacker believes are monitored by the malware classifier (D ′ in Section III). These hooks call the original API calls (to preserve the original malware functionality), keep track of the API sequences executed so far, and call the adversarial example's additional API calls in the proper position so they will be monitored by the malware classifier, instead of hard-coding the adversarial sequence to the code. Those API calls are either random (the isBenignP erturb = F alse case in Algorithm 3) or based on the configuration file, containing the GAN based API call trace classified as benign by the target classifier (the isBenignP erturb = T rue case in Algorithm 3).
Like GADGET, we generated a new malware binary that contains the wrapper's hooks by using IAT Patcher to patch the malware binary's IAT, redirecting the IAT's API calls' addresses to the matching C++ wrapper API hook implementation and adding special hooks for the LdrGetProcedureAddress()\GetProcAddress() hook to handle dynamic library calls transparently.
The code is a proof of concept and does not cover all corner cases, e.g., packing the wrapper code to evade statically signing it as malicious (dynamic analysis of it is challenging, since its functionality is implemented inline, without external API calls) or wrapping a packed malware, which requires special handling for the IAT patching to work.

C. Modified Malware Functionality Validation
In order to automatically verify that we do not harm the functionality of the malware we modify, we monitored each sample in Cuckoo Monitor before and after the modification. For all of the 18,000 modified samples, the API call sequence after the modification was the same as before the modification when comparing API call type, return value, and order of API calls, except for the added API calls, whose return value is always a success value. This means that the malware functionality is intact.

D. Handling API Arguments
We now modify our attack to evade classifiers that analyze arguments as well. In order to represent the API call arguments, we used MIST [28], as was done in other studies [29]. MIST (Malware Instruction Set) is a representation for monitored behavior of malicious software, optimized for analysis of behavior using machine learning. Each API call translates to an instruction. Each instruction has levels of information. The main idea underlying this arrangement is to move "noisy" elements, such as the loading address of a DLL,  [26] 88. 19 14.06 20.43 MaliGAN [27] 86.67 15.12 22.74 to the end of an instruction, while discriminative patterns, such as the loaded DLL file path, are kept at the beginning of the instruction. We used malware classifiers trained with MIST level 2 instructions/arguments. To handle MIST arguments, we modified our attack in the following way: Each of the MIST level 2 arguments are randomized from a set of possible noop alternatives. A diverse range of alternative values for each argument is crucial to prevent signing specific no-op argument values as malicious indicators e.g., a file path is chosen from several temporary file paths, a URL is selected from a range of valid URLs like www.google.com, etc. When an adversarial API needs to be added, the API call type is chosen randomly or based on our GAN (as described in Section V-B), and the arguments are randomly selected from the range of alternative values for each MIST level 2 argument. Handling other API arguments (and not MIST level 2) would be similar but require more preprocessing (generating random possibilities for every argument, etc.) with a negligible effect on the classifier accuracy [9]. Thus, focusing only on the most important arguments (MIST level 2) that can be used by the classifier to distinguish between malware and benign software, as done in other papers ( [1]), proves that analyzing arguments is not an obstacle for the proposed attack.
When using M w = 30 (maximum API modifications per window of size m = 140 API calls) to reduce the attack overhead, we achieved an attack effectiveness of 73.62% with overhead of 21.43%.

E. Handling Multiple Feature Types and Hybrid Classifiers
Combining several types of features might make the classifier more resistant to adversarial examples against a specific feature type. For instance, some real world next generation anti-malware products are hybrid classifiers, combining both static and dynamic features for a better detection rate [1]. An extension of our attack to handle hybrid classifiers is straightforward: attacking each feature type in turn using Algorithms 1 or 2. If the attack against a feature type fails, we continue and attack the next feature type until a benign classification by the target model is achieved or all feature types have been (unsuccessfully) attacked. We used the same hybrid malware classifier specified in Appendix IX.
When attacking only the API call sequences using the hybrid classifier, without modifying the static features of the sample, the attack effectiveness decreases to 23.76%, compared to 89.67% against a classifier trained only on the dynamic features, meaning that the attack was mitigated by the use of additional features. When attacking only the printable string features (again, assuming that the attacker has the knowledge of D ′ = D, which contains the printable strings being used as features by the hybrid classifier), the attack effectiveness is 28.25%, compared to 88.31% against a classifier trained only on the static features. Finally, the combined attack's effectiveness against the hybrid model was 90.06%. Other classifier types provide similar results, which are not presented here due to space limits.
To summarize, we have shown that while the use of hybrid models decreases the specialized attacks' effectiveness, our suggested hybrid attack performs well, with high attack effectiveness. While not shown due to space limits, the attack overhead isn't significantly affected.

VI. CONCLUSIONS AND FUTURE WORK
In this paper, we presented the first black-box attack that generates adversarial sequences and minimizes the number of queries for the target classifier, making it suited to attack cloud models. We demonstrated it against API call sequence based malware classifiers and verified the attack effectiveness against all relevant common classifiers: RNN variants, feed forward networks, and traditional machine learning classifiers. This is the first query-efficient decision based attack effective against RNN variants as well as CNNs. We also created the BADGER framework, showing that the generation of the adversarial sequences can be done end-to-end, in a generic way at the endpoint, without access to the malware source code, and, unlike previous adversarial attacks, without generating a costly substitute model, both in terms of classifier queries and the computing resources needed. Finally, we showed that the attack is effective even when API call arguments are analyzed or multiple feature types are used. Our attack is the first practical end-to-end attack dealing with all of the subtleties of the cyber security domain, without the need for a pre-deployment stage, making it suitable for sophisticated malware performing lateral movement between endpoints with different next generation anti-malware products. While this paper focuses on API calls and printable strings as features, the proposed attack is valid for every modifiable feature type, sequence or not. Furthermore, our attack is generic and can be applied to other domains, like text analysis (using word sequences instead of API calls).
One might expect an attack effectiveness of about 50%, and not 90%, when using random perturbation: either the random API helps or it doesn't. However, one should consider the domain in question: there is a limited and specific range of behaviors shown by malware (keyboard logging, file encryption, etc.) compared to goodware (Web browsers, word processors, etc.). Thus, adding API calls that are not part of the expected dynamic behavior of any malware might fool the classifier into labeling it as benign.
This sort of "domain overfitting" would not necessarily exist in other domains, e.g., sentiment analysis. In such cases, random perturbation would be less effective. However, even in those cases, a target class perturbation of a GAN generated sequence mimicking the target class samples, similar to our benign perturbation, would still be effective, making our attack generic in those cases as well.
Our future work will focus on defense mechanisms against such attacks. To the best of our knowledge, there is currently no published and evaluated method to either detect or mitigate RNN adversarial sequences. Moreover, existing papers on defense mechanisms against non-sequence attacks are focused on gradient based attacks, and thus are rarely effective against random perturbation attacks. For instance, distillation [10] can mask the gradient, but this has no effect on the attack if you choose an API call without calculating the gradient, as we have done. Adversarial training [12] is also less effective against random attacks, because a different stochastic adversarial sequence is generated every time, making it challenging for the classifier to generalize from one adversarial sequence to another. A comprehensive review of those defense methods and their effectiveness against stochastic attacks will also be a part of our future work.

VII. APPENDIX: TESTED DATASET
We used identical implementation details (e.g., dataset, classifiers' hyperparameters, etc.) as [9], so the attacks can be compared. Those details are added here, for the reader's convenience.
An overview of the malware classification process is shown in Figure 1, taken from [9]. The dataset being used is large and includes the latest malware variants, such as the Cerber and Locky ransomware families. Each malware type (ransomware, worms, backdoors, droppers, spyware, PUA, and viruses) has the same number of samples, to prevent a prediction bias towards the majority class. 20% of the malware families (such as the NotPetya ransomware family) were only used in the test set to assess generalization to an unseen malware family. 80% of the malware families (such as the Virut virus family) were distributed between the training and test sets, to determine the classifier's ability to generalize to samples from the same family. The temporal difference between the training set and the test set is six months (i.e., all training set samples are older than the test set samples), based on VirusTotal's 'first seen' date. The ground truth labels of the dataset were determined by VirusTotal, an online scanning service, which contains more than 60 different security products. A sample with 15 or more positive (i.e., malware) classifications from the 60 products is considered malicious. A sample with zero positive classifications is labeled as benign. All samples with 1-14 positives were omitted to prevent false positive contamination of the dataset.
It is crucial to prevent dataset contamination by malware that detects whether the malware is running in a Cuckoo Sandbox (or on virtual machines) and if so, quits immediately to prevent reverse engineering efforts. In those cases, the sample's label is malicious, but its behavior recorded in Cuckoo Sandbox (its API call sequence) isn't, due to its antiforensic capabilities. To mitigate such contamination of the dataset, two countermeasures were used: 1) Considering only API call sequences with more than 15 API calls (as in [1]) and omitting malware that detect a virtual machine (VM) and quits, and 2) Applying YARA rules to find samples trying to detect sandbox programs such as Cuckoo Sandbox and omitting all such samples. One might argue that the evasive malware that applies such anti-VM techniques are extremely challenging and relevant, however, in this paper we focus on the adversarial attack. This attack is generic enough to work for those evasive malware as well, assuming that other mitigation techniques (e.g., anti-anti-VM), would be applied.

VIII. APPENDIX: TESTED MALWARE CLASSIFIERS
As mentioned in Section IV-A, we used the malware classifiers from [9], since many classifiers are covered, allowing us to evaluate the attack effectiveness (Equation 2) against many classifier types. The maximum input sequence length was limited to m = 140 API calls, since longer sequence lengths, e.g., m = 1000, had no effect on the accuracy, and padded shorter sequences with zeros. A zero stands for a null API in our one-hot encoding. Longer sequences are split into windows of m API calls each, and each window is classified in turn. If any window is malicious, the entire sequence is considered malicious. Thus, the input of all of the classifiers is a vector of m = 140 API call types in one-hot encoding, using 314 bits, since there were 314 monitored API call types in the Cuckoo reports for the dataset. The output is a binary classification: malicious or benign. An overview of the LSTM architecture is shown in Figure 2a.
The Keras implementation was used for all neural network classifiers, with TensorFlow used for the backend. XGBoost and scikit-learn were used for all other classifiers.
The loss function used for training was binary cross entropy. The Adam optimizer was used for all of the neural networks. The output layer was fully connected with sigmoid activation for all neural networks. For neural networks, a rectified linear unit, ReLU (x) = max(0, x), was chosen as an activation function for the input and hidden layers due to its fast convergence compared to sigmoid() or tanh(), and dropout was used to improve the generalization potential of the network. A batch size of 32 samples was used.
The classifiers also have the following classifier-specific hyper parameters: • DNN -two fully connected hidden layers of 128 neurons, each with ReLU activation and a dropout rate of 0.2.
• CNN -1D ConvNet with 128 output filters, a stride length of one, a 1D convolution window size of three, and ReLU activation, followed by a global max pooling 1D layer and a fully connected layer of 128 neurons with ReLU activation and a dropout rate of 0.2. • RNN, LSTM, GRU, BRNN, BLSTM, bidirectional GRU -a hidden layer of 128 units, with a dropout rate of 0.2 for both inputs and recurrent states. • Deep LSTM and BLSTM -two hidden layers of 128 units, with a dropout rate of 0.2 for both inputs and recurrent states in both layers. • Linear SVM and logistic regression classifiers -a regularization parameter C=1.0 and L2 norm penalty. • Random forest classifier -10 decision trees with unlimited maximum depth and the Gini criteria for choosing the best split. • Gradient boosted decision tree -up to 100 decision trees with a maximum depth of 10 each. The classifiers' performance was measured using the accuracy ratio, which gives equal importance to both false positives and false negatives (unlike precision or recall). The false positive rate of the classifiers varied between 0.5-1%. 1 The performance of the classifiers is shown in Table IV. The accuracy was measured on the test set, which contains 36,000 samples. As can be seen in Table IV, the LSTM variants are the best malware classifiers, in terms of accuracy, and, as shown in Section IV-B, BLSTM is also one of the classifiers most resistant to the proposed attack.

IX. APPENDIX: TESTED HYBRID MALWARE CLASSIFIERS
As mentioned in Section IV-B.4, we used the hybrid malware classifier used in [9], with printable strings inside a PE file as our static features. Strings can be used, e.g., to statically identify loaded DLLs and called functions, and recognize modified file paths and registry keys, etc. Our architecture for the hybrid classifier, shown in Figure 2b, is: 1) A static branch that contains an input vector of 20,000 Boolean values: for each of the 20,000 most frequent strings in the entire dataset, do they appear in the file or not? (analogous to a similar procedure used in NLP, which filters the least frequent words in a language). 2) A dynamic branch that contains an input vector of 140 API calls, each one-hot encoded, inserted into an LSTM layer of 128 units, and sigmoid activation function, with a dropout rate of 0.2 for both inputs and recurrent states. This vector is inserted into two fully connected layers with 128 neurons, a ReLU activation function, and a dropout rate of 0.2 each. The 256 outputs of both branches are inserted into a fully connected output layer with sigmoid activation function. Therefore, the input of the classifier is a vector containing 20,000 Boolean values and 140 one-hot encoded API call types, and the output is malicious or benign classification. All other hyperparameters are the same as in Appendix VIII.
Due to hardware limitations, a subset of the dataset was used as a training set: 54,000 training samples and test and validation sets of 6,000 samples each. The dataset was representative and maintained the same distribution as the dataset described in Section IV-A. Trained on this dataset, a classifier using only the dynamic branch ( Figure 2a) achieves 92.48% accuracy on the test set, a classifier using only the static branch attains 96.19% accuracy, and a hybrid model, using both branches (Figure 2b) obtains 96.94% accuracy, meaning that using multiple feature types improves the accuracy.