Weakness (CWE)
CWE-407: Inefficient Algorithmic Complexity
An algorithm in a product has an inefficient worst-case computational complexity that may be detrimental to system performance and can be triggered by an attacker, typically using crafted manipulations that ensure that the worst case is being reached.
Source: MITRE CWE-407
307 results · Feed
-
High 8.7
Immutable.js: Hash-collision algorithmic complexity denial of service in Immutable.Map/Set
Immutable.js provides many Persistent Immutable data structures. Prior to 4.3.9 and 5.1.8, Immutable.Map and Immutable.Set keep keys that share the same 32-bit hash in a HashCollisionNode collision bucket that is scanned linearly, allowing an attacker who con…
-
Medium 5.3
js-yaml: YAML merge-key chains can force quadratic CPU consumption
js-yaml is a JavaScript YAML parser and dumper. From 5.0.0 before 5.2.0, when merge keys are enabled, js-yaml can spend quadratic CPU time parsing a document whose size grows only linearly when a chain of mappings uses merge keys where each mapping merges the…
-
High 7.5
js-yaml: YAML merge-key chains can force quadratic CPU consumption
js-yaml is a JavaScript YAML parser and dumper. From 3.0.0 before 3.15.0 and from 4.0.0 before 4.3.0, js-yaml can spend quadratic CPU time parsing a document whose size grows only linearly when a chain of mappings uses merge keys where each mapping merges the…
-
High 7.5
js-yaml quadratic-complexity denial of service via YAML11_SCHEMA !!omap parsing
js-yaml is a JavaScript YAML parser and dumper. Prior to 3.15.1, 4.3.1, and 5.2.1, YAML11_SCHEMA support for the !!omap tag in src/tag/sequence/omap.ts uses omapTag.addItem() to perform a linear duplicate-key scan on every insertion, causing O(n^2) CPU consum…
-
High 8.7
Unauthenticated denial-of-service via unbounded HPACK integer decoding in hpax
Inefficient Algorithmic Complexity vulnerability in elixir-mint hpax allows unauthenticated denial-of-service via unbounded HPACK integer decoding. hpax decodes HPACK variable-length integers with no upper bound on the decoded value or the number of continuat…
-
High 7.5
Pathway - Unauthenticated Denial of Service via Exponential Glob Pattern Matching in Document Store
Pathway through 0.31.1, fixed in commit d09722e, document store applies a caller-supplied glob pattern to indexed document paths using a hand-written recursive matcher that branches two ways on each ** token without memoization, giving exponential worst-case …
-
Medium 5.7
Denial of Service in fzf
fzf is vulnerable to a Denial of Service (DoS) due to inefficient HTTP body processing in the --listen mode due to inefficient HTTP body processing using repeated string concatenation, resulting in quadratic time complexity (O(n²)). A crafted POST request wit…
-
High 7.7
brace-expansion: DoS via exponential-time expansion of consecutive non-expanding {} groups
brace-expansion through 5.0.6 is vulnerable to denial of service. The expand() function exhibits exponential-time complexity in the number of consecutive non-expanding '{}' brace groups. An attacker who passes a crafted string to expand(), directly or transit…
-
Medium 6.6
decode-uri-component: Denial of service via exponential decoding of malformed percent-encoded input
decode-uri-component through 0.4.1 is vulnerable to denial of service. The decode() function splits input on '%' producing N tokens and calls decodeComponents(), exhibiting super-linear parsing time: 200 '%ab' tokens takes approximately 0.7s, 700 tokens appro…
-
High 7.5
shell-quote parse() is quadratic in token count, enabling denial of service
shell-quote prior to 1.8.5 finalizes parsed tokens in parse() using Array.prototype.concat as a reduce accumulator, which reallocates and copies the entire growing array on every iteration. As a result parse() runs in O(n^2) time relative to the number of inp…
-
High 8.7
Mistune: Potential DoS via quadratic-time parsing in parse_link_text
Mistune is a Python Markdown parser with renderers and plugins. Prior to 3.3.0, Mistune is vulnerable to a CPU exhaustion DoS due to superlinear (approximately O(n²)) behavior in parse_link_text. When parsing Markdown containing many consecutive [ characters,…
-
High 8.7
Plug: quadratic-time decoding of nested query/body parameters enables denial of service
Inefficient algorithmic complexity in Plug's nested-parameter decoder allows an unauthenticated remote attacker to cause denial of service. Plug.Conn.Query.decode/4 (and Plug.Conn.Query.decode_each/2) parse query strings and application/x-www-form-urlencoded …
-
High 8.2
MessagePack-CSharp: Denial of service vulnerabilities can swamp the CPU or crash the process with stack and heap overflows
MessagePack for C# is a MessagePack serializer for C#. Prior to 2.5.301 and 3.1.7, MessagePackReader.ReadDateTime() can allocate stack memory based on an attacker-controlled MessagePack extension length. In the slow path for timestamp extension parsing, the c…
-
Medium 6.3
MessagePack-CSharp: ExpandoObject formatter can perform quadratic insertion work on untrusted maps
MessagePack for C# is a MessagePack serializer for C#. Prior to 2.5.301 and 3.1.7, ExpandoObjectFormatter.Deserialize populates System.Dynamic.ExpandoObject by calling IDictionary<string, object>.Add for each map entry. ExpandoObject internally maintains memb…
-
Medium 6.3
MessagePack-CSharp: InterfaceLookupFormatter bypasses collision-resistant comparer settings
MessagePack for C# is a MessagePack serializer for C#. Prior to 2.5.301 and 3.1.7, InterfaceLookupFormatter<TKey,TElement> constructs an internal Dictionary<TKey, IGrouping<TKey,TElement>> with the default equality comparer instead of the security-aware compa…
-
Medium 5.1
pypdf: Inefficient decoding of FlateDecode PNG predictor streams
pypdf is a free and open-source pure-python PDF library. Prior to 6.12.2, an attacker who uses this vulnerability can craft a PDF which leads to long runtimes. This requires accessing a stream which uses the /FlateDecode filter with a PNG predictor. This vuln…
-
High 7.5
Python-Multipart: Quadratic-time querystring parsing with semicolon separators causes CPU denial of service
Python-Multipart is a streaming multipart parser for Python. Prior to 0.0.30, when parsing application/x-www-form-urlencoded bodies, QuerystringParser located the field separator with a two step lookup: it first scanned the entire remaining buffer for &, and …
-
Medium 5.3
js-yaml: Quadratic-complexity DoS in merge key handling via repeated aliases
js-yaml is a JavaScript YAML parser and dumper. Prior to 4.2.0 and 3.15.0, a crafted YAML document can trigger algorithmic CPU exhaustion in js-yaml merge-key processing (<<) by repeating the same alias many times in a merge sequence. This causes quadratic pa…
-
High 7.5
CPU exhaustion via O(n^2) BigInt construction on radix-prefixed integer literals
js-toml is a TOML parser for JavaScript, fully compliant with the TOML 1.0.0 Spec. Versions up to and including 1.1.1 parse hexadecimal / octal / binary integer literals via a hand-written `parseBigInt` loop that multiplies a `BigInt` accumulator by the radix…
-
Medium 5.3
markdown-it: Quadratic complexity DoS in smartquotes rule via replaceAt string operations
markdown-it is a Markdown parser. Versions 14.1.1 and below contain a denial-of-service vulnerability when typographer: true is enabled, due to quadratic (O(n^2)) processing in the smartquotes rule. The issue stems from repeatedly modifying strings with repla…
-
Medium 5.3
ImageMagick: Policy Bypass in MNG coder could
ImageMagick is free and open-source software used for editing and manipulating digital images. Prior to versions 6.9.13-47 and 7.1.2-22, because of a missing check in the MNG coder it would be possible to read more images than the list limit policy would allo…
-
High 7.5
Spring Framework Algorithmic Denial of Service via SpEL Expressions
Applications that evaluate user-supplied Spring Expression Language (SpEL) expressions are vulnerable to an Algorithmic Denial of Service (DoS). By providing a specially crafted expression, an attacker can trigger excessive resource consumption during evaluat…
-
Low 3.3
bytedance InfiniStore KV Map infinistore.h purge_kv_map algorithmic complexity
A vulnerability was found in bytedance InfiniStore up to 0.2.33. The impacted element is the function purge_kv_map in the library /src/infinistore.h of the component KV Map Handler. Performing a manipulation results in inefficient algorithmic complexity. The …
-
Medium 6.3
Potential DoS via quadratic complexity in unicodedata.normalize()
unicodedata.normalize() can take excessive CPU time when processing specially crafted Unicode input containing long runs of combining characters with alternating Canonical Combining Class values. This affects all normalization forms.
-
High 7.5
Quadratic complexity in WordDecoder.DecodeHeader in mime
Decoding a maliciously-crafted MIME header containing many invalid encoded-words can consume excessive CPU.
-
Medium 6.2
Text::LineFold versions through 2019.001 for Perl duplicate the output based on the number of special break characters
Text::LineFold versions through 2019.001 for Perl duplicate the output based on the number of special break characters. Text::LineFold splits the input string by specific line break characters (such as VT, FF and others) into segments, but applies the break f…
-
Medium 6.9
Botan: Quadratic complexity decoding BER indefinite length encodings
Botan is a C++ cryptography library. Prior to 3.12.0, certain patterns of indefinite length encodings in BER data could cause quadratic behavior in the parser, resulting in a denial of service. Such BER encodings were accepted even in structures which are req…
-
High 7.5
IO::Uncompress::Unzip versions before 2.220 for Perl allow CPU exhaustion via per-byte read loop in fastForward
IO::Uncompress::Unzip versions before 2.220 for Perl allow CPU exhaustion via per-byte read loop in fastForward. fastForward() compares length $offset (the digit count of the offset, 1 to 19) against the chunk size $c instead of $offset itself, so $c shrinks …
-
Medium 6.9
Unbounded name compression in certain cases causes degradation of service
NLnet Labs Unbound up to and including version 1.25.0 has a vulnerability when handling replies with very large RRsets that Unbound needs to perform name compression for. Malicious upstream responses with very large RRsets with records that don't share a suff…
-
Medium 6.9
Degradation of service with unbounded NSEC3 hash calculations
NLnet Labs Unbound up to and including version 1.25.0 has a vulnerability in the DNSSEC validator where the code path to consult the negative cache for DS records does not take into account the limit on NSEC3 hash calculations introduced in 1.19.1. This leads…
-
Medium 6.6
Long list of incoming EDNS options degrades performance
NLnet Labs Unbound up to and including version 1.25.0 is vulnerable to a degradation of service attack related to parsing long lists of incoming EDNS options. An adversary sending queries with too many EDNS options can hold Unbound threads hostage while they …
-
High 7.5
Twisted: Denial of Service (DoS) in twisted.names via Crafted DNS Compression Pointer Chains
Twisted is an event-based framework for internet applications, supporting Python 3.6+. Prior to 26.4.0rc2, the twisted.names module is vulnerable to a Denial of Service (DoS) attack via resource exhaustion during DNS name decompression. A remote, unauthentica…
-
Low 2.9
In libexpat before 2.8.1, the computational complexity of attribute name collision checks allows a denial of service vi…
-
Low 2.3
net-imap: Quadratic complexity when reading response literals
Net::IMAP implements Internet Message Access Protocol (IMAP) client functionality in Ruby. Prior to versions 0.4.24, 0.5.14, and 0.6.4, Net::IMAP::ResponseReader has quadratic time complexity when reading large responses containing many string literals. A hos…
-
High 8.7
Quadratic fragment-name uniqueness check causes denial of service in absinthe
Inefficient Algorithmic Complexity vulnerability in absinthe-graphql absinthe allows unauthenticated denial of service via quadratic fragment-name uniqueness validation. 'Elixir.Absinthe.Phase.Document.Validation.UniqueFragmentNames':run/2 iterates over all f…
-
Medium —
hickory-proto vulnerable to CPU exhaustion during message encoding due to O(n²) name compression
During message encoding, `hickory-proto`'s `BinEncoder` stores pointers to labels that are candidates for name compression in a `Vec<(usize, Vec<u8>)>`. The name compression logic then searches for matches with a linear scan. A malicious message with many rec…
-
High 7.5
webonyx/graphql-php has quadratic validation cost in OverlappingFieldsCanBeMerged via inline fragments
## Summary `OverlappingFieldsCanBeMerged` validation rule has `O(n^2 x m^2)` worst case via flattened inline fragments. The CVE-2023-26144 named-fragment cache does not cover inline fragments. A 364 KB query (200 outer x 100 inner inline fragments) consumes 1…
-
Medium 6.9
graphql-php: Denial of Service via quadratic complexity in OverlappingFieldsCanBeMerged validation
graphql-go is a Go implementation of GraphQL. In versions 15.31.4 and below, the OverlappingFieldsCanBeMerged validation rule performs O(n²) pairwise comparisons of fields sharing the same response name. An attacker can send a query with thousands of repeated…
-
High 7.5
Nordic Semiconductor IronSide SE for nRF54H20 before 23.0.2+17 has an Algorithmic complexity issue.
-
High 7.5
jq: Algorithmic complexity DoS via hardcoded MurmurHash3 seed
jq is a command-line JSON processor. Before commit 0c7d133c3c7e37c00b6d46b658a02244fdd3c784, jq used MurmurHash3 with a hardcoded, publicly visible seed (0x432A9843) for all JSON object hash table operations, which allowed an attacker to precompute key collis…