Inefficient Algorithmic Complexity

pypdf is a free and open-source pure-python PDF library. Prior to 6.21.2, an incomplete remediation for repeated malformed cross-reference entries in GHSA-55h5-xmcq-c37v could still trigger a complete PDF stream reload during each recovery attempt even when a recovery cache was present, causing crafted cross-reference streams to produce long runtimes. This issue is fixed in version 6.21.2.Show less

`jwkFields.CheckConsistency` detected duplicate `key_ops` entries with a pairwise nested loop, making validation cost grow with the **square** of the entry count. Because the check runs on every JWK and JWKS unmarshal, a modestly sized but hostile JWKS document could occupy a CPU core for many seconds.Show less

An attacker able to supply a crafted XML document to an application using QXmlStreamReader can cause disproportionate CPU consumption during parsing, making the application unresponsive (denial of service). Exploitation requires only that the application parse attacker-influenced XML; no authentication, privileges, or user interaction beyond ingesting the input are needed. There is no loss of confidentiality or integrity — no data disclosure, data modification, or code execution — and the impact is contained to the affected process.Show less

Mistune before 3.3.0 contains an algorithmic complexity vulnerability in the inline link parser that allows unauthenticated attackers to exhaust CPU by submitting long runs of unmatched '[' characters. Attackers can send small markdown payloads that trigger O(N^2) parse_link_text and parse_link_label probing, occupying rendering workers for 30+ seconds per 16 KB input.Show less

Mistune before 3.3.0 contains an inefficient algorithmic complexity vulnerability in parse_link_text that allows remote attackers to cause denial of service through unbalanced square brackets. Attackers can submit markdown containing long runs of unmatched brackets to mistune.html(), triggering repeated forward scans that stall worker processes for minutes.Show less

GraphQL-core is a Python port of the GraphQL.js reference implementation. From 3.0.0 until 3.2.12 and 3.3.0rc1, the OverlappingFieldsCanBeMerged rule in specified_rules repeatedly compares fields that share response names and recursively re-compares flattened inline fragments during the validation phase. The prior named-fragment memoization does not cover this path, so nested repeated inline fragments can drive quadratic and worst-case O(n²·m²) CPU work before any resolver or AST-based depth or complexity control runs. An unauthenticated remote attacker can submit a shallow, highly compressible GraphQL query that pins a worker process and can saturate a multi-worker service. This issue is fixed in versions 3.2.12 and 3.3.0rc1.Show less

fzf 0.36.0 through 0.74.5 contains an inefficient algorithmic complexity vulnerability in maskActionContents that allows local attackers to exhaust the --listen HTTP server through quadratic string concatenation. Attackers can repeatedly send POST bodies of about 1 MB to the unauthenticated localhost port, blocking the single-threaded server for about 30 seconds each time.Show less

Pillow is a Python imaging library. From 11.0.0 until 13.0.0, Exif.load() in src/PIL/Image.py repeatedly slices the remaining EXIF data while it begins with the six-byte Exif header. src/PIL/PngImagePlugin.py accepts an uncapped PNG eXIf chunk, so a file filled with repeated headers causes a new shrinking copy on every iteration and quadratic CPU work. The condition is reachable through Image.getexif(), Image._getexif(), and ImageOps.exif_transpose(), including common photo-upload rotation workflows. This issue is fixed in version 13.0.0.Show less

Pillow is a Python imaging library. From 5.1.0 until 13.0.0, PdfParser.linearize_page_tree() in src/PIL/PdfParser.py treats a PDF /Pages graph as a tree without tracking duplicate indirect references. When Image.save(..., format="PDF", append=True) processes an attacker-controlled existing PDF whose /Kids arrays repeatedly reference the same child /Pages node, Pillow expands the shared subtree as distinct pages. A compact malformed PDF can therefore create exponentially many page references and consume disproportionate CPU before the append completes. This issue is fixed in version 13.0.0.Show less

toml-node is a TOML parser for Node.js and the browser. Prior to 5.0.1, toml.parse() repeatedly slices and rejoins every path prefix in lib/compiler.js while processing long dotted keys, table headers, array-of-tables headers, and inline-table keys in assign(), deepRef(), and setNestedKey(). The resulting quadratic work can block the Node.js event loop for several seconds, and sufficiently long paths can terminate the process through memory exhaustion. The maxDepth option does not limit key-segment count and therefore does not mitigate this path. This issue is fixed in version 5.0.1.Show less

toml-node is a TOML parser for Node.js and the browser. Prior to 5.0.1, the toml.parse() compiler's addTableArray() function in lib/compiler.js rescans the complete assignedPaths and valueAssignments bookkeeping sets for every array-of-tables header. Distinct [[name]] paths are not pruned, so a document with many such headers causes quadratic synchronous work and can block the Node.js event loop, denying service to other operations in the process. This issue is fixed in version 5.0.1.Show less

Django REST framework is a toolkit for building Web APIs. Prior to 3.18.2, DefaultContentNegotiation.get_accept_list in rest_framework/negotiation.py accepts an unbounded number and aggregate size of Accept tokens, while select_renderer in that file repeatedly invokes _MediaType parsing from rest_framework/utils/mediatypes.py for each attacker-controlled token, every renderer, and forced 406 renegotiation. A remote unauthenticated client can send many distinct media types containing large quoted parameter values with numerous semicolons, causing Django's parameter parser and DRF's repeated parsing structure to consume disproportionate CPU. Requests to any reachable endpoint can pin synchronous workers for prolonged periods, and concurrent requests can make the service unavailable until the requests stop. This issue is fixed in version 3.18.2.Show less

stream-json is a micro-library of stream components for processing JSON and JSONC with a minimal memory footprint. From 2.0.0 until 3.7.0, FlexAssembler compiles string and regular-expression path filters into matchers that join the full key stack on every container start. Because the key stack grows with unbounded object or array nesting, a document nested to depth D causes D joins whose cost grows with the current depth, resulting in quadratic CPU consumption on the single-threaded event loop. The join occurs before the rule match decision, so the attacker does not need to know the target schema. Consumers using only function filters or no rules are not affected. A crafted nested document can stall all concurrent work in a process that feeds it to an affected FlexAssembler. This issue is fixed in 3.7.0, which adds a default maximum depth.Show less

pypdf is a free and open-source pure-python PDF library. Prior to 6.21.0, an attacker can craft a PDF that causes large memory usage or long runtimes when an application retrieves the document's form fields. This issue is fixed in version 6.21.0.Show less

In a BIND resolver, inbound DNS protocol messages with a particular structure will result in additional processing, with no limit imposed by BIND. A DNS message with a maliciously large number of such structures will cause BIND to consume disproportionate amounts of CPU time and memory during processing. This issue affects BIND 9 versions 9.11.0 through 9.18.50, 9.20.0 through 9.20.29, 9.21.0 through 9.21.26, 9.11.3-S1 through 9.18.50-S1, and 9.20.9-S1 through 9.20.29-S1.Show less

Moov signedxml is a pure Go library for processing signed XML documents. Prior to 1.4.1, ExclusiveCanonicalization in exclusivecanonicalization.go copies the complete accumulated namespace map at every nested element before reference digest or signature checks. Attacker-controlled XML containing deeply nested elements with many unused namespace declarations causes quadratic allocation growth with depth and linear growth with prefixes per level, allowing a comparatively small document to consume multiple gigabytes of memory and terminate the process. The condition is reachable through ValidateReferences without a valid signature, matching certificate, or prior authentication, and it does not bypass signature verification. This issue is fixed in version 1.4.1.Show less

markdown-it is a Markdown parser. From versions 14.1.0 to before 14.3.3, and 15.0.0 to before 15.0.3, a link reference definition whose label or title is never closed is O(n²) with default options. Continuation lines are pulled lazily with str += lineContent in src/rules_block/reference.ts, and the subsequent charCodeAt and slice calls flatten the V8 cons-string, copying everything collected so far; this runs before the rule decides the definition is invalid. No options are required to trigger it. This issue has been patched in versions 14.3.3 and 15.0.3.Show less

Pillow is a Python imaging library. From 5.1.0 until 13.0.0, Pillow takes quadratic time to reserve PDF object identifiers when saving many frames with save_all enabled. PdfParser.next_object_id() repeatedly rebuilds and scans all previously reserved identifiers for every object. An attacker can supply a multi-frame image, including a small APNG with a large declared frame count, to an application that converts it to a multipage PDF. This can consume excessive CPU and deny service. This issue is fixed in version 13.0.0.Show less

Pillow is a Python imaging library. From 9.2.0 until 13.0.0, Pillow performs quadratic copying when saving a GIF with a long comment. _get_global_header() repeatedly copies portions of comment data while assembling the global header, including comments retained from an untrusted input image. An attacker can supply an image with a large GIF comment to an application that saves it as GIF. This can consume excessive CPU and delay or deny service. This issue is fixed in version 13.0.0.Show less

Pillow is a Python imaging library. From 5.4.0 until 13.0.0, Pillow performs quadratic copying while parsing GIF comments. GifImageFile._seek() repeatedly appends immutable bytes for comment sub-blocks and multiple comment extensions, and frame zero is parsed during Image.open(). An attacker can submit a small-dimension GIF containing many comment extensions to any application that opens the file. This can consume excessive CPU and deny service before the application can inspect the image. This issue is fixed in version 13.0.0.Show less