Enthüllung von Verwundbarkeiten: Kardinalitäts-Skizzen unter adaptiven Eingaben

Kardinalitäts-Skizzen sind beliebte Datenstrukturen, die die Effizienz bei der Verarbeitung großer Datensätze erhöhen. Die Skizzen sind randomisierte Darstellungen von Mengen, die nur logarithmische Größe haben, aber Mengenfusionen und annähernde Kardinalitätsanfragen (d.h. distinct count) unterstützen können. Wenn Anfragen nicht adaptiv sind, d.h. sie von vorhergehenden Abfrageantworten unabhängig sind, bietet das Design starke Garantien für die korrekte Beantwortung einer Anzahl von Anfragen, die exponentiell in der Skizzengröße k sind. In dieser Arbeit untersuchen wir die Leistung von Kardinalitäts-Skizzen in adaptiven Einstellungen und enthüllen inhärente Verwundbarkeiten. Wir entwerfen einen Angriff gegen die "Standard"-Schätzer, der einen gegnerischen Eingang konstruiert, indem er die Antworten auf eine Reihe von einfachen nicht-adaptiven Anfragen von linearer Größe in der Skizzengröße k nachbearbeitet. Empirisch verwendete unser Angriff nur 4k Anfragen mit der weit verbreiteten HyperLogLog (HLL++) ~hyperloglog: 2007, hyperloglogpractice: EDBT2013 Skizze. Die einfache Angriffstechnik zeigt, dass sie auch mit nachbearbeiteten natürlichen Arbeitslasten effektiv sein kann. Schließlich und wichtig ist, dass wir zeigen, dass die Verwundbarkeit inhärent ist, da jeder Schätzer, der auf bekannte Skizzenstrukturen angewendet wird, mit einer Anzahl von Anfragen, die quadratisch in k ist, angegriffen werden kann, was einer generischen oberen Grenze entspricht.