Panic with unordered range when parsing MinidumpLinuxMaps

This is mostly a note so that I don't forget about this, I don't have the time to fix it right at this moment, and I don't want it to be forgotten about.

This test:

#[test]
fn test_backwards_range() {
    let data = include_bytes!("../../testdata/invalid-range.dmp");

    match Minidump::read(&data[..]) {
        Ok(f) => {
            let e = f.get_stream::<MinidumpLinuxMaps>().unwrap_err();
            assert_eq!(e, Error::DataError);
        }
        Err(e) => {
            panic!("Expected to parse the header, got {:?}", e);
        }
    }
}

With this data:

b"MDMP\x93\xa7\x0e\x00\x04\x00\x00\x00\x02\x00\x00\x00\x00\x03\x00zM\x00\x00\x04\x00\x00\n\n\x01\x00\x00\xde\n\x07\x93\xa7\xa7\x15\t\x00gG\x02\x01\x00\x00\x00\x00\x00\x00\x15\t\x00gG(\x00\x00\x08\x00\x00\x00\n\n\n\x08\n\n\n\xc1\n\x08\n\n\ne0-A\n\x08\n\r\rA\n\x08\n\x00\x04\x00\xe3\xf9\x01\x00\x00\x00\x00\x03}\n\n\n\nA\n\x08\n\n\nA\n\r\r\r\r\r\r\r\r\r\r\r\r\r\n\n\nA\n\x08\n\n\n0-A\n\x08\n\r\n\n\n\n\nA\n\x08\n\n\x00\n\n\n\x00\x00\n\x00\x00\x00\x00\x0e\x00\x04\x00\xe3\xe3\xf9\x01\x00\x00\x00\x00\x03\n\n\n\nA\x00\x00\x15\t\x00gG(\x00\x00\x08\x00\x00\x00\n\n\n\x08\n\n\n\xc1\n\x08\n\n\n0-A\n\x08\n\r\rA\n\x08\n\x00\x04\x00\nA\n\r\r\r\r\r\r\r\r\r\r\r\r\r\n\n\n\nA\n\x08\n\n\nA\n\x08\n\n\x00\x04\n\n\x00\x00\n\x00\r\xf3\x8c\xf3\xf3\xf3\xf3\t\x00g\xf7\xf7\xf7\xf7w"

Panics with this error

thread 'test_backwards_range' panicked at 'Ranges must be ordered', /home/jess/.cargo/registry/src/github.com-1ecc6299db9ec823/range-map-0.1.5/src/lib.rs:47:13

Looks like IntoRangeMapSafe::into_rangemap_safe is probably not doing enough checks, and is letting something invalid through. Or, at least, that's where I'm planning to investigate putting the fix, I still don't fully understand what it is.

Going to claim this issue for now, but if I go more than a few days without fixing it, feel free to do it.

[luser]

Huh, interesting! into_rangemap_safe tries very hard to sanitize what it puts into the RangeMap, but clearly there's some edge cases it misses.

Thanks for all the fuzz testing!

[luser]

If desired, I bet we could make a simple fuzzer-friendly interface to fuzz into_range_map more directly. Like, we could just parse a byte stream as pairs of N-byte integers and then let _map: RangeMap<uNN, ()> = values.into_rangemap_safe();.

[Gankra]

NB into_rangemap_safe is my arch-nemesis, and there's now a copy of it in breakpad-symbols because the interface is a mess:

https://github.com/luser/rust-minidump/blob/1c5f5f81f4431f358d5342c7e1114b0737949474/breakpad-symbols/src/sym_file/parser.rs#L576-L593

We also do some jank pre-processing of the inputs to try to make it do more useful things:

https://github.com/luser/rust-minidump/blob/1c5f5f81f4431f358d5342c7e1114b0737949474/breakpad-symbols/src/sym_file/parser.rs#L446-L481

I would love to have a more principled and useful thing here than this weird sorted-array-wrapper.

[luser]

Keep in mind that Breakpad has a giant pile of hacks accumulated over the years to special-case all sorts of nonsense that breaks this in real-world use:
https://chromium.googlesource.com/breakpad/breakpad/+/772cfc1db6374b793a4a717466d3efc4effee12b/src/processor/minidump.cc#2786

Gotta love that someone gave up and added a bool is_android in there.

[saethlin]

The problem is that the check in this function is backwards:
https://github.com/luser/rust-minidump/blob/1c5f5f81f4431f358d5342c7e1114b0737949474/minidump/src/minidump.rs#L2078-L2084
This is actually a logic bug. Finding logic bugs with a fuzzer is always an adventure. I feel like a patch that flips this < around should come with a test case or two, because as far as I can tell all inputs to this function either hit the return None; or panic inside Range::new, which suggests to me that there is no test coverage for this function.

[Gankra]

slaps forehead.

I do have some basic tests for linux_maps that should have caught this, but unfortunately they don't specifically stress the by_addr and memory_info_at_address path. Instead it just queries the unordered iterator which is basically a plain Vec of the parsed input without any Range stuff.

https://github.com/luser/rust-minidump/blob/1c5f5f81f4431f358d5342c7e1114b0737949474/minidump/src/minidump.rs#L4965-L4970

The tests should be updated to also check the results reported by these APIs:

https://github.com/luser/rust-minidump/blob/1c5f5f81f4431f358d5342c7e1114b0737949474/minidump/src/minidump.rs#L1858-L1862

https://github.com/luser/rust-minidump/blob/1c5f5f81f4431f358d5342c7e1114b0737949474/minidump/src/minidump.rs#L1846-L1850

I stand by assuming it was into_rangemap_safe's fault, but yeah my tests just weren't thorough enough.