A Robust Counting Sketch for Data Plane Intrusion Detection

Sian Kim, Changhun Jung, Rhongho Jang, David Mohaisen, Dae Hun Nyang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

— Demands are increasing to measure per-flow statistics in the data plane of high-speed switches. However, the resource constraint of the data plane is the biggest challenge. Although existing in-data plane solutions improve memory efficiency by accommodating Zipfian distribution of network traffic, they cannot adapt to various flow size distributions due to their static data structure. In other words, they cannot provide robust flow measurement under complex traffic patterns (e.g., under attacks). Recent works suggest dynamic data structure management schemes, but the high complexity is the major obstruction for the data plane deployment. In this paper, we present CountLess (CL) sketch that enables robust and accurate network measurement under a wide variety of traffic distributions without dynamic data structure updates. Count-Less adopts a novel sketch update strategy, called minimum update (CL-MU), which approximates the conservative update strategy of Count-Min for fitting into in-network switches. Not only theoretical proof on CL-MU’s estimation but also comprehensive experimental results are presented in terms of estimation accuracy and throughput of CL-MU, compared to Count-Min (baseline), Elastic sketch, and FCM sketch. More specifically, experiment results on security applications including estimation errors under various skewness parameters are provided. CL-MU is much more accurate in all measurement tasks than Count-Min and outperforms FCM sketch and Elastic sketch, state-of-the-art algorithms without the help of any special hardware like TCAM. To prove its feasibility in the data plane of a high-speed switch, CL-MU prototype on an ASIC-based programmable switch (Tofino) is implemented in P4 language and evaluated. In terms of data plane latency, CL-MU is faster than FCM, while consuming fewer resources such as hash bits, SRAM, and ALU of a programmable switch.

Original languageEnglish
Title of host publication30th Annual Network and Distributed System Security Symposium, NDSS 2023
PublisherThe Internet Society
ISBN (Electronic)1891562835, 9781891562839
DOIs
StatePublished - 2023
Event30th Annual Network and Distributed System Security Symposium, NDSS 2023 - San Diego, United States
Duration: 27 Feb 20233 Mar 2023

Publication series

Name30th Annual Network and Distributed System Security Symposium, NDSS 2023

Conference

Conference30th Annual Network and Distributed System Security Symposium, NDSS 2023
Country/TerritoryUnited States
CitySan Diego
Period27/02/233/03/23

Bibliographical note

Publisher Copyright:
© 2023 30th Annual Network and Distributed System Security Symposium, NDSS 2023. All Rights Reserved.

Fingerprint

Dive into the research topics of 'A Robust Counting Sketch for Data Plane Intrusion Detection'. Together they form a unique fingerprint.

Cite this