Lightweight packet-drop detection for ad hoc networks

• US 9,065,753 B2
• Filed: 10/21/2009
• Issued: 06/23/2015
• Est. Priority Date: 12/13/2004
• Status: Expired due to Fees

• Current Assignee: Nytell Software LLC (Intellectual Ventures LLC)
• Original Assignee: TTI Inventions A LLC (Intellectual Ventures LLC)
• Inventors: Talpade, Rajesh R., Farooq, Anjum
• Primary Examiner(s): TAYLOR, BARRY W
• Application Number:
  US12/603,182
• Publication Number:
  US 20100050258A1
• Time in Patent Office: 2,071 Days
• Field of Search: 370/252, 370/254, 370/232, 370/235, 370/315
• US Class Current: 1/1
• CPC Class Codes: H04L 2463/143 Denial of service attacks involving systematic or selective dropping of packets
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 43/067 using time frame reporting
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection
• CPC Class Codes: H04W 12/122 Counter-measures against attacks; Protection against rogue devices
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

In packet-drop attacks in ad hoc networks, a malicious network node chooses to selectively drop packets that are supposed to be forwarded, which results in adverse impact on application good-put and network stability. A method and system for detection of packet-drop attacks in ad hoc networks requires network nodes to report statistics on IP flow packets originated, received, or forwarded to neighbors. These statistics are analyzed and correlated to determine nodes suspected of dropping packets.

Claims

1. A method for determining nodes suspected of dropping packets, the method comprising:

creating statistics at a network node in a network, wherein the statistics correspond to a flow of Internet Protocol (IP) packets received at or transmitted from the network node, and wherein the statistics include information related to neighboring nodes, the information comprising an IP address of a neighboring node and a number of IP packets transmitted from the network node to the neighboring node during a first time period; and

transmitting the statistics from the network node to a coordination node for determining network nodes suspected of dropping packets, wherein the coordination node maintains a suspect-counter entry for each of a plurality of network nodes, and wherein the suspect-counter entry indicates a likelihood that a respective network node is dropping packets, wherein the coordination node is configured to compare a first number of IP packets received by the respective network node and a second number of IP packets transmitted by the respective network node to a third number of IP packets received by a first neighboring node and a fourth number of IP packets transmitted by a second neighboring node, and increment a first suspect-counter entry for the respective network node and a second suspect-counter entry for the neighboring node if the number of IP packets transmitted from the respective network node to the neighboring node is not equal to a statistic received from the neighboring node indicating a number of IP packets received at the neighboring node.

2. The method of claim 1, wherein the statistics include a unique flow identification corresponding to a source address of the IP packets and a destination address of the IP packets in the flow.

3. The method of claim 1, wherein the statistics include the number of IP packets received at the network node.

4. The method of claim 1, wherein the statistics include a time when the network node begins collecting data on the flow.

5. The method of claim 1, further comprising storing the statistics in a database maintained by the network node.

6. The method of claim 5, further comprising incrementing a statistic corresponding to a number of IP packets received at the network node in response to receiving an IP packet at the network node, wherein the statistic corresponding to the number of IP packets received at the network node is stored in the database.

7. The method of claim 5, further comprising incrementing the number of IP packets transmitted from the network node to the neighboring node in response to transmitting an IP packet from the network node to the neighboring node.

8. The method of claim 5, further comprising resetting a timer corresponding to a second time period for which the flow is non-active.

9. The method of claim 5, further comprising resetting the statistics in the database corresponding to the flow after the statistics are transmitted to the coordination node.

10. The method of claim 1, wherein the transmitting the statistics is performed after the first time period has ended.

11. A network node comprising:

a processor configured to create statistics corresponding to a flow of Internet Protocol (IP) packets received at or transmitted from the network node, and wherein the statistics include information related to neighboring nodes, the information comprising an IP address of a neighboring node and a number of IP packets transmitted from the network node to the neighboring node during a first time period; and

a transmitter configured to transmit the statistics from the network node to a coordination node for determining network nodes suspected of dropping packets, wherein the coordination node maintains a suspect-counter entry for each of a plurality of network nodes, and wherein the suspect-counter entry indicates a likelihood that a respective network node is dropping packets, wherein the coordination node is configured to compare a first number of IP packets received by the respective network node and a second number of IP packets transmitted by the respective network node to a third number of IP packets received by a first neighboring node and a fourth number of IP packets transmitted by a second neighboring node, and increment a first suspect-counter entry for the respective network node and a second suspect-counter entry for the neighboring node if the number of IP packets transmitted from the respective network node to the neighboring node is not equal to a statistic received from the neighboring node indicating a number of IP packets received at the neighboring node.

12. The network node of claim 11, wherein the statistics include a unique flow identification corresponding to a source address of an IP packet and a destination address of the IP packet.

13. The network node of claim 11, wherein the statistics include the number of IP packets received at the network node.

14. The network node of claim 11, wherein the statistics include a time when the network node begins collecting data on the flow.

15. The network node of claim 11, further comprising storing the statistics in a database maintained by the network node.

16. The network node of claim 15, wherein the processor is further configured to increment a statistic corresponding to a number of IP packets received at the network node in response to receiving an IP packet at the network node, wherein the statistic corresponding to the number of IP packets received at the network node is stored in the database.

17. The network node of claim 15, wherein the processor is further configured to increment the number of IP packets transmitted from the network node to the neighboring node in response to transmitting an IP packet from the network node to the neighboring node.

18. The network node of claim 15, wherein the processor is further configured to reset a timer corresponding to a second time period for which the flow is non-active.

19. The network node of claim 15, wherein the processor is further configured to reset the statistics in the database corresponding to the flow after the statistics are transmitted to the coordination mode.

20. The network node of claim 11, wherein the transmitter is further configured to transmit the statistics after the first time period has ended.

21. A method comprising:

receiving statistics at a coordination node from a network node in a network, wherein the statistics correspond to a flow of Internet Protocol (IP) packets received at or transmitted from the network node, and wherein the statistics include information related to neighboring nodes, the information comprising an IP address of a neighboring node and a number of IP packets transmitted from the network node to the neighboring node during a time period; and

analyzing the statistics to determine network nodes suspected of dropping packets, wherein the coordination node maintains a suspect-counter entry for each of a plurality of network nodes, and wherein the suspect-counter entry indicates a likelihood that a respective network node is dropping packets, wherein the analyzing the statistics comprises comparing a first number of IP packets received by the respective network node and a second number of IP packets transmitted by the respective network node to a third number of IP packets received by a first neighboring node and a fourth number of IP packets transmitted by a second neighboring node, and incrementing a first suspect-counter entry for the respective network node and a second suspect-counter entry for the neighboring node if the number of IP packets transmitted from the respective network node to the neighboring node is not equal to a statistic received from the neighboring node indicating a number of IP packets received at the neighboring node.

22. The method of claim 21, further comprising incrementing a suspect-counter entry for the network node if the number of IP packets received by the network node is not equal to a number of IP packets transmitted to neighboring nodes.

23. The method of claim 21, further comprising decrementing the first suspect-counter entry for the respective network node and the second suspect-counter entry for the neighboring node if the number of IP packets transmitted from the respective network node to the neighboring node is equal to a statistic received from the neighboring node indicating a number of IP packets received at the neighboring node.

24. The method of claim 21, further comprising ranking the plurality of network nodes according to the suspect-counter entry for each of the plurality of network nodes.

25. A coordination node comprising:

a receiver configured to receive statistics from a network node, wherein the statistics correspond to a flow of Internet Protocol (IP) packets received at or transmitted from the network node, and wherein the statistics include information related to neighboring nodes, the information comprising an IP address of a neighboring node and a number of flow packets transmitted from the network node to the neighboring node during a time period; and

a processor configured to analyze the statistics to determine network nodes suspected of dropping packets, wherein the processor is configured to maintain a suspect-counter entry for each of a plurality of network nodes at a database, and wherein the suspect-counter entry indicates a likelihood that a respective network node is dropping packets, wherein the processor is configured to compare a first number of IP packets received by the respective network node and a second number of IP packets transmitted by the respective network node to a third number of IP packets received by a first neighboring node and a fourth number of IP packets transmitted by a second neighboring node, and increment a first suspect-counter entry for the respective network node and a second suspect-counter entry for the neighboring node if the number of IP packets transmitted from the respective network node to the neighboring node is not equal to a statistic received from the neighboring node indicating a number of IP packets received at the neighboring node.

26. The coordination node of claim 25, wherein the processor is configured to increment a suspect-counter entry for the network node if the number of IP packets received by the network node is not equal to a number of IP packets transmitted to neighboring nodes.

27. The coordination node of claim 25, wherein the processor is configured to decrement the first suspect-counter entry for the network node and the second suspect-counter entry for the neighboring node if the number of IP packets transmitted from the respective network node to the neighboring node is equal to a statistic received from the neighboring node indicating a number of IP packets received at the neighboring node.

28. The coordination node of claim 25, wherein the processor is configured to rank the plurality of network nodes according to the suspect-counter entry for each of the plurality of network nodes.

29. A system for determining nodes suspected of dropping packets in a network, the system comprising:

a plurality of network nodes configured to report statistics corresponding to a flow of Internet Protocol (IP) packets received at or transmitted from each of the plurality of network nodes, and wherein the statistics include information related to neighboring nodes, the information comprising an IP address of a neighboring node and a number of IP packets transmitted from each of the plurality of network nodes to the neighboring node during a time period; and

a coordination node configured to receive the statistics from each of the plurality of network nodes and analyze the statistics to determine network nodes suspected of dropping packets, wherein the coordination node is configured to compare a first number of IP packets received by a first network node of the plurality of network nodes and a second number of IP packets transmitted by the first network node to a third number of IP packets received by a first neighboring node and a fourth number of IP packets transmitted by a second neighboring node, and increment a first suspect-counter entry for a first network node and a second suspect-counter entry for the neighboring node if the number of IP packets transmitted from the first network node to the neighboring node is not equal to a statistic received from the neighboring node indicating a number of IP packets received at the neighboring node.

30. The system of claim 29, wherein the coordination node is configured to maintain a suspect-counter entry at a database for each of the plurality of network nodes, and wherein the suspect-counter entry indicates a likelihood that a respective network node is dropping packets.

31. The system of claim 30, wherein the coordination node is configured to increment a suspect-counter entry for the first network node of the plurality of network nodes if a number of IP packets received by the first network node is not equal to a number of IP packets transmitted to neighboring nodes.