Semgrep consume all of the CPU, Possible Regex DoS inside the engine.

[ajinabraham]

Describe the bug

Certain files and rules cause semgrep to consume all CPU and hangs the process.

To Reproduce
$ semgrep -f foo.yaml ~/Downloads/juice-shop-master/frontend/src/assets/private/three.js

File: https://github.com/bkimminich/juice-shop/blob/master/frontend/src/assets/private/three.js
Rule: foo.yaml

rules:
  - id: cpu_kill
    patterns:
      - pattern-either:
          - pattern: |
              var $PARSER = new libxmljs.SaxParser();
              ...
              $PARSER.parseString(..., <... $REQ.$QUERY ...>, ...);
          - pattern: |
              var $PARSER = new libxmljs.SaxParser();
              ...
              $PARSER.foo(...);
          - pattern: |
              var $PARSER = new libxmljs.SaxParser();
              ...
              $PARSER.bar(...);
          - pattern: |
              var $PARSER = new libxmljs.SaxParser();
              ...
              $PARSER.again(...);
          - pattern: |
              var $PARSER = new libxmljs.SaxParser();
              ...
              $PARSER.again(...);
          - pattern: |
              var $PARSER = new libxmljs.SaxParser();
              ...
              $PARSER.blaa(...);
          - pattern: |
              var $PARSER = new libxmljs.SaxParser();
              ...
              $PARSER.fo(...);
          - pattern: |
              var $PARSER = new libxmljs.SaxParser();
              ...
              $PARSER.ell(...);
          - pattern: |
              var $PARSER = new libxmljs.SaxParser();
              ...
              $PARSER.nothing(...);
          - pattern: |
              var $PARSER = new libxmljs.SaxParser();
              ...
              $PARSER.again(...);
          - pattern: |
              var $PARSER = new libxmljs.SaxParser();
              ...
              $PARSER.fance(...);
    message: CPU gone!
    languages:
      - javascript
    severity: ERROR

This issue is present with rules that have ellipsis ... used to match eveything in between, which makes me think that there is Regex dos happening inside semgrep core.

 - pattern: |
              var $PARSER = new libxmljs.SaxParser();
              ...
              $PARSER.fance(...);

Expected behavior
semgrep should have checks against this or timeout on the file if the analysis is taking more than X time.

Screenshots

Environment
semgrep 0.8.0 installed from PyPi

$ semgrep --version
0.8.0

[ajinabraham]

Forcefully killing throws

-c intercepted, will do some cleaning before exiting
[Parmap]: error at index j=3 in (10,14), chunksize=5 of a total of 5 got exception Common.UnixExit(-1) on core 2
an internal error occured while invoking the semgrep engine: unknown exception: Common.UnixExit(-1).
An error occurred while invoking the semgrep engine; please help us fix this by filing an an issue at https://semgrep.dev

[dlukeomalley]

@ajinabraham Thank you for filing this. Being sensitive to your project, on what timeline would you like to see a fix? We don't want to block you or your v4 rollout. Depending on how pressing this is, is it acceptable for us to investigate this next week?

[ajinabraham]

This is not blocking me as of now. This was reported by one of the early adopters of nodejsscan cli. For now he can scan the source by ignoring the problematic files.ajinabraham/njsscan#1

[aryx]

Yes it's probably because of the '...' which right now can be slow on huge files because of the
deep statement matching that is done implicitely (it basically tries to match on any sequence of statements where those sequences are the flatten list of all statements in a file, including in nested functions. We know this could be slow, I'm not sure though what to do for those. Maybe limit the depth of those sequences.

[ajinabraham]

Yeah it would be ideal to support a configurable depth parameter in semgrep API with a reasonable default.

[aryx]

no need for -depth parameter yet. The code I wrote was just terribly slow and was doing lots of useless work. With the small fix things seems more tractable.