Carousel: scalable logging for intrusion prevention systems

摘要: We address the problem of collecting unique items in a large stream information context Intrusion Prevention Systems (IPSs). IPSs detect attacks at gigabit speeds and must log infected source IP addresses for remediation or forensics. An attack with millions sources can result hundreds records when counting duplicates. If logging are much slower than packet arrival rates memory IPS is limited, scalable technical challenge. After showing that naive approaches will not suffice, we solve new algorithm call Carousel. Carousel randomly partitions set into groups be logged without duplicates, then cycles through possible groups. prove collects almost all high probability close to optimal time as long keep transmitting. describe details Snort implementation hardware design. Simulations worm propagation models show up factor 10 improvement collection times practical scenarios. Our technique applies any non-cooperative appears repeatedly.