REPLICANT: Learning Policies for Evading and Hardening Malware Detectors

Machine Learning (ML) classifiers have become a key line of defence against malware, with extensive research focusing on improving their performance and robustness to drift. However, the field of Adversarial Machine Learning (AML) has repeatedly demonstrated the brittleness of ML-based systems under targeted modifications. Although well established, this vulnerability is often underpinned with strong assumptions, such as access to confidence scores; therefore, the question most relevant for risk assessment is not whether these detectors can be evaded, but how general and efficient an attack can be under realistic constraints.

Most evasion research operates in the feature space, directly modifying the input that is fed into ML systems. Although sufficient to evade systems such as image detection, these approaches are not applicable to crafting evasive malware due to the inverse mapping problem: a change to the feature vector does not necessarily correspond to any realizable and function-preserving change in the application. Alternatively, problem-space attacks avoid this problem by modifying the application directly while enforcing syntactical and semantic constraints; therefore, every adversarial example is a valid program by construction.

Problem-space attacks must meet the following criteria:

• (i) available transformations (realizability), using only modifications an attacker could perform in practice;
• (ii) preserved semantics, the transformations performed must preserve the original malicious behavior of the sample;
• (iii) plausibility, the sample should appear realistic upon manual inspection;
• (iv) robustness to preprocessing, the modifications should survive a realistic pre-processing pipeline.

The most established way to satisfy these constraints for problem-space Android malware attacks is gadget extraction and transplantation, where self-contained code fragments alongside their known features are harvested from benign applications and transplanted into malware. As a result of gadgets being harvested from real applications, they are realizable and plausible by construction. Furthermore, since gadget transplantation only adds benign code, and thus features (0 → 1), it preserves the original behavior (semantics) of the malware.

We therefore lack a comprehensive understanding of how evasion strategies generalize and transfer across classifiers, feature spaces, and time. To address these limitations, we propose REPLICANT: a unified Deep Reinforcement Learning (DRL) framework that learns problem-space evasion policies.

The goal of the attacker is to violate the integrity of the system by modifying malware to be classified as goodware while preserving its malicious behavior. Furthermore, in the process of achieving this goal, the attack aims to minimize the number of both malware modifications and target queries.

In the black-box setting, the attacker has no explicit knowledge of the target classifier clf_target and receives only its predicted label (i.e., either benign or malicious), rather than a confidence score. To learn an evasion policy, the attacker instead uses a surrogate classifier clf_surrogate created by themselves or others, which is trained on distinctly different data from the target. Therefore, the surrogate may also differ from the target in both classifier architecture or feature space.

In the white-box setting, the attacker has unrestricted access to the target and thus may use its confidence scores and feature-space representation. We adopt the white-box threat model for the adversarial training (AT) experiments for the following reasons. First, a defender hardening their own model has complete access to it and thus would use the strongest realistic attacker available to them. Second, isolating the robustness gained from AT is best measured using white-box attacks as adding black-box constraints conflates robustness with the difficulty of finding an evasive strategy without access to the target.

Evasion here is formulated as a sequential decision-making problem (specifically, a Markov Decision Process) where an agent observes the current representation of a modified malware sample and chooses either: (i) to submit the sample to the target; or, (ii) to modify the sample and select which capability to apply. Since each capability corresponds to a concrete problem-space modification whose effect on the feature space is known in advance, we can model and evaluate the MDP in the feature space while maintaining the problem-space realizability of every transition.

Hierarchical DRL splits a policy across different levels of abstraction, where a higher-level policy decides what to do next and a lower-level policy decides how to do it. The hierarchical action space of REPLICANT is split across two separate policies: the higher-level query policy and the lower-level modify policy. Based on s_t, REPLICANT first selects a query action, q_t ∈ {SUBMIT, MODIFY}. If q_t = SUBMIT then the classifier is queried, clf(s_t) ∈ {0, 1}, and no capabilities are applied. If q_t = MODIFY, then the modify policy selects a capability to apply to the malware sample and does not query the classifier. Action masking removes, prior to selection, any modify action whose capability either: (i) adds no new features (a no-op), or (ii) would conflict in the problem space.

The relative magnitudes of these three terms determine the trade-offs between modification and query efficiency learned by the agent. These values were chosen to: (i) ensure every successful episode has a positive return, since the total penalties over an episode of at most H steps cannot surpass R_success; and (ii) incentivize an efficient but balanced use of both modifications and queries.

During training, the query policy is masked to force periodic submits (PS). We scale the reward of these forced submits by λ_PS ∈ [0, 1]. We set λ_PS = 0 for two reasons. First, early in training the agent is usually detected when it queries and can learn to avoid querying altogether; making these periodic queries zero-cost encourages it to explore querying. Second, once the agent is more capable, λ_PS = 0 encourages the agent to voluntarily submit early to maximize reward.

A shared MLP encoder feeds three heads, each adding one further layer before its output: a query head over {SUBMIT, MODIFY}, a masked modify head over the capability set C, and a critic head estimating state value V(s_t). Training uses Proximal Policy Optimization (PPO), with the query policy loss applied at every step; the modify policy loss applied only on MODIFY steps, relying on the evasion reward being propagated through advantage estimation; and the critic is shared across both. The query and modify heads share a common entropy coefficient, encouraging exploration over both when to query and what to add.

REPLICANT is deliberately agnostic to what the problem-space capabilities are: it learns effective evasion policies given any capability set and a representation that captures how the modifications affect the sample. Our capability set comprises gadgets harvested by prior problem-space work, together with their feature-space effects we computed. Each gadget affects only a small set of features, so for each feature space we use the subset that changes at least one of its features, resulting in 3,143 for Drebin, 4,804 for APIGraph, and 1,739 for RAMDA. For cross-feature-space attacks, the attacker selects from the capability set applicable in their own feature space, and the target sees the effect of applying those gadgets in its own feature space.

In the matched setting, the surrogate and target classifiers share an architecture and feature space but are trained on separate training sets; with no difference between architecture or feature space, this setting represents the best-case scenario for a black-box attacker. REPLICANT achieves a mean ASR of 96.6% using an average of 3.6 queries per sample. The strongest baseline, APG, reaches only 77.7% while the ADZ, EvD, and random baselines sit at 61.5%–69.7%. APG is statistically tied with REPLICANT on SVM, SecSVM and DeepDrebin, where ranking capabilities by their contribution to the surrogate decision function most closely aligns with the target boundary. The gap is largest on the RL-based DRMD, where APG collapses to 25.2% against the 90.2% of REPLICANT, followed by RAMDA and RF (35.4 & 27.6 points), with every other baseline statistically beaten on every target.

In practice, an attacker rarely has a surrogate that matches the target, so we now evaluate REPLICANT across all 1,764 surrogate/target combinations, in which the surrogate and target may differ in classifier, feature space, training period, or all axes. REPLICANT achieves the highest evasion rate (78.8% ASR), beating every Android baseline by 13.6–22.2 ASR points. Since the baselines use changes in confidence to steer capability selection, as the surrogate diverges from the target, its confidence degrades as a proxy for the decision boundary of the target. REPLICANT instead learns a policy over the malware used to train the surrogate, thereby capturing the general task of evasion rather than the surrogate confidence topology.

Rnd uses the same MDP as REPLICANT, however, it selects when to query and which applicable capability to add at random. Across all settings, Rnd matches the performance of both ADZ and EvD, while approaching the performance of APG at a budget of twenty queries. This demonstrates that: (i) the environment design of REPLICANT provides performance on par with prior attacks under our threat model; (ii) the performance gains over prior attacks are the result of our learned policy; and (iii) it exposes the weakness of relying on surrogate confidence scores for black-box attacks.

To isolate the gains of our architecture and reward function, we compare against five alternative RL agent designs adapted to Android by using our environment, threat model, and capability set. We find that in comparison to prior agent designs, REPLICANT improves the mean ASR by 5.6–22.2 points across all 1,764 settings, using 1.1–5.2 less queries on average.

At a query budget of 20, REPLICANT is also the most query-efficient attacker by AvgQ, spending the fewest average queries per sample of any attack: 3.6 in the matched setting and 7.4 across all settings versus the 6.5 and 9.3 of APG, the Android strongest baseline.

Our main results use the canonical Hypercube dataset, which samples the distribution and labels applications using VirusTotal threshold of 2 (VTT2). To confirm our results are not an artifact of this threshold, we re-run the black-box experiments on a variant of Hypercube created for VTT4. Since VTT4 creates a higher standard for samples to be labeled as malware, it simplifies the detection task, dropping misclassification rates for 2022 malware from 63.8% to 46.9%. Thus VTT4 has a two-fold effect on our evaluation that makes it more favorable for the attacker: (i) it provides a larger test set as more malware are detected by all targets for a given seed and (ii) it produces more capable surrogates that provide a better proxy for the targets. These two factors result in a higher mean ASR across all attacks; REPLICANT rises from 78.8% (VTT2) to 94.1% (VTT4), remaining the dominant attacker (12.6% better than the best baseline). Therefore, since using VTT2 follows current best practice and it is the more conservative setting for attack performance, our main results give a realistic measure of attack efficacy that is not inflated by higher labeling thresholds.

To confirm the attacks are also effective in-distribution, we additionally test on the malware from the surrogate split of each target’s training year (e.g., 2021a malware for a 2021b target, and 2022a for a 2022b target). The attack remains effective, with only a minor decline in performance; the mean ASR of REPLICANT on in-distribution malware is 70.0% compared to the 78.7% of the main temporally withheld results. Furthermore, when testing on malware from two and three years after the training periods, the mean ASR rises to 89.4% and 95.4%, respectively.

We analyze both Policy Transfer Evasion (PTE), where the policy learned by REPLICANT is deployed against the target; and Sample Transfer Evasion (STE), where REPLICANT evades the surrogate, and those adversarial samples are applied directly to the target. Therefore, both attacks use identical policies, capabilities, and surrogates; they only differ in whether the learned policy is employed as an active attacker or used to pre-compute adversarial samples, as done in classical transfer attacks.

Specifically, we consider four transferability axes: the temporal gap (when training periods differ), the architecture gap (when classifiers differ), the representation gap (when feature spaces differ), and the combined gap (when all differ).

• Temporal Gap. Matching the classifier and feature space but training the surrogate and target in different periods, PTE retains a mean ASR of 96.6%, statistically indistinguishable from the matched setting. Therefore, the learned policy is effectively invariant to the temporal gap; the only appreciable difference is between 2021b and 2022b targets, which is a result of temporal luck rather than the surrogate-target gap.
• Architecture Gap. When the surrogate and target share the same feature space but differ in architecture, transfer remains strong: PTE evades 87.4% of malware within twenty queries against 44.7% for STE, and overtakes STE within roughly two queries. Given a shared representation, the learned effect that each modify action has on the feature space still holds for the target; the agent, therefore, retains an accurate model of how its capabilities change a sample. The architecture gap is thus paid foremost in queries: ASR rises slowly against the targets whose boundaries differ most from the surrogate, most notably DRMD, the only RL-trained detector, whose categorically different training regime makes its boundary the least similar to the others.
• Representation Gap. Keeping the architecture fixed while moving the surrogate and target into different feature spaces lowers ASR to 78.8%, still far above the 42.5% of sample transfer. The performance decay concentrates on pairs involving RAMDA especially when it is used as the surrogate. A policy trained on RAMDA, the smallest feature space, and deployed against a richer target space has only learned capabilities that affect a small fraction of the target representation and must therefore rely either on that sub-region to influence the decision of the target or on incidental side-effects its capabilities produce elsewhere in the larger representation. Conversely, transferring an attack into a smaller representation, such as RAMDA, can render many of its modifications invisible to the target, as they are not captured by the representation of the target. Therefore, this reduction in ASR reflects an underlying property of the representation gap rather than any intrinsic robustness of RAMDA.
• Combined Gap. This is the hardest regime, where the surrogate differs from the target in architecture, feature space, and training period. The costs of each transferability gap now compound: the policy pays in queries to push towards the shifted boundary and in expressiveness to compose capabilities in a representation it was not trained on, lowering the ASR of PTE to 73.0%, still far above the 41.4% of STE. DRMD is the hardest target to evade, which is further compounded by the representation gap to produce the slowest per-query ASR rise. Even so, PTE reaches an ASR of 41.1% against it, whereas STE reaches only 4.2%.

Despite a long history of proposed defenses against evasion attacks, adversarial training remains one of the few defenses that has consistently demonstrated empirical robustness. Evasion attacks highlight the weakness in a models decision-making; by retraining against these adversarial samples the model can become hardened or more robust against such attacks.

The robustness gained from adversarial training depends on the quality of the attacker, so we harden with the strongest attacker from each attack type (i.e., policy-based and per-sample optimization). Therefore, we use REPLICANT for learned policies and APG for per-sample optimization to provide the most informative comparison. As we are not considering transferability, and evasion rates are similar between the feature spaces in the matched setting, we focus this analysis on the Drebin feature space because it is the most widely used representation.

We also produce a white-box variant of REPLICANT (REPLICANT_WB) for use in AT and the robustness evaluations of the hardened targets. Architecturally, REPLICANT_WB drops the query head and submits after every modification, since query efficiency is not required in the white-box setting; it also uses the confidence score of the target, clf_score, for rewards. Since confidence deltas can be small, we scale them by λ_WB = 5 for all targets. Beyond architecture and reward, the rest of the REPLICANT formulation remains unchanged.

AT-REPLICANT and AT-APG follow the pipeline, however, AT-APG collects adversarial samples during its per-sample rollouts as it does not have a training phase.

We evaluate each classifier trained by both AT pipelines against both REPLICANT_WB and APG_WB attacks.

After 15 rounds, AT-REPLICANT reduces the mean ASR to 9.9% and 16.3% for REPLICANT_WB and APG_WB, respectively. Therefore, AT-REPLICANT produces classifiers that are robust against both the attack it was trained on and an unseen attacker. Conversely, AT-APG primarily reduces the mean ASR of APG_WB (35.6%) while remaining vulnerable to REPLICANT_WB (62.4%).

APG is greedy and deterministic, thus each round naturally focuses on a small sub-set of capabilities and limits the diversity of adversarial samples produced. As a result, REPLICANT_WB learns capability sequences outside from the targeted paths AT-APG trained on, and achieves a mean ASR of 62.4%. Conversely, the robustness learned by AT-REPLICANT generalizes better as it collects diverse adversarial samples during stochastic policy training, providing significantly more coverage of attack paths. Therefore, the coverage of possible paths modulates how broadly the robustness gained by AT can generalize.

AT-REPLICANT has a more adverse effect than AT-APG to the initial F₁ performance in the first test month (mean F₁ drop across classifiers of −5.6 versus −3.1). However, when considering performance-over-time, both AT pipelines increase mean A-AUT(F₁) in four of the seven total classifiers, with AT-REPLICANT hardened classifiers improving mean A-AUT(F₁) by 2.8 compared to the 1.1 gain of AT-APG. Therefore, although AT reduces initial performance, the new malware variants for training created by AT-REPLICANT mildly improve the generalization of most classifiers as samples start to drift over time.

In this section we test whether the robustness learned by the AT pipelines generalizes to unseen problem-space capabilities, which we refer to as capability drift. Therefore, we split the capability set in two: (i) the capability set used by both the AT and the initial attacker; and, (ii) the held-out attacker capabilities used to measure generalization to capability drift. Attackers are evaluated six separate times, starting with the initial capability set, and then progressively adding 10% of the total capabilities back in each subsequent evaluation.

AT-REPLICANT shows robustness against both REPLICANT_WB (8.7%) and APG_WB (14.6%), whereas AT-APG primarily against APG_WB (26.6% versus the 49.5% of REPLICANT_WB). However, as capability drift increases so does the mean ASR of REPLICANT_WB, with the full capability set reaching 91.3% (AT-REPLICANT) and 96.1% (AT-APG).

Therefore, as the attacker set changes, the two AT pipelines demonstrate similar robustness to APG_WB; however, AT-REPLICANT remains consistently more robust than AT-APG to the REPLICANT_WB attacker at every stage of capability drift (mean ASR reduction of −40.8 to −4.9 percentage points). This demonstrates that although AT-REPLICANT generalizes better to capability drift than AT-APG, AT has natural limitations with respect to the capability set it was trained against. Therefore, in practical deployments just as classifiers need active learning to adapt to temporal drift, AT must also adapt to capability drift.

Over time both goodware and malware evolve, without adaptation, the performance of a trained detector decays as new samples drift further from the training distribution. We compare five different pipelines for the classifiers against fixed REPLICANT attackers (under both the white-box and black-box settings): (i) Base, the static classifier from its respective training period; (ii) AL, which performs monthly AL updates with 400 samples selected from that period using uncertainty-based selection; (iii) AT, the AT-REPLICANT pipeline; (iv) AT&AL, the AT-REPLICANT hardened classifiers with AL across the test periods; and, (v) Robust AL (RAL). We propose RAL, which extends AL by running one AT-REPLICANT round on the malware collected each AL period and adds the resulting adversarial samples to the AL update set.

Drift adaptation (↑A-AUT(F₁)) and adversarial robustness (↓A-AUT(ASR) WB & BB) are largely orthogonal, with no prior strategy improving both metrics over the three-year evaluation. AL recovers the most clean performance of any configuration (49.8) but, as it never exposes the classifiers to adversarial samples in training, the adaptation only has a minor reduction on attack performance (98.2% WB, 88.5% BB); AT conversely suppresses the attackers to near-zero ASR, however, provides only minor robustness to temporal drift (29.5). Combining AT&AL improves performance with regards to temporal drift at the cost of adversarial robustness (19.4% WB, 20.6% BB). Finally, only our RAL, with its combination of clean and adversarial samples for retraining, improves on both axes, matching the clean performance of AL (49.0 versus 49.8) while preserving the adversarial robustness from AT (0.6% WB versus 0.1% WB).

Therefore, just as AL is needed to adapt to temporal drift, AT must continually adapt alongside it, as neither AL nor AT alone is sufficient.