【软件分析/静态程序分析学习笔记】5.数据流分析基础(Data Flow Analysis |
您所在的位置：网站首页 › data数据分析软件 › 【软件分析/静态程序分析学习笔记】5.数据流分析基础(Data Flow Analysis |
【软件分析/静态程序分析学习笔记】5.数据流分析基础(Data Flow Analysis
|
写在前面的话
本渣有幸成为南京大学软件学院研究生，在前往仙林校区蹭课的时候偶然发现了这门宝藏课程，听了以后感觉深有收获，但又因为课程难度较大，国庆假期归来发现遗忘较多，因此开了一坑来记录自己对每节课知识点的理解。也由于这是本人第一次开坑写博客，结构内容自有诸多不合理之处，希望有问题的地方大家可以指出。 前两篇文章中比较直观的介绍了数据流分析是什么并举了几个算法的例子，本章将对数据流分析的基础部分进行详细讲解，这部分虽然名为基础，但是那种偏向底层的基础，非常晦涩难懂，没看过前两篇的请先看一下前面的内容，不过就算看不懂也没关系，反正我第一遍上完课也听不懂，老师说有些博士对这块内容可能都不是特别懂，所以平常心看看就行了。 系列文章目录1.静态程序分析(Static Program Analysis)介绍 2.中间表示(Intermediate Representation) 3.数据流分析(Data Flow Analysis) (上)：可达性分析(Reaching Definitions) 4.数据流分析Data Flow Analysis) (下)：存活变量分析(Live Variables Analysis)及可用表达式分析(Available Expressions Analysis) 5.数据流分析基础(Data Flow Analysis-Foundations) 6.过程间分析(Interprocedural Analysis) 7.指针分析(Pointer Analysis)入门 8.指针分析基础知识(Pointer Analysis Foundations) 一、从另一个角度看待迭代算法 1.1 前向传播May算法回顾
这是一个类似前文提到的Reaching Definitions的算法，是一个May分析，顺序是前向传播，相信大家并不陌生。 1.2 从另一个角度看待迭代算法接下来要用数学的方式看待之前的迭代算法，首先先对其进行定义： 给定一个有着k个节点的CFG，迭代算法会在每次迭代过程中为每个节点n更新对应的OUT[n]；假设数据流分析中的数值域为V，那么我们可以定义一个k元组来保存每次迭代后的分析值。这个k元组内容为(OUT[n1],OUT[n2],…,OUT[nk])，表示为(V1 x V2 x … x Vk)，记作Vk。每一次的迭代过程可以视作采取一个动作，通过使用转换函数和控制流函数，将一个元素Vk映射到新的元素Vk上。这个过程可以表示为函数F：Vk→Vk然后算法迭代输出k元组，直到两次输出的k元组完全一致算法停止。以上便是迭代算法数学层面的定义，将其用符号表示得到下图： 接下来将围绕这三个问题，讲解内容。 二、偏序本章开始是大段的离散数学方面的概念知识点，懂的同学可以扫一眼过去，不懂得要自己理解一下，否则后面会直接一脸懵逼。 定义： 我们定义一个偏序集为一个对(P, ⊑)，其中二元关系符⊑在数据集P上定义了一种偏序关系，并且拥有以下性质： ∀x ∈ P, x ⊑ x（自反性）∀x, y ∈ P, x ⊑ y ∧ y ⊑ x ⟹ x = y （反对称性）∀x, y, z ∈ P, x ⊑ y ∧ y ⊑ z ⟹ x ⊑ z（传递性） 举个例子，如图所示结构，定义的偏序符号是子串关系，根据定义可以发现满足三条性质，因此这是一个偏序关系。其中pin和sin并不满足⊑，但是并不妨碍定义的正确，并不是所有元素之间都要满足 ⊑。  再举个例子，偏序符号代表子集关系，同样满足三个性质，这张图可以记牢，后续经常用来讲解。 提示：再思考一下，如果偏序符号代表 |
当迭代算法没有停止的时候会有Xi=F(xi-1)，但是当迭代停止的时候会有Xi+1=F(Xi)=Xi=F(xi-1)，因此得到一个结论： 当X是不动点时，X=F(x)。 当我们得到了这个数学表达形式以后，提出三个问题： 
翻译一下，三个问题分别是：【本文地址】