Skip to content

[8.x] [Security Solution] Fixes multi-line diff algorithm performance in the `upgrade/_review` endpoint (#199388)#200096

Merged
kibanamachine merged 1 commit intoelastic:8.xfrom
kibanamachine:backport/8.x/pr-199388
Nov 13, 2024
Merged

[8.x] [Security Solution] Fixes multi-line diff algorithm performance in the `upgrade/_review` endpoint (#199388)#200096
kibanamachine merged 1 commit intoelastic:8.xfrom
kibanamachine:backport/8.x/pr-199388

Conversation

@kibanamachine
Copy link
Copy Markdown
Contributor

Backport

This will backport the following commits from main to 8.x:

Questions ?

Please refer to the Backport tool documentation

…e `upgrade/_review` endpoint (elastic#199388)

**Fixes elastic#199290

## Summary

The current multi-line string algorithm uses a very inefficient regex to
split and analyze string fields, and exponentially increases in time
complexity when the strings are long. This PR substitutes a much simpler
comparison regex for far better efficiency as shown in the table below.

### Performance between different regex options using sample prebuilt
rule setup guide string

| | `/(\S+\|\s+)/g` (original) | `/(\s+)/g` | `/(\n)/g` |
`/(\r\n\|\n\|\r)/g` |

|-----------------------|---------------|----------|---------|-------------------|
| Unit test speed | `986ms` | `96ms` | `1ms` | `2ms` |
| FTR test with 1 rule | `3.0s` | `2.8s` | `2.0s` | `2.0s` |
| FTR test with 5 rules | `11.6s`        | `6.8s`    | `6.1s`   |  |

### Performance between different regex options using intentionally long
strings (25k characters)

|                      | `/(\S+\|\s+)/g`       | `/(\r\n\|\n\|\r)/g` |
|----------------------|-----------------------|---------------------|
| Unit test speed      | `1049414ms` (17 min)  | `58ms`              |
| FTR test with 1 rule | `>360000ms` (Timeout) | `2.1 s`             |

### Checklist

Delete any items that are not applicable to this PR.

- [x] [Unit or functional
tests](https://www.elastic.co/guide/en/kibana/master/development-tests.html)
were updated or added to match the most common scenarios
- [ ] [Flaky Test
Runner](https://ci-stats.kibana.dev/trigger_flaky_test_runner/1) was
used on any tests changed

### For maintainers

- [ ] This was checked for breaking API changes and was [labeled
appropriately](https://www.elastic.co/guide/en/kibana/master/contributing.html#_add_your_labels)
- [ ] This will appear in the **Release Notes** and follow the
[guidelines](https://www.elastic.co/guide/en/kibana/master/contributing.html#kibana-release-notes-process)

---------

Co-authored-by: Elastic Machine <elasticmachine@users.noreply.github.com>
Co-authored-by: Georgii Gorbachev <georgii.gorbachev@elastic.co>
(cherry picked from commit 4f6d357)
@kibanamachine kibanamachine merged commit 930e586 into elastic:8.x Nov 13, 2024
@elasticmachine
Copy link
Copy Markdown
Contributor

💚 Build Succeeded

Metrics [docs]

✅ unchanged

cc @dplumlee

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

backport This PR is a backport of another PR

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants