US-12625893-B2 - Hardware acceleration device for string matching and range comparison

Abstract

Systems and methods are described for providing effective hardware acceleration by performing a combination of string matching and range comparison. According to one embodiment, acceleration device of a host device associated with datacenter receives an input stream of information. The received information is matched with contents of a hash-based lookup table to identify one or more units, which satisfy at least one condition for any or a combination of a string match and a range comparison. The identified one or more units are correlated based on a set of conditions, which define at least one rule related to any of a network policy definition, a packet inspection rule, a database operation command or a format of the input stream. Any or a combination of exact string matching and exact range matching is then performed based on the at least one set of correlated units.

Inventors

• Zhi Guo
• Xu Zhou

Assignees

• FORTINET, INC.

Dates

Publication Date

20260512

Application Date

20190916

Claims (20)

1. 1 . A method comprising: receiving, by a hardware acceleration device of a host device associated with a data center, an input stream of information, said input stream comprising any combination of a string or an integer range, wherein the hardware acceleration device comprises a SmartNIC on a network interface card (NIC) of the host device and is made available for use of a plurality of other host devices within the data center to perform operations on behalf of one or more of the other host devices; for a string-type input stream, passing the input stream through a set of Bloom filters arranged in a cascaded manner to determine one or more fixed-length characters, and when a length of the input stream is less than a pre-defined threshold, passing the input stream through a symbol content address memory; matching, by the hardware acceleration device, the input stream or parts thereof with contents of a hash based lookup table in a plurality of levels such that each level matches a specific length of the input stream or a part thereof with an entry of the hash-based lookup table, each entry including a value that is a string or an integer range and a type indicating mask is applied to the input prior to a hash index calculation, to identify one or more units of the input stream, which satisfy at least one condition of a plurality of conditions for any combination of a string match and a range comparison; correlating, by the hardware acceleration device, the one or more identified units based on a set of conditions selected from the plurality of conditions to form at least one set of correlated units, wherein the set of conditions define at least one rule related to any of a network policy definition, a packet inspection rule, a database operation command or a format of the input stream; and performing, by the at least one set of correlated units any or a combination of exact string matching and exact range matching.
2. 2 . The method of claim 1 , wherein when a length of said input stream is less than a pre-defined threshold, the input stream is passed through a symbol content address memory to identify the one or more units of the input stream, which satisfy at least one condition.
3. 3 . The method of claim 1 , wherein when the input stream pertains to the string, the method comprises determining one or more fixed length characters from the string so that the one or more fixed length characters are matched with the contents of the hash based lookup table to identify the one or more units of the input stream, which satisfy the at least one condition.
4. 4 . The method of claim 3 , wherein the input stream pertaining to the string is passed through a set of filters arranged in a cascaded manner to determine the one or more fixed length characters from the string.
5. 5 . The method of claim 1 , wherein the acceleration device generates contents of the hash based lookup table based the one or more conditions of the at least one rule.
6. 6 . The method of claim 1 , wherein the input stream pertains to any or a combination of a packet stream from a network interface and a data stream from a storage interface.
7. 7 . The method of claim 1 , wherein the acceleration device transmits the at least one set of correlated units to one or more other host devices of the data center.
8. 8 . The method of claim 1 , wherein when the input stream pertains to the integer range, a mask is applied to the input stream to match the input stream or parts thereof with the contents of the hash based lookup table.
9. 9 . The method of claim 1 , wherein the step of matching is performed in plurality of levels such that each level of the plurality of levels matches a specific length of input stream or part thereof with an entry of the hash based lookup table.
10. 10 . The method of claim 9 , each entry of the hash based lookup table corresponds to a format of the input steam and includes a value of the integer range or the string.
11. 11 . The method of claim 1 , wherein the acceleration device provides hardware acceleration to the one or more other host devices within the data center that each include slower speed capability to that performed by the acceleration device.
12. 12 . A non-transitory computer-readable storage medium embodying a set of instructions, which when executed by one or more processors of an acceleration device of a host device associated with a data center, causes the one or more processors to perform a method comprising: receiving, by a hardware acceleration device of a host device associated with a data center, an input stream of information, said input stream comprising any combination of a string or an integer range, wherein the hardware acceleration device comprises a SmartNIC on a network interface card (NIC) of the host device and is made available for use of a plurality of other host devices within the data center to perform operations on behalf of one or more of the other host devices; for a string-type input stream, passing the input stream through a set of Bloom filters arranged in a cascaded manner to determine one or more fixed-length characters, and when a length of the input stream is less than a pre-defined threshold, passing the input stream through a symbol content address memory; matching, by the hardware acceleration device, the input stream or parts thereof with contents of a hash based lookup table in a plurality of levels such that each level matches a specific length of the input stream or a part thereof with an entry of the hash-based lookup table, each entry including a value that is a string or an integer range and a type indicating mask is applied to the input prior to a hash index calculation, to identify one or more units of the input stream, which satisfy at least one condition of a plurality of conditions for any combination of a string match and a range comparison; correlating, by the hardware acceleration device, the one or more identified units based on a set of conditions selected from the plurality of conditions to form at least one set of correlated units, wherein the set of conditions define at least one rule related to any of a network policy definition, a packet inspection rule, a database operation command or a format of the input stream; and performing, by the at least one set of correlated units any or a combination of exact string matching and exact range matching.
13. 13 . The non-transitory computer-readable storage medium of claim 12 , wherein when a length of said input stream is less than a pre-defined threshold, the input stream is passed through a symbol content address memory to identify the one or more units of the input stream, which satisfy at least one condition.
14. 14 . The non-transitory computer-readable storage medium of claim 12 , wherein when the input stream pertains to the string, the method comprises determining one or more fixed length characters from the string so that the one or more fixed length characters are matched with the contents of the hash based lookup table to identify the one or more units of the input stream, which satisfy the at least one condition.
15. 15 . The non-transitory computer-readable storage medium of claim 14 , wherein the input stream pertaining to the string is passed through a set of filters arranged in a cascaded manner to determine the one or more fixed length characters from the string.
16. 16 . The non-transitory computer-readable storage medium of claim 12 , wherein the acceleration device generates contents of the hash based lookup table based the one or more conditions of the at least one rule.
17. 17 . The non-transitory computer-readable storage medium of claim 12 , wherein the input stream pertains to any or a combination of a packet stream from a network interface and a data stream from a storage interface.
18. 18 . The non-transitory computer-readable storage medium of claim 12 , wherein when the input stream pertains to the integer range, a mask is applied to the input stream to match the input stream or parts thereof with the contents of the hash based lookup table.
19. 19 . A non-transitory computer-readable storage medium embodying a set of instructions, which when executed by one or more processors of a network interface card (NIC) of a network node of a plurality of network nodes within a data center, causes the one or more processors to perform a method comprising: receiving, by a hardware acceleration device of a host device associated with a data center, an input stream of information, said input stream comprising any combination of a string or an integer range, wherein the hardware acceleration device comprises a SmartNIC on a network interface card (NIC) of the host device and is made available for use of a plurality of other host devices within the data center to perform operations on behalf of one or more of the other host devices; for a string-type input stream, passing the input stream through a set of Bloom filters arranged in a cascaded manner to determine one or more fixed-length characters, and when a length of the input stream is less than a pre-defined threshold, passing the input stream through a symbol content address memory; matching, by the hardware acceleration device, the input stream or parts thereof with contents of a hash based lookup table in a plurality of levels such that each level matches a specific length of the input stream or a part thereof with an entry of the hash-based lookup table, each entry including a value that is a string or an integer range and a type indicating mask is applied to the input prior to a hash index calculation, to identify one or more units of the input stream, which satisfy at least one condition of a plurality of conditions for any combination of a string match and a range comparison; correlating, by the hardware acceleration device, the one or more identified units based on a set of conditions selected from the plurality of conditions to form at least one set of correlated units, wherein the set of conditions define at least one rule related to any of a network policy definition, a packet inspection rule, a database operation command or a format of the input stream; and performing, by the at least one set of correlated units any or a combination of exact string matching and exact range matching.
20. 20 . The non-transitory computer-readable storage medium of claim 19 , wherein the NIC is utilized for pattern matching by one or more other of the plurality of network nodes.

Description

COPYRIGHT NOTICE Contained herein is material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent disclosure by any person as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all rights to the copyright whatsoever. Copyright © 2019, Fortinet, Inc. BACKGROUND Field Embodiments of the present invention generally relate to network security and distributed computing. In particular, embodiments of the present invention relate to systems and methods that provide effective hardware acceleration by performing a combination of string matching and range comparison. Description of the Related Art High speed network technologies with complex architectures use pattern matching based on efficient and accurate string matching and range comparison techniques for various applications, such as information retrieval, virus scanning, DNA sequence analysis, data mining, machine learning, network security and pattern recognition. In network architectures, network policies are defined using a combination of integers, integer ranges, time, date, etc. Stand-alone firewall appliances and server-based firewall devices use pattern matching for comparing metadata of network packets (e.g. Internet Protocol (IP) addresses, ports, etc.) against a list of network policies with priority to implement network policy search. As users of cloud computing services platforms and data centers are not typically directly charged for network security workload, it is desirable to free host CPU cores from time consuming tasks, such as network policy search. Additionally, in data centers many user applications, such as database applications, often involve heavy pattern matching, regular expression matching and range comparison techniques. Consequently, such heavy processes increase the computational burden on host systems and create dissatisfying user experience and/or heavy data streams to host processors. When a need to perform certain computational functions more efficiently than a general-purpose CPU arises, a device known as a hardware accelerator may be employed. A hardware accelerator broadly refers to any hardware device that performs certain functions faster and more efficient than a general purpose processor by offloading computationally intense processing tasks that the processor would normally handle. These devices are implemented to decrease latency and increase throughput, thereby improving overall user experience; however, due to the fluctuation of workloads within servers of data centers, hardware accelerators, such as dedicated Peripheral Component Interconnect Express (PCIe)-based boards are not always cost effective. SUMMARY Systems and methods are described for providing effective hardware acceleration by performing a combination of string matching and range comparison. According to one embodiment, an acceleration device of a host device receives an input stream of information including a string and/or an integer range. The input stream or part of the input stream is matched with contents of a hash-based lookup table to identify one or more units of the input stream, which satisfy at least one condition for any or a combination of a string match and a range comparison. The identified one or more units of the input stream are correlated based on set of conditions to form at least one set of correlated units such that the set of conditions define at least one rule related to any of a network policy definition, a packet inspection rule, a database operation command or a format of the input stream. Further, based on the at least one set of correlated units, the acceleration device performs any or a combination of exact string matching and exact range match. Other features of embodiments of the present disclosure will be apparent from accompanying drawings and detailed description that follows. BRIEF DESCRIPTION OF THE DRAWINGS In the Figures, similar components and/or features may have the same reference label. Further, various components of the same type may be distinguished by following the reference label with a second label that distinguishes among the similar components. If only the first reference label is used in the specification, the description is applicable to any one of the similar components having the same first reference label irrespective of the second reference label. FIG. 1 is a block diagram providing a simplified illustration of a data center in which embodiments of the present invention may be utilized. FIG. 2A is a block diagram illustrating an exemplary architecture of a host system including an acceleration device in accordance with an embodiment of the present invention. FIG. 2B is a block diagram illustrating a network interface card (NIC) including an acceleration device in accordance with an embodiment of the present invention. FIG. 3 illustrates examples of a packet inspection rule, a firewall pol