algorithm complexity attack on big

[pynixwang]

require "big"
BigDecimal.new("1e10000000000")

block and cup 100% and memory 100%

require "bigdecimal"
BigDecimal.new("1e10000000000")

ruby is ok

[watzon]

Good find. For me this is the output I get:

icr(0.28.0) > BigDecimal.new("1e10000000000")
GC Warning: Failed to expand heap by 4179820544 bytes
GC Warning: Failed to expand heap by 4179689472 bytes
GC Warning: Out of Memory! Heap size: 0 MiB. Returning NULL!
Invalid memory access (signal 11) at address 0x0
[0x55fa4df27dc6] *CallStack::print_backtrace:Int32 +118
[0x55fa4df1b300] __crystal_sigfault_handler +192
[0x7f5b6ee944d0] ???
[0x7f5b6efa42d0] __gmpz_n_pow_ui +352
[0x55fa4df69872] *BigInt#**<UInt64>:BigInt +146
[0x55fa4df6b361] *BigDecimal#initialize<String>:UInt64 +4673
[0x55fa4df6a0da] *BigDecimal::new<String>:BigDecimal +90
[0x55fa4df1b3c2] *__icr_exec__:BigDecimal +34
[0x55fa4df0dcf6] __crystal_main +1734
[0x55fa4df6c086] *Crystal::main_user_code<Int32, Pointer(Pointer(UInt8))>:Nil +6
[0x55fa4df6bfe9] *Crystal::main<Int32, Pointer(Pointer(UInt8))>:Int32 +41
[0x55fa4df18776] main +6
[0x7f5b6ec5dce3] __libc_start_main +243
[0x55fa4df0d55e] _start +46
[0x0] ???

[asterite]

Reduced:

require "big"

10.to_big_i ** 10000000000

But ** just delegates to a gmp method. It consumes time and memory by (GMP's) design.

I'm not sure there's a problem to solve here.

[pynixwang]

the problem is e, it 's easy to create a big big number, if we read a user form such as price or amount, and new with BigDecimal, is hard to validate before new, only use regex to test e, and easy to forget to do.

[pynixwang]

should we have a 64bits version of Decimal, more time, we just want Decimal, not Big.

[pynixwang]

BigDecimal.new("1e1000000000000000000")
# gmp: overflow in mpz type

add more zero, it crash.

[asterite]

In Ruby:

> BigDecimal("1e10000000000000000000")
=> Infinity

Interesting... 🤔

But I don't know whether we can do the same. It's the same issue for BigInt.

[pynixwang]

can we have some limitation for gmp, eg max value or max bits.

and limit to a low value, then if we really need big, increment it explicit.

[girng]

there is no "attack" here, it's a developer self-destructing their code manually

happens in literally every language

[pynixwang]

@girng but ruby is ok

[pynixwang]

@girng no more suck.

[HertzDevil]

The actual problem is that BigDecimal#scale in Crystal is a UInt64, so it can express 1e-10000000 very concisely (value == 1.to_big_i, scale == 10000000), but not 1e+10000000 (value == 10.to_big_i ** 10000000, scale == 0). Note that in the former case BigDecimal.new(String) understands the exponent part and doesn't go through BigInt#**.

I'm not sure why scale is unsigned. We based our implementation on bigdecimal-rs, but their scale has always been a signed quantity: https://github.com/akubera/bigdecimal-rs/blob/351411addce5018f6808e85ad7a3460993e81340/src/lib.rs#L173