Regular expression catastrophic backtracking in Git URL parsing

[mschwager]

• I am on the latest Poetry version.
• I have searched the issues of this repo and believe that this is not a duplicate.
• If an exception occurs when executing a command, I executed it again in debug mode (-vvv option).

• OS version and name: Linux 4.15.0-74-generic x86_64 GNU/Linux
• Poetry version: Github master
• Link of a Gist with the contents of your pyproject.toml file: N/A

Issue

Hi there! I've been working on a new Python static analysis tool called Dlint. Most recently I've been working on a rule that searches for regular expression denial-of-service: DUO138. When running this rule against your codebase I found a few violations:

$ python -m flake8 --select=DUO138 poetry
poetry/vcs/git.py:22:5: DUO138 catastrophic "re" usage - denial-of-service possible
poetry/vcs/git.py:33:5: DUO138 catastrophic "re" usage - denial-of-service possible
poetry/version/version.py:14:19: DUO138 catastrophic "re" usage - denial-of-service possible

Note that DUO138 hasn't been released to PyPI yet, so if you want to run the rule yourself you'll have to install from Github: python -m pip install https://github.com/dlint-py/dlint/tarball/master.

After further investigation, it appears the violations in poetry/vcs/git.py are true positives, and the violation in poetry/version/version.py is a false positive.

If we dig into the Git parsing violations:

re.compile(
    r"^(git\+)?"
    r"(?P<protocol>https?|git|ssh|rsync|file)://"
    r"(?:(?P<user>.+)@)*"
    r"(?P<resource>[a-z0-9_.-]*)"
    r"(:?P<port>[\d]+)?"
    r"(?P<pathname>[:/]((?P<owner>[\w\-]+)/(?P<projects>([\w\-/]+)/)?)?"
    r"((?P<name>[\w\-.]+?)(\.git|/)?)?)"
    r"([@#](?P<rev>[^@#]+))?"
    r"$"
),
re.compile(
    r"^(?:(?P<user>.+)@)*"
    r"(?P<resource>[a-z0-9_.-]*)[:]*"
    r"(?P<port>[\d]+)?"
    r"(?P<pathname>/?(?P<owner>.+)/(?P<projects>([\w\-/]+)/)?(?P<name>.+).git)"
    r"([@#](?P<rev>[^@#]+))?"
    r"$"
),

The violations occur due to r"(?:(?P<user>.+)@)*" in both expressions. This is due to nested quantifiers with overlapping character space. We can confirm the bugs with the following code:

from poetry.vcs import git
git.ParsedUrl.parse("https://" + "@" * 64 + "!")
...Spins...

from poetry.vcs import git
git.ParsedUrl.parse("@" * 64 + "!")
...Spins...

To fix the issue you should be able to change both violations to r"(?:(?P<user>[^@]+)@)*", which avoids the overlapping character space. Note that Dlint will still flag these lines due to nested quantifiers - these are false positives that are still being ironed out.

Hope this is helpful, let me know if you have any questions!

[finswimmer]

Hello @mschwager,

thanks a lot for pointing to this! 👍

Would this be fixed by changing it to r"^(?:(?P<user>\w+)@)*" like it is in the other regexes?

fin swimmer

[mschwager]

Yes, that should work! \w and @ don't overlap so there should be no ReDoS.

[github-actions]

This issue has been automatically locked since there has not been any recent activity after it was closed. Please open a new issue for related bugs.