Unmasking Vulnerabilities:
Cardinality Sketches under Adaptive Inputs

Composable sketches for cardinality estimation are data structures that are commonly used in practice (Apache Software Foundation, Accessed: 2024; Google Cloud, Accessed: 2024) and had been studied extensively (Flajolet and Martin, 1985; Flajolet et al., 2007b; Cohen, 1997; Bar-Yossef et al., 2002; Kane et al., 2010; Nelson et al., 2014; Cohen, 2015; Pettie and Wang, 2021). The sketch of a set is a compact representation that supports merge (set union) operations, adding elements, and retrieval of approximate cardinality. The sketch size is only logarithmic or double logarithmic in the cardinality of queries, which allows for a significant efficiency boost over linear size data structures such as Bloom filters.

Formally, for a universe $\mathcal{U}$ of keys, and randomness $\rho$, a sketch map $U\mapsto S_{\rho}(U)$ is a mapping from sets of keys $U\in 2^{\mathcal{U}}$ to their sketch $S_{\rho}(U)$. Sketch maps are designed so that for each $U$ we can recover with high probability (over $\rho$) an estimate of $|U|$ by applying an estimator $\mathcal{M}$ to $S_{\rho}(U)$. A common guarantee is a bound on the Normalized Root Mean Squared Error (NRMSE) so that for accuracy parameter $\epsilon$,

The maps $S_{\rho}$ are designed to be composable: For a set $U$ and key $u$, the sketch $S_{\rho}(U\cup\{u\})$ can be computed from $S_{\rho}(U)$ and $u$. For two sets $U$, $V$, the sketch $S_{\rho}(U\cup V)$ can be computed from their respective sketches $S_{\rho}(U)$, $S_{\rho}(V)$. Composability is a crucial property that makes the sketch representations useful for streaming, distributed, and parallel applications. Importantly, the use of the same internal randomness $\rho$ across all queries is necessary for composability and therefore in typical use cases it is fixed across a system.

The basic technique in the design of cardinality (distinct count) sketches is to randomly prioritize the keys in the universe $\mathcal{U}$ through the use of random hash functions (specified by $\rho$). The sketch of a set $U$ keeps the lowest priorities of keys that are in the set $U$. This provides information on the cardinality $|U|$, since a larger cardinality corresponds to the presence of lower priorities keys in $U$. This technique was introduced by Flajolet and Martin (1985) for counting distinct elements in streaming and as composable sketches of sets by Cohen (1997). The core idea of sampling keys based on a random order emerged in reservoir sampling (Knuth, 1998), and in weighted sampling  (Rosén, 1997). Cardinality sketches are also Locality Sensitive Hashing (LSH) maps (Indyk and Motwani, 1998) with respect to set differences.

The specific designs of cardinality sketches vary and include MinHash sketches (randomly map keys to priorities) or domain sampling (randomly map keys to sampling rates). With these methods, the sketch size dependence on the maximum query size $|U|\leq n$ is $\log n$ or $\log\log n$. The sketch size (number of registers) needed for the NRMSE guarantee of Equation (1) is $k=O(\epsilon^{-2})$. The sketch size needed for the following $(\epsilon,\delta)$ guarantee (confidence $1-\delta$ of relative error of $\epsilon$)

is $k=O(\epsilon^{-2}\log(1/\delta))$. This guarantee means that for any $U$, almost any sampled $\rho$ works well.

We model the use of the sketching map $S_{\rho}$ as an interaction between a source, that issues queries $U_{i}\subset\mathcal{U}$, and a query response (QR) algorithm, that receives the sketch $S_{\rho}(U_{i})$ (but not $U_{i}$) applies an estimator $\mathcal{M}$ and returns the estimate $\mathcal{M}(S_{\rho}(U_{i}))$ on the cardinality $|U_{i}|$.

When randomized data structures or algorithms are invoked interactively, it is important to make a distinction between non-adaptive queries, that do not depend on $\rho$, and adaptive queries. In non-adaptive settings we can treat queries as fixed in advance. In this case, we can apply a union bound with the guarantee of Equation 2 and obtain that the probability that the responses for all $r$ queries are within a relative error of $\epsilon$, is at least $1-r\delta$. Therefore, the sketch size needed to provide an $(\epsilon,\delta)$-guarantee on this $\ell_{\infty}$ error is $k=O(\epsilon^{-2}\log(r/\delta)$. In particular, the query response algorithm can be correct on a number of non-adaptive queries that is exponential in the sketch size until a set is encountered for which the estimate is off.

Many settings, however, such as control loops, optimization processes, or malicious behavior, give rise to adaptive inputs. This can happen inadvertently when a platform such as Apache Software Foundation (Accessed: 2024) or SQL (Google Cloud, Accessed: 2024) is used. In such cases, information on the randomness $\rho$ may leak from query responses, and the union bound argument does not hold. An important question that arises is thus to understand the actual vulnerability of our specific algorithms in such settings. Are they practically robust? How efficiently can they be attacked? What can be the consequences of finding such an adversarial input?

Randomized data structures designed for non-adaptive queries can be applied in generic ways with adaptive queries. However, the guarantees provided by the resulting (robust) algorithms tend to be significantly weaker than those of their non-robust counterparts. The straightforward approach is to maintain multiple copies of the sketch maps (with independent randomness) and discard a copy after it is used once to respond to a query. This results in a linear dependence of the number of queries $r$ in the size of the data structure. Hassidim et al. (2020) proposed the robustness wrapper method that allows for $r^{2}$ adaptive queries using $\tilde{O}(r)$ sketch maps. The method uses differential privacy to protect the randomness and the analysis uses generalization (Dwork et al., 2015b; Bassily et al., 2021) and advanced composition (Dwork et al., 2006). The quadratic relation is known to be tight in the worst-case for adaptive statistical queries with an attack (Hardt and Ullman, 2014; Steinke and Ullman, 2015) designed using Fingerprinting Codes (Boneh and Shaw, 1998). But these attacks do not preclude a tailored design with a better utility guarantee for cardinality sketches and also do not apply with “natural” workloads.

There are prolific lines of research on the effect of adaptive inputs that span multiple areas including dynamic graph algorithms (Shiloach and Even, 1981; Ahn et al., 2012; Gawrychowski et al., 2020; Gutenberg and Wulff-Nilsen, 2020; Wajc, 2020; Beimel et al., 2022), sketching and streaming algorithms (Mironov et al., 2008; Hardt and Woodruff, 2013; Ben-Eliezer et al., 2021b; Hassidim et al., 2020; Woodruff and Zhou, 2021; Attias et al., 2021; Ben-Eliezer et al., 2021a; Cohen et al., 2022a, b), adaptive data analysis (Freedman, 1983; Ioannidis, 2005; Lukacs et al., 2009; Hardt and Ullman, 2014; Dwork et al., 2015a) and machine learning (Szegedy et al., 2013; Goodfellow et al., 2014; Athalye et al., 2018; Papernot et al., 2017).

Reviriego and Ting (2020) and Paterson and Raynal (2021) proposed attacks on the HLL sketch with standards estimators. The proposed attacks were in a streaming setting and utilized many dependent queries in order to detect keys whose insertion results in updates to the cardinality estimate. Our attacks are more general: We construct single-batch attacks with standard estimators and also construct attacks on these cardinality sketches that apply with any estimator. The question of robustness of cardinality sketches to adaptive inputs is related but different than the well studied question of whether they are differentialy private. Cardinality sketches were shown to be not privacy preserving when the sketch randomness or content are public (Desfontaines et al., 2019). Other works (Smith et al., 2020; Pagh and Stausholm, 2021; Knop and Steinke, 2023) showed that cardinality sketches are privacy preserving, but this is under the assumption that the randomness is used once. Our contribution here is designing attacks and quantifying their efficiency. The common grounds with privacy is the high sensitivity of the sketch maps to removal or insertion of low priority key.

Several works constructed attacks on linear sketches, including the Johnson Lindenstrauss Transform (Cherapanamjeri and Nelson, 2020), the AMS sketch (Ben-Eliezer et al., 2021b; Cohen et al., 2022b), and CountSketch (Cohen et al., 2022a, b). The latter showed that the standard estimators for CountSketch and the AMS sketch can be compromised with a linear number of queries and the sketches with arbitrary estimators can be compromised with a quadratic number of queries. The method was to combine low bias inputs with disjoint supports and have the bias amplified, since the bias increases linearly whereas the $\ell_{2}$ norms increases proportionally to $\sqrt{r}$. This approach does not work with cardinality sketches, which required a different attack structure. Combining disjoint sets on which the estimate is slightly biased up will not amplify the bias. The common ground, perhaps surprisingly, is that these fundamental and popular sketches are all vulnerable with adaptive inputs and in a similar manner: Estimators that optimally use the sketch require linear size attacks. Arbitrary correct estimators require quadratic size attacks.

An attack is an interaction designed to construct a set that is adversarial to the randomness $\rho$. An adversarial set can be identified by trying out a large number of inputs. We measure the efficiency of the attack by its size (number of issued queries) and concurrency (number of batches of concurrent queries).

A set $U$ is adversarial for the randomness $\rho$ if a sufficient statistics for the cardinality that is computed from $S_{\rho}(U)$ is very skewed with respect to its distribution under sampling of $\rho$. That is, it has proportionally too few or two many low priority keys.

The “standard” cardinality estimators optimally use the content in the sketch. They can be equivalently viewed as reporting a sufficient statistics. We design a single-batch attack described in Algorithm 1. The algorithm fixes a ground set $N$ of keys. For $r$ queries, it samples a random subset $U\subset N$ where each $u\in N$ is included independently with probability $1/2$. It receives from the estimator the value of the sufficient statistics $T(S_{\rho}(U)):=1/M(S_{\rho}(U))$ (we use the inverse of the cardinality estimate). For each key $x\in N$ it computes a score $A[x]$ that is the average value of $T(S_{\rho}(U))$ over all subsets where $x\in U$.

We show that for $\alpha>0$, an attack of size $O(r/\alpha^{2})$ produces an adversarial set with sketch that is biased up by a factor $\alpha$ (see Definition 3.2).

Our analysis extends to the case when the estimator reports $T(S_{\rho}(U))$ with relative error $O(1/\sqrt{k})$. That is, as long as the estimates are sufficiently accurate (within the order of the accuracy guarantees of a size $k$ sketch), then $O(k)$ attack queries suffice.

In this section, we empirically demonstrate the efficacy of our proposed attack (Algorithm 1) against the HyperLogLog (HLL) sketch Durand and Flajolet (2003); Flajolet et al. (2007b) with the HLL++ estimator Heule et al. (2013). This is the most widely utilized sketch for cardinality estimation in practice. Given an accuracy parameter $\epsilon$, the HLL sketch stores $k=1.04\epsilon^{-2}$ values that are the negated exponents of a $k$-partition MinHash sketch (described in Section 3.1).

The HLL++ estimator is a hybrid that was introduced in order to improve accuracy on low cardinality queries. When the sketch representation is sparse (fewer parts are populated), which is the case with cardinality lower than the sketch size, HLL++ uses the sketch as a hash table and estimates cardinality based on the number of populated parts. This yields essentially precise values. When all parts are populated, HLL++ uses an estimator based on the MinHash property. We set the size of our ground set $n\gg k$ to be in this relevant regime.

We conduct two primary experiments: (i) For a fixed sketch size, we analyze the efficacy of the attack with a varying number of queries. (ii) For different sketch sizes, we evaluate the effectiveness of the attack with the number of queries linearly proportional to the sketch size. In the following section, we will first provide a detailed explanation of the ingredients required for our experimental setup. Subsequently, we will present the results of each experiment.

We design attacks that apply generally against any query response (QR) algorithm. The attacks are effective even when the specifics of the attack and the full internal state of the attack algorithm are shared with the QR algorithm, including the per-step distribution from which the attacker selects each query. Moreover, we can even assume that the QR algorithm is provided with an enhanced sketch that includes the identities of the low priority keys that determined the sketch and that after the QR algorithm responds to a query, the full query set $U$ is shared with it. The only requirement from the QR algorithm is that it selects correct response maps (with respect to the query distribution). Note that such a powerful QR algorithm precludes attacks that use queries of fixed cardinality, since the QR algorithm can simply return that cardinality value without even considering the actual input sketch.²²2Our attack in Algorithm 1 is also precluded, since a fixed response of $n/2$ satisfies the requirements (the cardinality is $\textsf{Binom}(n,p)$ and for $n\gg k$, all queries have size close to $n/2$).

Moreover, the task of the QR algorithm is the following problem that is more specialized than cardinality estimation:

Algorithm 3 specifies a single-batch attack. We establish that the attack succeeds when we set the size $r=\tilde{O}(k^{2})$ and QR is constrained to be symmetric (see Definition 7.2). In essence symmetry means that the QR algorithm does not make a significant distinction between components of the sketch. Symmetry excludes strategies that distinguish between components of the sketch as in the proof of Lemma 6.5 but still allows for flexibility including randomly selecting components of the sketch. In Section 8 we extend this attack to an adaptive attack that works against any QR algorithm.

The attacker initializes the scores $C[x]\leftarrow 0$ of all keys $x\in N$ in the ground set. Each query is formed by sampling a rate $q$ (as described in Algorithm 5) and selecting a random subset $U\subset N$ so that each key in $N$ is included independently with probability $q$. The attacker receives $Z$ and increments by $Z$ the score $C[x]$ of all keys $x\in U$. The final product is the set $M$ of keys with scores that are higher by $\tilde{\Omega}(r/k)$ than the median score.

An attack on general QR algorithms is given in Algorithm 4. The attacker maintains an initially empty set $M\subset N$ of keys which we refer to as mask. The query sets have the form $M\cup U$, where $U\sim\mathcal{D}_{0}$ is sampled and scored as in Algorithm 3. A key is added to $M$ when its score separates out from the median score. We establish the following:

We overview the proof with details deferred to Appendix B. The condition for adding a key to $M$ is such that with probability at least $0.99$, only $N_{0}$ keys are placed in $M$, so $|M|\leq\alpha n$ (Claim B.9). If the QR algorithm fails, there is no correct map for the distribution $M\cup\mathcal{D}_{0}$.³³3A situation of no correct maps can be identified by Attacker, by tracking the error rate of QR, even if not declared by QR. It remains to consider the case where the attack is not halted.

Since the mask $M$ is shared with QR “for free,” QR only needs to estimate $|U|$ (or $q$). But the sketch of $M\cup U$ partially masks the sketch of $U$. The set of non-transparent keys $N^{\prime}_{0}\subset N_{0}$ decreases as $M$ increases. Additionally, the effective sketch size $k^{\prime}\leq k$ is lower (that is, QR only obtains $k^{\prime}$ i.i.d $\textsf{Geom}[q]$ random variables). Recall that when $k^{\prime}<\log(k)/2$, there is no correct map.

With general correct maps, we can only establish a weaker average version of the score gap over $N^{\prime}_{0}$ keys. This allows some $N^{\prime}_{0}$ keys to remain indistinguishable by score from transparent keys. But what works in Attacker’s favour is that in this case the score of other $N_{0}$ keys must increase faster. Let $p(\pi,M,x)$ be the probability that key $x$ is scored with map $\pi$ and mask $M$. The probability is the same for all transparent keys $x\not\in N^{\prime}_{0}$ and we denote it by $p^{\prime}(\pi,M)$. We establish (see Lemma B.8) that for a correct map $\pi$ for $M\cup\mathcal{D}_{0}$ it holds that

Therefore, in $r=\tilde{O}(k^{2})$ steps, the combined score advantage of $N_{0}$ keys is (concentrated well around) $\tilde{O}(k^{2})$. But crucially, any one key can not get too much advantage: once $C(x)-\overline{C}=\tilde{\Omega}(k)$ (where $\overline{C}$ is the median score), then key $x$ is placed in the mask $M$, exits $N^{\prime}_{0}$, and stops getting scored. Therefore if QR does not fail, $\tilde{\Omega}(r/k)>|N_{0}|$ keys are eventually placed in $M$, which must include all $N_{0}$ keys.

We demonstrated the inherent vulnerability of the known composable cardinality sketches to adaptive inputs. We designed attacks that use a number of queries that asymptotically match the upper bounds: A linear number of queries with the “standard” estimator and a quadratic number of queries with any estimator applied to the sketch. Empirically, our attacks are simple and effective with small constants. An interesting direction for further study is to show that this vulnerability applies with any composable sketch structure. On the positive side, we suspect that restricting the maximum number of queries that any one key can participate in to sublinear (with standard estimators) or subquadratic (with general estimators) would enhance robustness.

The authors are grateful to Jelani Nelson and Uri Stemmer for discussions. Edith Cohen is partially supported by Israel Science Foundation (grant no. 1156/23).