洛谷第四代评测系统技术分析

## 0. 前言 - 洛谷评测机的前世今生 自2013年洛谷创立以来，已经陆续更新了4代评测技术。 在2013-2015年的洛谷1、洛谷2时代，使用的是基于 Windows 系统的评测机。 当时的评测机技术架构十分简单，原理大概是每秒钟自动从数据库获取未评测的程序，在 Windows 系统上进行评测，甚至直接在 Windows 的最高管理员 Administrator 账户下运行，程序运行环境上没有任何的安全限制，也不支持多线程评测等减少用户等待时间的重要功能，不过对于当时还只是小作坊 OJ 的洛谷来说，也算是比较够用了。 当时，lzn 站长想了一个比较聪明的办法来保证评测安全： 我们知道 `gcc -E` 指令可以调用 `gcc` 编译器的预处理器，即输出处理了 `#include` `#define` 等定义之后的代码。通过检查预处理之后的代码，隐藏在宏定义中的危险函数调用将无所遁形。洛谷第一代评测系统采用的便是对预处理后的代码进行关键字检查的安全措施，虽然不是万无一失，但至少可以防住大部分小学生————直到当时本文作者 lin_toto 和 kkksc03 打了一个赌，说可以用5种不同的办法在评测机上弹计算器。（结果最后只找到4种） （科普：弹出计算器是安全界比较流行的，证明对Windows系统已经取得控制的方式。） 而洛谷第二代评测系统，也就是老一辈用户所熟知的“港记号”，是随着洛谷3一起推出的，基于 Linux 的评测系统。随着当时用户体量和评测量的增大，洛谷也迫切地需要改进的评测技术。洛谷第二代评测系统由洛谷开发组最神秘的 w 主导开发，带来了多线程并行评测等高级特性（因此也常常被称为“跑得快”）。同时，基于 seccomp 系统调用过滤机制的沙箱，也第一次为洛谷的评测系统带来了真正意义上的安全性。 随着评测量的不断增长，洛谷研发了试验性的“云端评测”系统，将一些对常数、时限要求不敏感的题目提交到云端评测系统。云端评测系统是真正“无队列”的：当你在洛谷上提交一道云端评测的题目时，不需要进行排队等待，而是系统立刻为你开设新的评测机并立刻开始评测。在云端评测技术逐渐成熟后，洛谷也停止了第二代评测系统的使用，将所有题目均迁移至云端评测。你一定想问，这套系统是如何实现的呢？ 云端评测技术必须配合公有云服务实现。有些云服务厂商提供一种特殊的服务器：只在运行任务的时候被启用，任务结束立刻停止，洛谷也只需在有运行任务的时候对服务器付费。利用这种服务，我们便可以无限制地运行几乎任意多的评测系统，也无需担心购买太多评测机造成的资源浪费。 然而云端评测也有着各种各样的限制。洛谷云端评测在最初期，使用与“港记号”同样的沙箱技术保证评测安全。但在云端评测运行一段时间后，洛谷使用的云服务商毫无征兆地封禁了所有 seccomp 的使用。不过由于每次评测，服务商为洛谷开设的容器是相互独立的，因此即使容器被恶意毁坏，也不会影响到其他的评测。 直到近期，十分毒瘤的云服务商开始了“容器重用”的机制，也就是说，洛谷在短时间内向云服务商提交的评测任务，均会共享同一个评测容器。只要其中有一份恶意代码运行，这个容器中所有的评测任务均会全废。云服务商逐渐加入的各种限制使得洛谷越来越难以维护评测系统的安全性，同时也使开发组意识到了一个问题：云端评测系统过于依赖公有云。 评测安全问题最后的爆发则在上上周，一位名为@Fedoraer 的用户突然在 GitHub 上公开了恶意破坏评测容器、以及通过越权读取容器数据达到“自动AC”的代码（详见主站右下角小黑屋）。开发组也因此认为，评测机技术的更新迫在眉睫。 因此，洛谷第四代评测机于2018年8月18日晚间正式上线，现正服务除提交答案和在线IDE外的所有评测。题外话，洛谷同时对非法滥用并传播云端评测漏洞的多名主要嫌疑人进行了严打，给予了棕名至永久封禁不等的处罚。 ## 1. 第四代评测机设计目标 第四代评测机在设计上必须考虑的难点，是如何使用较低的成本，服务洛谷今日巨大的评测规模，同时每个用户也能获得较好的评测体验。 洛谷今年的用户体量增长有时候会让人感觉巨大得难以置信。根据后台统计，进入今年暑假后，评测量最低的一天，系统都处理了32000条以上的评测。而目前统计的日均值则在42000-43000条评测的范围，最高纪录则在8月17日的某节48118条评测。要知道，去年NOIP前日的洛谷单日评测量也才5万3千条。 洛谷每日晚高峰的评测量则基本在五分钟300条以上，也就是说基本每天到了晚间时分，不到1秒钟洛谷评测机就要处理一条新的评测。而我们历史上统计过的最高值则在4月1日的愚人节月赛，当时达到了5分钟1103条评测的最高记录，相当于1秒钟接近4个。可能老辈的洛谷用户知道早期洛谷点击评测列表，默认和其他OJ相同，是显示完整的评测队列；而某一天突然切换成了默认只显示自己提交的评测。这是因为洛谷高峰的时候评测记录实在更新得太快了；基本上你刚刚提交完还在队列顶部，一刷新网页就到了底下，再一刷新就根本找不到了。 总结，洛谷评测机所面临的评测压力，基本和国际大OJ Codeforces 相匹敌，甚至可能超过。使用过 Codeforces 的同学可能都知道，CF 在评测压力大的时候，立刻会陷入排长队的等待局面。而洛谷评测机的设计目标，则是在如此大的压力下，也尽量不让用户“排长队”，甚至在高峰期都能以不输平峰太多的速度获得评测结果。同时，也不能无脑买一堆服务器，然后在平峰时放着闲置，而应该通过技术，智能化评测系统的调度，实现类似云端评测的机队自动扩容。 ## 2. 调度和基本架构 第四代评测机再次回到了与第二代类似的队列调度，但这不代表技术上的倒退。相反，开发组引进了云端评测时代的先进经验，创造了一套先进的调度系统。 当用户提交评测任务时，任务首先由网页端通过内部通信，发送到评测后端的处理程序上。在简单检查评测任务的合法性后，便被放入评测队列等待程序编译。 完成编译后，程序的二进制文件被读取放入一个在所有评测机间共享的存储中。同时，评测任务被按照该题的所有测试点打散，安排进入队列，有空余线程的评测机便读取任务，并行进行评测。在评测结束后，负责结果收集的组件将结果发送回网页端，由网页端进行下一步处理。 而四代评测系统的队列机制，相比第二代，主要做出了以下改进： - 智能优先级。并不是所有的评测任务都会被评测机一视同仁，公平地按照先来后到受到安排。例如，对于本身时限就较长的题目，可以适当降低其评测优先级，因为本身评测就需要花费较久时间，此时多等一些也无妨。又例如被系统认为正在对评测机进行恶意攻击的用户，则会被分配很低的评测优先级，甚至直接拒绝评测。 - 智能扩容。因为洛谷不像 Codeforces 服务来自世界五湖四海的用户，用户群主要来自中国，因此评测量有明显的波动。如果购买大量评测机并在平峰的时候闲置则非常的浪费。因此，第四代评测系统具有自行监测评测拥挤度的功能。当发现评测机的负载过大，或用户出现较长时间等待的情况下，便会自动向云服务器厂商提交订单，在1-2分钟内，新的评测机即可上线服务。在高峰结束之后，多余的评测机则会被自动关闭，以节省不必要的资金花费。 同时同以往一样，四代评测系统的所有输入、输出文件，均放置在虚拟内存盘中，因此不存在磁盘速度带来的输入输出速度瓶颈。 ## 3. 沙箱 洛谷第四代评测机采用了基于 [lrun](https://github.com/quark-zju/lrun) 且自行研发改进的评测沙箱技术。该沙箱技术不再限制系统调用，其原理与近年大火的容器技术 docker 类似，利用 Linux 内核的 cgroup、rlimit 等功能，对用户程序进行全方位的限制。 因此直接可见的效果便是你现在可以随意在洛谷上提交所有你在网上找到的所谓“卡评测机程序”而不会影响洛谷评测机的正常运行。你的程序看到的是一个完整的 Linux 操作系统，然而你所看到的文件系统只是一个经过我们筛选的只读镜像，只包含对于评测必要的文件，而包括评测数据、其他人的程序等敏感数据，都在用户程序无权也无法读取的镜像外的文件系统，因此类似于“AC自动机”的事件的发生可能性被彻底斩断。程序运行时可申请的内存、磁盘空间等资源受到严格的限制，如有超出则会自动被系统停止运行。你无法看到运行在同一台机器上的其他进程，因为 pid namespace 不被共享。基于同样的原因，以及随机的评测用户 uid/gid ，攻击者也无法施展利用 ptrace 逃出镜像文件系统等等的奇技淫巧。 同时，由于第四代评测系统的沙箱本质是创建了一个一模一样的镜像操作系统并全方位限制其权限，我们可以非常轻易地使其支持各种各样的编程语言。作为对比，使用 ptrace 或 seccomp 的传统方案则不得不使用一些非常蹩脚、且安全性值得怀疑的手法来进行安全审查，如系统调用计数等。 ## 4. 比较器 第四代评测系统的比较器全面接入了 Testlib 。包括默认的 NOIP 风格比较器也实现成了类似 SPJ 的形式。简单来说，在第四代评测系统里所有的比较器都是 Special Judge；如果你上传的题目并没有设置 SPJ，评测机则会自动分配默认的 NOIP 风格比较器作为你的 SPJ 。 ## 5. 评测数据管理 所有题目的评测数据被放置在一个统一的仓库中，评测机根据需要自行获取。为了降低网络 IO ，评测机在本地磁盘对评测数据进行缓存。同时，评测机维护每道题目的评测数据被最后一次使用的时间，当磁盘空间不足时，自动从本地删除最近没有被使用过的缓存评测数据。 当评测机需要使用某个测试点时，系统将对应的测试点从磁盘复制到虚拟内存盘中，同时将输入绑定到用户评测程序的 stdin 上。因此，在镜像文件系统中是找不到输入文件的————它存在于外部的文件系统。 ## 6. 结语 虽然洛谷评测机至今有一些 Bug 还需要解决，但是对于如此大的提交量，我们选择了比较合理的方案，并且一直不断改进。洛谷的评测机系统是凝结了洛谷开发者智慧的结晶，具有诸多创新点。我们之所以要不断地更新换代洛谷评测机，是为了让满足越来越多的用户通过洛谷学习提升的需求，并且增强用户体验。虽然新版本的洛谷还是咕咕咕，但是洛谷生态圈(大家看得到的和看不到的地方)依然是每天都有在改进。一切改进都是为了我们用户。