Skip to content

ReDoS: revert new superlinear algorithm. #13127

Merged
erik-krogh merged 5 commits intogithub:mainfrom
erik-krogh:polReDoS
Jun 2, 2023
Merged

ReDoS: revert new superlinear algorithm. #13127
erik-krogh merged 5 commits intogithub:mainfrom
erik-krogh:polReDoS

Conversation

@erik-krogh
Copy link
Contributor

@erik-krogh erik-krogh commented May 11, 2023

We just traded one performance tradeoff with another.
I've gotten too many reports of polynomial-redos timing out recently.

So I've gone back to the ugly approach of limiting the search space for "complex" regular expressions.
But I'm keeping the succ -> pumpEnd rename suggestion from #12628.

Evaluations: Python, Ruby (<- includes the regression that motivated this PR), JavaScript all look good.

We flag slightly different results, which is expected, we go back to the resutls we had before #12628.

@erik-krogh erik-krogh marked this pull request as ready for review May 24, 2023 17:26
@erik-krogh erik-krogh requested review from a team as code owners May 24, 2023 17:26
@erik-krogh erik-krogh requested a review from a team May 24, 2023 17:26
@aschackmull
Copy link
Contributor

This affect Java as well, right?

@erik-krogh
Copy link
Contributor Author

erik-krogh commented May 25, 2023

This affect Java as well, right?

Oh, yes, that's right.
I'll run the tests locally to see if they pass.

Edit: The Java tests are fine, I'll request review from the team.

@erik-krogh erik-krogh requested a review from a team May 25, 2023 10:14
@yoff
Copy link
Contributor

yoff commented May 25, 2023

Was CI not run for Python?

@erik-krogh
Copy link
Contributor Author

Was CI not run for Python?

Because no file in the python/ folder was touched.
I've run the tests locally, and everything is fine.
You can add the shared/ folder as a path that triggers the Python CI if you want.

@yoff
Copy link
Contributor

yoff commented May 25, 2023

Was CI not run for Python?

Because no file in the python/ folder was touched.

I see.

I've run the tests locally, and everything is fine.

Cool

You can add the shared/ folder as a path that triggers the Python CI if you want.

I do want that :-)

@aschackmull
Copy link
Contributor

You can add the shared/ folder as a path that triggers the Python CI if you want.

That ought to be fixed for all languages. Otherwise main will be broken by accident very soon.

Copy link
Contributor

@yoff yoff left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@erik-krogh
Copy link
Contributor Author

erik-krogh commented May 25, 2023

That ought to be fixed for all languages. Otherwise main will be broken by accident very soon.

Every language has some implementation in shared/ now,. So yes, it's probably a good idea.

That ought to be fixed for all languages. Otherwise main will be broken by accident very soon.

I know how to do it for the CI workflows defined in github/codeql.
But I don't know how to do it for the internal CI jobs (Python is one of those).
@yoff: do you have experience with the internal CI jobs? Otherwise can you delegate to someone that does?

Edit: Looks like internal DX is on it, see below.

@aschackmull
Copy link
Contributor

See also https://github.com/github/code-scanning-internal-dx-team/issues/87

@asgerf
Copy link
Contributor

asgerf commented Jun 2, 2023

@erik-krogh is anything blocking us from merging this? The above discussion about CI checks doesn't seem like it should block this particular PR.

@erik-krogh
Copy link
Contributor Author

@erik-krogh is anything blocking us from merging this? The above discussion about CI checks doesn't seem like it should block this particular PR.

No. I'll merge.

@erik-krogh erik-krogh merged commit 219ec9d into github:main Jun 2, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants