Identification of mislabeled samples via phantom nodes in label propagation

• US 10,198,576 B2
• Filed: 12/09/2016
• Issued: 02/05/2019
• Est. Priority Date: 12/10/2015
• Status: Active Grant

• Current Assignee: Avast Software SRO (Gen Digital Inc.), Ustav Informatiky Av Cr, V.V.I.
• Original Assignee: Avast Software SRO (Gen Digital Inc.), Ustav Informatiky Av Cr, V.V.I.
• Inventors: Vejmelka, Martin
• Primary Examiner(s): Pyzocha, Michael
• Application Number:
  US15/374,865
• Publication Number:
  US 20170169215A1
• Time in Patent Office: 788 Days
• CPC Class Codes: G06F 21/564 by virus signature recognition

Abstract

Systems and method identify potentially mislabeled file samples. A graph is created from a plurality of sample files. The graph includes nodes associated with the sample files and behavior nodes associated with behavior signatures. Phantom nodes are created in the graph for those sample files having a known label. During a label propagation operation, a node receives data indicating a label distribution of a neighbor node in the graph. In response to determining that the current label for the node is known, a neighborhood opinion is determined for the associated phantom node, based at least in part on the label distribution of the neighboring nodes. After the label propagation operation has completed, differences between the neighborhood opinion and the current label distribution for nodes are determined. If the difference exceeds a threshold, then the current label may be incorrect.

Claims

1. A computer-implemented method for protecting computing devices from mislabeled malware, the method comprising:

creating a graph from a plurality of sample executable files by executing the sample executable files in an isolated execution environment, the graph including sample file nodes associated with the sample executable files and behavior nodes associated with behavior signatures, wherein edges in the graph connect a behavior node with a set of one or more sample file nodes, wherein the one or more sample executable files associated with the one or more sample file nodes exhibit the behavior signature associated with the behavior node;

receiving data indicating a label distribution of a neighbor node of a sample file node in the graph;

in response to determining that a current label for the sample file node is unknown, setting the current label distribution for the sample file node to a consensus of label distributions of neighboring nodes;

in response to determining that the current label for the sample file node is known, performing operations including;

creating a phantom node associated with the sample file node,

determining a neighborhood opinion for the phantom node, based at least in part on the label distribution of the neighboring nodes,

determining a difference between the neighborhood opinion and the current label for the sample file node, and

determining whether the current label is incorrect based, at least in part, on the difference; and

in response to determining that the current label for the sample file node is incorrect, performing at least one remedial action on the sample executable file associated with the sample file node having the incorrect current label.

2. The computer-implemented method of claim 1 further comprising performing an iterative label propagation operation.

3. The computer-implemented method of claim 1, wherein the at least one remedial action comprises flagging at least one of the current node and the sample executable file associated with the current node for further analysis.

4. The computer-implemented method of claim 1 wherein the at least one remedial action comprises applying at least one malware detection tool to determine what the current label should be.

5. The computer-implemented method of claim 1, wherein the current label indicates that the sample executable file associated with current label contains malware and wherein said determining whether the current label is incorrect comprises determining that the sample executable file associated with the current label does not contain malware.

6. The computer-implemented method of claim 1, wherein the current label indicates that the sample executable file associated with current label is free of malware and wherein said determining whether the current label is incorrect comprises determining that the sample executable file associated with the current label does contain malware.

7. The method of claim 1, wherein the at least one remedial action comprises decreasing an influence of the sample file node during propagation of the current label by weighting data flowing from the sample file node to neighboring nodes according to the determined difference between the neighborhood opinion and the current label for the sample file node.

8. A system comprising:

at least one processor; and

a non-transitory computer readable storage medium having a program stored thereon, the program causing the at least one processor to execute the steps of;

(a) creating a graph from a plurality of sample executable files by executing the sample executable files in an isolated execution environment, the graph including sample file nodes associated with the sample executable files and behavior nodes associated with behavior signatures, wherein edges in the graph connect a behavior node with a set of one or more sample file nodes, wherein the one or more sample executable files associated with the one or more sample file nodes exhibit the behavior signature associated with the behavior node;

(b) receiving data indicating a label distribution of a neighbor node of a sample file node in the graph;

(c) in response to determining that a current label for the sample file node is unknown, setting the current label distribution for the sample file node to a consensus of label distributions of neighboring nodes,

(d) in response to determining that the current label for the sample file node is known, performing operations including;

(i) creating a phantom node associated with the sample file node,

(ii) determining a neighborhood opinion for the phantom node, based at least in part on the label distribution of the neighboring nodes,

(iii) determining a difference between the neighborhood opinion and the current label for the sample file node, and

(iv) determining whether the current label is incorrect based, at least in part, on the difference; and

(e) in response to determining that the current label for the sample file node is incorrect, performing at least one remedial action on the sample executable file associated with the sample file node having the incorrect current label.

9. The system of claim 8, wherein the program further performs causes the at least one processor to perform an iterative label propagation operation.

10. The system of claim 8, wherein the at least one remedial action comprises flagging at least one of the current node and the sample executable file associated with the current node for further analysis.

11. The system of claim 8, wherein the at least one remedial action comprises applying at least one malware detection tool to determine what the current label should be.

12. The system of claim 8, wherein the current label indicates that the sample executable file associated with current label contains malware and wherein said determining whether the current label is incorrect comprises determining that the sample executable file associated with the current label does not contain malware.

13. The system of claim 8, wherein the current label indicates that the sample executable file associated with current label is free of malware and wherein said determining whether the current label is incorrect comprises determining that the sample executable file associated with the current label does contain malware.

14. A non-transitory computer readable storage medium comprising a set of instructions executable by a computer, the non-transitory computer readable storage medium comprising:

instructions for creating a graph from a plurality of sample executable files by executing the sample executable files in an isolated execution environment, the graph including sample file nodes associated with the sample executable files and behavior nodes associated with behavior signatures, wherein edges in the graph connect a behavior node with a set of one or more sample file nodes, wherein the one or more sample executable files associated with the one or more sample file nodes exhibit the behavior signature associated with the behavior node;

instructions for receiving data indicating a label distribution of a neighbor node of a sample file node in the graph;

instructions for, in response to determining that a current label for the sample file node is unknown, setting the current label distribution for the sample file node to a consensus of label distributions of neighboring nodes;

instructions for, in response to determining that the current label for the sample file node is known, performing operations including;

creating a phantom node associated with the sample file node, determining a neighborhood opinion for the phantom node, based at least in part on the label distribution of the neighboring nodes,

determining a difference between the neighborhood opinion and the current label for the sample file node, and

determining whether the current label is incorrect based, at least in part on the difference; and

instructions for, in response to determining that the current label for the sample file node is incorrect, performing at least one remedial action on the sample executable file associated with the sample file node having the incorrect current label.

15. The non-transitory computer readable storage medium of claim 14 further comprising instructions for performing an iterative label propagation operation.

16. The non-transitory computer readable storage medium of claim 14, wherein the at least one remedial action comprises flagging at least one of the current node and the sample executable file associated with the current node for further analysis.

17. The non-transitory computer readable storage medium of claim 14, wherein the at least one remedial action comprises applying at least one malware detection tool to determine what the current label should be.

18. The non-transitory computer readable storage medium of claim 14, wherein the current label indicates that the sample executable file associated with current label contains malware, further comprising instructions for determining that the sample executable file associated with the current label does not contain malware.

19. The non-transitory computer readable storage medium of claim 14, wherein the current label indicates that the sample executable file associated with current label is free of malware, further comprising instructions for determining that the sample executable file associated with the current label does not contain malware.