软件静态分析
2021-10-07 20:30:33 0 举报
AI智能生成
静态分析相关知识
作者其他创作
大纲/内容
1.Source Code源码
2.Scanner - 词法Lexical分析-Regular Expression
3.Parser- 语法Syntax分析-Context-Free Grammar
4.生成AST
5.Type Checker - 语义Semantic分析 - Attribute Grammar
6.生成 Decorated AST
7.Translator,生成IR,进行静态分析
8.Code Generator
编译过程
只有1个开头入口和1个结尾出口的最长3-地址指令序列。
基本块
控制流边:基本块A的结尾有跳转指令跳转到基本块B;原始指令序列中,B紧跟着A,且A的结尾不是无条件跳转。
控制流图
高级,更接近于语法结构,依赖于语言种类,适用于快速类型检查,缺少控制流信息
抽象语法树
低级,更接近于机器码,不依赖语言种类,压缩且简洁,包含控制流信息。是静态分析的基础
3-地址码
给每一个定义变量一个新的名字,传递到接下来的使用当中,每个变量有1个定义(赋值的目标变量)。唯一的变量名可以间接体现程序流信息,简化分析过程;清楚的Define-Use信息。
静态单赋值
基本概念
LLVM IR
VEX-IR
IR
数据流分析的结果:最终得到,每一个程序点对应一个数据流值(data-flow value),表示该点所有可能程序状态的一个抽象。例如,只关心x、y的值,就用抽象来表示x、y所有可能的值的集合(输入/输出的值域/约束),代表了该程序点的程序状态。
Nodes (BBs/statements)
Edges (control flows)
CFG (a program)
输入/输出状态:程序执行前/执行后的状态(本质就是抽象表达的数据的状态,如变量的状态)。
控制流约束:约束求解做的事情,推断计算输入到输出,或反向分析。
Forward Analysis前向分析:按程序执行顺序的分析。OUT[s]=fs(IN[s]),s-statement
Backward Analysis反向分析:逆向分析。IN[s]=fs(OUT[s])
输出可能正确的信息
(需做over-approximation优化,才能成为Safe-approximation安全的近似,可以有误报-completeness完备性)
注意大多数静态分析都是may analysis;
may analysis
输出必须正确的信息
(需做under-approximation优化,才能成为Safe-approximation安全的近似,可以有漏报-soundness可靠性);
must analysis
基础知识
Definition? D: v = x op y 类似于赋值。
给变量v一个定义d(赋值),存在一条路径使得程序点p能够到达q,且在这个过程中不能改变v的赋值。
检测未定义的变量,若v可达p且v没有被定义,则为未定义的变量。
Reaching Definitions Analysis (may analysis)
某程序点p处的变量v,从p开始到exit块的CFG中是否有某条路径用到了v,如果用到了v,则v在p点为live,否则为dead。其中有一个隐含条件,在点p和引用点之间不能重定义v。
可用于寄存器分配,如果寄存器满了,就需要替换掉不会被用到的变量。
Live Variables Analysis (may analysis)
程序点p处的表达式x op y可用需满足2个条件,一是从entry到p点必须经过x op y,二是最后一次使用x op y之后,没有重定义操作数x、y。(如果重定义了x 或 y,如x = a op2 b,则原来的表达式x op y中的x或y就会被替代)。
用于优化,检测全局公共子表达式。
属于forward分析。
Available Expressions Analysis (must analysis)
Reaching Definitions表示只要从赋值语句到点p存在1条路径,则为reaching,结果不一定正确;
Live Variables表示只要从点p到Exit存在1条路径使用了变量v,则为live,结果不一定正确;
Available Expressions表示从Entry到点p的每一条路径都经过了该表达式,则为available,结果肯定正确。
compare
数据流分析
本质是调用边的集合,从调用点(call-sites)到目标函数(target methods / callees)的边。
Class hierarchy analysis(CHA)
Rapid type analysis(RTA)
Variable type analysis(VTA)
Pointer analysis(k-CFA)
应用:是所有过程间分析(跨函数分析)的基础,程序优化,程序理解,程序调试。
调用图构建
CFG表示的是单个方法的结构
ICFG = CFG + (Call edges + Return edges)。
Call edges:连接调用点和目标函数入口
Return edges:从return语句连到Return site(Call site后面一条语句)
过程间控制流图ICFG
Node transfer:与过程内分析相同,对每个调用点,将等号左边部分去掉。
Call edge transfer:传参
Return edge transfer:传返回值
过程间数据流分析
过程间分析
指针分析:分析指针所有可能指向的对象。
别名分析:分析两个指针是否指向相同的对象,可通过指针分析来推导得到。
Allocation-Site原理:将动态对象抽象成它们的创建点(Allocation-Site),来表示在该点创建的所有动态对象。Allocation-Site个数是有限的。
Heap abstraction
Context-sensitive:根据某函数调用上下文的不同,多次分析同一函数。
Context-insensitive:每个函数只分析一次。
Context sensitivity
问题:考虑语句顺序(控制流)的影响 vs 把程序当做无序语句的集合。
方法:流敏感会在每个程序点都保存一份指针指向关系映射,而流不敏感则对整个程序保存一份指向关系映射。
说明:目前流敏感对Java提升不大,不过在C中很有效,本课程分析的是Java,所以重点讨论流不敏感技术。
Flow sensitivity
Whole-program 全程序:分析全程序的指向关系。
Demand-driven 需求驱动:只分析影响特定域的指针的指向关系。
Analysis scope
Static call: C.foo()
Special call: super.foo() / x.<init>() / this.privateFoo()
Virtual call:x.foo()
影响指针指向
Nodes:Pointer = V U (O x F) 节点n表示一个变量或抽象对象的域。
Edges:Pointer X Pointer 边x -> y 表示指针x指向的对象may会流入指针y。
Edges添加规则:根据程序语句 + 对应的规则。
PFG:用指针流图PFG来表示指针之间的关系,PFG是有向图。
指针分析
访问控制:关注信息访问。
信息流安全:关注信息传播。
信息流:x->y表示x的值流向y。
信息等级:对不同变量进行分级,即安全等级,H-高密级,L-低密级。
安全策略:非干涉策略,高密级变量H的信息不能影响(流向)低密级变量L。
1.信息流安全
保密性—信息泄露,读保护;
完整性—信息篡改,写保护。
完整性错误类型:命令注入、SQL注入、XSS攻击、... 。都属于注入错误。
准确性、完整性、一致性。
准确性表示关键数据不被不可信数据破坏;
完整性表示系统存储了所有的数据;
一致性表示发送的数据和接收的数据是一致的。
完整性更宽泛的定义
2.保密性和完整性
显示流:直接的数值传递。由于显示流能泄露更多信息,所以本课程关注显示流的信息泄露。
隐式信息流—侧信道:程序可能会以一些意想不到的方式泄露数据。
covert channels:信道指的是传递信息的机制,原本目的不是为了传递信息的信道。
3.显式流和隐藏信道
Sources是污点数据的源,一般是有些函数的返回值,如read();Sink是特定的程序点,某些敏感函数。
保密性:Source是秘密数据,Sink是泄露点,信息泄露漏洞。
完整性:Source是不可信数据,Sink是关键计算,注入漏洞。
Sources & Sink
4.污点分析
污点分析
Interprocedural,Finite,Distributive,Subset Problem
Infeasible Paths:CFG中实际不会执行到的路径,如不匹配的调用返回边。这种路径可能会影响到程序分析的结果,但静态分析不能完全判定路径是否可达。
Realizable Paths:跨函数调用产生的返回边和对应的callsite边匹配,这样的path。
Infeasible and Realizable Paths
CFL可达性&IFDS
软件分析
0 条评论
回复 删除
下一页