Understanding integer overflow in C/C++ (2012)

原文：Understanding integer overflow in C/C++

贡献

基于LLVM的开源、运行时IO检查工具IOC，是Clang的扩展；基于SPEC 2000/2006以及一些开源应用，分析了IO的模式和来由，有些是手工的分析；找到了未知漏洞，甚至某些专门消除IO的库，如SafeInt。

动态检测显然会有漏报；有意和无意的回卷需要手工区分；报告的是溢出点，显然有溢出不代表有漏洞。

2011的MITRE报告把IO列入了Top 25最危险的软件错误。

IO的原因：unsigned的回卷是合法和良定义的，很多场合下存在故意的溢出；但C/C++对signed的溢出和超出字节长度的shift操作没有定义。

目前的工作很少能回答下面的问题：

1. 数字错误在C/C++中有多普遍？
2. 编译器将未定义的故意的溢出编译成正确代码的可能性有多大？现在正确不代表以后也正确（此类称为“时间炸弹”）。
3. 故意使用良定义的unsigned回卷有多普遍？

IO成因

良定义的行为

unsigned整数运算是良定义的，但不一定是可移植的。如0U-1明确定义为UINT_MAX，但实际上不同的编译器和平台有不同的解释。

未定义的行为

1. Silent Breakage。编译器可能会对未定义的行为做优化，导致程序行为失常。如把代码中的安全检查优化成了计算1<<32，而这个未定义的行为可能被编译器计算成nop。此外，同样的代码，出现在函数调用里和内联里时，编译器的解释都有可能不一致（Listing 1）。
2. Time Bomb。新版本的编译优化导致老版本里没有问题的行为变成了漏洞。
3. Illusion of Predictability。某些编译器对未定义的行为有自己的理解，但不代表别的编译器也以相同方式理解这些行为。
4. Informal Dialects。编译器采用了比标准更强的语义，如GCC和LLVM的-fwrapv参数，强制signed整数溢出采用补码（two’s complement）
5. Non-Standard Standard。标准本身对溢出的定义也会改变，如1<<31在ANSI C中是要求由编译器实现定义的，到了C99和C11则变成了未定义。极少有人关注标准的变动。又如，由于实现上的困难，极少有编译器正确地给出C99标准对INT_MIN%-1的返回值，0。于是C11将其要求改成了未定义。

工具设计

1600行的代码以扩展的形式在Clang生成AST之后对其进行插桩，以加入溢出检查。另900行代码的运行时库，用于处理程序运行时溢出检查触发的警报。

溢出检查包括：运算执行前对操作结果的预先检查；执行前CPU flag的预查，这个用到了llvm的特殊支持；执行后对字宽扩展的检查。

运行库包括获取溢出点/检查点的操作类型、位置和数据类型信息。平均负载在30%。

IO分析

将IO根据是否有意和是否有定义分为四类，除了有意的已定义行为外，其他的三类都可能导致整数错误。

POSIX对memcpy的src和tgt出现重叠的情况没有定义。

2/3的溢出是unsigned整数，剩下的是signed整数溢出。主要的溢出出现在hashing，需要-fwrapv的溢出检查，比特操作和随机数生成。然而，大部分溢出并不是漏洞。

对于未定义的溢出，现在没有危害不代表以后没有。

除了测试SPEC 2000/2006，还测试了常见的开源应用和库，使用的都是自带的测试用例。只有3个测试对象没有未定义的整数溢出：Kerberos，libpng和libjpeg。