【S2E插件分析】Recipe插件 -- 1.Recipe

工具
,

Recipe 插件 – 1. Recipe

从总体来看（ 【S2E插件分析】Recipe插件 -- 0.概述 ），Recipe 插件导入了一个 recipes 目录，并设置了输出等级，功能应该比较简单（？）

  • 没搞懂对 Recipe Right::NEGOTIABLE 类型的右值是怎么处理的；

1. 导入 recipes 目录

Recipe::initialize() 中：

1
2
m_recipesDir = cfg->getString(getConfigKey() + ".recipesDir");
loadRecipesFromDirectory(m_recipesDir);

调用了 loadRecipesFromDirectory() 函数来处理。总之，处理完之后，会保存到类变量 m_recipes ，类型是 typedef std::map<std::string, RecipeDescriptor *> RecipeMap; 。

Recipe::loadRecipesFromDirectory() 函数

从指定目录中读取 .rcp 文件（所有文件都将被视为 .rcp 文件）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for (llvm::sys::fs::directory_iterator i(directory, error), e; i != e; i.increment(error)) { // 遍历整个目录
		
  	// 错误处理
  	... ...
    // 不再递归地遍历指定目录下的目录
    if (status.type() == llvm::sys::fs::file_type::directory_file) {
        continue;
    }
  
  	// typedef std::map<std::string, RecipeDescriptor *> RecipeMap;
  	// RecipeMap m_recipes;
		
  	// 对每个 Recipe 文件调用 RecipeDescriptor::fromFile 函数来生成一个 RecipeDescriptor 对象
  	RecipeDescriptor *desc = RecipeDescriptor::fromFile(entry);
  	... ...
    // 然后保存到 m_recipes 中
    m_recipes[recipeName] = desc;
}

所以重点在 RecipeDescriptor::fromFile 函数里（禁止套娃）。我比较关心的是 RecipeDescriptor 的内容，因为这是对 .rcp 文件的分析结果。至于分析的过程有空再说。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// RecipeDescriptor.h
struct RecipeDescriptor {
    RecipeSettings settings;
    Preconditions preconditions;
    EIPType eipType;

    static RecipeDescriptor *fromFile(const std::string &recipeFile);
    static bool mustTryRecipe(const RecipeDescriptor &recipe, const std::string &recipeName, const StateConditions &sc,
                              uint64_t eip);

    bool isUsable(S2EExecutionState *state, OSMonitor *monitor) const;

private:
    uint64_t concreteTargetEIP;
    bool parseSettingsLine(const std::string &line);
    bool parsePreconditionLine(const std::string &line);
    bool isValid() const;
};

  • RecipeSettings：保存了包括 利用类型（1，2），通用寄存器/ EIP 掩码，平台，架构等等

  • Preconditions：是 Precondition 的向量。

    1
    typedef std::vector<Precondition> Preconditions;

    而 Precondition 是一种表达式（left == right）

    1
    2
    3
    4
    5
    6
    7
    struct Precondition {
        klee::ref<Left> left;
        klee::ref<Right> right;
        ... ...
        /* 所以按照 .rcp 文件，左值大致就是 [eip+i]，右值就是 0x90 等具体的指令值
        */
    }

  • EIPType：分为 SYMBOLIC_EIP 和 CONCRETE_EIP 两种。

  • 还有一些其他的变量和结构体函数。

2. 检查程序状态是否可利用

Recipe::tryRecipes() 函数，调用时依次处理每个 rcp ，检查当前的程序状态是否满足某个 rcp 规定的结果。

当然，并不是每得到一个新的程序状态就使用该函数检查（这样可能开销太大了）。文中有两处调用了 tryRecipes() 函数：

  • onAfterCall：是 onTranslateBlockEnd() 内部注册的，当检查到当前基本块类型是 TB_CALL_IND 或者 TB_CALL 的时候触发，这个时候会调用 tryRecipes() 检查；

  • onSymbolicAddress：当遇到符号化的地址时。这里限定了必须是符号化的 EIP 才能够调用 tryRecipes() 检查。

    onSymbolicAddress 事件是即将处理符号化变量时弹出的事件，其中的 virtualAddress 变量就是即将处理的符号化变量的地址。

1. 检查当前状态是否符合 Recipe 应用条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
foreach2 (it, m_recipes.begin(), m_recipes.end()) {
	// 判断当前模块。有些 rcp 指定应用于某些模块
    if (module->Name != recipe.settings.moduleName) {
    	... ...
    }
    
    // 调用 isUsable 检查。该函数主要检查系统架构是否匹配。可忽略。
    if (!recipe.isUsable(state, m_monitor)) {
        continue;
    }
	// 调用 mustTryRecipe，将 sc (state condition) 传入
    // 感觉上，如果 eip 是符号化的，或者eip具体但是刚好和recipe规定的相等，就`必须尝试`，如果不是必须尝试，就跳过（感觉起名叫`必须`不太贴切，应该是检查是否满足条件）
    if (!RecipeDescriptor::mustTryRecipe(recipe, recipeName, sc, state->regs()->getPc())) {
            continue;
        }
    
    // 然后开始尝试应用 rcp ... ... 
    
}

mustTryRecipe() 函数调用时传入变量 StateConditions sc ，该变量代表的是当前状态的 EIP 状态（具体还是符号），并顺便记录 nextEIP 的信息。如下：

1
2
3
4
5
6
7
8
9
10
struct StateConditions {
    ModuleDescriptor module;
    klee::ref<klee::Expr> nextEip;
    EIPType eipType; // 两种类型，具体化的 EIP，符号化的 EIP
};
... 
enum EIPType {
    SYMBOLIC_EIP = 1u << 0,
    CONCRETE_EIP = 1u << 1,
};

与前面 tryRecipes() 的调用条件对应：

  • onAfterCall：在 call 时检查 recipe，此时的 EIP 必定是具体的。
  • onSymbolicAccess：只有在 EIP 是符号化时才调用。

2. 尝试应用 Recipe

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
foreach2 (it, m_recipes.begin(), m_recipes.end()) {
  // 检查当前状态是否符合 Recipe 应用条件
  ... ...
    
  // 开始尝试应用 recipe
  getDebugStream(state) << "Trying recipe '" << recipeName << "'\n";
  			// recipeConditions 是函数的参数，是一个引用，保存返回值。
        RecipeConditions l_recipeConditions = recipeConditions;

        if (!applyPreconditions(state, settings.type, sc, recipe.preconditions, l_recipeConditions)) {
            continue;
        }

        getWarningsStream(state) << "Recipe '" << recipeName << "' ready\n";

        success = true;

        PovOptions opt;

        opt.m_type = settings.type;
        opt.m_faultAddress = state->regs()->getPc();
        opt.m_extraConstraints = l_recipeConditions.constraints;
        opt.m_remapping = l_recipeConditions.remappings;

        if (settings.type == PovType::POV_TYPE1) {
            opt.m_ipMask = settings.ipMask;
            opt.m_regMask = settings.regMask;
            opt.m_regNum = settings.gp->reg();
        } else if (settings.type == PovType::POV_TYPE2) {
            opt.m_bytesBeforeSecret = settings.skip;
        }

        onPovReady.emit(state, opt, recipeName);
    }

applyPreconditions() 函数

applyPreconditions() 函数用于检查约束是否满足。传入的 recipe.preconditions 就是 recipe 中写好的约束。applyPreconditions()

1
enum PovType { POV_GENERAL, POV_TYPE1, POV_TYPE2 }; // POV type 分为三种
1
2
3
4
5
6
7
bool Recipe::applyPreconditions(
  S2EExecutionState *state, 
  PovType type, // 来自 .rcp 文件的类型
  const StateConditions &sc, // EIP Type
  const Preconditions &p, // 来自 .rcp 文件的约束
  RecipeConditions &recipeConditions // 返回值
);

该函数首先调用 classifyPreconditions() 函数来对约束分类，将普通约束保存到 simple 变量里：

1
2
3
4
5
6
7
	std::unordered_set<uint64_t> executablePages;
  // 有关 MemoryPages 的操作我都看不懂。
m_memutils->findMemoryPages(state, m_monitor->getPid(state), false, true, executablePages);

  Preconditions simple;
  std::map<Register::Reg, MemPrecondition> memory;
  classifyPreconditions(state, sc, p, simple, memory);

接下来对分类后的普通约束 simple 分别处理：

1
2
3
4
5
6
7
8
9
10
11
// 左值的类型在 RecipeDescriptor.h 中定义
class Left {
public:
    enum Type {
        INV,         // invalid
        REGBYTE,     // register[offset] (EAX[0])
        REGPTR,      // memory referenced by register+offset
        REGPTR_EXEC, // register must point to executable memory
        REGPTR_PTR,  // [register+offs1][offs2] ([ESP+4][0])
        ADDR,        // memory referenced by address
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
		RecipeConditions l_recipeConditions = recipeConditions;

    foreach2 (it, simple.begin(), simple.end()) {
    if (it->left->type() == Left::REGPTR_EXEC) {
      	// 如果是 REGPTR_EXEC，则先检查对应地址是否可执行，不可执行则 false
        ref<Expr> reg = getRegExpr(state, sc, it->left->reg());
        uint64_t regVal = dyn_cast<ConstantExpr>(reg)->getZExtValue();

        if (executablePages.find(regVal & TARGET_PAGE_MASK) == executablePages.end()) {
            getDebugStream(state) << "Precondition " << *it << " is not satisfiable\n";
            return false;
        }
    } else {
      // 如果是其他类型的左值
        if (checkUsedRegs(state, it->left, l_recipeConditions.usedRegs)) {
          // 该函数用于检查这一条约束所使用的寄存器是否已经被约束过。
          // 例如， [EIP+0]=0xa, [EIP+1]=0xb
          // 在处理第二条时，EIP已经被处理过了，所以此时会返回 true
          
          // 如果已经约束过了，那么直接返回。（？？？）
            return false;
        }

        ref<Expr> left;
        if (!getLeftExpr(state, sc, *it, left)) {
            getDebugStream(state) << "Cannot get left expr, " << *it << " is not satisfiable\n";
            return false;
        }
				
      	// 取出左值之后，就尝试加上右值的约束
        if (!applySimplePrecondition(state, sc, left, it->right, l_recipeConditions)) {
            getDebugStream(state) << "Precondition " << *it << " is not satisfiable\n";
            return false;
        }
    }
}

applySimplePrecondition() 函数

applySimplePrecondition() 函数负责解析右值，并将约束附加到左值上。

右值的类型有下面几种。（除了 NEGOTIABLE 以外都好理解）

1
2
3
4
5
6
7
8
class Right {
public:
    enum Type {
        INV,        // invalid
        REGBYTE,    // register[offset] (EAX[0])
        NEGOTIABLE, // can take arbitrary values
        CONCRETE    // has concrete value
    };
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
s2e_assert(state, !left.isNull(), "left expr must not be null!");
RecipeConditions l_recipeConditions = recipeConditions;

// 没看懂具体是怎么提取的，总之把 left 中的每一个字节都保存到
// usedExprs 中了（usedExprs 是 vector 变量）
// 但是话说回来，left 必须是 1 个字节啊，为啥还要提取
extractSymbolicBytes(left, l_recipeConditions.usedExprs);

switch (right->type()) {
  case Right::NEGOTIABLE: { // TODO: 没看懂
  ... ...
  } break;
  case Right::REGBYTE: {
    ref<Expr> ee_right = getRegbyteExpr(state, sc, right->reg());

    // 左值的宽度必须是 1 字节
    if (left->getWidth() != Expr::Int8) {
        getWarningsStream(state) << "Invalid left value width " << left->getWidth() << "\n";
        return false;
    }

    ref<Expr> c = E_EQ(left, ee_right);
    if (isa<ConstantExpr>(c) && dyn_cast<ConstantExpr>(c)->isFalse()) {
        // 如果左值是具体化的，且和右值不相等，那么约束必然失败。直接返回 False
        return false;
    }

    // 将这条约束添加到 constrains 向量中。
    l_recipeConditions.constraints.push_back(c);
  } break;
  
  // 如果右值是具体的，那么和上面类似。
  case Right::CONCRETE: {
  	... ...
  } break;
    
 	... ...
  
recipeConditions = l_recipeConditions;
return true;

classifyPreconditions() 函数

classifyPreconditions(state, sc, p, simple, memory);

对 .rcp 文件中的约束进行分类（分类为内存约束和普通约束（我随便起名字的）），并普通约束保存到 simple 中，内存约束保存到 memory 里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// p 是 Preconditions 变量，是来自 .rcp 文件的约束
foreach2 (it, p.begin(), p.end()) {
	ref<Expr> ptrExpr;
	if (isSymbolicRegPtr(state, sc, it->left, ptrExpr)) {
    // 该函数的功能是：根据 .rcp 中规定的约束，例如：
    // EIP[0] == $pc[0]
    // 该函数检查左值是否是一个 的值（显然是寄存器，EIP）
    // 如果是，那么将寄存器的值取出，保存到 ptrExpr 中，
    // 如果是符号变量，则返回 true，否则返回 false
    // 如果左值不是寄存器，那么也返回 false.
    
    
    MemPrecondition &mp = memory[it->left->reg()->reg()];
    mp.ptrExpr = ptrExpr;
    mp.requiredMemSize = std::max(mp.requiredMemSize, unsigned(it->left->offset() + 1));
    // 如果是 REGPTR_EXEC 类型，那么要求内存区域可执行
    if (it->left->type() == Left::REGPTR_EXEC) {
        mp.exec = true;
    } else { // 如果是 REGPTR 类型，则要求对应内存区域是指定值
        mp.preconditions.push_back(*it);
            }
  } else {
    simple.push_back(*it);
  }
}

这里似乎说明，Recipe 也支持自动寻找可执行的内存区域？

getLeftExpr() 函数

1
2
3
4
5
6
bool Recipe::getLeftExpr(
  	S2EExecutionState *state, 
  	const StateConditions &sc, // 当前 state 的类型（符号化EIP还是具体化）
  	const Precondition &p, // .rcp 的一条约束信息
  	ref<Expr> &val // 返回值
);

该函数将 Precondition p 中的左值取出，保存到 val 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
switch (p.left->type()) {
    // 如果左值是寄存器的某一字节，那么直接把这个寄存器的对应字节取出来。
    case Left::REGBYTE: {
        val = getRegbyteExpr(state, sc, p.left->reg());
    } break;
    
    // 如果左值是寄存器作为指针 (例如 [EIP+1] = 0xa)
   	case Left::REGPTR: {
        ref<Expr> base = getRegExpr(state, sc, p.left->reg());
      	// 断言：该寄存器必须是具体的。（符号化的情况在哪里处理了？）
        s2e_assert(state, isa<ConstantExpr>(base), "Symbolic memory pointers are handled separately");

        uint64_t addr = dyn_cast<ConstantExpr>(base)->getZExtValue() + p.left->offset();
      	// 从内存中把改地址对应的 Expr 读出来
        val = m_memutils->read(state, addr);
        if (val.isNull()) {
            getWarningsStream(state) << "Failed to read memory at " << hexval(addr) << "\n";
            return false;
        }
    } break;
    
    // 如果左值是某个固定地址，那么直接把对应内容读出来就可以了
    case Left::ADDR: {
        val = m_memutils->read(state, p.left->addr());
        if (val.isNull()) {
            getWarningsStream(state) << "Failed to read memory at " << hexval(p.left->addr()) << "\n";
            return false;
        }
    } break;
    
    // 如果左值是指针的指针（没这样写过，看起来可能是支持的），套娃处理。
    case Left::REGPTR_PTR: {
      ... ...
    } break;
    
    // 如果是 REGPTR_EXEC 类型，已经在其他位置处理过了。
    case Left::REGPTR_EXEC: {
      s2e_assert(state, false, "unhandled type of left expression");
    }

总结

Recipe 插件从指定目录中导入所有 .rcp 文件后，将每个 .rcp 的每一条约束都解析为左值（被约束的表达式，可以是内存地址，也可以是寄存器）和右值（一般是常数，表示将某个地址或寄存器的值约束为某个常数），然后在两种情况下（call 调用时或者访问符号变量时）触发检查，对每个 .rcp 都进行测试，查看当前 state 是否满足 .rcp 的应用条件。如果应用成功，则触发 onPovReady 事件。

onPovReady 事件将被 PovGenerationPolicy 插件捕获，见 【S2E插件分析】Recipe插件 -- 2.PovGenerationPolicy

1. 取出表达式

从内存中取出表达式：

1
2
3
MemUtils *m_memutils = s2e()->getPlugin<MemUtils>();
klee::ref<klee::Expr> e = m_memutils->read(state, addr, klee::Expr::Int8);
// ref<Expr> MemUtils::read(S2EExecutionState *state, uint64_t addr, klee::Expr::Width width);

从寄存器中取出表达式：

1
klee::ref<klee::Expr> value = state->regs()->read(CPU_OFFSET(regs[reg->reg()]), state->getPointerWidth());

2. 创建约束

先创建一个约束表达式，例如相等：

1
2
ref<Expr> constraint = E_EQ(left, right); // left 和 right 都是 klee::ref<klee::Expr>
ref<Expr> c = E_EQ(left, E_CONST(right->value(), right->valueWidth())); // 或者直接构建一个 const Expr

3. 测试约束

1
2
3
4
5
6
typedef std::vector<klee::ref<klee::Expr>> ExprList;
... ...
ExprList constraints;
constraints.push_back(constraint);
... ...
state->testConstraints(constraints, nullptr, nullptr);