Method and apparatus for detecting and correcting malicious data in an ad-hoc network

• US 7,362,711 B2
• Filed: 12/16/2004
• Issued: 04/22/2008
• Est. Priority Date: 12/16/2004
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Staddon, Jessica N., Greene, Daniel H., Lunt, Teresa F., Golle, Philippe
• Primary Examiner(s): Patel; Ajit
• Application Number:
  US11/014,016
• Publication Number:
  US 20060133289A1
• Time in Patent Office: 1,223 Days
• Field of Search: 370/241, 370/252, 370/242, 370/245, 370/310, 370/338, 370/400, 370/445, 370/229, 370/328, 714/100, 714/1, 726/22, 726/23
• US Class Current: 370/241
• CPC Class Codes: H04L 63/0492 by using a location-limited connection, e.g. near-field communication or limited proximity of entities
• CPC Class Codes: H04L 63/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 63/08 for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04W 12/122 Counter-measures against attacks; Protection against rogue devices
• CPC Class Codes: H04W 12/126 Anti-theft arrangements, e.g. protection against subscriber identity module [SIM] cloning
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

One embodiment of the present invention provides a system that detects malicious data in an ad-hoc network. During operation, the system receives data at a node in the ad-hoc network, wherein the data was sensed and redundantly communicated to the node by other nodes in the ad-hoc network. Note that in this ad-hoc network, a given node senses data associated with itself and with proximate nodes in the ad-hoc network. In this way, proximate nodes in the ad-hoc network can redundantly sense data about each other. Next, the system determines at the node if the received data, along with data sensed locally by the node, is consistent. If not, the system uses a model which accounts for malicious nodes to determine an explanation for the inconsistency.

Claims

1. A method for detecting malicious data in an ad-hoc network, comprising:

receiving data at a node in the ad-hoc network, the data having purportedly been sensed by other nodes in the ad-hoc network,

wherein a given node senses data associated with itself and with proximate nodes in the ad-hoc network, whereby proximate nodes in the ad-hoc network can redundantly sense data about each other,

wherein the received data was redundantly communicated to the node by the other nodes in the ad-hoc network;

determining, at the node, if the received data, along with data sensed locally by the node, is consistent; and

if not, using a model which accounts for malicious nodes to determine an explanation for the inconsistency.

2. The method of claim 1,

wherein nodes in the ad-hoc network are vehicles;

and

wherein the data includes location information for the vehicles.

3. The method of claim 1, wherein determining an explanation for the inconsistency involves:

generating a set of explanations for the inconsistency;

ranking the set of explanations according to likelihood; and

selecting an explanation from the set of explanations based on the ranking.

4. The method of claim 3, wherein generating the set of explanations involves facilitating “

local distinguishability”

by comparing data which was sensed locally by the node with data received from the proximate nodes to determine if the proximate nodes are telling the truth, and if so labeling them as truthful nodes.

5. The method of claim 4, wherein generating the set of explanations also involves facilitating “

extended distinguishability”

by comparing data provided by truthful nodes with data received from nodes which are proximate to the truthful nodes to determine if the proximate nodes are telling the truth, and if so, labeling them as truthful nodes.

6. The method of claim 3, wherein ranking the set of explanations according to likelihood involves considering simpler explanations to be more likely than more complicated explanations.

7. The method of claim 1, wherein the model which accounts for malicious nodes also accounts for the possibility that malicious nodes can generate fictitious data from fictitious “

spoof nodes”

that do not actually exist.

8. The method of claim 1, further comprising using the explanation for the inconsistency to perform a remedial action.

9. The method of claim 8, wherein if there exist multiple nearly equally highly ranked explanations, these explanations can be combined to obtain a partial explanation for the inconsistency to facilitate taking a remedial action on part of the data.

10. The method of claim 1, wherein the received data was redundantly communicated between nodes in the ad-hoc network using:

a flooding protocol;

a gossip protocol;

or

an epidemic protocol.

11. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for detecting malicious data in an ad-hoc network, the method comprising:

receiving data at a node in the ad-hoc network, the data having purportedly been sensed by other nodes in the ad-hoc network,

wherein a given node senses data associated with itself and with proximate nodes in the ad-hoc network, whereby proximate nodes in the ad-hoc network can redundantly sense data about each other,

wherein the received data was redundantly communicated to the node by the other nodes in the ad-hoc network;

determining, at the node, if the received data, along with data sensed locally by the node, is consistent; and

if not, using a model which accounts for malicious nodes to determine an explanation for the inconsistency.

12. The computer-readable storage medium of claim 11,

wherein nodes in the ad-hoc network are vehicles;

and

wherein the data includes location information for the vehicles.

13. The computer-readable storage medium of claim 11, wherein determining an explanation for the inconsistency involves:

generating a set of explanations for the inconsistency;

ranking the set of explanations according to likelihood; and

selecting an explanation from the set of explanations based on the ranking.

14. The computer-readable storage medium of claim 11, wherein generating the set of explanations involves facilitating “

local distinguishability”

by comparing data which was sensed locally by the node with data received from the proximate nodes to determine if the proximate nodes are telling the truth, and if so labeling them as truthful nodes.

15. The computer-readable storage medium of claim 14, wherein generating the set of explanations also involves facilitating “

extended distinguishability”

by comparing data provided by truthful nodes with data received from nodes which are proximate to the truthful nodes to determine if the proximate nodes are telling the truth, and if so labeling them as truthful nodes.

16. The computer-readable storage medium of claim 15, wherein ranking the set of explanations according to likelihood involves considering simpler explanations to be more likely than more complicated explanations.

17. The computer-readable storage medium of claim 11, wherein the model which accounts for malicious nodes also accounts for the possibility that malicious nodes can generate fictitious data from fictitious “

spoof nodes”

that do not actually exist.

18. The computer-readable storage medium of claim 11, wherein the method further comprises using the explanation for the inconsistency to perform a remedial action.

19. The computer-readable storage medium of claim 18, wherein if there exist multiple nearly equally highly ranked explanations, these explanations can be combined to obtain a partial explanation for the inconsistency to facilitate taking a remedial action on part of the data.

20. The computer-readable storage medium of claim 11, wherein the received data was redundantly communicated between nodes in the ad-hoc network using:

a flooding protocol;

a gossip protocol;

or

an epidemic protocol.

21. An apparatus that detects malicious data in an ad-hoc network, comprising:

a receiving mechanism at a node in the ad-hoc network, which is configured to receive data purportedly been sensed by other nodes in the ad-hoc network,

wherein a given node senses data associated with itself and with proximate nodes in the ad-hoc network, whereby proximate nodes in the ad-hoc network can redundantly sense data about each other,

wherein the received data was redundantly communicated to the node by the other nodes in the ad-hoc network;

a determination mechanism at the node configured to determine if the received data, along with data sensed locally by the node, is consistent; and

wherein if not, the determination mechanism is configured to use a model which accounts for malicious nodes to determine an explanation for the inconsistency.

22. The apparatus of claim 21,

wherein nodes in the ad-hoc network are vehicles;

and

wherein the data includes location information for the vehicles.