R3：Read/write访存指令插桩（Instrument read/write instructions）：影子值工具需要对访问寄存器或内存的指令进行插桩
R4：Read/write系统调用插桩（Instrument read/write system calls）：系统调用都会涉及到寄存器和/或内存的访问，影子值工具需要对这些系统调用进行插桩

Allocation and deallocation operations

R5：启动时分配插桩（Instrument start-up allocation）：程序启动时，影子值工具需要为所有的寄存器及静态分配的内存位置分配影子值；另外，影子值工具还必须为此时未分配的内存位置创建适当的影子值，用于检测其在被分配之前被错误访问
R6：分配/释放内存区域的系统调用插桩（Instrument system call (de)allocations）：分配内存的系统调用(如brk、mmap)和释放内存的系统调用(munmap)，影子值工具必须对这些操作进行插桩；另外，mremap系统调用使得内存值被复制，相应的影子值也需要被复制
R7：栈分配/释放（Instrument stack (de)allocations）：栈指针更新还涉及栈空间的分配和释放，影子值工具工具必须对这些操作进行插桩
R8：堆分配/释放（Instrument heap (de)allocations）：malloc/realloc/free等用户态堆内存管理函数需要插桩

Transparent execution, but with extra output

R9：额外的输出（Extra output）

总结：作者认为：影子值工具是最重量级的动态二进制分析（Dynamic Binary Analysis,DBA）工具之一；因此，一个能良好支持影子值的动态二进制插桩（Dynamic Binary Analysis, DBI）框架也应该支持大多数DBA工具能够实现的功能。

（注：DBA是工具的作用，DBI是DBA的实现方式）

Valgrind工作原理

Valgrind是一个专为构建重量级DBI工具而设计的框架，首次发布于2002年。最初Valgrind的发行版包含四个工具，其中最受欢迎的是Memcheck（用于内存检测的DBI工具）。

基本架构

Valgrind tools现在是作为Valgrind core插件(plug-ins)的形式存在的，使用C语言编写。

$$ \begin{equation} \text{Valgrind core} + \text{tool plug-in} = \text{Valgrind tool} \end{equation} $$

Valgrind tools的主要工作是对Valgrind core递交的代码进行插桩(instrumentation)。

Valgrind使用动态二进制重编译技术。执行程序命令前添加valgrind --tool=<工具名>，来调用Valgrind工具。指定的工具启动之后，将Client Program加载到同一进程，逐个代码块地重编译

Valgrind core将代码块反汇编为中间表示（Intermediate Representation, IR），然后tools添加分析代码进行插桩，最后由core将其转换回机器代码。插桩后的代码存储在代码缓存中，以便在需要时运行。Client Program的原始代码不会被直接执行。

Valgrind core会处理的代码包括正常的可执行代码、动态链接库/共享库以及动态生成的代码。系统调用内部的代码不受valgrind控制

总结：将Client Program和Valgrind Tool两者放入单个进程中会带来许多复杂性。它们必须要共享许多资源，例如寄存器和内存。此外，在系统调用、信号和线程存在的情况下，Valgrind必须小心不要在处理这些情况时放弃对Client Program的控制，

启动过程

启动阶段的目标是将Valgrind的Core、Tool和Client Program加载到单个进程，共享相同的地址空间。每个Tool都是一个静态链接的可执行文件，包含了Tool的代码和Core的代码。每个Tool都有一个Core的副本会浪费一些磁盘空间（Core大约占2.5MB），但这样做简化了问题。

What’s the difference of section and segment in ELF file format

Valgrind

--num-transtab-sectors=<number>[default:6 for Android platforms, 16 for all others]

Valgrind将Client Program的机器代码分割成小的片段[基本块]并进行转译和插桩。这些转译后的机器代码存储在一个被分成多个sections(sectors)的转译缓存中。如果缓存已满，包含最旧的转译的sector将被清空并重新利用。如果这些旧的转译再次需要，Valgrind必须重新转译和插桩相应的机器代码；另外，sector是按需分配的。一旦分配了某个sector，它将永远不能被释放，并且占用相当大的空间，这取决于tool和–avg-transtab-entry-size选项的值（对于Memcheck来说，每个sector大约占用40MB的空间）。

Client Executable链接后加载到(is linked to load at)0x58000000中，使用gdb打印对应内存：

Magic number (programming)

用户调用的Valgrind可执行文件会扫描其命令行参数以查找–tool选项，并使用execve加载所选工具的静态可执行文件。Valgrind Core首先初始化一些子系统，例如地址空间管理器和自身的内部内存分配器。然后，它加载Client可执行文件（text和data），配置client的堆栈和数据段.

然后，Core通知Tool解析命令行参数并处理相关选项，并初始化更多的core子系统：转译表、信号处理机制、线程调度器，并加载Client Program的调试信息。此时，Valgrind工具完全控制client，并且一切都准备就绪，可以开始从client的第一条指令进行转译和执行。

Guest和Host的寄存器

Valgrind本身在主机的物理CPU上运行，并将Client Program运行在模拟的CPU上。主机CPU中的寄存器称为Host寄存器，将模拟CPU中的寄存器称为Guest寄存器。Valgrind为每个Client线程提供了一个名为“ThreadState”的内存块。ThreadState包含Client Program该线程的所有的寄存器及其相应的Shadow寄存器。

D&R vs. C&A

disassemble-and-resynthesise

首先将机器代码转换为IR，每一条指令对应于一个或者多个IR操作。然后对IR插桩再转回机器代码。Valgrind 使用D&R是与其它DBI 框架最显著区分的单一特征。

copy-and-annotate

原始机器代码指令会被直接复制，每条指令都通过数据结构（如 DynamoRIO）或instruction-querying API（例如 Pin）附带对其效果的描述。

Valgrind IR

每个IR块包含了一个语句（statements）列表，这些语句是具有副作用的操作，例如寄存器写入、内存存储和临时变量赋值。语句包含表达式（expressions），这些表达式代表纯粹的值，例如常量、寄存器读取、内存载入和算术操作。

例如，一个存储语句包含一个用于存储地址的表达式和另一个用于存储值的表达式。

总结：表达式是语句的基本结构。

Valgrind按需翻译代码块。为了创建一个代码块的翻译，Valgrind遵循指令，直到满足以下条件之一：a)达到指令数量限制，b)遇到条件分支，c)遇到未知目标分支，或者d)遇到超过三个已知目标的无条件分支。

分为8个阶段：

Disassembly*: machine code → tree IR
Optimisation 1: tree IR → flat IR
Instrumentation: flat IR → flat IR
Optimisation 2: flat IR → flat IR
Tree building: flat IR → tree IR.
Instruction selection*: tree IR → instruction list
Register allocation: instruction list → instruction list
Assembly*: instruction list→machine code

系统调用

//TODO

IRSB

IRSB表示“IR Super Block”，是单入口, 多出口(single entry, multiple exit)的代码块，包括：

// VEX/pub/libvex_ir.h
typedef
   struct {
      IRTypeEnv* tyenv;
      IRStmt**   stmts;
      Int        stmts_size;
      Int        stmts_used;
      IRExpr*    next;
      IRJumpKind jumpkind;
      Int        offsIP;
   }
   IRSB;

ttyenv：indicates the type of each temporary value present in the IRSB

// VEX/pub/libvex_ir.h
typedef
   struct {
      IRType* types;
      Int     types_size;
      Int     types_used;
   }
   IRTypeEnv;

stmts：a list of statements, which represent code
stmts_size：stmts数组的大小
stmts_used：stmts数组实际使用的条目数量
next：计算下一跳(final jump)的地址
jumpkind：下一跳的类型
offsIP：Instruction Pointer(IP)在machine state中的偏移，在final jump之前会被更新

Tip：由于这些代码块具有多个出口，因此可能会在stmts中有额外的条件退出语句，使得执行流在判定exit之前就离开IRSB中的stmts。同时由于这一点，IRSB可以包含最多3个基本代码块

VexGuestExtents

VexGuestExtents记录了这些分隔的代码块（基本代码块）的信息：

// VEX/pub/libvex.h
// 现在Vex可以跨基本块边界进行处理，因此仅通过其起始地址和长度来描述代码块的旧方案已经不足够
typedef
   struct {
      Addr   base[3]; // IRSB中基本代码块(Basic Blocks)的真实地址
      UShort len[3];
      UShort n_used;
   }
   VexGuestExtents;

黎浩然的编程小屋

Ernest's Hub

Valgrind Vex IR

代码链接

参考资料

论文阅读笔记

Shadow Value Requirements