# A New Formulation for Zeroth-Order Optimization of Adversarial EXEmples in Malware Detection

arXiv: https://arxiv.org/abs/2405.14519 · HTML: https://mlsanity.com/paper/2405.14519/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 41 references that are in the map.
- First posted on arXiv 23 May 2024.

## Builds on (most cited first, 23 of 23)

- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [RobustBench: a standardized adversarial robustness benchmark](https://mlsanity.com/paper/2010.09670/) (2020)
- [Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning](https://mlsanity.com/paper/1712.03141/) (2017)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [EMBER: An Open Dataset for Training Static PE Malware Machine Learning Models](https://mlsanity.com/paper/1804.04637/) (2018)
- [Malware Detection by Eating a Whole EXE](https://mlsanity.com/paper/1710.09435/) (2017)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [A Theoretical and Empirical Comparison of Gradient Approximations in Derivative-Free Optimization](https://mlsanity.com/paper/1905.01332/) (2019)
- [Adversarial Malware Binaries: Evading Deep Learning for Malware Detection in Executables](https://mlsanity.com/paper/1803.04173/) (2018)
- [Functionality-preserving Black-box Optimization of Adversarial Windows Malware](https://mlsanity.com/paper/2003.13526/) (2020)
- [Structured Evolution with Compact Architectures for Scalable Policy Optimization](https://mlsanity.com/paper/1804.02395/) (2018)
- [Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling](https://mlsanity.com/paper/2003.13001/) (2020)
- [A Zeroth-Order Block Coordinate Descent Algorithm for Huge-Scale Black-Box Optimization](https://mlsanity.com/paper/2102.10707/) (2021)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [Malware Makeover: Breaking ML-based Static Analysis by Modifying Executable Bytes](https://mlsanity.com/paper/1912.09064/) (2019)
- [Zeroth order optimization with orthogonal random directions](https://mlsanity.com/paper/2107.03941/) (2021)
- [AVClass2: Massive Malware Tag Extraction from AV Labels](https://mlsanity.com/paper/2006.10615/) (2020)
- [RS-Del: Edit Distance Robustness Certificates for Sequence Classifiers via Randomized Deletion](https://mlsanity.com/paper/2302.01757/) (2023)
- [Global Convergence Rate Analysis of a Generic Line Search Algorithm with Noise](https://mlsanity.com/paper/1910.04055/) (2019)
- [An Optimal Structured Zeroth-order Algorithm for Non-smooth Optimization](https://mlsanity.com/paper/2305.16024/) (2023)
- [Quo Vadis: Hybrid Machine Learning Meta-Model based on Contextual and Behavioral Malware Representations](https://mlsanity.com/paper/2208.12248/) (2022)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [secml-malware: Pentesting Windows Malware Classifiers with Adversarial EXEmples in Python](https://mlsanity.com/paper/2104.12848/) (2021)

## Built on by (most cited first, 1 of 1)

- [A Structured Tour of Optimization with Finite Differences](https://mlsanity.com/paper/2505.19720/) (2025)

## Abstract (arXiv)

Machine learning malware detectors are vulnerable to adversarial EXEmples, i.e., carefully-crafted Windows programs tailored to evade detection. Unlike other adversarial problems, attacks in this context must be functionality-preserving, a constraint that is challenging to address. As a consequence, heuristic algorithms are typically used, which inject new content, either randomly-picked or harvested from legitimate programs. In this paper, we show how learning malware detectors can be cast within a zeroth-order optimization framework, which allows incorporating functionality-preserving manipulations. This permits the deployment of sound and efficient gradient-free optimization algorithms, which come with theoretical guarantees and allow for minimal hyper-parameters tuning. As a by-product, we propose and study ZEXE, a novel zeroth-order attack against Windows malware detection. Compared to state-of-the-art techniques, ZEXE provides improvement in the evasion rate, reducing to less than one third the size of the injected content.