车如流水马如龙,花月正春风

3.9号，苏杉杉宣布了暂休的决定，可是在小偶像的行业里，暂休的一百个大概只有一个会回来，而这次的气氛也是十分的沉重，所以大概率…，整场演出和表演完之后粉丝的呐喊和合唱让人泪流。

告别时刻，你的面色像是波澜不惊的湖面，看上去一如人生初见时的云淡风轻。可你红着的眼眶和泪水却分明出卖了你，就像平静湖面下的暗流涌动，这是留恋，是不舍，是对过往的满目深情。再见，苏杉杉

Interprocedural Analysis

Interprocedural Analysis

今日推荐歌曲：R&B歌曲 别问很可怕-J.Sheon

可惜一溪风月,莫教踏碎琼瑶

Motivation

过程内的分析未考虑函数调用，导致分析不精确，例如存在如下程序（常量传播，Constant Propagation）

_P_2_PDPR__KM4I_L4Z@_GC.png

Inraprocedural analysis为了safe-approximation会采用最保守的假设，也就是假设方法调用可以做任何事情，基于这种过于保守的假设，在Inraprocedural analysis下，会认为：

1
n = NAC x = NAC, y = NAC

所以需要使用过程间分析：Inter-procedural Analysis，考虑函数调用，又称为全程序分析（Whole Program Analysis），需要构建调用图，加入 Call edges 和 Return edges

Call Graph Construction

本质是调用边的集合，从调用点（call-sites）到目标函数（target methods / callees）的边

_4WSCVS_3UZT398___0LTVA.png

Call Graph Construction

Q_R_HK8JRAMUGX~_BY_MCML.png

越往上，速度越快，但是精度越低，越往下速度越慢，但是精度越高。主要学习的就是CHA和k-CFA算法

Method Calls(Invocations) in Java

在java中的调用类型为三类 其中Virtual Call主要应用于多态，因为多态，其目标方法只能在运行时确定；在Java中，认为除了静态方法、构造方法、私有方法和父类方法，其他的都为Virtual Call

VIB___V1K2_A3_8A___FB_T.png

Z8Y`@DSXV`~R_AQ_IRZU_4B.png

Receiver objects：方法调用对应的实例对象（static方法调用不需要对应实例）

Target methods：表达IR指令到被调用目标方法的映射关系

Num of target methods：call对应的可能被调用的目标方法的数量。Virtual call与动态绑定和多态实现有关，可以对应多个对象下的重写方法。所以Virtual call的可能对象可能超过1个

Determinacy：指什么时候能够确定这个call的对应方法。Virtual call与多态有关，只能在运行时决定调用哪一个具体方法的实现。其他两种call都和多态机制不相关，编译时刻就可以确定

Method Dispatch of Virtual Calls

virtual call 在程序运行时才能得到，virtual call 基于2个要素

  1. receiver object的type
  2. call site的方法签名（method signature）

方法签名由以下部分组成

1
2
Signature = class type + method name + descriptor 
Descriptor = return type + parameter types

V450_42_8XQI0~_1IY_6HK8.png

用 Dispatch(c, m) 来模拟动态 Method Dispatch 过程，c 表示 receiver object，m 表示函数签名

RKAUY_V_P_BL8_UTY5__RRF.png

示例如下：

YO__O6NNFBZ28J1___45NDX.png

Class Hierarchy Analysis (CHA)

Definition of CHA

Require the class hierarchy information (inheritance structure) of the whole program

Resolve a virtual call based on the declared type of receiver variable of the call site

Assume the receiver variable a may point to objects of class A or all subclasses of A（Resolve target methods by looking up the class hierarchy of class A）

对一个 call site 执行 Resolve 方法得到所有可能的 target methods 算法如下

_M3MUIR77_W_5_LY@1URK@7.png

示例如下：

N2Y~EP_5_J_71I0_H6WGZIK.png

CHA的优势是速度快原因是只考虑call site中receiver variable的declared type和它的继承结构还有忽略数据流和控制流信息

CHA的劣势是精度较低原因是容易引入虚假目标方法和没有使用指针分析

Call Graph Construction

Build call graph for whole program via CHA

Start from entry methods (focus on main method)

For each reachable method 𝑚, resolve target methods for each call site 𝑐𝑠 in 𝑚 via CHA (Resolve(𝑐𝑠))

Repeat until no new method is discovered

从入口方法开始（例如对于Java而言的main方法）对于每一个可达方法m，在方法m中通过CHA算法为每一个call site计算目标方法一直到重复这个过程直到没有新的方法被发现

UC~YHTF3NA05ZCP_OR__M_K.png

示例如下：

37_9__LI0CXA_UYGV34_OQM.png

Interprocedural Control-Flow Graph

ICFG = CFGs + call & return edges

Call edges: from call sites to the entry nodes of their callees

Return edges: from exit nodes of the callees to the statementsfollowing their call sites (i.e., return sites)

示例如下：

![8_MKAEY5~`LRXFGHG__3_CS.png](https://img.le1a.com/2023/01/20/f64f1cc6406c8.png)

Interprocedural Data-Flow Analysis

![X__DMM_B9H433XOR`RK4Q.png](https://img.le1a.com/2023/01/20/1bcad91c5df58.png)

4种transfer函数

Node transfer

Edge transfer

  • Call edge transfer
  • Return edge transfer
  • Node transfer 每一个函数调用都要kill掉LHS（Left hand side）的变量

示例如下：

@OQO_I_7G@_021_NJI_6S_3.png

Data Flow Analysis

Data Flow Analysis

开局一张图

_BJIAZQ__`YP`O0PBHJ42OT.png

如图所示一共有三种数据流分析应用分别为reaching definitions、live variables、available expressions、available expressions，不同的数据流分析有不同的 data abstraction和不同的 flow safe-approximation strategies，如不同的 transfer functions 和 control-flow handlings

Overview of Data Flow Analysis

Data Flow Analysis可以概括为：How Data Flows on CFG，展开来的英文就是 How application-specific Data Flows through the Nodes(BBs/statements) and Edges(control flows) of CFG(a program)？

How application-specific Data :对数据的抽象(data abstraction) e.g:+, -, 0 等

Flows ：根据分析的类型，做出合适的估算

Nodes：数据如何通过转换函数（Transfer functions）进行分析处理

Edges ：Control-flow如何处理，例如两个控制流汇入一个BB

~IOZLO1IGM3_OLUCJN~1_OP.png

Notations for Transfer Function’s Constraints

转换函数的约束规则的基本概念，主要分为这两种analysis

![J_ZXF9G`0_QXQ_42AOID@UN.png](https://img.le1a.com/2023/01/19/9ae950aaa0f55.png)

Notations for Control Flow’s Constraints

控制流约束规则如下

6V_I@H_MIO24VBP6F51__N9.png

Reaching Definitions Analysis

A definition d at program point p reaches a point q
if there is a path from p to q such that d is not “killed” along that path

![IVZ8R2QU_KI`O7YI_YL9R.png](https://img.le1a.com/2023/01/19/a81a7c8427fc2.png)

假定 x 有定值 d (definition)，如果存在一个路径，从紧随 d 的点到达某点 p，并且此路径上面没有 x 的其他定值点，则称 x 的定值 d 可达 (reaching) p。如果在这条路径上有对 x 新的定值，我们说变量 x 的这个定值 d 被杀死 (killed) ，其实就是说给变量v一个定义d，存在一条路径使得程序点p能够到达q，且在这个过程中不能改变v的赋值

应用于检测可能未初始化的变量；例如，在CFG的Entry节点，为所有的变量引入dummy definition（也就是代表未初始化变量的定义），如果dummy定义可到达点p，且定义对应的变量被使用，则这个点可能存在undefined错误；

Data Flow Values/Facts

![2BJ_Z1X@@`HQP_UN9_12Q_A.png](https://img.le1a.com/2023/01/19/5878b82a33b1c.png)

算法如图：

N__~RP_@F3Y_QWQGRB_K_2T.png

Transfer Function:

OUT[B]=genB∪(IN[B]−killB) gen 的是新的、definitionkill 的是其他 Basic Block 里定义 v 的 definitions（如对于一条赋值语句 D: v = x op y，该语句生成了 v 的一个定值 D，并杀死程序中其它对变量 v 定义的定值）

Control Flow:

IN[B]=∪P a predecessor of B OUT[P]

一个例子如下：

![LXSFRWYGM`_NZ8UB8_9KZZQ.png](https://img.le1a.com/2023/01/19/6ac0bcd1eea15.png)

一个例子运行结果为

![_F6NEAKWTG_P`_557_K__AV.png](https://img.le1a.com/2023/01/19/f304600b39d60.png)

Live Variables Analysis

Live variables analysis tells whether the value of variable v at program point p could be used along some path in CFG starting at p. If so, v is live at p; otherwise, v is dead at p.

某程序点p处的变量v，从p开始到exit块的CFG中是否有某条路径用到了v，如果用到了v，则v在p点为live，否则为dead。其中有一个隐含条件，在点p和引用点之间不能重定义(redefined)v。

![_A1_V7EO_Y2GPW@_I`WW3.png](https://img.le1a.com/2023/01/19/a51950fab00c6.png)

可以应用于寄存器分配，当一个变量不会再被使用，那么此变量就可以从寄存器中腾空，用于新值的存储。

Data Flow Values/Facts

__XD_1___1_V_TZ2A4_KH8D.png

Control Flow：

OUT[B]=∪S a successor of BIN[S]

Transfer Function:

IN[B]=useB∪(OUT[B]−defB) use 是指那些被用到，且用之前在本 basic block 没有被重定义过的变量、def 是指在本 basic block 中重定义的变量

算法如下：

![YMY`W_IN__K_MQP@V7DT_45.png](https://img.le1a.com/2023/01/19/44b6ae870f743.png)

例子如下：

3R_16~8____7_U9L_3_NK79.png

一个例子运行结果为

F_TERWHO6__3_QOT8C_Q_6K.png

Available Expressions Analysis

An expression x op y is available at program point p if all paths from the entry to p must pass through the evaluation of x op y, and after the last evaluation of x op y, there is no redefinition of x or y

程序点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就会被替代）

Transfer Function：

OUT[B]=genB∪(IN[B]−killB) gen：基本块求值 x op y，且之后没有对 x 或 y 赋值、kill：基本块对 x 或 y 赋值，且没有重新计算 x op y（如果重新计算，即使值不一样，也属于 gen)

Control Flow:

IN[B]=∩P a predecessor of BOUT[P]

WO6_K56A0H_FR_RR3B_S_0C.png

算法如下：

0_YAA8NZ6_~_B7COB_P7_Y9.png

运行实例如下：

_8G_OU_B``CU8UB_9BK@5VA.png

静态分析学习笔记

静态分析学习笔记

想学静态分析已经很久了但是一直没有系统的学习过，中间看过asm字节码技术、gadgetinspector、tabby、codeql的原理分析但依然对于静态分析不了解，最近感觉也快离开学校了想在离开学校之前学会这个技术

program analysis

程序分析01_1.jpg

Compilers and Static Analyzers

编译器将source code 转换为machine code 其中流程图如下图所示

FI_KA39SJY32Q_LEO_4_3HQ.png

![M5_45`QM_V__CAWWZB_W2UG.png](https://img.le1a.com/2023/01/17/5168adfe73eaa.png)

Intermediate Representation

看上图得知在translator层将decorated AST 翻译为生成三地址码这样的中间表示形式(Intermediate Representation)并对其做静态分析，也就是说静态分析基于IR，通常IR的表现形式为三地址码（3AC，Three-Adress Code），静态程序分析通常会将IR转换为CFG（Controll Flow Graph）进行下一步分析

Three-Address Code（3AC）

3AC是一种IR，在每个指令的右边至多有一个操作符，每一语句最多有三个“地址”，地址可以是名称，变量，常量（编译器生成的临时变量 Compiler-generated Temporary: t1, t2）

常见的3AC如下

  • x = y bop z：双目运算并赋值，bop = binary operator

  • x = uop z：单目运算并赋值，uop = unary operator

  • x = y：直接赋值

  • goto L：无条件跳转，L = label

  • if x goto L：条件跳转

  • if x rop y goto L：包含了关系运算的条件跳转，rop = relational operator

在soot中的3AC如下

  • @parameter：函数参数
  • $x：临时变量
  • <method signature>：类+返回值类型+方法名+函数参数类型
  • <init>：构造函数
  • <clinit>：类初始化函数（静态变量初始化等）
  • invokespecial：调用构造函数、父类方法、私有方法
  • invokevirtual：实例方法调用（virtual dispatch）
  • invokeinterface：不能优化、调用接口、检查接口实现
  • invokestatic：调用静态方法
  • invokedynamic：运行其他动态语言

Static Single Assignment（SSA）

静态单赋值（SSA），就是让每次对变量x赋值都重新使用一个新的变量xi，并在后续使用中选择最新的变量传递到接下来的使用当中，每个变量有唯一的定义，优点是但缺点也很明显，就是因为会引入过多的变量还有phi function，优点也是因为变量唯一而唯一的变量名可以间接体现程序流信息，简化分析过程

  • Give each definition a fresh name
  • Propagate fresh name to subsequent uses
  • Every variable has exactly one definition
1
2
3
4
5
3AC        | SSA
p = a + b    p1 = a + b
q = p - c    q1 = p1 - c
p = q * d    p2 = q1 * d
q = p + q    q2 = p2 + q1

OS_LE_8_UV5FCCR01TI93_I.png

Basic Blocks (BB)

  • 96G6H7BZ@@3~___~XPPLRUX.png

basic blocks是一个最长的语句序列，并保证入口只能在最开始指令且出口只能在最后一个指令，实际操作为将程序的若干个三地址码分为几个basic blocks,每个bb都满足上图的要求，下面将程序标注为p 如何去构建这些bb的算法为

  • INPUT: A sequence of three-address instructions of P

  • OUTPUT: A list of basic blocks of P

    METHOD:

    (1) Determine the leaders in P

    • The first instruction in P is a leader
    • Any target instruction of a conditional or unconditional jump is a leader
    • Any instruction that immediately follows a conditional or unconditional jump is a leader

    (2)build bb :A BB consists of a leader and all its subsequent instructions until the next leader

  • O21_@_F`B`_AU_8_@EH_VVB.png

Control Flow Graphs

Control Flow Graphs的主体就是basic blocks，我们对basic blocks添加块到块的边，添加的规则是块 A 和块 B 之间有一条边，

1、基本块A的结尾有跳转指令跳转到基本块B

2、原始指令序列中，B紧跟着A，且A的结尾不是无条件跳转。

除了这两个添加规则以外，我们还需要添加两个额外的节点entry和exit，所以刚才图片构成的bb画成cfg图应该如下图所示

<<<<<<< HEAD

=======

81841d6924b6b29513f63a397204312cda445246

CVE-2022-22947SpringCloud复现及分析

CVE-2022-22947SpringCloud复现及分析

typora的图片传不上来 于是直接转成图片放上来
需要了解漏洞要点的文章链接
https://blog.csdn.net/weixin_44141495/article/details/110160186

https://cloud.spring.io/spring-cloud-gateway/multi/multi__actuator_api.html

https://www.cnblogs.com/liukaifeng/p/10055867.html

https://github.com/vulhub/vulhub/blob/master/spring/CVE-2022-22947/README.zh-cn.md

https://juejin.cn/post/7021720843898060807