Online sketching of network flows for real-time stepping-stone detection

Baris Coskun, Nasir Memon

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present an efficient and robust stepping-stone detection scheme based on succinct packet-timing sketches of network flows. The proposed scheme employs an online algorithm to continuously maintain short sketches of flows from a stream of captured packets at the network boundary. These sketches are then used to identify pairs of network flows with similar packet-timing characteristics, which indicates potential stepping-stones. Succinct flow sketches enable the proposed scheme to compare a given pair of flows in constant time. In addition, flow sketches identify pairs of correlated flows from a given list of flows in sub-quadratic time, thereby allowing a more scalable solution as compared to known schemes. Finally, the proposed scheme is resistant to random delays and chaff, which are often employed by attackers to evade detection. To explore its efficacy, we mathematically analyze the robustness properties of the proposed flow sketch. We also experimentally measure the detection performance of the proposed scheme.

Original languageEnglish (US)
Title of host publication25th Annual Computer Conference Security Applications, ACSAC 2009
Number of pages11
StatePublished - 2009
Event25th Annual Computer Conference Security Applications, ACSAC 2009 - Honolulu, HI, United States
Duration: Dec 7 2009Dec 11 2009

Publication series

NameProceedings - Annual Computer Security Applications Conference, ACSAC
ISSN (Print)1063-9527


Other25th Annual Computer Conference Security Applications, ACSAC 2009
Country/TerritoryUnited States
CityHonolulu, HI


  • Data sketching
  • Network security
  • Stepping-stones
  • Streaming algorithms

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software
  • Safety, Risk, Reliability and Quality

Cite this