Providing prevalence information using query data

• US 9,607,086 B2
• Filed: 03/27/2014
• Issued: 03/28/2017
• Est. Priority Date: 03/27/2014
• Status: Active Grant

• Current Assignee: McAfee, LLC
• Original Assignee: McAfee, Inc. (McAfee, LLC)
• Inventors: Morrey, Richard, Roberts, Guy, Venugopalan, Ramnath, Wilson, Nick
• Primary Examiner(s): Nguyen, Cam-Linh
• Application Number:
  US14/227,201
• Publication Number:
  US 20150278354A1
• Time in Patent Office: 1,097 Days
• Field of Search: 707/723, 707/747
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

In one example, a data security system may determine prevalence of a file based query data for an object (e.g., a file or a hash or a file). An example algorithm may provide using a statistically justifiable estimate of the prevalence while storing few data records, and therefore may provide prevalence information in O(1) time complexity (i.e., constant time). Such an algorithm may be applied in near real-time to provide, e.g., an immediate response to a query for the prevalence of a file.

Claims

1. A machine readable non-transitory storage medium having instructions stored thereon for providing prevalence information based on a query, wherein the instructions when executed by at least one processors cause the at least one processors to perform the following operations:

retrieving a sequence of target values from a data source;

receiving query data from a communication device;

generating a sequence of query values based on an identifier associated with the communication device;

comparing each value in the sequence of query values and a corresponding value in the sequence of target values to identify a number of matching values, wherein the number of matching values counts the number of times the value is equal to the corresponding value;

upon determining that the number of matching values exceeds a maximum number of matches stored in the data source, updating the maximum number of matches in the data source;

calculating, using a statistical model, a prevalence value and a degree of confidence in the prevalence value based, at least in part, on the maximum number of matching values, the prevalence value being proportional to the number of matching values;

weighting the prevalence value based on the degree of confidence in the prevalence value, and

outputting to the communication device the prevalence value for the query data.

2. The machine readable non-transitory storage medium of claim 1, further comprising:

receiving additional query data from the communication device, wherein the additional query data and the query data are the same; and

in response to the receiving the additional query data, maintaining the maximum number of matches in the data source by not updating the maximum number of matches in the data source.

3. The machine readable non-transitory storage medium of claim 1, wherein the comparing comprises a pairwise comparing of consecutive values in the sequence of query values and corresponding consecutive values in the sequence of target values beginning with the first value in each of the sequence of query values and the sequence of target values.

4. The machine readable non-transitory storage medium of claim 1, wherein retrieving the sequence of target values from the data source comprises:

receiving first query data from a first communication device;

generating a first sequence of bits based upon an identifier associated with the first communication device; and

storing the first sequence of bits in the data source as the sequence of target values.

5. The machine readable non-transitory storage medium of claim 4, wherein the receiving the query data from the communication device comprises receiving second query data from a second communication device, and wherein generating the sequence of query values based on an identifier associated with the communication device comprises generating a second sequence of bits based upon an identifier associated with the second communication device.

6. The machine readable non-transitory storage medium of claim 5, wherein the generating a first sequence of bits comprises applying a hash function to the identifier associated with the first communication device to generate the first sequence of bits;

and wherein generating the second sequence of bits comprises applying the hash function to the identifier associated with the second communication device to generate the second sequence of bits.

7. The machine readable non-transitory storage medium of claim 6, wherein the hash function comprises at least one of:

a message-digest algorithm, a cryptographic hash function, message-digest algorithm 5 (MD5), secure hash algorithm 1 (SHA1), or secure hash algorithm (SHA256).

8. The machine readable non-transitory storage medium of claim 1, wherein the query data is a hash of a file.

9. The machine readable non-transitory storage medium of claim 1, wherein a length of the sequence of query values is determined based on a threshold value.

10. The machine readable non-transitory storage medium of claim 1, wherein the prevalence value comprises at least one value corresponding to an order of magnitude.

11. The machine readable non-transitory storage medium of claim 1, wherein the degree of confidence comprises a probability calculated for the at least one value.

12. An apparatus for providing prevalence information based on a query, the apparatus comprising:

at least one memory element;

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

a reputation information server coupled to the at least one processor, wherein the reputation information server is configured to;

retrieve a sequence of target values from a data source;

receive query data from a communication device;

generate a sequence of query values based on an identifier associated with the communication device;

compare each value in the sequence of query values and a corresponding value in the sequence of target values to identify a number of matching values, wherein the number of matching values counts the number of times the value is equal to the corresponding value;

upon determining that the number of matching values exceeds a maximum number of matches stored in the data source, update the maximum number of matches in the data source;

calculate, using a statistical model, a prevalence value and a degree of confidence in the prevalence value based, at least in part, on the maximum number of matching values, the prevalence value being proportional to the number of matching values;

weight the prevalence value based on the degree of confidence in the prevalence value, and

output to the communication device the prevalence value for the query data.

13. The apparatus of claim 12, wherein the reputation information server is further configured to:

receive additional query data from the communication device, wherein the additional query data and the query data are the same; and

in response to the receiving the additional query data, maintain the maximum number of matches in the data source by not updating the maximum number of matches in the data source.

14. The apparatus of claim 12, wherein retrieving the sequence of target values from the data source comprises:

receiving first query data from a first communication device;

generating a first sequence of bits based upon an identifier associated with the first communication device; and

storing the first sequence of bits in the data source as the sequence of target values.

15. The apparatus of claim 14, wherein the receiving the query data from the communication device comprises receiving second query data from a second communication device, and wherein generating the sequence of query values based on an identifier associated with the communication device comprises generating a second sequence of bits based upon an identifier associated with the second communication device.

16. A method for providing prevalence information based on a query, the method comprising:

retrieving a sequence of target values from a data source;

receiving query data from a communication device;

generating a sequence of query values based on an identifier associated with the communication device;

comparing each value in the sequence of query values and a corresponding value in the sequence of target values to identify a number of matching values, wherein the number of matching values counts the number of times the value is equal to the corresponding value; and

upon determining that the number of matching values exceeds a maximum number of matches stored in the data source, updating the maximum number of matches in the data source;

calculating, using a statistical model, a prevalence value and a degree of confidence in the prevalence value based, at least in part, on the maximum number of matching values, the prevalence value being proportional to the number of matching values;

weighting the prevalence value based on the degree of confidence in the prevalence value, and

outputting to the communication device the prevalence value for the query data.