METHOD AND SYSTEM FOR RESILIENT PACKET TRACEBACK IN WIRELESS MESH AND SENSOR NETWORKS

• US 20080244739A1
• Filed: 03/30/2007
• Published: 10/02/2008
• Est. Priority Date: 03/30/2007
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Zhen, Yang, Hao, Ye, Fan
• Granted Patent: US 8,695,089 B2
• Time in Patent Office: Days
• US Class Current: 726/22
• CPC Class Codes: H04L 2463/146 Tracing the source of attacks
• CPC Class Codes: H04L 63/1458 Denial of Service
• CPC Class Codes: H04L 63/1466 Active attacks involving interception, injection, modification, spoofing of data unit addresses, e.g. hijacking, packet injection or TCP sequence number attacks
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements

Abstract

A system and method for packet traceback in a network includes maintaining an identity number (ID) for each node in a network and generating a signature (e.g., a message authentication code (MAC)) using a secret key shared between each node on a forwarding path and a sink. Each forwarding node leaves a mark by appending its ID and a signature in the packet, either in a deterministic manner or with a probability. Upon receiving a packet at the sink, correctness of the signatures included in each packet is verified in the reverse order by which these signatures were appended. A last valid MAC is determined in the forwarding path to determine the locations of compromised nodes that collude in false data injection attacks.

Claims

1. A method for packet traceback in a network, comprising:

maintaining an identity number (ID) for each node in a network;

generating a signature at each forwarding node using a secret key shared between this node and a sink;

upon receiving a packet at the sink, verifying correctness of the signatures of each packet by the sink in reverse order in which the signatures were added; and

determining signature validity in the forwarding path to determine a location of a false data injection source, and/or a colluding compromised node.

2. The method as recited in claim 1, wherein the ID indicates a node'"'"'s presence in the forwarding path and the signature proves that the node sent the packet associated with the ID.

3. The method as recited in claim 1, further comprising hashing the packet in its entirety from a previous node in accordance with the key to generate the signature.

4. The method as recited in claim 1, wherein determining signature validity includes retrieving an ID for a last hop node;

computing the signature for the last hop node and verifying the signature of the last hop node; and

repeating until the last valid signature is determined.

5. The method as recited in claim 1, wherein maintaining an identity number (ID) includes mapping an anonymous ID from the ID using a key known by a current node and the sink.

6. The method as recited in claim 5, wherein the mapping of the anonymous ID includes using a current packet message to change the anonymous ID for each message forwarded.

7. The method as recited in claim 6, wherein verifying includes determining the ID from the anonymous ID for nodes in the forwarding path.

8. The method as recited in claim 1, further comprising marking packets to provide a node order through the forwarding path.

9. The method as recited in claim 8, wherein marking packets includes marking packets probabilistically, with a probability, at each forwarding node.

10. The method as recited in claim 8, wherein marking packets includes deterministically marking packets at each node and providing an incremented sequence number for each packet.

11. The method as recited in claim 1, wherein verifying correctness of the signatures of each packet includes employing a sliding window of to determine valid sequence numbers.

12. The method as recited in claim 1, further comprising removing moles from the forwarding path.

13. The method as recited in claim 1, further comprising locating a plurality of collusive moles in the forwarding path.

14. The method as recited in claim 1, further comprising locating moles within one hop of the mole.

15. A computer program product for packet traceback in a network comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:

maintaining an identity number (ID) for each node in a network;

generating a signature at each forwarding node using a secret key shared between this node and a sink;

upon receiving a packet at the sink, verifying correctness of the signatures of each packet by the sink in reverse order in which the signatures were added; and

determining signature validity in the forwarding path to determine a false data injection source.

16. A method for packet traceback in a wireless mesh or sensor network, comprising:

maintaining a real identity number (ID) for each node in a network;

computing an anonymous ID from the real ID based on a secret key known only to a current node and a sink;

generating a message authentication code (MAC) using the secret key for each node in a forwarding path to mark each packet with at least two probabilities;

tracing back the path to discover false data injection sources by;

determining the real ID from the anonymous ID for nodes in the network;

reconstructing a node route using marks present in each packet; and

verifying correctness of the MAC of each packet back through each node of the forwarding path using the real ID and the secret key to determine a last valid MAC in the forwarding path.

17. The method as recited in claim 16, wherein the ID indicates a node'"'"'s presence in the forwarding path and the MAC proves that the node sent the packet associated with the ID.

18. The method as recited in claim 16, further comprising hashing the packet from a previous node in accordance with the secret key to generate the MAC.

19. The method as recited in claim 16, wherein verifying correctness includes retrieving the real ID for a last hop node;

computing the MAC for the last hop node and verifying the MAC of the last hop node; and

repeating until the last valid MAC is determined.

20. The method as recited in claim 16, further comprising locating a plurality of collusive moles in the forwarding path;

and removing the collusive moles.

21. The method as recited in claim 16, wherein locating moles is performed within one hop of the mole.

22. A computer program product for packet traceback in wireless mesh or sensor networks comprising a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:

maintaining a real identity number (ID) for each node in a network;

computing an anonymous ID from the real ID based on a secret key known only to a current node and a sink;

generating a message authentication code (MAC) using the secret key for each node in a forwarding path to mark each packet with at least two probabilities;

tracing back the path to discover false data injection sources by;

determining the real ID from the anonymous ID for nodes in the network;

reconstructing a node route using marks present in each packet; and

verifying correctness of the MAC of each packet back through each node of the forwarding path using the real ID and the secret key to determine a last valid MAC in the forwarding path.