Re: [musl] Bug: BOL/EOL anchors in regex capture groups won't match EOL

[Szabolcs Nagy <nsz@port70.net>]

* Mike Beattie <mike@ethernal.org> [2022-07-21 18:08:19 +1200]:
> FRRouting uses musl-libc in its docker container build, and it also appears
> to be in use in the GNS3 appliances for frr available online.
> 
> BGP as-path matching is regex powered, and usage of a special token of '_'
> allows for the easy matching of the boundary of an ASN in an as-path.
> Internally, it's translated into the regex capture group of:
> 
>    (^|[,{}() ]|$)
> 
> A valid as-path is a sequence of integers such as:
> 
>    100 200 300
> 
> A BGP as-path filter might be specified as so:
> 
>    bgp as-path access-list foo seq 20 permit _300_
> 
> which would get expanded to:
> 
>    (^|[,{}() ]|$)300(^|[,{}() ]|$)
> 
> when checking for a match. The usage of the pattern "(^|$)" in musl's regex
> implementation will never match EOL, but it does match BOL. Removal of the
> circumflex will let the match succeed.

thanks for the report.

it seems to me regcomp does not handle assertions corretly if there is
a union (|) of multiple subexpressions that match the empty string.

it simply takes the assertion of the leftmost subexpression so e.g.

'(|$)a' matches 'a' but
'($|)a' does not because it matches as '$a' and the $ assertion fail.

since posix does not allow (| empty pattern in the syntax a conforming
example is e.g.

'(b*|$)a' vs '($|b*)a'

all supported assertions are affected (^, $, \b, \B, \<, \>).

the fix is not obvious: there is a regcomp step like

	tags, assertions = leftmost_empty_match(subexpr)
	process(tags, assertions)

which should be

	list = all_empty_match(subexpr)
	for tags, assertions in list:
		if assertions are weaker than previous ones:
			process(tags, assertions)

i think this can increase storage and computation requirements
significantly unless the algorithm is further optimized.


> 
> Here is the output of a test programs I've written to confirm this:
> 
>    $ musl-gcc -o r r.c
> 
>    $ ./r "_300_" "100 200 300"
>    regex: (^|[,{}() ]|$)300(^|[,{}() ]|$)
>    regexec on [100 200 300]: NOT Found
> 
> Removal of "^|" from the beginning of the trailing capture group:
> 
>    $ ./r "(^|[,{}() ]|$)300([,{}() ]|$)" "0000 1111 2222"
>    regex: (^|[,{}() ]|$)300([,{}() ]|$)
>    regexec on [100 200 300]: Found
> 
> Thanks,
> Mike.
> -- 
> Mike Beattie <mike@ethernal.org>