SketchProbe: Discovering Vulnerabilities in Sketch-based Applications with Reinforcement Learning

Abstract

Sketches are approximate data structures critical to network traffic monitoring. Theyare specifically designed for environments constrained by memory, enabling the maintenance of accurate statistics within a compact space. This efficiency comes at the cost of estimation error that varies based on the workload encountered by the sketch. Traditionally, sketch-based applications are optimized for average traffic scenarios, and this assumption of standard patterns of network traffic introduces vulnerabilities, as these applications may not be prepared for atypical or adversarial traffic patterns. Manual testing for these vulnerabilities is time-intensive and often impractical due to the vast range of possible traffic scenarios. In this paper, we introduce SketchProbe, a novel system leveraging Reinforcement Learning (RL) to identify adversarial traffic patterns in sketch-based applications. Unlike manual identification, SketchProbe automates the discovery process, ensuring a thorough and efficient exploration of potential failure modes. Our evaluation indicates that SketchProbe effectively identifies critical scenarios that significantly impact the performance of sketch-based applications, which is valuable for improving the robustness of such applications.