crystal-lang
algorithm complexity attack on big
require "big"
BigDecimal.new("1e10000000000")
block and cup 100% and memory 100%
require "bigdecimal"
BigDecimal.new("1e10000000000")
ruby is ok
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] ???
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.
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.
should we have a 64bits version of Decimal, more time, we just want Decimal, not Big.
BigDecimal.new("1e1000000000000000000")
# gmp: overflow in mpz type
add more zero, it crash.
In Ruby:
> BigDecimal("1e10000000000000000000")
=> Infinity
Interesting... 🤔
But I don't know whether we can do the same. It's the same issue for BigInt.
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.
there is no "attack" here, it's a developer self-destructing their code manually
happens in literally every language
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
