Finding Multiple Regular Expressions with Hyperscan

In this article, I would like to talk about my own experience in optimizing the execution of many regular expressions using the hyperscan system . It turned out that when developing my rspamd spam filter , I was faced with the need to port a large amount of old rules written for spamassassin over several years of work. My first decision was to write a plugin that reads these rules and builds a syntax tree from them. Then, various optimizations were performed on this tree to reduce the overall execution time (I even made a short presentation about this ).

Unfortunately, during the operation it turned out that pcre is still a bottleneck, and for large letters this set of rules is too slow. It turned out, for example, that on a megabyte-sized letter pcre checks for about a gigabyte (!) Of text. Various tricks, such as limiting the amount of text for regular expressions, had a negative impact on the rules, and optimizing pcre by using jit fast path through pcre_jit_exec intensively turned out to be too dangerous - some old expressions were frankly incorrect and combined with incorrect input text, for example, containing “Beaten” UTF8 characters led to reproducible bugs with damage to the program stack. However, at the highload conferencewe talked with Vyacheslav Olkhovchenkov, and he advised me to look at hyperscan. Next, I will go to the point and tell you what came of it.

Briefly about hyperscan

Hyperscan is a project with a fairly long history, and it was created to sell deep packets introspection (DPI) solutions. But in October last year, Intel decided to open its source code, and even under the BSD license. The project is written in C ++ with rather intensive use of boost, which causes certain problems when porting (but more on that later). Inside, hyperscan is a non-backtracking regular expression engine based on a non-deterministic finite state machine (NFA). In principle, all modern performance-oriented regular expression engines are written using the same theory and completely abandon backtracking (which, of course, is quite rational if you want to ensure linear search speed). The most important hyperscan feature for me was the abilitysimultaneous execution of many regular expressions on some text. The naive approach to doing the same thing in pcre is to try combining multiple expressions with | in a sort of "sausage":

(?: re1) | (?: re2) | ... | (?: reN)

. Unfortunately, this approach will not work - after all, the task is to find all the occurrences from a given set of expressions, and not just those that worked before. Hyperscan doesn’t work like that - for each expression found, it calls a callback function with a position in the text (though only the last character of the entry), which can be shown in the following diagram:

Hyperscan Architecture

Hyperscan consists of two parts: the compiler and, in fact, the engine. The compiler is a very large part of the library, which can take a bunch of expressions, compose an NFA for it, and convert this NFA to assembly code using, for example, vector instructions, in particular, AVX2. This task is difficult and resource-consuming, so the compiler also allows you to serialize the resulting code for later use. The search engine is a smaller library, and it is, in fact, designed to run NFA on specific text. For applications that use only precompiled expression sets, you can use the separate libhs_runtime library , which is much smaller than the compiler + engine libhs combined library. To start, I tried to build hyperscan, which turned out to be a fairly simple task if there is a fairly fresh boost for the system (minimum version 1.57). Perhaps the only remark is that when building with debugging symbols, the library is just gigantic - about 200Mb on my macbook. And since by default only a static library is collected, when connected, its size of binaries is also obtained in the region of 200Mb. If debugging symbols are not needed, it is better to collect hyperscan without them, specifying

-DCMAKE_BUILD_TYPE = MinSizeRel

at the configuration stage via cmake.

Test code

Then I tried to compare hyperscan and pcre, writing a very rough prototype that you can see under the spoiler (I warn you - this is the prototype code, which was written in a hurry without any claims to quality).



The result was quite impressive: on a megabyte spam email and a set of ~ 1000 regular expressions, I got the following results:

PCRE compile time: 0.0138553
Hyperscan compile time: 4.94309; approx re: 191; total re: 971
Hyperscan serialize time: 0.00312218; size: 5242956 bytes
Hyperscan deserialize time: 0.00359501; size: 5242956 bytes
Time for individual re: 0.440707; matches: 7
Time for hyperscan re: 0.0770988; matches: 7

Prefilter

One of the most impressive features of hyperscan is its ability to function as a pre-filter. This mode is useful when there are unsupported constructs in the expression, for example, the same backtracking. In this mode, hyperscan creates an expression that is a guaranteed superset of the specified unsupported expression. That is, the new expression is guaranteed to work on all cases of the initial operation, but it can work in other cases, giving a false positive operation. Therefore, the result needs to be checked on a traditional regular expression engine, for example, pcre (although in this case you do not need to run the entire text, but you need to check it from the beginning to the point of occurrence of the pre-expression). This is clearly illustrated in the following diagram:

Compilation issues

Unfortunately, two unpleasant moments became clear. The first one is compilation time — it takes an unrealistically long time compared to pcre. The second point is related to the fact that some expressions simply compile during compilation into the pre-filter. The simplest “vicious” expression was, for example, this:

] {0,2048} \ bhref = (?: 3D)?.? (Https?: [^> "'\ #] {8,29} [^>"' \ #: \ /? & =]) [ ^>] {0,2048}> (?: [^ <] {0,1024} <(?! \ / A) [^>] {1,1024}>) {0,99} \ s {0, 10} (?! \ 1) https? [^ \ W <] {1,3} [^ <] {5}

As a result, I did that before compiling expressions, all pre-filter expressions are first checked in a separate fork of the process. And if the expression compiles too long, then this process is beaten, and the expression is marked as hopeless, that is, pcre is always used for it. About four thousand of these expressions were found. All of them came from my beloved spamassassin'a and are quite characteristic products of the disease called "perl of the brain." After some communication with Intel engineers, they fixed the endless compilation, but the above regexp still compiles on the order of a minute, which is unacceptable for practical purposes.

For hyperscan to work, it also turned out to be necessary to break down sets of expressions into so-called “classes” —this is the type of input text that is checked through regular expressions from the set, for example, the header of a letter with a specific name or the full body of a letter, or only text parts. Such classes are shown in the following diagram:



For compilation, I used the following approach:

• In a separate process, start checking the expression classes, and for each class look for whether there is already a compiled and valid file for it.
• If there is no such file or if it contains the wrong set of expressions (it is checked by the hash of the expression pattern), then compile it by checking the compilation time of the preliminary filters.
• When all expressions are compiled in the cache, then send a message to all processes to the scanners, having received which the scanners load the cached expressions and switch from pcre to hyperscan.

This approach allowed us to start checking mail immediately after launch (using pcre), rather than waiting for an expensive and long hyperscan compilation, and upon completion of compilation, immediately switch from pcre to hyperscan (which is called without leaving the cash desk). And the use of bit sets for checked and triggered regular expressions also allows us not to disturb when switching the work of letters already running in the scan.

conclusions

During the work of rspamd + hyperscan, I got about the following results:

It was:

len: 610591, time: 2492.457ms real, 882.251ms virtual
regexp statistics: 4095 pcre regexps scanned, 18 regexps matched, 694M bytes scanned using pcre

It became:

len: 610591, time: 654.596ms real, 309.785ms virtual
regexp statistics: 34 pcre regexps scanned, 41 regexps matched, 8.41M bytes scanned using pcre, 
9.56M bytes scanned total

The greater number of regexps matched in the hyperscan version is caused by syntax tree optimizations that are performed for pcre but are useless in the case of hyperscan (since all expressions are checked at the same time).

The Hyperscan version is already in production, and is included in the new version of rspamd . I can confidently advise hyperscan for performance-critical projects for checking regular expressions (DPI, proxies, etc.), as well as for applications for finding static lines in text.

For the last task, I made a comparison of hyperscan with the aho-corasick algorithm traditionally used for such purposes . I compared the fastest implementation I know from Mischa Sandberg.

Comparison results for 10 thousand static lines in a megabyte letter with a large number of such lines (that is, the worst possible conditions for aho-corasic having complexity O (M + N), where M is the number of lines found):

actrie compile time: 0.0743811
Hyperscan compile time: 0.1547; approx re: 0; total re: 7400
Hyperscan serialize time: 0.000178297; size: 1250856 bytes
Hyperscan deserialize time: 0.000312379; size: 1250856 bytes
Time for hyperscan re: 0.117938; matches: 3001024
Time for actrie: 0.100427; matches: 3000144

Unfortunately, it also turned out that the number of hits did not converge due to an error in the ac-trie code, while hyperscan never made a mistake.

Also, the materials of this article are available in the presentation . The code can be seen in the rspamd project on the github