CARBINE: Exploring Additional Properties of HyperLogLog for Secure and Robust Flow Cardinality Estimation

Counting distinct elements (also named flow cardinality) of large data streams in the network is of primary importance since it can be used for many practical monitoring applications, including DDoS attack and malware spread detection. However, modern intrusion detection systems are struggling to reduce both memory and computational overhead for such measurements. Many algorithms are designed to estimate flow cardinality, in which HyperLogLog has been proven the most efficient due to its high accuracy and low memory usage. While HyperLogLog provides good performance on flow cardinality estimation, it has inherent algorithmic vulnerabilities that lead to both security and robustness issues. To overcome these issues, we first investigate two possible threats in HyperLogLog, and propose corresponding detection and protection solutions. Lever-aging proposed solutions, we introduce CARBINE, an approach that aims at identifying and eliminating the threats that most probably mislead the output of HyperLogLog. We implement our CARBINE to evaluate the threat detection performance, especially in case of a practical network scenario under volumetric DDoS attack. The results show that our CARBINE can effectively detect different kinds of threats while performing even higher accuracy and update speed than original HyperLogLog.