入门例子

二分查找算法是非常经典的算法，它看似简单，但是写出一个完全正确的二分查找算法还是比较考验工程师的算法功力的，下面是在网上流传的一个版本，请读者思考：这个程序正确吗？

#include <iostream>
#include <vector>

size_t binary_search(std::vector<int> &nums, int target)
{
    size_t left = 0, right = nums.size();
    while (left < right)
    {
        size_t mid = left + (right - left - 1) / 2;
        if (nums[mid] == target)
        {
            return mid;
        }
        else if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid;
        }
    }
    return nums[left] == target ? left : -1;
}

int main()
{
    std::vector<int> a = {2};
    int target = 3;
    std::cout << binary_search(a, target) << std::endl;
}

运行上述程序后输出 -1，显然是符合预期的，那这是否就说明这个程序是完全正确呢？

答案是：这个程序是存在错误的。那错在哪一句呢？读者可以通过分析发现问题所在，在这里我们尝试使用 asan 工具来定位问题，完整程序在:

https://github.com/dengking/sanitizers/tree/main/asan/examples/heap-buffer-overflow/binary-search-example

其中记录了在不同 OS 上的运行情况。运行程序，可以看到如下输出：

==13564==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x000104e00734 at pc 0x000102a1894c bp 0x00016d3eae60 sp 0x00016d3eae58
READ of size 4 at 0x000104e00734 thread T0
    #0 0x102a18948 in binary_search(std::__1::vector<int, std::__1::allocator<int> >&, int) test.cc:34
    #1 0x102a18cf4 in main test.cc:23
    #2 0x102c5d084 in start+0x200 (dyld:arm64e+0x5084)

通过上述输出我们知道在 test.cc 的 23 行发生了 heap-buffer-overflow，准确的说就是下面这句：

nums[left] == target

通过上述小例子， 展示了 asan 的作用：严格地对程序中的内存访问进行检查，一旦发现访问了不该访问的内存区域，立即汇报准确的错误信息并终止程序，而不是在错误的基础上继续运行导致当程序异常退出时最终表现出的现象非常扑朔迷离，能够帮助工程师快速地定位到程序中与内存相关的 bug。

asan 简介

asan 是在 Google 研发团队于 2011 年发表的论文 AddressSanitizer: A Fast Address Sanity Checker  中提出的，并在 LLVM clang 中实现。论文中对 asan 的优势总结为：

AddressSanitizer achieves efficiency without sacrificing comprehensiveness. Its average slowdown is just73% yet it accurately detects bugs at the point of occurrence.

总的来说，asan 的优势：

• 功能更加全面：能够检查大多数类型的非法内存访问错误

• 更快：asan 是同类工具中对进程运行速度影响最小的

asan 的作用、能力

asan 的核心功能是检测内存访问错误，简单地说就是如果发现程序访问了不该访问的内存，asan 能够及时报告详细的错误信息。更加具体的说：asan 能够发现对 heap object、stack object、global object 的 out-of-bounds access（越界访问）、use-after-free（dangling）等 bug。除了内存访问错误，asan 还能检测一些其它内存错误，比如 Static Initialization Order Fiasco。为了便于读者学习，下面结合 example code 来展示 asan 能够检测的错误。

asan 提供了丰富的 flag 供工程师决定开启或关闭对某种内存错误的检测，这将在 AddressSanitizerFlags 章节进行介绍。

非法内存访问的 example code 

下面结合具体的例子来描述asan的能力，这些例子展示了一些典型的memory error，这些例子主要来自于：

• https://github.com/google/sanitizers/wiki/AddressSanitizer

• https://docs.microsoft.com/en-us/cpp/sanitizers/asan?view=msvc-170

• https://github.com/llvm/llvm-project/tree/main/compiler-rt/test/asan/TestCases

为便于工程师学习使用，我对上述文章中的例子进行了一些调整：

• 为便于跨平台使用 cmake build

• 改写为标准 C++，避免使用 C++ extension

需要注意的是: 

• 不同的编译器对 asan 的支持程度不同，有的编译器并不具备检查出下面罗列的所有内存错误的能力，因此在使用之前，工程师应该使用小程序进行验证，然后再投入到生产环节；

• 不同的编译器对 asan 的实现方式不同、标准库的实现方式也不同，因此相同的程序由不同的编译器生成的可执行文件运行时报出的错误可能不同。

完整的工程在笔者的 GitHub 仓库 sanitizers/asan 中，其中记录了我在不同的编译器上的验证细节，仓库的链接为:

https://github.com/dengking/sanitizers 。

• OOB

  OOB 是 out-of-bound 的缩写，表示越界访问，包括：

  1. overflow：

  更多内容参见-https://en.wikipedia.org/wiki/Buffer_overflow。

  2. underflow

• Dangling

Dangling 的含义是空悬，C++ 语言支持如下两种形式的 indirection:

1. pointer

2. reference

因此 Dangling 可以分为:

1. dangling pointer：

参见-https://en.wikipedia.org/wiki/Dangling_pointer

2. dangling reference：

参见-https://en.cppreference.com/w/cpp/language/reference

概括地说，引发 Dangling 的原因主要包括如下：

UAF：use-after-free

UAR：use-after-return

UAC：use-after-scope

由 Dangling 引发的内存错误有的时候是难以排查的，因为它会导致进程以多种扑朔迷离的方式终止。有一种情况是最终进程会因为访问了不属于自己的内存而被操作系统终止，这是由操作系统对内存的管理机制决定的：当一个进程将内存释放后，操作系统将在未来的某个时间将这片内存区域重新分配给其他进程，因此 Dangling 可能不会立即引起当前进程退出，而是在 OS 将这个内存分配给了其他的进程后，当原进程再次访问时，就会因为访问了不属于自己的内存而将问题暴露，而它的根源其实是 Dangling。下面是 Windows 下当进程“访问了不属于自己的 memory”时的报错：

导致进程访问了不属于自己的内存的原因还包括野指针等，因此由 Dangling 引发的内存错误排查的难度较大。对于这类错误，asan 能够及时发现进而在问题刚刚出现的时候就提示工程师，能够极大地减少排查时间。

• Wild pointer

wild pointer 即野指针，它和 Dangling 类似，在

（https://en.wikipedia.org/wiki/Dangling_pointer）

中将两者放在一起介绍。

• Double free

• Param-overlap

• Invalid pointer pairs

• Strict string check

• Deallocation of Nonallocated Memory

Static Initialization Order Fiasco

asan 的 initialization-order checker 主要是为了帮助工程师发现 Static Initialization Order Fiasco 问题，Static Initialization Order Fiasco 问题的根源在于 C++ 标准对于不同 translation unit 中具备 static storage duration 的 static object 的 dynamic initialization 的相对顺序无法进行统一定义，从而导致当位于不同的 translation unit 中的 static object 的 dynamic initialization 存在依赖关系时，可能会读取到未初始化的内存，进而导致程序错误，更多关于 Static Initialization Order Fiasco 的内容可以参见:

• https://en.cppreference.com/w/cpp/language/siof

• Müller, Johnathan https://www.youtube.com/watch?v=dlTrziwQU-w

• https://github.com/google/sanitizers/wiki/AddressSanitizerInitializationOrderFiasco

为了检测初始化顺序问题，asan 会在已编译的程序中插入“checker”。asan 的 initialization-order checker 默认是关闭的，通过传递运行时标志（run-time flag）来启用它们。asan 的 initialization-order checker 支持如下两种模式：

显然，“Loose init-order checking”在实际发生错误的情况下会及时报告错误，而“Strict init-order checking”则只要发现存在依赖关系，不管实际运行时是否会出现错误，都会报错。

在官方文档

（https://github.com/google/sanitizers/wiki/AddressSanitizerInitializationOrderFiasco）

中给出了非常好的例子来对上述两种模式进行验证，为了便于读者验证，我对它进行了简单的整理，参见：

https://github.com/dengking/sanitizers/tree/main/asan/examples/initialization-order-checker

Mismatch

std::vector

std::vector 是 C++ 工程师最常使用的容器之一，在笔者的 GitHub 仓库 sanitizers/STL 中有关于 std::vector 的总结。

• AddressSanitizerContainerOverflow

官方文档：

https://github.com/google/sanitizers/wiki/AddressSanitizerContainerOverflow

本节内容需要对 std::vector 的实现原理有一定了解。

给定 std::vector<T> v，当访问位于 [v.end(), v.begin() + v.capacity()) 范围内的元素，这个范围在 v 分配的 heap 内但在当前容器边界之外（容器的边界为 v.end()），asan 认为这是一种内存错误，它会报 “AddressSanitizer: container-overflow”。这种错误也可以归入到 OOB 范畴，此时的 bound 是 v.end()，而不是 heap 的 bound。

下面是展示这种错误的 example code：

由于不同的 STL 对 container 的实现是不同的，因此相同的程序由不同的编译器生成的可执行文件运行时报出的错误可能不同。

asan 对它的检测有赖于对 std::vector 进行特殊实现，一般使用“code annotation”来帮助发现这种错误，如果没有这样做，那么 asan 可能无法发现这种错误。

需要注意的是有时候虽然 asan 会报“AddressSanitizer: container-overflow”这种错误，但是实际上它可能并不会导致程序异常，工程师可以通过如下方式来关闭这种检查从而关闭这种错误:

方式一: 对触发错误的函数关闭检查，这在“让asan关闭检查”章节进行了介绍。

方式二: 通过运行时标志 detect_container_overflow 全局关闭这种检查，asan 支持如下两种方式来传递运行时标志:

• 环境变量 ASAN_OPTIONS

ASAN_OPTIONS=detect_container_overflow=0 

在 AddressSanitizerFlags 章节对 ASAN_OPTIONS 进行了介绍。

• 函数 __asan_default_options

const char*__asan_default_options()
{
    return "detect_container_overflow=0";
}

完整例子:

https://github.com/dengking/sanitizers/blob/main/asan/examples/asan-default-options/detect_container_overflow.cc 。

Access outside of object lifetime in multi-thread application 

C++ 标准对 object lifetime 进行了规范，并明确指出 access outside of lifetime 是错误的，通过 cppreference Storage duration 中的内容可知，每个 C++ object 都对应一片内存区域，这提示我们前面提到的很多内存访问错误都属于“access outside of lifetime”范畴。

在实际开发过程中，更容易发生 access outside of lifetime 的情况是在多线程程序中，由于篇幅有限，关于这个 topic 的内容可以参见笔者的笔记：

如何开启 asan

cmake-based-project 

下面两种方式各有优劣，适合于不同的工程: 

第一种：

set (CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -fno-omit-frame-pointer -fsanitize=address")
set (CMAKE_C_FLAGS_DEBUG "${CMAKE_C_FLAGS_DEBUG} -fno-omit-frame-pointer -fsanitize=address")
set (CMAKE_LINKER_FLAGS_DEBUG "${CMAKE_LINKER_FLAGS_DEBUG} -fno-omit-frame-pointer -fsanitize=address")

二、arsenm/sanitizers-cmake

项目链接: https://github.com/arsenm/sanitizers-cmake

优势:  sanitizers-cmake 是一个 cmake package，它使用起来比较方便，能够帮助 cmake-based project 快速地开启各种 sanitizers，目前在 litesdk 中已经尝试使用了。

劣势:

• 不支持 Windows

• 不适合于有很多 target 的项目

IDE 

• Visual Studio 

参考：https://devblogs.microsoft.com/cppblog/addresssanitizer-asan-for-windows-with-msvc/

• xcode

参考：https://developer.apple.com/documentation/xcode/diagnosing-memory-thread-and-crash-issues-early

AddressSanitizerFlags

官方文档:

https://github.com/google/sanitizers/wiki/AddressSanitizerFlags

asan 提供了丰富的 flag 来供使用者对它进行灵活的调整。

Compiler flags 

Run-time flags

Sanitizers 的 run-time flag 非常多，它可以分为两大类:

• common flag

  这些 flag 并不专属于特定 Sanitizer 而是所有的 Sanitizer 公用的，完整列表参见：

  https://github.com/google/sanitizers/wiki/SanitizerCommonFlags 。

• sanitizer flag

  这些 flag 是专属于特定 Sanitizer 的，在介绍对应的 Sanitizer 的时候会进行专门介绍。

  asan 的 run time flag 比较多，完整列表参见：

  https://github.com/google/sanitizers/wiki/AddressSanitizerFlags ，可以分为如下几大类:

  1. 开启/关闭 asan 能力的 flag

  2. 调节 asan 的 resource usage 的 flag

设置 flag 的两种方式

asan 支持如下两种方式来传递 run-time flags，工程师可以根据实际情况选取合适的方式。

1. 环境变 ASAN_OPTIONS 

   ASAN_OPTIONS 是环境变量，在不同的 OS 中，设置的方式不同。

2. 函数 __asan_default_options

使用该函数来将 run-time flags 嵌入代码中，例子:

https://github.com/dengking/sanitizers/tree/main/asan/examples/asan-default-options

查看完整的 run-time flag

以 macOS 为例，可以通过如下方式来查看 asan 实际支持的完整的 run-time flag：

ASAN_OPTIONS=help=1 ./a.out

例子：

https://github.com/dengking/sanitizers/tree/main/asan/examples/run-time-flags

开启/关闭 asan能力的flag

asan 的一些能力可以通过 run-time flags 来开启/关闭，本节对此进行总结：

让 asan 关闭检查

出于如下原因想让 asan 不检查特定函数： 

• 不检查一个执行频率比较高的已知是正确的函数来加速应用程序；

• 不检查使用一些偏底层技术（例如，绕过帧边界遍历线程堆栈）的函数；

• 不要报告已知问题。

目前 asan 提供了两种方式来指定不检查指定函数:

• function attribute

• compiler flag: sanitize-blacklist、sanitize-ignorelist

function attribute

使用 C++ 语言的 function attribute 语法特性，完整例子:

https://github.com/dengking/sanitizers/tree/main/asan/examples/turning-off-instrumentation 。

在 https://github.com/dengking/sanitizers/blob/main/asan/examples/turning-off-instrumentation/attribute/no_sanitize_address_attribute.h 中，给出了跨平台的写法。

从目前的实践来看，clang、GCC、MSVC 都支持这种方式。

• clang、gcc

• MSVC

__declspec(no_sanitize_address)

compiler flag: sanitize-blacklist、sanitize-ignorelist

在github Turning off instrumentation

（https://github.com/google/sanitizers/wiki/AddressSanitizer#turning-off-instrumentation）

中，介绍的 compiler flag 是 Sanitize-blacklist，而在 clang Sanitizer special case list

（https://clang.llvm.org/docs/SanitizerSpecialCaseList.html）

中介绍的 compiler flag 是 Sanitize-ignorelist，从实践来看，两者的功能类似，以 clang Sanitizer special case list 为准，使用 Sanitize-ignorelist。

下面是 ignorelist 文件的例子：

# Lines starting with # are ignored.
# Turn off checks for the source file (use absolute path or path relative
# to the current working directory):
src:/path/to/source/file.c
# Turn off checks for a particular functions (use mangled names):
fun:MyFooBar
fun:_Z8MyFooBarv
# Extended regular expressions are supported:
fun:bad_(foo|bar)
src:bad_source[1-9].c
# Shell like usage of * is supported (* is treated as .*):
src:bad/sources/*
fun:*BadFunction*
# Specific sanitizer tools may introduce categories.
src:/special/path/*=special_sources
# Sections can be used to limit ignorelist entries to specific sanitizers
[address]
fun:*BadASanFunc*
# Section names are regular expressions
[cfi-vcall|cfi-icall]
fun:*BadCfiCall
# Entries without sections are placed into [*] and apply to all sanitizers

AddressSanitizerCallStack

官方文档:

https://github.com/google/sanitizers/wiki/AddressSanitizerCallStack

asan 会收集以下事件的调用堆栈：

• malloc and free

• thread creation

• failure

malloc 和 free 发生相对频繁，因此快速展开调用堆栈很重要，否则会影响性能。asan 使用一个简单的 unwinder 来展开调用堆栈，它依赖于帧指针。

如果不关心 malloc/free 调用堆栈，可以通过设置运行时标识 malloc_context_size=0 来完全禁用。

为了使错误信息能够包含源代码信息以便于工程师定位，每个栈帧都需要符号化（前提是二进制产物是以 debug 模式编译的），在符号化后，给定 PC 寄存器，asan 能够打印

#0xabcdf function_name file_name.cc:1234

asan 对栈帧的符号化是依赖于 symbolizer 可执行程序，不同编译器的 symbolizer 可执行程序不同，比如 clang 使用 llvm-symbolizer。通常情况下，工程师的开发环境的编译器套件已经包含 symbolizer 并且能够正常调用，因此大多数情况下工程师是无需关注 symbolizer。

总的来说，asan 使用 unwinder 来展开调用堆栈，使用 symbolizer 来符号化堆栈。

asan 支持通过环境变量 ASAN_SYMBOLIZER_PATH 来指定 symbolizer 可执行程序，此时需要保证 symbolizer 可执行程序位于 PATH 环境变量中，如果出于某种原因要禁用符号化，可以通过提供空字符串作为 ASAN_SYMBOLIZER_PATH 值来实现，下面以 macOS 为例来说明：

ASAN_SYMBOLIZER_PATH= ./a.out

读者可以使用 examples

（https://github.com/dengking/sanitizers/tree/main/asan/examples） 中的例子进行验证，对比禁用符号化前后的堆栈信息。

Continue after error mode

默认情况下，在发现错误后，asan 会立即让进程 crash，但 asan 支持更改这种默认行为让进程在发现错误后继续运行，这种模式被称为“continue after error mode”，要启用“continue after error mode”，需要使用 -fsanitize-recover=address 进行编译，运行时需要设置 ASAN_OPTIONS=halt_on_error=0

完整例子参见: 

https://github.com/dengking/sanitizers/tree/main/asan/examples/continue-after-error

工程实践

Chromium 工程实践

根据 Google 论文中的介绍, 自从 2011 年 5 月发布 asan 工具以来，开源浏览器 Chromium 已定期使用 asan 进行测试。在测试的前 10 个月中，该工具在 Chromium 代码和第三方库中检测到 300 多个以前未知的错误。210 个 bug 是 heap-use-after-free，73 个是 heap-buffer-overflow，8 个 global-buffer-overflow，7 个 stack-buffer-overflow 和 1 个 memcpy 参数重叠。在另外 13 种情况下，asan 触发了一些其他类型的程序错误（例如，未初始化的内存读取）。

Chromium 主要通过如下两种方法来发现 bug：

• 定期运行单元测试

• 有针对性的 Fuzzing test（模糊测试）

在上述任何一种情况下，开启 asan 后生成产物的运行速度都是至关重要的。对于单元测试，asan 的高性能优势允许使用更少的机器来跟上源代码的变化。对于 Fuzzing test，asan 的性能优势允许在几秒钟内运行随机测试，一旦发现错误，在合理的时间内最小化测试来准确定位问题。通过手动运行开启 asan 后生成的产物也发现了少量错误。

除了 Chromium，Google asan 团队还测试了大量其他代码，发现了很多错误。和 Chromium 一样，heap-use-after-free 是最常见的 bug。然而， stack-buffer-overflow 和 global-buffer-overflow 比 Chromium 更常见。在 LLVM 本身中检测到几个 heap-use-after-free 错误。Google asan 团队也收到了有关 asan 在 Firefox、Perl、Vim 和其他几个开源项目中发现的错误的通知。

Dynamic shared library

例子：https://github.com/dengking/sanitizers/tree/main/asan/examples/dynamic-shared-library 。

后续我们会继续推出 Address Sanitizer 原理篇、Leak Sanitizer 介绍等相关文章。