Simple regexp length error not caught by Gateway

[akhenakh]

A simple regexp is rejected by Envoy Proxy:

Envoy Proxy is measuring a regexp complexity and compare it with max_program_size.

According to this, increasing it per entry has been deprecated several years ago
https://github.com/envoyproxy/envoy/blob/main/api/envoy/type/matcher/regex.proto#L41

Using 0.6.0 Gateway, this value is still 100 which is quite low, for example this regexp is valued 118:
^/v4/advisory/[0-9a-z-]{36}/clone$.

Envoy Proxy will reject it at runtime, we found it the hard way, since on a restart it will then refuse to load every route 404ing on everything.

Can we increase the default in Gateway and raise an error earlier in Gateway rather than in Proxy?

[zirain]

will custom bootstrap help this? should EG make runtime_flags configurable?

[akhenakh]

It seems other gateways are defaulting to 1000.

In the meantime yes I'm trying to change via replacing the bootstrap...
static_layer:
re2.max_program_size.error_level: 1000

[arkodg]

thanks for raising this issue, looks like the outcome of this issue is

• figure out what the re2.max_program_size.error_level should be for the default case
• set it in the bootstrap
• add a validation in the gateway-api layer to make sure we reject long regexes, else envoy will NACK and reject all xds

as mentioned by zirain, workaround for now is to use a custom bootstrap
https://gateway.envoyproxy.io/latest/user/customize-envoyproxy/#customize-envoyproxy-bootstrap-config

[akhenakh]

For refs this is a working config:

  bootstrap:
    type: Merge
    value: |
      layered_runtime:
        layers:
        - name: "static-runtime"
          static_layer:
            re2.max_program_size.error_level: 1000

[davidalger]

It seems other gateways are defaulting to 1000.

I did some looking into this. I've seen this in a few places as well as issues opened because 1000 is also not high enough. For example, here are a couple "high cost" expressions:

• ^/api/v1/object/[^\/]{124}/action$ has program size of 1003
• ^/static/[a-zA-Z0-9._-]{0,200}/[a-zA-Z0-9._-]{0,200}$ has program size of 2005

Size can increase linearly based on the length of a single match due to how cost is calculated in RE2. For the first example the cost increases by 8 as the length of the match is incremented, or: 11 + 8 * 124 == 1003

Program size of regular expressions can also apparently change between RE2 versions, which happened when the cost of . was reduced in 2019 breaking a test in Envoy (xref9174#issue-530487212)

Kuma raised the error level configured in Envoy to uint32 max value with warn level of 1000 a while back:

• xref: Use layered runtime to max out the regex program size kumahq/kuma#2103
• xref: fix(kuma-cp) raise the regex program size limit kumahq/kuma#2139

Contour did similar and set the warning level to 1000 with an error level of 2 ^ 20 at some point (xref) although it may have changed since then.

As it stands currently this is a serious stability issue, so what I'd like to propose is initially we configure error_level to UINT32_MAX and warn_level to 1000 in the bootstrap template:

re2.max_program_size.error_level: 4294967295
re2.max_program_size.warn_level: 1000

With this the error should no longer occur as Envoy will effectively not enforce the deprecated max_program_size option, but will continue to warn for higher complexity matches:

[2024-02-07 17:17:51.358][1][warning][misc] [source/common/common/regex.cc:41] regex '^/static/[a-zA-Z0-9._-]{0,200}/[a-zA-Z0-9._-]{0,200}$' RE2 program size of 2005 > max program size of 1000 set for the warn level threshold. Increase configured max program size if necessary.
[2024-02-07 17:17:51.358][1][warning][misc] [source/common/common/regex.cc:41] regex '^/api/v1/object/[^\/]{124}/action$' RE2 program size of 1003 > max program size of 1000 set for the warn level threshold. Increase configured max program size if necessary.

Envoy will also emit a counter re2.exceeded_warn_level, incremented each time the warn level threshold is exceeded providing visibility into how often this is exceeded.

In the future regex validation and optionally configurable program size limits could be implemented to enforce in the gateway controller to prevent publishing invalid or costly regex matches in the XDS. Envoy proxy comments seem to indicate this is the expected path forward:

// This field is deprecated; regexp validation should be performed on the management server
// instead of being done by each individual client.

If this sounds reasonable, I'll open an MR to add the max_program_size settings to the bootstrap template.

[arkodg]

thanks for digging deeper into this @davidalger
agree with the approach of setting error_level to UINT32_MAX and warn_level to 1000 for now

either in the same PR or different, lets also highlight this in the control plane as a status
using https://pkg.go.dev/regexp/syntax (len(prog.Inst) is a close approximation)

[davidalger]

Submitted a PR to amend the bootstrap config. I'll look into validation and exposing in route status as a followup.