type
status
date
slug
summary
tags
category
icon
password
软件安全与程序分析概述
似乎没什么重要的
软件安全的威胁：Vulnerabilities（漏洞） Malware（恶意软件）Backdoor（后门）
方法：反编译 反汇编 debug 污点分析 程序切片 符号执行 模糊测试
静态分析概述
完美的程序分析器
soundness：对程序进行了over-approximate过拟合，不会漏报（有false positives假阳性误报）。
completeness：对程序进行了under-approximate欠拟合，不会误报（有false negatives假阴性漏报）。
完美：即二者重合，得到truth
Rice's Theorem
trivial：要么恒真要么恒假，能给出yes or no
说明，这世上并不存在一个完美的算法，来准确的判定每个程序是否有某个非平凡的性质P。（perfect里面的三个性质至少有一个无法完成）不恒真或不恒假的无法被判断为true或false
设计一个useful的程序分析器：保留termination，舍弃completeness，保留soundness（允许误报）
数据流分析
Data-flow
Control flow
CFG 控制流图 DFA 程序流分析
Forward analysis：从entry到exit（backward反之）
May/Must analysis分别对应过拟合和欠拟合
Live Variable Analysis
LVA分析变量是否需要（之后仍然有用）
右侧的变量开始时是dead，不需要分析
LVA的分析是backward analysis 同时是may analysis（只要有一个用了就好）
3:增加f活，2:增加e活，d死，1:增加b c活，a死
LVA算法
Output是Successor（接班人）的I的并集
这里的m？注意一句一分析，先y=m-1增加了m，再m=k删除了m。而同一句中注意结合率，先define后use
Available Expression Analysis
储存一个不变的运算式（编译器优化）
注意：从entry到p，为forward analysis，且all path，为must
x+1是不保留的！先保留后删除，输入是之前输出的交集
AEA算法
forward analysis的output预设为全集（防止空集交集），backward analysis的input预设为空集
不过这个例子里2*y似乎有点问题（没有问题，记录的是output）
DFA Theory
（考试重点）
首先解释下may analysis的意思，may analysis要求对程序进行over-approximate，而must analysis要求对程序进行under-approximate，或者可以这样理解，may analysis输出的报告是一种特称命题（存在分支使得X发生），而must analysis是一种全称命题（对于所有分支，X必然发生）；来看例子
LVA提供的是变量在一点的可能值，而如果在程序的某一点上某个表达式的计算结果是可用的，那么这是一个强制性的情况，不是可能性的问题，所以AEA是must analysis。
*我猜会考RDA
DFA是否一定Terminate？（while循环是不好的）
Lattice
格理论
对于偏序集讨论：
满足自反性 传递性 反对称性，事实上只要满足三律就是偏序集，自动满足lub和glb
（lub glb记法）
abc是S的upper bound，空集是S的lower bound，主要关注lub和glb
lattice的上下界定义
Product Lattice：笛卡尔积
Complete Lattice：不只是{a，b}，每一个子集都有lub和glb
会有求lattice的height的题
DFA via Lattice
在状态机上处理，与编译原理类似
power set是幂集
Fixed-point Theorem
Question：这里的f是lattice内？
不动点理论
单调函数存在独特的Least fixed-point和Greatest fixed-point
证明：
证明DFA的Termination
Join和Meet操作是Monotone的
比如def(n)和use(n)的值不变，O为并集操作，只增不减，因此I也只增不减，每个node的I和O为单调函数。每个node的值是complete lattice，因此存在LF和GF
到了fixed point之后程序的powerset不变，因此终止
Worklist Algorithm
总结LVA与AEA，worklist只修改改变了的点（但没有例子，似乎不重要？
指针分析
alias是别名的意思
上下文敏感/不敏感
流敏感/不敏感
问题陈述：
只考虑这四种情况（不包括p+q等）
Andersen-style Pointer Analysis
使用集合操作代替指针操作，这里的箭头代表包含
考试会有画图（注意指针层级）
理解Store：*p=q，则对于p的每一个pts内容，都有pts(v)包含于pts(q)，即有a箭头指向b，将q的地址赋值于p指针指向的内容，因此有a的内容包含了b，b是a的子集（may be q）
是flow sensitive内容
而如果使用flow insensitive：
出现t多指问题
这里p→q指的是被p指向的内容可能被q包含？（啥意思）就是p的值可能流入q（很生动啊）
Andersen算法
flow insensitive算法 不关心文本先后
ppt上给了一个运行的例子，按照算法画pf图就好
注意Worklist的更新（加指针相关的东西）同时注意最后一个foreach循环（p→s）
第一个内层循环找*n，外层循环找n指向的内容
算法复杂度：理论复杂On^3，但实际可能为On^2
*Steensgaard-style Pointer Analysis 比Andersen更快
有例子的地方都会有考题，所以所有例子都要看
- Author:faii
- URL:https://www.faii.top/article/98fb197b-7378-4f36-9586-5a2084acf1fa
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts