Detecting and preventing execution of a malicious computer application using utility driven graph summarization

Patent metadata

Field	Value
Publication number	US-10742670-B1
Application number	US-201815956608-A
Country	US
Kind code	B1
Filing date	Apr 18, 2018
Priority date	Apr 18, 2018
Publication date	Aug 11, 2020
Grant date	Aug 11, 2020

Abstract

Utility driven graph summarization for use in detecting and preventing malicious computer application. In one embodiment, a method may include receiving a graph comprising a plurality of nodes and a plurality of edges, prioritizing each of the plurality of nodes by way of assigning a relative importance value to each node of the plurality of nodes, combining at least two nodes of the plurality of nodes into a supernode based at least on the relative importance value of each node, calculating a utility penalty value for creating a superedge between the supernode and a node neighboring the supernode, creating the superedge between the supernode and the node neighboring the supernode if the utility penalty value satisfies a pre-determined penalty threshold, calculating a utility level based at least in part on creating the supernode and the superedge, and repeating the method until the calculated utility level satisfies a pre-determined threshold.

First claim

The invention claimed is:

1. A computer-implemented method for detecting and preventing execution of a malicious computer application using utility driven graph summarization, at least a portion of the method being performed by a computing system comprising one or more processors, the method comprising:
(a) receiving a first graph comprising a plurality of nodes and a plurality of edges, the first graph used for detecting and preventing execution of the malicious computer application on the computing system, the first graph having a first utility level;
(b) prioritizing each of the plurality of nodes by way of assigning a relative importance value to each node of the plurality of nodes;
(c) combining at least two nodes of the plurality of nodes into a supernode based at least on the relative importance value of each node;
(d) calculating a utility penalty value for creating a superedge between the supernode and a node neighboring the supernode;
(e) creating the superedge between the supernode and the node neighboring the supernode if the utility penalty value satisfies a pre-determined penalty threshold;
(f) calculating a second utility level based at least in part on creating the supernode and the superedge;
(g) repeating (a)-(f) until the calculated second utility level satisfies a pre-determined utility threshold resulting in a second graph;
(h) in response to determining that the calculated second utility level satisfies the pre-determined utility threshold, employing the second graph to analyze a computer application and determine that the computer application is malicious; and
(i) performing a security action on the malicious computer application to prevent the malicious computer application from executing in a computing environment.

2. The method of claim 1 , wherein the assigning of the relative importance value to each node of the plurality of nodes at (b) further comprises:
executing a centrality algorithm on the plurality of nodes.

3. The method of claim 1 , wherein the combining of at least two nodes of the plurality of nodes at (c) further comprises:
determining, for each node of the plurality of nodes, a list of pairs of two-hop neighbors;
calculating a sum of the relative importance value of each of the nodes in each of the pairs of two-hop neighbors;
sorting each of the pairs of two-hop neighbors based at least in part on the sum of the relative importance value; and
combining the nodes in the pair of two-hop neighbors having a lowest sum.

4. The method of claim 3 , wherein the determining of the list of pairs of two-hop neighbors further comprises:
determining, for each node of the plurality of nodes, a list of neighboring nodes having an edge distance equal to two.

5. The method of claim 1 wherein the calculating of the utility penalty value at (d) further comprises:
identifying at least one spurious edge in the first graph;
assigning a benefit value to the at least one spurious edge; and
adjusting the first utility level based at least in part on the benefit value.

6. The method of claim 1 wherein the calculating of the utility penalty value at (d) further comprises:
identifying an absence of a previously present edge;
assigning a benefit value to the previously present edge; and
adjusting the first utility level based at least in part on the benefit value.

7. The method of claim 1 , wherein the calculating of the utility penalty value at (d) further comprises:
determining a benefit value that combining a first edge between the supernode and a neighboring node and a second edge between the supernode and the neighboring node satisfies the pre-determined penalty threshold.

8. The method of claim 1 , further comprising:
after creating the superedge at (e), eliminating previous edges present between the nodes of the supernode and neighboring nodes.

9. The method of claim 1 , wherein the assigning of the relative importance value at (b) further comprises:
executing a centrality algorithm on the plurality of nodes.

10. The method of claim 1 , further comprising:
maintaining a record of utility calculations for each repetition of (a)-(f).

11. The method of claim 1 , wherein the repeating of (a)-(f) further comprises:
repeating (a)-(f) iteratively until the calculated second utility level is equal to or greater than the pre-determined utility threshold.

12. The method of claim 1 , further comprising:
determining that the utility penalty value is greater than the pre-determined utility threshold; and
maintaining an original edge between at least one of the nodes of the pair of nodes of the supernode and a neighboring node without creating a superedge.

13. The method of claim 1 , wherein the prioritizing of the nodes at (b) further comprises:
assigning a weight value to each of the nodes of the plurality of nodes such that the sum of the weight values for all of the nodes is equal to one.

14. The method of claim 1 , wherein the first utility level is equal to a user-specified composition ratio of the number of nodes and the number of edges.

15. The method of claim 1 , wherein performing the security action further comprises:
at least one of removing the malicious computer application from the computing environment; quarantining the malicious computer application in the computing environment; alerting an administrator to the malicious computer application; testing the malicious computer application in a safe environment; sending the malicious computer application to a separate computing environment for testing or a combination herein.

16. One or more non-transitory computer-readable media comprising one or more computer-readable instructions that, when executed by one or more processors of a computing device, cause the computing device to perform a method for detecting and preventing execution of a malicious computer application using utility driven graph summarization, the method comprising:
(a) receiving a first graph comprising a plurality of nodes and a plurality of edges, the first graph used for detecting and preventing execution of the malicious computer application on the computing system, the first graph having a first utility level;
(b) prioritizing each of the plurality of nodes by way of assigning a relative importance value to each node of the plurality of nodes;
(c) combining at least two nodes of the plurality of nodes into a supernode based at least on the relative importance value of each node;
(d) calculating a utility penalty value for creating a superedge between the supernode and a node neighboring the supernode;
(e) creating the superedge between the supernode and the node neighboring the supernode if the utility penalty value satisfies a pre-determined penalty threshold;
(f) calculating a second utility level based at least in part on creating the supernode and the superedge; and
(g) repeating (a)-(f) until the calculated second utility level satisfies a pre-determined utility threshold resulting in a second graph;
(h) in response to determining that the calculated second utility level satisfies the pre-determined utility threshold, employing the second graph to analyze a computer application and determine that the computer application is malicious; and
(i) performing a security action on the malicious computer application to prevent the malicious computer application from executing in a computing environment.

17. The one or more non-transitory computer-readable media of claim 16 , wherein the combining of at least two nodes of the plurality of nodes further at (c) comprises: determ

Assignees

• Symantec Corp
• Nortonlifelock Inc

Inventors

• Kayyoor Ashwin Kumar
• Efstathopoulos Petros

Classifications

• H04L63/1441

  Countermeasures against malicious traffic (countermeasures against attacks on cryptographic mechanisms H04L9/002) · CPC title

• H04L63/1408

  by monitoring network traffic (monitoring network traffic per se H04L43/00) · CPC title

• G06F21/56 Primary

  Computer malware detection or handling, e.g. anti-virus arrangements · CPC title

• H04L63/1425

  Traffic logging, e.g. anomaly detection · CPC title

• G06F21/53

  by executing in a restricted environment, e.g. sandbox or secure virtual machine · CPC title