59
课程简介
对学生的要求
准时到达，参加所有课程
课堂上积极参与
及时提交作业、项目
成绩依据
平时: 50%
项目(proposal, written, oral): 50%
2016/9/18 3
4
软件已经渗透到社会的各个角落软件重要性
1 背景介绍
5
美国军方：百年来对计算机最有影响的10人
① Charles Babbage：可编程计算机
② Ada King：第一个程序员
③ Alan Kay：面向对象编程之父
④ Alan Turing：人工智能之父
⑤ Capers Jones：功能点度量
⑥ Watts Humphrey：软件质量之父
⑦ Barry Boehm：成本估算模型
⑧ Tim Berners-Lee：Web之父
⑨ Grace Hopper：第一个编译器
⑩ Ed Yourdon：结构化分析与设计
1 背景介绍
6
软件(20/46)
人工智能/数据
库/操作系统…
图灵奖 (1966-2011)
1 背景介绍
7
2 研究意义
软件中很小的故障错误也可能产生灾难性的后果 航天失败：1962年6月，美宇航局发往火星的水手1号
探测器因一条程序故障导致刚发射即坠毁，数亿美元顷刻化为灰烬
飞机失事：1979年，新西兰航空公司一架飞机因飞行
系统故障撞上Erebus山，257名旅客与机组人员全部遇难
战争判敌为友：1982年马岛战争期间，英驱逐舰因防
御系统故障，将飞来的敌导弹误判为友军武器，而被该导弹击沉
医疗仪器杀人：Therac－25放射治疗仪因软件故障导
致控制系统失灵，致多名病人失去生命
商务灾难：1991年，美电话网因软件问题中断，给数
千依靠电信公司运营业务的公司造成巨额损失
8
3 研究历程
程序设计语言
ALGOL60、FORTRAN、COBOL，PL/I、ALGOL68
Ada语言
YW语言（为远望号配，051、052）
Ada实现
语言比较分析，研究了当时数十种程序设计语言
大型程序设计设施分别编译
类属设施（模板）
并发程序设计设施
……
程序设计语言
9
3 研究历程
软件工程“三要素”
程序设计语言
软件方法论（程序设计方法论）
软件工具与环境
C语言的启迪
中西方学术差异
转向：研究程序设计语言的细节问题
程序设计语言
10
3 研究历程
程序流分析悬挂指针问题
内存泄漏问题
……
各种程序设计设施之间的转换
当时关注点：各种语言程序之间的转换研究
问题：这样保持风格、性质和效率
对象抽取
不同并发设施之间的转换
……
最终：软件分析度量与测试
程序设计语言
软
件
测
试
程序分析
软件度量
• 程序切片
• 代码重构
• 别名分析
•…
• 度量的开发
• 度量的验证
• 度量的应用
• …
• 度量的开发
• 度量的验证
• 度量的应用
• …
•测试用例生成
•测试用例优化
•Web服务测试
• GUI测试
•…
4 研究内容
江苏省软件质量研究所http://jisq.nju.edu.cn
12
4.1 软件分析
自1989年起，开始软件分析：
程序流依赖性分析方法及其应用
开发的效率
逆向工程技术 设计模式恢复 用例恢复
软件演化技术 重构技术
产品的质量
软件调试技术
自动审查技术
基础技术
程序切片 指针分析 类型分析 ……
13
4.1 软件分析
基本问题 对程序进行解剖划分，从中抽取与某一关注计算相关的部分
洞悉程序中的因果关系，为后期处理提供支持
缩小关注范围，从而提高相关应用的效率
切片标准
切片
程序
程序切片
14
面向对象程序切片技术
并发程序切片技术
Web程序切片技术
基于语义的程序切片技术
动态程序切片技术
与UML模型结合的程序切片技术
切片技术应用
……
4.1 软件分析
程序切片
15
4.1 软件分析
基本问题研究由指针(C/C++)以及引用(Java)造成的程序内存间的拓扑关系
指向关系：每个指针都指向了什么目标
别名关系：不同指针表达式是否访问相同目标
p
q
r
指向方式表示：pq别名方式表示：<*p, *q>
指向分析
16
4.1 软件分析
指向分析
主要应用
指针分析是大量含指针、引用程序分析的必备基础。
编译、分析、验证、测试都可能需要使用指针、引用信息
几乎所有通用语言都使用指针、引用类型 (Java, C#, Python, Javascript, …)
17
4.1 软件分析
程序重构
程序重构是通过调整代码，改善既有设计的一种手段。
提高模块性、可维护性、可扩展性、…
软件重构
泛型化重构 方面化重构物理重构包重构
其它重构面向并发的重构
18
4.2 软件测试
2000年，华为公司的故事：
从国外购买测试用例向我们求助
打印范围分：3打印内容分：4 打印颜色/灰度分: 3打印效果分：2打印到文件：2逐份打印：2打印份数：2根据纸张调整大小：2高质量：2属性：>10万
>3x4x3x2x2x2x2x2x2x10万 = 23亿
19
4.2 软件测试
开始尝试正交试验法
发现缺点：等概率覆盖/参数间无约束
测试用例优先级
测试用例约简
测试用例生成
组合测试
错误定位方法
转向
20
4.3 软件度量
结合软件分析开始研究软件度量：
软件度量方法及其应用
开发的效率
逆向工程技术 关键模块识别 对象抽取
软件演化技术 代码重构
产品的质量
缺陷预测
软件维护
基础技术
内聚性度量 耦合性度量 复杂性度量 ……
21
4.3 软件度量
关键模块识别
单元测试中的一个问题
(1) 所测试的系统规模大，模块数目很多
(2) 时间非常紧，人手不够用
不可能测试所有模块，优先测试关键模块
源代码
模块依赖图
Web度量 关键模块序列
22
4.3 软件度量
关键模块识别
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.00.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Re
call
Selected modules in percent
AUTHORITY_recall HUB_recall PageRank_recall
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
0.0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1.0
Re
call
Selected modules in percent
AUTHORITY_recall HUB_recall PageRank_recall
Ant 1.6.1 Jmeter 2.0.1
• 选择模块序列的前10%模块进行审查，能发现50%到60%的关键模块
• 只需要源代码，现有方法需要执行测试用例
• 识别准确性高于现有的静态方法
• 时间性能大幅度提高，我们工具10秒内，现有方法1个多小时
23
4.3 软件度量
缺陷预测
产品度量
预测方法
预测模型
特征特征选择
规模/复杂性/内聚性/耦合性/....
开发方法/测试时间/...
问题难度/编程语言/开发环境/...
探索好的特征
探索好的方法
过程度量
其他因素 线性回归
logistic回归神经网络贝叶斯网络
...
24
4.4 Web信息获取与测试
结合软件分析测试开始研究：
Web信息获取与分析测试技术
Web信息获取与推理 搜索引擎
爬虫算法、页面分析 页面排序 图象搜索
推理技术 描述逻辑 推理算法
Web分析测试 Web应用测试
测试模型 用例生成 性能测试
Web服务测试 服务发现与组合 用户需求驱动的测试
基础技术
Web特性分析 本体映射 语义推理 软件测试……
5 课程概要
静态分析
过程内分析 抽象语法树, 控制流, 数据流, 控制依赖, 数据依赖, 等等
复杂因素 过程间分析, 递归
指针, 引用, 多态, 动态绑定, 等等
切片, 可达性分析, 基于需求的分析
应用 软件测试
软件调试
软件度量
2016/9/18 25
5 课程概要
动态分析
插桩, 剖面分析
控制流的动态分析，等等
应用
动态分析与静态分析的结合
2016/9/18 26
以下部分讲义摘自北大熊英飞老师的课件：
http://sei.pku.edu.cn/~xiongyf04/SA/2015/main.htm
2016/9/18 27
软件缺陷检测问题
2016/9/18 28
软件缺陷检测问题
2016/9/18 29
停机问题
停机问题：判断一个程序在给定输入上是否会终止• 图灵于1936年证明：不存在一个算法能回答停机问题• 因为当时还没有计算机，就顺便提出了图灵机
2016/9/18 30
停机问题
2016/9/18 31
可判定问题
2016/9/18 32
世界末日到了吗？
问题：到底有多少程序分析问题是不可判定的？
2016/9/18 33
超人在哪？
2016/9/18 34
2016/9/18 35
近似求解判定问题
2016/9/18 36
近似法判断内存泄露
2016/9/18 37
非判定问题
2016/9/18 38
课堂练习
测试属于must分析还是may分析？
类型检查属于must分析还是may分析？
2016/9/18 39
2016/9/18 40
安全性分析
2016/9/18 41
问题一
2016/9/18 42
解决方案
2016/9/18 43
数据分析举例
通过分析代码注释，获取对应函数的规约
通过分析代码库帮助文件，获取代码库实现的规约
对于程序优化任务，没有优化的程序就是规约
需求和设计文档里面包含了程序的规约
实现相似功能的代码可能包含了规约
……
2016/9/18 44
如何做数据分析
大量现有可用技术
信息检索• 数据表示、特征匹配
数据挖掘• 频繁模式挖掘
机器学习• 聚类算法、分类器学习
自然语言处理• 分词、句子结构分析、语义理解
数据库• 海量数据处理
2016/9/18 45
问题二
2016/9/18 46
没有安全性的分析
数据分析技术通常不保证安全性，但在各领域广泛使用• 例：百度返回的结果既不保证覆盖所有相关的网页也不保证返回的网页一定相关
更多的一些智能技术• 启发式搜索• 模糊分析和概率分析
2016/9/18 47
更多应用
除了衡量和提高软件质量，基于数据的智能化软件分析还有更多应用• 通过分析大量程序日志，优化系统和硬件• 通过分析开发人员的通信记录，优化管理方式• 通过分析相似软件的行为，发现恶意软件• 通过分析代码和缺陷报告的关系，自动分配开发人员修复• ……
2016/9/18 48
6 课程起源
2016/9/18 49
词法分析语法分析
代码生成优化
代码执行
中间表示
分析中间表示将所得信息用于各种应用
目标代码
源代码
7 软件分析测试基础
源代码
结构, 内容
中间表示
抽象语法树 (AST)
控制流图 (CFG)
数据流图 (DFG)
依赖图 (DG)
2016/9/18 50
语法
具体语法表示语言相关的结构
抽象语法表示程序结构
中间表示
语法分析树描述具体语法
抽象语法树描述抽象语法
三地址码
2016/9/18 51
7.1 具体语法树与抽象语法树
2016/9/18 52
7.2 语法实例
2016/9/18 53
7.3 语法分析树实例
2016/9/18 54
7.4 抽象语法树实例
2016/9/18 55
7.5 三地址码实例
7.6 基本块实例
7.7 控制流计算算法
输入：程序
输出：控制流图（节点与边）
算法：
构造基本块
创建入口与出口节点，标记边
对于所有可执行的路径，标记边
8 关键技术
程序分析
2016/9/18 58
9 技术趋势
软件分析
2016/9/18 59
