Method for estimating the fan-in and/or fan-out of a node
View Patent ↗A method for detecting anomalies in traffic patterns and a traffic anomalies detector are presented. The method and the detector are based on estimating the fan-in of a node, i.e. the number of distinct sources sending traffic to a node, based on infrequent, periodic sampling. Destinations with an abnormally large fan-in are likely to be the target of an attack, or to be downloading large amounts of material with a P2P application. The method and the anomalies detector are extremely simple to implement and exhibit excellent performance on real network traces.
1. A method performed by an anomalies detector for tracking anomalous activity in a data packet network, the method comprising:
sampling, at the anomalies detector, over a predetermined time window a number of sampled packets, for determining a packet source address (PSA) and a packet destination address (PDA) of each said sampled packet; and
determining at least one of:
a fan-in count for said PDA by incrementing a counter for said PDA whenever said PSA of said sampled packet is not the same as a most recently seen source address (MRSS) for said PDA, and
a fan-out count for said PSA by incrementing a counter for said PSA whenever said PDA of said sampled packet is not the same as a most recently seen destination address (MRSD) for said PSA.
2. The method of claim 1 , further comprising, when said fan-in count is determined, identifying at the end of said time window if any of said destination addresses is a target destination address for an anomalous activity if said respective fan-in count is abnormally large with respect to a preset threshold.
3. The method of claim 2 , further comprising:
providing a plurality of observation points throughout said network; and
generating at each said observation point a list with partial fan-in counts for a specified number of target destination addresses.
4. The method of claim 3 , further comprising:
automatically transmitting said list from each said observation point to an inspection facility at the end of said time window; and
at said inspection facility, for each target destination address, determining an estimated value of the total number of packets Fanin(d) destined to said target destination address by aggregating said partial fan-in counts that have said target destination address.
5. The method of claim 1 , further comprising, when said fan-out count is determined, identifying at the end of said time window if any of said source addresses is an origin of anomalous activity if said respective fan-out count is abnormally large with respect to a preset threshold.
6. The method of claim 5 , further comprising:
providing a plurality of observation points throughout said network; and
generating at each said observation point a list with partial fan-out counts for a specified number of suspect source addresses.
7. The method of claim 6 , further comprising:
automatically transmitting said list from each said observation point to an inspection facility at the end of said time window; and
at said inspection facility, for each suspect source address, determining an estimated value of a total number of packets transmitted from said suspect source address by aggregating said partial fan-out counts that have said suspect source address.
8. A traffic anomalies detector for tracking anomalous activity in a data packet network, the detector comprising:
a sampling unit that samples a number of sampled packets seen by said detector over a predetermined time window;
a storing means that maintains at least one of:
a fan-in count and a most recently seen source address (MRSS) for at least one observed destination address, and
a fan-out count and a most recently seen destination address (MRSD) for at least one observed source address; and
an address resolving processor that determines a packet source address (PSA) and a packet destination address (PDA) of each said sampled packet and performs at least one of:
when said storing means maintains a fan-in count and an MRSS for said PDA, setting said MRSS equal to said PSA whenever said PSA is not the same as said MRSS, and
when said storing means maintains a fan-out count and an MRSD for said PSA, setting said MRSD equal to said PDA whenever said PDA is not the same as said MRSD.
9. The detector of claim 8 further comprising a timer for setting said predetermined time window.
10. The detector of claim 8 , wherein said fan-in count is provided as a destinations table comprising:
one row for each destination address identified by said address resolving processor;
a first column identifying the destination address of each sampled packet;
a second column identifying the most recently seen source address for the respective destination address in the first column; and
a counter column that provides an approximation to the number of source addresses that have said destination address in said first column.
11. The detector of claim 10 , wherein said destinations table is implemented with a hash table, where each destination address is associated to a row with an index H(d) for the selected hash function.
12. The detector of claim 8 , further comprising a table management unit for identifying at the end of said time window if any of said destination addresses is a target destination address for any anomalous activity.
13. The detector of claim 8 further comprising a counter management unit for updating said fan-in count whenever said most recently seen source address corresponding to said destination address changes.
14. The detector of claim 8 , wherein said fan-out count is provided as a sources table comprising:
one row for each source address identified by said address resolving processor;
a first column identifying the source of each sampled packet;
a second column identifying the most recently seen destination address for the respective source address in the first column; and
a counter column that provides an approximation to the number of destination addresses that have said source address in said first column.
15. The detector of claim 14 , wherein said sources table is implemented with a hash table, where each source address is associated to a row with an index H(d) for the selected hash function.
16. The detector of claim 14 , further comprising a table management unit for identifying at the end of said time window if any of said source addresses is transmitting malware traffic.
17. The detector of claim 14 further comprising a counter management unit for updating said fan-out count whenever said most recently seen destination address corresponding to said destination address changes.