Semgrep: RFC: Add primitive for mathematical comparisons of metavariable

[mschwager]

In an attempt to further reduce our reliance on pattern-where-python, I'd like to propose adding a new primitive for performing basic mathematical comparisons on metavariables. First let's look at how pattern-where-python is used in semgrep-rules:

Semgrep rules examples

$ rg 'pattern\-where\-python' -A 5
contrib/dlint/redos.yaml
6:  - pattern-where-python: |
7-      # COPIED FROM https://github.com/dlint-py/dlint/blob/master/dlint/redos/detect.py
8-
9-      import sre_constants
10-      import sre_parse
11-

go/gorilla/security/audit/handler-attribute-read-from-multiple-sources.yaml
41:  - pattern-where-python: vars['$KEY'].strip('"') == vars['$ATT']
42-  message: "Attribute $ATT is read from two different sources: '$X[$KEY]' and '$Y.$ATT'. Make sure this is intended, as this\
43-    \ could cause logic bugs if they are treated as if they are the same object."
44-  languages: [go]
45-  severity: WARNING

java/lang/security/audit/crypto/weak-rsa.yaml
17:  - pattern-where-python: |-
18-      int(vars['$BITS']) < 2048

go/lang/correctness/overflow/overflow.yaml
11:  - pattern-where-python: int(vars['$NUM'].replace('"', '')) > 32767 or int(vars['$NUM'].replace('"', '')) < -32768
12-- id: interter-overflow-int32
13-  message: Potential Integer overflow made by strconv.Atoi result conversion to int32
14-  languages: [go]
15-  severity: WARNING
16-  patterns:
--
21:  - pattern-where-python: |-
22-      int(vars['$NUM'].replace('"', '')) > 2147483647 or int(vars['$NUM'].replace('"', '')) < -2147483648

go/lang/correctness/permissions/file_permission.yaml
12:  - pattern-where-python: |
13-      int(vars['$PERM'], 8) > 0o600
14-- id: incorrect-default-permission
15-  message: Expect permissions to be `0600` or less for ioutil.WriteFile()
16-  metadata:
17-    cwe: 'CWE-276: Incorrect Default Permissions'
--
24:  - pattern-where-python: |
25-      int(vars['$PERM'], 8) > 0o600
26-- id: incorrect-default-permission
27-  message: Expect permissions to be `0600` or less for ioutil.WriteFile()
28-  metadata:
29-    cwe: 'CWE-276: Incorrect Default Permissions'
--
36:  - pattern-where-python: |
37-      int(vars['$PERM'], 8) > 0o600
38-- id: incorrect-default-permission
39-  message: Expect permissions to be `0600` or less for ioutil.WriteFile()
40-  metadata:
41-    cwe: 'CWE-276: Incorrect Default Permissions'
--
48:  - pattern-where-python: |
49-      int(vars['$PERM'], 8) > 0o600
50-- id: incorrect-default-permission
51-  message: Expect permissions to be `0600` or less for ioutil.WriteFile()
52-  metadata:
53-    cwe: 'CWE-276: Incorrect Default Permissions'
--
60:  - pattern-where-python: |-
61-      int(vars['$PERM'], 8) > 0o600

go/lang/security/audit/crypto/use_of_weak_rsa_key.yaml
18:  - pattern-where-python: |-
19-      int(vars['$BITS']) < 2048

python/cryptography/security/insufficient-rsa-key-size.yaml
7:  - pattern-where-python: |
8-      alert = False
9-      try:
10-        alert = int(vars['$SIZE']) < 2048
11-      except:
12-        alert = False

java/lang/security/audit/blowfish-insufficient-key-size.yaml
18:  - pattern-where-python: |-
19-      int(vars['$SIZE']) < 128

python/pycryptodome/security/insufficient-dsa-key-size.yaml
9:  - pattern-where-python: |
10-      alert = False
11-      try:
12-        alert = int(vars['$SIZE']) < 2048
13-      except:
14-        alert = False

python/pycryptodome/security/insufficient-rsa-key-size.yaml
9:  - pattern-where-python: |
10-      alert = False
11-      try:
12-        alert = int(vars['$SIZE']) < 2048
13-      except:
14-        alert = False

python/cryptography/security/insufficient-dsa-key-size.yaml
7:  - pattern-where-python: |
8-      alert = False
9-      try:
10-        alert = int(vars['$SIZE']) < 2048
11-      except:
12-        alert = False

python/flask/experimental/correctness/different-route-names.yaml
25:  - pattern-where-python: |-
26-      set([part.split(":")[-1].lstrip("<").rstrip(">") for part in vars["$PATH"].replace('"', "").replace("'", "").split("/") if part.startswith("<") and part.endswith(">")]) != set([v for k, v in vars.items() if k.startswith("$A")])
27-  message: The view function arguments `$PATH` to `$R` don't match the path defined in @app.route($PATH)
28-  languages: [python]
29-  severity: WARNING

python/lang/security/audit/insecure-file-permissions.yaml
8:  - pattern-where-python: |-
9-      import stat
10-
11-      def stat_to_bits(mode):
12-        bits = 0
13-        for flag in mode.split('|'):

We can see most of the rules are performing simple mathematical comparisons. E.g. < 2048, > 0o600, > 32767, etc. Instead of relying on pattern-where-python in this situation, and thus --dangerously-allow-arbitrary-code-execution-from-rules, we should provide a safer, more ergonomic alternative.

I'd like to purpose another operator similar to metavariable-regex. For now let's call this operator metavariable-comparison with the understanding that this name could change during implementation. An example of this operator would look like:

metavariable-comparison:
    metavariable: '$SIZE'
    comparison: '< 2048'

The more general form would be:

metavariable-comparison:
    metavariable: '<METAVARIABLE_NAME>'
    comparison: '<COMPARISON_OPERATOR> <COMPARISON_VALUE>'

These correspond to:

• METAVARIABLE_NAME: a metavariable integer value returned from a pattern. Must be an integer value. Validated with int().
• COMPARISON_OPERATOR: an object comparison operator taken from operator. Note the only object type considered is int.
• COMPARISON_VALUE: an integer value to be compared against.

One of the primary motivators here is a safer alternative to pattern-where-python. So how can we ensure we're safely evaluating the comparison expression? I found a useful StackOverflow post that can help shape our thoughts here: Evaluating a mathematical expression in a string. Especially this answer.

In short, we can implement a custom evaluator that only operates on a very limited subset of possible inputs. Here's a more thorough listing of defenses:

• The metavariable value in METAVARIABLE_NAME is an integer. Confirmed by passing to int() and ensuring no ValueError.
• Limit our supported operators to integer comparison operators.
  
  
  
  • Note we're removing mathematical operators like addition and exponentiation to avoid DoS by large math operations.
  
  
• We will place the metavariable value from METAVARIABLE_NAME into the comparison string like f"metavariables[metavariable-comparison['metavariable']] metavariable-comparison['comparison'].
  
  
  
  • So $SIZE=42 and < 2048 will become 42 < 2048.
  
  
  • We will limit the characters of the resulting expression to numbers, spaces, and comparison operators.
  
  
• Limit the overall string length of the expression to some reasonable value, e.g. 64. This avoids any potential for integer comparison DoS.
• We will then evaluate the expression using our custom evaluator.
  
  
  
  • The evaluator only operates on supported AST node types: numbers, unary operators, and binary comparison operators.
  
  

Failure here means arbitrary code execution, so we need to get this right. Are there any defenses I'm missing? Does this fail under certain malicious inputs? This defeats obvious malicious attempts like:

• "__import__('os').remove('important file')"
• "(1).__class__.__bases__[0].__subclasses__()"

Other potentially useful flags for this operator:

metavariable-comparison:
    metavariable: '$SIZE'
    comparison: '< 2048'
    strip: true|false
    base: int

• The strip flag could be used to remove quotes from the metavariable value returned.
  
  
  
  • This is useful if we find integers in a string and would still like to process them.
  
  
  • E.g. the Golang overflow rule uses this.
  
  
• The base flag would be another integer passed to the int() base keyword argument.
  
  
  
  • This would allow for different bases to be utilized.
  
  

Things out of scope for now, but considered for future extensibility:

• Operations on float's, not just int's. I don't see a need for this yet based on existing Semgrep rules.
• Operations on str's - use metavariable-regex.
• Multiple comparisons, e.g. 42 < $SIZE < 2048. This can be achieved with a pattern-either operation.

[brendongo]

Something to think about but might be out of scope: comparing two metavariables to enforce something like $X < $Y

[mschwager]

After thinking about this a bit more, since we're using such a restricted input set we could use simple string parsing to identify the operation. E.g. a regex like (<|<=|>|>=|==|!=) ?-?\d+ should be sufficient. Then find the correct operator, convert the number strings to integers, and perform the comparison. No need for more complicated implementations like AST evaluation.

[aryx]

Why not use pattern-where-python: and statically analyze when the python code is safe to execute.
You can parse the string (there's a builtin Python parser in Python), and when the AST is a simple expression, just evaluate it.
Otherwise each time we will need to add yet another metavariable-xxx: special name.

[ievans]

+1 to what @aryx said, though my suggestion would be to write a minimal valid python-subset intepreter that doesn't have enough power to exec arbitrary code but can perform all the ops we care about, rather than encoding it as part of the YAML syntax. Or just use one someone else already wrote. E.g. https://deno.land/

[clintgibler]

Thanks for the great write-up @mschwager! 🙏

I do like the idea of limiting use of pattern-where-python by providing safer primitives, but I also see @aryx and @ievans's trade-offs about not bloating the pattern language.

Only evaluating simple expressions seems "safe," (assuming we do it right), but I'm a little concerned about our ability to correctly enforce the safety properties we intend given arbitrary hacker input creativity.

Proposed solution:

1. The live editor never runs pattern-where-python.
   
   
   
   • Currently we allow some whitelisted rules, but to be safer, might be better to not allow it all. Users can test locally if they want to use pattern-where-python.
   
   
2. pattern-where-python clauses that are strictly simple expressions (no imports, maybe limited function calls, etc) are allowed without a --dangerously-allow-arbitrary-code-execution-from-rules flag.
3. If you want arbitrary Python functionality, you must use that flag.
4. Even given the flag, Semgrep by default does not run any rules that include pattern-where-python (perhaps unless they're ones published in semgrep-rules?).
   
   
   
   • Users must whitelist via CLI, project config, or policy which rules with pattern-where-python are allowed.
   
   
   • v0 this can be by name, v1 this should be a hash of the rule to detect changes over time which need to be re-approved.
   
   

If we were to add metavariable-comparison, I would encourage us to split the operator into a separate key, like:

metavariable-comparison:
    metavariable: '$SIZE'
    operator: '<'
    compared_value: '2048'
    strip: true|false
    base: int

[mschwager]

Why not use pattern-where-python: and statically analyze when the python code is safe to execute.

How do we know when it's safe to execute? What about "__import__('os').remove('important file')" and "(1).__class__.__bases__[0].__subclasses__()"? These are just the easy ones. What about 'f"{().__class__.__base__}"' or "f\"{eval('()' + chr(46) + '__class__')}\""? That's just a string to the interpreter. What about this monstrosity? What about all the potential things we don't know about? The dynamic nature of Python makes this list very hard to enumerate. What about all possible avenues in future Python versions? From that SO post:

This really highlights how much of a moving target trying to secure eval is. Right now, it's f-strings. Who knows what 3.7 will bring?

My point is that this is difficult to _get_ right, and _keep_ right. We should also consider that this is high risk, low reward. We currently have 13 / 541 = 2.4% of our rules using pattern-where-python, and 9 / 13 of those are doing a simple integer comparison. So we don't really have a need for a more powerful, safer pattern-where-python, yet. On the other hand, if we mess up our safe evaluator implementation then that's remote code execution.

If we were to add metavariable-comparison, I would encourage us to split the operator into a separate key ...

Nice! This interface is much better.

[aryx]

I didnt say to run eval. I said that we could parse the string with the python parser, you get an AST and then you write a simple interpreter allowing only simple constructs (literals, variables, arith operator). What about the monstrosity you mentioned? Easy, they are complex AST constructs not allowed by our interpreter.

[disconnect3d]

Hey,

I think I have a possible answer for you regarding safe execution of Python expressions, though I haven't read the whole topic, so please forgive me if my reply is not applicable.

Why not use pattern-where-python: and statically analyze when the python code is safe to execute.

How do we know when it's safe to execute?

Assuming that we only want "simple expressions" and not e.g. allowing of using functions, we can compile the input expression via Python's compile function, parse the resulting code object into AST and walk through the tree to ensure it only contains a whitelisted set of nodes: ones that allow the use of simple mathematical expressions.

And... there is already a library for that. The pwnlib.safeeval: https://docs.pwntools.com/en/stable/util/safeeval.html does exactly that.

The downside to this is that Python's opcodes may differ between versions and such library may need to be synced between Python versions. However, opcode changes do not occur that frequently.

In case someone is not familiar with the described concepts, back then when pwntools was only Py2 I made a livestream where I ported most (or all) of its safeeval module to Python3 (though, I never send a PR with it): https://www.youtube.com/watch?v=89YXEi-ZYWE