Lightweight packet-drop detection for ad hoc networks

• US 20060239203A1
• Filed: 12/12/2005
• Published: 10/26/2006
• Est. Priority Date: 12/13/2004
• Status: Active Grant

• Current Assignee: Nytell Software LLC (Intellectual Ventures LLC)
• Original Assignee: Telcordia Licensing Co LLC (Telefonaktiebolaget LM Ericsson)
• Inventors: Farooq, Anjum, Talpade, Rajesh R.
• Granted Patent: US 7,706,296 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• 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 of determining nodes suspected of dropping packets in an ad hoc network comprising the steps of:

creating statistics at network nodes in the ad hoc network regarding IP flow packets originated, received, or forwarded to neighbors; and

analyzing the statistics to determine network nodes suspected of dropping packets.

2. A method as set forth in claim 1, where said creating statistics comprises:

initiating flow database at node to null;

for each IP packet originated at or transiting node;

check if source and destination IP address pair exists in flow database if flow does not exist;

create new entry for flow (defined by unique source and destination IP address pair);

set Sampling-Start-Time to current time;

increment Received-Packet-Count;

increment Forwarded-Packet-Count for current Next-Hop-IP;

if current Next-Hop-IP does not exist in Next-Hop-Structure, create entry and update;

else, update existing entry;

reset Liveness for flow; and

go to check if source and destination IP address pair exists in flow database for next flow step.

3. A method as set forth in claim 2, further comprising forwarding the statistics to a coordinator node.

4. A method as set forth in claim 1, where said creating statistics comprises:

initiate Reporting-Time-Slot;

when current Reporting-Time-Slot ends

for all flows in database

send report to coordinator node that includes following information obtained from the flow'"'"'s database entry;

source and destination IP, Sampling-Start-Time, Received-Packet-Count, and Next-Hop-Structure;

reduce Liveness in flow'"'"'s database entry by Reporting-Time-Slot;

if Liveness≦

zero, delete flow from database;

else,

in the flow'"'"'s database entry, reset Sampling-Start-Time to the current time, Received-Packet-Count to zero, and Forwarded-Packet-Count for all Next-Hop-IP in Next-Hop-Structure to zero; and

Go to initiate Reporting-Time-Slot step.

5. A method as set forth in claim 4, further comprising forwarding the statistics to a coordinator node.

6. A method as set forth in claim 1, where said analyzing the statistics comprises:

for each received message from a network node

separate out reports for individual flows within message;

for each individual flow report in message

if no entry exists for that flow in Flow-List maintained at coordinator node

create new entry for flow (Each Flow-List entry includes a list of nodes (Flow-Node-List) that have sent reports about flow);

start Flow-Timer for flow 704;

if no entry exists for node in Flow-Node-List of Flow-List

create new entry for node (Each entry in Flow-Node-List has Report-Duration=(current time−

Sampling-Start-Time), Received-Packet-Count, and Next-Hop-Structure);

else if entry for node exists in Flow-Node-List, then ignore report since it is duplicate (each node sends one report per flow during each Reporting-Time-Slot); and

go to separate out reports for individual flows within message step.

7. A method as set forth in claim 6, further comprising:

when a Flow-Timer expires, for each node entry X in Flow-Node-List belonging to flow;

if Received-Packet-Count is not equal to the sum of Forwarded-Packet-Count for all Next-Hop-IP in Next-Hop-Structure, increment Suspect-Counter for node X by difference/Received-Packet-Count;

for each node entry X in Flow-Node-List belonging to flow

for each Next-Hop-IP in Next-Hop-Structure, decrement Received-Packet-Count in Next-Hop-IP'"'"'s Flow-Node-List entry, by Forwarded-Packet-Count in Next-Hop-Structure of X;

for each node entry X in Flow-Node-List belonging to flow

if abs(Received-Packet-Count)/(sum of Forwarded-Packet-Count)>

Permissible-Packet-Loss increment Suspect-Counter in Network-Node-List entry for node X, by abs(Received-Packet-Count)/(sum of Forwarded-Packet-Count) and increment Suspect-Counter in Network-Node-List entry for all nodes that list X as Next-Hop-IP in their Flow-Node-List entry, by abs(Received-Packet-Count)/(sum of Forwarded-Packet-Count) 806.

else

decrement Suspect-Counter in Network-Node-List entry for node X, by Credit-Value and decrement Suspect-Counter in Network-Node-List entry for all nodes that list X as Next-Hop-IP in their Flow-Node-List entry, by Credit-Value; and

delete flow entry from unique flow list.

8. A method as set forth in claim 7, further comprising:

set LiPaD-Timer;

when LiPaD-Timer expires, generate ordered list of “

suspect”

nodes by Suspect-Counter values; and

go to set LiPaD Timer step.

9. A method as set forth in claim 8, further comprising said analyzing the statistics penalizing and rewarding network nodes for identifying lying nodes.

10. An ad hoc network including lightweight packet-drop detection comprising:

a plurality of network nodes reporting statistics regarding IP flow packets originated, received, or forwarded to neighbor network nodes; and

at least one coordinator node associated with one or more network nodes for receiving the reports and analyzing the statistics for determining network nodes suspected of dropping packets.

11. An ad hoc network as set forth in claim 10, where each network node reports statistics by:

initiating flow database at node to null;

for each IP packet originated at or transiting node;

check if source and destination IP address pair exists in flow database if flow does not exist;

create new entry for flow (defined by unique source and destination IP address pair);

set Sampling-Start-Time to current time;

increment Received-Packet-Count;

increment Forwarded-Packet-Count for current Next-Hop-IP;

if current Next-Hop-IP does not exist in Next-Hop-Structure, create entry and update;

else, update existing entry;

reset Liveness for flow; and

go to check if source and destination IP address pair exists in flow database for next flow step.

12. An ad hoc network as set forth in claim 10, where each network node reports statistics by:

initiate Reporting-Time-Slot;

when current Reporting-Time-Slot ends

for all flows in database

send report to coordinator node that includes following information obtained from the flow'"'"'s database entry;

source and destination IP, Sampling-Start-Time, Received-Packet-Count, and Next-Hop-Structure;

reduce Liveness in flow'"'"'s database entry by Reporting-Time-Slot;

if Liveness≦

zero, delete flow from database;

else,

in the flow'"'"'s database entry, reset Sampling-Start-Time to the current time, Received-Packet-Count to zero, and Forwarded-Packet-Count for all Next-Hop-IP in Next-Hop-Structure to zero; and

go to initiate Reporting-Time-Slot step.

13. An ad hoc network as set forth in claim 10, where said coordinator node analyzes the statistics by:

for each received message from a network node

separate out reports for individual flows within message;

for each individual flow report in message

if no entry exists for that flow in Flow-List maintained at coordinator node

create new entry for flow (Each Flow-List entry includes a list of nodes (Flow-Node-List) that have sent reports about flow);

start Flow-Timer for flow 704;

if no entry exists for node in Flow-Node-List of Flow-List

create new entry for node (Each entry in Flow-Node-List has Report-Duration=(current time−

Sampling-Start-Time), Received-Packet-Count, and Next-Hop-Structure);

else if entry for node exists in Flow-Node-List, then ignore report since it is duplicate (each node sends one report per flow during each Reporting-Time-Slot);

go to separate out reports for individual flows within message step;

when a Flow-Timer expires, for each node entry X in Flow-Node-List belonging to flow;

if Received-Packet-Count is not equal to the sum of Forwarded-Packet-Count for all Next-Hop-IP in Next-Hop-Structure, increment Suspect-Counter for node X by difference/Received-Packet-Count;

for each node entry X in Flow-Node-List belonging to flow

for each Next-Hop-IP in Next-Hop-Structure, decrement Received-Packet-Count in Next-Hop-IP'"'"'s Flow-Node-List entry, by Forwarded-Packet-Count in Next-Hop-Structure of X;

for each node entry X in Flow-Node-List belonging to flow

if abs(Received-Packet-Count)/(sum of Forwarded-Packet-Count)>

Permissible-Packet-Loss increment Suspect-Counter in Network-Node-List entry for node X, by abs(Received-Packet-Count)/(sum of Forwarded-Packet-Count) and increment Suspect-Counter in Network-Node-List entry for all nodes that list X as Next-Hop-IP in their Flow-Node-List entry, by abs(Received-Packet-Count)/(sum of Forwarded-Packet-Count) 806.

else

decrement Suspect-Counter in Network-Node-List entry for node X, by Credit-Value and decrement Suspect-Counter in Network-Node-List entry for all nodes that list X as Next-Hop-IP in their Flow-Node-List entry, by Credit-Value;

delete flow entry from unique flow list;

a plurality of network nodes reporting statistics regarding IP flow packets originated, received, or forwarded to neighbor network nodes; and

at least one coordinator node associated with one or more network nodes for receiving the reports and determining network nodes suspected of dropping packets.

14. A program storage device, readable by machine, tangibly embodying a program of instructions executable by the machine to cause the machine to perform a method for reporting statistics regarding IP flow packets, comprising the steps of:

initiating flow database at node to null;

for each IP packet originated at or transiting node;

check if source and destination IP address pair exists in flow database

if flow does not exist;

create new entry for flow (defined by unique source and destination IP address pair);

set Sampling-Start-Time to current time;

increment Received-Packet-Count;

increment Forwarded-Packet-Count for current Next-Hop-IP;

if current Next-Hop-IP does not exist in Next-Hop-Structure, create entry and update;

else, update existing entry;

reset Liveness for flow;

go to check if source and destination IP address pair exists in flow database for next flow step; and

initiate Reporting-Time-Slot;

when current Reporting-Time-Slot ends

for all flows in database

send report to coordinator node that includes following information obtained from the flow'"'"'s database entry;

source and destination IP, Sampling-Start-Time, Received-Packet-Count, and Next-Hop-Structure;

reduce Liveness in flow'"'"'s database entry by Reporting-Time-Slot;

if Liveness≦

zero, delete flow from database;

else,

in the flow'"'"'s database entry, reset Sampling-Start-Time to the current time, Received-Packet-Count to zero, and Forwarded-Packet-Count for all Next-Hop-IP in Next-Hop-Structure to zero; and

go to initiate Reporting-Time-Slot step.

15. A program storage device, readable by machine, tangibly embodying a program of instructions executable by the machine to cause the machine to perform a method for analyzing statistics for determining network nodes suspected of dropping packets in an ad hoc network, comprising the steps of:

for each received message from a network node

separate out reports for individual flows within message;

for each individual flow report in message

if no entry exists for that flow in Flow-List maintained at coordinator node

create new entry for flow (Each Flow-List entry includes a list of nodes (Flow-Node-List) that have sent reports about flow);

start Flow-Timer for flow 704;

if no entry exists for node in Flow-Node-List of Flow-List

create new entry for node (Each entry in Flow-Node-List has Report-Duration=(current time−

Sampling-Start-Time), Received-Packet-Count, and Next-Hop-Structure);

else if entry for node exists in Flow-Node-List, then ignore report since it is duplicate (each node sends one report per flow during each Reporting-Time-Slot);

go to separate out reports for individual flows within message step;

when a Flow-Timer expires, for each node entry X in Flow-Node-List belonging to flow;

if Received-Packet-Count is not equal to the sum of Forwarded-Packet-Count for all Next-Hop-IP in Next-Hop-Structure, increment Suspect-Counter for node X by difference/Received-Packet-Count;

for each node entry X in Flow-Node-List belonging to flow

for each Next-Hop-IP in Next-Hop-Structure, decrement Received-Packet-Count in Next-Hop-IP'"'"'s Flow-Node-List entry, by Forwarded-Packet-Count in Next-Hop-Structure of X;

for each node entry X in Flow-Node-List belonging to flow

if abs(Received-Packet-Count)/(sum of Forwarded-Packet-Count)>

Permissible-Packet-Loss increment Suspect-Counter in Network-Node-List entry for node X, by abs(Received-Packet-Count)/(sum of Forwarded-Packet-Count) and increment Suspect-Counter in Network-Node-List entry for all nodes that list X as Next-Hop-IP in their Flow-Node-List entry, by abs(Received-Packet-Count)/(sum of Forwarded-Packet-Count) 806.

else

decrement Suspect-Counter in Network-Node-List entry for node X, by Credit-Value and decrement Suspect-Counter in Network-Node-List entry for all nodes that list X as Next-Hop-IP in their Flow-Node-List entry, by Credit-Value;

delete flow entry from unique flow list;

a plurality of network nodes reporting statistics regarding IP flow packets originated, received, or forwarded to neighbor network nodes; and

at least one coordinator node associated with one or more network nodes for receiving the reports and determining network nodes suspected of dropping packets.

16. A program storage device, readable by machine, tangibly embodying a program of instructions executable by the machine to cause the machine to perform a method for analyzing statistics for determining network nodes suspected of dropping packets in an ad hoc network as set forth in claim 15, further comprising penalizing and rewarding network nodes in the ad hoc network.