MENU

写一个OJ

August 14, 2014 • 扯淡

为了保证博客不会长草我还是很努力在坚持一月一更的……八月花了几天完工了一个OJ的一期工程,那么现在就来讨论讨论这个吧,也算是给自己做个备忘,可能之后有什么改动或者优化的也可以看看这里。

“Online Judge系统(简称OJ)是一个在线的判题系统。用户可以在线提交程序多种程序(如C、C++)源代码,系统对源代码进行编译和执行,并通过预先设计的测试数据来检验程序源代码的正确性。”——摘自百度百科。

由定义看,显然一个OJ至少是由两个部分组成的:一是Web,二是Judger(下称评测机)。看起来评测机部分应该比较大头,那么本文主要内容就是评测机。

还是由定义,我们可以把评测机的整个工作流程拆分一下:领取一个任务;编译源代码;在题目给定的资源限制下运行程序并与给定答案进行比较(重复进行);返回评测结果。OJ这个东西,做的人还是很多的,开源的程序虽然不至于到满天飞,也是有不少的。我没有对这些代码参考太多,而是自己陆续写出过3个原型。一是完全使用PHP编写:编译不用说、使用popen和管道进行运行,用死循环监测运行状况、写一个鸡肋的算法验证答案;二是使用C编写监测程序,用PHP调用并完成其他流程;三是现行的版本,为了性能,使用C++(监测部分只能用C,谁让操作系统是C写的呢)编写。对比一下三种方法,会发现PHP性能差到可怕:死循环中用microtime卡时间,用ps然后sscanf卡内存……有点难以想象。但是做了三个原型之后有一个信念倒是根深蒂固了:必须使用标准输入输出!PHP中我们使用pipe来重定向,C中fork的时候直接一个freopen就搞定了。而文件输入输出不仅面临修改文件名/复制文件的开销,还会因为可进行磁盘IO而造成一些不必要的麻烦。

伴随着原型敲定的,是评测的具体流程:Web端接收一个提交,将相关信息写入数据库,状态设为“未评测”,并将源代码写入一特定目录。评测机的main中是一个数据库的轮询,一旦能够读到一条未评测的数据,就将该记录作为参数传给评测函数Judge。Judge通过该任务的问题ID(PID)进行一次查询,得到时间、内存限制和测试数据的组数。接着是编译,编译过程中需要注意对于结果“编译错误”的判定:我见过很多OJ中,只要编译器有输出就判定为编译错误,这其实是不合理的——尤其是参数中开了-Wall,warn all的情况。因此逻辑应该是这样的:system运行编译器,并将所有输出重定向到某一文件,将输出悉数写入数据库的“编译输出”字段;检测一下是否存在编译器生成的可执行文件,若存在,即编译成功,可以继续了。接下来就是fork一个子进程来跑评测,再用ptrace进行监测了。用ptrace,获得运行时间和main返回的值是轻而易举的——可判定“超时”或“运行时错误”,在fork的时候可以得到pid,那么依据“Everything is a file”,可以通过/proc/%pid%/statm读内存状况。实现答案对比是挺简单的活儿,比对完答案,就可以判断是“通过”还是“答案错”了。伴随着最终结果的得出,所有评测数据被保存进数据库,新一次的轮询开始了。整个程序只用到了一个外部库libmysqlclient哦——当然,不包括它的依赖。

没错,我只提了流程,完全没提到技术细节——事实上OJ确实是一个非常非常危险的东西——用户竟然可以上传源码并编译执行。出于安全考虑,也是对代码信心不足,能不公开当然不公开。显然安全问题也是重头戏,下面我们就来聊聊安全。

现在好像有个高大上的东西叫做Docker,没办法,暂时折腾不了,还是继续rlimit吧……为了尽可能的提高安全系数,我始终建议是Web和Judger隔离的,至少Judger跑在一个虚拟机上,并且跑评测机的用户绝对不可以是root。对于评测机需要访问到的目录,比如源码目录,临时文件目录和评测数据目录,一定注意好访问权限控制(以防恶意代码把整个题库洗了什么的…)。然后就是编译器了。头文件是必须要改的,危险函数什么的统统注释掉,特别危险的直接删掉。完全有理由相信对于菜鸟,没了头文件会直接蒙圈。最好是能够重新编译C/C++库,找不到符号是最好的。过滤字符串,同理,也是对于菜鸟有效。真正想黑的,奇奇怪怪的宏满天飞,根本无法战胜,搞不好还会误伤无辜变量……另外说到宏,让人联想到预处理器,这玩意儿也是有挺多奇技淫巧的玩法,要是include了个什么奇奇怪怪的东西(不能说出来,否则自找不痛快啊)……所以字符串过滤还是需要做一下的:但是要建立在先把反斜杠连接的多行语句给还原为一行的基础上。

安全问题要考虑全面了估计不容易。所以这个OJ预计将处于并将长期处于内部使用阶段……刚才谈完了(简单地)评测机部分,Web部分可以说的内容不多。毕竟Web也就是这么个东西,要实现的都是很普通的需求。想把页面做漂亮了,想把功能做舒服了,砸时间进去就行。

Tags: 杂谈
Archives Tip
QR Code for this page
Tipping QR Code