论文标题
Hyperloglog（HLL）基数估算的安全性：漏洞和保护
Security of HyperLogLog (HLL) Cardinality Estimation: Vulnerabilities and Protection
论文作者
论文摘要
计数不同的或心脏的估计值广泛用于网络监控安全性。可以使用它们来检测恶意软件扩展，网络扫描或拒绝服务攻击。有许多算法可以估计基数。其中，Hyperloglog（HLL）是最广泛采用的产品之一。 HLL很简单，提供了良好的基数估计值，可以在广泛的值中，需要少量的内存，并允许从不同来源合并估计值。但是，由于HLL越来越多地用于检测攻击，因此它本身可以成为想要避免被检测到的攻击者的目标。据我们所知，HLL的安全性以前尚未进行过研究。在这封信中，我们首先暴露了HLL的脆弱性，该信中的第一步使攻击者可以操纵其估计。这显示了设计安全的HLL实现的重要性。在信的第二部分中，我们提出了一种有效的保护技术，以检测并避免HLL操纵。提出的结果强烈表明，鉴于在许多网络和计算应用程序中广泛采用了HLL的安全性。
Count distinct or cardinality estimates are widely used in network monitoring for security. They can be used, for example, to detect the malware spread, network scans, or a denial of service attack. There are many algorithms to estimate cardinality. Among those, HyperLogLog (HLL) has been one of the most widely adopted. HLL is simple, provides good cardinality estimates over a wide range of values, requires a small amount of memory, and allows merging of estimates from different sources. However, as HLL is increasingly used to detect attacks, it can itself become the target of attackers that want to avoid being detected. To the best of our knowledge, the security of HLL has not been studied before. In this letter, we take an initial step in its study by first exposing a vulnerability of HLL that allows an attacker to manipulate its estimate. This shows the importance of designing secure HLL implementations. In the second part of the letter, we propose an efficient protection technique to detect and avoid the HLL manipulation. The results presented strongly suggest that the security of HLL should be further studied given that it is widely adopted in many networking and computing applications.
