On Normalized Compression Distance and Large Malware
This work addresses a practical problem for malware classification, but it is incremental as it modifies an existing method.
The authors tackled the problem of Normalized Compression Distance (NCD) failing to classify large malware files due to theoretical assumptions not holding in practice, and they introduced variants of NCD that mitigated this issue, though no concrete performance numbers were provided.
Normalized Compression Distance (NCD) is a popular tool that uses compression algorithms to cluster and classify data in a wide range of applications. Existing discussions of NCD's theoretical merit rely on certain theoretical properties of compression algorithms. However, we demonstrate that many popular compression algorithms don't seem to satisfy these theoretical properties. We explore the relationship between some of these properties and file size, demonstrating that this theoretical problem is actually a practical problem for classifying malware with large file sizes, and we then introduce some variants of NCD that mitigate this problem.