the-story-of-me

先讲一个2016年博客刚开的故事:

先听我讲完一个故事,关于我的故事,一个摸爬滚打的”黑客“成长的故事,我很早就接触过这个专业的内容,说起来我初中就开始接触网络安全,那是我因为想玩私服却中毒了,那时在网上到处找工具杀毒,可惜还是没能成功,之后只好重装系统。这过程中耽误了大量的时间,最后导致我爹发展很多年的游戏账号被洗了。于是在愧疚和不甘的情绪下, 这次意外的邂逅让我选择了未来的人生的路, 也慢慢变成了同学眼中的"黑客"。

从那以后我开始研究各种杀毒软件,研究如何让电脑变得更安全. 去了很多论坛,意外地去了360, 我骗了那个论坛大管理,还记得那个叫人随云,我当了其中一个版主, 他一定不会知道在他面前的只是一个初二的学生。还记得是防火墙的一个版主。只是我不是大牛,其实什么都不会,只会百度, 但是也能帮助别人解决一些问题, 似乎那时候360自己的防火墙才刚刚内测。特别地,那时觉得拥有一个远控很酷,我到处找,可没有方向,到最后被别人骗到被控制,但我还是想要一个。最后我找了一个黑客论坛,我注册了帐号,开始在里面找各种东西学,很幸运我遇到了我生命中帮助我走上这条路的朋友,或者说是老师。

开始弄扫端口,弄肉鸡,没有服务器扫端口,所以只好无奈的找别人苦苦的求一个,却被我如获至宝,135,1433是那个时候最流行的东西吧,一个免杀的远控和扫端口,就是你的最大的宝物,我也成了其中一个人,很幸运我遇到了那些愿意帮助我的人,在这条路上很少有人愿意闲出时间帮你,远程教我lcx转发端口,给我远控,他教我踏踏试试去学一门语言,帮我远程装VC6,我心底谢谢他,我过了很长时间才知道,他放弃了他的爱好,回家结婚生子,有些时候要扛氧气瓶子走近70度的斜坡,我想这就是现实,我现在也没跟他联系过了,也许他忘了我这个曾经渴求的技术的菜鸟,但我心底始终有这么一个人。

从那开始我认识到还是要学一门语言才行,选择了c语言,放学跑到新华书店高高兴兴的买了一本c语言的书,我把他当作至宝,可惜入门很难,我逐渐放弃,过了一段时间我又重启,不知道在哪看见一句话说视频学习可能会好一点,我开始了视频学习,叫一个郝斌的c语言教程,很生动,奇迹般我坚持了下来,170课每节课几十分钟,我坚持了下来,我逐渐能看懂一些平时的代码,我很庆幸自己学了c,这样我都能大致看懂其他语言,对我帮助很大。

那时,我又认识了一个我真正的师傅–冰蓝,他已经能自己写一些端口扫描的,他告诉我是用c写的,我平时有一些不懂的东西就问他. 因为逐渐地进入了初三,学业也比较重了,但并没有阻挡我的热血,一次我问我师傅,你最近在干嘛,他说渗透,我那时并不懂什么叫渗透,很好奇,师傅带我进入了这个新奇的领域,给我了一个90sec论坛账号和一些资料,但我那时我并没有在意。后来随着我师傅,我认识许多朋友,如今却已早已不联系。

那段时间,我学了做免杀,特征码,花指令,跳转,依稀还在心头,我还记得那是做出第一个ghost的免杀是多么高兴,过了金山,360,发在了论坛上,给大家分享。一个免杀许多特征码要改,是很难的,灰鸽子就太难了,几百处,所以我还是有耐心。我又学了缓冲区溢出,感谢ice的几个G的教程,如今shellcode都忘记的差不多了,还学了逆向破解,吾爱破解应该是最厉害的论坛吧,可惜没汇编的知识,很难我放弃了。 那时我记得越南菲律宾的南海权益站爆发了,身为小黑客的我也必须要给祖国做出自己的一份贡献,很搞笑是那时候在yy上(语音软件)在集合,我遇到了一个人还跟他讲技术,之后我才发现是一个大牛,我认为自己很搞笑,之后却成为了好朋友。

那时不懂技术就ddos呗,会的人就渗透,这一次我才真正的进入到渗透的奥秘,简单的sql开始,google搜索,到之后的bt5渗透平台,第一次拿后台,第一次拿shell,第一次拿服务器,我很开心那段时间,我常常因为往软件里跑个站睡着了,一睡醒就扫好了,那段时间技术提高很快,逐渐初三快结束了,考试我差几分没考起重点高中,出了几万块,我心里过意不去,离开了自己的网络,将一切东西封存,开始了努力学习,常常就翻翻c语言书,心里还是挺温暖的。

高中是一个学习的青春,每个人都这样,我也不过如此,没有了太多时间去弄其他的。离开了自己钟情的网络,时常上课会想想这些经历,总会笑起来。高中的图书馆我也去过不少但书太少太老,但也很感谢,学了linux操作系统,javascript等等,不过忘的差不多了,高三结束了,高考如期举行,在填志愿的时候,我毅然决然地选择了信息安全,每一个学校都是只填了这一个专业且不服从调剂,父母都给我担心。想考军校,去考了,没考起,体检太紧张,心跳快了,既然没考起就安心上学,我选择了许多信息安全的专业的学校,但是因为数学意外地失败,其实也不是意外,后知后觉吧。没想到来了天津理工,但是预料之中的。

沉迷了半年在大学生活,我有缘在博客园上看见了一个高二的学生追逐信息竞赛的梦想和执着,我想到了自己,上了自己理想的专业却无所作为, 我想重新开始,别忘了当初的梦想。曾经的hacker梦,未来谁也说不定,我的那些朋友应该基本都离开了网络,我是不是该坚持呢,我想只是我的梦想。我一路走了也学会了很多,不放弃。就这样,我一路走来与hacker有缘,我会坚持,从来都是自学,大多数黑客都是这样走来的吧。

上面就是我故事, 但是实际要精彩的多,我写不出来。现在看来那些在的技术不过如此可笑,但我现在我总少一点当时在那种兴奋感,我走过的路没人知道,我的努力没人看见,不过没事。我知道自己在什么,累了歇歇。

如何走下去?

不管你是如何走上这条道路。首先你要学会感谢自己这一路走来你没有放弃,感谢自己一路上变得如此坚强。有人常常问我如何学起hacker,我可能一时无法回答他,因为这过程充斥了太多偶尔,缘份。也许你遇见我也是一种缘份,回头去看看那些牛逼的人,他们的成长之路也充满着太多偶尔,也许你生来就是为了这,喜欢探索,也许你会走在很顺。首先你得问自己一个问题,你是否真的对它感兴趣,不感兴趣,我劝你趁早放弃,浪费时间!

1.首先你可以去寻找一本类似所谓黑客的书看看是否感兴趣,如果有兴趣接着下去。

2.当一段时间脚本小子,然后可以接着深入。

3.学习一门语言或者多种

接下来的路你比我懂

学着独立去完成一个东西,别急着问别人,别人也没有那么多的耐心。其实你的路我也不知道,自己走下去,我相信你会走出自己的路。也许你现在能想到什么,那我也就值得了。

劈柴,打水,喂马,周游世界,挺好。end -M4p1e


再讲一个2021年的故事

看着上面稚嫩的语言,往事不堪回首啊!前天我在准备更新博客的时候,脑子抽筋把服务器reset了. 刚开始我楞了几秒,很快我知道我弄出大问题了. 当前vps是vultr,我马上去问了他们的工作人员,能否恢复数据?答案也很显然是不能,因为我没有打任何的snapshot和做任何的backup. 当时很无助,我不知道怎么办,那种感觉我不知道怎么说... 你最珍贵的东西突然间全部没有了! 但是我马上冷静下来,互联网是有记忆!说到这里不得不提一下paadqd了,它是大三我突发奇想写的一个php后端web框架. 你肯定会觉得它的名字很奇怪对吧,实际上它是有内在含义的,它代表着一条崎岖不平的路,象征着我这一路走过来的信安路. 是不是还像那么回事儿?哈哈!为了让它支持markdown,我使用了stackedit这样一个前端markdown的编辑器,paadqd会把文章完整的content内嵌到js中作为一个常量,交给stackedit去处理。 正是当初这一懒惰的做法,才有了现在的一线生机. 首先检查了一下google 是否有cache我的内容,Yes! its there! 几乎所有东西都在,配合百度的快照我觉得一切都回来了. 随即把所有的cached html都爬了下来. 当然也丢掉了一些内容,我想那些内容估计也没有人看,不如让它随风远去吧...

随之而来的问题是,我需要重建整个博客. 这一次我抛弃了我的paadqd,选择了更为省心的hexo. 我的第一准则是让我的博客看起来干净,于是开始了手工重建的工作,经过12小时的奋战,就有了现在你们看见的效果. 不得不说效果还是不错的嘛! 这一次我做了万全策略! 好吧,既来之,则安之。无论如何,新博客开张了!

2021-05-05


directed-greybox-fuzzing

Directed Greybox Fuzzing

https://acmccs.github.io/papers/p2329-bohmeAemb.pdf

0x00 用一句话描述其内涵

directed fuzzer把大多数时间花在其关注的特定程序点上.

0x01 它能做什么呢?

  • patch testing 把关注点放到patch changelog上,更具体些即关注那些因为某处patch而改变过的代码,反过来去测试未打patch之前的应用。
  • crash reproduction 例如把关注点放到crash info的call stack上: 当一个crash report出现的时候,提供的有用信息可能只有相应的环境上下文,并没有特定的输入,这种情况下就make sense了,可能需要构造输入来触发相应的call stack来辅助探查问题。
  • static analysis report verification 顾名思义用程序真实执行结果来验证静态分析得到的相关结论,其过程也需要构造输入,构造的输入需要尽可能的往静态分析的结果位置走。
  • information flow detection 标注程序中的sinks和sources,作为敏感位置,为dynamic taint analysis提供驱动力。

0x02 现存相关的directed fuzzer存在的局限

  • 大多数based symbolic execution,被称为directed symbolic execution,它将reachability problem的求解过程转换为了一个迭代约束满足性问题(iterative constraint satisfaction problem), ,其中表示某个已经已经reached的点,表示其reach到所需要的条件,接着你如果需要在的基础上探索更深的路径,你就可以考虑接下来需要的condition 。但是这样做就比较依赖source code,并且你需要构造对应某条路径的constraint,这里的constraint要作为可以求解的表达式,这就是说你需要一个constraint slover,太过于抽象不能机器自动求解,也是鸡肋。当然你考虑在binary上来做的话也是可以的,只要你有相应的representation就行。
  • directed symbolic execution代价太昂贵,参考Katch;

0x03 简单介绍一下本文工作

本文在尝试改进directed fuzzer,在前提我们感兴趣的target side给定的情况下,我们如何让fuzzer的行进路线更优于它们?

  • 将reachability problem转换了一个优化问题,将种子和the distance of target side绑定来作为种子选择的依据;
  • 距离的度量分为过程间和过程内两个计算策略,其计算过程依赖call graph和control flow graph;
  • 距离的计算同时发送在静态和动态,静态计算每个基本块与目标地址的距离, 动态计算种子的距离;
  • 种子选择策略是模拟退火来驱动能量调度;

0x04 最值得关注点

  • seed distance的度量方式
  • seed optimization

0x05 seed distance的度量方式

1. function-level

用于度量某个给定函数和目标函数之间的距离,自然地这个距离的计算建立在CG(call graph)上。给定两个CG上的node ,用表示它们之间的最短路径(shortest path),路径的构成即CG上的edges。 最短路径的计算本文采用的是经典的Dijkstra算法。若给定某个CG上某个函数node 和目标函数构成的集合,对不同的目标函数你都要考虑最短路径,所以自然地的你要考虑在它们的基础上取平均,这里采用的策略是取调和平均(harmonic mean)。下面严格定义的距离

其中表示那些对可达(reachable)的目标函数构成的集合。这里的undefined也可以理解为。可以看到的是这个调和平均并不标准,大括号里面少了一个。这里为什么要用调和平均,而不是算术平均或者几何平均呢?实际上调和平均的哲学意义是如果一个过程中有多条平行的路径,经过这些平行路径之后,等效的结果就是调用平均。图中举了一个例子,用来解释算术平均对当前描述更近或者更远的路径这个意义下不是很敏感。

image-20210516122929085

可以看到在算术平均下,三个nodes对目标函数的平均是相等的,这显然不符合预期。作为补充,特别地,文中更关注是找到一条最近的路径,这也可以成为什么选择调和平均的理由,因为调和平均和几何平均都是对小数更“敏感”,这个敏感如何精确的描述呢? 参考其图像,其中小数让其图像更陡(观察下图中变小的过程),也就是说其描述的函数的二阶导是个负数。

2. basic-block-level

用于度量给定某个基本块和另外一个带有函数调用基本块的距离。过程内的计算目的是对前面过程间计算的补充,如果我们把前面提到的函数调用中被调用的函数特指为在调用目标函数过程中产生的调用链上的函数,那这个计算就make sense了。即过程内的计算是为了构造我们想要的对目标函数的某种调用链。给定某个CFG ,其上的某个基本块和带有目标函数调用基本块的集合,下面严格定义的距离 其中表示基本块里面存在可以reach到的被调用函数,即我们有表示上那些的所有基本块;是一个常量系数用于扩大函数间距离;表示一个CFG内两个基本块之间的最短路径,当然这个两个基本块的路径可能是不存在的,这种情况下它们直接的距离可以描述为,这样在结果上也是well-defined。上面整个计算过程度量的基本块距离不仅仅是在过程内,而是涵盖了整个调用链。

通过前面定义的两种度量方式,我们可以在静态阶段就给某个CFG上每个node(基本块)都assign一个值,这个值就表示其距离目标函数的远近程度。这个值你可以类比coverage info,文中就通过它来度量seed distance,严格定义如下 其中表示某个seed,则表示执行所触发的trace,trace具体指在执行过程中触发基本块的个数。注意这里是取了一次算术平均,其合理性值得探讨,我猜可以从基本块之间的order关系展开。

0x06 seed optimization

在具体构建模拟退火调度之前,先理解文中提到的两个概念:

  1. exploration

    探索模式可以理解为在全局上有策略地随机的搜索最好的local解,这个过程aflgo和afl工作方式相同,都是基于覆盖率来调度seed sequence。这个模式要先于下面的exploitation,并不是一上来就基于user

    defined target info来做辅助,而是先拿到更多路径,到了一定limits再使用下面的策略,从直觉上说这是确实是对的,有了路径多样性,我们才能来做更准确的distance的测算。

  2. exploitation

    构造模式在前面探索模式达到一定limits就选择进入,例如设置相关的时间阈值。在拥有了路径的多样性之后,针对性对target location发起进攻,优先选择离target location更近的种子来进行fuzz,并增加其mutation次数。

exploration和exploitation由能量调度策略来进行切换,首先需要理解什么是the energy of seed? 一个种子所带的能量其实就是指其fuzzer对其做mutation的次数,能量越大,fuzzer在其基础上产生的新种子可能就越多。

在“Coverage-based Greybox Fuzzing As MarkovChain”一文中使用了马尔科夫链来model fuzzing,结合power schedule来驱动fuzzing。本文作者正是由此而尝试使用模拟退火方法,因为模拟退火在本质上就是一种马尔科夫蒙特卡洛方法。常用于固定时间内在较大的解空间中搜索近似全局最优解的优化方法。模拟退火的思想借鉴于固体的退火原理,当固体的温度很高的时候,内能比较大,固体的内部粒子处于快速无序运动,当温度慢慢降低的过程中,固体的内能减少,粒子的慢慢趋于有序,最终当固体处于常温时,内能达到最小,此时粒子最为稳定。

模拟退火从描述是从某一较高的稳定出发,这个温度称为初始温度,伴随着温度参数的不断下降,得到近似解也在不断的变换。类比爬山算法,该算法每次都会从当前的临近解空间中选择一个最优的解,直到达到一个局部最优解。而模拟退火,即使某次搜索过程中得到了局部最优解,也有一定概率去搜索其他的解(接受非最优解),避免陷入局部最优解。这个概率是随着温度地降低而变化的,这个过程参照物理系统总是趋向于能量最低,但分子热运动则趋向于破坏这种低能量的状态,所以存在一定几率导致其能量并没有发送变化,温度越低这个概率是越小的。

在了解模拟退火的基本概念之后,首先需要model一个降温过程即cooling schedule,这个降温过程应该是比较缓慢的,文章使用model如下 其中通常定义为为迭代次数,初始温度设置为

前面提到exploration和exploitation切换的limits文章显式的设置为,求出 注意这里用到是自变量迭代次数,换下元用某一时刻来具体表示,让 ,其中作为某个设置好的limit time, 所有的seeds构成的空间就是我们这里的解空间,接下来就是model具体一个seed它的能量,在此之前首先要对做一个归一化(放缩),有点像模糊数学里面的隶属函数,即通过max-min的方法把放缩到,具体操作如下 其中表示所有已知seeds构成的集合。

给定种子 和目标地址 ,在某一时刻,其能量model如下 我们先来简单看一下这个函数的性质:

  1. 且时,最大值为,同理当最小值为. 所以有.

  2. 对任意seed而言在初始状态时都相同的能量

  3. 固定多个时刻,观察种子能量随着的变化

    image-20210517230445130

    相同时刻越小,其能量是越低的。

  4. 固定多个相互均不相同,观察它们随着的变化

    image-20210517230709412

    时,这条曲线有问题,应该是随着时间的增加其能量也是逐渐增加收敛到,这里应该是标注反了。

从图像上分析你会发现最终无论是随着时间或者种子距离都会其随着时间的增加而趋于稳定,这一点是至关重要的。有了R-value function 来model种子对应的能量,那么理想模拟退火的下一步是描述解是如何移动的,即model 如何接受新解? 其过程可能通过来model接受稍微差一点解的概率。但是文中下一步并没有这样做,因为在2.2b afl中已经有一个explore schedule机制了,文中的做法是对其schedule利用上面的进行二次调参,其过程如下 其中表示afl的explore schedule对赋值的能量。观察上述过程有下面的性质

  1. 前面我们分析的时候知道,在时所有seeds的能量都是,所以这里也有 这是符合预期的

  2. 的最大值和最小值,可以得出的最大值为()和最小值为(). 符合越进近的种子,其能量是越大的。

整体上有一些definition我始终觉得缺点什么?

延伸阅读:

  1. Constraint-guided Directed Greybox Fuzzing usenix2021 (为target生成constraint,以slove constraint作为驱动)
  2. Targeted Greybox Fuzzing with Static Lookahead Analysis icse2020 (区块链但是它考虑targets的order关系)

参考资料:

  1. https://zhuanlan.zhihu.com/p/143016455 马尔科夫蒙特卡洛方法
  2. https://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html 大白话解析模拟退火
  3. https://zhuanlan.zhihu.com/p/47628209 比较详细和科学的模拟退火介绍

php optimizer about ssa

0x01 e-SSA Pis

在SSA我们经常能听见Phi,那么什么是Pi呢?,Pi就是一个特殊的Phi,它有range和constraint.,例如:

1
2
3
4
5
if($a>5){
$a = pi($a) > 5
//..
}
$a = phi($a) <= 5 ???

在路径条件的约束下,转头去执行不同路径分支时,某些变量就自动的满足了约束,但是有些情况我们是可以确定的,比如插入的第一个pi,但是第二个的phi的约束不一定完全正确,因为if分支可能影响$a的值。

php里面只考虑条件分支影响下的局部约束,记录一下几种特殊的约束法则的应用。

  • $a > 5 很显然的约束
  • $a + 5 == 0 这里可以做一个变换 $a = 0 - 5 ,分两种情况讨论即
  • $a + 5 == $b +6 同样这里也可以做变换 $a = $b+((-5)-(-6))$a+((-6)-(-5)) = $b. 这里的range除了constant还有其他变量的依赖. 这里为什么要写成上述的形式,我是按照php里面的计算方式来的,他会有一个操作数的adjustment,比如上面equal的RHS操作数的adjustment就是-5. 同理LHS操作数的adjustment是-6. 最后需要把$a$b都单独表示表示出来,就需要adjustment之间做一下运算了.

上述提到的只是php中关于range的特殊约定格式,你也可以写出自己独特的约定。局部约束真的还是挺优雅的。

考虑几种情况不需要插

  1. 变量在target位置并不活跃,只用了一次,后面就不用了,我们在target位置插入一个,没有什么意义.

  2. 依赖于incoming edge,如果有两条相同的incoming edge就不插,这是什么意思呢? 两条相同的incoming edge会无法区分pi是属于哪条edge. 但是我好奇什么时候会导致有两条相同的incoming edge,真奇怪?

  3. 还有一种非常特殊的情况,首先给一个definition: incoming edge定义为从'from'到'to',我们需要在to这里插入pi,我们考虑插入的pi目的是在to这里添加constraint,给我们后面的分析带来一些便利,但是可能你添加constraint是冗余的,举个例子

    1
    2
    3
    4
    5
    6
    7
    8
    9
    $a = $b??$c;

    /*
    *1: T1 = ZEND_COALESCE $b,3

    *2: T1 = QM_ASSIGN $c

    *3: ASSIGN $a,T1
    */

    这里有3行opcode对应了三个blocks,第1行这里是可以尝试给第3行这里添加一个pi的,因为如果从第1行跳到第3行,那么$b肯定不是null. 自然地我们可以在第3行这里添加一个pi断言$b不是null. 但是这没有意义,因为如果执行了第2行,那么第3行这里$b又是一个null,相当于之前添加的那个pi没有任何effort在这里起作用,即. 我们$b是什么还是一无所知.

    所以我们需要识别可能某个opcode造成的两种互斥的约束是否会merge,如果互斥的值同时可能流到to上,那我们去添加pi几乎没有任何意义的,幸运是,当前php的control flow相关的opcode都只有两个successors,所以我们可能不用考虑多个互斥的值同时作用.

    所以我们现在需要考虑from另外的successor(除了from到to的这条edge),我们记为other. 那么具体的问题是other到to是否有一条路径,并且这条路上,里面constraint对应var没有发生变化?.

    其实这个问题回答其实是比较复杂的,因为找路径的同时你还要去关注var没有发生变化. php里面只做了最简单的优化. 记住我们在这里考虑要不要插pi,只是为了避免冗余的constraint,并不是说不能插,也就是说即使插了也是safe的. 所以尽量能减少多少算多少)php在这里会直接考虑to的直接前驱predecessor,如果predecessor里面的var发生变化了,不用想,经过这个predecessor都不会在我们的考虑范围之内了. 如果var没有发生变化,我们就要考虑other到这个predecessor有没有一条路径了,判断有没有路径最简单的方法就是看other是不是这个predecessor的dominator. (笑死!!!!) 再结合我们的问题下一步就显而易见了,有路径不插入pi, 实际上这个是不太准确的,我们在这里只知道有路径,但是路径具体是那条我们并不知道,并且在predecessor前面的路径上的节点var有没有发生变化,我们也是不知道. 所以这里只是作者的小推测. 其他我们没有提到的情况都会插入pi.

    这里考虑如果插入的是prefect pi,那么它是真的有作用的. 如果插入是冗余的pi,这个constraint会造成一些错误吗?因为整个模式都偏向于不要插(留下这个问题,我要去看inference). 但是实际是要插入,而导致没有插入,将会导致后面inference的精度降低.

    exmaple

0x02 SSA Definition

  • 在SSA表示下,任意状态下的某个变量使用,只有一个var definition能够生效。
  • 程序的控制流在SSA下保持不变。
  • 有一个特殊的merge操作,用于处理多个前驱node的变量definition的交汇取值。
  • 并不是所有node交汇处都需要
  • 自然地如果在交汇处所有前驱node对某个变量的definition都相同,则不需要使用
  • use-def analysis is faster on SSA (application)。
  • SSA to machine code???

如何精确的插入phi呢?

single reaching-definition: A definition of variable reaches a point in the CFG if there exists a path from to that does not pass through another definition of . (简而言之就是变量的definition和use之间只有一条确定的路径,且变量的值没有改变).

直觉上如果有两个distinct 基本块,他们都有关于同一个变量的definition,并且存在一个是它们一个join node即存在非空路径.那么我们应该在的开头插入,但是这样做可能会导致一些不必要的插入,所以在插入时候,考虑了minimality的问题,理论上我们需要去掉single reaching-definition的情况,所以这里就引入的join set的,它就表示了对于每个变量的应该至少需要插入的个数.

Join Set Definition 给定图上的节点集合, 表示一些特殊节点的集合(通常表示某个变量的Assignment BBs):

给定 , 至少有两条来自不同起始节点()的路径在点交汇,且这样的路径之间除了点以外不应该有其他相同的节点(也就是说之间只有一个交点),则

的迭代操作表示为,定义如下: 这样迭代的意义是什么呢? 如果给定的是某个变量被赋值的节点,即下面红色节点,得到了蓝色的结点,得到了绿色结点.这样做的目的就可以找到所有的变量的definition交汇的结点,其实也就是需要放置的位置。

it-of-ssa

如何实现?为什么说在所有上插很浪费?举个例子说明中的某个不需要插 我还真找不到!!!!!! retard author(https://iith.ac.in/~ramakrishna/fc5264/ssa-intro-construct.pdf), join set 本身的提出就是为了解决minimality...

那么如何让插函数变得efficient呢?就需要用到dominator tree和dominance frontier的概念,dominator tree就不用介绍了,主要把dominance frontier的概念弄清楚,这个概念是相对于某个结点来说的,即某个dominator tree上结点的dominance frontier:

给定某个结点,表示的dominance frontier,若, 则之间存在一条路径,且是这条路径上第一个不支配的结点,如果换一句话来说就是如果如果在dominator tree上有前驱,且这个前驱不是最后支配这个前驱结点.

dominance frontier

为什么dominance frontier可以帮助我们解决在哪里插入 如果某个变量在结点下定义,理论上变量可能会被传到所有被它严格支配的结点上,当变量抵达dominance frontier时,就要考虑其他来自其他结点的是否也有关于变量的定义,这是最初的直觉。

那么如何计算呢?

how-to-compute-df

这算法很神奇啊,从每个结点的每个前驱开始,让在dominator tree上向上回溯,直到碰到停止,中间所有遇到的结点都把扔到它们的里面去。让我想想这背后的直觉到底是什么?

  1. 首先这个算法并不是一开始就对某个点寻找它的df,而是在确定是谁的df? 所以算法一开始从的前驱开始。
  2. 再看这其中while循环的limit,在从点的某个前驱开始时,如果 dom , 那么我们实际上已经不能接着分析下去了,因为我们考虑所有从开始过点到的路径,且 dom , 那么马上就可以得到 dom . 所以再接着分析所有过的路径已经没有什么意义了.
  3. 回溯dominator tree可以保证到过的路径存在,且路径的开始 dom . 这是很自然的,如果 不是dom 的,那么我们自然要考虑的所有dominators, 所以从idom(p)开始考虑所有合理的dominators.

还有一个小问题,为什么可以保证一定可以碰到,因为的前驱,有几种情况:

  1. 就是. 这是trivial的

  2. 如果不是,我们需要证明也必须是的dominator,假设不是的dominator,则存在一条经过不经过的路径抵达,产生矛盾了不支配.所以的一个dominator,所以往上回溯总可以碰到.

  3. 为什么回溯dominator tree的时候可以把扔到里面去呢?我们知道这条dom-tree回溯路径上的节点都是严格支配前驱结点的,但是并不严格支配,所以.

    这里也需要一个小lemma,dominator tree上的路径并不是CFG中的真实路径:

    dominator tree上任意两点,, 如果他们之间有一条路径, 不失一般性假设的level小于的level,那么也可以在CFG上找到一条的路径,且支配这条路径上的所有结点。

    proof: 假设不存在这样的路径,即所有这样的路径,都不完全支配其上的所有点,那么总可以找到一条从start不经过的路径,这和 dom 是矛盾. 所以原命题得证。

其实还可以证一下这样得到的是不是完全的,也就是说在用上面lemma找的过程是完全的,其实是完全的,因为这东西是依赖于dominator tree的.

0x03 SSA Construction

  1. 变量声明周期的维护,保证runtime阶段所有definition reachable且任一程序点某一时间点只有一个definition起作用.
  2. 每个变量只有一次的赋值机会,即每次assignment的左端的变量名都是独一无二的,保证definition的唯一性.

phi-insertion

这个算法看起来也很简单,先收集所有的变量的defBB, 丢到worklist里面,然后one by one算支配边界,在支配边界上插, 同时这个支配边界也变成了一个变量的defBB,直到worklist空为止.

直觉上是ok的,所有变量的defBB都会被考虑到,所以是不会漏掉,但是可能会造成不是minimal的,因为需要考虑一下是否used情况.

variable-renaming

让我们来推理一下这算法这背后的直觉?

这个过程里面糅杂了reachingDefinition的东西,这玩意儿就是一个definitions cache,也正是我们处理和use-def时候需要的, 大循环遍历所有基本块,内在两个小循环,一个小循环遍历每个instruction,另外一个小循环更新后继的phi的use. 在遍历每一个instruction的时候,我们需要先更新当前instrument的use-var,再考虑是否有def-var的情况. 在更新use-var时候,我们找离这个instrument最近的对应var的definition,注意这是是排除了phi函数的,phi函数的use-var由它的前驱负责更新. 如果有def-var的情况,我们需要考虑给def-var重命名,并且更新原var名的definition, 让后面的instruction在更新use-var的时候,使用这个新命名的变量名. 最后处理完当前的基本块所有instruction之后,更新后继节点的中phi函数可能用到的use-var.

这个reachingDefinition的record到底是如何实现的呢? 注意在上述在处理def-var的时候,会把老的definition和新的definition串起来,实际上这个record结构是一个list,在一个bb内原来相同var definition都是串起来了. 那么在不同的基本块之间definition又是如何传递的呢? 我们来考虑为什么updatedefinition就是找closest definition that dominates i?

传递过程就发生在上图中的更新successor中的phi函数use-var,但是我实在没有看懂在更新之前,为什么要updateReachingDef一下,如果当前bb不是dominate这个successor,那么所有新的var-definition不就清除了吗?图片来自ssabook,如果不出意外的话确实是错了...

use-def-chain
  1. 为什么要深度遍历dominator tree?

    我们目的是给每个assignment的左边重命名,把assignment右边的变量名再修正. 所谓重命名就是给某一变量在重新被赋值的时候,给变量名加了一个下标,这个东西叫version. 为了控制version我们需要有序东西存在,采用dominator tree有几个好处:

    1. tree!!! 它里面肯定没有环,不用考虑什么back-edge...
    2. 还有就是深度遍历,其实你可以理解为先序遍历,只要你是standard dominator tree(children从左到右,从大到小),在处理每一个基本块的时候,都能保证前面的过程执行完整,就是该到你这的definition 都会 reach! 不会存在有一个理论上definition到不了你这里. 画个图就能理解.

RWCTF2021 Mop 0day Writeup

在刚刚结束的RW上,今年又出现了一道2019年类似的master of php,刚开始我还不知道,在看完orange的议题之后,主持人讲解的时候我才知道今年又有一道mop,orange的议题也是带来的关于php的web和binary结合,似乎对web选手们越来越不友好了...

回到正题,2021的mop是一道0day,但是很多人应该拿非预期的spldoublelink秒了,我也不例外,今天不讲它,这里我只想分享一下我是如何利用作者预期的0day.

作者给出的0day还是比较有趣的,绕过了php里面type hint,从而导致的type confusion. 我们具体来看一下作者给的trigger poc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<?php  
//author: https://github.com/wupco/
//realworldctf 2021 MoP https://realworldctf.com/challenge
class A{
function __construct(){
// str_ireplace could be replaced by other functions which have "reference args" such as similar_text etc.
$this->{'str_ireplace'} = "call_user_func_array";
}
}

$type_confusion ="AAAAAAAAA";

//arguments list
$args = array("a","b","a",$type_confusion);
array_walk(new A(), "call_user_func", $args);
print_r($type_confusion);
?>

php里面的type hint是个什么东西呢? php本身是个弱类型的脚本语言,但是它也提供typed机制,例如你在定义函数的时候,你如果在参数前面标识上它的类型,这个类型在这里就是一个type hint,如果你传递参数的时候不满足它的类型定义,会直接抛出异常。

但是有趣的是,如果你调用php函数的时候走的是zend_call_function,它也会检查type hint,但是不会抛异常,只会抛一个warning,并且在args no separation的情况下它不会对你传的参数做任何的其他的事,直接的给你传到目标函数上. 如果你的目标函数没有很好二次check参数类型的时候,就可能会发生一些意想不到的情况. 上面的str_ireplace就是一个很典型的例子,它的第4个参数需要的是一个引用类型,在non-debug模式下,它是不会二次检查这个参数类型的,从而导致了类型混淆.如果利用这个type hint的bypass加到fuzzer上,应该也会有一些不错的发现.

我们来看一下这个类型混淆,到底能给我们提供哪些帮助?

1
2
3
4
5
6
7
8
9
10
11
12
13
#define _ZEND_TRY_ASSIGN_LONG(zv, lval, is_ref) do { \
zval *_zv = zv; \
if (is_ref || UNEXPECTED(Z_ISREF_P(_zv))) { \
zend_reference *ref = Z_REF_P(_zv); \
if (UNEXPECTED(ZEND_REF_HAS_TYPE_SOURCES(ref))) { \
zend_try_assign_typed_ref_long(ref, lval); \
break; \
} \
_zv = &ref->val; \
} \
zval_ptr_dtor(_zv); \
ZVAL_LONG(_zv, lval); \
} while (0)

上面zv变量被误认为reference类型进行assign的过程,我们简单看一下reference类型的结构

1
2
3
4
5
struct _zend_reference {
zend_refcounted_h gc;
zval val;
zend_property_info_source_list sources;
};

assign的过程,分为两步:先把原变量的内容尝试释放掉,再把新的值赋给这个变量,你用这个逻辑去看上面的代码,会很快明白这里在干什么。值得注意的是如果reference里面的sources字段不为空的话,会进入一个漫长的判断过程,我们肯定不希望它进去的,因为我们要为此做很多额外的工作.

到了这一步,我的想法是要用这个assign的过程第一步造一个UAF出来,但是非常无奈的是这里似乎没有任何leak的方式,没有一个有效内存块的地址,我们拿什么释放?这里地方我想了一会儿,我想了一个比较有趣的方式,无法leak,我就给它造一个地址出来!

怎么造呢? php有自己独特的内存管理,但是这个内存管理安全性到不怎么样,是因为经常可以通过它实现任意写的效果. 在申请大内存的时候指超过2M的时候,会直接mmap一块内存,这就非常有用了,如果我能再去读一下/proc/self/maps,这块内存地址我们是可以轻易拿到的,然后我们尝试在上面造一个小内存块出来,把它利用上面的洞,再释放掉,丢到php的main heap bins storage上,这样UAF的效果就实现了。

具体怎么做呢? 首先申请一个比较大的内存块 , 然后从这个 里面再切一块大小为2M的chunk出来,因为heap bins storage操作对象是一个chunk,我们把这个fake chunk修剪修剪让它变成一个看起来不错的chunk,再在其上面划分bins,利用类型混淆释放掉再丢到main heap bins storage上. 常规的UAF就是拿到一个可控的closure,然后把其内部的函数handler修改成zif_system,所以我们释放一个closure大小的bin就是比较好的.

我们可以总结一下这个过程:

  1. 申请一个比较大的内存块 ,用maps拿到其地址.
  2. 上在划一个正常的2M的chunk出来,你需要修剪一下,让它成为一个合法的chunk,这里面包括一些比较重要的字段,比如page maps,main heap.
  3. 还是在 上剩下的内存上构造一个fake reference类型结构出来,让它能释放指定内存.
  4. 我们这里最开始用long类型来制造类型混淆,因为long可以直指我们的fake reference.
  5. 最后trigger UAF, alloc closure, motify closure.... 这都是常规思路.

原题只需要通过ini_alter绕一下open_basedir,是有机会读maps的,所以可以造一个有地址的fake chunk出来,还是比较有趣的. 详细的exploit见.

那么不读maps,应该如何leak呢?想一想这个问题...

旭哥儿,最近在筹备我们论坛新年一个小小的趣味ctf活动,让我出一个题,我也想出一个php上的UAF,它不同于功能性造成的UAF,它是php编译优化里面的一个小小东西,是我曾经写出来一个bug... 我觉得php8的进步在于他的optimizer,往这方面研究研究应该是非常有趣的. 不知道大家有没有兴趣....

从前有一个女孩叫Laura

maple喜欢一个女孩她叫Laura,maple对她模糊的记忆还停留10年前,maple想关于她的记忆已经抹不去了,不如记录下来,因为maple记性不好,怕突然某个时间忘了...

真的有10年吗?大概有了,可能已经10年多了吧,maple多么希望其实做了一个将近10年的梦,突然梦醒了,maple还在初中某堂数学课上,为什么是数学课呢?因为记得那时的maple喜欢和那个数学老师做对,他上课maple就睡觉或者做他自己的东西,数学老师会经常在教室的小黑板上写一道题,说我做出来就可以不用听,我也懒得做,(太丑了!!!!),为什么天底下,竟然有maple这么无耻的人? 赶紧揭过这一章 ...maple现在只想确定她是不是还坐在他的身后,maple赶紧回头,还好她还在那里,乎,原来这是一场异常之长的梦,她疑惑地望着他.他却笑了...

马尾辫,大眼睛,眼镜,呆滞的眼神... 反正她在他眼里挺傻的,他和她刚认识的时候,他和她都是英语课代表,在上初一之前,初一的英语maple已经学了两边了,好吧,那时候英语对他来说确实是挺简单的...

那么什么究竟真正的喜欢呢?maple自己想过很多次这个问题,他觉得这个世界上,除了父母,似乎没有其他人的离去能让他有难以想象的情绪。于她,他想如果有一天他突然听闻她的消息,她有了好的归宿,他内心是开心的,因为她终于成为了别人的那个她,一切尘埃落定,maple再也不用有一份侥幸的心思放在她身上了。但是那时深深的遗憾,可能会永远也散不去,人啊真是一种奇奇怪怪的动物。但是还是没有说清楚喜欢一个人到底怎样的情绪?

maple此刻,静静的回想着,心里其实早有了一个清晰的答案,喜欢就是偶然想起她的时候,会笑出来,觉得这个世界上还有除了父母之外的人值得去喜欢,去爱,但也仅此而已。裴南苇说过:“可能很快,但也可能是很久很久以后,你才会在某一天明白,当你喜欢一个人,只是那个人不喜欢你,虽然不如两个人相互喜欢,但比起你连一个喜欢的人都没有,要幸运很多。”,轩辕青峰也说过:“喜欢你是我的事,与你无关”。

也像洪洗像十四岁时在武当山上遇见的红衣女子,憋红了脸,却一句话也说不来。这些故事用起来竟如此轻巧,我极其理性的专业知识在这里却毫无用武之地,因为它们极其冰冷,我也不喜欢给它们赋予任何情感。

像十四岁的洪洗像那样,十四岁的maple也遇见过叫Laura的女孩,可惜的是,maple和洪洗像一样,什么话都说不出口,眼睁睁的看着女孩离开,但是maple却很羡慕洪洗像,因为他没有洪洗像的“今日解签,宜下江南”,也没有那个一直在等他的凭栏而望的红衣女子。但是十四岁那年的maple却幸运的记录下了这一刻:

weak-maple

可胆小的maple,如今却没有勇气把那句“我喜欢你”说出口,这可不是徐凤年在身危之际才说出口的“姜泥,老子喜欢你!”,而是真真切切的胆小鬼的样子。

可怜的maple除了去喜欢别人这样一件对他极其困难的事情,他也有自己的梦想,而且是他活在这个世界最大的动力,14岁的maple除了遇见Laura之外,还有一件影响了他整个未来的事情,他觉得他找到了自己喜欢的事情,这一喜欢就喜欢了几十年,maple始终觉得他是幸运的,因为有很多人寻寻觅觅了一辈子,却也找不到到底喜欢什么?

大学毕业,整个社会于maple是一片海,他像一条鱼一样游进了这片海。当maple回望前面几十年的学习生活的时候,大学之前很多事情于他,都无法选择,但是大学的他似乎浪费了很多时间,所以他下定决心要把现在的一年当两年过,他给了自己一个期限是三年,这三年他只想给曾经的自己一个交掉,不想自己曾经那般对梦想的热情被轻易地丢弃。

所以maple告诉laura,他需要三年,但是他还有一句话,可是他没敢说...

“你都等了我几十年了,换我等你这三年,不是应该的吗?”maple幻想着这句话如果能从她口中说出来,那他将不顾一切的往前直行... 我想这一刻只能用一句话来形容“江南好,最好是红衣”。

maple在阿里的花名叫枫聆,枫是他自己,聆是laura,枫聆,风铃,玲... maple幻想的也有一个于离阳王朝下爱恨情仇的江湖,有一个游侠儿叫“枫”,这一天游侠儿枫走在边境古道,北风呼啸,两侧的树上挂满了风铃,随着风不停地摇曳着,它们在诉说着风的声音,也是在指引那边境之外的外乡人,家的位置,突然漫天红雨,枫望着风中泛起的枫叶,他想起了那个曾在某地遇见的那个女子,风铃,红雨...

这是之前的故事,但是开头的故事才刚刚开始...

下回有时间在写吧...

我想我这一辈子都不会说出那句话了,她很幸福,这个故事也没有必要在写下去了.

还来不及

仔仔细细

写下你的关于

描述我如何爱你

...

你的美 我不配

终. 2021年01月02日15:21:49

函子等价

定理1.1. 如果一个函子是等价的,当且仅当这个函子是faithful,full,essentially surjective on objects(dense)。

在证明这个定理之前,需要提出一个小lemma

引理1.2. 对于态射 和同构 , 可以唯一确定态射 ,等价地下面四个交换图

img

从这几个交换图上我们已经很容易构造出 了,简单描述一下,定义 ,反之它们的逆用 表示。第一个最为直观

开始证明定理1.1 给定 定义了一个范畴间的等价关系。对于任意的 ,有 ,取 ,显然 是稠密的。再考虑两个并行的态射 ,如果 ,则 同时满足下面交换图

img

根据引理1.2 是唯一确定的,所有 ,因此 是一个局部单.对称地,考虑 和同构 ,可以唯一确定

img

,所以 是局部满的。

这个方向证明,我在怎么用dense这个性质的时候想了很久,最后突然发现一句“由选择公理”就完了,就完了,是的,你没有听错...

任取 ,由dense性质和选择公理,是可以构造一个 ,在dense下选一个 .对象映射处理好了,就可以来构造一个交换图了

img

任取范畴 中一个态射 , 都是同构,所以可以上面的lemma可以唯一确定一个 。因为 是faithful,所以换个角度看 也是唯一的,现在 里面所有的components都是可以确定一个交换图的,且都是同构的,但是这里有一个问题,我们用选择公理弄了上面这样一个 出来,我们并没有证明它确实是一个函子,还少一步验证它对态射作用,首先是单位态射,我们有下面这个交换图

img

还是由前面的lemma和 上对态射的单射性质,这里有 ,相似地,再给一个态射 ,我们有下面的交换图

img

这里有 .

现在已经完成了前一半的证明,接下来想一下如何构造 .并不能直接来构造,尝试构造下面的交换图

img

声明一下其中的几个定义,态射 ,两个component , ,把 定义为 . 这样做的目的是使得 再反过来做一次就得到了同构 .

再看这个大长方形和两个小正方形的交换性,大长方形由上述定义交换,右边这个小正方形因为 是个自然同构,所以也是交换的,言下之意左边这个小正方形也是交换的。这两个小正方形带来的作用是什么?左边这个交换可以得到