Panic: attempt to subtract with overflow

[dbrgn]

Decoding the following input file crashes in debug mode (but not in release mode, because overflows silently wrap in release mode).

id:000000,sig:06,src:000000,op:flip2,pos:1027.tar.gz

$ RUST_BACKTRACE=1 cargo run --bin reproduce_decode out/crashes/id\:000000\,sig\:06\,src\:000000\,op\:flip2\,pos\:1027
    Finished dev [unoptimized + debuginfo] target(s) in 0.02s
     Running `target/debug/reproduce_decode 'out/crashes/id:000000,sig:06,src:000000,op:flip2,pos:1027'`
thread 'main' panicked at 'attempt to subtract with overflow', /home/danilo/Projects/jpeg-decoder/src/decoder.rs:760:17
stack backtrace:
   0: backtrace::backtrace::libunwind::trace
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.40/src/backtrace/libunwind.rs:88
   1: backtrace::backtrace::trace_unsynchronized
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.40/src/backtrace/mod.rs:66
   2: std::sys_common::backtrace::_print_fmt
             at src/libstd/sys_common/backtrace.rs:77
   3: <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt
             at src/libstd/sys_common/backtrace.rs:61
   4: core::fmt::write
             at src/libcore/fmt/mod.rs:1028
   5: std::io::Write::write_fmt
             at src/libstd/io/mod.rs:1412
   6: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:65
   7: std::sys_common::backtrace::print
             at src/libstd/sys_common/backtrace.rs:50
   8: std::panicking::default_hook::{{closure}}
             at src/libstd/panicking.rs:188
   9: std::panicking::default_hook
             at src/libstd/panicking.rs:205
  10: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:464
  11: std::panicking::continue_panic_fmt
             at src/libstd/panicking.rs:373
  12: rust_begin_unwind
             at src/libstd/panicking.rs:302
  13: core::panicking::panic_fmt
             at src/libcore/panicking.rs:139
  14: core::panicking::panic
             at src/libcore/panicking.rs:70
  15: jpeg_decoder::decoder::refine_non_zeroes
             at /home/danilo/Projects/jpeg-decoder/src/decoder.rs:760
  16: jpeg_decoder::decoder::decode_block_successive_approximation
             at /home/danilo/Projects/jpeg-decoder/src/decoder.rs:721
  17: jpeg_decoder::decoder::Decoder<R>::decode_scan
             at /home/danilo/Projects/jpeg-decoder/src/decoder.rs:484
  18: jpeg_decoder::decoder::Decoder<R>::decode_internal
             at /home/danilo/Projects/jpeg-decoder/src/decoder.rs:235
  19: jpeg_decoder::decoder::Decoder<R>::decode
             at /home/danilo/Projects/jpeg-decoder/src/decoder.rs:138
  20: reproduce_decode::decode
             at src/reproduce_decode.rs:6
  21: reproduce_decode::main
             at src/reproduce_decode.rs:17
  22: std::rt::lang_start::{{closure}}
             at /rustc/73528e339aae0f17a15ffa49a8ac608f50c6cf14/src/libstd/rt.rs:61
  23: std::rt::lang_start_internal::{{closure}}
             at src/libstd/rt.rs:48
  24: std::panicking::try::do_call
             at src/libstd/panicking.rs:287
  25: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:78
  26: std::panicking::try
             at src/libstd/panicking.rs:265
  27: std::panic::catch_unwind
             at src/libstd/panic.rs:396
  28: std::rt::lang_start_internal
             at src/libstd/rt.rs:47
  29: std::rt::lang_start
             at /rustc/73528e339aae0f17a15ffa49a8ac608f50c6cf14/src/libstd/rt.rs:61
  30: main
  31: __libc_start_main
  32: _start
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

Found using afl (see #131).

Potentially related to #63.

[Shnatsel]

FYI cargo afl build actually compiles with optimizations but with debug assertions and overflow checks enabled, so it's much faster than true debug mode.

[dbrgn]

Ah, interesting. What's the difference between cargo afl build and cargo afl build --release then? Will the latter exclude debug assertions / overflow checks?

[Shnatsel]

I believe the latter will, yes. I'm not 100% sure, test it if you need to rely on that behavior.

[fintelia]

The panic in happening on this line. I don't know the code well enough to say what is going on there or what the right way to handle underflow would be, but it kind of looks like it is trying to compute coefficients[index] = coefficients[index] | bit?

[quilan1]

The panic in happening on this line. I don't know the code well enough to say what is going on there or what the right way to handle underflow would be, but it kind of looks like it is trying to compute coefficients[index] = coefficients[index] | bit?

This is an incorrect reading, although it would make things a lot easier if it were the case. [edit: stuff removed, see next post for a more correct analysis]

To look at the spec:

G.1.2.3 Coding model for subsequent scans of successive approximation
[...]
The run length-magnitude composite value is Huffman coded and each Huffman code is followed by additional bits:
a) One bit codes the sign of the newly non-zero coefficient. A 0-bit codes a negative sign; a 1-bit codes a
positive sign.
b) For each coefficient with a non-zero history, one bit is used to code the correction. A 0-bit means no
correction and a 1-bit means that one shall be added to the (scaled) decoded magnitude of the coefficient.

All that said, I think the current code may be incorrect:

The current code is as follows:

// On coefficients with a non-zero history
// Note: `bit` is (1<<successive_approximation_low)
else if huffman.get_bits(reader, 1)? == 1 && coefficients[index] & bit == 0 {
    if coefficients[index] > 0 {
        coefficients[index] += bit;
    }
    else {
        coefficients[index] -= bit;
    }
}

I believe the check on coefficients[index] & bit == 0 is potentially erroneous, as e.g. if the coefficient is +1 and the adjustment is +1, it should (as I read it) result in +2, instead of remaining at +1. [edit: stuff removed, see next post]

This is a RAW (read-as-written) rather than likely RAI (read-as-intended) interpretation though. I think the RAI is that subsequent approximation passes add on individual bits (the current code); this appears to be the guidance in the spec for encoders to follow. A RAW interpretation is that a poor encoder could encode multiple passes on the same bits, to incrementally increase them or decrease them. I guess this really depends upon how we'd like to handle weird cases like this. Simple encoders would likely be fine with the existing code, but unless I'm reading the spec wrong, I can see cases where this wouldn't be applicable.

---

As for OP's issue, even though it's clearly a pathological case, I think the expected operation here would be a saturating_add / saturating_sub, no?

[quilan1]

Actually, further reading clarified things a bit, apologies. It looks like there are no cases where positive coefficients would be given a negative correction value, or vice-versa.

The first pass (zero-history) should always look like:
Negative value: Huff[XXXX0001] + 0 + 1 => a value of -(1<<successive_approximation_low)
Positive value: Huff[XXXX0001] + 1 + 1 => a value of (1 << successive_approximation_low)

Non-zero history should always look like:
Negative history, increment: 1 => a value of prev_value - (1 << successive_approximation_low)
Positive history, increment: 1 => a value of prev_value + (1 << successive_approximation_low)

I guess we'll consider each case then for the non-zero history:
Negative previous value: 0xFFFE (-2), magnitude increment of 1: result should be 0xFFFD (-3).
Positive previous value: 0x0002 (+2), magnitude increment of 1: result should be 0x0003 (+3).

In the negative coefficient case, a simple | would not yield the correct value.