{"@ID": "1333", "@Name": "Inefficient Regular Expression Complexity", "@Abstraction": "Base", "@Structure": "Simple", "@Status": "Draft", "@Diagram": "/data/images/CWE-1333-Diagram.png", "Description": "The product uses a regular expression with a worst-case computational complexity that is inefficient and possibly exponential.", "Related_Weaknesses": {"Related_Weakness": [{"@Nature": "ChildOf", "@CWE_ID": "407", "@View_ID": "1000", "@Ordinal": "Primary"}, {"@Nature": "ChildOf", "@CWE_ID": "407", "@View_ID": "1003", "@Ordinal": "Primary"}]}, "Weakness_Ordinalities": {"Weakness_Ordinality": {"Ordinality": "Primary"}}, "Applicable_Platforms": {"Language": {"@Class": "Not Language-Specific", "@Prevalence": "Undetermined"}}, "Background_Details": {"Background_Detail": "Some regular expression engines have a feature called \"backtracking\". If the token cannot match, the engine \"backtracks\" to a position that may result in a different token that can match."}, "Alternate_Terms": {"Alternate_Term": [{"Term": "ReDoS", "Description": "ReDoS is an abbreviation of \"Regular expression Denial of Service\"."}, {"Term": "Regular Expression Denial of Service", "Description": "While this term is attack-focused, this is commonly used to describe the weakness."}, {"Term": "Catastrophic backtracking", "Description": "This term is used to describe the behavior of the regular expression as a negative technical impact."}]}, "Modes_Of_Introduction": {"Introduction": [{"Phase": "Implementation", "Note": "A RegEx can be easy to create and read using unbounded matching characters, but the programmer might not consider the risk of  excessive backtracking."}, {"Phase": "Implementation", "Note": {"xhtml:p": null, "xhtml:ul": {"xhtml:li": ["The number of possible backtracking attempts is exponential relative to the length of the input.", "The input can fail to match the regular expression.", "The input can be long enough."]}, "#text": "Backtracking becomes a weakness if all of these conditions are met:"}}]}, "Likelihood_Of_Exploit": "High", "Common_Consequences": {"Consequence": {"Scope": "Availability", "Impact": "DoS: Resource Consumption (CPU)", "Likelihood": "High", "Note": "Attackers can create crafted inputs that\n\t\t    intentionally cause the regular expression to use\n\t\t    excessive backtracking in a way that causes the\n\t\t    CPU consumption to spike."}}, "Detection_Methods": {"Detection_Method": {"@Detection_Method_ID": "DM-14", "Method": "Automated Static Analysis", "Description": "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.)", "Effectiveness": "High"}}, "Potential_Mitigations": {"Mitigation": [{"Phase": "Architecture and Design", "Description": "Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.", "Effectiveness": "High", "Effectiveness_Notes": "This is one of the few effective solutions when using user-provided regular expressions."}, {"Phase": "System Configuration", "Description": "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.", "Effectiveness": "Moderate"}, {"Phase": "Implementation", "Description": "Do not use regular expressions with untrusted input. If regular expressions must be used, avoid using backtracking in the expression.", "Effectiveness": "High"}, {"Phase": "Implementation", "Description": "Limit the length of the input that the regular expression will process.", "Effectiveness": "Moderate"}]}, "Demonstrative_Examples": {"Demonstrative_Example": [{"@Demonstrative_Example_ID": "DX-158", "Intro_Text": "This example attempts to check if an input string is a \"sentence\" [REF-1164].", "Example_Code": [{"@Nature": "Bad", "@Language": "JavaScript", "xhtml:br": [null, null], "#text": "var test_string = \"Bad characters: $@#\";\n                        var bad_pattern  = /^(\\w+\\s?)*$/i;\n                        var result = test_string.search(bad_pattern);"}, {"@Nature": "Good", "@Language": "JavaScript", "xhtml:br": [null, null], "#text": "var test_string = \"Bad characters: $@#\";\n                        var good_pattern  = /^((?=(\\w+))\\2\\s?)*$/i;\n                        var result = test_string.search(good_pattern);"}], "Body_Text": [{"xhtml:p": ["The regular expression has a vulnerable backtracking clause inside (\\w+\\s?)*$ which can be triggered to cause a Denial of Service by processing particular phrases.", "To fix the backtracking problem, backtracking is removed with the ?= portion of the expression which changes it to a lookahead and the \\2 which prevents the backtracking. The modified example is:"]}, "Note that [REF-1164] has a more thorough (and lengthy) explanation of everything going on within the RegEx."]}, {"Intro_Text": "This example attempts to check if an input string is a \"sentence\" and is modified for Perl [REF-1164].", "Example_Code": [{"@Nature": "Bad", "@Language": "Perl", "xhtml:br": [null, null], "#text": "my $test_string = \"Bad characters: \\$\\@\\#\";\n                        my $bdrslt = $test_string;\n                        $bdrslt =~ /^(\\w+\\s?)*$/i;"}, {"@Nature": "Good", "@Language": "Perl", "xhtml:br": [null, null], "#text": "my $test_string = \"Bad characters: \\$\\@\\#\";\n                        my $gdrslt = $test_string;\n                         $gdrslt =~ /^((?=(\\w+))\\2\\s?)*$/i;"}], "Body_Text": [{"xhtml:p": ["The regular expression has a vulnerable backtracking clause inside (\\w+\\s?)*$ which can be triggered to cause a Denial of Service by processing particular phrases.", "To fix the backtracking problem, backtracking is removed with the ?= portion of the expression which changes it to a lookahead and the \\2 which prevents the backtracking. The modified example is:"]}, "Note that [REF-1164] has a more thorough (and lengthy) explanation of everything going on within the RegEx."]}]}, "Observed_Examples": {"Observed_Example": [{"Reference": "CVE-2020-5243", "Description": "server allows ReDOS with crafted User-Agent strings, due to overlapping capture groups that cause excessive backtracking.", "Link": "https://www.cve.org/CVERecord?id=CVE-2020-5243"}, {"Reference": "CVE-2021-21317", "Description": "npm package for user-agent parser prone to ReDoS due to overlapping capture groups", "Link": "https://www.cve.org/CVERecord?id=CVE-2021-21317"}, {"Reference": "CVE-2019-16215", "Description": "Markdown parser uses inefficient regex when processing a message, allowing users to cause CPU consumption and delay preventing processing of other messages.", "Link": "https://www.cve.org/CVERecord?id=CVE-2019-16215"}, {"Reference": "CVE-2019-6785", "Description": "Long string in a version control product allows DoS due to an inefficient regex.", "Link": "https://www.cve.org/CVERecord?id=CVE-2019-6785"}, {"Reference": "CVE-2019-12041", "Description": "Javascript code allows ReDoS via a long string due to excessive backtracking.", "Link": "https://www.cve.org/CVERecord?id=CVE-2019-12041"}, {"Reference": "CVE-2015-8315", "Description": "ReDoS when parsing time.", "Link": "https://www.cve.org/CVERecord?id=CVE-2015-8315"}, {"Reference": "CVE-2015-8854", "Description": "ReDoS when parsing documents.", "Link": "https://www.cve.org/CVERecord?id=CVE-2015-8854"}, {"Reference": "CVE-2017-16021", "Description": "ReDoS when validating URL.", "Link": "https://www.cve.org/CVERecord?id=CVE-2017-16021"}]}, "Related_Attack_Patterns": {"Related_Attack_Pattern": {"@CAPEC_ID": "492"}}, "References": {"Reference": [{"@External_Reference_ID": "REF-1180"}, {"@External_Reference_ID": "REF-1162"}, {"@External_Reference_ID": "REF-1163"}, {"@External_Reference_ID": "REF-1164"}, {"@External_Reference_ID": "REF-1165"}, {"@External_Reference_ID": "REF-1166"}, {"@External_Reference_ID": "REF-1167"}]}, "Mapping_Notes": {"Usage": "Allowed", "Rationale": "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.", "Comments": "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.", "Reasons": {"Reason": {"@Type": "Acceptable-Use"}}}, "Content_History": {"Submission": {"Submission_Name": "Anonymous External Contributor", "Submission_Date": "2021-01-17", "Submission_Version": "4.4", "Submission_ReleaseDate": "2021-03-15"}, "Modification": [{"Modification_Name": "CWE Content Team", "Modification_Organization": "MITRE", "Modification_Date": "2021-07-20", "Modification_Version": "4.5", "Modification_ReleaseDate": "2021-07-20", "Modification_Comment": "updated References"}, {"Modification_Name": "CWE Content Team", "Modification_Organization": "MITRE", "Modification_Date": "2021-10-28", "Modification_Version": "4.6", "Modification_ReleaseDate": "2021-10-28", "Modification_Comment": "updated Description"}, {"Modification_Name": "CWE Content Team", "Modification_Organization": "MITRE", "Modification_Date": "2022-04-28", "Modification_Version": "4.7", "Modification_ReleaseDate": "2022-04-28", "Modification_Comment": "updated Observed_Examples, Potential_Mitigations"}, {"Modification_Name": "CWE Content Team", "Modification_Organization": "MITRE", "Modification_Date": "2022-10-13", "Modification_Version": "4.9", "Modification_ReleaseDate": "2022-10-13", "Modification_Comment": "updated Observed_Examples, Relationships"}, {"Modification_Name": "CWE Content Team", "Modification_Organization": "MITRE", "Modification_Date": "2023-01-31", "Modification_Version": "4.10", "Modification_ReleaseDate": "2023-01-31", "Modification_Comment": "updated Demonstrative_Examples, Observed_Examples"}, {"Modification_Name": "CWE Content Team", "Modification_Organization": "MITRE", "Modification_Date": "2023-04-27", "Modification_Version": "4.11", "Modification_ReleaseDate": "2023-04-27", "Modification_Comment": "updated References, Relationships"}, {"Modification_Name": "CWE Content Team", "Modification_Organization": "MITRE", "Modification_Date": "2023-06-29", "Modification_Version": "4.12", "Modification_ReleaseDate": "2023-06-29", "Modification_Comment": "updated Mapping_Notes"}, {"Modification_Name": "CWE Content Team", "Modification_Organization": "MITRE", "Modification_Date": "2025-12-11", "Modification_Version": "4.19", "Modification_ReleaseDate": "2025-12-11", "Modification_Comment": "updated Detection_Factors, Weakness_Ordinalities"}, {"Modification_Name": "CWE Content Team", "Modification_Organization": "MITRE", "Modification_Date": "2026-04-30", "Modification_Version": "4.20", "Modification_ReleaseDate": "2026-04-30", "Modification_Comment": "updated Background_Details, Common_Consequences, Description, Diagram, Modes_of_Introduction"}]}}