第1章 源代码分析概要 1
1.1基本概念 1
1.1.1源代码 1
1.1.2源代码分析 1
1.1.3分析过程 2
1.1.4源代码建模 2
1.2语法与语义分析 4
1.2.1语法分析 4
1.2.2抽象语法树 4
1.2.3符号表 5
1.2.4语义分析 7
1.3控制流分析 8
1.3.1控制流图 9
1.3.2支配图 11
1.3.3依赖图 12
1.4数据流分析 13
1.5源代码分析常用方法 15
1.6常用源代码分析技术 17
1.6.1程序的抽象 17
1.6.2区间运算 18
1.6.3程序切片计算 19
1.6.4路径计算 20
1.6.5约束求解 21
参考文献 22
第2章 抽象解释 24
2.1引言 24
2.2基本概念 26
2.2.1格与不动点理论 26
2.2.2伽罗瓦连接 34
2.2.3 Widening/Narrowing算子 38
2.3程序分析与抽象解释 40
2.3.1程序分析的不可判定性 40
2.3.2程序语义及其不动点形式 41
2.3.3抽象解释中的语义层次体系 43
2.4抽象解释应用实例 45
参考文献 48
第3章 符号计算 50
3.1简介 50
3.2符号执行技术的基本原理 50
3.3符号执行技术的形式化表达 52
3.4符号执行实现方法 55
3.4.1静态符号执行 55
3.4.2动态符号执行 56
3.4.3符号执行技术总结 57
3.5符号执行工具简介 58
3.5.1 SPF 58
3.5.2 KLEE 59
3.5.3 SAGE 59
3.5.4 PEX 60
参考文献 60
第4章 区间运算技术 63
4.1经典的区间代数 63
4.1.1区间及区间运算 63
4.1.2区间向量和区间函数 64
4.2扩展的区间运算 64
4.2.1数值型区间集代数 64
4.2.2非数值型区间代数 67
4.2.3条件表达式中的区间计算 68
4.2.4基于区间运算的变量值范围分析 74
4.3变量的相关性分析 80
4.3.1变量间关联关系的分类 80
4.3.2符号分析 82
4.4区间运算在程序分析中的应用 90
4.4.1检测矛盾节点 90
4.4.2检测不可达路径 93
4.4.3提高缺陷检测效率 93
参考文献 95
第5章 路径敏感分析 97
5.1概述 97
5.2路径不敏感分析方法 97
5.2.1数据流分析 97
5.2.2四种典型数据流问题 99
5.2.3数据流分析的理论依据 109
5.2.4数据流解的含义 109
5.3路径敏感分析方法 113
5.3.1缺陷模式状态机 113
5.3.2不可达路径引入误报 116
5.3.3路径信息抽象 117
5.3.4检测算法 118
参考文献 120
第6章 抽象内存建模 122
6.1传统的程序分析模型 122
6.1.1二元模型 122
6.1.2数组模型 123
6.2抽象内存模型 124
6.2.1模型定义 125
6.2.2模型的基本操作 128
6.3语义模拟算法 129
6.3.1通用操作符 130
6.3.2指针 130
6.3.3数组 137
6.3.4结构体 138
6.3.5字符串 138
6.4基于抽象内存模型的测试用例生成 142
参考文献 144
第7章 上下文分析 146
7.1问题分析 146
7.1.1函数调用后影响上下文 146
7.1.2函数调用前约束上下文 148
7.1.3函数特征影响上下文 149
7.2函数影响 150
7.2.1函数影响描述 150
7.2.2函数影响生成 150
7.2.3函数影响应用 152
7.2.4函数影响实验 153
7.3函数约束 154
7.3.1函数约束描述 154
7.3.2函数约束生成 157
7.3.3函数约束应用 162
7.3.4函数约束实验 163
7.4函数特征 164
7.4.1函数特征描述 164
7.4.2函数特征生成 165
7.4.3函数特征实验 166
参考文献 168
第8章 程序切片 169
8.1基本概念 169
8.1.1程序切片的定义 169
8.1.2程序切片标准 171
8.2常见程序切片种类 171
8.2.1静态切片 172
8.2.2动态切片 173
8.2.3后向切片 174
8.2.4前向切片 174
8.2.5准静态切片 175
8.2.6同步切片 176
8.2.7条件切片 177
8.2.8无定型切片 178
8.2.9混合切片 179
8.2.10程序砍片 179
8.3程序切片计算方法 180
8.3.1过程内切片计算方法 180
8.3.2过程间切片计算方法 183
8.3.3面向对象的程序切片计算方法 185
8.4程序切片的应用 187
8.4.1软件质量保证 187
8.4.2软件维护 187
8.4.3软件度量 188
参考文献 188
第9章 路径计算 192
9.1路径生成 192
9.1.1不包含循环结构的路径生成 192
9.1.2循环结构路径生成 194
9.2路径可达性计算 199
9.2.1基于矛盾片段模式的路径可达性计算 199
9.2.2基于优化区间运算的路径可达性计算 200
9.2.3基于等式系数矩阵的路径可达性计算 208
9.2.4基于仿射运算的路径可达性计算 210
参考文献 210
第10章 约束求解 212
10.1求解布尔约束满足问题 212
10.1.1布尔约束满足问题 212
10.1.2基础知识 213
10.1.3算法 214
10.1.4典型的SAT求解器和SMT求解器 216
10.2求解有限约束满足问题 219
10.2.1有限约束满足问题 219
10.2.2回溯法 220
10.2.3不完备算法-局部搜索法 221
10.3求解混合约束满足问题 225
10.3.1混合布尔约束满足问题 225
10.3.2数值约束求解算法 225
10.4基于约束求解的测试用例自动生成 228
10.4.1常见的测试用例生成方法 228
10.4.2基于抽象内存模型的分支限界法 237
参考文献 241
第11章 源代码分析应用 244
11.1缺陷检测系统DTS 244
11.1.1产品功能 244
11.1.2产品特色 245
11.1.3缺陷模式 246
11.1.4技术架构 247
11.1.5技术指标 248
11.1.6使用步骤 248
11.2代码测试系统CTS 255
11.2.1系统功能 255
11.2.2操作步骤 257
11.3其他代码分析工具 261
11.3.1 Emma 262
11.3.2 C＋＋test 268
11.3.3 Testbed 272