Improving the Performance of Regular Expressions - Documentation for Bmc Discovery 20.08

BMC Discovery allows users to enter regular expressions (regexes) for a number of purposes, such as:

• associating TPL rules with events
• processing information in the body of a TPL pattern
• filtering out sensitive information from command lines.

These regular expressions are often matched against a large data set, so it is important that they are written to be efficient.

Why is regular expression efficiency important?

While a well written regular expression can be very efficient, a badly written regular expression might take a long time to run and slow the system down significantly. It is quite possible to write a regular expression that will take hours or days to finish - it is even possible to write a regular expression that will not finish within the lifetime of the universe when run against moderately sized strings.

Several improvements have been made in BMC Discovery to make it more robust against inefficient regular expressions than previous versions. It now minimizes the regular expression matching needed when deciding which TPL patterns to run. It also spreads the work of running TPL patterns among multiple processors so that if one is busy with a long regular expression match, the other processors can carry on working.

Despite the improvements, writing efficient regular expressions is still important for keeping BMC Discovery running at its best. If BMC Discovery slows down significantly while scanning a network and either the reasoning or discovery service are using 100% CPU for long periods then one possible cause is an inefficient regular expression.

Anatomy of an inefficient regular expression

So how do you write an inefficient regular expression? One problem is when the regular expression does excessive backtracking; this can happen when there is more than one repetition operator in the regular expression. A repetition operator is +, *, or {n,m}. If the regular expression makes a partial match but then fails, then it must loop back and try any other possible partial matches in case any of them succeed.

For example, consider matching the regular expression a.*b.*cd against the string abc abc abc. The match will never succeed since there is no d in the string, but the regular expression must still check every possible combination of the letters a, b, and c before it gives up. That is:

"*abc* abc abc",
"*ab*c ab*c* abc",
"*ab*c abc ab*c*",
"*a*bc a*bc* abc",
"*a*bc a*b*c ab*c*",
"*a*bc abc a*bc*",
"abc *abc* abc",
"abc *ab*c ab*c*",
"abc *a*bc a*bc*",
"abc abc *abc*"

As a rough guide the number of comparisons that the regular expression needs to perform is proportional to the length of the string times the number of possible intermediate matches.

In this example using the non-greedy operators, that is, a.*?b.*?cd, makes no difference to the number of matches it will make, since the regular expression engine still needs to try every combination.

Real World examples

Let's take a look at some examples based on real regular expressions that have caused problems in BMC Discovery:

\b.*xx.*foo

This was a regular expression that was compared against the command line of processes found on a host. It was failing when run against a half-megabyte string which included lots of repetitions of xx but did not contain foo.

Let's break down what happens when it is matched against a string:

1. The engine starts scanning from the start of the string.
2. The engine scans forward until it finds a word boundary \b.
3. The engine scans forward from the word boundary until it finds a matching xx.
4. The engine scans forward from the xx until it finds the string foo or it reaches the end of the string.
5. If it has reached the end of the string and not matched foo, it loops back to step 3 and scans forward to the next xx.
6. If it has matched all the xx and still not found foo, it loops back to step 2 and scans forward to the next word boundary.

So the regular expression matching contains nested loops; the total processing time is determined by the length of the string (for the command line that was causing the problem this was approximately 500,000) times the number of xx substrings (approximately 500) times the number of word boundaries (approximately 80,000). This was roughly equivalent to scanning a string twenty trillion characters long, and took more than a day to complete.

This was fixed in two ways:

Firstly, the \b.* was removed from the start of the regular expression, since it served no purpose other than to slow the whole thing down. This change reduced the runtime from days to a few seconds.

Secondly, we can use knowledge about the data we want to match; in this case we are only interested in the text from the start of the string up to the first space. So to stop the regular expression scanning the entire string we can anchor the regular expression to the start of the string with ^ and use the \S token to match non-whitespace characters. The final regular expression ^\S*xx\S*foo will stop as soon as it reaches a whitespace character. It now takes a few microseconds when run against the same string.

-A(\D+)+-B(\D+)

This was used as a sensitive data filter. The intention was to scan command lines and remove options that start with -A and -B. However it not only did not do what the writer intended, it performed in a manner that could potentially take forever to process.

Let's break it down:

1. Scan from the start of the string until we find -A.
2. Match all non-digit characters until we find -B.
3. If -B is not found then try matching every combination of groups between -A and the end of the string or the next digit. For example, if the remainder of the string was abcd then it would match each of the following groups for (\D+)+
(abcd)
(abc)(d)
(ab)(cd)
(ab)(c)(d)
(a)(b)(cd)
(a)(bc)(d)
(a)(bcd)
(a)(b)(c)(d).

The number of combinations will double for each additional character in the remaining string.

So for the situation where the command line contains -A but not followed by -B it will take a time proportional to 2 ^N, where N is the number of characters between the -A and the next digit or end of the string. To put that into perspective, on a standard PC a string of 22 characters takes about one second. A string of 40 characters would take about 3 days, and a string of 100 characters would take 9,583,696,565,945,500 years, though this has not been tested.

This regular expression was fixed by removing the group repetition, since it served no purpose:

-A(\D+)-B(\D+). The runtime went down from forever to a few microseconds.