源代码分析

目录
前言
第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