Beware the letter 'M'. The strangest bug of my life / Habr

On a Friday evening, a colleague, let's call him Avenger, asked if I had ever encountered a problem where a route returns 400... but "if you change the name to something very different," then everything is okay. At first, I didn't pay attention to the word "very". Maybe the route registration is duplicated somewhere? Or Avenger mixed up GET and POST. Or is there some general bug in handler creation?

The Mystical Letter 'M'

Monday morning began with a trial by fire. Killing gradle daemons. Updating the JDK. A clean build. Removing authorization code. Fiddling with call logging. The debugger. All in vain — no error logs anywhere.

The ordeal lasted a couple of hours before Avenger discovered a surprising pattern:

If the endpoint name contains the letter M, it doesn't work.

The release was at stake, so the priority was to solve the problem.

Using git-bisect, Avenger found the broken commit — it was an update of library versions to "secure" ones at the request of the security team. The most "secure" endpoints turned out to be those with the letter 'M'.

Using the same binary search, rolling back half of the libraries per Gradle sync, Avenger found the broken library — it was Netty codec http 4.1.129.Final.

We took a newer version — and the problem was solved. The fix is available starting from 4.1.130.Final.

My Methodical Microanalysis

I couldn't just leave it at that, so after work, I started digging into what was wrong with the letter 'M'.

Here is a GitHub project to reproduce the problem. It consists only of the aforementioned version of Netty codec and a server with two endpoints:

fun main() {
    embeddedServer(Netty, port = 8080) {
        routing {
            get("/hello") { call.respondText("ok", ContentType.Text.Plain, HttpStatusCode.OK) }
            get("/helloM") { call.respondText("ok", ContentType.Text.Plain, HttpStatusCode.OK) }
        }
    }.start(wait = true)
}

We start the service, send a curl:

curl -i localhost:8080/hello # ok
curl -i localhost:8080/helloM # 400

To be fail fast, most libraries validate the URL before routing. If you've seen % in links — that's it. It's called percent-encoding. What if we hide the 'M' so that it's already 'encoded'?

Percent-encoding uses only ASCII characters. We find in the table that the hexadecimal for 'M' is '4D'.

From Wikipedia on percent-encoding:

Special characters are replaced with a percent sign (%) followed by two hexadecimal digits representing the character's byte value

curl -i localhost:8080/hello%4D # ok

And so we've confirmed that the validation is not working.

The Mystical Letter... 'J'!

Let's figure out what else isn't working right away. We'll send curls for each letter of the alphabet:

for c in {A..Z}; do
  _path="/hello${c}"
  code=$(curl -s -o /dev/null -w "%{http_code}" "http://localhost:8080$\\_path")
  echo "$code $_path"
done

# 404 /helloA
# 404 /helloB
# 404 /helloC
# 404 /helloD
# 404 /helloE
# 404 /helloF
# 404 /helloG
# 404 /helloH
# 404 /helloI
# 400 /helloJ
# 404 /helloK
# 404 /helloL
# 400 /helloM
# 404 /helloN
# 404 /helloO
# 404 /helloP
# 404 /helloQ
# 404 /helloR
# 404 /helloS
# 404 /helloT
# 404 /helloU
# 404 /helloV
# 404 /helloW
# 404 /helloX
# 404 /helloY
# 404 /helloZ

We see two types of responses:

404, when the endpoint is not found.
400, when Netty is going crazy.

It turns out the letter 'J' doesn't work either. Another hint that the Masons and Jesuits rule the world.

Maniacally Digging into the Problem

There are 10 types of people: those who understand binary, and those who don't.

Let's create a build:

./gradlew installDist
# бинарь будет лежать в build/install/mmm/bin/mmm

Set JAVA_TOOL_OPTIONS to a value that records all errors and run:

export JAVA_TOOL_OPTIONS=-Xlog:exceptions=debug:file=logs/netty.log

./build/install/mmm/bin/mmm

From another terminal tab, send a curl:

curl -i localhost:8080/helloM # 400

Kill the process and search the log file for the validation errors we suspected:

cat logs/netty.log | grep validat

It will print:

 thrown in interpreter method <{method} {0x0000000128e0c9d8} 'validateRequestLineTokens' '(Lio/netty/handler/codec/http/HttpVersion;Lio/netty/handler/codec/http/HttpMethod;Ljava/lang/String;)V' in 'io/netty/handler/codec/http/HttpUtil'>
[1.578s][debug][exceptions] Looking for catch handler for exception of type "java.lang.IllegalArgumentException" in method "validateRequestLineTokens"
[1.578s][debug][exceptions] No catch handler found for exception of type "java.lang.IllegalArgumentException" in method "validateRequestLineTokens"

We search for validateRequestLineTokens directly in IntelliJ IDEA by symbols — we see that it's netty-codec-http-4.1.129.Final.jar!/io/netty/handler/codec/http/HttpUtil.class:

static void validateRequestLineTokens(HttpVersion httpVersion, HttpMethod method, String uri) {
    if (method.getClass() != HttpMethod.class) {
        if (!isEncodingSafeStartLineToken(method.asciiName())) {
            throw new IllegalArgumentException(
                    "The HTTP method name contain illegal characters: " + method.asciiName());
        }
    }

    if (!isEncodingSafeStartLineToken(uri)) {
        throw new IllegalArgumentException("The URI contain illegal characters: " + uri);
    }
}

The function used inside is:

private static final long ILLEGAL_REQUEST_LINE_TOKEN_OCTET_MASK = 1L << '\n' | 1L << '\r' | 1L << ' ';

public static boolean isEncodingSafeStartLineToken(CharSequence token) {
    int i = 0;
    int lenBytes = token.length();
    int modulo = lenBytes % 4;
    int lenInts = modulo == 0 ? lenBytes : lenBytes - modulo;
    for (; i < lenInts; i += 4) {
        long chars = 1L << token.charAt(i) |
                1L << token.charAt(i + 1) |
                1L << token.charAt(i + 2) |
                1L << token.charAt(i + 3);
        if ((chars & ILLEGAL_REQUEST_LINE_TOKEN_OCTET_MASK) != 0) {
            return false;
        }
    }
    for (; i < lenBytes; i++) {
        long ch = 1L << token.charAt(i);
        if ((ch & ILLEGAL_REQUEST_LINE_TOKEN_OCTET_MASK) != 0) {
            return false;
        }
    }
    return true;
}

We set breakpoints, run the project in debug mode, send a curl with 'M', and see that in the lower loop, the code exits with false when token.charAt(i) = M.

In the specification for Java, we read:

If the promoted type of the left-hand operand is long then only the six lowest-order bits of the right-hand operand are used as the shift distance... The shift distance actually used is therefore always in the range 0 to 63, inclusive.

63 in binary is 0b111111.

This means that a bitwise shift (the <<) by n will be no more than a shift by 63 or n & 0b111111.

1L & 0  // 0
1L & 63 // 63
1L & 64 // то же что и  `1L & 0`   т.к. 64 & 63 = 0
1L & 77 // то же что и  `1L & 13`  т.к. 77 & 63 = 13

In the code, we see long ch = 1L << token.charAt(i). 'M' is 77, 'J' is 74.


long ILLEGAL_REQUEST_LINE_TOKEN_OCTET_MASK = 1L << '\n' | 1L << '\r' | 1L << ' ';
// 4294976512L

(1L << 'M') & ILLEGAL_REQUEST_LINE_TOKEN_OCTET_MASK
 // 8192

And that's how we get false, because the developers didn't account for the fact that a shift on a Long shifts by no more than 63 bits.

long ch = 1L << token.charAt(i);
if ((ch & ILLEGAL_REQUEST_LINE_TOKEN_OCTET_MASK) != 0) {
    return false; // выходим из `isEncodingSafeStartLineToken` с `false`
}

Everything else that doesn't fall into ILLEGAL_REQUEST_LINE_TOKEN_OCTET_MASK doesn't fall there by chance.

Maybe 6 bits is not enough for a long?

Why only 6 bits for the shift?

A Long fits into 64 bits. That is, the ones and zeros are laid out in positions from 0 to 63.
These 64 values can be represented as 2^6 = 64. Just enough to account for a shift over the entire length of a "long".

The Moment of Truth — The Fix

In 4.1.130.Final the problem was fixed (issue), here's what the familiar isEncodingSafeStartLineToken looks like:

public static boolean isEncodingSafeStartLineToken(CharSequence token) {
    int lenBytes = token.length();
    for (int i = 0; i < lenBytes; i++) {
        char ch = token.charAt(i);
        // this is to help AOT compiled code which cannot profile the switch
        if (ch <= ' ') {
            switch (ch) {
                case '\n':
                case '\r':
                case ' ':
                    return false;
            }
        }
    }
    return true;
}

The Conclusion

So that's how Netty messed up. Minor mistakes are normal, but it's unexpected to see something like this from a framework like Netty. And it was surprising that I couldn't find the problem by googling. Perhaps we are now the only ones who know about the M & J conspiracy.

Glad you read to the end! If you don't want to say goodbye and want to see more interesting facts about the letter 'M' — visit my channel.