Zipf-Gramming: Scaling Byte N-Grams Up to Production Sized Malware Corpora
Not on the map. Why?
Abstract (arXiv)
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× 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.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 24 of its 71 references that are in the map. First posted on arXiv 17 Nov 2025.
Builds on
24 of 71 references.
References · 24
- 2018TESSERACT: Eliminating Experimental Bias in Malware Classification across Space and Timecited by 108
- 2015Deep Neural Network Based Malware Detection Using Two Dimensional Binary Program Featurescited by 48
- 2020A Survey of Machine Learning Methods and Challenges for Windows Malware Classificationcited by 33
- 2017Survey of Machine Learning Techniques for Malware Analysiscited by 31
- 2025EMBER2024 -- A Benchmark Dataset for Holistic Evaluation of Malware Classifierscited by 19
- 2020Automatic Yara Rule Generation Using Biclusteringcited by 17
- 2021MOTIF: A Large Malware Reference Dataset with Ground Truth Family Labelscited by 17
- 2021A Framework for Cluster and Classifier Evaluation in the Absence of Reference Labelscited by 16
- 2014Zipf's law holds for phrases, not wordscited by 12
- 2024Assemblage: Automatic Binary Dataset Construction for Machine Learningcited by 12
- 2025ClarAVy: A Tool for Scalable and Accurate Malware Family Labelingcited by 10
- 2019KiloGrams: Very Large N-Grams for Malware Classificationcited by 9
12 more
- 2023Semi-supervised Classification of Malware Families Under Extreme Class Imbalance via Hierarchical Non-Negative Matrix Factorization with Automatic Model Selectioncited by 9
- 2021Rank-1 Similarity Matrix Decomposition For Modeling Changes in Antivirus Consensus Through Timecited by 7
- 2022Efficient Malware Analysis Using Metric Embeddingscited by 6
- 2022Transformers for End-to-End InfoSec Tasks: A Feasibility Studycited by 6
- 2024Is Function Similarity Over-Engineered? Building a Benchmarkcited by 6
- 2015On Normalized Compression Distance and Large Malwarecited by 5
- 2023AVScan2Vec: Feature Learning on Antivirus Scan Data for Production-Scale Malware Corporacited by 5
- 2019Would a File by Any Other Name Seem as Malicious?cited by 4
- 2024High-Dimensional Distributed Sparse Classification with Scalable Communication-Efficient Global Updatescited by 3
- 2024Living off the Analyst: Harvesting Features from Yara Rules for Malware Detectioncited by 3
- 2014A Parallel Space Saving Algorithm For Frequent Items and the Hurwitz zeta distributioncited by 1
- 2018Smooth q-Gram, and Its Applications to Detection of Overlaps among Long, Error-Prone Sequencing Readscited by 1
Built on by
Citing papers per year: 2026: 2.
2 papers.