Regular Expression Denial Of Service issue in deploy slash command

Summary

I wasn't able to successfully get the slack command integration to work locally (see https://gitlab.slack.com/archives/CK4Q4709G/p1635809660009400) but I'm opening this issue anyway because the fix is simple and at this point fixing the issue is going to be more efficient than continuing to spend time on the repro.

The regular expression in https://gitlab.com/gitlab-org/gitlab/-/blob/734ddb6fcbdc541df1dff9d1ba1856ddc4c89bba/lib/gitlab/slash_commands/deploy.rb#L7 is vulnerable to a regular expression denial of service (ReDoS) attack which causes very high CPU consumption and availability issues.

Steps to reproduce

We can see the growth of the execution time here

$ time ruby -e '/\Adeploy\s+(?<from>\S+.*)\s+to+\s+(?<to>\S+.*)\z/.match("deploy a to " + "b" * 10000 + "\n")'
ruby -e   0.45s user 0.17s system 107% cpu 0.579 total
$ time ruby -e '/\Adeploy\s+(?<from>\S+.*)\s+to+\s+(?<to>\S+.*)\z/.match("deploy a to " + "b" * 20000 + "\n")'
ruby -e   1.41s user 0.18s system 102% cpu 1.554 total
$ time ruby -e '/\Adeploy\s+(?<from>\S+.*)\s+to+\s+(?<to>\S+.*)\z/.match("deploy a to " + "b" * 40000 + "\n")'
ruby -e   5.46s user 0.20s system 100% cpu 5.643 total
$ time ruby -e '/\Adeploy\s+(?<from>\S+.*)\s+to+\s+(?<to>\S+.*)\z/.match("deploy a to " + "b" * 80000 + "\n")'
ruby -e   21.40s user 0.30s system 99% cpu 21.745 total

String length growth	Execution time growth
2x	3x
4x	12x
8x	48x

I think a request that looks like this would do it, but I couldn't ever setup the ChatNames properly to have my requests authenticated.

curl http://gitlab.local:3000/api/v4/projects/2/services/slack_slash_commands/trigger -H "Private-Token: $GITLAB_PAT" -H 'Content-Type: application/json' --data '{"token": "slack_token", "text": "payload here"}'

I think it's easier to repro with a GitLab Slack Application but I didn't test that not to impact prod. The bug has to be exploited through the API though and I don't think it would work directly from Slack because it needs a newline character to trigger the bug and I don't think Slack would include that in the command.

Example Project

What is the current bug behavior?

Regular expression vulnerable to ReDoS and causes excessive consumption of resources

What is the expected correct behavior?

Regular expression should execute in linear time or better.

Relevant logs and/or screenshots

Output of checks

Results of GitLab environment info

Expand for output related to GitLab environment info

(For installations with omnibus-gitlab package run and paste the output of:
`sudo gitlab-rake gitlab:env:info`)

(For installations from source run and paste the output of:
`sudo -u git -H bundle exec rake gitlab:env:info RAILS_ENV=production`)

Results of GitLab application Check

Expand for output related to the GitLab application check

(For installations with omnibus-gitlab package run and paste the output of:
sudo gitlab-rake gitlab:check SANITIZE=true)
(For installations from source run and paste the output of:
sudo -u git -H bundle exec rake gitlab:check RAILS_ENV=production SANITIZE=true)
(we will only investigate if the tests are passing)

Possible fixes

diff --git a/lib/gitlab/slash_commands/deploy.rb b/lib/gitlab/slash_commands/deploy.rb
index 157d924f99f..5a23f7ecb03 100644
--- a/lib/gitlab/slash_commands/deploy.rb
+++ b/lib/gitlab/slash_commands/deploy.rb
@@ -4,7 +4,7 @@ module Gitlab
   module SlashCommands
     class Deploy < BaseCommand
       def self.match(text)
-        /\Adeploy\s+(?<from>\S+.*)\s+to+\s+(?<to>\S+.*)\z/.match(text)
+        /\Adeploy\s+(?<from>\S.*)\s+to+\s+(?<to>\S.*)\z/.match(text)
       end
 
       def self.help_message