软件静态分析
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信息。
IR
LLVM IR
VEX-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])
may analysis
输出可能正确的信息
（需做over-approximation优化，才能成为Safe-approximation安全的近似，可以有误报-completeness完备性）
注意大多数静态分析都是may analysis；
must analysis
输出必须正确的信息
（需做under-approximation优化，才能成为Safe-approximation安全的近似，可以有漏报-soundness可靠性）；
Reaching Definitions Analysis (may analysis)
Definition？ D: v = x op y 类似于赋值。
给变量v一个定义d（赋值），存在一条路径使得程序点p能够到达q，且在这个过程中不能改变v的赋值。
检测未定义的变量，若v可达p且v没有被定义，则为未定义的变量。
Live Variables Analysis (may analysis)
某程序点p处的变量v，从p开始到exit块的CFG中是否有某条路径用到了v，如果用到了v，则v在p点为live，否则为dead。其中有一个隐含条件，在点p和引用点之间不能重定义v。
可用于寄存器分配，如果寄存器满了，就需要替换掉不会被用到的变量。
Available Expressions Analysis (must 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分析。
compare
Reaching Definitions表示只要从赋值语句到点p存在1条路径，则为reaching，结果不一定正确；
Live Variables表示只要从点p到Exit存在1条路径使用了变量v，则为live，结果不一定正确；
Available Expressions表示从Entry到点p的每一条路径都经过了该表达式，则为available，结果肯定正确。
过程间分析
调用图构建
本质是调用边的集合，从调用点（call-sites）到目标函数（target methods / callees）的边。
应用：是所有过程间分析（跨函数分析）的基础，程序优化，程序理解，程序调试。
Class hierarchy analysis(CHA)
Rapid type analysis(RTA)
Variable type analysis(VTA)
Pointer analysis(k-CFA)
过程间控制流图ICFG
CFG表示的是单个方法的结构
ICFG = CFG + (Call edges + Return edges)。
Call edges：连接调用点和目标函数入口
Return edges：从return语句连到Return site（Call site后面一条语句）
过程间数据流分析
Node transfer：与过程内分析相同，对每个调用点，将等号左边部分去掉。
Call edge transfer：传参
Return edge transfer：传返回值
指针分析
指针分析：分析指针所有可能指向的对象。
别名分析：分析两个指针是否指向相同的对象，可通过指针分析来推导得到。
Heap abstraction
Allocation-Site原理：将动态对象抽象成它们的创建点（Allocation-Site），来表示在该点创建的所有动态对象。Allocation-Site个数是有限的。
Context sensitivity
Context-sensitive：根据某函数调用上下文的不同，多次分析同一函数。
Context-insensitive：每个函数只分析一次。
Flow sensitivity
问题：考虑语句顺序（控制流）的影响 vs 把程序当做无序语句的集合。
方法：流敏感会在每个程序点都保存一份指针指向关系映射，而流不敏感则对整个程序保存一份指向关系映射。
说明：目前流敏感对Java提升不大，不过在C中很有效，本课程分析的是Java，所以重点讨论流不敏感技术。
Analysis scope
Whole-program 全程序：分析全程序的指向关系。
Demand-driven 需求驱动：只分析影响特定域的指针的指向关系。
影响指针指向
Static call： C.foo()
Special call： super.foo() / x.<init>() / this.privateFoo()
Virtual call：x.foo()
PFG：用指针流图PFG来表示指针之间的关系，PFG是有向图。
Nodes：Pointer = V U (O x F) 节点n表示一个变量或抽象对象的域。
Edges：Pointer X Pointer 边x -> y 表示指针x指向的对象may会流入指针y。
Edges添加规则：根据程序语句 + 对应的规则。
污点分析
1.信息流安全
访问控制：关注信息访问。
信息流安全：关注信息传播。
信息流：x->y表示x的值流向y。
信息等级：对不同变量进行分级，即安全等级，H-高密级，L-低密级。
安全策略：非干涉策略，高密级变量H的信息不能影响（流向）低密级变量L。
2.保密性和完整性
保密性—信息泄露，读保护；
完整性—信息篡改，写保护。
完整性错误类型：命令注入、SQL注入、XSS攻击、... 。都属于注入错误。
完整性更宽泛的定义
准确性、完整性、一致性。
准确性表示关键数据不被不可信数据破坏；
完整性表示系统存储了所有的数据；
一致性表示发送的数据和接收的数据是一致的。
3.显式流和隐藏信道
显示流：直接的数值传递。由于显示流能泄露更多信息，所以本课程关注显示流的信息泄露。
隐式信息流—侧信道：程序可能会以一些意想不到的方式泄露数据。
covert channels：信道指的是传递信息的机制，原本目的不是为了传递信息的信道。
4.污点分析
Sources & Sink
Sources是污点数据的源，一般是有些函数的返回值，如read()；Sink是特定的程序点，某些敏感函数。
保密性：Source是秘密数据，Sink是泄露点，信息泄露漏洞。
完整性：Source是不可信数据，Sink是关键计算，注入漏洞。
CFL可达性&IFDS
Interprocedural，Finite，Distributive，Subset Problem
Infeasible and Realizable Paths
Infeasible Paths：CFG中实际不会执行到的路径，如不匹配的调用返回边。这种路径可能会影响到程序分析的结果，但静态分析不能完全判定路径是否可达。
Realizable Paths：跨函数调用产生的返回边和对应的callsite边匹配，这样的path。
0 条评论
下一页
为你推荐
查看更多
