Box Theorem

我对国外励志片或者大家一致认为非常经典的电影从来不感冒,也一定是看着看着就会睡着了的人。 但是却熬夜看完了《当幸福来敲门》和《幸福终点站》,看完之后有一些觉得有趣的想法,我觉得写下来是一个不错的选择,写作其实是一种非常好的自我交流的方式。

我并没有对这两个电影表面的励志所感动,因为我从不怀疑一个人要得到某个东西的背后需要付出多大代价。我只是在静静地思考并汲取当一个人面对绝望,困境和无人倾诉的时候应当如何走下去? 有一个画面《当幸福来敲门》中父子二人因无法承担房租而流落街头,坐在地铁站台附近的长条凳子上一左一右,儿子突然看着Chris旁边的Box说道“Daddy Its not time machine...”, 直到看到这里时候我还在为这对父子如何渡过这个夜晚担心,我也以为Chris会尝试安慰儿子,但是Chris却说“Yes, It is...”,然后以此跟儿子做了一个小游戏回到了侏罗纪时代,把站台的厕所当做安全的cave渡过整个夜晚... 对啊Box为什么不能是time machine呢? 在那一刻它不是正好帮助了这对父子穿越了那片刻的苦难? 但是它却还只是一个Box。更让我觉得有趣的是,平时在生活总有许许多多的人,把自己困境当做祈求帮助的途径,而Chris并没有,它没有在找工作的时候告诉别人我是一个孩子的父亲,我们已经走投无路了,也没有在教堂排队等待分配临时住所的时候,因为自己还带着一个孩子希望别人同情一下,但是也看得出来他确实是一个自尊心很强的人。而在《幸福终点站》中整个机场对于Viktor就是一个Box,在这个Box某个角落67号登机口给自己建了一个家,结识了一些朋友,渡过了外人看起来不可思议的9个月。

我在想自己面对这些境遇的时候会如何做? 能不能拥有像Chris和Viktor一样的智慧?如果将Viktor在异乡的语言不通比作无人倾诉,Viktor无疑提供了一种比较好的方法,尝试找到共同语言,在尝试的过程中利用你可以接触的一切资源。这里有一个很自然的问题: 在我们的成长经历和日常生活该从哪里学习这种在困境中生活的方法? 这里我又想到了龙应台在《跌倒-寄K》中的一段话:

“我想说的是,K,在我们整个成长的过程里,谁,教过我们怎么去面对痛苦、挫折、失败?它不在我们的家庭教育里,它不在小学、中学、大学的教科书或课程里,它更不在我们的大众传播里。家庭教育、学校教育、社会教育只教我们如何去追求卓越,从砍樱桃的华盛顿、悬梁刺骨的张秦到平地起楼的比尔盖茨,都是成功的典范。即使是谈到失败,目的只是要你绝地反攻,再度追求出人头地,譬如越王勾践的卧薪尝胆,洗雪耻辱,譬如哪个战败的国王看见蜘蛛如何结网,不屈不挠。我们拼命地学习如何成功冲刺一百米,但是没有人教过我们:你跌倒时,怎么跌得有尊严;你的膝盖破得血肉模糊时,怎么清洗伤口、怎么包扎;你痛得无法忍受时,用什么样的表情去面对别人;你一头栽下时,怎么治疗内心淌血的伤口,怎么获得心灵深层的平静,心像玻璃一样碎了一地时,怎么收拾?”

没人教会我们,或者说别人也无法教会我们,因为有相同的经历才能让人共情。但是正如你所看到的Box is everywhere。 另外一个让我惊叹Box伟大的地方是modal logic里面出现的necessary modality, 第一次遇见它的时候是在natural deduction中作为characterize valid formula方式的出现,同时它又可以出现在lambda calculus中作为characterize closed term的方式。 但是它却只是Box,在见证了它无处不在,它最终以单独subsection named "Box is powerful"在我笔记里面存在。过去我不喜欢赋予冰冰冷冷的抽象事物以任何的感情,因为觉得它们永远只能那样,但是我逐渐发现它或许可以成为生活某个地方的钥匙。 直到我在姚期智大佬文中读到一个关于数学家保罗·埃尔德什(Paul Erdos)的故事:

“我想说的是他是完完全全一个专心做研究的人,而且他有一些特别的地方,他是没有家的人,365天,有360天在路上,在美国欧洲各个地方旅行,基本所需都在一个行李箱里,也不住旅馆,住在朋友家,基本都是数学家,从早到晚都可以交流。他有很多脍炙人口的小故事。比如Epsilon,微积分里用来代表“微小”,小(little)的意思,他喜欢用Epsilon代表小孩子。朋友问他:“吃过午饭了吗?(Have you had lunch?)”他回答:我吃了一点。(Yes,I ate an epsilon)。朋友笑他:你是食人族,吃了个小孩子! 再比如咖啡,他用一个词“定理咖啡(Theorem coffee)”来指咖啡很浓,可以激发数学思维,证明出定理。他在斯坦福访问时,曾在我们家住过两天,称赞储教授做的咖啡堪称“Theorem coffee”。他的整个思维,觉得数学不但是很高深重要的科学,也是社会合作的一个活动,觉得数学应该大家都参与,互相都合作,这是做数学最好的方式。科学界流行一个埃数(Erdos number)的概念,代表和Erdos合作的“最近”距离,可说是最早的一个社交网(social network)。网络之广,甚至许多生物学家、经济家都有一个近距离的埃数(Erdos number)。我本人的埃数(Erdos number)是2,这是因为储枫教授和埃尔德什(Erdos)教授写过一个论文,我又和储教授写过论文,所以她是1,我是2”。

显然Erdos教授将自己天天面对那些冰冷的东西以某种和谐的方式融入了自己的生活,为什么我不能呢? 在这里我也正式提出我的Box Theorem, that is, Box is everywhere! 如果将其称为The existence of Box, 那么我可以继而给出Semantic Box第二个定理Powerful Box Theorem, that is, Box is interpretable everywhere!

其实我想说是学会取悦自己是一个非常重要的能力,Box无疑是一种不错的工具,Box Theorem告诉你Box随处可见,而Powerful Box Theorem告诉你Box等待你探索它的意义。 但是并没有一个Deterministic Box Theorem告诉你某个Box一定有其特别的含义。 如果再将Box放到Kripke frame里面,Box此时会帮你记录下一个时刻会存在什么东西。 BoxBoxBoxBox... 盒中盒的形式也是存在的,至于它的语义不过是只是“人生无常,大肠包小肠”。

希望你也能找到自己的Box.

但行好事,莫问前程

已连续一个星期未碰电脑,感觉甚好。 人在乡下,内心平静。 前有万千思绪,如今也不知从哪里开始。此文为理清思绪,重新上路。即日启程。

0x01 短暂的两天

半年的时光尽皆汇聚于两天的莫名情绪,两天亦半年。

当你试图压制所有负面情绪的时候,你可能就要考虑它们堆积达到极限时,散落一地而难以收拾的场景。

考试那两天,天气莫名地令人有些讨厌,气温骤降,大雪纷至。最初我并不是多么紧张,但考完第一天的那个晚上,突然变得的非常非常紧张,无法言之笔下,我知道那可能是我从出生到如今最紧张的一次,因为我忘记了高考时是哪般心情。在床上躺下又爬起来,如此反复,不时地看一下窗外,窗外雪没停,还是很大。最后也记不得是如何入睡了,大概是让自己变得异常疲倦才入睡了。此时我想竭力写下当时的心情,那种萦绕心头的久久难以散去的焦虑和紧张,我真的写不出来,也有可能是潜意识地规避自己去回忆。 但我心里还是清楚地知道那种焦虑来自于哪里,来自于让人喘不过气的期望。 第二天是考数学和专业课,这两门相比于英语和政治而言,我是更有把握的,但是恰恰是这种更有把握让我窒息,“最有优势的拿不下怎么办?”,“它们都很杂,万一有一个地方我没记住怎么办?”... 种种疑问当你一闭眼就开始在你脑子里面念经了,尽管我觉得毕业两年之后的我,心理承受能力和心境还是相对于说比较成熟了,至少要比那些未涉社会的学生还是要强上一些的。 无论怎样,它们都过去了。

考试的地点是在一座建在山顶的学校,而我和我妈住在山脚的一家酒店,自然地每次考试都需要上下山,幸好有崔锅儿开着电动车的免费接送,非常感谢崔锅儿的无微不至的照顾。第一天早上崔锅儿帮我数着我是排队第8个进考点的,同时我也在8考场的8号座位,有点意思,不管怎样是个好彩头。周围都是和我一样的考生,他们都在争分夺秒地看书复习,不进考场的最后一刻不放手,说实话挺震撼我的,也应了某个家长说的,“他们都是不容易的孩子”。回头看看自己,亦何尝不是如此,往往一边剧烈地咳嗽,一边还在做题,眼睛瞎了(熬夜以至于眼睛发炎,上药之后约等于瞎了),疼痛不止,还在背单词... 我也习以为常了,这些诸多磨难也会给单调的复习时光染上一点生气。当然也有纯纯地摆烂选手,来了直接看小说,一到还剩30分钟就提前交卷; 同样也有拿着红牛进考场的人,我总在想会不会下一个是拿着啤酒进来的选手...

我也常常在想,就这一场两天的考试能否真地可以客观地评价一个人他可以成为一个合格的研究生? 我的观点也一直在重复对立,我也不知道。但我心里对于研究生的定位一直都没有变,你如果想要从事科研,你就绕不开读研究生,因此我心里的研究生是以科研为己任的一群人。当然每个人境遇不同,对此的观点也可能不同,总之如果你觉得研究生生活能让你觉得有意义,那便足够了。

0x02 第二条路

我在2019年末2020初写了一篇文章《猜想与证明》,在文章的末尾我说我在心里埋下了一个猜想,其实我在猜未来我还有没有机会做自己喜欢的事,我不知道,只能靠猜。 在辞职的那一瞬间,我有种错觉仿佛我的人生又充满了无限可能。

在人生平稳地上升阶段,我转头选择了一条完全陌生的路,一条未来不那么清晰的路。 实际上并不是偶然,我内心有很多次关于它的抉择,直到我觉得工作上阶段性的东西我做完了,可以对得起我的同事了,其次对于身边的人来说,我不是一无是处,我还有是有一点能耐的,尽管他们都不知道我在做什么。有那么一句话,“小的事情听从你的大脑,大的事情听从你的内心”,这样能使得人尽可能地避免遗憾,在这一次驻足十字路口上我听从了内心的选择。

选择了第二条路,意味着从今往后我只想做一个纯粹的人,纯粹是一种我所追求的人生态度。无论在工作中和学习中,我都喜欢挑战更难的东西,只觉得有意思,更难的东西意味着需要更长的思考历程,所以对我来讲,每一个工作都会演化成一场漫长的自言自语。 这第二条路,就是我想从事更纯粹的研究,能让我所学所想找到一个施展的地方,尽情地大展身手。 记得醒哥对我说过,“做研究没有什么不好,但是我们都是出来打工的,就算是在科技公司的研究院,也没有纯粹的研究。” 这我都知道,大家出来混的,研究的东西能赚钱才是王道。 我同样知道尽管我去读了研究生,也可能并没有多么纯粹的研究环境,但是相对于工作来说,时间是够的,同时可以学到一些系统地研究手法。 我不奢求研究的过程中有人能同行,因为我深知这几乎是不可能的,每个人都有自己专研的领域,而这些领域都是一些主干上的细枝末节,能碰到同行的人,机会太小。 因此我只希望偶尔能交流谈及一些有趣的问题,就足够了。在老东家做了一些有趣东西,我希望让更多的人看见它的有趣的一面,而后再去重新做一些有趣的东西,这便是第二条路的主线。 我清楚的记得我想要什么,我将要去哪里,这便是第二条路上最大的明灯,不求走一步看十步,看两步就够了。

人生大部分的选择是很偶然的,但任何一种选择之后,都需要绵长的意志力来克服浅滩暗礁的责难。在过去的半年里面,我告诉自己如果能收敛来自各方面的情绪,看淡周围一切,无论身边的人取得了怎样的成绩,选择了怎样的路,我都可以不为所动,那么我就真地选择了当下的路。 我真的做到了,因为我是真的喜欢当下的路,与其说是喜欢,不如说是热爱!我想在这样一条路上做出点成绩,走的更远,不为其他的,只为曾经那个年少的自己,答应过他站在顶峰。我也没有理由不成为自己热爱的领域的专家。

在辞职的时候,有很多朋友也曾和我交流他们也想和我一样,但是或多或少有一些阻力在里面,这样的想法最终也只能停留至想一想。我希望我的经历能带给他们一些启示,当然了并不是怂恿他们去肆无忌惮地追逐一些难以完成的梦。 总之一句话: 要避免遗憾。

其实我非常开心地看见身边的每个人都有自己的方向上前进,耕耘. 这样的感觉真好,我喜欢跟身上有“光”的人相处,他们在人群中是那么的刺眼却又那么的孤单。

我是幸运的,在各种因素使然的情况下,我有机会选择这样第二条路。纵然前方不知何处,踏路前行又何妨?

0x03 关于未来

回想过去这半年,首先我觉得是有趣的,收获很多,其次无论结果如何,我不后悔。

临毕业至现在,每年元旦都会写一遍文章总结过去,但是去年没有写,当时提笔写下几句,只觉无趣,不写也罢。 《平凡亦自然》是去年我提前我想好的文章标题,代表了那一年是在北京最好的奋斗的生活状态,也就有了那句模仿村上春树喊出的“至死18”,我的“至死24”。今年本想延续的这一标题,但是想想过去就过去了,它已然成为过去那一年的符号,今年并不适用,而后我又想了一个标题“人生是否有无限可能?”对自己的质问和感想,但又觉得像一个暮气沉沉的人说的话,亦觉不适。 不如还是用“但行好事,莫问前程”,记得在离职的时候我也是说的这句话,那么同样此刻还是坚守初心。“但行好事,莫问前程”是我当下的心态: 庆幸自己有机会做你当下做的事,因此要加倍珍惜。对于结果,放下迷执。 非常有魔力的一句话,不同人或许对其有不同的引申含义,但是都能带给人心灵上的慰藉。

自从毕业之后,焦虑也随之越来越多,我知道我的一直治不好的咳嗽也与它有关,或许什么时候,我不做计算机了,它也就自然而然的好了,谁知道呢。 此刻对未来的焦虑,也依然还在,试图努力地散去,但也是徒劳。既然不可避免,那就安然接受。

关于未来,我在过去半年有无限的遐想,想象自己顺利进入上科大,开始大展手脚,那些曾经的所学所想尽情的挥洒,也曾想象,选修了所有我想学的课程,学个痛快,还曾想象,和大牛面对面的讨论问题,在台上激情演讲而台下是求知若渴的同学。 这便是我最期望的状态,但是总是不能事事如愿,例如是否能顺利的进入上科大,这是一切上述的前提,能否做自己想做的东西,要是和老师的想法有冲突怎么办? 时间是否满足选择诸多有趣的课程? 是否有大牛愿意和你交流? 是否有对你所做工作感兴趣的同学? 显然这一切不得而知。也是应了前面我说的走一步看两步,我能做的就是让自己回归状态,时刻保持清晰,对即将而来的一切快速地做出决策。

若是我没有顺利进入上科大,我想我不会再去大城市了,因为刚从大城市逃离出来。不太喜欢在偌大的一个毫无生气的城市的狭小的盒子里面生活,太压抑。 人不是52hz的Alice,没人真的愿意孤单地工作和学习,如果有人告诉你他喜欢,那他肯定是骗你的。在北京我喜欢上了数学,因为一个人休息的时候有点无聊,同时浮光掠影般的学习数学往往能给我带来惊喜,在此过程中,时间也奇迹般地过得很快。回想毕业在北京这3年,我好像走了很远的路,学了很多乱七八糟的东西,正如blog上的about里面写的我是一个兴趣一望无际的人,我只要觉得有趣,我就愿意去学一学,总能排遣零碎的时光。

若是能开个小店,自己当收银员,有一台电脑,无人时,偶尔研究一下有趣的东西,似乎也颇为有趣。但是你做的东西真的能上的了台面吗?正如读研究生是我的执念,我希望我的研究能被世界上更多的人看见,若是一个人偷摸干,始终我觉得差了一些东西,但那又怎样呢?

还记得小刀师傅说的,“安全技术领域何其广阔,一己之力亦仅似瀚海拾贝一般,很多时候究其一生终将只得冰山一角,难以窥其全貌。但正因如此,每次进步、每个新的领悟,都让人如获至宝,充满难以言明的喜悦。” 每个人都仅仅在自己那一偶之地默默耕耘,我希望我能坚持自己擅长的领域并走到前列,同时也能用鸟的眼睛俯瞰整个信安领域,这便是我对我从事领域的态度。

那些出现在我脑海里面的,我相信在未来都能一一实现,因为谁都决定不了一条鱼终将奔赴大海。

但行好事,莫问前程。

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;
  • 距离的计算同时发生在静态(被compiler编译之前)和动态(程序运行之后),静态计算每个基本块与目标地址的距离, 动态计算种子的距离;
  • 在种子选择策略上使用模拟退火来驱动能量调度。

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也可以理解为,意味着两者距离无限大。可以看到的是这个调和平均并不标准,大括号里面少了一个。这里为什么要用调和平均,而不是算术平均或者几何平均呢?实际上调和平均的哲学意义是如果一个过程中有多条平行的路径,经过这些平行路径之后,等效的结果就是调和平均。图中举了一个例子,用来解释算术平均对当前描述更近或者更远的路径这个意义下不是很敏感。

arithmetirc mean and harmonic mean

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

2. basic-block-level

用于度量给定某个基本块和目标基本块的距离。注意这个目标基本块它是指包含目标函数调用的基本块,也就是说文章的instrument过程不标记基本块为目标,而是如果某个基本块可能发生问题,我可以在这里插一个目标函数,让它往这里走. 给定某个特定过程内的CFG 上某个基本块和目标基本块的集合,下面严格定义的距离 其中表示基本块里面那些可以reach到的函数调用(间接或者直接),即我们有表示上那些的所有基本块;是一个常量系数用于放缩函数间距离;表示一个CFG内两个基本块之间的最短路径,当然这两个基本块的路径可能是不存在的,这种情况下它们直接的距离可以描述为,这样在结果上也是well-defined。前述定义是足够清晰的,其涵盖的三种情况包括

  • 如果正好落在了上,这种情况下自然的距离为0;
  • 如果,那么取到目标函数最短的距离乘上某个常系数;
  • 在不满足上述两个情况的条件下,考虑上可达的其他基本块,类似地考虑的距离,同时加上的最短路径.

实际上,针对前面计算操作,这里我有一个疑问是如何解决reachability问题? 因为所有的计算都建立在假设已知函数和函数之间的可达性以及基本块之间的可达性的基础之上。关于这一点还需要去看代码才行。

通过前面定义的两种度量方式,我们可以在静态阶段就给某个CFG上每个node(基本块)都assign一个值,这个值就表示其距离目标函数的远近程度。然后利用这个值来计算当前运行过程中seed对应的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. 固定多个时刻,观察种子能量随着的变化,随时间增加越小,曲线越陡。

    energy under different timing

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

  4. 固定多个不同的种子距离,观察它们随着的变化

    energy under different seed

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

从图像上分析你会发现最终无论是随着时间或者种子距离都会其随着时间的增加而趋于稳定,这一点是至关重要的。有了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 i.e code generation

如何精确的插入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的问题,理论上我们需要去掉来自两个不同前驱但是对有相同definition的情况,为了解决这样问题这里就引入的join set的,它就表示了对于每个变量的应该至少需要插入的source个数.

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

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

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

it-of-ssa

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

如何插入phiDefinition 给定某个结点表示的dominance frontier,若, 则之间存在一条路径,且是这条路径上第一个不支配的结点.

dominance frontier如何插入phi

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

那么如何计算呢?

how-to-compute-df

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

  1. 首先这个算法并不是一开始就对某个点寻找它的df,而是在确定是谁的df? 所以算法一开始从的前驱开始。

  2. 因此考虑每个前驱结点,从在dominator tree向上回溯,得到结点序列都是严格支配,所以这个结点序列任意一个结点的所有路径上都有支配的,接下来只要保证不支配,那么,这也是上述while循环中的条件.

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

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

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

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

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

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时候需要的, 大循环按照先序深度遍历dominator tree,内在两个小循环,一个小循环遍历每个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作用是什么呢? 注意在上述在处理def-var的时候,会把一个变量老的definition和新的definition用一张链表串起来. 那么reachingDefinition的作用就是你想在某个instruction处使用某个变量,它会准确地帮你找到这个变量的定义,如何描述“准确”呢? 就是离这个instruction最近的关于对应变量的definition,“最近”表示某个变量definition所在的基本块是dominate当且使用这个变量的基本,且这个definition所在的instruction离当且instruction在线性距离上最近(closest definition that dominates i). 你也理解为先在当且基本块找definition,找不到再去idom,具体操作见下图. reachingDefinition会帮你管理好这样一条def-chain,其中v.reachingDef就是一个链表元素。

use-def-chain

一些细节问题:

  1. 为什么要深度遍历dominator tree?

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

    1. 可以保证在处理每个基本块的Phi的时候,Phi里面的source var已经被重命名了.
    2. 让reachingDef chain works.

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,往这方面研究研究应该是非常有趣的. 不知道大家有没有兴趣....

函子等价

定理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 , ,把 定义为 . 这样做的目的是使得 再反过来做一次就得到了同构 .

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