关于算法:Sanitizers-系列之-address-sanitizer-用法篇

29次阅读

共计 10194 个字符，预计需要花费 26 分钟才能阅读完成。

入门例子

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

#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/s…

其中记录了在不同 OS 上的运行状况。运行程序，能够看到如下输入：


==13564==ERROR: AddressSanitizer: heap-buffer-overflow on address0x000104e00734 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/san…
  • https://docs.microsoft.com/en…
  • https://github.com/llvm/llvm-…

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

  • 为便于跨平台应用 cmake build
  • 改写为规范 C++，防止应用 C++ extension

须要留神的是: 

  • 不同的编译器对 asan 的反对水平不同，有的编译器并不具备查看出上面列举的所有内存谬误的能力，因而在应用之前，工程师应该应用小程序进行验证，而后再投入到生产环节；
  • 不同的编译器对 asan 的实现形式不同、规范库的实现形式也不同，因而雷同的程序由不同的编译器生成的可执行文件运行时报出的谬误可能不同。

残缺的工程在笔者的 GitHub 仓库 sanitizers/asan 中，其中记录了我在不同的编译器上的验证细节，仓库的链接为:
https://github.com/dengking/s…。

  • OOB

OOB 是 out-of-bound 的缩写，示意越界拜访，包含：

1. overflow：

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

2. underflow

  • Dangling
    Dangling 的含意是空悬，C++ 语言反对如下两种模式的 indirection:

1. pointer

  1. reference

因而 Dangling 能够分为:

  1. dangling pointer：

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

  1. dangling reference：

参见 -https://en.cppreference.com/w…

概括地说，引发 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…）

中将两者放在一起介绍。

  • 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…
  • Müller, Johnathan https://www.youtube.com/watch…
  • https://github.com/google/san…

为了检测初始化程序问题，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/san…）

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

https://github.com/dengking/s…

Mismatch

std::vector

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

  • AddressSanitizerContainerOverflow

官网文档：

https://github.com/google/san…

本节内容须要对 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/s…。

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/san…

劣势:  sanitizers-cmake 是一个 cmake package，它应用起来比拟不便，可能帮忙 cmake-based project 疾速地开启各种 sanitizers，目前在 litesdk 中曾经尝试应用了。

劣势:

不反对 Windows

不适宜于有很多 target 的我的项目

IDE

  • Visual Studio 

参考:

https://devblogs.microsoft.co…

  • xcode

参考：https://developer.apple.com/d…

AddressSanitizerFlags

官网文档:

https://github.com/google/san…

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

Compiler flags

Run-time flags

Sanitizers 的 run-time flag 十分多，它能够分为两大类:

  • common flag

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

https://github.com/google/san…。

  • sanitizer flag

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

asan 的 run time flag 比拟多，残缺列表参见：

https://github.com/google/san…，能够分为如下几大类:

1. 开启 / 敞开 asan 能力的 flag

2. 调节 asan 的 resource usage 的 flag

设置 flag 的两种形式

asan 反对如下两种形式来传递 run-time flags，工程师能够依据理论状况选取适合的形式。

  • 环境变 ASAN_OPTIONS 

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

  • 函数 __asan_default_options

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

https://github.com/dengking/s…

查看残缺的 run-time flag

以 macOS 为例，能够通过如下形式来查看 asan 理论反对的残缺的 run-time flag：


ASAN_OPTIONS=help=1 ./a.out

例子：

https://github.com/dengking/s…

开启 / 敞开 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/s…。

在 https://github.com/dengking/s… 中，给出了跨平台的写法。

从目前的实际来看，clang、GCC、MSVC 都反对这种形式。

  • clang、gcc
  • MSVC

__declspec(no_sanitize_address)

compiler flag: sanitize-blacklist、sanitize-ignorelist

在 github Turning off instrumentation

（https://github.com/google/san…）

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

（https://clang.llvm.org/docs/S…）

中介绍的 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/san…

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/s…）中的例子进行验证，比照禁用符号化前后的堆栈信息。

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/s…

工程实际

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/s…。

后续咱们会持续推出 Address Sanitizer 原理篇、Leak Sanitizer 介绍等相干文章。

正文完
算法
发表至： 算法
2022-10-28
 0
关于算法:如何评价-ChatGPT-回答策略的-ensure-only-ethical-usage-特质
关于算法:机器学习算法八基于BP神经网络的乳腺癌的分类预测
关于算法:FIT1047网络安全系统研究
关于算法:算法学习笔记-day5二叉树