Method and system for detecting an anomalous networked device

• US 8,117,486 B2
• Filed: 04/10/2007
• Issued: 02/14/2012
• Est. Priority Date: 04/10/2007
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Handley, John C.
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): Truong, Loan
• Application Number:
  US11/733,295
• Publication Number:
  US 20080256230A1
• Time in Patent Office: 1,771 Days
• Field of Search: 714/4, 714/4.1, 714/27, 714/37, 714/40, 714/4.21, 714/4.3
• US Class Current: 714/4.1
• CPC Class Codes: H04L 63/145 the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms

Abstract

Methods and systems for detecting one or more anomalous devices are disclosed. For each of a plurality of devices, semi-structured data may be received from the device. For each pair of devices, of the plurality of devices, a similarity measurement may be determined between semi-structured data from a first device of the pair of devices and semi-structured data from a second device of the pair of devices. One or more anomalous devices may then be identified and one or more remedial actions may be performed for the one or more identified anomalous devices.

Claims

1. A method for detecting one or more anomalous devices, the method comprising:

for each of a plurality of devices, receiving, from the device, semi-structured system registry data corresponding to one or more applications on the device;

for each pair of devices of the plurality of devices, determining a similarity measurement between first semi-structured system registry data from a first device of the pair of devices and second semi-structured system registry data from a second device of the pair of devices by;

compressing the first semi-structured system registry data and the second semi-structured system registry data,

determining a first size associated with the compressed first semi-structured system registry data,

determining a second size associated with the compressed second semi-structured system registry data,

concatenating the first semi-structured system registry data and the second semi-structured system registry data to create concatenated semi-structured system registry data, and

determining the similarity measurement by determining a ratio of a size of the concatenated semi-structured system registry data and a sum of the first size and the second size;

clustering the devices based on the determined similarity measurements to form one or more device clusters;

identifying one or more outliers based on the clustering, wherein an outlier represents an anomalous device that is part of a cluster that has a small number of devices as compared to other clusters; and

performing one or more remedial actions for the one or more identified anomalous devices.

2. The method of claim 1 wherein using the determined similarity measurements to identify one or more anomalous devices comprises:

for each device;

determining one or more distances for the device, wherein each of the one or more distances is determined between the device and one of the plurality of devices other than the device, and

selecting a minimum distance for the device from the one or more distances;

determining a median distance from the minimum distances for each of the plurality of devices;

for each device, determining an absolute value of a difference between the minimum distance for the device and the median distance;

determining a median absolute deviation equal to a median of the absolute values; and

for each device, identifying the device to be anomalous if the minimum distance for the device exceeds a sum of the median distance and a product of a positive constant and the median absolute deviation.

3. The method of claim 1, wherein the clustering algorithm comprises one or more of hierarchical agglomerative clustering and K-means clustering.

4. The method of claim 3 wherein determining a distance comprises determining one or more of a single link metric, a complete link metric and an average link metric.

5. The method of claim 1 wherein receiving semi-structured system registry data from the device comprises receiving XML data from the device.

6. The method of claim 1 wherein determining a similarity measurement comprises determining a value for a compression dissimilarity measure.

7. The method of claim 1 wherein each device comprises one or more of a computer, a print engine and a document processing device.

8. The method of claim 1 wherein performing one or more remedial actions comprises providing information identifying the one or more anomalous devices.

9. The method of claim 1, further comprising:

displaying a graph representing differences between the similarity measurements for each device.

10. A system for detecting one or more anomalous devices, the system comprising:

a processor;

a communication port in communication with the processor; and

a processor-readable storage medium in communication with the processor, wherein the processor-readable storage medium comprises one or more programming instructions for;

for each of a plurality of devices, receiving, from the device, semi-structured system registry data corresponding to one or more applications on the device,

for each pair of devices of the plurality of devices, determining a similarity measurement between first semi-structured system registry data from a first device of the pair of devices and second semi-structured system registry data from a second device of the pair of devices by;

compressing the first semi-structured system registry data and the second semi-structured system registry data,

determining a first size associated with the compressed first semi-structured system registry data,

determining a second size associated with the compressed second semi-structured system registry data,

concatenating the first semi-structured system registry data and the second semi-structured system registry data to create concatenated semi-structured system registry data, and

determining the similarity measurement by determining a ratio of a size of the concatenated semi-structured system registry data and a sum of the first size and the second size;

clustering the devices based on the determined similarity measurements to form one or more device clusters;

identifying one or more outliers based on the clustering, wherein an outlier represents an anomalous device that is part of a cluster that has a small number of devices as compared to other clusters; and

performing one or more remedial actions for the one or more identified anomalous devices.

11. The system of claim 10 wherein identifying one or more outliers comprises one or more programming instructions for performing the following:

for each device;

determining one or more distances for the device, wherein each of the one or more distances is determined between the device and one of the plurality of devices other than the device, and

selecting a minimum distance for the device from the one or more distances;

determining a median distance from the minimum distances for each of the plurality of devices;

for each device, determining an absolute value of a difference between the minimum distance for the device and the median distance;

determining a median absolute deviation equal to a median of the absolute values; and

for each device, identifying the device to be anomalous if the minimum distance for the device exceeds a sum of the median distance and a product of a positive constant and the median absolute deviation.

12. The system of claim 10 wherein the one or more programming instructions for clustering the devices comprise one or more programming instructions for performing one or more of hierarchical agglomerative clustering and K-means clustering.

13. The system of claim 12 wherein determining a distance comprises one or more programming instructions for determining one or more of a single link metric, a complete link metric and an average link metric.

14. The system of claim 10 wherein receiving semi-structured system registry data from the device comprises one or more programming instructions for receiving XML data from the device.

15. The system of claim 10 wherein determining a similarity measurement comprises one or more programming instructions for determining a value for a compression dissimilarity measure.

16. The system of claim 10 wherein each device comprises one or more of a computer, a print engine and a document processing device.

17. The system of claim 10, wherein performing one or more remedial actions comprises one or more programming instructions for performing one or more of the following:

providing information identifying the one or more anomalous devices to a user;

removing the anomalous device from a network; and

shutting down the anomalous device.

18. The system of claim 10, wherein the processor-readable storage medium further comprises one or more programming instructions for performing the following:

displaying a graph representing differences between the similarity measurements for each device.