Method and system for resilient packet traceback in wireless mesh and sensor networks

• US 8,695,089 B2
• Filed: 03/30/2007
• Issued: 04/08/2014
• 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
• Primary Examiner(s): Rahman, Mohammad L
• Application Number:
  US11/694,388
• Publication Number:
  US 20080244739A1
• Time in Patent Office: 2,566 Days
• Field of Search: 713/153, 726/23, 726/25, 726/22
• 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 forwarding node in a network, wherein each forwarding node includes a non-transitory computer readable storage medium for storing the ID;

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

marking each packet as each packet passes through each forwarding node in a forwarding path such that each added mark includes at least the ID and the signature of the node and protects all previously added marks;

upon receiving a packet at the sink, verifying correctness of the signatures as marked on 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 the forwarding node'"'"'s presence in the forwarding path and the signature proves that the forwarding node sent each packet associated with the ID.

3. The method as recited in claim 1, further comprising hashing each packet in its entirety from a previous forwarding 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 forwarding node;

computing the signature for the last hop forwarding node and verifying the signature of the last hop forwarding 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 forwarding 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 forwarding nodes in the forwarding path.

8. The method as recited in claim 1, wherein marking packets provides a forwarding 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 forwarding 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 non-transitory computer readable storage 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 forwarding node in a network;

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

marking each packet as each packet passes through each forwarding node in a forwarding path such that each added mark includes at least the ID and the signature of the forwarding node and protects all previously added marks;

upon receiving a packet at the sink, verifying correctness of the signatures as marked on 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 forwarding node in a network, wherein each forwarding node includes a non-transitory computer readable storage medium for storing the ID;

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

generating a message authentication code (MAC) using the secret key for each forwarding node in a forwarding path to mark each packet with at least two probabilities, wherein each packet is marked, said mark including at least the node'"'"'s MAC, such that each mark added protects all previously added marks;

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 forwarding 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 forwarding node'"'"'s presence in the forwarding path and the MAC proves that the forwarding node sent the packet associated with the ID.

18. The method as recited in claim 16, further comprising hashing the packet from a previous forwarding 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 forwarding node;

computing the MAC for the last hop forwarding node and verifying the MAC of the last hop forwarding 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 non-transitory computer readable storage 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 forwarding node in a network;

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

generating a message authentication code (MAC) using the secret key for each forwarding node in a forwarding path to mark each packet with at least two probabilities, wherein each packet is marked, said mark including at least the node'"'"'s MAC, such that each mark added protects all previously added marks;

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

determining the real ID from the anonymous ID for forwarding 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 forwarding node of the forwarding path using the real ID and the secret key to determine a last valid MAC in the forwarding path.