Certified Adversarial Robustness of End-to-End Malware Detectors via (De)Randomized Smoothing

End-to-end machine learning malware detectors are vulnerable to adversarial EXEmples, carefully-crafted malicious programs that evade detection through minimal perturbations. Such attacks typically operate by either replacing unused content (patch attacks), or injecting new patterns (content-injection attacks). To counter these attacks, recent research has focused on certification methods for end-to-end models that aim to prove robustness guarantees within bounded perturbation sizes. However, existing approaches (i) are not robust against content-injection manipulations and (ii) provide only probabilistic guarantees for perturbations that are negligible relative to the overall program size. Hence, in this paper we address these limitations through a novel deterministic certification schema based on (de)randomized smoothing. Our defense splits each executable into non-overlapping chunks and classifies them independently. The final decision is obtained via majority voting across all chunks, ensuring that localized modifications, such as injected or patched code, influence only a limited subset of chunks and have minimal impact in the overall classification. This design guarantees that each chunk either contains or does not contain an adversarial perturbation, enabling us to (i) handle manipulations occurring at arbitrary locations within the program, and (ii) compute deterministic estimates of the perturbation magnitude required to evade detection. We demonstrate the effectiveness of our certification schema through extensive experimental analysis, comparing our defense against a range of state-of-the-art attacks and defenses. The results show that our approach achieves unmatched robustness across all tested attack scenarios, substantially outperforming competing defenses.