CWE-1333
Inefficient Regular Expression Complexity
2021-03-15
00h00 +00:00
00h00 +00:00
特定のCWEの通知
特定のCWEの変更情報をいち早くお届けします。
名前: Inefficient Regular Expression Complexity
The product uses a regular expression with a worst-case computational complexity that is inefficient and possibly exponential.
一般情報
背景の詳細
導入モード
Implementation : A RegEx can be easy to create and read using unbounded matching characters, but the programmer might not consider the risk of excessive backtracking.Implementation : Backtracking becomes a weakness if all of these conditions are met:
適用可能なプラットフォーム
言語
クラス： Not Language-Specific (Undetermined)名前： Go (Undetermined)
一般的な結果
| スコープ | 影響 | 可能性 |
|---|---|---|
| Availability | DoS: Resource Consumption (CPU) 注記：Attackers can create crafted inputs that intentionally cause the regular expression to use excessive backtracking in a way that causes the CPU consumption to spike. | High |
観察された例
| 参考文献 | 説明 |
|---|---|
CVE-2020-5243 | server allows ReDOS with crafted User-Agent strings, due to overlapping capture groups that cause excessive backtracking. |
CVE-2021-21317 | npm package for user-agent parser prone to ReDoS due to overlapping capture groups |
CVE-2019-16215 | Markdown parser uses inefficient regex when processing a message, allowing users to cause CPU consumption and delay preventing processing of other messages. |
CVE-2019-6785 | Long string in a version control product allows DoS due to an inefficient regex. |
CVE-2019-12041 | Javascript code allows ReDoS via a long string due to excessive backtracking. |
CVE-2015-8315 | ReDoS when parsing time. |
CVE-2015-8854 | ReDoS when parsing documents. |
CVE-2017-16021 | ReDoS when validating URL. |
潜在的な緩和策
Phases : Architecture and DesignUse regular expressions that do not support backtracking, e.g. by removing nested quantifiers.
Phases : System Configuration
Set backtracking limits in the configuration of the regular expression implementation, such as PHP's pcre.backtrack_limit. Also consider limits on execution time for the process.
Phases : Implementation
Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression.
Phases : Implementation
Limit the length of the input that the regular expression will process.
検出方法
Automated Static Analysis
Automated static analysis, commonly referred to as Static Application Security Testing (SAST), can find some instances of this weakness by analyzing source code (or binary/compiled code) without having to execute it. Typically, this is done by building a model of data flow and control flow, then searching for potentially-vulnerable patterns that connect "sources" (origins of input) with "sinks" (destinations where the data interacts with external components, a lower layer such as the OS, etc.)有効性 : High
脆弱性マッピングノート
理由 : This CWE entry is at the Base level of abstraction, which is a preferred level of abstraction for mapping to the root causes of vulnerabilities.コメント : Carefully read both the name and description to ensure that this mapping is an appropriate fit. Do not try to 'force' a mapping to a lower-level Base/Variant simply to comply with this preferred level of abstraction.
関連する攻撃パターン
| CAPEC ID | 攻撃パターン名 |
|---|---|
| CAPEC-492 | Regular Expression Exponential Blowup
An adversary may execute an attack on a program that uses a poor Regular Expression(Regex) implementation by choosing input that results in an extreme situation for the Regex. A typical extreme situation operates at exponential time compared to the input size. This is due to most implementations using a Nondeterministic Finite Automaton(NFA) state machine to be built by the Regex algorithm since NFA allows backtracking and thus more complex regular expressions. |
参考文献
REF-1180
Regular Expression Denial of ServiceScott A. Crosby.
https://web.archive.org/web/20031120114522/http://www.cs.rice.edu/~scrosby/hash/slides/USENIX-RegexpWIP.2.ppt
REF-1162
Runaway Regular Expressions: Catastrophic BacktrackingJan Goyvaerts.
https://www.regular-expressions.info/catastrophic.html
REF-1163
Regular expression Denial of Service - ReDoSAdar Weidman.
https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS
REF-1164
Catastrophic backtrackingIlya Kantor.
https://javascript.info/regexp-catastrophic-backtracking
REF-1165
Freezing the Web: A Study of ReDoS Vulnerabilities in JavaScript-based Web ServersCristian-Alexandru Staicu, Michael Pradel.
https://www.usenix.org/system/files/conference/usenixsecurity18/sec18-staicu.pdf
REF-1166
The Impact of Regular Expression Denial of Service (ReDoS) in Practice: An Empirical Study at the Ecosystem ScaleJames C. Davis, Christy A. Coghlan, Francisco Servant, Dongyoon Lee.
https://fservant.github.io/papers/Davis_Coghlan_Servant_Lee_ESECFSE18.pdf
REF-1167
The Regular Expression Denial of Service (ReDoS) cheat-sheetJames Davis.
https://levelup.gitconnected.com/the-regular-expression-denial-of-service-redos-cheat-sheet-a78d0ed7d865
REF-1566
Golang Secure Coding Practices guideOWASP.
https://github.com/OWASP/Go-SCP
登録情報
| 名前 | 組織 | 日付 | リリース日 | Version |
|---|---|---|---|---|
| Anonymous External Contributor | 4.4 |
変更履歴
| 名前 | 組織 | 日付 | コメント |
|---|---|---|---|
| CWE Content Team | MITRE | updated References | |
| CWE Content Team | MITRE | updated Description | |
| CWE Content Team | MITRE | updated Observed_Examples, Potential_Mitigations | |
| CWE Content Team | MITRE | updated Observed_Examples, Relationships | |
| CWE Content Team | MITRE | updated Demonstrative_Examples, Observed_Examples | |
| CWE Content Team | MITRE | updated References, Relationships | |
| CWE Content Team | MITRE | updated Mapping_Notes | |
| CWE Content Team | MITRE | updated Detection_Factors, Weakness_Ordinalities | |
| CWE Content Team | MITRE | updated Background_Details, Common_Consequences, Description, Diagram, Modes_of_Introduction | |
| CWE Content Team | MITRE | updated Applicable_Platforms, References, Relationships, Taxonomy_Mappings |
