json:parse_bjdata_fuzzer reaches assertion

[nlohmann]

Description

The input 0x5b, 0x23, 0x49, 0x20, 0xff triggers an assertion in the fuzzer for BJData.

• https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=47305
• https://oss-fuzz.com/testcase-detail/5621157828624384

Reproduction steps

• Call the fuzzer on input 0x5b, 0x23, 0x49, 0x20, 0xff.
• Observe the assertion.

Expected vs. actual results

No assertion should be triggered. Either the fuzzer must be made more robust against or there is a bug in the library that must be fixed.

Minimal code example

Adapted fuzzer:

#include <nlohmann/json.hpp>

using json = nlohmann::json;

int main() {
    std::vector<std::uint8_t> vec1 = {{0x5b, 0x23, 0x49, 0x20, 0xff}};

    json j1 = json::from_bjdata(vec1);

    try
    {
        // step 2.1: round trip without adding size annotations to container types
        std::vector<uint8_t> vec2 = json::to_bjdata(j1, false, false);

        // step 2.2: round trip with adding size annotations but without adding type annonations to container types
        std::vector<uint8_t> vec3 = json::to_bjdata(j1, true, false);

        // step 2.3: round trip with adding size as well as type annotations to container types
        std::vector<uint8_t> vec4 = json::to_bjdata(j1, true, true);

        // parse serialization
        json j2 = json::from_bjdata(vec2);
        json j3 = json::from_bjdata(vec3);
        json j4 = json::from_bjdata(vec4);

        // serializations must match
        assert(json::to_bjdata(j2, false, false) == vec2);
        assert(json::to_bjdata(j3, true, false) == vec3);
        assert(json::to_bjdata(j4, true, true) == vec4);
    }
    catch (const json::parse_error&)
    {
        // parsing a BJData serialization must not fail
        assert(false);
    }
}

Error messages

Assertion

// parsing a BJData serialization must not fail
assert(false);

is triggered. In the original context, the following stack trace is produced:

+----------------------------------------Release Build Stacktrace----------------------------------------+
Command: /mnt/scratch0/clusterfuzz/resources/platform/linux/unshare -c -n /mnt/scratch0/clusterfuzz/bot/builds/clusterfuzz-builds-afl_json_26b1464c0c18fac23c49bf26ed996090f90e682a/revisions/parse_bjdata_fuzzer /mnt/scratch0/clusterfuzz/bot/inputs/fuzzer-testcases/crash
Time ran: 0.16492581367492676
parse_bjdata_fuzzer: src/fuzzer-parse_bjdata.cpp:66: int LLVMFuzzerTestOneInput(const uint8_t *, size_t): Assertion `false' failed.
AddressSanitizer:DEADLYSIGNAL
=================================================================
==765==ERROR: AddressSanitizer: ABRT on unknown address 0x0539000002fd (pc 0x7f986288918b bp 0x7f98629fe588 sp 0x7fff5efdeb10 T0)
SCARINESS: 10 (signal)
    #0 0x7f986288918b in raise /build/glibc-eX1tMB/glibc-2.31/sysdeps/unix/sysv/linux/raise.c:51:1
    #1 0x7f9862868858 in abort /build/glibc-eX1tMB/glibc-2.31/stdlib/abort.c:79:7
    #2 0x7f9862868728 in __assert_fail_base /build/glibc-eX1tMB/glibc-2.31/assert/assert.c:92:3
    #3 0x7f9862879f35 in __assert_fail /build/glibc-eX1tMB/glibc-2.31/assert/assert.c:101:3
    #4 0x4d9414 in LLVMFuzzerTestOneInput json/tests/src/fuzzer-parse_bjdata.cpp:66:13
    #5 0x4d729a in ExecuteFilesOnyByOne aflplusplus/utils/aflpp_driver/aflpp_driver.c:234:7
    #6 0x4d706d in main aflplusplus/utils/aflpp_driver/aflpp_driver.c:318:12
    #7 0x7f986286a0b2 in __libc_start_main /build/glibc-eX1tMB/glibc-2.31/csu/libc-start.c:308:16
    #8 0x41e5bd in _start
AddressSanitizer can not provide additional info.
SUMMARY: AddressSanitizer: ABRT (/lib/x86_64-linux-gnu/libc.so.6+0x4618b)
==765==ABORTING

Compiler and operating system

macOS 12.3.1, Apple clang version 13.1.6

Library version

develop

Validation

• The bug also occurs if the latest version from the develop branch is used.
• I can successfully compile and run the unit tests.

[nlohmann]

Introduced with #3336, similar to #3461 /cc @fangq

[fangq]

this is embarrassing. I assume this keeps triggering fuzzer error is because I do not fully understand the exception handling in the code.

right now, if using json.cpp with #3461 patch, I see the above code, as well as the adapted fuzzer code in #3461, output the below message

terminate called after throwing an instance of 'nlohmann::detail::parse_error'
  what():  [json.exception.parse_error.112] parse error at byte 3: syntax error while parsing BJData type: marker 0x5B is not a permitted optimized array type
Aborted (core dumped)

upon reading the code, I do not think it should be triggered - here is the part throwing this error

        if (current == '$')
        {
            std::vector<char_int_type> bjdx = {'[', '{', 'S', 'H', 'T', 'F', 'N', 'Z'}; // excluded markers in bjdata optimized type

            result.second = get();  // must not ignore 'N', because 'N' maybe the type
            if (JSON_HEDLEY_UNLIKELY( input_format == input_format_t::bjdata && std::find(bjdx.begin(), bjdx.end(), result.second) != bjdx.end() ))
            {
                auto last_token = get_token_string();
                return sax->parse_error(chars_read, last_token, parse_error::create(112, chars_read,
                                        exception_message(input_format, concat("marker 0x", last_token, " is not a permitted optimized array type"), "type"), nullptr));
            }
            ....
       }

because there is no $ (0x24) in the input, this error should not be triggered.

can you explain to me what JSON_HEDLEY_UNLIKELY does? I coped it from other lines and thought it is safe for me to have it, but I don't fully understand what it does.

[falbrechtskirchinger]

JSON_HEDLEY_UNLIKELY is just a hint to the compiler telling it a condition is unlikely to evaluate to true. It's purely for optimization, nothing more.

[fangq]

never mind, I was running a wrong fuzzer code. with the above code, the error is

error
int main(): Assertion `false' failed.
Aborted (core dumped)

tracing it now.

[fangq]

ok, essentially this is the same bug that triggered #3461 - it seems that in both cases, the return false statement triggered by unexpected_eof() was not handled.

if I replace bjdata by ubjson in the test code, the unexpected eof error was triggered via line 2225 instead of line 2190.

I am still trying to understand why the return false on line 2190 is not handled in the higher levels of the call stack.

[nlohmann]

Unfortunately, I currently can't get AFL to work locally. I think these bugs can be triggered by letting it run for a few minutes.

[falbrechtskirchinger]

Unfortunately, I currently can't get AFL to work locally. I think these bugs can be triggered by letting it run for a few minutes.

I've just installed AFL, if you give me instructions or pointers on what to do next, I can give it a shot.

Edit: I found the make targets, We should add one for BJData.

[nlohmann]

1. Add a target fuzz_testing_bjdata to Makefile and copy the code from fuzz_testing_ubjson and just replace all occurrences of ubjson with bjdata.
2. Call afl-fuzz -i fuzz-testing/testcases -o fuzz-testing/out fuzz-testing/fuzzer

I haven't tried this in a while. LibFuzzer also worked once - I should add a proper documentation for this... (added #3477)

[falbrechtskirchinger]

Fuzzer is running. Will report back when it finds something.

Edit: I switched to AFL++ and the fuzzer has now been running for almost 5h with only one crash due to a stack overflow.

[nlohmann]

I added documentation how to use the fuzzers: #3478

Feedback welcome!

[nlohmann]

FYI: LibFuzzer immediately detects similar errors in the BJData parser:

crash-1acc1496ec2710ad0bfbc648dd720375ae1137b9
00000000: 5b23 6c5b 23a3 a3a3 a3a3 00              [#l[#......

crash-3a2724760bdeeb68448156339fc43ea3db142904
00000000: 5b5b 236c a3a3 a3a3 a3a3 00              [[#l.......

crash-8e50bc54cb9d32b0632daeca7721b00f29e0a0ae
00000000: 7b23 69cc 0000 4c                        {#i...L

crash-39fe215fb1a2c59fdd80e2cf0524fe2c6ac7c27f
00000000: 5b23 6c90 9090 9090 9090 9090 9090 9090  [#l.............
00000010: 9090 9090 9090 9090 9090 9090 9090 9090  ................
00000020: 9090 9090 9090 9090 9090 9090 9090 9090  ................
00000030: 9090 9090 9090 9090 9080 0000 00         .............

crash-70b54ba2df5d9a423a3540e97f1ea88be7263599
00000000: 5b23 6ca3 a3a3 a374 00                   [#l....t.

crash-b6d108368cf5ce2632ebf9865e7f06d66eafffc4
00000000: 5b23 6ca3 a3a3 fe                        [#l....

crash-fec4863ffbee79a6ec21b993c2b2c078552bb456
00000000: 5b23 6c80 236c 8000                      [#l.#l..

[falbrechtskirchinger]

Indeed. It fails within seconds. Now I'm wondering if I made a mistake with AFL++...

[nlohmann]

Indeed. It fails within seconds. Now I'm wondering if I made a mistake with AFL++...

You should be able to pass the failing example from libFuzzer to the AFL binary and see how it reacts. I only played around a bit with afl++ in Docker just long enough to write the documentation. I did not wait for an error either.

[falbrechtskirchinger]

I've tried again using the redqueen mutator (also in persistent mode, which is significantly faster) and I'm getting thousands of crashes in a few minutes (6 unique ones so far).

[nlohmann]

Can the persistent mode be used together with libFuzzer or do we still need a wrapper?

[falbrechtskirchinger]

If by wrapper you're referring to fuzzer-driver_afl.cpp then yes, it is still needed. It's quite easy to modify it for persistent mode:
https://github.com/AFLplusplus/AFLplusplus/blob/stable/instrumentation/README.persistent_mode.md#2-tldr

[falbrechtskirchinger]

@fangq bool get_ubjson_array() seems to be missing a call to sax->start_object()?

Triggered by this input:

std::vector<std::uint8_t> vec1{0x5b, 0x5b, 0x5d, 0x5b, 0x24, 0x44, 0x23, 0x69, 0xe5};

Near the end of the snippet there's a call to sax->key() without a previous call to sax->start_object().

    bool get_ubjson_array()
    {
        std::pair<std::size_t, char_int_type> size_and_type;
        if (JSON_HEDLEY_UNLIKELY(!get_ubjson_size_type(size_and_type)))
        {
            return false;
        }

        // detect and encode bjdata ndarray as an object in JData annotated array format (https://github.com/NeuroJSON/jdata):
        // {"_ArrayType_" : "typeid", "_ArraySize_" : [n1, n2, ...], "_ArrayData_" : [v1, v2, ...]}

        if (input_format == input_format_t::bjdata && size_and_type.first != string_t::npos && size_and_type.first >= (1ull << (sizeof(std::size_t) * 8 - 1)))
        {
            std::map<char_int_type, string_t> bjdtype = {{'U', "uint8"},  {'i', "int8"},  {'u', "uint16"}, {'I', "int16"},
                {'m', "uint32"}, {'l', "int32"}, {'M', "uint64"}, {'L', "int64"}, {'d', "single"}, {'D', "double"}, {'C', "char"}
            };

            string_t key = "_ArrayType_";
            if (JSON_HEDLEY_UNLIKELY(bjdtype.count(size_and_type.second) == 0 || !sax->key(key) || !sax->string(bjdtype[size_and_type.second]) ))
            {
                return false;
            }

Edit:
Adding || !sax->start_object(2) avoids the segfault. (Test input throws out_of_range exception.)

            string_t key = "_ArrayType_";
            if (JSON_HEDLEY_UNLIKELY(bjdtype.count(size_and_type.second) == 0 || !sax->start_object(2) || !sax->key(key) || !sax->string(bjdtype[size_and_type.second]) ))
            {
                return false;
            }

[fangq]

@falbrechtskirchinger, thanks for troubleshooting this.

when an ND-array construct is parses, the sax->start_object call was initiated here:

json/include/nlohmann/detail/input/binary_reader.hpp

Line 2122 in b205361

if (JSON_HEDLEY_UNLIKELY(!sax->start_object(3) || !sax->key(key) || !sax->start_array(dim.size())))

3 keys are expected: _ArraySize_ is written inside the above block in get_ubjson_size_value, and the remaining two fields _ArrayType_ and _ArrayData_ are written inside the caller get_ubjson_array, i.e. where you found the sax->key().

The caller get_ubjson_array uses size_and_type.first to tell if an object has been initiated: if the highest bit of size_and_type.first is 1, set here

json/include/nlohmann/detail/input/binary_reader.hpp

Line 2135 in b205361

result |= (1ull << (sizeof(result) * 8 - 1)); // low 63 bit of result stores the total element count, sign-bit indicates ndarray

, then it assumes it is already inside an object of 3 keys with one already written (_ArraySize_), and then, just keep writing the remaining two keys.

I suppose using the highest bit of size_and_type.first may overlap with something else and fails to carry this information.

[falbrechtskirchinger]

@fangq Ah, thanks for clarifying. That makes sense. Otherwise, I'm sure a missing sax->start_object() call would have caused failures sooner.

[fangq]

I think I know what happened - in all of these cases, the length following # markers are erroneously negative, however, because I used the sign-bit for ndarray, so it proceeds with writing an ND array object.

looks like I should find another way to indicate that I am in the middle of decoding an ND array, or throw an error in-place when the length in a non-NDarray construct # <int> is negative.

can I query if I am inside an object using sax functions?

[falbrechtskirchinger]

I was just going to write that. :-)

Unfortunately, the SAX interface is one-way only. You cannot query it. I think you might want to create a struct to replace the std::pair and add a dedicated boolean field. Or, encode it in the type instead (bit 7 maybe if that is free)?

[nlohmann]

I have the feeling there is still a lot in flux for BJData - in particular since the written format is not yet fully optimized. Any idea how long it would take to complete this?

[fangq]

@nlohmann and @falbrechtskirchinger, the fuzzer errors should now be fixed with the above commit. All CI tests have passed.

[fangq]

in particular since the written format is not yet fully optimized. Any idea how long it would take to complete this?

I noticed that not just bjdata output file has room to compress, UBJSON output can also generate smaller sizes if the same_prefix lambda function can be further optimized

for example

json j=json({1,2,127,128});
std::vector<std::uint8_t> vec1 = json::to_ubjson(j,true,true);

because ubjson_prefix returns i for the first 3 numbers, but U for the last number, so same_prefix returned false and this array outputs as [ # i 4 i 1 i 2 i 127 U 128. If the same_prefix can find the max and min of the numbers in the vector, and use the lowest data type to contain both ends (or test max of the absolute value, combined with the sign), that could produce a more compact buffer [ $ U # i 3 1 2 127 128. The space saving is more significant when the vector size grows.

[falbrechtskirchinger]

As promised, here's my list of test inputs that are triggering assertion failures:

Edit: They are indeed all fixed by #3479. Including the one reported by Niels. :-)

// (1) Niels' input from the issue description
std::vector<std::uint8_t> vec1{0x5b, 0x23, 0x49, 0x20, 0xff};

// (2) fixed by #3479
std::vector<std::uint8_t> vec1{0x5b, 0x5b, 0x5d, 0x5b, 0x24, 0x44, 0x23, 0x69, 0xe5};
// can be simplified to
std::vector<std::uint8_t> vec1{0x5b, 0x24, 0x44, 0x23, 0x69, 0xe5};

// (3) fixed by #3479
std::vector<std::uint8_t> vec1{0x7b, 0x23, 0x4d, 0x76, 0xdd, 0x5d, 0x48, 0x5b, 0x00, 0x49, 0x83, 0x83, 0x49, 0x7b, 0xdd, 0x5b, 0x49, 0x5d, 0x6c, 0x22, 0x5b, 0x4d, 0x83, 0xdd, 0x5d, 0x5d, 0x6c, 0x22, 0x5b, 0x00, 0x48, 0x5b};

// (4) fixed by #3479
std::vector<std::uint8_t> vec1{0x7b, 0x23, 0x4d, 0x83, 0x2c, 0x5b, 0x4d, 0x83, 0xff, 0xff, 0xff, 0xff};

// (5) fixed by #3479
std::vector<std::uint8_t> vec1{0x5b, 0x24, 0x49, 0x23, 0x69, 0xd9, 0x7b, 0x71, 0x65, 0x38, 0x49, 0x62, 0x00, 0x04, 0x7b, 0x49, 0x00, 0x62, 0x94, 0x61, 0x2d, 0x56, 0x00, 0x69, 0xd0, 0x2b, 0xd4, 0xca, 0xfc, 0x7f, 0x00, 0x00, 0x00, 0x00, 0x00, 0x1f, 0xff, 0xfb, 0x00, 0x00, 0x00, 0x00, 0xde, 0xde, 0xfa, 0xde, 0xde, 0xde, 0xde, 0xc7, 0xde, 0xde, 0xde, 0xde, 0xde, 0xde, 0xde, 0xde, 0xde, 0xde, 0xde, 0xde, 0xde, 0xde, 0xde, 0x00, 0x49, 0x01, 0x00, 0xf7, 0xff, 0xff, 0xff, 0x00, 0x48, 0x00, 0x00, 0x00, 0x00, 0xff, 0x7f, 0x5b, 0x74, 0x31, 0x39, 0x5f, 0x53, 0x70, 0x5f, 0x6d, 0x61, 0x6b, 0x65, 0x5f, 0x73, 0x68, 0x67, 0x5f, 0x6b, 0x53, 0x74, 0x31, 0x43, 0x69, 0x61, 0x87, 0x65, 0xff, 0xff, 0x74, 0x61, 0x67};

// (6) fixed by #3479
std::vector<std::uint8_t> vec1{0x7b, 0x23, 0x4d, 0xed, 0xed, 0xed, 0xed, 0xed, 0xed, 0xed, 0xed, 0xed};

// (7) fixed by #3479
std::vector<std::uint8_t> vec1{0x5b, 0x24, 0x49, 0x23, 0x69, 0xf4, 0x40, 0x00, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x58, 0x49, 0x69, 0x49, 0x49, 0x31, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x49, 0x02, 0xd2};

// (8) fixed by #3479
std::vector<std::uint8_t> vec1{0x7b, 0x23, 0x4d, 0x83, 0x22, 0x5b, 0x4d, 0x83, 0xdd, 0x5d, 0xff, 0xff, 0x00, 0xff, 0xff, 0xff, 0xff, 0x7f, 0x5d, 0x6c};

[falbrechtskirchinger]

It seems to me, that various input results in a discarded value without raising an exception.

@nlohmann That is only expected if any SAX call returns false, correct?

For example, these if statements in get_ubjson_object() should both return sax->parse_error(...)?

        std::pair<std::size_t, char_int_type> size_and_type;
        if (JSON_HEDLEY_UNLIKELY(!get_ubjson_size_type(size_and_type)))
        {
            return false;
        }

        if (input_format == input_format_t::bjdata && size_and_type.first != string_t::npos && size_and_type.first >= (1ull << (sizeof(std::size_t) * 8 - 1)))
        {
            return false;
        }

Likewise, statements like these

                    if (JSON_HEDLEY_UNLIKELY(!get_ubjson_string(key) || !sax->key(key)))
                    {
                        return false;
                    }

should be separated so that a parse error can be raised when get_ubjson_string(key) fails.

[nlohmann]

Yes, the binary parsers all end with

return res ? result : basic_json(value_t::discarded);

where res is the bool returned by json_sax_dom_parser. That one can return false in two situations:

• A parse error occurs and allow_exceptions is true.
• A function in the SAX parser returns false.

It seems you're right.

[falbrechtskirchinger]

Can the persistent mode be used together with libFuzzer or do we still need a wrapper?

I think I was wrong about that. AFL++ ships with a libFuzzer driver that supposedly uses persistent mode.
https://github.com/AFLplusplus/AFLplusplus/blob/stable/docs/fuzzing_in_depth.md#g-libfuzzer-fuzzer-harnesses-with-llvmfuzzertestoneinput

[nlohmann]

I got a confirmation from OSS-Fuzz that the issue is fixed now. Thanks @fangq and @falbrechtskirchinger for the quick help!