Contar a torcida sem anotar cada nome.
Imagine a portaria de um estádio que precisa saber quantas pessoas diferentes entraram na temporada. Anotar cada nome exige um caderno enorme. O truque dos resumos compactos é outro: cada pessoa passa por um embaralhador que transforma o nome num número e a manda para uma de 16.384 caixinhas. Olhando só as caixinhas, dá para estimar o total com erro de menos de 1%, gastando 12 KB de memória.
É assim que o Redis conta visitantes únicos, que bancos de dados contam clientes distintos e que plataformas de IA contam quantos pedidos caros cada cliente fez, para cobrar e para impor limites.
A promessa de "menos de 1% de erro" tem uma letra miúda: vale para quem não está tentando enganar.
Um cadeado com a senha no manual.
O Redis usa sempre o mesmo embaralhador, com uma semente fixa e pública (0xadc83b19). O DataSketches, a mesma coisa (9001). Qualquer um pode reproduzir o embaralhador no próprio computador e garimpar nomes que caem onde ele quer.
Com isso, dá para errar para os dois lados. Escondendo: milhares de pedidos caros aparecem como um só, e o limite de uso nunca dispara. Inflando: poucos visitantes aparecem como milhões, e o painel de audiência mente.
O conserto é barato: uma chave secreta por contador, sorteada na criação. Sem a chave, o atacante não sabe onde cada nome vai cair, e o garimpo não tem alvo. O resumo continua do mesmo tamanho. A teoria já dizia que blindar esses resumos custa pouco (Ben-Eliezer e colegas, 2022), mas não havia biblioteca pronta para instalar. O TRUSS é essa biblioteca.
Nos contadores instalados de verdade.
Não fizemos o ataque num modelo de papel. Rodamos contra o Redis 8.8 instalado e contra o Apache DataSketches 6.1.1, o contador de distintos usado por Druid, Hive, Spark e Pinot.
No Redis, 30.000 usuários distintos, escolhidos pelo atacante, foram contados como 1. Que o Redis tenha respondido exatamente 1 prova que a nossa cópia do embaralhador dele bate byte a byte. No DataSketches, 50.000 distintos viraram 13,1 milhões: 262 vezes a mais. Mesma causa, direções opostas.
Com a chave secreta do TRUSS, os mesmos ataques deram 29.705 no primeiro caso e uma contagem dentro de 1% no segundo.
Levamos o caso para o custo de IA: uma plataforma com limite de 1.000 pedidos caros por cliente, a US$ 0,10 cada. Com o contador do Redis, o cliente abusivo fez 30.000 pedidos e o limite não disparou: US$ 2.999,90 passaram sem cobrança. Com o TRUSS, o limite disparou.
| Contador | Cenário | Distintos de verdade | Contado | Efeito |
|---|---|---|---|---|
| Redis 8.8 (HyperLogLog) | tráfego honesto | 30.000 | 30.195 | fiel |
| Redis 8.8 (HyperLogLog) | ataque que esconde | 30.000 | 1 | 30.000× a menos; limite de uso não dispara |
| TRUSS, chave secreta | mesmo ataque | 30.000 | 29.705 | fiel; limite dispara |
| DataSketches 6.1.1 (Theta) | ataque que infla | 50.000 | 13,1 milhões | 262× a mais |
| TRUSS, chave secreta | mesmo ataque | 50.000 | ±1% | fiel |
Também medimos o ataque mais sutil, em que o atacante faz perguntas, olha a resposta e ajusta o próximo passo. Contra o estimador de "soma dos quadrados" (a medida clássica de concentração), ele inflou um contador comum para 2,1 vezes o valor certo. Com a troca de cópias descrita no artigo de 2022, que só revela uma cópia nova quando a estimativa muda de patamar, o resultado ficou em 1,0: nenhum dos 20.000 itens do atacante conseguiu mexer na conta.
Quando alguém ganha dinheiro com o erro.
Cobrança e limite de uso de IA
Pedido caro é incentivo para esconder a contagem. Um limite que não dispara vira prejuízo direto, como os US$ 2.999,90 do teste.
Audiência e anúncios
Visitantes únicos e impressões podem ser inflados para vender mais caro. O painel precisa aguentar quem tem interesse em inflá-lo.
Segurança e abuso
Alarme de varredura, de contas novas ou de cartões diferentes costuma depender de "quantos distintos". Escondê-los desliga o alarme.
Onde não precisa
Se ninguém tem incentivo para manipular a conta, o contador comum basta. E se a resposta precisa ser exata, e não aproximada, conte exato.
Um contador que estima o total guardando pouquíssimo: 12 KB para milhões de itens, com erro típico abaixo de 1% no tráfego honesto.
A função que decide em que caixinha cada item cai. Com a chave pública, o atacante escolhe; com a chave secreta, não.
Quem faz uma pergunta, olha a resposta e usa isso para escolher o próximo passo. A garantia comum não cobre esse caso; o TRUSS foi desenhado para ele.
Onde isso pode estar errado.
Nem toda defesa é completa
Rodar várias cópias e tirar a mediana reduziu o ataque adaptativo em 2 a 3 vezes, sem zerar. A defesa completa contra quem se adapta, a troca de cópias, está feita para a soma dos quadrados. A contagem de distintos está protegida do garimpo pela chave secreta. Outras estatísticas estão em andamento.
A chave precisa ser guardada
Para juntar contadores de máquinas diferentes, todos usam a mesma chave secreta. Se ela vazar, volta o problema do cadeado com a senha no manual.
O primeiro ataque falhou
Tentar inventar um item frequente no Count-Min não funcionou: 1 erro em 100 mil perguntas. Ele só erra para cima de um jeito limitado. O ataque que funcionou mira outro tipo de contador, e registramos os dois.
Um laboratório, não a sua carga
Os números vêm de testes com 30 mil a 100 mil itens. Em produção, o tamanho do resumo e o volume mudam o erro típico; o que não muda é a diferença entre chave pública e secreta.
← Telemetria certificada · stickybit.com.br
- Medições próprias com a biblioteca TRUSS (Go): ataque de garimpo contra Redis 8.8 instalado (30.000 distintos contados como 1; TRUSS 29.705) e contra Apache DataSketches 6.1.1 Theta (50 mil contados como 13,1 milhões; TRUSS dentro de 1%); caso de limite de uso de IA (1.000 pedidos, US$ 0,10 cada); troca de cópias sobre a soma dos quadrados (2,1× contra 1,0×).
- Ben-Eliezer, Jayaram, Woodruff e Yogev, "A Framework for Adversarially Robust Streaming Algorithms", Journal of the ACM, 2022.
- Cohen e colegas, ataques ao CountSketch, ICML 2022.
- Flajolet e colegas, HyperLogLog (2007): erro típico de 1,04/√m, onde m é o número de caixinhas.