TrustSketch: Trustworthy Sketch-based Telemetry on Cloud Hosts

—Cloud providers deploy telemetry tools in software to perform end-host network analytics. Recent efforts show that sketches, a kind of approximate data structure, are a promising basis for software-based telemetry, as they provide high fidelity for many statistics with a low resource footprint. However, an attacker can compromise sketch-based telemetry results via software vulnerabilities. Consequently, they can nullify the use of telemetry; e.g., avoiding attack detection or inducing accounting discrepancies. In this paper, we formally define the requirements for trustworthy sketch-based telemetry and show that prior work cannot meet those due to the sketch’s probabilistic nature and performance requirements. We present the design and implementation T RUST S KETCH , a general framework for trustworthy sketch telemetry that can support a wide spectrum of sketching algorithms. We show that T RUST S KETCH is able to detect a wide range of attacks on sketch-based telemetry in a timely fashion while incurring only minimal overhead.