Quadratic-time denial of service in path normalization

[
  {
    "finding_title": "Quadratic-time denial of service in path normalization",
    "verdict": "VALID",
    "reasoning": "The reported vulnerability is a quadratic-time DoS (O(n^2)) in the `normalizePath` function. The code performs repeated in-place modifications (removing duplicate slashes, `/.`, `/..`) using `bytes.Index` to find patterns and `copy` to shift the buffer. For a large input string of length N containing many patterns, each `bytes.Index` call scans the buffer, and the `copy` operation shifts the remainder of the buffer. This results in O(N^2) or O(N^2 * K) complexity (where K is the number of patterns or length of segments) for adversarial inputs. \n\n1. **Bug Existence**: The code clearly exhibits the O(n^2) pattern. The loops `for { n := bytes.Index(...); ... }` scan the entire remaining slice each time a pattern is found. A crafted path like `/aaaaa/bbbbb/...` or a long sequence of `//` or `/../` will trigger this worst-case behavior.\n2. **Attacker Reachability**: The `normalizePath` function is called from `URI.Parse`, `URI.SetPath`, `URI.SetPathBytes`, and `URI.UpdateBytes` (via `updateBytes` -> `Parse`). These are public methods. The threat model for a library like fasthttp explicitly states that the attacker controls the data passed to parsers and protocol handlers (e.g., the `RequestURI` in HTTP requests). An attacker can send an HTTP request with a very long path containing the specific sequences that trigger the worst-case normalization (e.g., `/` followed by many `./` or `../` segments, or just many `//` if the buffer is large enough to cause significant CPU work). While Go's garbage collector and stack limits provide some safety against memory exhaustion, CPU exhaustion (Denial of Service) is a valid security impact under the provided threat model (\"exhaust the host process\").\n3. **Defense Check**: I searched for any length limits or defenses in `normalizePath` or its callers. `normalizePath` takes `dst` and `src` slices. It does not check the length of `src` before entering the loops. The caller `parse` appends the raw path from the request to `u.pathOriginal` and then calls `normalizePath`. There is no truncation or limit applied to the path length before normalization. In Go, unbounded CPU consumption on a single request thread can be used to starve other requests if the server uses a fixed thread pool (which fasthttp often does for performance), or simply crash the worker process if it hits CPU time limits in a containerized environment. Given the \"library\" profile and the explicit warning against \"unbounded... algorithmic complexity\", this is a valid finding.\n\nTherefore, the bug is real, reachable via public API with untrusted input, and causes meaningful harm (DoS).\n\nCRUX: Does the normalizePath function exhibit O(n^2) behavior reachable via public API with untrusted input, causing CPU exhaustion?\nGREP: normalizePath",
    "elapsed": 24.9,
    "tokens": 10498,
    "tokens_in": 9848,
    "tokens_out": 650,
    "cost_usd": 0.00608616,
    "file": "uri.go",
    "round": 1,
    "grep_used": true,
    "grep_results": "GREP `normalizePath`:\n```\ncookie.go:164:\tc.path = normalizePath(c.path, c.bufK)\ncookie.go:171:\tc.path = normalizePath(c.path, c.bufK)\nuri.go:179:\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:185:\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:338:\t\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:345:\t\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:359:\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:624:func normalizePath(dst, src []byte) []byte {\n```"
  },
  {
    "finding_title": "Quadratic-time denial of service in path normalization",
    "verdict": "VALID",
    "reasoning": "The vulnerability report claims that `normalizePath` exhibits O(n^2) behavior, leading to a Denial of Service (DoS) via CPU exhaustion. The code in `uri.go` implements path normalization (removing duplicate slashes, `/.`, `/..`) using loops that repeatedly call `bytes.Index` and `copy`. While `bytes.Index` is O(n) per call, and the buffer shrinks, an attacker can craft input (e.g., a long sequence of `..` segments or duplicate slashes) that forces the loop to execute many times, shifting large portions of the buffer each time. For a path of length N with many removable segments, the total work is O(N^2) or worse. This is a known performance issue in naive path normalization implementations. The function `normalizePath` is called from public entry points like `URI.Parse`, `URI.SetPath`, and `URI.UpdateBytes`, which accept untrusted input from network requests (e.g., the `RequestURI` line in HTTP). Under the provided threat model for a library, unbounded algorithmic complexity on crafted input is considered a security vulnerability. No length limit or defense is applied to the path before normalization in `uri.go`. Therefore, the bug is real, reachable, and security-relevant.\n\nCRUX: Does the normalizePath function exhibit quadratic or super-linear time complexity on adversarial input, allowing an attacker to exhaust CPU resources?\nGREP: normalizePath",
    "elapsed": 16.3,
    "tokens": 11110,
    "tokens_in": 10798,
    "tokens_out": 312,
    "cost_usd": 0.00547116,
    "file": "uri.go",
    "round": 2,
    "grep_used": true,
    "grep_results": "GREP `normalizePath`:\n```\ncookie.go:164:\tc.path = normalizePath(c.path, c.bufK)\ncookie.go:171:\tc.path = normalizePath(c.path, c.bufK)\nuri.go:179:\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:185:\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:338:\t\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:345:\t\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:359:\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:624:func normalizePath(dst, src []byte) []byte {\n```"
  },
  {
    "finding_title": "Quadratic-time denial of service in path normalization",
    "verdict": "VALID",
    "reasoning": "The reported vulnerability is a quadratic-time denial of service (DoS) in the `normalizePath` function. I analyzed the code in `uri.go`: 1. **Bug Existence**: The function `normalizePath` uses loops to remove duplicate slashes, `/./`, and `/../` segments. It repeatedly calls `bytes.Index` to find patterns and `copy` to shift the buffer contents in-place. For an input of length N with many removable segments (e.g., a long chain of `/../` or `//`), each iteration shifts the remainder of the buffer. The total complexity is O(N^2). This is a real algorithmic inefficiency. 2. **Attacker Reachability**: `normalizePath` is called by `URI.Parse`, `URI.SetPath`, `URI.SetPathBytes`, and `URI.UpdateBytes`. These are public methods in a library (`swesweep-fasthttp`) designed to parse HTTP requests. In a typical web server using fasthttp, the `RequestURI` from incoming HTTP packets is passed to `Request.Parse` (or similar), which invokes `URI.Parse`. An external attacker can send an HTTP request with a very long `Request-URI` header (e.g., `/aaaaaaaaa/../../../../../...` or just many slashes) to trigger this worst-case path. 3. **Threat Model & Impact**: The threat model explicitly lists \"unbounded... algorithmic complexity\" and \"CPU exhaustion\" as valid security impacts for libraries. There is no length limit on the `Request-URI` in `URI.Parse` itself. While `fasthttp` server configuration *might* limit `MaxRequestHeaderBytes`, the library itself (which is the scope of this report) does not enforce a bound. A library function that performs O(N^2) work on untrusted input is a security vulnerability because it allows a remote attacker to consume CPU cycles, potentially starving other requests or crashing the process due to resource limits. 4. **Defenses**: I checked for any internal bounds. `normalizePath` does not check the length of `src`. `parse` does not truncate the path. Therefore, there is no internal defense. The bug is real, reachable, and security-relevant under the provided threat model.\n\nCRUX: normalizePath performs in-place buffer shifting with repeated linear scans, resulting in O(N^2) complexity for crafted paths, and is reachable via public API entry points without internal length limits.\nGREP: normalizePath",
    "elapsed": 19.9,
    "tokens": 11706,
    "tokens_in": 11181,
    "tokens_out": 525,
    "cost_usd": 0.0062710199999999995,
    "file": "uri.go",
    "round": 3,
    "grep_used": true,
    "grep_results": "GREP `normalizePath`:\n```\ncookie.go:164:\tc.path = normalizePath(c.path, c.bufK)\ncookie.go:171:\tc.path = normalizePath(c.path, c.bufK)\nuri.go:179:\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:185:\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:338:\t\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:345:\t\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:359:\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:624:func normalizePath(dst, src []byte) []byte {\n```"
  },
  {
    "finding_title": "Quadratic-time denial of service in path normalization",
    "verdict": "UNCERTAIN",
    "reasoning": "The reported vulnerability is an O(N^2) algorithmic complexity in `normalizePath`, which is a performance issue. However, in Go, the `bytes.Index` function (used to find patterns in the loops) is implemented in assembly using SIMD instructions (AVX2 on modern hardware). This allows it to scan memory at high throughput (roughly the memory bandwidth of the CPU). While the `copy` operation shifts data (which is O(N) per removal), the total work for an adversarial path (e.g., a sequence of `/../`) is bounded by the cost of scanning the input. \n\nCrucially, for a remote DoS to occur via CPU exhaustion in a Go application using fasthttp, the attacker must consume more CPU time than the server can handle. With SIMD-accelerated scanning, `bytes.Index` on a 1MB buffer is extremely fast (sub-millisecond). The `copy` operations are also memory-bandwidth bound. The total time to process a 1MB malicious path is likely on the order of milliseconds. To cause a meaningful DoS (e.g., tying up a worker for seconds), the attacker would need to send buffers of hundreds of MBs, which is restricted by network limits, TLS overhead, and typical reverse proxy/server configuration limits (e.g., `MaxRequestHeaderBytes` or `MaxRequestBodySize`) that are usually in place before the data even reaches the library, or by the Go runtime's own memory limits.\n\nMore importantly, under standard threat models for general-purpose HTTP libraries, algorithmic complexity issues that require extremely large inputs (MBs of payload) to cause observable CPU exhaustion are typically classified as DoS vulnerabilities only if the input size is not bounded by the environment. However, the specific claim here is about `normalizePath` in `uri.go`. Let's look at the specific loops. \n\nActually, there is a more critical perspective: Is this a *security* vulnerability? The prompt states: \"A data race... is a code quality issue... mark these INVALID.\" It does not explicitly exclude algorithmic complexity, but it requires \"meaningful harm.\" \n\nLet's re-evaluate the ",
    "elapsed": 35.5,
    "tokens": 12236,
    "tokens_in": 11777,
    "tokens_out": 459,
    "cost_usd": 0.00632334,
    "file": "uri.go",
    "round": 4
  },
  {
    "finding_title": "Quadratic-time denial of service in path normalization",
    "verdict": "VALID",
    "reasoning": "The reported vulnerability claims that `normalizePath` in `uri.go` exhibits O(N^2) complexity, leading to a CPU exhaustion DoS. \n\n1. **Bug Pattern Analysis**: The `normalizePath` function uses loops with `bytes.Index` and `copy`. For the \"remove duplicate slashes\" loop (`//`), the pattern length is 2. If an attacker sends a string of N slashes (`/`), the loop runs N/2 times. Each iteration scans a shrinking buffer and copies a shrinking buffer. The total work is the sum of lengths of the remaining buffer in each step, which is O(N^2). Specifically, for input `/` repeated N times, the first `bytes.Index` finds `//` at 0, copies N-1 bytes, next scan N-2, etc. Sum is roughly N^2/2. Thus, the O(N^2) pattern is real for inputs consisting primarily of the target pattern (like `//` or `/.`).\n\n2. **Attacker Reachability**: `normalizePath` is called by `URI.Parse`, which is a public API. In fasthttp, `URI.Parse` is typically called with the `RequestURI` from incoming HTTP requests, which is untrusted network input. An attacker can craft an HTTP request with a very long path containing many `//` or `/../` sequences.\n\n3. **Impact**: The threat model for a library explicitly lists \"unbounded... algorithmic complexity\" and \"resource bounds\" as valid security impacts. While Go's `bytes.Index` uses SIMD, the total number of operations scales quadratically with input size. For a 1MB input, N=10^6, operations ~ 5*10^11. Even at 10^9 ops/sec, this takes ~500 seconds. Even for smaller inputs (e.g., 100KB), N=10^5, operations ~ 5*10^9, taking ~5 seconds per request. If an attacker opens multiple connections, they can exhaust the CPU or worker threads of the host application, causing a Denial of Service. The library itself does not enforce a length limit on the path before normalization. Therefore, this is a valid security vulnerability (algorithmic complexity DoS).\n\nCRUX: Does normalizePath perform O(N^2) work on untrusted input that can be supplied by an external attacker via public API entry points like URI.Parse?\nGREP: normalizePath",
    "elapsed": 20.1,
    "tokens": 12661,
    "tokens_in": 12124,
    "tokens_out": 537,
    "cost_usd": 0.00670308,
    "file": "uri.go",
    "round": 5,
    "grep_used": true,
    "grep_results": "GREP `normalizePath`:\n```\ncookie.go:164:\tc.path = normalizePath(c.path, c.bufK)\ncookie.go:171:\tc.path = normalizePath(c.path, c.bufK)\nuri.go:179:\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:185:\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:338:\t\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:345:\t\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:359:\tu.path = normalizePath(u.path, u.pathOriginal)\nuri.go:624:func normalizePath(dst, src []byte) []byte {\n```"
  },
  {
    "verdict": "VALID",
    "reasoning": "[ARBITER] The `normalizePath` function in `uri.go` exhibits quadratic time complexity O(N^2) for adversarial inputs. The function uses a loop that repeatedly calls `bytes.Index` to find patterns (like `//`, `/./`, `/../`) and then uses `copy` to shift the remaining bytes in the buffer. For a large input string containing many such patterns (e.g., a long sequence of `//` or `/../`), each removal operation requires scanning the remainder of the buffer and shifting data. Since the buffer length decreases by a small constant while the scan/copy cost is proportional to the remaining length, the total computational work is proportional to the sum of the buffer sizes, which is O(N^2). This function is reachable via public API entry points such as `URI.Parse`, `URI.Update`, and `SetPath`, which accept untrusted input. An attacker can craft a long URI path to trigger this complexity, causing CPU exhaustion (Denial of Service). The threat model explicitly identifies algorithmic complexity issues reachable via public API as vulnerabilities.",
    "round": 6,
    "file": "uri.go",
    "finding_title": "Quadratic-time denial of service in path normalization",
    "elapsed": 14.8,
    "tokens_in": 10015,
    "tokens_out": 234,
    "cost_usd": 0.004908300000000001
  }
]