第九章：Dynamic Symbolic Execution

Dynamic Symbolic Execution

overview

Dynamic Symbolic Execution（DSE），也称为符号执行或符号化测试，是一种程序分析技术，用于自动发现软件中的错误。它是通过将程序的实际执行与抽象的符号执行相结合来完成的，这可以帮助发现程序中的各种路径，并验证这些路径上是否存在问题，如错误或安全漏洞。

motivation

• 编写和维护测试是繁琐且容易出错的。

• idea:

  • Generate regression test suite

  回归测试套件（regression test suite）是一组测试用例，它们被设计用来验证软件在修改后（比如说，修复了bug或添加了新功能）仍然按照预期工作，既有功能没有因为新的代码变动而发生故障。回归测试的关键目的是确保新的代码更改没有引入新的缺陷到已有的功能中，即没有“回归”或倒退。

  • Execute all reachable statements
  • Catch any assertion violations

• new technique: dynamic symbolic execution

dynamic symbolic execution

- 存储程序状态的具体和符号化表示
- 解决约束以指导分支点处的执行
- 探索被测试单元的所有执行路径

• 一种常用的 dynamic symbolic execution 是 hybrid analysis
  

• 程序可以看成是一个 binary tree，可能有无限的深度（因为可能存在循环），这个 tree 称为 computation tree

• 每个 node 代表 一个条件语句的执行

• 每条 edge 表示执行一系列非条件语句。也就是说，如果 node2是一个条件语句，那么 left 的分支就是使得 node2 条件为 false 的执行操作，而 node2 右边的分支就是使得其为 true 的执行操作

• 树上的每条路径表示 inputs 的一个等价类

• 实例：
  

• 通常会用 assert 来 if 不满足时抛出错误的操作

• 还有因为这个里面没有循环操作，因此这个树是有界的

常用的其他技术对比

Random Testing

• 如果使用 random testing，对于一个 if 条件，可能非常难测到，比如上面的例子

symbolic execution

• symbolic execution 的核心是一个 test prover，而不使用任何具体的值

• 当程序在第一个分支的时候，test prover 会证明是否存在一个 x 使得 $x\ast 3==15$ 这个条件成立；test prover 会说 “存在”，那么这个 condition 为 true 的分支就会成功执行；接下来会询问是否存在 x 使得 $x\ast 3!=15$ 这个条件成立（也就是 condition 的 else 分支），test prover 会说 “存在”，因此第一个 condition 的 else 也会成功执行

• 接下来是第二层分支，继续询问 test prover，是否存在 $x$ 满足 $x\ast 3==15\&\&x\%5==0$ ，test prover 会说 “存在”，那么 print(ok) 成功可达；然后询问 else 的 condition，即是否存咋 $x$ 满足 $x\ast 3==15\&\&x\%5!=0$，test prover 会说 “不存在”；因此这个 else 永远不可达，无论在什么条件下。

• 这成功避免了 random testing 的无法进入分支的问题。但他也存在自己的问题，那就是，在大型程序中，这种 if else 的叠加会迅速爆炸，因为条件太多了且都是级联的。

• 另外一个缺点是 symbolic execution 可能不够强大
  

• 上述条件对于 test prover 来说是困难的，因此可能存在误报

Combined static and symbolic - Dynamic Execution (DSE)

step1: 初始化两个具体的值 x,y

• 除了两个具体的值之外，x，y 分别的 symbolic 的 state 也会记录下来，现在是 $x=x_0,y=y_0$
  

step2: 根据定义得出 z 的 concrete value 和 symbolic state

• 可以计算出 z = 14 z=14