【数据流分析】软件分析技术-熊英飞

Security Classification: 【C-1】 | Publish Time:2024-08-27 | Category:Reading Notes | Edit
Old Version | Diff |

AI Summary: 本文讨论了数据流分析和符号分析的基本概念与方法。数据流分析通过忽略程序条件判断，分析状态数据在转移过程中的变化。符号分析则关注给定路径下的结果符号的抽象取值，并探讨如何遍历所有路径及合并问题。提出了活跃变量分析的概念，定义了活跃变量和may分析，采用逆分析方法。数据流分析的单调框架包括控制流图、有限高度的半格、入口节点初值以及节点转换函数，强调了合流与收敛的重要性。整体上，文章围绕数据流分析的理论框架及其应用进行了详细阐述。 --- (From Model:gpt-4o-mini-2024-07-18)

## 数据流分析

近似方案1：**忽略程序的条件判断，认为所有分支都有可能到达**。

程序可以看作为状态（数据）和状态之间的转移（控制）两部分，因为状态转移的条件都被忽略了，核心分析的部分是状态数据在转移过程中的变化，所以叫做数据流分析。

## 符号分析

基本思路：如果我们给定程序的一条执行路径，我们能推出结果符号的抽象取值。

如何知道程序的所有路径？

如何遍历所有可能的路径？

近似方案2：**不在路径末尾做合并，在控制流汇合的位置做合并**。

算法安全性问题：

1、Must分析中，一条路径变多条，是否存在问题？
2、近似方案2将合并提前，是否存在问题？
3、路径上有环，是否会一直循环？（保证终止）
4、有多个节点需要更新，无论先更新哪一个，最后结果是否一致？控制流汇合处更新节点是否有顺序要求？（合流）

终止+合流 = 收敛

## 活跃变量分析

活跃变量：给定程序的某条语句s和变量v，如果s在执行前保存在v中的值在后续执行中还会被读取，则称为v为活跃变量。

may分析，返回所有可能的活跃变量。

方法：逆分析，定义活跃变量集合。在出口节点，此时活跃变量集合为{}。往前节点判断活跃变量情况，加入集合。如遇变量覆盖，则移出集合。（先判断覆盖，在判断是否读取）

算法：

1、如何证明多条路径的安全性？
2、算法保证收敛吗？

## 数据流分析单调框架

1、控制流图（v，e）
定义：控制流图是程序的图形表示，其中节点（v）代表程序中的指令或代码块，边（e）代表控制流，即程序执行的可能路径。
2、有限高度的半格
定义：在数据流分析中，用于表示变量值集合的结构，它具有最大和最小元素，以及合并操作（如取上界或下界）。
3、entry节点初值I
定义：在控制流图中的起始节点，为变量赋予一个初始值。
4、一组节点转换函数
定义：在控制流图中，每个节点转换函数定义了如何根据输入值计算输出值。

每个游乐设施（节点）都有特定的规则（转换函数），告诉你是否可以玩。你从入口（起始节点）开始，拿到一张地图（初始值），然后根据地图和游乐设施的规则，决定你可以玩哪些设施。你走过的路径（控制流图的边）构成了你的游玩路线。

在这个过程中，你可能需要做出选择（比如选择玩过山车还是旋转木马），这些选择就像数据流分析中的合并操作，你需要根据规则（转换函数）来决定你的下一步。

Comment List

Comment

© Copyright: This article is an original work and the copyright belongs to the Depy's docs unless marked as Reproduced

Please contact the blogger for authorization to reprint

【数据流分析】软件分析技术-熊英飞

© Copyright: This article is an original work and the copyright belongs to the Depy's docs unless marked as ReproducedPlease contact the blogger for authorization to reprint

© Copyright: This article is an original work and the copyright belongs to the Depy's docs unless marked as Reproduced

Please contact the blogger for authorization to reprint