静态切片
一、概述
控制流图CFG、数据流图DFG、程序依赖图PDG、系统依赖图SDG
程序切片从可执行到不可执行
根据输入分类：静态切片，动态切片，有条件切片
程序切片应用之处
二、图论基础
控制流图
基本块：第一句进入，最后一句离开
控制流图以基本块为节点
控制流和数据流
控制流分析就是去发现过程内or过程间的控制流
什么是过程？~函数
控制流图表示形式：
- AST
- CFG
- PDG中的控制依赖
数据流描述了变量的值从定义点如何流到使用点
数据流边表示什么？~变量和变量之间的关系
可到达定义怎么计算？~求解数据流方程
控制依赖和数据依赖
控制依赖：控制流引起的程序实体之间的关系
控制依赖定义：满足以下三个条件：
- n1n2之间存在可执行路径
- 对可到达路径上的其他点，n2都是它的后必经节点
- n2不是n1的后必经节点
条件语句内部的语句控制依赖于条件部分
数据依赖：由于数据定义和使用所形成的实体之间的关系
数据依赖定义：满足以下三个条件：
- n2定义了变量v
- n1使用了变量v
- n2n1存在可执行路径且变量v未重新定义
程序依赖图
这里只是简单介绍
过程内依赖图：即过程依赖图PrDG，即控制依赖图+数据依赖图
过程间依赖图：即系统依赖图，各个过程依赖图+调用边+调用引起的依赖边
三、静态程序分析
MarkWeiser程序切片
切片准则：
其实就是在简化代码，希望留下切片准则相关的代码，求切片就是求图的可达性问题
切片结果可能不符合语法
切片优化：寻找最小切片问题是不可解的
不足：只能解决简单的程序，为了解决过程和过程调用的问题提出了过程内切片和过程间切片
过程内切片
先在cfg上构建控制依赖图和数据依赖图，然后把两个图合并即可得到pdg
先构建程序依赖图pdg，再应用图可达性算法
前向后向区别：
- 后向：是指以漏洞关注点为终点，能够到达该节点的所有路径上的所有节点
- 前向：是指从关注点节点出发，能够达到达到的所有路径上的节点
过程间切片
一样的逻辑，构建系统依赖图，然后应用图可达性算法
在过程依赖图上添加调用边、参数输入边和参数输出边形成系统依赖图（根据P50，好像有更多操作）
参考资料
《程序切片技术及其应用》