C++ 太复杂了!即使编写的时候非常小心,也不能完全杜绝内存安全问题的出现。就算是算法竞赛时编写的百余行简短代码,也时不时会有数组越界、变量未初始化、未定义行为等问题困扰我们。
在算法竞赛短短几个小时中,花费时间检查这种与算法本身无关的错误,无疑是浪费时间。那有没有什么工具能帮助我们检查这类错误呢?
Sanitizers 是由 Google 发起的一套开源工具集,包含了数个帮助开发者查找 C++ 代码中疑难杂症的工具。其中有些工具,在算法竞赛领域也十分实用。
AddressSanitizer
AddressSanitizer 简称 ASan,可以帮助我们检查代码中的内存使用问题。
它从 LLVM 3.1 起被集成到 Clang 中,从 GCC 4.8 起被集成到 GCC 中。你可以通过在编译参数中添加 -fsanitize=address
来使用它。
解引用悬垂指针
来看一段显然存在问题的代码:
int main() {
char *x = new char[10];
delete[] x;
return x[5];
}
我们申请了一段长度为 10 的 char
数组,随后释放了它,这时我们再取出数组的第 5 个元素——然而这个位置的内存已经被我们释放掉了!
像这种使用已经被释放的内存的问题,我们称之为解引用悬垂指针。让我们试试 ASan 能不能帮我们发现这个问题吧!
首先尝试编译这份代码:
g++ main.cpp -o main -g -fsanitize=address
代码顺利编译,看上去什么都没有发生?不要着急,我们试试执行编译出的程序:
./main
程序崩溃了!同时给出了很长一段错误信息:
=================================================================
==19311==ERROR: AddressSanitizer: heap-use-after-free on address 0x602000000015 at pc 0x562f45c941de bp 0x7ffc3b87b640 sp 0x7ffc3b87b630
READ of size 1 at 0x602000000015 thread T0
#0 0x562f45c941dd in main /home/yur/Workspace/Codes/main.cpp:4
#1 0x7ff979dca28f (/usr/lib/libc.so.6+0x2328f)
#2 0x7ff979dca349 in __libc_start_main (/usr/lib/libc.so.6+0x23349)
#3 0x562f45c940a4 in _start ../sysdeps/x86_64/start.S:115
0x602000000015 is located 5 bytes inside of 10-byte region [0x602000000010,0x60200000001a)
freed by thread T0 here:
#0 0x7ff97a38e35a in operator delete[](void*) /usr/src/debug/gcc/libsanitizer/asan/asan_new_delete.cpp:155
#1 0x562f45c941a1 in main /home/yur/Workspace/Codes/main.cpp:3
#2 0x7ff979dca28f (/usr/lib/libc.so.6+0x2328f)
previously allocated by thread T0 here:
#0 0x7ff97a38d7f2 in operator new[](unsigned long) /usr/src/debug/gcc/libsanitizer/asan/asan_new_delete.cpp:98
#1 0x562f45c9418a in main /home/yur/Workspace/Codes/main.cpp:2
#2 0x7ff979dca28f (/usr/lib/libc.so.6+0x2328f)
SUMMARY: AddressSanitizer: heap-use-after-free /home/yur/Workspace/Codes/main.cpp:4 in main
Shadow bytes around the buggy address:
0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa fa[fd]fd fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8010: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
==19311==ABORTING
通过这段错误信息,我们可以看到 ASan 告诉我们,在 main.cpp
的第 4 行出现了一个 heap-use-after-free
错误,也就是我们在释放了某块堆内存后又使用了它。
不仅如此,它还告诉我们这块内存是在 main.cpp
的第 2 行申请的,在 main.cpp
的第 3 行被释放掉,并且打印出了这三个地方的调用栈!
也就是说,ASan 很好地完成了它的工作,但是是在运行时而不是编译时。这听上去有些令人沮丧,但这已经是最好的结果了,因为很多运行时错误只有在特定的输入下才会出现,在编译时发现它们是不可能的!
换一个角度想想,利用 ASan,我们可以在遇到运行时错误的时候,快速定位到错误的原因,以及发生错误的位置,这已经极大地方便调试了!
全局数组越界
看到这里,你可能会想:好吧 ASan 确实是个很棒的工具,可是在算法竞赛中我们真的很少很少会手动分配堆内存,事实上如果不使用 STL,我的程序可能根本不会用到任何堆内存,那么 ASan 对我来说不就没有用处了吗?
我们来看一段更贴近算法竞赛的,显然存在问题的代码:
#include <iostream>
constexpr int N = 100010;
int n, a[N];
int main() {
for (int i = 0; i < N; ++ i)
a[i] = i;
std::cin >> n;
std::cout << a[n] << std::endl;
return 0;
}
我申请了一个长为 $N$ 的全局数组——这种做法在算法竞赛中很常见,然后我将数组中每个位置的值初始化为它的下标。
接着我们输入了一个 $n$,并输出下标为 $n$ 的位置的值。这太糟糕了!当输入的 $n$ 足够大的时候,这段代码显然会出现数组越界!
让我们再看看 ASan 的表现:
不出所料,ASan 也能检测到这个错误,它告诉我们在 main.cpp
的第 12 行出现了一个 global-buffer-overflow
错误:
=================================================================
==65354==ERROR: AddressSanitizer: global-buffer-overflow on address 0x558afdb55f68 at pc 0x558afdaf12e3 bp 0x7fff39a9d580 sp 0x7fff39a9d570
READ of size 4 at 0x558afdb55f68 thread T0
#0 0x558afdaf12e2 in main /home/yur/Workspace/Codes/main.cpp:12
#1 0x7fc18ed9c28f (/usr/lib/libc.so.6+0x2328f)
#2 0x7fc18ed9c349 in __libc_start_main (/usr/lib/libc.so.6+0x23349)
#3 0x558afdaf1124 in _start ../sysdeps/x86_64/start.S:115
0x558afdb55f68 is located 0 bytes to the right of global variable 'a' defined in 'main.cpp:5:8' (0x558afdaf44c0) of size 400040
SUMMARY: AddressSanitizer: global-buffer-overflow /home/yur/Workspace/Codes/main.cpp:12 in main
Shadow bytes around the buggy address:
0x0ab1dfb62b90: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab1dfb62ba0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab1dfb62bb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab1dfb62bc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab1dfb62bd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0ab1dfb62be0: 00 00 00 00 00 00 00 00 00 00 00 00 00[f9]f9 f9
0x0ab1dfb62bf0: f9 f9 f9 f9 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab1dfb62c00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab1dfb62c10: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab1dfb62c20: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x0ab1dfb62c30: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
Addressable: 00
Partially addressable: 01 02 03 04 05 06 07
Heap left redzone: fa
Freed heap region: fd
Stack left redzone: f1
Stack mid redzone: f2
Stack right redzone: f3
Stack after return: f5
Stack use after scope: f8
Global redzone: f9
Global init order: f6
Poisoned by user: f7
Container overflow: fc
Array cookie: ac
Intra object redzone: bb
ASan internal: fe
Left alloca redzone: ca
Right alloca redzone: cb
==65354==ABORTING
以及…
除此之外,ASan 还能检测堆栈上数组的越界、使用离开作用域时被析构的对象、初始化顺序导致的 bug、内存泄漏等疑难杂症。由于它们在算法竞赛中出现得较少,这里就不多赘述。
值得一提的是,既然 ASan 是在运行时进行的检测,那它就必然会对程序的效率产生一定影响。经过测试,开启 ASan 后的程序效率平均只有原先的一半左右。这个损失会根据平台和程序的不同而有所不同,但无论如何,请记得在进行重视效率的测试(如测试你的程序执行大样例时是否会超时)时关掉 ASan 以保证测试结果准确。
UndefinedBehaviorSanitizer
UndefinedBehaviorSanitizer 简称 UBSan,可以帮助我们检查代码中的未定义行为。
它从 LLVM 3.3 起被集成到 Clang 中,从 GCC 4.9 起被集成到 GCC 中。你可以通过在编译参数中添加 -fsanitize=undefined
来使用它。
按位位移溢出
int main() {
int x = 42;
x <<= 27;
return 0;
}
上面的代码,按位左移的时候会溢出 int
的上界,这是未定义行为。如果你使用了 UBSan,它会在运行时报错:
main.cpp:3:5: runtime error: left shift of 42 by 27 places cannot be represented in type 'int'
数值溢出
using i64 = long long;
constexpr int mod = 998244353;
int main() {
int x = 114514;
int y = 1919810;
x = ((i64)x * x + y * y) % mod;
return 0;
}
上面的代码,y * y
的部分会溢出 int
的上界,这是未定义行为。如果你使用了 UBSan,它会在运行时报错:
main.cpp:9:23: runtime error: signed integer overflow: 1919810 * 1919810 cannot be represented in type 'int'
使用空指针
#include <iostream>
struct Node {
Node *left, *right;
int value;
Node(int _value):
left(nullptr),
right(nullptr),
value(_value) { }
~Node() {
delete left;
delete right;
}
};
void print(Node *now) {
if (now->left != nullptr)
print(now->left);
printf("%d ", now->value);
if (now->right != nullptr)
print(now->right);
}
int main() {
Node *root = new Node(5);
root->left = new Node(3);
root->right = new Node(8);
root->left->right = new Node(4);
print(root);
delete root;
print(nullptr);
return 0;
}
上面的代码是使用指针实现的简单的二叉树,其中 print
函数存在一个致命的问题:如果传入的参数本身是空指针,它就会在 now->left
这一步对空指针取左儿子,这是未定义行为。如果你使用了 UBSan,它会在运行时报错:
main.cpp:19:12: runtime error: member access within null pointer of type 'struct Node'
如果希望 UBSan 打印出错位置的调用栈,可以在执行程序时加上 UBSAN_OPTIONS=print_stacktrace=1
环境变量:
除此之外…
UBSan 还能检测十数种未定义行为,并且每种未定义行为是否需要被检测可以通过编译参数自由控制。与 ASan 相同的是,UBSan 也会影响程序运行效率,在实际使用时请务必注意!
ThreadSanitizer
ThreadSanitizer 简称 TSan,可以帮助我们检查多线程代码中的数据竞争。
算法竞赛不涉及多线程程序,因此这里不讨论 TSan 相关内容,有兴趣可以自行了解。
MemorySanitizer
MemorySanitizer 简称 MSan,可以帮助我们检查对未初始化的值的使用。
它从 LLVM 4.0 起被集成到 Clang 中。而不幸的是,GCC 并没有集成这个工具。你只能通过在 Clang 中使用 -fsanitize=memory
参数来使用它。
#include <iostream>
// please ignore unused `argv` :)
int main(int argc, char *argv[]) {
int a[10];
for (int i = 2; i < 10; ++ i)
a[i] = i;
int x = a[argc];
int y = x * 2;
if (y == 0) {
std::cout << "Hello" << std::endl;
} else {
std::cout << "MSan" << std::endl;
}
return 0;
}
上面的代码中,当我们通过 ./main
执行程序时,argc
的值将会为 $1$,然而我们没有初始化 a[1]
,MSan 将会在运行时报错:
==95226==WARNING: MemorySanitizer: use-of-uninitialized-value
#0 0x55a96ddb3c96 in main /home/yur/Workspace/Codes/main.cpp:12:7
#1 0x7f1b4f9d628f (/usr/lib/libc.so.6+0x2328f) (BuildId: 1e94beb079e278ac4f2c8bce1f53091548ea1584)
#2 0x7f1b4f9d6349 in __libc_start_main (/usr/lib/libc.so.6+0x23349) (BuildId: 1e94beb079e278ac4f2c8bce1f53091548ea1584)
#3 0x55a96dd221d4 in _start /build/glibc/src/glibc/csu/../sysdeps/x86_64/start.S:115
SUMMARY: MemorySanitizer: use-of-uninitialized-value /home/yur/Workspace/Codes/main.cpp:12:7 in main
Exiting
可以发现,MSan 直到第 12 行 if (y == 0)
处才报错,这是因为 MSan 不会在读取未初始化值时立即报错,而是会等到这个值影响程序执行时才报错!在此之前,它会跟踪并记录这个未初始化值产生的影响。
如果一个未初始化值经过很远的传播后才引发 MSan 报错,你可能得花很大力气才能找到这个值是在哪里产生的。这时你可以选择在编译时加上 -fsanitize-memory-track-origins
参数,这样 MSan 报错时会从最初的未初始化值开始追踪,打印它的每一次移动,直到来到报错的位置:
==96812==WARNING: MemorySanitizer: use-of-uninitialized-value
#0 0x559164b57fe0 in main /home/yur/Workspace/Codes/main.cpp:12:7
#1 0x7fd4af63f28f (/usr/lib/libc.so.6+0x2328f) (BuildId: 1e94beb079e278ac4f2c8bce1f53091548ea1584)
#2 0x7fd4af63f349 in __libc_start_main (/usr/lib/libc.so.6+0x23349) (BuildId: 1e94beb079e278ac4f2c8bce1f53091548ea1584)
#3 0x559164ac61d4 in _start /build/glibc/src/glibc/csu/../sysdeps/x86_64/start.S:115
Uninitialized value was stored to memory at
#0 0x559164b57f5d in main /home/yur/Workspace/Codes/main.cpp:10:7
#1 0x7fd4af63f28f (/usr/lib/libc.so.6+0x2328f) (BuildId: 1e94beb079e278ac4f2c8bce1f53091548ea1584)
Uninitialized value was stored to memory at
#0 0x559164b57e95 in main /home/yur/Workspace/Codes/main.cpp:9:7
#1 0x7fd4af63f28f (/usr/lib/libc.so.6+0x2328f) (BuildId: 1e94beb079e278ac4f2c8bce1f53091548ea1584)
Uninitialized value was created by an allocation of 'a' in the stack frame of function 'main'
#0 0x559164b57920 in main /home/yur/Workspace/Codes/main.cpp:4
SUMMARY: MemorySanitizer: use-of-uninitialized-value /home/yur/Workspace/Codes/main.cpp:12:7 in main
Exiting
Work with sanitizers
上述例子中的所有代码,在开启 GCC 最高级别警告的情况下都不会产生任何警告(最后一个例子的 unused parameter
除外),它们几乎只能在运行时才能发现问题,而这也就是 Sanitizers 的职责所在。
如果你在调试的时候遇到了恼人的「段错误」(运行时错误),而你又没有头绪,不妨试试 Sanitizers 吧。只需要在编译时加上 -fsanitize=address,undefined
参数,然后重新执行样例,兴许就能发现问题了。
才疏学浅,如有纰漏,欢迎指出!
5 条评论
你的文章让我感受到了无尽的欢乐,谢谢分享。 https://www.4006400989.com/qyvideo/95351.html
你的文章内容非常卖力,让人点赞。 http://www.55baobei.com/MCA3U3gLTQ.html
你的文章内容非常卖力,让人点赞。 http://www.55baobei.com/dEIwqQkaio.html
你的文章充满了智慧,让人敬佩。 http://www.55baobei.com/ytAY7MLr9S.html