System and method for range matching

• US 10,630,588 B2
• Filed: 07/23/2015
• Issued: 04/21/2020
• Est. Priority Date: 07/24/2014
• Status: Active Grant

• Current Assignee: Cognyte Technologies Israel Ltd. (Cognyte Software Ltd.)
• Original Assignee: Verint Systems Limited (Verint Systems Incorporated)
• Inventors: Yishay, Yitshak
• Primary Examiner(s): Thier, Michael
• Assistant Examiner(s): Mensah, Prince A
• Application Number:
  US14/807,808
• Publication Number:
  US 20160028631A1
• Time in Patent Office: 1,734 Days
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 61/35 involving non-standard use of addresses for implementing network functionalities, e.g. coding subscription information within the address or functional addressing, i.e. assigning an address to a function
• CPC Class Codes: H04L 61/4552 Lookup mechanisms between a plurality of directories; Synchronisation of directories, e.g. metadirectories
• CPC Class Codes: H04L 61/5007 Internet protocol [IP] addresses

Abstract

Methods and systems for range matching. The system holds a definition of one or more ranges of Internet Protocol (IP) addresses. The definition may specify any desired number of ranges of any suitable size, and some ranges may overlap one another or be contained in one another. The definition may also specify certain returned values and/or relative priorities for the various ranges. In a pre-processing phase, a hash table that is subsequently queried with addresses to be range-matched. The hash table may be updated at run-time. During operation, the system receives addresses (e.g., extracts addresses from monitored communication traffic) and identifies by querying the hash table, for each address, whether the address falls within any of the ranges.

Claims

1. A method for IP address range matching, the method comprising:

constructing a hash table comprising a plurality of entries corresponding to predefined ranges of IP addresses, wherein the hash table specifies relative priorities among the predefined ranges of IP addresses;

storing the hash table in a processor cache memory;

monitoring packets exchanged over a network to obtain an IP address from a packet;

generating a first key, wherein the first key comprises a first sequence of bits of the IP address that begins with the most significant bit and wherein the first key is generated by applying a first template to the IP address by calculating a bit-wise AND between a bit mask and the IP address;

querying the hash table using the first key to obtain a first entry that specifies an inconclusive result, wherein the inconclusive result includes an updated template;

applying, after obtaining the inconclusive result, the updated template to the IP address to obtain an updated key, wherein the updated key comprises an updated sequence of bits of the IP address that begins with the most significant bit, and wherein the updated key includes more bits of the IP address than the first key;

repeating the querying using updated keys and the applying updated templates until a conclusive result is achieved;

matching, based on the entry specifying the conclusive result with the highest priority, the IP address to one of the predefined ranges of IP addresses; and

discarding packets according to results of said matching step.

2. The method for IP address range matching according to claim 1, wherein the matching the IP address to one of the predefined ranges of IP addresses comprises:

checking the IP address against sub-ranges specified by an entry of the one or more entries specifying conclusive results.

3. The method for IP address range matching according to claim 1, further comprising:

routing the packet based on the matching.

4. The method for IP address range matching according to claim 1, further comprising:

analyzing the packet based on the matching.

5. The method for IP address range matching according to claim 1, further comprising:

communicating to an intrusion detection system, based on the matching.

6. The method for IP address range matching according to claim 1, wherein the querying the hash table using the first key, further comprises:

obtaining a negative result that the IP address is not within any of the predefined ranges of IP addresses specified by the hash table.

7. The method of claim 1, wherein the updated template is a bit mask.

8. The method of claim 1, wherein the predetermined number of times is 1.

9. The method of claim 1, wherein the predetermined number of times is 2.

10. The method of claim 1, wherein the conclusive result is an indication the IP address falls within one of the predefined ranges of IP addresses.