专栏首页LINUX阅码场AddressSanitizer算法及源码解析

AddressSanitizer算法及源码解析

AddressSanitizer简介

AddressSanitizer是Google用于检测内存各种buffer overflow(Heap buffer overflow, Stack buffer overflow, Global buffer overflow)的一个非常有用的工具。该工具是一个LLVM的Pass,现已集成至llvm中,要是用它可以通过-fsanitizer=address选项使用它。AddressSanitizer的源码位于/lib/Transforms/Instrumentation/AddressSanitizer.cpp中,Runtime-library的源码在llvm的另一个项目compiler-rt的/lib/asan文件夹中。

AddressSanitizer算法

具体的算法可以参考WIKI (https://github.com/google/sanitizers/wiki/AddressSanitizerAlgorithm),在此对AddressSanitizer算法做一个简短的介绍。AddressSanitizer主要包括两部分:插桩(Instrumentation)和动态运行库(Run-time library)。插桩主要是针对在llvm编译器级别对访问内存的操作(store,load,alloca等),将它们进行处理。动态运行库主要提供一些运行时的复杂的功能(比如poison/unpoison shadow memory)以及将malloc,free等系统调用函数hook住。其实该算法的思路很简单,如果想防住Buffer Overflow漏洞,只需要在每块内存区域右端(或两端,能防overflow和underflow)加一块区域(RedZone),使RedZone的区域的影子内存(Shadow Memory)设置为不可写即可。具体的示意图如下图所示。

内存映射

AddressSanitizer保护的主要原理是对程序中的虚拟内存提供粗粒度的影子内存(每8个字节的内存对应一个字节的影子内存),为了减少overhead,就采用了直接内存映射策略,所采用的具体策略如下:Shadow=(Mem >> 3) + offset。每8个字节的内存对应一个字节的影子内存,影子内存中每个字节存取一个数字k,如果k=0,则表示该影子内存对应的8个字节的内存都能访问,如果0<k<7,表示前k个字节可以访问,如果k为负数,不同的数字表示不同的错误(e.g. Stack buffer overflow, Heap buffer overflow)。具体的映射策略如下图所示。

图1: 虚拟地址映射图

插桩

为了防止buffer overflow,需要将原来分配的内存两边分配额外的内存Redzone,并将这两边的内存加锁,设为不能访问状态,这样可以有效的防止buffer overflow(但不能杜绝buffer overflow)。一下是在栈中插桩的一个例子。

未插桩的代码:

插桩后的代码:

动态运行库

在动态运行库中将malloc/free函数进行了替换。在malloc函数中额外的分配了Redzone区域的内存,将与Redzone区域对应的影子内存加锁,主要的内存区域对应的影子内存不加锁。

free函数将所有分配的内存区域加锁,并放到了隔离区域的队列中(保证在一定的时间内不会再被malloc函数分配)。

AddressSanitizer源码分析

AddressSanitizer主要有三种层面的变量:Stack Variable(局部变量),Global Variable, Heap Variable。由于每种变量的生命周期(life time)不同,所以对不同种类的变量处理也是不同的。下面分别从Global Variable,Stack Variable,Heap Variable三个层次来分析AddressSanitizer源码的逻辑结构。

Global Variable

Global Variable存放在程序的数据段。在该算法的实现过程中,处理GlobalVariale的是AddressSanitizerModule类,该类继承自llvm的ModulePass,所以我们先看一下AddressSanitizerModule类的runOnModule(Module &M)方法的处理过程,该过程首先进行一些初始化,然后我们可以看到对Global的插桩方法InstrumentGlobals()方法。

图2: RunOnModule

在InstrumentGlobals()方法中,主要是分成两步:首先,重新声明一个GlobalVariable,这个GlobalVariable包含以前的GlobalVariable和一个RedZone;然后,调用runtime-library将新声明的这个GlobalVariable的RedZone区域加锁。我们先来看第一步的具体实现,如图3所示。

图3: 生成包含RedZone的新的GlobalVariable

下面,我们首先看一下一个Struct结构,该结构记录GlobalVariable存储的首地址,数据的大小,Redzone的大小,Module的名字等信息,便于在Runtime-library中使用。该结构在AddressSanitizerModule和runtime-library中都有相应的定义:

然后我们可以看到对GlobalVariable进行插桩来实现RedZone的Poison和整个GlobalVariable的Poison操作。

具体的Poison RedZone和Poison GlobalVariable的实现在Runtime-library中:

Stack Variable

Stack Variable保存在栈区,在栈中的数据我们需要控制好变量的声明周期(lifetime),当调用一个函数时,会开辟一个栈,栈中的数据会有相应的redzone和shadow memory,并将redzone的shadow memory Poison,当函数结束(正常返回,异常),栈被销毁,需要将数据和redzone清空,其相应的shadow memory也要UnPoison掉。

对于Stack Variable,AddressSanitizer算法中实现了AddressSanitizer类,该类是继承了llvm的FunctionPass,该Pass能够处理每一个函数,在处理每个函数的时候,处理每一个load,store等能够访问内存的指令,在这些指令执行前进行插桩,看其访问的内存是不是被poison。

下面我们主要看一下AddressSanitizer::runOnFunction(Module &M)函数中主要的插桩过程。

在每次访问内存时,都会查看影子内存的值,看其是否是0,如果是0则表示都能访问具体的插桩在instrumentMop函数中,

其中具体的处理过程在instrumentAddress函数中:

Heap Variable

Heap Variable保存在堆区,其分配的函数是malloc函数,该部分的主要代码在runtime-library中,该库中主要是先将malloc的库函数hook住,然后自己定义malloc函数,定义分配策略。

具体的分配策略定义在compiler-rt/lib/asan/asan-allocator.cc文件中,感兴趣可以看一下。

本文来源: http://blog.binpang.me/2017/07/26/AddressSanitizer/

本文分享自微信公众号 - Linux阅码场(LinuxDev)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 一些小知识点

    全局作用域下,let和const声明变量,变量并不会挂载到window上。存在暂时性死区。

    用户3258338
  • C语言入门这一篇就够了-学习笔记

    按照之前的计划,这篇文章本该写C语言简介,包括一些历史背景,发展状况, 语言特点什么的,这些东西着实比较啰嗦。

    诸葛青云
  • 《细说PHP》 第四版 样章 第二章 PHP的应用与发展 4

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    ITXDL
  • C语言进阶system函数

    我们今天来看看在windows操作系统下system () 函数详解(主要是在C语言中的应用)

    老九学堂-小师弟
  • C语言进阶内置函数补充

    1、如果有足够空间用于扩大mem_address指向的内存块,则分配额外内存,并返回mem_address 。这里说的是“扩大”,我们知道,realloc是从堆...

    老九学堂-小师弟
  • 学生时代所学的一些 C 语言知识点回顾(3)——再议指针的声明与使用

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    耕耘实录
  • 初识C语言二维数组

    一维数组只有一个下标,称为一维数组,其数组元素也称为单下标变量。在实际问题中有很多量是二维的或多维的,因此C语言允许构造多维数组。多维数组元素有多个下标,以标识...

    老九学堂-小师弟
  • C语言基本数据类型

    语言中的基本数据类型有整形、字符型、浮点型:单精度型、双精度型;枚举类型、数组等。

    老九学堂-小师弟
  • C语言中的运算符

    C语言运算符是说明特定操作的符号,它是构造C语言表达式的工具。C语言的运算异常丰富,除了控制语句和输入输出以外的几乎所有的基本操作都作为运算符处理。除了常见的三...

    老九学堂-小师弟
  • LeetCode攀登之旅(1)

    给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

    公众号guangcity

扫码关注云+社区

领取腾讯云代金券