编程语言的设计原理 Recursive Types

Save this PDF as:
 WORD  PNG  TXT  JPG

Size: px
Start display at page:

Download "编程语言的设计原理 Recursive Types"

Transcription

1 软件分析 错误定位技术 熊英飞北京大学 2018

2 自动化调试 静态分析 测试等技术都是为了发现缺陷 当一个缺陷被发现之后, 如何修复该缺陷? 如何知道缺陷是因为哪行程序的错误导致的? 当定位到有缺陷的语句之后, 如何修复该语句的缺陷? 2

3 基于测试的错误定位 输入 : 软件系统的源码 一组测试, 至少有一个没有通过 输出 : 一个可能有错误的程序元素列表, 根据出错概率排序 程序元素可以定义在不同级别上 表达式 语句 方法 类 文件 3

4 基于测试的错误定位 程序切片 4

5 程序切片 给定程序中的一条语句 S, 找到所有可能可能影响 S 或者 S 可能影响的语句 语句 S 称为切片准则 切片准则也可能是执行到某个位置的某个变量 切片分类 后向切片 : 找到所有影响 S 的语句 前向切片 : 找到所有 S 可能影响的语句 静态切片 : 找到在任何输入下可能被影响的语句 动态切片 : 给定特定输入, 只考虑该输入下可能被影响的语句 5

6 程序切片示例 : 静态切片 a=0; b=3; If (x>0) {a=1; b++;} else {a=2; b--;} z=a; b=b+z; b=b-a; If (b>0) 后向切片 a=0; b=3; If (x>0) {a=1; b++;} else {a=2; b--;} z=a; b=b+z; b=b-a; If (b>0) 前向切片 6

7 程序切片示例 : 静态切片 a=0; b=3; If (x>0) {a=1; b++;} else {a=2; b--;} z=a; b=b+z; b=b-a; If (b>0) 后向切片 a=0; b=3; If (x>0) {a=1; b++;} else {a=2; b--;} z=a; b=b+z; b=b-a; If (b>0) 前向切片 7

8 程序切片示例 : 动态切片 a=0; b=3; If (x>0) {a=1; b++;} else {a=2; b--;} z=a; b=b+z; b=b-a; If (b>0) 后向切片 a=0; b=3; If (x>0) {a=1; b++;} else {a=2; b--;} z=a; b=b+z; b=b-a; If (b>0) 前向切片 8

9 程序切片示例 : 动态切片 a=0; b=3; If (x>0) {a=1; b++;} else {a=2; b--;} z=a; b=b+z; b=b-a; If (b>0) 后向切片 a=0; b=3; If (x>0) {a=1; b++;} else {a=2; b--;} z=a; b=b+z; b=b-a; If (b>0) 前向切片 9

10 实现程序切片 三种依赖关系 数据依赖 : 语句 a 读取了由语句 b 写入的一个变量 控制依赖 : 语句 a 是否被执行由语句 b 的执行结果决定 同步依赖 : 在多线程程序同步时引入的依赖 10

11 程序依赖图 结点为语句, 边为依赖关系 切片 : 从出发点开始求图可达性 Control Dep. Edge Data Dep. Edge Slice Point 11

12 构造过程内静态依赖关系 数据依赖 假设已经有了指针分析的结果 流非敏感 :s1 写某个内存位置,s2 读该内存位置, 则有依赖关系 流敏感 : 可达定值分析 控制依赖 结构化程序 If,switch 每个分支中的语句依赖 if 条件 While, for 循环体中的语句依赖循环条件 12

13 非结构化程序的例子 : A 和 B 有控制依赖吗? A Entry B 13 Exit

14 复习支配关系 / 边界 结点 A 支配 (dominate) 结点 B: 所有从 Entry 到 B 的路径都要通过 A 结点 A 严格支配 (Strictly dominate) 结点 B:A 支配 B 并且 A 和 B 不是一个结点 结点 A 的支配边界中包括 B, 当且仅当 A 支配 B 的某一个前驱结点 至少有一条路径经过 A A 不严格支配 B 至少有一条路径没有经过 A, 且两条在 B 处汇合 存在快速算法可以计算支配边界 14

15 非结构化程序的控制依赖 结点 B 反向支配 (postdominate) 结点 A: 所有从 A 到 Exit 的路径都要通过 B 结点 B 严格反向支配结点 A:B 支配 A 并且 B 和 A 不是一个结点 结点 B 的反向支配边界中包括 A, 当且仅当 B 支配 A 的某一个后继结点 B 不严格反向支配 A 将支配边界算法反过来就是反向支配边界算法 B 控制依赖 A:B 的反向支配边界中包括 A 15

16 构造过程间静态依赖关系 数据依赖 不考虑堆上的数据 被调函数入口语句依赖调用语句的 调用语句依赖被调函数返回语句 16

17 构造过程间静态依赖关系 数据依赖 考虑堆上的数据 计算过程 P 读的内存位置的集合 P r 过程内的语句读 x:x P r P 调用了 Q:Q r P r 类似可计算过程 P 写的内存位置集合 P w P r 当参数处理,P w 当返回值处理 17

18 构造过程间静态依赖关系 控制依赖 函数中所有顶层语句依赖函数入口 函数入口依赖调用该函数的语句 上下文敏感的过程间依赖关系 通过上下文无关文法的可达性实现 18

19 构造动态依赖关系 打印程序的运行的追踪信息 执行的语句编号 每个语句读写的内存地址 具体位置而非抽象位置 数据依赖 语句执行 a 依赖于语句执行 b a 读了一个最近由 b 写的内存位置 控制依赖 实际在执行中发生的静态控制依赖 19

20 切片与错误 出错的语句只可能存在于动态反向切片中 切片准则 : 发现出错的位置 失败的 assert 语句 抛出的未捕获的异常 通常为运行追踪信息中的最后一条语句 动态反向切片可以有效的缩小错误语句的范围 20

21 基于测试的错误定位 基于标准测试覆盖的错误定位 21

22 基于频谱的错误定位 使用最广泛的自动化错误定位方法 形式简单, 效果较好 程序频谱 (Program Spectrum) 最早由威斯康星大学 Tom Reps 于 1997 年在处理千年虫问题时发明 指程序执行过程中的统计量 基于频谱的错误定位 佐治亚理工 James Jone, Mary Jean Harrold 等人 2002 把 Tom Reps 的方法通用化成通用调试方法 主要用到的频谱信息为测试覆盖信息 22

23 基于频谱的错误定位 基本思想 被失败的测试用例执行的程序元素, 更有可能有错误 被成功的测试用例执行的程序元素, 更有可能没有错误 程序元素可以定义在不同的粒度上 基本块 方法 类 文件 可以是语句 表示式吗? 23

24 例子 24

25 计算程序元素的怀疑度 a ef : 执行语句 a 的失败测试的数量,a nf : 未执行语句 a 的失败测试的数量 a ep : 执行语句 a 的通过测试的数量,a np : 未执行语句 a 的通过测试的数量 Tarantula: Jaccard: Ochiai: D*: a ef,* 通常设置为 2 或者 3 a nf +a ep Naish1: 1 a nf > 0 a np a nf = 0 25

26 哪个公式是最好的公式? 实验验证 在不同对象上的实验结果并不一致 早期实验认为 Ochiai 最好,D* 论文认为 D* 最好 最新在 Java 的真实缺陷上的研究认为不同公式之前并无统计性显著差异 语句级别 Top-5 能平均能定位准 18%,Top10 为 27% 理论研究 武汉大学谢晓园等人理论上证明了 Naish1 优于 Ochiai, Ochiai 优于 Jaccard, Jaccard 优于 Tarantula, 但不存在单一最佳公式 新加坡管理大学 David Lo 等人做实验验证出和谢晓园不一致的结论 26

27 其他可能的覆盖信息 之前考虑的是对程序元素的直接覆盖 也可以考虑其他覆盖类型 分支覆盖 : 对于分支语句的每个选择的覆盖 数据流覆盖 : 对于每个变量定义 - 使用对的覆盖 映射其他覆盖到程序元素的错误 分支覆盖 : 分支语句的条件是出错语句 数据流覆盖 : 定义语句是出错语句 平均来说效果更好, 但并不稳定 27

28 数据流覆盖的例子 a=abs(a);. If ( ) { b=sqrt(a); } 如果只有失败的测试用例覆盖 sqrt (a), 会认为是 sqrt (a) 错误, 但其实错误出现在对 a 取绝对值的时候 28

29 数据流覆盖的例子 a=1;. If ( ) { b=sqrt(-1); } 但是正确性是没有保障的 29

30 基于测试的错误定位 基于状态覆盖的错误定位 30

31 程序元素的粒度如何选择? 粒度越细 缺陷定位的结果越精细, 对测试信息的利用越精确 单个元素上覆盖的测试数量越少, 统计显著性越低 常见情况举例 方法级别 基本块级别 31

32 能否比语句更精细? 状态级别 : 程序的每个执行状态作为一个元素 定位结果最精细, 对测试的利用最充分 几乎不会有两个测试覆盖同样的状态 能否找到一个折中方案? 32

33 基于状态覆盖的错误定位 a=abs(a);. If ( ) { b=sqrt(a); } 33 a=abs(a); a>=0 a<0 该语句执行完系统的状态可以分成两组抽象状态 通过的测试只有 a>=0 的状态 只有失败的测试有 a<0 的状态 可以判断出 a<0 是缺陷状态, 引入该状态的语句为缺陷语句

34 状态抽象方案 1: 预定义谓词 定义一些常见谓词 (predicate), 每个谓词的不同状态把具体状态划分成抽象状态 不同谓词形成的划分可以重叠 常见谓词 对整形变量 a a>0 a<0 a==0 对布尔变量 b b==true b==false 对对象 o o==null o!=null 34

35 状态抽象方案 2: 谓词挖掘 从通过的测试执行中挖掘谓词而不是自定义 Daikon: 从程序的运行过程中挖掘不变式 给定不变式模板和程序中的位置,Daikon 监控程序的执行, 并尽量多地挖掘出不变式 常见模板 假设 x,y,z 是变量,a,b,c 是常量 x>=c ax+by+c=0 某数组是按升序排列 35

36 状态抽象方案 3: 定值位置 根据变量定值的位置定义抽象状态 给定语句 s, 令该语句读取的变量集合为 V 该位置的抽象状态为 ς v V 执行到 s 时 v 可能的定值位置的集合 和基于数据流覆盖的情况有什么不同? 考虑 Def-Use 关系的组合而不是单个 Def-Use 关系 36

37 如何给抽象状态的出错可能性打分 基于频谱的公式理论上可以继续使用 但现在居然还没人试过, 诡异 打分方法 1: 统计性调试公式 假设令 predicate 为真的状态为 a, 为假的状态为 b 2 1 log F a ef a ef +b + ef log a aep+a ef ef aep+a ef +bep+b ef 37

38 打分方法 2: 状态迁移的概率 给定程序依赖图上的两个结点 S a 和 S b,s a 直接依赖于 S b, 则 S a 的任意抽象状态 a 直接依赖 S b 的抽象状态 b, 记为 a b 对于任意满足 a b 的抽象状态 a 和 b, 基于通过的测试统计条件概率 P(a b) 对于失败测试执行中的每一个状态 a, 计算出错可能性 1 min P(a b) a b 38

39 打分方法 3: 机器学习 基本思路 : 不同类型的谓词具有不同的预测能力 n!=null 可能有很强的预测能力 n>=25 不一定 采用机器学习来给不同的谓词分的类打分 具体方法 : 把不同的谓词分类 Daikon 已经分好了 311 个类别 令 a 为对应某个谓词 P 为真的抽象状态, b 为 P 为假的抽象状态, 假定 P 的类别为 S, 添加一系列的二元特征 S p f, 为真表示 b ep = 0, a ep > 0, 且 b ef > 0, 即 P 在通过测试中恒成立, 但在失败测试中不一定成立 S pf, 为真表示 b ef = 0, a ef > 0, 且 b ep > 0, 即 P 在通过测试中不一定成立, 但在失败测试中恒成立 通过机器学习用这组特征预测语句出错的概率 39

40 基于状态覆盖的错误定位代表方法 统计性调试 : 预定义谓词 + 统计调试公式 斯坦福 Ben Liblit 和 Alex Aiken 等人于 2003 年提出 概率依赖图 : 定值位置 + 状态迁移概率 佐治亚理工 Mary Jean Harrold 等人于 2010 年 (Mary 去世前三年 ) 提出 Savant: 谓词挖掘 + 机器学习 新加坡管理大学 David Lo 等人于 2016 年提出 各种组合的优劣还是未知数 40

41 基于测试的错误定位 基于变异的错误定位 41

42 变异分析 变异 : 对程序的任意随机修改 变异分析 : 收集变异后程序上原测试用过与否的信息的分析 变异分析被广泛应用于测试领域来衡量一个测试集的好坏 如果一个测试集中任意测试在一个变异后的程序上执行失败, 称为该变异体被这个测试杀死 能杀死越多变异体的测试集越好 42

43 常见变异测试工具 C Milu Java MuJava: 基础变异测试工具, 支持变异算子较完善 Javalanche: 支持 Mutation Schemata 的加速 Major: 支持预先过滤测试执行的加速, 支持变异算子较少 PIT: 商业工具, 功能最完善速度最快 43

44 关于变异的假设 假设 1: 变异错误语句时 失败测试用例输出发生变化的概率 > 通过测试用例输出发生变化的概率 假设 2: 变异正确语句时 失败测试用例输出发生变化的概率 < 通过测试用例输出发生变化的概率 假设 3: 导致失败测试变成通过的概率 变异错误语句时 > 变异正确语句时 假设 4: 导致通过测试变成失败的概率 变异正确语句时 > 变异错误语句时 Metallaxis MUSE 44

45 Metallaxis 卢森堡大学的 Yves Le Traon 教授等人 2012 年提出 m: 变异体,m f : 输出发生变化的失败测试数, m p : 输出发生变化的通过测试数,F: 原失败测试总数 变异体可疑度公式 m f F (m f +m p ) 与 Ochiai 类似, 但主要考虑输出的变化 程序元素可疑度为该元素上的最高变异体的可疑度 45

46 MUSE 韩国科学技术院 Moonzoo Kim 和英国 UCL 大学 Shin Yoo 于 2014 年提出 m: 变异体,m f2p :m 上从失败变成通过的测试数, m p2f : m 上从通过变成失败的测试数 变异体可疑度公式 m f2p m p2f σ m m f2p σ m m p2f 程序元素可疑度为该元素上的变异体的可疑度平均 46

47 基于变异 vs 基于频谱 在基于频谱的错误定位中, 不同测试只要覆盖了语句, 对结果的效果就是相同 但不同测试受同一个语句的影响是不同的 不同测试触发错误的概率不同 不同测试传播错误的概率不同 不同测试捕获错误的概率不同 基于变异的错误定位实际依靠变异捕获了测试和语句之间的关系 47

48 基于测试的错误定位 构造正确执行状态 48

49 动机 在 MUSE 中, 如果有一个变异让失败的测试通过, 同时通过的测试仍然通过, 那么该变异有最高的怀疑度 换句话说, 该变异很可能是正确的补丁 动机 : 直接分析出这样的变异, 然后将能产生出的语句当作怀疑度最高的语句 困难 : 直接分析出比较困难 解决方案 : 不分析出变异本身, 只分析出该变异对系统状态的影响 49

50 谓词翻转 Predicate Switching 2006 年由普度的张翔宇教授提出 假设出错的是一个布尔表达式 不考虑表达式的副作用 该表达式修改后, 必然在原失败测试中至少一次求值返回翻转的结果 true -> false false -> true 依次翻转失败测试中表达式求值结果, 如果测试通过, 则说明对应表达式可能有错误 50

51 天使调试 Angelic Debugging 2013 年由华盛顿大学的 Emina Torlak 提出 如何把谓词翻转从布尔表达式扩展到任意表达式上? 如 int, float, double 等 天使性条件 : 存在常量 c( 天使值 ) 把表达式的求职结果替换成 c, 失败的测试变得通过 是否满足天使性条件就代表表达式很可能有缺陷呢? 51

52 天使性条件 f(a): b = a+1; c = b+1; d = c++; 失败测试 : f(1); assert(d=4); 以上每个表达式都满足条件 52

53 完整天使调试 基础天使调试条件对应原来目标的前一半 : 失败的测试变得通过 利用后一半 : 通过的测试仍然通过 假设 : 对表达式进行修改后, 表达式在所有测试中都会得到不同的结果 比较强的假设, 但对数值型表达式有较大概率成立 灵活性条件 : 对于所有通过的测试中的每一次表达式求值, 都可以把求值结果换成一个不同的值, 并且测试仍然通过 可疑语句需要同时具有天使性和灵活性 53

54 完整天使调试 f(a): b = a+1; c = b+1; d = c++; 为什么谓词翻转不需要灵活性条件? 失败的测试 : f(1); assert(d=4); 通过的测试 : f(2); assert(c=4); 只有 c++ 是可疑的表达式 54

55 如何判断天使性和灵活性? 采用符号执行 首先选定表达式 将表达式的返回值用符号 v 替换 从该表达式所在语句开始符号执行, 考虑所有路径 ( 循环最多执行 n 次 ), 并收集路径约束和最后 test oracle 形成的约束求解 对于通过的测试, 还要添加约束 v c, 其中 c 是原来运行的结果 由于符号执行的开销, 天使调试无法应用到大型程序上 55

56 算法式调试 56

57 算法式调试 Algorithmic Debugging 之前的所有方法都是试图直接找出错误位置 交互式调试 : 通过询问程序员来定位错误位置 算法式调试 1983 年由 Ehud Shapiro 在 算法式调试 一书中提出 主要针对函数语言设计, 在 Haskell 等函数语言上广泛实现 主要通过询问 是 或者 否 的问题找到出错函数 57

58 58 算法调试示例

59 执行树 Execution Tree 59

60 二分查找算法 当用户对某个结点回答 是, 该结点为根子树可以排除 当用户对某个结点回答 否, 该结点为根子树以外的结点可以排除 一个基本思路是问尽量少的问题 即每次选择结点数最接近总结点一半的子树询问 60

61 算法式调试的其他改进 利用一次回答推出更多的信息 利用重复的结点 利用程序中的其他约束 减少人思维中的跳转, 尽量同一时间针对一个函数问问题 61

62 差异化调试 62

63 差别化调试 Delta Debugging 1999 年由德国 Saarland 大学 Andreas Zeller 提出 场景 1: 昨天, 测试还正常通过 晚上, 加班改了 1000 行代码 今天, 测试不通过了 哪些修改是罪魁祸首? 63

64 更多场景 场景 2 写了一个编译器 用户编译了一个 1000 万行代码的项目 编译器崩溃了 哪些输入代码导致编译器崩溃? 场景 3 输入 a 崩溃了, 输入 b 没有崩溃 在某个关键函数进入之前, 系统中有 1000 个内存位置存有数据 哪些内存位置存的数据导致输入 a 崩溃了? 64

65 基本思路 比较两个版本 场景 1; 昨天的代码, 今天的代码 场景 2: 空白输入, 失败输入 场景 3: 测试 b 的状态, 测试 a 的状态 前者测试通过, 后者测试不通过 找到最小修改集合 C 将 C 应用到前者上测试不通过 基本方法 : 集合上的二分查找 65

66 ddmin 问题定义 输入 : 所有可能修改的集合 C 测试函数 test: 2 C,,?, 满足 test = 集合 c C, 满足 test c = 输出 : 集合 c c, 满足 test c = c c, test c c 并非完备的的最小定义, 但完备的做不出来 66

67 ddmin 算法运行示例 67

68 ddmin 算法 68 注意 :99 年 Delta Debugging 第一篇论文中的 dd 算法是错误的

69 ddmin 算法的缺点 ddmin 算法运行时间较长 不用找到引发错误的完整输入 只用找到该输入中的任意部分就能开始调试了 找到两个修改集合 一个通过 一个不通过 两个修改集合的差别尽可能的小 69

70 dd 问题定义 输入 : 所有可能修改的集合 C 测试函数 test: 2 C,,?, 满足 test = 集合 c C, 满足 test c = 输出 : 集合 c, c, 满足 c c c, test c = test c = c c, test c c test c c 70

71 dd 算法运行示例 71

72 dd 算法 72

73 ddmin 和 dd 算法复杂度 最坏情况 :O c 2 最好情况 :O log c 73

74 寻找因果链 差异化调试的一个扩展应用 假设输入 a 让程序崩溃 或者其他可针对任意输入检查的缺陷类型 导致崩溃的因果链 输入中的 xx 字符导致变量 a 被设置成了 5, 然后在 f 函数中, b 变量被设置成了 8, 再然后在 g 函数中,c 变量被设置成了 5, 最后崩溃了 方法 首先运用 dd 算法找到两个差别最小的输入 然后运用 dd 算法在每个函数调用入口对比两个输入的运行状态, 找到有差异的变量 最后把结果组织起来 为节省时间, 上述过程也可以应用二分查找, 而不是在每个函数调用查找 74