How do I get IPs that sent more than X packets in less than a given time

Question

I have a C# program that detects incoming TCP/IP packets on any given ethernet device. Every packet is processed in the following struct:

struct Packet{
   String sourceIp;
   DateTime arrivalDate;
}

If I have a List of every incoming Packets (List), how do I get those IPs that have more than X packets in less than Y seconds (say 1 second)?

I have no idea how to approach this problem, any help/tip will be highly appreciated.

If you already have the list, you just need to count and filter. Where's the problem? — Mahmoud Al-Qudsi, May 26 '12 at 22:04
@MahmoudAl-Qudsi if it's so easy, add a solution. Don't assume just because it seems trivial to you that it's trivial to everyone. — jb., May 26 '12 at 22:24
Take a look at this. http://stackoverflow.com/questions/448203/linq-to-sql-using-group-by-and-countdistinct — paparazzo, May 26 '12 at 23:08
@jb I have issues when questions show zero attempt at even attempting to reason out what needs to take place. — Mahmoud Al-Qudsi, May 26 '12 at 23:29
@MahmoudAl-Qudsi I posted what I have done to this moment. Believe me, I've tried several times to aproach this situation. — Guj Mil, May 27 '12 at 00:45

agent-j · Accepted Answer · 2012-05-26T22:11:12.210

Using Linq, it will be something like this:

  List<Packet> allPackets =
     new List<Packet>
        {
           new Packet {arrivalDate = DateTime.Parse("2000-01-01 0:00:00"), sourceIp = "a"},
           new Packet {arrivalDate = DateTime.Parse("2000-01-01 0:00:01"), sourceIp = "a"},
           new Packet {arrivalDate = DateTime.Parse("2000-01-01 0:00:01"), sourceIp = "a"},
           new Packet {arrivalDate = DateTime.Parse("2000-01-01 0:01:00"), sourceIp = "a"},
           new Packet {arrivalDate = DateTime.Parse("2000-01-01 0:00:00"), sourceIp = "b"},
           new Packet {arrivalDate = DateTime.Parse("2000-01-01 0:01:00"), sourceIp = "b"},
           new Packet {arrivalDate = DateTime.Parse("2000-01-01 0:02:00"), sourceIp = "b"},
           new Packet {arrivalDate = DateTime.Parse("2000-01-01 0:03:00"), sourceIp = "b"},
        };
  var xPackets = 2;
  var interval = TimeSpan.FromSeconds(15);

  // We group all the packets by ip, then within that, order the packets by date.
  var ips =
     allPackets
        .GroupBy(
           p => p.sourceIp,
           (ip, packets) => new
                                {
                                   ip,
                                   packets = packets.OrderBy(p => p.arrivalDate).ToList()
                                })
        .ToList();
  // Build a list of IPs with at least x packets in y interval.
  var rapidIps = new List<string>();
  foreach (var ipPacket in ips)
  {
     for (int i = 0, j = xPackets; j < ipPacket.packets.Count; i++, j++)
     {
        if (ipPacket.packets[i].arrivalDate + interval >= ipPacket.packets[j].arrivalDate)
        {
           rapidIps.Add((ipPacket.ip));
           break;
        }

     }
  }

At the end, rapidIps contains [a].

Since the question is like a filter to prevent Denial Of Services, and i think that you should comment on the Big O of your code. — BachT, May 27 '12 at 00:15
@Bach, Good idea. The linq expression appears to be `O(n)` + the foreach/for is O(n). So it's `O(n)` + `O(n)` = `O(n)`. http://stackoverflow.com/questions/2799427/what-guarantees-are-there-on-the-run-time-complexity-big-o-of-linq-methods — agent-j, May 27 '12 at 02:08

How do I get IPs that sent more than X packets in less than a given time

1 Answers1