Zipf-Gramming: Scaling Byte N-Grams Up to Production Sized Malware Corpora
Authors:
- Edward RaffEREdward Raff
- Ryan R. CurtinRCRyan R. Curtin
- Derek EverettDEDerek Everett
- Robert J. JoyceRJRobert J. Joyce
- James HoltJHJames Holt
Preprint
Abstract
A classifier using byte n-grams as features is the only approach we have found fast enough to meet requirements in size (sub 2 MB), speed (multiple GB/s), and latency (sub 10 ms) for deployment in numerous malware detection scenarios. However, we've consistently found that 6-8 grams achieve the best accuracy on our production deployments but have been unable to deploy regularly updated models due to the high cost of finding the top-k most frequent n-grams over terabytes of executable programs. Because the Zipfian distribution well models the distribution of n-grams, we exploit its properties to develop a new top-k n-gram extractor that is up to $35\times$ faster than the previous best alternative. Using our new Zipf-Gramming algorithm, we are able to scale up our production training set and obtain up to 30\% improvement in AUC at detecting new malware. We show theoretically and empirically that our approach will select the top-k items with little error and the interplay between theory and engineering required to achieve these results.
Keywords
All Related Versions
- Version 1, 2025-11-17, ArXiv
- Published version: , 5988.
This publication has 23 references indexed in Scilit:
- Optimizing the Optimal Weighted Average: Efficient Distributed Sparse Classification2025
- AntiViruses under the microscope: A hands-on perspectiveComputers & Security, 2022
- Survey of machine learning techniques for malware analysisComputers & Security, 2019
- An investigation of byte n-gram features for malware classificationJournal of Computer Virology and Hacking Techniques, 2016
- A parallel space saving algorithm for frequent items and the Hurwitz zeta distributionInformation Sciences, 2016
- On normalized compression distance and large malwareJournal of Computer Virology and Hacking Techniques, 2015
- Zipf’s law holds for phrases, not wordsScientific Reports, 2015
- How popular is your paper? An empirical study of the citation distributionThe European Physical Journal B, 1998
- Order statistics from non-identical exponential random variables and some applicationsComputational Statistics & Data Analysis, 1994
- New fast method for generating discrete random numbers with arbitrary frequency distributionsElectronics Letters, 1974