MySQL Bugs: #69796: Bit-shift operators produce signed integer overflow on large input

Bug #69796	Bit-shift operators produce signed integer overflow on large input
Submitted:	19 Jul 2013 18:19	Modified:	3 Feb 2014 19:10
Reporter:	Arthur O'Dwyer	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Data Types	Severity:	S2 (Serious)
Version:	5.5.13	OS:	Any
Assigned to:		CPU Architecture:	Any

Description:
Item_func_shift_right::val_int() incorrectly truncates the RHS operand before checking for overflow. Item_func_shift_left has a similar bug.

Not only does this truncation give wrong answers on all platforms, but also the computation of "res" is performed before the check for overflow. For example, the computation of (1 << 99) attempts to evaluate (1uLL << 99u) before verifying that (99u < sizeof(longlong)*8). According to the C++ standard, this computation may overflow and invoke undefined behavior. On x86 targets, it benignly truncates the "99" at the sixth bit and computes (1 << 35) instead; but on more exotic targets, the compiler is allowed to generate code that traps or throws an exception.

Certain x86 compilers may even generate code that exposes this behavior; for example, Clang with the new -fsanitize= option. http://blog.regehr.org/archives/963

How to repeat:
select (16 >> 4294967297);    -- returns "8", not "0"
select (16 << 4294967297);    -- returns "32", not "0"
select (16 >> -4294967296);   -- returns "16", not "0"

Suggested fix:
diff --git a/sql/item_func.cc b/sql/item_func.cc
index 3ccecab..0fdf42f 100644
--- a/sql/item_func.cc
+++ b/sql/item_func.cc
@@ -2045,31 +2045,27 @@ double Item_func_cot::val_real()
 longlong Item_func_shift_left::val_int()
 {
   DBUG_ASSERT(fixed == 1);
-  uint shift;
-  ulonglong res= ((ulonglong) args[0]->val_int() <<
-          (shift=(uint) args[1]->val_int()));
   if (args[0]->null_value || args[1]->null_value)
   {
     null_value=1;
     return 0;
   }
+  ulonglong shift = args[1]->val_int();
   null_value=0;
-  return (shift < sizeof(longlong)*8 ? (longlong) res : LL(0));
+  return (shift < sizeof(longlong)*8) ? (ulonglong)args[0]->val_int() << shift : 0;
 }
 
 longlong Item_func_shift_right::val_int()
 {
   DBUG_ASSERT(fixed == 1);
-  uint shift;
-  ulonglong res= (ulonglong) args[0]->val_int() >>
-    (shift=(uint) args[1]->val_int());
   if (args[0]->null_value || args[1]->null_value)
   {
     null_value=1;
     return 0;
   }
+  ulonglong shift = args[1]->val_int();
   null_value=0;
-  return (shift < sizeof(longlong)*8 ? (longlong) res : LL(0));
+  return (shift < sizeof(longlong)*8) ? (ulonglong)args[0]->val_int() >> shift : 0;
 }

Dear Mr. O'Dwyer,

There are several ways in which shift operation can be done. If we write and run a small program in C, like this one:

-------------------------
#include <stdio.h>

int main()
{
unsigned long long ull1 = 16;
unsigned long long ull2 = 4294967297;
long long ll = -4294967296;

printf("16 >> 4294967297: %lld\n", ull1 >> ull2);
printf("16 << 4294967297: %lld\n", ull1 << ull2);
printf("16 >> -4294967296: %lld\n", ull1 >> ll);

exit(0);
}
-------------------------

you will get the results of 8, 32 and 16, just like MySQL server.

To repeat myself, there are several ways to shift an integer to the right or left. Each language defines them differently. SQL does not define how should shift-to-the-right and shift-to-the-left should operate. SQL standard does not have those operations at all. Hence, MySQL is doing it it's own way and, as long as it is coherent and it is, is entitled to do it. Why ???? Because there is no standard , no SQL standard that says ANYTHING about shifting integers. Strictly speaking, until SQL 2003, integer columns, as we know them, were not part of the standard.

What MySQL does and what C does is corresponding more to `rotate` then `shift`. What you are looking for is that MySQL behaves like an assembly language where `shift` and `rotate` are totally different operations. C does not have a separate `rotate` expression. You can write your own `rotate` function as well as your own `shift` function. You have written your own `shift` function which works like the one in assembly languages.

Which one is better, C or assembly, is irrelevant. We can adopt anyone we like, as SQL standards are silent on the issue. We adopted C. Hence, sorry, but not a bug.

Please, don't be discouraged and keep up with reporting any behavior in MySQL that you consider a bug !!!

I am reopening this bug, since it is actually a bug, and in fact leads to the possibility of taking down a MySQL install via a crafted input (via integer overflow at the C level).

Please don't spuriously close this issue again. This has nothing to do with "assembler" or "standard SQL"; it's simply an integer-overflow exploit in a particular path that is specific to MySQL's codebase. I have provided a patch. I strongly recommend that it be adopted.

Crashing a MySQL server is indeed a serious bug.

Please, provide a test case which will crash MySQL server with bit-shift operators and we will be more then happy to verify this bug.

Many thanks in advance.

I wonder if someone would like to give a less condescending reply than Sinisa's, and adopt (something like) the attached patch.

You'll notice that I do not file bogus bugs: http://bugs.mysql.com/search.php?cmd=display&status=Active&reporter=9911107

Arthur,

This is now a verified bug and as such, it will be scheduled for both the planning and fixing stages.

asan build outputs (on larger random tests):

./sql/item_func.cc:2716:50: runtime error: shift exponent 4223865762 is too large for 64-bit type 'ulonglong' (aka 'unsigned long long')
./sql/item_func.cc:2731:49: runtime error: shift exponent 33430 is too large for 64-bit type 'ulonglong' (aka 'unsigned long long')