Anomaly detection in groups of network addresses

• US 9,497,206 B2
• Filed: 04/16/2014
• Issued: 11/15/2016
• Est. Priority Date: 04/16/2014
• Status: Active Grant

• Current Assignee: Cyber-Ark Software Limited (CyberArk Software Ltd.)
• Original Assignee: Cyber-Ark Software Limited (CyberArk Software Ltd.)
• Inventors: Bernstein, Ruth, Dulkin, Andrey, Weiss, Assaf, Shmueli, Aviram
• Primary Examiner(s): Rashid, Harunur
• Assistant Examiner(s): TAYLOR, SAKINAH W
• Application Number:
  US14/253,945
• Publication Number:
  US 20150304349A1
• Time in Patent Office: 944 Days
• Field of Search: 726/22, 726/23, 726/24, 726/25
• US Class Current: 1/1
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/1425 Traffic logging, e.g. anomaly detection

Abstract

A method for identifying anomalies in a group of network addresses includes building a model of the group of network addresses and identifying a network address as anomalous based on the deviation of the network address from the model. The model is built from a group of network addresses. The network addresses are input and parsed into one or more address trees. A ripeness score is maintained for each of the nodes in the address trees, based, at least in part, on the number of occurrences of the network address portion represented by the node. Nodes having respective ripeness scores within a specified range are classified as ripe nodes, and may be indicative of normal behavior, and nodes having respective ripeness scores outside the specified range of ripeness scores are classified as unripe, and may be indicative of anomalous behavior.

Claims

1. A method for identifying anomalies in a group of network addresses, comprising:

inputting, with a data processor, a plurality of network addresses;

parsing said plurality of network addresses, with said data processor, into at least one tree data structure, each tree data structure comprising a plurality of nodes wherein successive nodes in said tree data structure represent successive portions of said network addresses;

during said parsing, assigning a respective ripeness score to each of said nodes, said respective ripeness score indicating a number of occurrences of each of said nodes in said plurality of network addresses;

building a model of normal behavior from tree data structure nodes assigned respective ripeness scores within a specified range of ripeness scores and excluding from said tree data structure nodes with assigned respective ripeness score outside said specified range; and

for an input network address;

traversing said model of network behavior along said input network address;

identifying whether said input network address is anomalous based on a deviation of said network address from said traversed model, said deviation being zero when said traversing said model of network behavior along said input network address leads to a leaf node;

when an anomalous network address is identified, calculating an abnormality score indicating said deviation of said anomalous network address from said model and reclassifying said anomalous network address as normal when said abnormality score is below a specified level; and

when said tree data structure comprises less than specified number of leaves and at least some of said leaves have respective ripeness scores greater than a specified ripeness score, recalculating said abnormality score for said identified anomalous network address.

2. A method according to claim 1, further comprising identifying said input network address as anomalous when said input network address is incompletely traversed inside said model.

3. A method according to claim 1, wherein said input network address is associated with at least one of:

a network event and an entity.

4. A method according to claim 1, wherein said plurality of network addresses is ordered and said parsing is performed in said order.

5. A method according to claim 1, wherein each of said network addresses has a respective timestamp.

6. A method according to claim 1, further comprising triggering an alert when an anomalous network address is identified.

7. A method according to claim 1, wherein said respective ripeness score is further a function of a frequency of occurrence of said node during a specified time range.

8. A method according to claim 1, further comprising pruning an intermediate node by logically removing descendants of said intermediate node from said tree data structure, such that pruned node spans a sub-range of network addresses in said tree data structure, such that said pruned node becomes a leaf node in said tree data structure.

9. A method according to claim 8, wherein said intermediate node is pruned in accordance with at least one of:

a number of descendants of said intermediate node and a depth of said intermediate node in said tree data structure.

10. A method according to claim 1, wherein said network addresses are associated with an entity such that said tree data structure models normal behavior for said entity, and wherein said entity comprises at least one of:

a user, an application, a client, a device, a target machine, an account and a command.

11. A method according to claim 1, wherein at least one network address in said plurality of network addresses is input from one of a group comprising:

an agent monitoring user activity, a network element monitoring communication within said network and a list of network addresses.

12. A method according to claim 1, further comprising classifying a tree data structure as a mature tree when said tree data structure comprises at least a specified number of nodes with a respective ripeness score within said specified range of ripeness scores, wherein said identifying whether said input network address is anomalous is performed only on mature trees.

13. A method according to claim 1, further comprising updating said tree data structure with said specified network address by:

when said tree data structure comprises anode representing said specified network address, incrementing respective ripeness scores of nodes traversed through said tree data structure to said node representing said specified network address; and

when said specified network address is outside said tree data structure, adding anode representing said specified address to said tree data structure, initializing a respective ripeness score of said added node and incrementing respective ripeness scores of nodes traversed through said tree data structure to said added node.

14. A method according to claim 1, further comprising removing one of said network addresses from said tree data structure when a respective number of occurrences of said removed network address over a specified time period is less than a specified minimum number of occurrences.

15. A method according to claim 1, wherein each of said network addresses comprises an ordered sequence of symbols having a respective type, and a direction of said parsing is in accordance with said respective type.

16. A method according to claim 1, wherein said specified network address is one of:

a destination of a data communication session and a sender of a data communication session.

17. A system for identifying anomalies in a group of network addresses, comprising:

a non-transient computer-readable storage medium storing code instructions; and

a processor coupled to said storage medium and adapted to execute the stored code, the code comprising;

instructions for inputting a plurality of network addresses;

instructions for parsing a plurality of network addresses into at least one data structure, each tree data structure comprising a plurality of nodes wherein successive nodes in said tree data structure represent successive portions of the network address;

instructions for, during said parsing, assigning a respective ripeness score to each of said nodes, said respective ripeness score indicating a number of occurrences of each of said nodes in said plurality of network addresses;

instructions for building a model of normal behavior from tree data structure nodes assigned respective ripeness scores within a specified range of ripeness scores and excluding from said tree data structure nodes with assigned respective ripeness score outside said specified range;

instructions for traversing said model of network behavior along an input network address;

instructions for identifying whether said input network address is anomalous normal based on a deviation of said network address from said traversed model, said deviation being zero when said traversing said model of network behavior along said input network address leads to a leaf node;

instructions for, when an anomalous network address is identified, calculating an abnormality score indicating said deviation of said anomalous network address from said model, and reclassifying said anomalous network address as normal when said abnormality score is below a specified level; and

instructions for, when said tree data structure corn rises less than specified number of leaves and at least some of said leaves have respective ripeness scores greater than a specified ripeness score, recalculating said abnormality score for said identified anomalous network address.

18. A system according to claim 17, wherein said processor is further adapted to execute code instructions for identifying said input network address as anomalous when said input network address is incompletely traversed inside said model.

19. A system according to claim 17, wherein said processor is further adapted to execute code instructions for triggering an alert when said anomalous network address is identified.

20. A system according to claim 17, wherein processor is further adapted to execute code instructions for pruning an intermediate node by logically removing descendants of said intermediate node from said tree data structure, such that pruned node spans a sub-range of network addresses in said tree data structure, such that said pruned node becomes a leaf node in said tree data structure.

21. A system according to claim 17, wherein processor is further adapted to execute code instructions for updating said tree data structure with said specified network address by:

when said tree data structure comprises a node representing said specified network address, incrementing respective ripeness scores of nodes traversed through said tree data structure to said node representing said specified network address; and

when said specified network address is outside said tree data structure, adding anode representing said specified address to said tree data structure, initializing a respective ripeness score of said added node, and incrementing respective ripeness scores of nodes traversed through said tree data structure to said added node.

22. A computer program product for identifying anomalies in a group of network addresses, the computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions executable by a data processor to cause the processor to:

input, with a data processor, a plurality of network addresses;

parse said plurality of network addresses into at least one tree data structure, each tree data structure comprising a plurality of nodes wherein successive nodes in said tree data structure represent successive portions of said network addresses;

assign a respective ripeness score to each of said nodes during said parsing, said respective ripeness score indicating a number of occurrences of each of said nodes in said plurality network addresses;

build a model of normal behavior from tree data structure nodes assigned respective ripeness scores within a specified range of ripeness scores and excluding from said tree data structure nodes with assigned respective ripeness scores outside said specified range;

for an input network address;

traverse said model of network behavior along said input network address; and

identify, with said data processor, whether said input network address is anomalous based on a deviation of said network address from said traversed model, said deviation being zero when said traversing said model of network behavior along said input network address leads to a leaf node;

calculate, when an anomalous network address is identified, an abnormality score indicating a deviation of anomalous network address from had model and reclassify said anomalous network address as normal when said abnormality score is below a specified level; and

when said tree data structure comprises less than specified number of leaves and at least some of said leaves have respective ripeness scores greater than a specified ripeness score, recalculate said abnormality score for said identified anomalous network address.

23. A computer program product according to claim 22, comprising further program instructions executable by said data processor to identify, with said data processor, said input network address as anomalous when said input network address is incompletely traversed inside said model.