Mathematics and Computer Science: Research Updates Vol. 10

Malware remains one of the most critical threats in the digital ecosystem, targeting both mobile and desktop platforms. Malware continues to evolve in ways that reduce the effectiveness of signature matching and evade analysis environments, creating demand for early detection methods that can flag suspicious binaries before behaviour is observed. Early malware detection is, therefore, a race against time, where the advantage often lies with the attacker. This chapter surveys information-theoretic approaches for early malware detection, focusing on the progression from classical uncertainty measures to algorithmic notions of complexity.

A structured literature-gathering process was employed, covering entropy-based analysis, compression-based approximations of algorithmic complexity, and compression-distance similarity measures. The study first examines Shannon entropy as a lightweight indicator of packing, encryption, and obfuscation, and explains how entropy computed over whole files, executable sections, or sliding windows can localise anomalous regions in portable executable binaries. It then explores algorithmic complexity through the lens of Kolmogorov complexity, outlining practical approximations using general-purpose compression. Compression-based measures enable the estimation of structural regularities in binaries that are not captured by frequency statistics alone. Building on this, normalised compression distance (NCD) is introduced as a featureless similarity measure for clustering and nearest-neighbor detection.

Findings highlight how entropy, compressibility, and compression-based similarity can be combined into hybrid pipelines that support triage, prioritisation, and explainable inspection, while also noting key limitations. High entropy is not unique to malware and can arise in legitimate packed installers, multimedia resources, or encrypted payloads, leading to false alarms if used in isolation. Section-wise and sliding-window entropy analysis provide better localisation of suspicious regions, improving interpretability compared to whole-file entropy approaches. Compression-based methods can be computationally demanding and sensitive to file size, compressor choice, and adversarial manipulation. NCD enables featureless similarity detection and effective malware family clustering, but faces scalability challenges due to pairwise comparisons. Hybrid pipelines combining entropy, compression, and structural features provide improved precision and reduced false positives, making them more suitable for real-world deployment.

By synthesising these techniques and their practical considerations, this article provides guidance for designing robust early-warning detectors and for integrating information-theoretic signals with complementary static and learning-based components in operational settings. The transition from Shannon entropy, a statistical measure of disorder, to Kolmogorov complexity, an algorithmic measure of information, represents a deeper analytical framework for malware detection. While entropy remains valuable for fast screening, integrating algorithmic information theory opens pathways toward more adaptive and generalised detection systems.