System and method for clustering host inventories

• US 8,843,496 B2
• Filed: 09/03/2013
• Issued: 09/23/2014
• Est. Priority Date: 09/12/2010
• Status: Expired due to Fees

• Current Assignee: McAfee, LLC
• Original Assignee: McAfee, Inc. (McAfee, LLC)
• Inventors: Bhargava, Rishi, Reese, David P. Jr.
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US14/016,497
• Publication Number:
  US 20140006405A1
• Time in Patent Office: 385 Days
• Field of Search: 707/737, 707/738, 707/748, 707/776, 707/791
• US Class Current: 707/737
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements

Abstract

A method in one example implementation includes obtaining a plurality of host file inventories corresponding respectively to a plurality of hosts, calculating input data using the plurality of host file inventories, and then providing the input data to a clustering procedure to group the plurality of hosts into one or more clusters of hosts. The method further includes each cluster of hosts being grouped using predetermined similarity criteria. In more specific embodiments, each of the host file inventories includes a set of one or more file identifiers with each file identifier representing a different executable software file on a corresponding one of the plurality of hosts. In other more specific embodiments, calculating the input data includes transforming the host file inventories into a matrix of keyword vectors in Euclidean space. In further embodiments, calculating the input data includes transforming the host file inventories into a similarity matrix.

Claims

1. One or more non-transitory media including code for execution that, when executed by a processor, is operable to:

obtain a plurality of host file inventories corresponding respectively to a plurality of hosts in a network environment, wherein each of the plurality of host file inventories includes one or more file identifiers, each of the file identifiers of a particular host file inventory representing a different executable file on one of the plurality of hosts corresponding to the particular host file inventory;

calculate input data by transforming the plurality of host file inventories into a similarity matrix for the plurality of hosts, wherein for at least each unique pair of host file inventories of the plurality of host file inventories, the transforming includes;

determining a normalized compression distance (NCD) between the unique pair of host file inventories;

determining a numerical value representing a similarity distance between the unique pair of host file inventories, the numerical value being determined based on the NCD; and

updating the similarity matrix to include the numerical value representing the similarity distance between the unique pair of host file inventories; and

provide the input data to a clustering procedure to group the plurality of hosts into one or more clusters of hosts, wherein the one or more clusters of hosts are grouped using a predetermined similarity criteria.

2. The one or more non-transitory media of claim 1, wherein the determining the NCD includes:

storing, in a first file, one or more file identifiers of a first host file inventory of the unique pair of host file inventories;

storing, in a second file, one or more file identifiers of a second host file inventory of the unique pair of host file inventories;

concatenating the first and second files in a concatenated file;

compressing the first file into a compressed first file;

compressing the second file into a compressed second file; and

compressing the concatenated file into a compressed concatenated file, wherein the NCD is computed based on the compressed first file, the compressed second file, and the compressed concatenated file.

3. The one or more non-transitory media of claim 1, wherein a variable n represents a total number of the plurality of hosts, the similarity matrix being an n by n (“

n×

n”

) matrix.

4. The one or more non-transitory media of claim 1, wherein each entry in the similarity matrix is one of a plurality of numerical values included in the similarity matrix, wherein each entry represents a similarity distance between a pair of hosts of the plurality of hosts.

5. The one or more non-transitory media of claim 4, wherein only one-half of the plurality of numerical values that are not entries in a diagonal line of symmetry in the similarity matrix are determined, and wherein the determined numerical values are reflected over the diagonal line of symmetry in the similarity matrix.

6. The one or more non-transitory media of claim 1, wherein the code for execution, when executed by a processor, is further operable to:

generate information indicating the one or more clusters of hosts, wherein each of the one or more clusters includes at least one host.

7. The one or more non-transitory media of claim 6, wherein the information is a proximity plot.

8. The one or more non-transitory media of claim 1, wherein the clustering procedure is an agglomerative hierarchical clustering technique with the predetermined similarity criteria including a cut point determination to define a stopping point of the clustering procedure.

9. The one or more non-transitory media of claim 1, wherein the clustering procedure is a partitional clustering technique.

10. An apparatus, comprising:

at least one processor coupled to at least one memory element;

a host inventory preparation module that when executed by the at least one processor, is configured to;

obtain a plurality of host file inventories corresponding respectively to a plurality of hosts in a network environment, wherein each of the plurality of host file inventories includes one or more file identifiers, each of the file identifiers of a particular host file inventory representing a different executable file on one of the plurality of hosts corresponding to the particular host file inventory; and

calculate input data by transforming the plurality of host file inventories into a similarity matrix for the plurality of hosts, wherein for at least each unique pair of host file inventories of the plurality of host file inventories, the transforming includes;

determining a normalized compression distance (NCD) between the pair of host file inventories;

determining a numerical value representing a similarity distance between the pair of host file inventories, the numerical value being determined based on the NCD; and

updating the similarity matrix to include the numerical value representing the similarity distance between the pair of host file inventories; and

a clustering module that when executed by the at least one processor, is configured to;

receive the input data; and

group the plurality of hosts into one or more clusters of hosts, wherein the one or more clusters of hosts are grouped using a predetermined similarity criteria.

11. The apparatus of claim 10, wherein the clustering module, when executed by the at least one processor, is further configured to:

generate information indicating the one or more clusters of hosts, wherein each of the one or more clusters includes at least one host.

12. The apparatus of claim 10, wherein the information is a proximity plot.

13. The apparatus of claim 10, wherein the clustering module includes an agglomerative hierarchical clustering technique with the predetermined similarity criteria including a cut point determination to define a stopping point of the clustering module.

14. The apparatus of claim 10, wherein the clustering module includes a partitional clustering technique.

15. The apparatus of claim 10, wherein the determining the NCD includes:

storing, in a first file, one or more file identifiers of a first host file inventory of the unique pair of host file inventories;

storing, in a second file, one or more file identifiers of a second host file inventory of the unique pair of host file inventories;

concatenating the first and second files in a concatenated file;

compressing the first file into a compressed first file;

compressing the second file into a compressed second file; and

compressing the concatenated file into a compressed concatenated file, wherein the NCD is computed based on the compressed first file, the compressed second file, and the compressed concatenated file.

16. The apparatus of claim 10, wherein a variable n represents a total number of the plurality of hosts, the similarity matrix being an n by n (“

n×

n”

) matrix.

17. The apparatus of claim 10, wherein each entry in the similarity matrix is one of a plurality of numerical values included in the similarity matrix, wherein each entry represents a similarity distance between a pair of hosts of the plurality of hosts.

18. The apparatus of claim 17, wherein only one-half of the plurality of numerical values that are not entries in a diagonal line of symmetry in the similarity matrix are determined, and wherein the determined numerical values are reflected over the diagonal line of symmetry in the similarity matrix.

19. A computer implemented method executed by one or more processors, comprising:

obtaining a plurality of host file inventories corresponding respectively to a plurality of hosts in a network environment;

calculating input data by transforming the plurality of host file inventories into a similarity matrix for the plurality of hosts, wherein, for at least each unique pair of host file inventories of the plurality of host file inventories, the transforming includes;

storing, in a first file, one or more file identifiers of a first host file inventory of the pair of host file inventories;

storing, in a second file, one or more file identifiers of a second host file inventory of the pair of host file inventories;

concatenating the first and second files in a concatenated file;

compressing the first file into a compressed first file;

compressing the second file into a compressed second file; and

compressing the concatenated file into a compressed concatenated file;

determining a normalized compression distance (NCD) between the first and second host file inventories based on the compressed first file, the compressed second file, and the compressed concatenated file;

determining a numerical value representing a similarity distance between the pair of host file inventories, the numerical value being determined based on the NCD; and

updating the similarity matrix to include the numerical value representing the similarity distance between the pair of host file inventories; and

providing the input data to a clustering procedure to group the plurality of hosts into one or more clusters of hosts, wherein the one or more clusters of hosts are grouped using a predetermined similarity criteria.

20. The computer implemented method of claim 19, wherein each of the plurality of host file inventories includes one or more file identifiers, each of the file identifiers of a particular host file inventory representing a different executable file on one of the plurality of hosts corresponding to the particular host file inventory.

21. The method of claim 19, wherein each entry in the similarity matrix is one of a plurality of numerical values included in the similarity matrix, wherein each entry represents a similarity distance between a pair of hosts of the plurality of hosts.

22. The method of claim 21, wherein only one-half of the plurality of numerical values that are not entries in a diagonal line of symmetry in the similarity matrix are determined, and wherein the determined numerical values are reflected over the diagonal line of symmetry in the similarity matrix.

23. The method of claim 19, wherein the clustering procedure is an agglomerative hierarchical clustering technique with the predetermined similarity criteria including a cut point determination to define a stopping point of the clustering procedure.

24. The method of claim 19, wherein the clustering procedure is a partitional clustering technique.