Query string parameter order is randomized per request for ALB (and other map-based) events, which breaks apps that rely on the raw request URL #1181

Summary

When the adapter receives an event from an ALB Lambda target, the order of the query string parameters seen by the web application changes from request to request. For GET /path?a=1&b=2 the application sees a=1&b=2 or b=2&a=1, randomly.

The cause is that lambda_http rebuilds the query string from a QueryMap, which wraps a std::collections::HashMap. The iteration order of a HashMap is randomized, so the rebuilt query string has a random order. The original order is lost, and even the same URL does not produce the same query string twice.

This is a problem for applications that use the raw request URL (including the query string) for something that must be reproducible. For example, CakePHP's FormProtection embeds the form action URL in a token and compares it with the URL of the POST request. When the order of the parameters differs, the token validation fails and the user gets a 400 Bad Request. About half of the form submissions fail when the URL has two parameters.

It works as expected without the adapter (for example, on a local docker-compose with nginx and php-fpm), so the problem only appears on AWS.

Environment

• AWS Lambda (container image) behind an ALB (target type lambda, lambda.multi_value_headers.enabled = true)
• aws-lambda-adapter 0.9.1 (public.ecr.aws/awsguru/aws-lambda-adapter:0.9.1)
• Application: nginx + PHP-FPM (CakePHP 5.1)
• I also read the sources of v1.1.0 (lambda_http 1.3.0) and lambda_http 1.3.1: the code path is the same (see below). I did not run the adapter 1.1.0 binary on AWS.

Steps to reproduce

1. Library level (no AWS needed)

This feeds the same ALB event 10,000 times through lambda_http, the same way the adapter does it.

Cargo.toml:

[package]
name = "lwa-query-order-repro"
version = "0.1.0"
edition = "2021"

[dependencies]
http = "1"
lambda_http = { version = "1.3", default-features = false, features = ["alb"] }
serde_json = "1"

src/main.rs:

use lambda_http::request::LambdaRequest;
use std::collections::BTreeMap;

// ALB (Lambda target) event for `GET /add?parent_id=1&type=leader_employee&a=1&b=2`
const EVENT: &str = r#"{
  "requestContext": { "elb": { "targetGroupArn": "arn:aws:elasticloadbalancing:ap-northeast-1:123456789012:targetgroup/tg/0123456789abcdef" } },
  "httpMethod": "GET",
  "path": "/add",
  "queryStringParameters": { "parent_id": "1", "type": "leader_employee", "a": "1", "b": "2" },
  "multiValueQueryStringParameters": { "parent_id": ["1"], "type": ["leader_employee"], "a": ["1"], "b": ["2"] },
  "headers": { "host": "example.com", "x-forwarded-proto": "https" },
  "multiValueHeaders": { "host": ["example.com"], "x-forwarded-proto": ["https"] },
  "body": "",
  "isBase64Encoded": false
}"#;

fn main() {
    let mut counts: BTreeMap<String, u32> = BTreeMap::new();
    for _ in 0..10_000 {
        let event: LambdaRequest = serde_json::from_str(EVENT).unwrap();
        let request: http::Request<lambda_http::Body> = event.into();
        let query = request.uri().query().unwrap_or_default().to_string();
        *counts.entry(query).or_default() += 1;
    }

    println!("{} distinct query strings from 10000 identical events:", counts.len());
    for (query, count) in &counts {
        println!("{count:>6}  ?{query}");
    }
}

Result (lambda_http 1.3.1, aws_lambda_events 1.2.0, query_map 0.7.0; the same process, the same event every time):

24 distinct query strings from 10000 identical events:
   441  ?a=1&b=2&parent_id=1&type=leader_employee
   387  ?a=1&b=2&type=leader_employee&parent_id=1
   442  ?a=1&parent_id=1&b=2&type=leader_employee
   ...
   410  ?type=leader_employee&parent_id=1&b=2&a=1

All 4! = 24 permutations show up, with a roughly uniform distribution.

2. On AWS

1. Put a web application that prints $_SERVER['QUERY_STRING'] (or logs the request URL) behind an ALB (Lambda target) with the adapter.
2. Request /?parent_id=1&type=x repeatedly (the URL is always the same).
3. The application sees parent_id=1&type=x and type=x&parent_id=1 in about half of the requests each.

In my environment, the application generates the link ...?parent_id=1&type=leader_employee (always in this order). Counting the requests the application received for this page: 28 requests with parent_id first, 28 requests with type first (a 50:50 split).

The same application running without the adapter (nginx → php-fpm) always sees the order of the request.

Expected behavior

The adapter passes the query string to the web application in the same order as the original request, or at least in a deterministic order, so that the same URL always produces the same query string.

Actual behavior

The order is randomized per request.

Root cause

• lambda_http request.rs: into_alb_request builds QueryMaps with decode_query_map() (to_query_string() → from_str()), and build_request_uri() joins them again with to_query_string().
• query_map: QueryMap is Arc<HashMap<String, Vec<String>>>. from_str() creates a new HashMap each time, and to_query_string() iterates over it. HashMap uses RandomState, whose seed is different for every instance.
• aws-lambda-adapter src/lib.rs (v1.1.0) copies parts.uri.query() to the URL that is sent to the web application.

The events from API Gateway HTTP API (v2) are not affected, because into_api_gateway_v2_request appends raw_query_string as it is. The events that are converted through QueryMap (ALB, and by reading the code, API Gateway REST API (v1) and VPC Lattice) are affected. I have only confirmed the ALB case.

Impact

Applications that use the raw URL with the query string for something that must be reproducible:

• CakePHP FormProtection (confirmed): the form action URL is embedded in the token and compared with the URL of the POST request. Two or more query parameters make the validation fail about half of the time (Form tampering protection token validation failed). CakePHP's CsrfProtectionMiddleware is not affected.
• Laravel signed URLs (not tested, from reading the code): UrlGenerator::signedRoute() signs the URL with the parameters sorted by key, and hasCorrectSignature() rebuilds the URL from the raw QUERY_STRING of the request, in the order received. I expect hasValidSignature() to fail randomly for a signed URL that has two or more parameters, but I did not verify this on AWS.
• In general, any logic that builds a cache key, a signature, or a token from the raw URL (for example, webhook URL signatures, or per-URL session keys).

Possible fixes

1. Keep the order of the original request. For ALB, the event only contains queryStringParameters / multiValueQueryStringParameters as JSON objects. If ALB emits the keys in the order of the request, an insertion-ordered map (for example indexmap) in QueryMap, or a Vec<(String, String)>, would keep it. I have not verified whether ALB keeps the order in the JSON object, so the maintainers' knowledge would help here.
2. If the original order can not be known, make the output deterministic (for example, sort by key, keeping the order of the values of the same key). Then the same URL always results in the same query string, which is enough for the use cases above, although the order differs from the request.
3. Document the behavior (the order of the query string parameters is not preserved for ALB), until it is fixed.

Workaround

Until this is fixed, the application can normalize the order of the query string itself. For example, sort the query string of the request URL (and of the URLs the application generates) so that both sides always use the same order.

Related

• Display errors returned by handler in CloudWatch #99 (this repository) and Querystrings that have percent encodings get double encoded for Lambda ALB Events in lambda-http #543: double encoding of the query string of ALB events. It is a different problem, but it is the same code path (decode_query_map() / build_request_uri()).
• lambda_http::Request should expose a QueryMap from a raw_query_string #470: the raw_query_string of API Gateway v2 is used as it is, which is why v2 is not affected.