New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Integer overflows in Numeric #3652

Closed
clayton-shopify opened this Issue May 10, 2017 · 0 comments

Comments

Projects
None yet
1 participant
@clayton-shopify
Contributor

clayton-shopify commented May 10, 2017

https://hackerone.com/shikchen reported the following:


Here we show the bug in the mruby with the build config from mruby-engine. So MRB_INT64 and MRB_WORD_BOXING is included in conf.cc.defines. The MRB_INT_MAX of this build is 4611686018427387903 (2^62 - 1). The bug is also presented in other build configurations, but may triggered with different input.

$ mirb
> 2 ** 61 + 2 ** 61
 => 4.6116860184274e+18
> 2.0 ** 62
 => 4.6116860184274e+18
> 2 ** 62
 => -4611686018427387904

Note that the other operators (add, sub, ...) does check the overflow properly.
The root cause of this bug is very subtle. Here is how mruby implements num_pow:

static mrb_value
num_pow(mrb_state *mrb, mrb_value x)
{
  mrb_value y;
  mrb_float d, yv;

  mrb_get_args(mrb, "o", &y);
  yv = mrb_to_flo(mrb, y);
  d = pow(mrb_to_flo(mrb, x), yv);
  if (mrb_fixnum_p(x) && mrb_fixnum_p(y) && FIXABLE(d) && yv > 0 &&
      (d < 0 || (d > 0 && (mrb_int)d > 0)))
    return mrb_fixnum_value((mrb_int)d);
  return mrb_float_value(mrb, d);
}

The key part for overflow checking is FIXABLE, a C macro:

#define POSFIXABLE(f) ((f) <= MRB_INT_MAX)
#define NEGFIXABLE(f) ((f) >= MRB_INT_MIN)
#define FIXABLE(f) (POSFIXABLE(f) && NEGFIXABLE(f))

Unfortunately, C macro expansion is just a typeless simple substitution. Since the variable d is a mrb_float, the constantsMRB_INT_MAX and MRB_INT_MIN are silently promoted from mrb_int to mrb_float as well. But the significand precision of double-precision floating-point is only 53 bits, so this check is passed. We can verify this behavior in python:

$ python
>>> float(2 ** 62) <= float(2 ** 62 - 1)
True

Another subtly failed overflow checking is (d > 0 && (mrb_int)d > 0). Because d is only 2^62, we can convert it to mrb_int without any problem. But when build with MRB_WORD_BOXING, the correspond slot in the mrb_value struct is a 63 bits bit-field:

typedef union mrb_value {
  union {
    void *p;
    struct {
      unsigned int i_flag : MRB_FIXNUM_SHIFT;
      mrb_int i : (MRB_INT_BIT - MRB_FIXNUM_SHIFT);
    };
    // ...
  } value;
  unsigned long w;
} mrb_value;

So the value survives these two checks, but still cause an integer overflow.

When reviewing this bug, I found that in mruby, some functions pass int64_t to FIXABLE like int64_value, which has no problem. But there are many other places pass floating point to FIXABLE like flo_ceil, flo_floor, etc. All of them have the same problem as num_pow.

> (2.0 ** 62).to_i
 => -4611686018427387904
> (2.0 ** 62).ceil
 => -4611686018427387904
> (2.0 ** 62).floor
 => -4611686018427387904

If there is any business logic or boundary check rely on this, it would fail.

A possible fix is split the macro into two macros/functions, like FIXABLE_INT and FIXABLE_FLOAT. I can provide a patch if needed, but I think we may need someone (Matz?) who is familiar with the codebase of mruby to check the impact of this bug.

@matz matz closed this in 06c4933 May 26, 2017

matz added a commit that referenced this issue May 26, 2017

Add new range check macro FIXABLE_FLOAT(); ref #3652
When MRB_INT64, valid value range of mrb_int is bigger than double,
which only has 53 bits significant precision.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment