Matrix factorization for automated malware detection

• US 9,398,034 B2
• Filed: 12/19/2013
• Issued: 07/19/2016
• Est. Priority Date: 12/19/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Ronen, Royi, Kels, Shay, Ziklik, Elad, Hudis, Efim, Feuerstein, Corina, Brand, Tomer
• Primary Examiner(s): Mehedi, Morshed
• Application Number:
  US14/135,247
• Publication Number:
  US 20150180890A1
• Time in Patent Office: 943 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/56 Computer malware detection or handling, e.g. anti-virus arrangements
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection

Abstract

Disclosed herein is a system and method for automatically identifying potential malware files or benign files in files that are not known to be malware. Vector distances for select features of the files are compared to vectors both known malware files and benign files. Based on the distance measures a malware score is obtained for the unknown file. If the malware score exceeds a threshold a researcher may be notified of the potential malware, or the file may be automatically classified as malware if the score is significantly high.

Claims

1. A malware detection system comprising:

at least one processor;

a feature identifier configured to generate a matrix of files and associated machines having a plurality of features associated with the files and machines, the feature identifier further configured to apply matrix factorization to the matrix of files and associated machines to generate a machine matrix and a file matrix, and is configured to perform dimensional reduction to identify a group of features from the plurality of features that are most informative features, wherein the group of features is a fixed number of features and comprises a subset of the plurality of features;

a malware database comprising files of known malware and a plurality of features associated with the known malware;

a comparison engine configured to identify for a file a number of other files that are similar to the file from the matrix of files and the malware database and to score the file based on a closeness of the other files to the file; and

malware classification component configured to identify potential malware based on the score of the file and is further configured to create an alert if the score for the file exceeds a first threshold score.

2. The malware detection system of claim 1 wherein feature identifier is further configured to determine the group of features by comparing a multiplication of the machine matrix and the file matrix limited to the group of features, the multiplication yielding a resultant matrix, and identifying the resultant matrix that most closely corresponds with the matrix of files and associated machines.

3. The malware detection system of claim 2 wherein the feature identifier identifies the group of features by applying all possible permutations of a number of features in the plurality of features that comprises the fixed number of features in the group of features.

4. The malware detection system of claim 2 wherein the comparison engine is further configured to generate a vector for the file based on the group of features and corresponding vectors for the number of other files based on the group of features.

5. The malware detection system of claim 4 wherein the comparison engine is further configured to score the file based on a distance measure of the vector for the file with the corresponding vector for each of the number of files.

6. The malware detection system of claim 4 wherein the comparison engine is further configured to:

identify at least one known malware in the number of other files; and

score the file based on a distance measure of the vector for the file with the corresponding vector for the at least one known malware.

7. The malware detection system of claim 4 wherein the malware database further comprises a whitelist of files known not to be malware and the plurality of features associated with the whitelist of files.

8. The malware detection system of claim 4 wherein the comparison engine is further configured to:

identify at least one known malware in the number of other files;

identify at least one file from the whitelist in the number of other files;

score the file based on a distance measure of the vector for the file with the correspond vector for the at least one known malware and the at least one whitelist file by adding the distance measure for the at least one known malware to the score and subtracting the distance measure for the at least one whitelist item.

9. The malware detection system of claim 1 wherein the malware classification component is further configured to automatically add the file to the malware database when the score for the file exceeds a second threshold score that is greater than the first threshold score.

10. The malware detection system of claim 1 wherein the malware classification component is further configured to generate a signal to a machine associated with the file instructing the machine to take an action relative to the file when the score for the file exceeds a second threshold score that is greater than the first threshold score.

11. A method for identifying unknown malware files from a plurality of files comprising:

receiving a plurality of files from a plurality of machines each file and each machine having a plurality of features each of the plurality of files associated with at least one of the plurality of machines upon which the file resides;

building a multidimensional matrix associating the plurality of files with the plurality of machines;

identifying from the multidimensional matrix a group of features that are most informative in describing a file in the matrix wherein the group of features is a fixed number of features and comprises a subset of the plurality of features for the plurality of files and the plurality of machines;

determining a malware score for at least one file in the plurality of files;

determining if the at least one file is potential malware by comparing the malware score for the at least one file against a threshold malware score; and

generating an alert when the at least one the is determined to be potential malware;

wherein the preceding steps are performed by at least one processor.

12. The method of claim 11 wherein determining the malware score further comprises:

identifying from a malware database and the plurality of files a group of files that are similar to the at least one file;

generating a vector for the at least one file and a plurality of corresponding vectors for each file in the group of files based on the group of features;

determining a distance measure between the vector for the at least one file and each of the plurality of corresponding vectors; and

adding the determined distance measures as the malware score for the at least one file.

13. The method of claim 12 further comprising:

ranking the group of files based on a similarity measure to the at least one file;

weighting each file in the group of files according to the ranking; and

applying the weighting to the determined distance measure for each file.

14. The method of claim 12 wherein the group of files includes at least one file known not to be malware and at least one file known to be malware, wherein adding further comprises:

adding to the malware score the determined distance measures for the at least one file known to be malware;

subtracting from the malware score the determined distance measure for the at least one file known not to be malware; and

not adding to the malware score files that are neither known malware or known not to be malware.

15. The method of claim 11 wherein determining the malware score further comprises:

identifying at least one malware file in a malware database;

for each of the at least one malware file;

identifying a group of files in the plurality of files that are similar to the malware file;

generating a vector for the malware file and a plurality of corresponding vectors for each file in the group of files based on the group of features;

determining a distance measure between the vector for the malware file and each of the plurality of corresponding vectors; and

for each file in the plurality of files;

adding the determined distance measure between the malware file and the corresponding file in the group of files as the malware score for that file.

16. The method of claim 14 wherein when the malware score for the at least one file exceeds the threshold score further comprising:

determining if the malware score exceeds a second threshold score that is greater than the threshold score;

when the malware score is less than the second threshold score, alerting a researcher that the at least one file is potential malware; and

when the malware score is not less than the second threshold score, classifying the at least one file as malware; and

automatically adding the at least one file to a malware database.

17. A computer readable storage device having computer readable instructions that when executed cause at least one computing device to:

receive a plurality of files from a plurality of machines each file and each machine having a plurality of features;

build a multidimensional matrix associating the plurality of files with the plurality of machines;

identify from the multidimensional matrix a group of features that are most informative in describing a machine in the matrix wherein the group of features is a fixed number of features and comprises a subset of the plurality of features;

determine a vector distance for files on the at least one machine with corresponding vectors for a plurality of known malware files in a malware database wherein the vector and corresponding vectors are based on the group of features;

determine a malware score for at least one machine in the plurality of machines by adding the determined distance; and

determine if the at least one machine is compromised by malware by comparing the malware score for the at least one malware against a threshold malware score.