github / github/codeql

LGTM.com - false positive - polynomial-redos

Abierto
#6,525 5 comentarios 0 reacciones 0 asignados Ver en GitHub
false-positive JS
Lenguaje dominante
CodeQL
Estrellas
10.1k
Forks
2.1k
Merge medio
2 d 15 h
PR fusionados (30 d)
141

Descripción

**Description of the false positive**

https://lgtm.com/projects/g/ExodusMovement/schemasafe/snapshot/5d16dfc8e862db856e8bef5c5f92845546eb6c05/files/src/pointer.js?sort=name&dir=ASC&mode=heatmap#x42c7ec6a02df0e9e:1

> This regular expression that depends on library input may run slow on strings with many repetitions of '.'.

I don't think that `/\/?[^/]*$/` has a polynomial ReDoS.

The actual regex pattern is `/?[^/]*$`.

1) The first part has length limited to 1 (i.e. 0 or 1 repetitions).

2) The first and the second parts don't have common allowed symbols (the first allows only `/`, the second doesn't allow `/`), so there should be no polynomial redos possible here, even if the first part would have allowed more repetitions.

Any of these two would suffice alone to make it not a ReDoS.

---

Also https://github.com/NicolaasWeideman/RegexStaticAnalysis returns this:
```
pattern = "/?[^/]*$"
NFA constructed in: 5ms
EDA analysis performed in: 15ms
Does not contain EDA
IDA analysis performed in: 37ms
Does not contain IDA
```

Unlike, for example, `x*[^/]*$` which does not satisfy any of (1) and (2) above and has a polynomial ReDoS (IDA):
```
pattern = "x*[^/]*$"
NFA constructed in: 2ms
EDA analysis performed in: 4ms
Does not contain EDA
IDA analysis performed in: 133ms
Contains IDA, degree 1, with: xxx...xx/
IDA exploit string as JSON: {"degree":1,"separators":["x"],"pumps":["xx"],"suffix":"/"}
Prefix: "x"
Pump 0: "xx"
Suffix: "/"
```

Note that Weideman's tool analysis typically has to be rechecked because of differences in regex engines. And some patterns are not analyzable by it and require preparation.

Also refs: https://github.com/github/codeql/issues/2804#issuecomment-715554498

Guía de contribución

Abrir la guía de contribución

Evaluación

Este issue todavía no se ha evaluado.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.