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

我并没有对这两个电影表面的励志所感动，因为我从不怀疑一个人要得到某个东西的背后需要付出多大代价。我只是在静静地思考并汲取当一个人面对绝望，困境和无人倾诉的时候应当如何走下去？ 有一个画面《当幸福来敲门》中父子二人因无法承担房租而流落街头，坐在地铁站台附近的长条凳子上一左一右，儿子突然看着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

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

可以看到在算术平均下，三个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. 固定多个时刻，观察种子能量随着的变化，随时间增加越小，曲线越陡。

   

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

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

   

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

从图像上分析你会发现最终无论是随着时间或者种子距离都会其随着时间的增加而趋于稳定，这一点是至关重要的。有了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 比较详细和科学的模拟退火介绍

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的精度降低.

   

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交汇的结点，其实也就是需要放置的位置。

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

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

如何插入phi

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

那么如何计算呢？

这算法很神奇啊，从每个结点的每个前驱开始在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的唯一性.

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

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

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

这个过程里面糅杂了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就是一个链表元素。

一些细节问题:

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

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

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

在刚刚结束的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. 对于态射 和同构 , 可以唯一确定态射 ,等价地下面四个交换图

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

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

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

,所以 是局部满的。

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

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

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

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

这里有 .

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

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

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

再由 的faithful性质，即有 ,这个等式就表示下面的图交换

乎将近拖了半个月的证明，终于证完了，选择公理的应用和间接构造自然同构，还是得在细细想想...

php optimizer about identifying loops

这篇文章用于记录php optimizer中关于循环结构识别算法，看了一些php optimizer components，目前最大的感受就是一个component一篇论文，每一个component都有它的出处，你如果单看代码，你很难去读懂它在描述怎样一种算法，所以你必须去看它出处的论文，只有读懂论文以后，你才能抓住最本质是东西去套代码。很幸运我遇见了正在“高速”发展的php，我很珍惜跟随着这些写optimizer的developers去学习的机会，php里面几乎%90的optimizers都是dmitry写的，我真的很佩服他...

我最近的工作中也需要identity loops的协助，有向图中循环识别算法很多，php里面用的算法来自于

Identifying Loops Using DJ Graph

这篇论文构造了一种叫DJ图结构去辅助识别循环，DJ图到底是什么呢？其实用特定的flowgraph生成的dominator tree(支配树)的基础上，把原flowgraph的边(不在dominator tree 中)以join edge的形式又添加到了dominator tree上，就构造了所谓的DJ图，这里J就是指的join edge。

Definition: 是flowgraph上的一条边，如果, 则称边是一条join edge。

这里我们引用论文里面的图，来具体的理解一下：

图a是原flowgraph，图b是生成的DJ graph，其中虚线是原flowgrpah的dominator tree上的边，而黑体实线就是join edges。

介绍完了关于DJ图构造，现在需要稍微了解一下关于循环的定义，循环也是有两种具体分类：

• reducible loop

  从循环最本质的直觉上，循环开始叫loop header(循环头)，在reducible loop里面这个loop header是唯一，且是严格支配其loop body(循环体)里面所有的节点。

  当然还有更一般的定义，reducible loop 也是指单入口强连通分量。reducible loop也关系到flowgraph的可约性，如果一个图是可约的，当且仅当我们可以对它的边划分为两个disjoint groups：

  • forward edges ：所有的forward edges里面的边，可以构造一个无环图，且所有图上的点和root节点都是可达的。
  • back edges：所有的back edges里面的边，目标节点支配源节点，即，

• irreducible loop

  irreducible loop 我们可以使用暴力的手法，不是reducible loop的其他循环都是irreducible loop （很多定义都是这样，但是出奇的好用，哈哈）

有了关于DJ图和循环的基本概念，尝试理解为什么DJ图能辅助识别原flowgraph里面的循环？

我们对dominator tree引入的J边构造了DJ图，可以看到DJ图上也有循环，现在我们还不知道这个循环是不是和原flowgraph是一一对应的，但是我们在尝试关注循环的时候，常常关注一种特殊的edge，称之为back edge，狭义上的理解就是把一条长而直的路径，突然把头和尾连起来变成了一个环。这种定义还是很模糊，我们尝试把这样的边放到DJ图上去，这样边肯定属于J边了，不可能是dominator tree上的边。现在给出严格定义：

Definition:将J边分为两种类型的边: Back J(BJ) 和 Cross J(CJ).

1. 若一个J边是BJ边，则 dom
2. 不是BJ边的其余边都是CJ边

BJ边就是我们环里面很重要的一类边，但是我们需要验证一下DJ图上的环和原flowgraph的环是不是一一对应的？

如何证明呢？其实不用证明只要保证原flowgraph上的边都在DJ图上出现了即可，哈哈 有趣。但是呢DJ图因为dominator tree的原因加入了一些在原flowgraph不存在的边？这些边会有什么副作用吗？实际上并不会，你看见似乎引入了很多新环，但是其实我们关注的只有BJ边，BJ边都是实际flowgraph存在的边。

上面把DJ图和原flowgraph的关系理清楚了，那么我们具体是怎么识别环的呢？

一个自然循环在flowgraph里面有循环头和循环体，例如常规的while，for等等，但是也有那么不太自然的循环，例如用goto来构造一个循环，常规的循环其实就是reducible loop，而用goto你就有可能搞出来irreducible loop，前面已经提到了，在reducible loop里面循环头是严格支配其循环体所有结点的，所以只要把每个reducible loop header弄出来，就可以唯一确定一个reducible loop。但是irreducible loop没有这个唯一的循环头啊，怎么办呢？为了和reducible loop识别方法统一，我也要给irreducible loop加一个header，但是这个header不唯一怎么呢？还有办法，对DJ图做一次深度遍历得到一个生成树，在生成树上那个最前面的那个header，我们作为irreducible loop的header。

值得一提是这里有一个小lemma，即使irreducible loop的header不唯一，但是它们都有一个唯一的idominator，这个lemma证明很简单，只需要用反证法假设有两个idominator即可证明，Sreedhar的论文中有详细的过程。

下面是在php中的具体应用：

前置工作我们需要的是一个dominator tree，还需要一个DFS spanning tree(深度优先生成树)。在这里php并没有生成一个生成一个显式的spanning tree，而是很聪明地使用entry/times的方式记录深度遍历过程中节点与节点的关系,可以理解为一个拓扑路径： A_entry，B_entry，B_exit，A_exit，这样就相当于B是A的子孙节点，不需要生成完整的spanning tree原因是，我只需要在识别irreducible loop的时候，查询loop header之间的祖孙关系，去唯一标识一个header即可。

找loop header是从DJ图的最下面往上找的，这个可以根据dominator tree level进行排序，具体过程我可以用一个简化的算法表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

for (n = 0; n < cfg->blocks_count; n++) {
	n = sorted_blocks[n].id //sorted_blcokeds 里面已经是从dominator level 从高到底排好了基本块
	for (j = 0; j < blocks[i].predecessors_count; j++){ //所有的入度边
		if (blocks[i].idom == pred) { //我们只关注J边
				continue;
        }
        
        if (dominates(blocks, i, pred)) { //当前bb支配前驱节点，也是我们说的BJ边
       		//这里就是标记reducible loop的位置  
        }else{
        	if (entry_times[pred] > entry_times[i] && exit_times[pred] < exit_times[i]) {
        		//不是BJ边，我们只标记在spanning tree里面那个bb为循环头 
        		//这里就是irreducible loop
        	}
        }
	}
	//...
}

有了循环头之后，之后就是把循环体对应到循环头上，这里面需要考虑循环嵌套的过程。所以每个bb只关联离他最近那个循环头。

呼，洋洋洒洒写了一些东西，我记性不好，写下来以后忘了看看，不然觉得挺可惜的。后面有时间我也许可以记录一些php里面其他optimizer的东西。如果有人看的话，看看就行，因为很多也是我胡诌的，哈哈。

paper

0x00 Introduction

Why should fuzzing error handling code?

因为有一些bug存在于错误和异常处理当中，而且想要fuzzing覆盖错误处理，实际上是比较难。

just a challenge,nothing else!

History

static analysis 容易造成很多的false positives(缺少运行时的信息, reachable?)，为了减少false positives,开始尝试用fuzzing来解决问题，简单的input-driven只能在一定程度上解决问题，因为存在一些异常并不依赖输入。基于直觉的software fault injection (SFI)运营而生，尝试人为的注入一些错误和异常，观察程序在运行时是否能正常的捕获这些错误和异常。

现存的一些SFI技术,通常采用是context insensitive fault injection,这种技术单纯地静态在某一些位置注入异常或者错误，可能会导致程序每次执行到该位置时都会触发错误，而导致一些其他行为，例如程序可能就直接exit,这样的情况下可能会错过一些real bugs,引用文中的例子：

采用上下文不敏感的方法在FuncP中的malloc注入错误，将会导致在调用FuncB时就直接退出了，而你就会错过调用FuncB而导致的double-free。试想有选择性地在FuncP的malloc中注入错误，将会有机会捕获到这个异常（第一个疑问when injects? ）。

Bug Examples in Error Handling Code

文中有一个例子举的很好，一下直观的说明了解决这个问题的意义：

在patch之前很明显这是UAF ,但是触发这个UAF必须先进入上这个if，文中提到必须在av_frame_new_side_data在申请内存失败，才会进这个if，这下子文章的整个主题“bugs in error handling code”就变得有意义起来了，有些异常的触发极有可能不依赖于输入，文中将异常分为了两类:1) input-related error 和 2) occasional error,第一类好理解，输入相关，第二类通常为内存或者网络引发的错误。为了触发第二类异常，需要改变改变mutate对象，结合Fuzzing 和fault injection可以擦出怎样的灿烂火花？

0x01 Basic Idea and Approach

Basic idea

为了实现Fuzzing和fault injection结合，文中构造了一个error sequence，其中包含多个error point，一个error point表示异常和错误可达且可被捕获，当使用fault injection可以决定每一个error point是否触发错误和异常，类似一个选择开关,形式化的表示如下： \[ ErrSeq = [ErrPt_1,ErrPt_2,\ldots,ErrPt_x],ErrPt_i=\{0,1\} \] 类似程序输入，同样影响着程序执行，其中核心问题变成了“哪些error point应该被触发？使其能覆盖尽可能多的异常处理代码“，在这里插入Fuzzing的思想，把mutation作用到error sequence，来解决这个核心核心。

Error Sequence Model

基础定义：

context insensitive error point： \(ErrPt = <ErrLoc>\) (单纯用error site来描述)

context sensitive error point: \(ErrPt = <ErrLoc, CallCtx>\) (在error site的基础上，添加了运行时的调用栈来表示上下文)

其中 \(CallCtx = [CallInfo_1,CallInfo_2,\ldots,CallInfo_x]\)

每一次函数调用包括caller和calle， \(CallInfo_i=<CallLoc,FuncLoc>\)

FIFUZZ

FIFUZZ就是原文提出的一种针对上面问题的context sensitive fault injection解决方法。它由6个步骤组成：

1. statically identifying the error sites in the source code of the tested program （静态地识别被测程序源码中的error sites）
2. running the tested program and collecting runtime information about calling contexts of each executed error site and code coverage （在运行时收集error site执行时的上下文和覆盖率）
3. creating error sequences about executed error sites according to runtime information, and each element of such a sequence is differentiated by the location of the executed error site and the information about its calling context （利用收集到的运行时的error point信息，构造用于执行mutation和fault inject的错误序列，）
4. after running the program, mutating each created error sequence to generate new sequences （迭代生成新的错误序列）
5. running the tested program and injecting faults according to the mutated error sequences （继续跑输入，并且在运行时执行fault injection）
6. collecting runtime information, creating new error sequences and performing mutation of these error sequences again, which constructs a fuzzing loop （循环往复）

error side定义是指注入的fault可以被正常触发和捕获的位置（code location）

我从直觉上猜测的是，通过instrument标记error side，一次运行程序，得到可以被覆盖的error side，并不是简单的count，应该是有上下文敏感的count,通过得到这个信息，构造一个error sequence序列，表示应该去触发哪些error side。

文中整个Fuzzing Loop的不同于一般情况下,mutation的对象重点关注错误序列，还有一个问题哪些因素会去影响mutation？其实还是覆盖率，只是变成了error sequence带来的覆盖率，如果一次error sequence可以带来新覆盖率，就把它加到mutation过程的pool里面（还有一个优先级的东西，但是太模糊，“贡献的覆盖率”是指这个error sequence完整的覆盖率，还是在prev error sequence上增长的覆盖率，显然后一种似乎并没有什么道理）。

Fuzzing Loop有一个初始化的过程，因为第一次跑程序的时候，其实是没有反馈的信息的，构造了下面一个初始化的mutation过程，initial error sequence每个error point都是0，然后把它拆开成多个error sequence，其中每个error sequence都只有一个error point是1，且每个error sequence是唯一的。

后面的迭代过程基于覆盖率，mutation尝试将mutate每一个error point(\(1 \rightarrow 0 \ or\ 0 \rightarrow 1\)) ,整个过程并无亮点，我觉得难点在于怎么在动态根据上下文做到的fault injection？ 和 如何做到的同时mutate程序输入和错误序列？

How to identity error side？

这一章节是第一次接触fault injection的人应该最想要知道的，用它的时候，你必须保证你触发的错误是实际中存在的，不然造成的false positive是没有任何意义的。文中尝试通过静态分析的方法去识别error side,更具体一点，一个特殊的函数调用可能变成一个error side，其unexpect的返回值可能触发异常和错误处理，所以识别error side的粒度其实以函数为标准，具体分析过程如下：

1. Identifying candidate error sites ：在大多数情况下，函数返回值为空指针或者负值时，表示一个failure，如果一个函数调用可能是一个error side,从两个方面来看：1）如果它的返回值类型为指针或者整型；2）它的返回值流到if上，并且检查其值是否为NULL或者zero。

2. Selecting library functions： 在大多数情况下，异常和错误产生于外部的库函数，从这个角度出发，如果定义在当前程序中的函数可能触发异常和错误，代表着它作用域下库函数可能会触发异常和错误。这个描述太过于模糊，应该建立函数的返回值和库函数（可能触发异常和错误）的联系。

3. 这一步不太容易理解，我尝试用我的理解来讲一下(可能并不是原文的意思，读者需斟酌)，第一步确定了候选的函数调用，需要进一步确定这些函数调用的目标函数返回值是否受错误和异常的影响？第二步给了一个最基础的标准，我们可以已知的库函数会引发错误和异常，通过这些库函数再去迭代标识，程序中定义的函数是否可能引发错误和异常？这两个步骤已经可以基本确定一些error side了，然后再这些error side处做一些特殊的instrument，如下：

   注意红色的部分，当指定的error point被触发时（需要检查上下文），将被标记为error side的函数调用替换成NULL或者zero，让其触发异常处理。但是第二步描述的非常模糊（个人觉得），只能识别一部分函数可能导致错误和异常，为了尽可能多的识别error function，在第三步这里用了一个统计方法，如果某个函数调用在候选的error side，在程序中全局搜索所有该函数调用的数量 \(S\) ，其中该函数调用的返回值进入if数量为 \(s_j\) ,且 \(s_j/S > R\) ,则认为该函数调用的目标函数是一个error function， \(R\) 代表一个阀值，如果 \(R\) 越大，导致error function越少，随之error side越少， \(R\) 的适配需要根据被测程序的实际情况来决定。

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   int Func_a(){ p = maybeTriggerError(...); if(!p){ //error handling } .... } int Func_b(){ maybeTriggerError(...); ... //maybe error handling }

0x02 Self Conclusion

有意思的一篇文章，改变了mutation的对象，在这里我总结了几个我想要知道的问题：

1. fault injection是个什么东西？如何确定error side？
2. 文中新的mutation对象error sequence是如何构造的？
3. 如何在动态运行时根据上下文做到的fault injection？
4. 如何做到的同时mutate程序输入和错误序列？（相互协调）

这几个问题都在前面有描述了，但是4文中没有提到，Fuzzing Loop反馈驱动比较常规，重点在于如何连续的Perform Software fault injection?

Angora: Efficient Fuzzing by Principled Search

0x00 解决路径问题的五种技术

1. 上下文敏感路径覆盖 （像AFL这种都是基于bitmap的edge计数，并不细分edge的上下文）

2. 关于taint analysis 确定 input 和 path constraints之间的映射。

3. 梯度下降算法 作用在 input mutate(ion)

4. input的结构推导 （shape => 结构， type => 结构里面字段）

5. input长度的探索方法

0x01 Something interesting

上下文分支敏感的分支统计

通常情况下我们的分支记录在有向图CFG上来完成，通过执行过程中对经过有向边edge进行计数，这里会丢失一些东西，理想情况下，在CFG上记录一条完整的分支，应该是edges的一个拓扑排序 ,这里变成了单纯的edge计数。作者并没有对这里进行改进，同样还是edge计数，但是他们把相同的edge，置于不同的上下文当作两个不同的edge，这里的上下文特指执行当前edge的函数调用栈。这样在原来计数的基础上提出了更细的计数对象，在一定程度能更细致的区别执行过程中edge的变化。（这些理解只看原文，其实有一点难理解，需要具体的看一下Angora中LLVM Pass过程）

文章在这里用一个例子说明问题，但是这个例子我觉得并不好，作者认为原有的edge计数并不能区别输入为10和01的区别，实际上是可以区别的：

10: L3:true;L4:false;L3:false;L10:true; 01: L3:false:L10:true;L3:true:L4:true;L5:(true|false);

两次执行走的分支情况，在01下是其实触发了新的路径，会多出一个L5分支记录，原文说两次都触发执行了L4，L10会被认为没有触发新路径。但是01的时候是触发了L5。

注意label %5这个基本块，01是会触发label %5到label %8这条边的。所以这个例子实际上在这里不合适。那在这里什么样的例子应该合适呢？应该是确保走过相同的edge的，不同上下文带来的影响。我能想到的唯一改变是下列这种情况:

1
2
3
4
5
6
7
8
9
10

void f(int x){
  ...
}

void main(){
  if(input()=='111'){
    f(input());
    f(input());
  }
}

加入context以后，因为L7和L8,处于不同callside,但是两者调用f,假设经过的edge一样，会导致在f,会多出一倍的edge元素，就像我前面说的，可能以前某个edge计数为2，可能现在被拆分成了两个不同的edge。在某种程度上改变了AFL中的edge计数的feature，可能变得更“敏感”一些了。但是我很难去推演它的这种”敏感“，到底能带来什么？我想要知道这种形式的”敏感“，是否可以孤身存在，而不对其他东西产生影响？这些东西于我而言，现在还是难以解释。

字节粒度的污点分析 （没有涉及taint rules）

文中没有细讲taint的过程，而是主要讲了一下taint过程中的污点表示，taint存在的意义是为了将输入和路径条件建立映射关系，在mutating阶段能更好的去解决路径条件。

定义：标签 表示输入input中的哪些字节会流入变量 。通常 用位向量来表示， 会随着输入的大小线性增长。为了应对large input，文中构造了一个数据结构，来存储和查询 ：

1. Binary tree：（ 代表一个位向量， 代表位向量的长度，长度概念应用树里面，就是指结点的高度）每一个位向量 ,都可以用这个树上的高度为 的节点 唯一表示，从根节点root到 路径上的节点依次展开为 。其中的每个结点都一个指向它父结点的指针，这样可以从 开始顺着树回溯遍历得到完整 。

2. Look-up table: 表里存储着 , 即保存着指向 Binary tree里面结点的指针。

   画了一个图，方便理解和记忆：

   

插入操作： 1. 去掉 结尾所有的0。 2. 遵循Binary tree策略，用 去遍历Binary tree，如果 ,则follow左子结点，反之亦然，如果子结点不存在则创建结点。 3. 把 存储到树上最后一个visited的结点。

注意到这个算法只在生产新结点的时候，插入 ，所以某个结点如果存在 则后面都是不会发生改变的。我计算得到的空间复杂度跟原文有一定区别,原文是 ,我在计算最坏复杂度时得到的是 . Maybe i am wrong,who know!

基于梯度下降的搜索算法

目标是解决路径，让路径条件满足某种要求，我们从最简单的条件出发，某个二元运算，和两个基本变量：我用 泛指所有可能出现的二元运算，基本变量用 , 表示： 文中尝试将求解约束转化成最优化问题，所以需要让上面的问号变成一个具体的值，而不是通常情况下的 ，文中做一个漂亮的转换。

将二元运算转化成了具体函数，函数值间接表示约束的成立。通过合适的函数表示，将所有的约束成立都变成了 ，复杂的组合条件可以经过转换变成简单的二元运算：

1
2
3
4
5
6
7
8

if(a&b){}

//transform
if(a){	
	if(b){
		
	}
}

这样，向最优化问题的转换变成了可能。注意 实际上还是一个黑盒函数，你是并不知道它完整构造的，只能通过输入，得到输出，也是一个无约束最优化的标准问题，为了解决这个问题，文中使用梯度下降的方法。

使用梯度下降过程中需要计算梯度，但是前面说了这里的 是一个完全黑盒的函数，甚至可能都不是一个连续的函数。在没有其他方法的情况，只能通过近似计算梯度，来保证后面的运算。

现给出 的定义： ,其中 ,即输入input中与f对应二元运算相关联的值。注意这里的 并不完全是像 中的 一样是单个字节，后面还有一个结构感知的过程，这里 可能是一个完整类型的变量。对于多元函数 而言，它的梯度定义为：

其中 $$ 是一个极小的正数（e.g. ,1）， 表示 方向上的单位向量。为了计算每个方向上的偏导数，需要跑两次input,第一次使用original input ，第二次使用经过变换preturbed input ，这里有一个非常重要的问题，有可能第二次使用preturbed input的时候，导致 所指的二元运算所在程序位置变成了unreachable，这个时候会导致无法计算或者计算出来的结果是毫无意义的。原文在这里没有细谈，而是一笔带过，但是在Matryoshka中在这里提到一种解决方法，有兴趣的同学可以去看看。

最后是否能收敛到理想状态的下(小于0或者小于等于0) ，文中提到了三个点：

• 是一个单调函数或者凸函数。
• 局部最小值满足约束。
• 如果局部最小值不满足于约束，Angora将会随机的使用其他的 ，直到局部最小值满足约束。

结构和类型推断

前面提到过 中的 并不是完全字节粒度的位向量，Angora会尝试把一起使用的字节归纳为一个type。文中这里也提到了一个问题，关于为什么要引入这个机制？假设某个程序把4个连续的字节 当作一个int类型，用 代表这个整型，那么在计算 的时候，只需要在 加上 ,但是把其分开成4个方向偏导数分别计算，可能会影响其收敛速度。

结构推断：哪些bytes总是一起被使用？

类型推断：一起被使用bytes是什么类型？

Angora里面的primitive type分为1，2，4，8bytes。它们之前可能会出现矛盾情况（e.g. 相同连续位置，被fetch一次8bytes，同时也被fetch一次4bytes），这种情况下，取最短的type。类型推断的依据使用其上下文的语义所决定的，比如某个指令操作对象是signed int,那么对应的type也是signed int。注意其整个过程都是在动态的污点分析中完成的。

输入长度探索

Angora这里特别地采取了关于输入长度的判断策略，通过关联read-like函数和read 系统调用，对read-like函数传参判定对应的输入offset(taint相关), 还会特殊标记它们的返回值，如果它们的返回值流到了路径条件上，且没有满足路径条件，Angora会尝试增加输入长度。这里我觉得这个策略并不会普遍适用于一般的程序输入，只能说一种有趣的尝试。

0x02 Self Conclusion

很有趣且朴素的一篇文章，使用的5种解决路径方法很实用，且开源（能看代码的感觉真好），但是仔细研究细节可能还是与自己想的不太一样。其中很多东西，可以尝试应用到实际情况下，我觉得就值得。“纸上得来终觉浅，绝知此事要躬行”。

0x00 Questions

这篇文章意在解决“嵌套”的条件结构（注意这里的嵌套并不是狭义上控制结构嵌套），这是一个比较难处理的问题，在找到一个能触发新分支 的输入 ，接下来的策略肯定就是在这个输入 上，去构造新的输入 来触发更多的新的分支，但是这里面有一 个问题，假设新分支 内有一个子分支条件是 ,这个分支条件位置为 (reachable by ),那么分支 的子分支就可以抽象为 ,构造出来的输入 ,极有可能 点并不是reachable，因为可能 点之前的某个分支条件满足性，在输入 和 上并不相同:

这里通过一个代码片段，来特别地说明几种特殊的情况：

控制流依赖，L6依赖于L2，L3，L4。（这里的依赖对象是分支条件，下同） 数据流依赖，L6依赖于L2，L3。

如果我们想要进入L6的true分支，首先(1 L6 is reachable，（2 satisfies L6’s condition。

0x01 The ways

1.1 分支条件的控制流依赖

这个依赖可以看作是从CFG上剥离出来的东西，图上的点从基本块变成了分支条件，什么是分支条件？可以更具体一点，cmp/jmpz(nz) 等等的组合，为了把分支条件之间的关系，描述更加紧密，文中抽象了一个叫prior conditional statements 的概念，对一个指定的路径条件 ,它的prior conditional statements是可能导致 变成unreachable的一组路径条件。

这个定义在实现过程中还是比较抽象，需要具体的研究一下它的性质，首先考虑它并不是一个等价关系（不满足对称性），那么它是一个偏序吗？自反性很显然，传递性也很显然，反对称性呢？考虑两个不相同的路径条件是否相互为prior conditional statement ,这个不要去想的太复杂，在这篇文章描述的依赖关系下，是不可能做到，因为执行流，两个statements，肯定有一个是先执行的。

抛开反对称性不说，重点关注它的传递性，这里prior conditional statement 关系我用 表示。传递性可以描述为 为了找到指定路径条件 所有的prior conditional statements，可以使用这个性质，但是还需要定义一个immediate prior conditional statement,如果 是 的一个immediate prior conditional statement,则在 和 之前找不到第二个prior conditional statement,这个“之前”是指所有执行到 到路径，往后看 都是最后一个路径条件。可以简单的理解为 离 最近。这个定义对研究路径的同学来说，是非常熟悉的，就是dominator tree的定义，仿照它的定义，是可以给出计算prior conditional statements的算法的。 其中IPrior表示immediate prior conditional statement

通常来说dominator tree只定义在过程内，文中又进一步改进，引入了过程间的prior conditional statement 关系，这个也很好理解，如果一个路径条件 在过程内没有prior conditional statement,那就去找调用个过程的call的prior conditional statement，这里会产生一个疑惑不是描述路径条件之前的关系吗？怎么又突然来了一个call，按照定义描述的是“可能导致这个call 变成unreachable的路径条件”，其实是合理的。

我以为文中技术实现是完全建立在静态分析上，但是直到读到这里，trace和stack的出现，告诉我极有可能是在动态过程中做的，而且文中给的找immediate prior conditional statement的算法是可以在动态做的。

Intraprocedural immediate prior conditional statement：（ of ）