写这篇文章的起因是看到了 jyy 老师的 信息学竞赛 (OI) 究竟发生了什么？ 视频，其实刚退役的时候就有想着和其他大佬的博客里写的一样，也写一篇自己的 OI 回忆录，但是我的 OI 生涯太短，罗列下来大抵写不出一篇初中作文的长度，加之 OI 的惨烈经历让我好些年来都对算法（竞赛）有一股强烈的抵触心理，因此我的 OI 回忆录一直都没有“新建文件”。 自高一那年的寒假退役以来，一直都没有勇气去面对算法，以为自己再也不会去碰它了，事实上，直到半年后的 CSP2020 我都确实没有写过一道算法题、学过一个新算法，但是，这种我以为我已经可以完全放下 OI 了的自以为是的想法很快便迎来了终结。 高二的某天，覃总问我参不参加今年的 NOIP 。「如果（已经退役了的）大家都去的话，那我也不得不去呢」抱着这样的想法，我问覃总：「你们都去吗？」，依稀记得当时得到的回答是「是」，然后我便稀里糊涂地报了个名。就这样，我又开始做题了，只是只能在晚自习下课后少的可怜的那点时间里来复习。 2020 年的 CSP-S 中有一题对后来的模拟赛产生了不少影响，这道题就是儒略历，被放在了 T1 的位置。正是这道题导致我的心态在开考的半小时到了崩溃的边缘——超级码农大模拟，我居然连 T1 都做不出来。又过了一段时间，我还是没能切掉它，心态爆炸了，放着 T4 很简单的 30 分暴力没调就提前半小时交卷走人了。出来后，我才知道，原来大家也不会 T1.就这样，我以 5 分的差距痛失省一，“光荣”地成为了省二最高分。 很不甘心，感觉心里像是缺失了什么似的，分数线出来那天晚上，拖着疲惫的身躯从结束了晚自习的教室走出来，躺在家里的床上，泪水在眼眶中打转。 我一定不会再去碰算法竞赛了。 是这样吗？好像是的。 高考完的暑假，漫长的假期，高考考砸了的我窝在家中，怅然若失。三个月过去了，这个假期仿佛从未开始。 进入大学校园，看到很多曾经的 OIer 不假思索地投身于 ACM 中了，看到他们的努力与取得的辉煌的成绩，我能做的，只是在冷冰冰的手机屏幕前独自感伤。 也许我从未觉得打算法竞赛快乐过，但是我还是很喜欢计算机的，所以还是毅然决然转去了网安。可能是尝到了机考满分的甜头吧，我没有多加考虑就报了 ACM 算法实践选修课。 大抵是因为这门课，我认识了 cls 和➕🚬，加了学校的 ACM 群和网安的 ACM 群，也和 cls、➕🚬 一起打了湖北省赛，甚至报了天梯赛和 CSP。其实当初的动机只是出于「顺势而为」或者「心血来潮」，比赛时的体验并不好，因为我仍未与曾经 OI 失败的那个我和解，代码写错或者思路卡住了，就会想起曾经的痛苦，于是又会以惨淡的结局收尾。 我果然还是没法打算法竞赛。 尽管说好了下半年要一起打比赛，暑假时我也还是没能拾起这份勇气，浪费了两个月宝贵的训练时间，一直到了要开始比赛了才不得不抱起佛脚。热身赛那天，状态不错，切掉了一道好题，但是很可惜没能保持到正式赛，我应该要前一天晚上保持做题的，这样正式赛的时候也许会好些。可惜了，给队伍拖了后腿，遗憾铜首。 那个学期很累，没有太多时间做兴趣使然的事情，但是比赛前的练习让我察觉到了，我恐怕还是喜欢算法的。 flag 倒塌了，我莫名的热血上头，希望再一次投身于算法的海洋中了，经历将近两年的大学生活，了解到了太多原本不曾注意到的人和事，思想也逐渐发生了一些变化。 是的，没有以前那么敏感脆弱了，是时候与曾经的那个软弱的自己和解了。 「算法还是有意思」。能不能再拥抱你一次？十年也好，一辈子也罢，我想做 TCS，这样就能一直拥抱在一起了，甚至还能继续学数学了。…

从 17 年底到 24 年初，从初二到大二，从懵懂无知的中二少年到现在的成熟稳重（？）、即将迈入大人的世界，六年半载，回想起来，塞尔达竟几乎承载了我几乎整个中学时代。 想当年，全校第二，拿到 5000 元奖学金，终于趁爹妈高兴的时候要到了一台当年新出的 Switch，还记得这台 Switch 是托亲戚从英国带回来的，花了🐭🐭2800+大洋，肉痛的一批。当然了，Switch 到手之后第一款游戏当然要买当时正大火的「塞尔达传说：旷野之息」啦！于是，那名初二少年开启了在海拉鲁大陆上的旅程。 一开始 Switch 没有中文，塞尔达就更不用说了，我试过拍屏翻译，然而体验实在太差于是开始自主探险。好景不长，我怎么也没办法离开那片小小的初始台地，就这样瞎探索了 20h+，我回去监狱上学了。 再之后 Switch 和塞尔达终于支持中文了，我兴高采烈地换了个号重新开始在海拉鲁大陆的生活，但是还是好景不长，因为初三的时候由于很多机缘巧合要去长沙读书了，能当摸鱼勇者的时间就更宝贵了。 时光荏苒，很快便来到了我记忆最深刻的那段时光——高一寒假，也就是著名的新冠爆发的那个时候（谁又能想到 3 年后我居然来了武汉读书呢）。那个时候正是我的低谷时期，期末考的稀烂，竞赛又出了强基计划，像我这种机房打了半年多摆终于觉醒要开始认真刷题的家伙来说这无疑是晴天霹雳，很显然，我退组了，也因为期末考的太烂把当时的 QQ 标签删完了留下一个“我太菜了”。看到这里大概都会觉得我会开始「未来可期，感谢经历，沉淀」罢，不过连我自己都没想到回家之后第一件事是玩「塞尔达传说」。毫无疑问，结局就是被我妈狠狠批斗了一顿然后就滚去自己房间用电脑摸鱼了（感谢在组里练就的摸鱼神功）。 高中三年，很失败，直到最后了都没能成功证明自己，但还是很怀念在学校摸鱼的日子。自那次被批斗之后，我再也没碰过塞尔达传说了，一直到大学了才重新拾起来。 2024.2.11，时隔六年半，我才终于通关了塞尔达传说的第一部。当年讲求探索，迷你任务、呀哈哈、神庙，追求完满，甚至花了不少时间攒钱买房，哪怕直到现在我也只进过那间小木屋里一次，堪称海拉鲁王国的败家骑士，纯纯一个摸鱼勇者，公主无数次提醒血月来临也没能让我从摸鱼中醒过来。但是从去年暑假开始，我林克一改过去“步步为营”的探险风格，目标明确，拯救最后的火蜥蜴神兽，拔出大师之剑，直奔王国城堡，善用 SL 大法，各种投机取巧打摆了灾厄盖侬，借助公主的力量完成了最后一场战役。没错，从一开始只会摸鱼的狗骑士到最后拯救王国的真正的勇士，我花了六年半的时间才完成这样的蜕变，那么，坐在电脑屏幕面前一字一句敲下这段文字的你又会在什么时候拔出属于你的大师之剑呢？

即便说出再多的言语，堆砌的话语，也无法打动你的心。 可即便如此，我也想要传达。 所以，请听我的言语吧，这微不足道的爱恋 纵使心中有千言万语，却不知从何说起…… 既然如此，那只能从 default 选项 —— 时间顺序开始谈起了。 故事的开头是从洸太郎的回忆开始的，孩提时真挚的感情、心急如焚地等待后迟迟没能收到的回复，配合背景里的钢琴曲，给人的感觉就是一股名为感伤的溪流缓缓流过。 直到后来樱花树下的再会，一份不可名状的感情迸发出来，很难不让人感受到洸太郎心中交错重叠的情感，进而也对画面里这个呆呆的女孩产生一种憧憬。 之后则是平淡的校园生活。不得不提到的是在这段故事的叙述，不对，准确来说是整个故事的叙述中，都是交替夹杂着洸太郎甜蜜、苦涩的回忆，她究竟怎么看待的那一封信？到底为什么什么也不说就默默地离开了？音乐的梦想最后又怎么样了？名为姬野星奏的少女身上隐藏着太多的谜团了，其实我只想单推星奏，但是不把其余的线推完没法进入最终章，如果不最后才推星奏的话又怕丢失了最初的感动，因此回学校准备期末考试前我只不甘地推完了彩音线，尽管在紧张旗鼓地复习预习中也仍然会时不时思考着星奏身上的谜团。这就是你大物考的一坨的原因吗 考完试回来之后我快进解决了剩余的 2 条线，进入了星奏线。本以为星奏答应了之后就已经成功传达到了心中的话语，故事的最终会在甜甜的情侣生活之后以 Happy Ending 的方式结束，但是没想到 Glorious Days 的突然出现、星奏莫名的恐惧、少女偶像与星奏之间像是说教一般的对话打破了这一切。这之后，星奏再一次默默地离开了，哪怕是已经成为了情侣之后她所做的也仅仅只是比上次多留了一则内容简单到不能再简单的邮件。 她有可能一直在等我，但也有可能离开了 这一路上，有可能下雨，也有可能天晴 我甚至可能无法到达 但是，即便如此， 我还是想尽一些全力，向你走去 还会再见面吗？我如是想着。故事还远远没有结束，下一次认真的再会是在洸太郎成为了老师之后了。 这一次的再会甚至都到了送戒指的环节，但是第二天星奏还是又一次抛弃了洸太郎奏了。看到这里实在很难继续对这个整整欺骗你三次感情的女人再抱有什么好的看法，哪怕内心中仍然在无力为她辩解着。 不过，这种「坏女人」的看法还是在洸太郎痴情地成为记者开始追寻星奏的背影后被扭转了。与星奏昔日队友之间的对话让我明白了星奏确实是实实在在地爱着洸太郎的，但是大概是觉得伤害了几次洸太郎的自己没有资格继续呆在他身边，再加上队友、大人的 PUA，才会选择再次离开洸太郎的吧，甚至许诺永远不会再出现在洸太郎的面前，永远不会再利用洸太郎了。心痛是我知晓这一切后最大的想法，最后一幕中，在洸太郎的想象里星奏回来了，尽管是半开放式的结局，我仍然相信洸太郎的话语有好好传达到了星奏的心中，那个名为姬野星奏的女人一定还是再次回到了洸太郎的身边。 看到网上大部分人都认为星奏是坏女人（其实我也是因为这个梗才玩的恋彼女），但是我并不认为这是一种背叛。至少星奏在感情上从来没有背叛过洸太郎，只是她无法传达出自己的爱恋，不能将心中的想法和感情传达给洸太郎才会导致这样一而再再而三的默默离开以至于被理解为「背叛」。诚然，大部分二次元作品中，女主在梦想与爱情中一定会毫无悬念的选择与男主在一起，但是星奏却一反常态多次都选择了追逐虚无缥缈的梦想，在队友与事务所的大人的 PUA 选择妥协，我觉得这也是无可厚非的，怀抱幼稚的想法大胆追梦的妄想战士们又有什么错呢？问题的根源还是在于「想要传达给你的爱恋」，推完了整个星奏线，这句话大概更适合用来形容星奏吧，小心翼翼地、笨拙地传达给你的爱恋，最后却仍然没能鼓起勇气以话语的方式传达。 总而言之，从来没想过会为他人的爱情故事感动到落泪，玩的第一部 galgame ATRI 没能给我留下太多的感动，反而让我感到有点无聊，断断续续花了得有 1 年多才终于推完，而《想要传达给你的爱恋》则不同，最终章的故事实在是有点太过好哭，给我带来的后劲居然如此之大，这大概是我的第一部青春伤痛文学了罢。 我们······我和你······ 没准还挺像的 牺牲了一切追寻着你，最后等待我的或许只有寂寞 全力追求着你的我，最后同样变得一无所有 但是回头一想，那个季节是多么耀眼动人 真是无可替代的至宝 你没有给我回信，一言不发地离开我。到了现在，我感觉自己能理解你为什么这么做了 你只是尽了自己的全力 一心为着那些你应当付出全力的事物 正因为这是就是你，所以你最后的最后写在信里的话语，肯定满含着无比的决心吧 你发誓不会再来见我了 如果这是你的决意，那我会郑重接受 但是即便如此，我还是想再尽一些全力说出来 我想见你 我喜欢你 再一次打开最终章，眼中不知何时噙满了泪水······

Info 南京大学「软件分析」课程 Soundness and Soundiness 部分的学习笔记。 Soundness and Soundiness 前面提到 static program analysis 追求的 goal 是 soundness，但是无论是在学术界还是在工业界，由于一些语言的 hard language features 的存在，对现实世界的大型 program 想要实现完全的 soundness 是（目前）做不到的。 Hard-to-analyze features: an aggressively conservative treatment to these features will likely make the analysis too imprecise to scale, rendering the analysis useless. 于是，为了避免 papers 中写 soundness 会误导读者，所以引入了 soundy 的概念：a soundy analysis typically means that the analysis is mostly sound, with well-identified unsound treatments to hard/specific language features.…

Info 南京大学「软件分析」课程 CFL-Reachability and IFDS 部分的学习笔记。 Feasible and Realizable Paths infeasible paths 指的是在 CFG 并不会实际执行到的路径，例如 if 语句中某些不可能到达的分支。由于 infeasible paths 的判定与程序的 semantics 相关，所以总体上是 undecidable 的。 realizable paths 指的是 “returns” 与 “call” 相对应的路径，例子参考 slides。realizable paths 不一定是 executable 的 (feasible paths)，但是 unrealizable paths 一定不是 executable 的 (infeasible paths)。 CFL-Reachability 使用 context sensitive 的技术可以去除 unrealizable paths，但是这里要介绍的技术是 CFL-Reachability。 CFG-reachability: A path is considered to connect two nodes A and B, or B is reachable from A, only if the concatenation of the labels on the edges of the path is a word in a specified context-free language.…

新年第一天，从「恋×シンアイ彼女」开始！ 新年第一天，从 Program Analysis 开始！ Info 南京大学「软件分析」课程 Datalog-Based Program Analysis 部分的学习笔记。 Motivation imperative: how to do (~implementation) E.g. C. 需要告诉机器要如何去实现 declarative: what to do (~specification) E.g. SQL. 仅仅需要指明你想要什么，如何实现则交给程序（DBMS）自行选择 在 program analysis 中，我们指明对于不同的 statement 对应不同的 rule，这就是一种 specification，而在 algorithm 中，我们则指明了每一步具体要怎么做，在实际的代码实现里更是要考虑更多的 implementation details。可以看出，前面所学的 program analysis 即是 declarative 也是 imperative 的。 在 tai-e assignments 中，我们使用 imperative 的方式实现 program analysis，同样的，我们也可以通过 declarative 的方式来实现。(via Datalog) Introduction to Datalog datalog 最早是以 database language 的身份出现的1，现在有了更广泛的应用。 Datalog = Data + Logic (and, or, not) no side-effects no control flows no functions not turing-complete Predicates (Data) 在 datalog 中，一个 predicate (relation) 就是值一系列的 statemetns，本质上其实是 a table of data。而 fact 则是指这个 table 中某个 tuple。…

Info 南京大学「软件分析」课程 Static Analysis for Security 部分的学习笔记。 security 指的是在存在 adversaries 的情况下能够成功达到一些 goals。 computer security 中非常重要的一个 topic 就是 information flow。 Information Flow Security information flow security 的目的就是阻止通过阻止 unwanted information flow 来保护 information security。 保护 sensitive data 的方式主要有 access control 和 information flow security 两种。 access control: a standard way 检查程序是否有权利 access 某些 information how information is accessed 不关心程序是如何使用这些 information 的 information flow security: end-to-end 跟踪 information flow how information is propagated "A practical system needs both access and flow control to satisfy all security requirements"…

Info 南京大学「软件分析」课程 Pointer Analysis 部分的学习笔记。 Introduction Motivation CHA 只关注 class hierarchy 存在很大的局限性，在形如 Number n = new One() 的声明后调用 n 的某个 method 会得到多个 call target，实际其中只有一个 target 是真的，同时运用 constant propagation 会得到 NAC 的结果，是 inefficient 且 imprecise 的。 而 pointer analysis 是基于 point-to relation 的，不会出现上述情况。 Introduction to Pointer Analysis pointer analysis 是一个 fundamental 的 analysis，对于 OOPL，它需要解决的问题是一个指针可能指向哪些 object，同样也是为了 safety，使用的是一种 may-analysis (over-approximation)。 alias analysis 解决的问题是两个指针是否指向的是同一个 object，可以从 pointer analysis 中推导得出。 "Pointer analysis is one of the most fundamental static program analyses, on which virtually all others are built.…

Info 南京大学「软件分析」课程 Interprocedural Analysis 部分的学习笔记。 Motivation 为了处理 method calls，我们可以做最 conservative assumptions 来直接不管这个 method 的具体形态，但是这样会产生很大的 imprecision，于是，针对 method calls 这种特殊形态，我们需要一个 Interprocedural Analysis。 Call Graph Construction (CHA) call graph: a representation of calling relationships in the program. 对于 OOPLs，call graph construction 主要有以下几种方法： Method Call 在 Java 中，有 3 中 method calls，如下图所示 其中 virtual call 是最大的难点也是 call graph construction 的重点。 在 run-time，virtual call 基于以下两点决定调用哪个方法： type of the receiver object $\to c$ method signature(identifier of a method) at the call site: <C: T foo(P, Q, R)> $\to m$ signature = class type(C) + method name(foo) + descriptor(T, P, Q, R) descriptor: return type + parameter types 我们使用 $Dispatch(c, m)$ 函数来描述 run-time 时 virtual call 的 dispatch 过程，实际就是递归向 parent 寻找对应的 method call 的过程。…

Info 南京大学「软件分析」课程作业踩坑记录。 本来想一步步 git commit 传到 github 上的，后来发现不能直接上传解题代码，遂删库跑路（在写完 A1 之前 qwq）。 写到 A2 的时候就已经踩了不少坑，感觉还是有必要记录一下，万一真有幸运读者看到这个辣鸡的博客之后就成功 AC 了呢（ A1: 活跃变量分析和迭代求解器 活跃变量分析 SetFact newBoundaryFact(CFG) 和 SetFact newInitialFact() 返回一个空的 SetFact 即可 boolean transferNode(Stmt,SetFact,SetFact) 注意拷贝要用 out.copy() 方法而不是直接赋值 要将一个 interface 实例当成某个 implementation class 的实例使用需要先用 instanceof 判断然后用 (Var) 强制转换 迭代求解器 Solver.initializeBackward(CFG,DataflowResult) 为了实现 meetInto 方法，需要将 IN 和 OUT 都赋上初值 A2: 常量传播和 Worklist 求解器 常量传播 CPFact newBoundaryFact(CFG) 为了 safety 的考虑，这里要初始化为 NAC 我们要将所有出现在 CFG 中的 variables 全部初始化，所以需要用到 cfg.getIR().getParams() 初始化的时候需要注意，对于 variable $v$，先检查是否属于 Integer 再进行初始化 Value meetValue(Value,Value) 就是课上讲到的 lattice 上的 $\cap$ 操作，分类讨论一下即可 boolean transferNode(Stmt,CPFact,CPFact) 只需要考虑 DefinitionStmt 可以使用 CPFact 的 copyFrom() 方法更新的同时返回是否改变 同样要考虑 variable 是否满足 canHoldInt Value evaluate(Exp,CPFact) 根据这个判断 exp 分类讨论进行处理 对应 Var 类型应该调用 in.…