Inefficient Algorithmic Complexity

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 parse-time behavior relative to input size and can block a Node.js worker/event loop for seconds with a relatively small payload (tens of KB), resulting in denial of service. The issue is in merge handling inside lib/loader.js. This vulnerability is fixed in 4.2.0 and 3.15.0.Show less

js-toml is a TOML parser for JavaScript, fully compliant with the TOML 1.0.0 Spec. Versions up to and including 1.1.0 parse hexadecimal / octal / binary integer literals via a hand-written `parseBigInt` loop that multiplies a `BigInt` accumulator by the radix once per input digit. Each iteration performs a `BigInt * BigInt` operation on an accumulator that grows linearly with the number of digits already consumed, so the whole loop is O(n²) in the literal length. The lexer regex places no upper bound on the literal length, so a single TOML document containing one ~500 kB hex literal pins one CPU core for ~40 seconds on a modern laptop (Apple M-series, Node v22). Memory amplification is bounded but CPU amplification is severe and grows quadratically: doubling the literal length quadruples the work. A caller that invokes `load()` on attacker-controlled TOML (configuration upload endpoints, CI/CD systems ingesting third-party `*.toml`, IDE plugins, build tools) is exposed to a single-request CPU exhaustion DoS. Version 1.1.1 fixes the issue.Show less

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 allow resulting in excessive resource use. This issue has been patched in versions 6.9.13-47 and 7.1.2-22.Show less

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 evaluation, leading to application degradation or unavailability. Affected versions: Spring Framework 7.0.0 through 7.0.7; 6.2.0 through 6.2.18; 6.1.0 through 6.1.27; 5.3.0 through 5.3.48.Show less

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 attack requires a local approach. The exploit has been made public and could be used. The project was informed of the problem early through an issue report but has not responded yet.Show less

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.Show less

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 function to the entire string, not just the segment. A side effect of this is that the full input can be duplicated for each segment. Besides being incorrect, this can lead to unexpected resource consumption and possible denial of service. Note that Text::LineFold is part of the Unicode-LineBreak distribution, which may have a higher version number than the module.Show less

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 required to be encoded as DER, which prohibits indefinite length encodings. This vulnerability is fixed in 3.12.0.Show less

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 from 16 KiB to 1-19 bytes per iteration. Extracting a named entry from an attacker supplied zip via IO::Uncompress::Unzip->new($zip, Name => $target) drives a per-byte read loop scaling with the entry's compressed size, up to the non-Zip64 4 GiB cap.Show less

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 suffix above the root can cause Unbound to spend a considerable time applying name compression to downstream replies. This can lead to degraded performance and eventually denial of service in well orchestrated attacks. An adversary can exploit the vulnerability by querying Unbound for the specially crafted contents of a malicious zone with very large RRsets. Before Unbound replies to the query it will try to apply name compression which was an unbounded operation that could lock the CPU until the whole packet was complete. A compression limit was introduced in 1.21.1 for this but it didn't account for the case where records would not share any suffix above the root. That causes Unbound to go in a different code path because of the compression tree lookup failure and eventually not increment the compression counter for those operations. Unbound 1.25.1 contains a patch with a fix that increments the compression counter regardless of the compression tree lookup. This is a complement fix to CVE-2024-8508.Show less

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 to degradation of service during the attack. An adversary that controls a DNSSEC signed zone can exploit this by signing NSEC3 records with acceptably high iterations for child delegations and querying a vulnerable Unbound. Unbound will keep performing the allowed hash calculations on the NSEC3 records and will not limit the work by the mitigation introduced in 1.19.1. As a side effect, a global lock for the negative cache will be held for the duration of the hashing, blocking other threads that need to consult the negative cache. Coordinated attacks could raise the vulnerability to denial of service. Unbound 1.25.1 contains a patch with a fix to bound the vulnerable code path with the existing limit for NSEC3 hash calculations.Show less

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 are parsing and creating internal data structures for the options. Coordinated attacks can result in degradation and/or denial of service. Unbound 1.25.1 contains a patch with a fix to limit acceptable incoming EDNS options (100).Show less

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, unauthenticated attacker can exploit this by sending a crafted TCP DNS packet containing deeply chained compression pointers. This flaw bypasses previous loop-prevention logic, causing the single-threaded Twisted reactor to hang while processing millions of recursive lookups, effectively freezing the server. This vulnerability is fixed in 26.4.0rc2.Show less

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 hostile server can send responses which are crafted to exhaust the client's CPU for a denial of service attack. This issue has been patched in versions 0.4.24, 0.5.14, and 0.6.4.Show less

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 fragments and for each one calls duplicate?/2, which evaluates Enum.count(fragments, &(&1.name == name)) — a full linear scan of the fragment list. The result is O(N²) comparisons per document, where N is the number of fragment definitions supplied by the caller. Because input.fragments is built directly from the GraphQL query body, N is fully attacker-controlled. A minimum-size fragment definition is roughly 16 bytes, so a ~1 MB document carries ~60,000 fragments and forces ~3.6 × 10⁹ comparisons inside this single validation phase. No authentication, schema knowledge, or special configuration is required. This issue affects absinthe: from 1.2.0 before 1.10.2.Show less

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 identical fields, causing excessive CPU usage during validation before execution begins. This is not mitigated by existing QueryDepth or QueryComplexity rules. This issue has been fixed in version 15.31.5.Show less