整数溢出分为无符号整数溢出和 有符号整数溢出

• 无符号整数溢出

对于unsigned 整型溢出,C的规范是有定义的 -- "溢出后的数会以2^(8*sizeof(type))作模运算",

也就是说,如果一个unsigned char(1byte, 8bit)溢出了,会把溢出的值与256求模

以32bit OS 为例

|Type |byte|模:2^(8*sizeof(type))|

|unsigned char |1 |2^8 = 256 |

|unsigned short |2 |2^16 = 65536 |

|unsigned int |4 |2^32 = 4294967296 |

• Example 1

#include <stdio.h>
int main(int argc, const char * argv[])
{
    //insert code here...
    unsigned char x = 0xff;
    x++;
    printf("x = %d\n", x);
}

上面的代码会输出：0 （因为0xff + 1是256，与2^8求模后就是0.

• 有符号整型溢出

对于signed 整型的溢出,C的规范定义是"undefined behavior",虽然没有定义,各编译器可自己实现,但是大部分的溢出机制是一样的.

有符号整型溢出可分为*向上溢出*和*向下溢出*.假设用k个字节表示一个整型变量,那么这个变量可以表示的有符号整数的范围是-2^(k-1) ~ 2^(k-1)-1,

那么两个正整数或者两个负整数相加就有可能超过这个整型变量所能表示的范围,向上超出 > 2^(k-1)-1称之为向上溢出,向下超出 < -2^(k-1)称之为向下溢出.

对于signed char,正整数最大值为127,负整数最小值为128,(-128 ~ 127) unsigned char 所能表示的最大值为255.

• Example 1

signed char x = 0x7f;
x++;

上面的代码会输出：-128，因为0x7f + 0x01得到0x80，也就是二进制的1000 0000，符号位为1，负数，后面为全0，就是负的最小数，即-128。

• Example 2

signed char x;
x = (-100) + (-100);

上面代码会输出56,因为200的二进制为11001000, -200根据补码的算法, 得出00111000即56.

上面的例子无论是向上溢出还是向下溢出, 绝对值都在相对于无符号整型能表示的范围内.

• Example 3

signed char x;
x = 200 + 200;

对于signed char如果为400, 超出了位数的表示范围,取结果的低八位.

因此上面代码会输出-112, 如果x的结果为负数且超出了255, 则取结果的低八位, 并进行补码的反向操作,减一后取反.

整型溢出的危害

• Example 1: 整型溢出导致死循环

...
...
short len = 0;
...
while (len < MAX_LEN) {
    len += readFromInput(fd, buf);
    buf += len;
}
其中的MAX_LEN可能会是一个比较大的整型,比如32767, short在32位OS中是16bits, 取值范围是-32768 ~ 32767之间.
但是上面的while循环代码有可能会造成整型溢出,而len又是一个有符号的整型,所以可能会成负数,导致不断的死循环.

• Example 2: 整型转型时的溢出

int copy_something(char *buf, int len)
{
    #define MAX_LEN 256
    char mybuf[MAX_LEN];
    ...
    ...
    if (len > MAX_LEN) // <----[1]
    {
        return -1;
    }
    return memcpy(mybuf, buf, len);
}

上面的len是个signed int, 而memcpy则需要一个size_t的len, 也就是一个unsigned 类型.

于是,len会被提升为unsigned, 此时, 如果我们给len传一个负数, 会通过了if的检查,但在memcpy里会被提升为一个正数,于是我们的mybuf就会overflow,

会导致mybuf缓冲区后面的数据被重写.

• Example 3: 分配内存

nresp = packet_get_int();
if (nresp > 0)
{
    response = malloc(nresp*sizeof(char*));
    for (i = 0; i < nresp; i++)
        response[i] = packet_get_string(NULL);
}

上面这个代码中, nresp是size_t类型(size_t 一般就是unsigned int/long int), 这是

一个解析数据包的示例,一般来说,数据包中都会有一个len, 然后后面就是data.

比如准备一个len(在32位系统上,指针占4个字节,unsigned int 的最大值是0xffffffff, 我们只要提供0xffffffff/4的值 -- 0x400000000, 这里我们设置0x400000000 + 1),

nresp 就会读到这个值, 然后nresp*sizeof(char*)就成了1073741825 * 4,于是溢出,结果成了0x1000000004, 然后求模,得到4. 于是malloc(4),

后面的for 循环nresp 次, 用户的数据就会覆盖malloc分配的4字节的空间以及后面的数据,包括程序代码,函数指针,于是就可以改写程序逻辑.

• Example 4: 缓冲区溢出导致安全问题

int func(char *buf1, unsigned int len1,
         char *buf2, unsigned int len2)
{
    char mybuf[256];
    if ((len1 + len2) > 256) //<----[1]
    {
        return -1;
    }
    memcpy(mybuf, buf1, len1);
    memcpy(mybuf + len1, buf2, len2);
    do_some_stuff(mubuf);
    return 0;
}

上面的例子是将buf1和buf2的内容copy到mybuf里, 其中对len1+len2是否超过256做了判断,

但是, 如果len1+len2溢出了,根据unsigned的特性,其会与2^32求模,所以, 基本上来说,上面的代码中的[1]处有可能为假的.

• Addition

• Ex1

void func(unsigned int ui_a, unsigned int ui_b) {
  unsigned int usum = ui_a + ui_b;
  /* ... */
}

• Compliant Solution(Precondition Test)

#include <limits.h>
  
void func(unsigned int ui_a, unsigned int ui_b) {
  unsigned int usum;
  if (UINT_MAX - ui_a < ui_b) {
    /* Handle error */
  } else {
    usum = ui_a + ui_b;
  }
  /* ... */
}

void func(unsigned int ui_a, unsigned int ui_b) {
  unsigned int usum = ui_a + ui_b;
  if (usum < ui_a) {
    /* Handle error */
  }
  /* ... */
}

• Ex2

pen->num_vertices = _cairo_pen_vertices_needed(
  gstate->tolerance, radius, &gstate->ctm
);
pen->vertices = malloc(
  pen->num_vertices * sizeof(cairo_pen_vertex_t)
);

• Compliant Solution

pen->num_vertices = _cairo_pen_vertices_needed(
  gstate->tolerance, radius, &gstate->ctm
);
 
if (pen->num_vertices > SIZE_MAX / sizeof(cairo_pen_vertex_t)) {
  /* Handle error */
}
pen->vertices = malloc(
  pen->num_vertices * sizeof(cairo_pen_vertex_t)
);