Tarallo: Evading Behavioral Malware Detectors in the Problem Space

Gabriele Digregorio, Salvatore Maccarrone, Mario D’Onghia, Luigi Gallo, Michele Carminati, Mario Polino, Stefano Zanero · 2025

Read Tarallo: Evading Behavioral Malware Detectors in the Problem Space by Gabriele Digregorio, Salvatore Maccarrone, Mario D’Onghia, Luigi Gallo, Michele Carminati, Mario Polino, Stefano Zanero (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-02660.txt.

Introduction

Gabriele Digregorio and co-authors build an attack that fools behavior-based malware detectors, in work from 2025. Such detectors watch what a program does and sort it with machine learning. The catch is that the same malware can act quite unlike itself from run to run, so a tweak that fools one run may fail on the next.

Their framework, Tarallo, pairs a faster search method for sequence data with two tricks built for that run-to-run spread. In tests in a sandbox and against two neural detectors, it reached success rates up to ninety-nine percent. It won in both open and closed settings, while changing the malware as little as possible. The work exposes a weak point defenders must plan for.

Catalog record

CREATORGabriele Digregorio, Salvatore Maccarrone, Mario D’Onghia, Luigi Gallo, Michele Carminati, Mario Polino, Stefano Zanero
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE55 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-02660

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tarallo: Evading Behavioral Malware Detectors in the Problem Space Gabriele Digregorio, Salvatore Maccarrone, Mario D’Onghia, Luigi Gallo, Michele Carminati, Mario Polino, Stefano Zanero Abstract Machine learning algorithms can effectively classify malware through dynamic behavior but are susceptible to adversarial attacks . Existing attacks, however, often fail to find an effective solution in both the feature and problem spaces. This issue arises from not addressing the intrinsic nondeterministic nature of malware, namely executing the same sample multiple times may yield significantly different behaviors. Hence, the perturbations computed for a specific behavior may be ineffective for others observed in subsequent executions. In this paper, we show how an attacker can augment their chance of success by leveraging a new and more efficient feature space algorithm for sequential data, which we have named PS-FGSM , and by adopting two problem space strategies specially tailored to address nondeterminism in the problem space. We implement our novel algorithm and attack strategies in Tarallo , an end-to-end adversarial framework that significantly outperforms previous works in both white and black-box scenarios. Our preliminary analysis in a sandboxed environment and against two RNN ( RNN )-based malware detectors, shows that Tarallo achieves a success rate up to 99% on both feature and problem space attacks while significantly minimizing the number of modifications required for misclassification. ML Machine Learning DL Deep Learning AML Adversarial Machine Learning DNN Deep Neural Network RNN Recurrent Neural Network LSTM Long Short-Term Memory API Application Programming Interface GAN Generative Adversarial Network FGSM Fast Gradient Sign Method PS-FGSM Position Sensitive - Fast Gradient Sign Method PE Portable Executable LKB Longest Known Behavior BCO Behavior Cascade Optimization TPR True Positive Rate FPR False Positive Rate CNN Convolutional Neural Network AUC Area Under the Curve IDS Intrusion Detection System This paper has been accepted at the International Conference on Detection of Intrusions and Malware, and Vulnerability Assessment (DIMVA ’24). Cham: Springer Nature Switzerland, 2024. 1 Introduction Malware detectors rely on software analysis techniques to identify malicious programs. These techniques are grouped into two main categories: static and dynamic . Static analysis techniques examine the code without running the program, such as strings or IP addresses within the code [ 20 ] . While providing a fast way to analyze software, static analysis falls short against obfuscated samples [ 11 , 48 , 16 , 53 ] . On the other hand, dynamic analysis gathers information while the program is running, capturing its dynamic behavior . This includes system calls, network traffic, and memory usage. One commonly employed dynamic feature is the sequence of executed API ( API ) calls, which can effectively represent the program functions and goals. ML ( ML ), and particularly DL ( DL ), can be employed to detect or classify malware, leveraging both static [ 38 , 4 , 5 ] and dynamic [ 39 , 54 , 32 ] features. They represent a more effective alternative to traditional approaches focusing on pattern identification (e.g., byte signatures) or heuristics due to their well-understood generalization capabilities [ 31 , 7 ] . Nonetheless, ML algorithms are susceptible to adversarial attacks, which consist in forcing an ML model to misclassify specially perturbed samples [ 18 ] . These attacks may heavily impact the reliability of ML for cybersecurity applications, forcing their advocates to preemptively research and address vulnerabilities. A substantial body of work in adversarial attacks against static analysis and ML -based malware detectors exists in the literature [ 24 , 23 , 45 , 27 , 10 ] . Fewer works have addressed the security of classifiers employing dynamically extracted features. Of great relevance are the works by Rosenberg et al. [ 43 , 42 ] , which introduced an adversarial framework that can target a variety of ML -based malware detectors that employ API call sequences. The authors also discussed and showed how to modify a program’s dynamic behavior without breaking its functionality, an essential requirement for the attack to be considered successful, formally known as preserved semantics [ 35 ] . However, these works do not explicitly discuss or evaluate the real impact of their attacks in the problem space . Our preliminary experiments show that only “attacking” the final ML classifier does not suffice to evade the whole detection system. This is due to the nondeterminism and probabilistic nature of malware behavior. Hence, computing an adversarial perturbation after observing a specific behavior may not be enough to guarantee a successful attack in subsequent executions. Furthermore, as shown in Section 5 , the original feature space attack proposed by Rosenberg et al. [ 43 ] requires a very large number of additional API calls to evade newer and more sophisticated classifiers such as [ 25 , 54 ] . This may affect both the stealthiness of the attack as well as its capacity to deliver its original and intended behavior. Our main contribution consists in designing an AML ( AML ) attack that is effective both in the feature and problem spaces while targeting systems that employ sophisticated DL algorithms such as [ 25 , 54 ] . First, we propose PS-FGSM , a new adversarial attack specific to sequential data, able to produce evasive behaviors with minimal perturbations. Then, we address the problem space limitations through two variants: with the first, the attacker executes several times the malware sample, recording all behaviors, and then selects the longest. The second approach consists of performing the attack while considering multiple behaviors at once. We preliminary evaluate our attacks through an array of experiments against two state-of-the-art RNN ( RNN )-based malware detectors, measuring the attack success in the problem space [ 35 ] in both white- and black-box scenarios. We confirm that after modification and re-execution in the sandbox, the adversarial samples can still evade detection. Our more stringent criterion contrasts with those adopted in previous works [ 43 , 42 ] , which solely focused on evaluating the evasion rate in the feature space. Tarallo achieved a success rate of 99\% in the feature space. Additionally, it significantly reduced the number of injections required to achieve misclassification, with an average of 27 additional API calls required, a value significantly lower than what is required by current state-of-the-art approaches against weaker models. In the problem space experiments, our method attains a success rate of up to 99\% . While securing high evasion rates, our approach also maintains the original malware functionality. In 89\% of the cases, the modified malware preserves its original behavior, thus ensuring its capability to execute its original malicious functions while evading detection. Overall, the results from our experimental evaluations highlight the effectiveness and efficiency of our approach, particularly when compared to state-of-the-art attacks. The main contributions of this research are summarized below: • We introduce PS-FGSM , a novel AML attack algorithm that targets discrete sequences, which, against RNN models, proves to be more effective and efficient than state-of-the-art approaches. • We design two strategies to compute an optimal API call sequence that aims to evade detection in the problem space, addressing the nondeterminism between executions. • We propose a less invasive code-modification strategy that preserves the original functionality of modified malware samples. • We present Tarallo, an

Read the complete text