Catch potential integer overflows in bigint operations.

runtime/vm/bigint_operations.cc

 // Copyright 2012 Google Inc. All Rights Reserved.
 
 #include "vm/bigint_operations.h"
 
+#include "platform/assert.h"
 #include "platform/utils.h"
 
 #include "vm/double_internals.h"
 #include "vm/exceptions.h"
 #include "vm/object_store.h"
 #include "vm/zone.h"
 
 namespace dart {
 
 RawBigint* BigintOperations::NewFromSmi(const Smi& smi, Heap::Space space) {
@@ skipping 84 matching lines @@
   // recursive call is not negative.
   // We don't catch leading '-'s for zero. Ex: "--0", or "---".
   if (str[0] == '-') {
     const Bigint& result = Bigint::Handle(NewFromCString(&str[1], space));
     result.ToggleSign();
     ASSERT(result.IsZero() || result.IsNegative());
     ASSERT(IsClamped(result));
     return result.raw();
   }
 
-  intptr_t str_length = strlen(str);
+  const intptr_t str_length = strlen(str);
+  if (str_length < 0) {
+    FATAL("Fatal error in BigintOperations::NewFromCString: string too long");
+  }
   if ((str_length > 2) &&
       (str[0] == '0') &&
       ((str[1] == 'x') || (str[1] == 'X'))) {
     const Bigint& result = Bigint::Handle(FromHexCString(&str[2], space));
     ASSERT(IsClamped(result));
     return result.raw();
   } else {
     return FromDecimalCString(str, space);
   }
 }
 
 
 intptr_t BigintOperations::ComputeChunkLength(const char* hex_string) {
   ASSERT(kDigitBitSize % 4 == 0);
-  intptr_t hex_length = strlen(hex_string);
+  const intptr_t hex_length = strlen(hex_string);
+  if (hex_length < 0) {
+    FATAL("Fatal error in BigintOperations::ComputeChunkLength: "
+          "string too long");
+  }
   // Round up.
   intptr_t bigint_length = ((hex_length - 1) / kHexCharsPerDigit) + 1;
   return bigint_length;
 }
 
 
 RawBigint* BigintOperations::FromHexCString(const char* hex_string,
                                             Heap::Space space) {
   // If the string starts with '-' recursively restart the whole operation
   // without the character and then toggle the sign.
@@ skipping 16 matching lines @@
 
 
 RawBigint* BigintOperations::FromDecimalCString(const char* str,
                                                 Heap::Space space) {
   Isolate* isolate = Isolate::Current();
   // Read 8 digits a time. 10^8 < 2^27.
   const int kDigitsPerIteration = 8;
   const Chunk kTenMultiplier = 100000000;
   ASSERT(kDigitBitSize >= 27);
 
-  intptr_t str_length = strlen(str);
+  const intptr_t str_length = strlen(str);
+  if (str_length < 0) {
+    FATAL("Fatal error in BigintOperations::FromDecimalCString: "
+          "string too long");
+  }
   intptr_t str_pos = 0;
 
   // Read first digit separately. This avoids a multiplication and addition.
   // The first digit might also not have kDigitsPerIteration decimal digits.
   int first_digit_decimal_digits = str_length % kDigitsPerIteration;
   Chunk digit = 0;
   for (intptr_t i = 0; i < first_digit_decimal_digits; i++) {
     char c = str[str_pos++];
     ASSERT(('0' <= c) && (c <= '9'));
     digit = digit * 10 + c - '0';
@@ skipping 72 matching lines @@
                                            void* data,
                                            uword (*allocator)(intptr_t size)) {
   NoGCScope no_gc;
 
   ASSERT(kDigitBitSize % 4 == 0);
 
   intptr_t chunk_length = length;
   Chunk* chunk_data = reinterpret_cast<Chunk*>(data);
   if (length == 0) {
     const char* zero = "0x0";
-    const int kLength = strlen(zero);
+    const intptr_t kLength = strlen(zero);
     char* result = reinterpret_cast<char*>(allocator(kLength + 1));
     ASSERT(result != NULL);
     memmove(result, zero, kLength);
     result[kLength] = '\0';
     return result;
   }
   ASSERT(chunk_data != NULL);
 
   // Compute the number of hex-digits that are needed to represent the
   // leading bigint-digit. All other digits need exactly kHexCharsPerDigit
   // characters.
   int leading_hex_digits = 0;
   Chunk leading_digit = chunk_data[chunk_length - 1];
   while (leading_digit != 0) {
     leading_hex_digits++;
     leading_digit >>= 4;
   }
   // Sum up the space that is needed for the string-representation.
   intptr_t required_size = 0;
   if (is_negative) {
     required_size++;  // For the leading "-".
   }
   required_size += 2;  // For the "0x".
   required_size += leading_hex_digits;
   required_size += (chunk_length - 1) * kHexCharsPerDigit;
   required_size++;  // For the trailing '\0'.
+  if (required_size < 0) {
+    FATAL("Fatal error in BigintOperations::ToHexCString: string too long");
+  }

[siva, 2013/09/17 00:19:52]

As discussed offline the overflow could happen before the last computation
making it positive.

We should probably compute a kMaxChunkLen and compare chunk_length against that
and error out.

[Michael Lippautz (Google), 2013/09/17 03:36:50]

Done.

   char* result = reinterpret_cast<char*>(allocator(required_size));
   // Print the number into the string.
   // Start from the last position.
   intptr_t pos = required_size - 1;
   result[pos--] = '\0';
   for (intptr_t i = 0; i < (chunk_length - 1); i++) {
     // Print all non-leading characters (which are printed with
     // kHexCharsPerDigit characters.
     Chunk digit = chunk_data[i];
     for (int j = 0; j < kHexCharsPerDigit; j++) {
@@ skipping 53 matching lines @@
   // Approximate the size of the resulting string. We prefer overestimating
   // to not allocating enough.
   int64_t bit_length = length * kDigitBitSize;
   ASSERT(bit_length > length);
   int64_t decimal_length = (bit_length * kLog2Dividend / kLog2Divisor) + 1;
   // Add one byte for the trailing \0 character.
   int64_t required_size = decimal_length + 1;
   if (bigint.IsNegative()) {
     required_size++;
   }
-  ASSERT(required_size == static_cast<intptr_t>(required_size));
+  if (required_size != static_cast<intptr_t>(required_size)) {

[siva, 2013/09/17 00:19:52]

Ditto comment here too.

[Michael Lippautz (Google), 2013/09/17 03:36:50]

Removed the check, because it's already there (as far as I see) :)
line 345: kMaxAllowedDigitLength (conservative estimate)

One more thing: The code here (line 350+) throws an OOM exception, while the new
checks use the FATAL() macro. Change the new checks to throw an OOM exception,
or leave them?

+    FATAL("Fatal error in BigintOperations::ToDecimalCString: "
+          "string too long");
+  }
   // We will fill the result in the inverse order and then exchange at the end.
   char* result =
       reinterpret_cast<char*>(allocator(static_cast<intptr_t>(required_size)));
   ASSERT(result != NULL);
   int result_pos = 0;
 
   // We divide the input into pieces of ~27 bits which can be efficiently
   // handled.
   const intptr_t kChunkDivisor = 100000000;
   const int kChunkDigits = 8;
@@ skipping 969 matching lines @@
 
 
 void BigintOperations::FromHexCString(const char* hex_string,
                                       const Bigint& value) {
   ASSERT(hex_string[0] != '-');
   intptr_t bigint_length = ComputeChunkLength(hex_string);
   // The bigint's least significant digit (lsd) is at position 0, whereas the
   // given string has it's lsd at the last position.
   // The hex_i index, pointing into the string, starts therefore at the end,
   // whereas the bigint-index (i) starts at 0.
-  intptr_t hex_length = strlen(hex_string);
+  const intptr_t hex_length = strlen(hex_string);
+  if (hex_length < 0) {
+    FATAL("Fatal error in BigintOperations::FromHexCString: string too long");
+  }
   intptr_t hex_i = hex_length - 1;
   for (intptr_t i = 0; i < bigint_length; i++) {
     Chunk digit = 0;
     int shift = 0;
     for (int j = 0; j < kHexCharsPerDigit; j++) {
       // Reads a block of hexadecimal digits and stores it in 'digit'.
       // Ex: "0123456" with kHexCharsPerDigit == 3, hex_i == 6, reads "456".
       if (hex_i < 0) {
         break;
       }
@@ skipping 393 matching lines @@
 int BigintOperations::CountBits(Chunk digit) {
   int result = 0;
   while (digit != 0) {
     digit >>= 1;
     result++;
   }
   return result;
 }
 
 }  // namespace dart