PatchScope: Memory Object Centric Patch Diffing
介绍
分析目的是为了定位补丁，通过丰富的语意解释为什么要添加补丁。分析补丁的根源，理解补丁细节。
定位补丁
二进制区分技术 [27, 34, 49]
[7, 25, 29] 用静态特征控制流图。动态行为如系统调用[5, 64]
[16, 18, 21, 22, 71]。 上面两种技术在漏洞检测方面的应用
[40, 60, 64] 软件抄袭方面的应用。
[5, 12, 44, 70]混淆抗混淆恶意软件比较
分析补丁
分析补丁成因，理解补丁细节
现有技术静态
APEG [8]。识别一个安全补丁对应的代码是否涉及安全性检察。（定位所有补丁里面有关安全的补丁？？）
SPAIN [72] 识别安全补丁基于一个假设：安全补丁不会改变程序语意，通常引用一个新的分支来检测无效的语意。
SID [68] 通过总结通常类型漏洞的补丁的模式总结来确定安全漏洞的影响
现有技术动态
execution comparison techniques [53, 75] （执行比较技术）
对于观察到的crash，差分切片（differential slicing [30, 67]）为分析构建了相关控制和数据依赖
PatchScope介绍
动态补丁区分技术PatchScope。针对低级的二进制指令，将补丁差异表现为具有丰富语义的高级抽象，可以促进对漏洞来源和补丁细节的研究。
核心推动是主要是两个方面：1.程序处理输入的方式揭露了有价值的语义信息。2.很多安全补丁尤其是内存破坏漏洞旨在更好的调整问题输入的处理。即作者对安全补丁如何影响语义的看法是：它通常修改输入相关数据结构
区分方式为 给定一个POC通过比较打补丁和未打补丁程序两次执行的内存访问序列来识别补丁差异。
识别细节：动态地挖掘在程序执行过程中基于内存访问模式被涉及到的内存对象 通过多标签污染分析，进一步识别了与相应内存对象相关的输入字段。然后定义了内存对象模型来表示对输入字段的操作。通过这种方式我们将动态执行语义抽象为内存对象访问序列，最后用生物信息学的局部序列对比算法来识别patch的不同
作者的贡献
- 对安全补丁的大规模研究的新的见解：通过检查补丁源代码的更改将补丁分为九类
- 以内存对象为中心的技术为补丁区分：提出了新的角度来识别补丁不同即如何通过相应的数据结构操作输入
- 开发的PatchScope在补丁分析中更有效
问题和动机
要解决的问题
从相同poc的比较得到的执行路径得到
- 1.定位补丁的区别。
- 2.用丰富的语义解释已识别的差异去理解补丁以及修补的漏洞
作者假设POC可用，研究主要内容为动态的补丁区分，怎么得到POC不是研究内容
安全补丁模式
别人对补丁分析的研究[37, 41, 46, 65, 68] 提供了补丁数据库。 [72] 补丁分析
[45, 66]。这两篇文章定义了补丁模式，作者对这个进行改进
[8, 50] 1day exp生成技术
从上图可以看到
- 使用最多的方式是添加对输入的安全检查
- 3，4，5改变数据结构（添加变量，修改变量数据类型，把栈换成堆）
- 6, 7, 8, and 9 修改函数和参数
- 说明很多漏洞是逻辑漏洞（不太懂怎么看出来的）
概念补充
syntactic 语法 control flow/call graph [7, 25, 29]
semantics-aware features 语意 dynamic behaviors [20] and system call sequences [5, 64]
跟别人成果比较（会有一些好用的工具）
BinDiff [27], Diaphora [34], and DarunGrim [49] 三种工业上常用的二进制区分工具，在 [31, 47, 48, 55, 62]里面被应用。这些技术是静态分析。
问题：这些工具对很小程度上的代码改变识别效果比较差（如调整缓冲区大小）
符号执行方式
code level [35, 51, 52] or the binary level [15, 25, 40, 70]. 使用符号执行源代码级和二进制级。（用符号执行得到的计算的代码片段来区分二进制区别，用定理证明器检测差异）
DSE [51] and DiSE [52] leverage static analysis techniques to identify differences 用静态方式定位代码区别不准确。符号执行的输出–符号公式特别是指令生成的公式很难理解补丁的效果。
At last, symbolic
execution is typically performed within a basic block [15, 25, 40]
or a loop body [70] at the binary level, which may not be scalable
to deal with complicated patches involving library function calls
(e.g., No. 6, 7, 8, and 9 in Table 1)
符号执行一般是基本块或循环体内操作的不能准确处理涉及库函数调用的复杂补丁（不太对）
库函数和api检测
clone detection [20, 64] and malware variant comparison [5, 23, 33, 44].克隆检测和恶意软件变体比较。这两种场景用的比较多
BLEX [20]。把二进制代码当成黑盒，动态检测，比较他们的相似度。
基于ai的识别
[18, 19, 26, 38, 42, 43, 71, 76] 对微小的代码变化不敏感
作者对分析的要求
- 补丁分析应该对汇编代码之外的补丁进行定位
- 应该输出可解释的结果
- 应该为理解和修补漏洞提供丰富的语意
memory object access sequence (MOAS)
为了解决上面三个要求提出了这个
MOA
存储输入的数据结构没有意义，各种程序对数据结构的操作反映了丰富的语意信息。 对各种对象的访问就是memory object access (MOA).
用内存对象表示沿着一条执行路径的逆向工程数据结构。mobj=(alloc,size,type)
alloc表示分配内存对象的上下文信息，size是字节为单位的内存空间大小，type表示类型包含静态变量和在队里申请的动态变量以及栈里的局部变量(type包含静态变量，局部变量，全局变量)因为内存对象申请的多样化来自不同类型的数据结构，所以定义alloc要考虑上下文
alloc的表示方法
alloc的表示方法：
- 1.静态变量用地址表示
- 2.局部变量用栈帧指针以及这个正在调用函数的上下文。比较特殊的是寄存器存储局部变量，用寄存器来表示它
- 3.堆的动态变量，用申请堆的地址和调用malloc的地址表示（用hook malloc实现）
如图上面的例子中a图中temp的mobj的alloc会写函数调用的上下文（作者也没有说清楚），main-serveconnection-Log，栈帧指针的偏移。
Memory Object Access
A(mobj) = (mobj, cc, op, optype, α)
-
mobj是上面说到的
-
cc记录了使用mobj的上下文，因为mobj能够通过指针被其他函数访问，cc包括引用mobj的函数以及该函数引用mobj的上下文。
-
op引用mobj的数据流相关操作，主要关注三种输入传播的指令：数据移动指令，算数指令和库函数/系统调用的调用指令。用op来表示这些指令的操作码以及这些指令的地址
-
optype 包含两种访问类型：读，写
-
α连续的输入字节，输入字段在运行期间会改变。
内存访问对象的比较
临时内存对象沿着执行路径形成一个内存访问序列memory object access sequence (MOAS)
用相同的Poc运行修补过的和原始文件，动态收集内存访问对象序列比较他们的不同
MOAS会存储内存对象分配，内存对象操作，内存对象与输入字段的关联关系信息
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SPkZjwi9-1619507620106)(./image/image-20210312165716598.png)]
上图是分析结果，只有6个不同点，与之相比bindiff有30个
a1，b2为申请的内存对象。a2，b2为内存对象在运行期间被怎样引用。
a2，b2展示了上下文<main-serveconnection-Log> operations 0x804acd5: call sprintf operation types W/R correlated inputs（相关输入） (间隔 [0x4, 0x15d]).
上图的比较结果可以看出：L2和R2不同原因是申请空间方式，这回导致访问L3和R3不同。
通过上面的图中b1的R3被补丁变成了堆，并且污点执行确定这里的size跟输入长度有关，R2虽然被改成了堆，但是长度并没有被输入改变通过逆向发现这里的heap大小是跟一个常亮字符串相关的，足够大的输入依然能够造成溢出。
回到上面图中打过的补丁，把数据存储从stack变成heap但是数据的大小跟输入无关也就说明这个漏洞依然可能存在。
PATCHSCOPE系统设计
包含dynamic taint（动态污点执行） and execution monitoring（执行监控）, memory object excavation（内存对象挖掘）, memory object access construction（内存访问对象构建），MOAS alignment（内存访问对象对齐）。
动态污点执行和执行管理
在**DECAF [28]**的基础上做的，是一个基于qemu的完整系统动态分析平台。 作者进行修改使之支持多标签污染传播并且记录后续分析中有必要的运行时信息
每个输入字节作为唯一污点标签，如果一条指令的多个源操作数被污染，将设置目标操作数的污染标记为所有源操作数污染标记的并集。
当然还需要保存一些运行时指令状态信息，后面需要恢复栈获取操作数的纸等操作，为了方便获取分配的空间还需要劫持系统调用或者库函数的调用。这些功能DECAF可以实现。
函数调用栈识别
一般是计算call，ret对，难点是补丁可能会触发编译器的一些优化选项干扰识别。
一般包含这两种tail call optimization [11] and。function inline.
- 尾部调用优化：会开启跳转指令代替call指令 GCC/Clang -O2和 -O3开启了这种优化，在Apache-1.3.35作测试其中这种优化的代码占了大约12%。
- 函数内联是调用的时候把被调函数的代码塞进调用函数里
解决：
使用 iCi [17]检测基于jmp的调用。（iCi的检测原理是检测跳转的位置是不是在函数内，检测跳转到的地方是不是函数的开始）。
对于内联函数的处理是直接不管，对于补丁使用内联原始文件没使用的情况这里的内存对象的上下文部分将会不同。
挖掘数据结构与输入字段
基于Howard [57]的识别，但是作者的内存对象只是识别和输入字段相关的内存对象而不是所有。
根指针的提取
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jfKmANo1-1619507620110)(./image/image-20210313102904140.png)]
申请一个内存对象通常返回一个指针我们定义这个指针为根指针。内存对象和根指针是一对一关系我们通过根指针提取内存对象。
- 对于一个静态变量我们直接使用这个内存地址表示根指针
- 堆上的动态变量hook内存分配函数获取返回值为根指针
- 局部变量的根指针由ebp的偏移量表示。 难题是有时候esp表示，我们进行了归一化为ebp表示，执行期间记录的执行状态可以检测到指针是否有别名（如上图的 mov $0x804b108,0x4(%esp) 中函数设置参数的时候使用esp的方式）。第二个难题是当编译器添加
- fomit-frame-pointer参数的时候不会设置栈帧这时候用esp表示（如果检测到没有平衡栈帧的语句就可以确定是否开启这种优化）
size的提取
- 堆申请的空间可以由参数确定。
- 对于静态变量和临时变量这里作者采用两个变量之间的距离表示，但是有时候中间有些内存对象没有被使用（作者关注的内存对象仅仅是和输入有关的）会造成错误。作者认为，两次内存对象之间的比较可以抵消这种不确定性。识别size准确性不足，有待改进改进完可以进行缓冲区溢出的识别。
追踪指针传播
识别内存对象可以识别内存对象的定义和分配。之后将是追踪这些内存对象。
基于Howard [57] ，具体流程
- 识别所有根指针。
- 其次通过追踪根指针的数据移动来识别别名指针
- 还要识别指针上的算术运算指令
- 最后通过检查oad/store对内存地址的依赖性获取根指针。
计算方式为address = base + (index × scale) + offset
关联输入字段
使用多标签污染传播的结果去建立内存对象和输入字段之间的关联。
对每个受污染的操作数
-
首先确定污染标签，如果操作数是寄存器回朔执行获取到相关内存操作数。
-
第二提取根指针从根指针到内存操作数基地址的偏移量。
-
第三在引用的内存对象和带有污点标签的输入之间构建关联关系。
输入连续的字符串或者数组通常是用循环或者字符串操作来处理，基于heuristics（翻译为启发式算法）给这种内存对象分组。
具体一点就是：
- 首先识别内存单元属于同一内存对象（几个内存单元操作连续输入使用来自根指针的连续偏移量）。
- 然后把它们分组为同一个内存对象。
构建MOAS
整个MOAS确定了mobj, cc, and α，还剩下op and optype
-
对于数据移动指令，通过确定被污染对象被存储或者加载来确定optype。
-
低于算数指令先确定是否是内存对象的一个副本，如果是，取算数操作的操作码作为op，并且通过是否污染寄存器是源或者目的操作数作为optype。
-
对于调用的库函数，使用运行时函数摘要进行优化，然后更新op和optype。（作者的描述很模糊）
MOAS排列
作者尝试过最长公共字串算法，不能解决问题。
最终选择使用这种算法Smith-Waterman algorithm [58] 更好地从两个序列中找到相似的局部变量。
因为相同内存对象可能有不同的根指针，转化为向量用SMITH-WATERMAN ALGORITHM算法比较两个内存访问对象之间的相似度。在附录D记录了关于应用这个算法的细节。
史密斯-沃特曼算法（Smith-Waterman algorithm）是一种进行局部序列比对（相对于全局比对）的算法，用于找出两个核苷酸序列或蛋白质序列之间的相似区域。该算法的目的不是进行全序列的比对，而是找出两个序列中具有高相似度的片段。（这个算法或许有用）
问题
如果内存对象被拷贝，然后对副本和源进行了不同的操作是怎么处理的。