Creating generic rules in a high dimensional sparse feature space using negative feedback

1. A method comprising:

receiving, by one or more processors, a set of fingerprints, each fingerprint including a set of features of a file;

clustering, by the one or more processors, the set of fingerprints into one or more clusters; and

for each cluster of the one or more clusters:

creating a proto-rule,

simplifying the proto-rule using negative feedback to create a candidate well-formed rule, comprising:

randomly selecting a subset of conditions in the proto-rule;

in response to determining that none of the conditions in the subset match any of the fingerprints in a database of clean fingerprints improving the score of each of the conditions in the subset;

creating a second proto-rule from a cluster of clean fingerprints;

comparing each condition in the proto-rule with each condition in the second proto-rule; and

in response to determining that a condition in the proto-rule is similar to a condition in the second proto-rule, reducing the score of the condition in the proto-rule,

initializing N to the smallest number of conditions allowed in a well-formed rule;

iteratively performing for a predetermined or configurable number of iterations operations a-d comprising:

a. randomly selecting a subset of N conditions from the N+X top scoring conditions, where X is a predetermined or configurable constant,

b. creating a potential candidate rule from the subset of N conditions,

c. determining a C score, M score, and U score for the potential candidate rule, the C score based, at least in part, on fractions of fingerprints matching the potential candidate rule in a database of clean fingerprints, the M score based, at least in part, on fractions of fingerprints matching the potential candidate rule in a database of malware fingerprints, and the U score based, at least in part, on fractions of fingerprints matching the potential candidate rule in a database of unknown fingerprints, and

d. in response to determining that the C score is zero, adding the potential candidate rule to a set of potential candidate rules; and

selecting, as the candidate rule, a rule from the set of candidate rules having the highest combined M score and U score,

determining if the candidate well-formed rule is a valid well-formed rule, and

in response to determining that the candidate well-formed rule is a valid well-formed rule, adding the valid well-formed rule to a set of malware detection rules.

2. The method of claim 1 , wherein creating the proto-rule comprises creating the proto-rule to have at least one condition for each feature in the set of features for a fingerprint.

3. The method of claim 1 , wherein simplifying the proto-rule comprises:

determining a score for each condition in the proto-rule; and

removing from the proto-rule one or more conditions whose score is below a predetermined or configurable threshold.

4. The method of claim 1 , wherein simplifying the proto-rule comprises:

determining a score for each condition in the proto-rule, the score based, at least in part, on respective fractions of fingerprints matching the condition in a database of clean fingerprints, a database of malware fingerprints, and a database of unknown fingerprints; and

retaining in the proto-rule one or more conditions whose score is in a set of top scores and removing from the proto-rule conditions whose score is not in the set of top scores.

5. The method of claim 1 , further comprising:

in response to determining that the condition in the proto-rule is different from each condition in the second proto-rule, increasing the score of the condition in the proto-rule.

6. The method of claim 1 , wherein determining that the condition in the proto-rule is similar to the condition in the second proto-rule comprises determining that the condition in the second proto-rule is a subset of the condition in the proto-rule.

7. The method of claim 1 , wherein determining that the condition in the proto-rule is similar to the condition in the second proto-rule comprises determining that the condition in the second proto-rule overlaps the condition in the proto-rule.

8. The method of claim 1 , wherein determining that the condition in the proto-rule is similar to the condition in the second proto-rule comprises determining that the condition in the second proto-rule is the same as the condition in the proto-rule.

9. The method of claim 1 , further comprising:

in response to determining that the set of candidate rules is empty:

incrementing N;

iteratively performing operations a-d for the predetermined or configurable number of iterations.

10. A system comprising:

one or more processors;

a machine-readable medium having stored thereon instructions that, when executed, cause the one or more processors to:

receive a set of fingerprints, each fingerprint including a set of features of a file;

cluster the set of fingerprints into one or more clusters; and

for each cluster of the one or more clusters:

create a proto-rule,

simplify the proto-rule using negative feedback to create a candidate well-formed rule, comprising:

randomly select a subset of conditions in the proto-rule;

in response to a determination that none of the conditions in the subset match any of the fingerprints in a database of clean fingerprints improve the score of each of the conditions in the subset;

create a second proto-rule from a cluster of clean fingerprints;

compare each condition in the proto-rule with each condition in the second proto-rule; and

in response to a determination that a condition in the proto-rule is similar to a condition in the second proto-rule, reducing the score of the condition in the proto-rule,

initialize N to the smallest number of conditions allowed in a well-formed rule;

iteratively perform for a predetermined or configurable number of iterations operations a-d comprising:

a. randomly select a subset of N conditions from the N+X top scoring conditions, where X is a predetermined or configurable constant,

b. create a candidate rule from the subset of N conditions,

c. determine a C score, M score, and U score for the candidate rule, the C score based, at least in part, on fractions of fingerprints matching the candidate rule in a database of clean fingerprints, the M score based, at least in part, on fractions of fingerprints matching the candidate rule in a database of malware fingerprints, and the U score based, at least in part, on fractions of fingerprints matching the candidate rule in a database of unknown fingerprints, and

d. in response to a determination that the C score is zero, add the potential candidate rule to a set of potential candidate rules; and

selecting, as the candidate well-formed rule, a rule from the set of candidate rules having the highest combined M score and U score,

determine if the candidate well-formed rule is a valid well-formed rule, and

in response to a determination that the candidate well-formed rule is a valid well-formed rule, add the valid well-formed rule to a set of malware detection rules.

11. The system of claim 10 , wherein the proto-rule comprises at least one condition for each feature in the set of features for a fingerprint.

12. The system of claim 10 , wherein the instructions to simplify the proto-rule comprise instructions to cause the one or more processors to:

determine a score for each condition in the proto-rule; and

remove from the proto-rule one or more conditions whose score is below a predetermined or configurable threshold.

13. The system of claim 10 , wherein the instructions to simplify the proto-rule comprise instructions to cause the one or more processors to:

determine a score for each condition in the proto-rule, the score based, at least in part, on respective fractions of fingerprints matching the condition in a database of clean fingerprints, a database of malware fingerprints, and a database of unknown fingerprints; and

retain in the proto-rule one or more conditions whose score is in a set of top scores and remove from the proto-rule conditions whose score is not in the set of top scores.

14. The system of claim 10 , wherein the instructions further comprise instructions to cause the one or more processors to:

in response to a determination that the condition in the proto-rule is different from each condition in the second proto-rule, increase the score of the condition in the proto-rule.

15. The system of claim 10 , wherein the determination that the condition in the proto-rule is similar to the condition in the second proto-rule comprises instructions to determine that the condition in the second proto-rule is a subset of the condition in the proto-rule.

16. The system of claim 10 , wherein the determination that the condition in the proto-rule is similar to the condition in the second proto-rule comprises instructions to determine that the condition in the second proto-rule overlaps the condition in the proto-rule.

17. The system of claim 10 , wherein the determination that the condition in the proto-rule is similar to the condition in the second proto-rule comprises instructions to determine that the condition in the second proto-rule is the same as the condition in the proto-rule.

18. The system of claim 10 , wherein the instructions further comprise:

in response to determination that the set of candidate rules is empty:

increment N;

iteratively perform operations a-d for the predetermined or configurable number of iterations.

19. A non-transitory computer-readable medium having stored thereon computer-executable instructions to cause one or more processors to: receive a set of fingerprints, each fingerprint including a set of features of a file; cluster the set of fingerprints into one or more clusters; and for each cluster of the one or more clusters: create a proto-rule, simplify the proto-rule using negative feedback to create a candidate well-formed rule, comprising: randomly selecting a subset of conditions in the proto-rule; in response to determining that none of the conditions in the subset match any of the fingerprints in a database of clean fingerprints improving the score of each of the conditions in the subset; creating a second proto-rule from a cluster of clean fingerprints; comparing each condition in the proto-rule with each condition in the second proto-rule; and in response to determining that a condition in the proto-rule is similar to a condition in the second proto-rule, reducing the score of the condition in the proto-rule, initializing N to the smallest number of conditions allowed in a well-formed rule; iteratively performing for a predetermined or configurable number of iterations operations a-d comprising: a. randomly selecting a subset of N conditions from the N+X top scoring conditions, where X is a predetermined or configurable constant, b. creating a potential candidate rule from the subset of N conditions, c. determining a C score, M score, and U score for the potential candidate rule, the C score based, at least in part, on fractions of fingerprints matching the potential candidate rule in a database of clean fingerprints, the M score based, at least in part, on fractions of fingerprints matching the potential candidate rule in a database of malware fingerprints, and the U score based, at least in part, on fractions of fingerprints matching the potential candidate rule in a database of unknown fingerprints, and d. in response to determining that the C score is zero, adding the potential candidate rule to a set of potential candidate rules; and selecting, as the candidate rule, a rule from the set of candidate rules having the highest combined M score and U score, determine if the candidate well-formed rule is a valid well-formed rule, and in response to a determination that the candidate well-formed rule is a valid well-formed rule, add the valid well-formed rule to a set of malware detection rules.