Visible to the public Biblio

Filters: Author is Savaria, Yvon  [Clear All Filters]
Luinaud, Thomas, Savaria, Yvon, Langlois, J.M. Pierre.  2017.  An FPGA Coarse Grained Intermediate Fabric for Regular Expression Search. Proceedings of the on Great Lakes Symposium on VLSI 2017. :423–426.

Deep Packet Inspection systems such as Snort and Bro express complex rules with regular expressions. In Snort, the search of a regular expression is performed with a Non-deterministic Finite Automaton (NFA). Traversing an NFA sequentially with a CPU is not deterministic in time, and it can be very time consuming. The sequential traversal of an NFA with a CPU is not deterministic in time consequently it can be time consuming. A fully parallel NFA implemented in hardware can search all rules, but most of the time only a small part is active. Furthermore, a string filter determines the traversal of an NFA. This paper proposes an FPGA Intermediate Fabric that can efficiently search regular expressions. The architecture is configured for a specific NFA based on a partial match of a rule found by the string filter. It can thus support all rules from a set such as Snort, while significantly reduce compute resources and power con-sumption compared to a fully parallel implementation. Multiple parameters can be selected to find the best tradeoff between resource consumption and the number and types of supported expressions. This architecture was implemented on a Xilinx R XC7VX1140 Virtex-7. The reported implementation, can sustain up to 512 regular expressions, while requiring 2% of the slices and 16% of the BRAM resources, for a throughput of 200 million characters per second.

Vakili, Shervin, Langlois, J.M. Pierre, Boughzala, Bochra, Savaria, Yvon.  2016.  Memory-Efficient String Matching for Intrusion Detection Systems Using a High-Precision Pattern Grouping Algorithm. Proceedings of the 2016 Symposium on Architectures for Networking and Communications Systems. :37–42.

The increasing complexity of cyber-attacks necessitates the design of more efficient hardware architectures for real-time Intrusion Detection Systems (IDSs). String matching is the main performance-demanding component of an IDS. An effective technique to design high-performance string matching engines is to partition the target set of strings into multiple subgroups and to use a parallel string matching hardware unit for each subgroup. This paper introduces a novel pattern grouping algorithm for heterogeneous bit-split string matching architectures. The proposed algorithm presents a reliable method to estimate the correlation between strings. The correlation factors are then used to find a preferred group for each string in a seed growing approach. Experimental results demonstrate that the proposed algorithm achieves an average of 41% reduction in memory consumption compared to the best existing approach found in the literature, while offering orders of magnitude faster execution time compared to an exhaustive search.