0x00 前提

自从2015年WeJudge(亦简称为OJ)第一个版本面世以来,经历过两次比较大规模的重写。为什么是重写不是重构?因为代码写的很烂。目前的3.x版本是最好的一个版本了,但无论是从技术层面来看,还是从产品层面来看,它都还存在很多很多的问题。基于这些问题,加上我对个人成长的期望,我希望能从现有的基础出发,开发一套代码判题服务实现的解决方案。这个项目会以BSD协议开源,同时,判题机程序deer-executor会以GPL协议开源。开源是希望能够和大家分享交流,希望知识和成果要属于大家。

0x01 反思

先从技术层面上谈谈现在的WeJudge。技术选型方面,3.x版本在服务端采用Python3.6 + Django 2.x 的方案;前端则采用React 16.x + Ant design 4.x的方案。同时,我还编写了相关的CI/CD脚本,实现开发环境和生产环境的一键部署,这个要感谢老东家ones.ai提供的实习机会让我能接触devops相关的知识。下边以我自己的角度来评价一下存在的问题。

产品:

  1. 题库:OJ首个版本的设计思路一开始是参考杭电OJ的设计思路,题目列表、评测队列放全局。后续为适应实际需要,2.x、3.x开始对题目进行分类,通过题库来管理题目。现在主要的问题是题库太多了也不好管理,权限设计上存在问题。目前正在解决
  2. 课程:从设计之初就考虑自研一套方案去解决课程排课问题。3.x定下的方案是学生选课-老师排课-发布作业-按排课设定访问权限。权限方面暂时正常,但学生选课依然是一个大问题。无论如何,北师的老师希望直接从教务系统导入,但3.x已经摆脱了当时学号-账号的模式,改为通用的账号模式。如何更高效的实现学生-账号的绑定呢?并不想依赖教务系统,这种第三方的系统存在风险,你无法预支他什么时候会突然挂掉,或者把你的爬虫封掉。
  3. 评测:现有评测功能是自研的方案,但又多少有杭电的影子,我习惯性称为while(scanf() != EOF),即一个文件内多组数据,需要循环输入来获取。这个方法好处是减少IO,一次性把n组数据丢到程序里跑完即可。然而毛病实在是太多了。WeJudge设计的初衷是服务教学的,面对的群体是广大学生而不是广大ICPCer,你不能用大神的眼光去看待初学者,认为他们啥都能自己解决。他们不能解决的问题,自然需要老师的帮助。但是面对特别大的数据量,这种方式几乎无法定位问题。这方面我又非常赞同以codeforces为代表的那种一数据一文件的方式。服务器资源是拿来用的,哪怕评测一次要不停地打开成百上千的文件,IO效率再低,只要能让用户的使用体验更舒适,那就是值得的。

服务端:

  1. Python并不是一个很适合用来编写复杂系统的语言。自由的数据类型,通过缩进来表示代码块等,给开发者带来一些额外的顾虑。
  2. 没有好的Log习惯,虽然我补充了Sentry的异常跟踪,在500的时候能记录异常点,但是要通过log来排查一些偶发的异常还是比较麻烦
  3. 性能问题,Python确实跑啥都慢
  4. 依赖ORM,导致性能不佳,好在有实现缓存,主要功能的接口不置于慢的难受
  5. 没有单元测试,接口行为基本靠人工调试

前端:

  1. 部分功能的交互行为确实不够清晰,缺乏用户文档,在用户体验上有所不足
  2. 同样是没有单元测试,编程习惯规范的也不是很好,代码存在坏味道
  3. 整个应用功能复杂,加载速度较慢。
  4. 没有类似dva的状态管理方案,状态逻辑部分(Redux+Saga)其实维护起来很复杂。这个我一直在想自己整一个方案来处理,但还没有找到很好的方案。轮子好用,但是为时已晚,不可能把现有代码推翻重来。

其他:从3.x开始,我有幸找到两位大佬学弟帮忙开发这个系统。事实上,因为各种原因,从提出方案到开发完成耗费了1年的时间,期间我负责架构和关键部分额开发,他们负责业务逻辑的开发。整个过程相对还是顺利的,但由于比较仓促,没有留下太多的文档,导致后要找人维护起来较为困难。他们快毕业了,我也担心后继无人。

还有很多可能一时想不到,先暂时写下这么多。

0x02 WeJudge Polygon – 打造一个通用的开源代码评测服务 

在设计之初,WeJudge就被定义为是一个面向教学的OJ系统,以实现基本的评测功能为前提,开发出题库、课程、比赛这三个核心模块。服务端采用“接口服务”-“异步队列”-“判题机”的工作模型,异步完成评测流程。

这是一个较为简单的模式,能够快速的完成这套系统的开发。但并不是一个面向未来的设计,说到底,谁都离不开谁,谁离开谁都不能独立工作。系统只会变得越来越臃肿,变得更加难以维护。

在微服务的热度不断提高的今天,我决定将WeJudge自带的评测功能重新开发,令其能够独立地运行评测任务。无论未来系统如何变化,只要需要评测功能,都可以使用这个服务来支持。

这就是为什么我要重写deer-executor和开发一个全新的评测服务:WeJudge Polygon

0x03 Deer-executor的前世今生

2015年5月,我在OJ项目立项之初就在github找到了一位大佬开发的名为Lo-runner的评测核心,这是一个CPython模块,需要在linux下进行编译后使用。1.x和2.x的OJ都是使用这个模块作为核心的,我在这个项目里加入了特殊评测的代码,以及做了一些优化调整,缝缝补补又一年。

后来觉得需要研发自己的判题机,在接触了Go语言后,参考Lo-runner里的判题工作思路,经过1个多月时间的准备,于2018年12月31日发布了deer-executor的第一个版本。此时deer-executor只是一个功能包,它并不能独立工作。3.x版其实有个内部为开源的判题机叫deer-judger,真正的判题调度、队列管理、结果持久化和通知等,是由它完成的。简单的理解就是,v1版的executor只能评测一题里的一个数据,真正能够完整运行一个题目所有测试数据并计算结果的,只有deer-judger

而v2版本,我将deer-judger里关于评测的基本逻辑搬运过来,并增加了CLI功能,让它能够独立编译成一个程序。在Linux/Mac环境下,你只要通过

./deer-executor run <config> <code>

即可在本地完整运行一次评测流程。同时我还增加了一套本地的题目和评测结果持久化方案。通过自研的二进制打包格式,支持用户将出好的题目打包成一个独立的题目文件,也可以将运行结果打包成一个文件分享给别人。

题目打包可以实现在任意地方轻松地运行一次评测,未来也方便出题者直接将题目更新到OJ上,以及从OJ上备份题目;

结果分享则方便老师下载以后,回放评测过程,定位问题。毕竟大量数据如果通过浏览器去比对,性能和效率都太差,你不好我也不好。比对工具暂未实现,在做了在做了(新建github项目

v2版本提供了对cf的出题库testlib.h支持,方便出题人出相关特判的题目,当然出题门槛也稍高,但至少是支持的。

安全性方面暂时还是又docker去实现隔离,能力有限,未来有空再研究沙盒了;由于windows下不能支持评测(同样能力有限),我屏蔽了windows下的评测功能,但testlib.h的出题、题目打包解包那些还是支持的。为未来出题人可以在自己电脑上直接出题做好准备。(当然需要安装编译器的,我可没把gcc打包进去)

总之,deer-executor要成为一个基于命令行的,独立的判题机程序。目前它已经发布了,但我不敢说它是正式发布或者稳定版,因为它只能跑过单元测试,并没有经过时间和用户的检验。先成长吧,勿骄勿躁。

为啥叫deer-executor?有故事,但我没有酒,所以你猜呗。

0x04 所以呢?

从这篇开始,我将以日记的方式,记录WeJudge Polygon的开发历程,真正如标题所说,从零开始去开发一个评测系统,分享我的心得。

如果你有想法,欢迎和我讨论。

判题机: https://github.com/LanceLRQ/deer-executor

WeJudge Polygon公共项目:https://github.com/wejudge/wejudge-polygon (目前在我个人Fork出的项目下开发,等准备好了会merge过去)

0x05 夹带私货

当年的毕业论文:

程序设计在线评测辅助教学系统的设计与实现-蓝荣祺.pdf

原文作者: 阮一峰

这是阮一峰老师关于RSA算法的一篇很有名的文章,文章对RSA算法的原理讲解的比较细,内容通俗易懂。如果你对密码学感兴趣,本文绝对是值得一读的!原文分了两节,我都整理到一起了,删去了一些失效的链接,并且使用LaTex重新整理各个数学公式,让你更加方便阅读。

原文链接:
http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

——小七

如果你问我,哪一种算法最重要?

我可能会回答“公钥加密算法”

因为它是计算机通信安全的基石,保证了加密数据不会被破解。你可以想象一下,信用卡交易被破解的后果。

进入正题之前,我先简单介绍一下,什么是”公钥加密算法”。

一、一点历史

1976年以前,所有的加密方法都是同一种模式:

(1)甲方选择某一种加密规则,对信息进行加密;

(2)乙方使用同一种规则,对信息进行解密。

由于加密和解密使用同样规则(简称”密钥”),这被称为“对称加密算法”(Symmetric-key algorithm)。

这种加密模式有一个最大弱点:甲方必须把加密规则告诉乙方,否则无法解密。保存和传递密钥,就成了最头疼的问题。

1976年,两位美国计算机学家Whitfield Diffie 和 Martin Hellman,提出了一种崭新构思,可以在不直接传递密钥的情况下,完成解密。这被称为“Diffie-Hellman密钥交换算法”。这个算法启发了其他科学家。人们认识到,加密和解密可以使用不同的规则,只要这两种规则之间存在某种对应关系即可,这样就避免了直接传递密钥。

这种新的加密模式被称为”非对称加密算法”。

(1)乙方生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。

(2)甲方获取乙方的公钥,然后用它对信息加密。

(3)乙方得到加密后的信息,用私钥解密。

如果公钥加密的信息只有私钥解得开,那么只要私钥不泄漏,通信就是安全的。

1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。从那时直到现在,RSA算法一直是最广为使用的”非对称加密算法”。毫不夸张地说,只要有计算机网络的地方,就有RSA算法。

这种算法非常可靠,密钥越长,它就越难破解。根据已经披露的文献,目前被破解的最长RSA密钥是768个二进制位。也就是说,长度超过768位的密钥,还无法破解(至少没人公开宣布)。因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全。

下面,我就进入正题,解释RSA算法的原理。文章共分成两部分,今天是第一部分,介绍要用到的四个数学概念。你可以看到,RSA算法并不难,只需要一点数论知识就可以理解。

二、互质关系

如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。比如,15和32没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。

关于互质关系,不难得到以下结论:

1. 任意两个质数构成互质关系,比如13和61。

2. 一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如3和10。

3. 如果两个数之中,较大的那个数是质数,则两者构成互质关系,比如97和57。

4. 1和任意一个自然数是都是互质关系,比如1和99。

5. p是大于1的整数,则p和p-1构成互质关系,比如57和56。

6. p是大于1的奇数,则p和p-2构成互质关系,比如17和15。

三、欧拉函数

请思考以下问题:

任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?)

计算这个值的方法就叫做欧拉函数,以φ(n)表示。在1到8之中,与8形成互质关系的是1、3、5、7,所以 φ(n) = 4。

φ(n) 的计算方法并不复杂,但是为了得到最后那个公式,需要一步步讨论。

第一种情况

如果n = 1,则 φ(1) = 1。因为1与任何数(包括自身)都构成互质关系。

第二种情况

如果n是质数,则 \Phi(n)=n-1 。因为质数与小于它的每一个数,都构成互质关系。比如5与1、2、3、4都构成互质关系。

第三种情况

如果n是质数的某一个次方,即 n = p^k (p为质数,k为大于等于1的整数),

\Phi (p^{k}) = p^{k} - p^{k-1}

比如 \Phi(8) = \Phi(2^3) =2^3 - 2^2 = 8 -4 = 4

这是因为只有当一个数不包含质数p,才可能与n互质。而包含质数p的数一共有p^{k-1}个,即1×p、2×p、3×p、...、p^{k-1}×p,把它们去除,剩下的就是与n互质的数。

上面的式子还可以写成下面的形式:

\Phi (p^{k}) = p^{k} - p^{k-1} = p^{k}(1-\frac{1}{p})

可以看出,上面的第二种情况是 k=1 时的特例。

第四种情况

如果n可以分解成两个互质的整数之积,

n = p1 \times p2

\Phi(n) = \Phi(p1p2) = \Phi(p1)\Phi(p2)

即积的欧拉函数等于各个因子的欧拉函数之积。比如,\Phi(56) = \Phi(8\times7)=\Phi(8)\times\Phi(7)=4\times6=24

这一条的证明要用到“中国剩余定理”,这里就不展开了,只简单说一下思路:如果a与p1互质(a < p1),b与p2互质(b < p2),c与p1p2互质(c < p1p2),则c与数对 (a, b) 是一一对应关系。由于a的值有φ(p1)种可能,b的值有φ(p2)种可能,则数对 (a,b) 有φ(p1)φ(p2)种可能,而c的值有φ(p1p2)种可能,所以φ(p1p2)就等于φ(p1)φ(p2)。

第五种情况

因为任意一个大于1的正整数,都可以写成一系列质数的积。

n = p_{1}^{k_{1}} p_{2}^{k_{2}} ... p_{r}^{k_{r}}

根据第4条的结论,得到

\Phi(n) = \Phi(p_{1}^{k_{1}}) \Phi(p_{2}^{k_{2}}) ... \Phi(p_{r}^{k_{r}})

再根据第3条的结论,得到

\Phi(n) = p_{1}^{k_{1}} p_{2}^{k_{2}}...\;p_{r}^{k_{r}}(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{r}})

也就等于

\Phi(n) = n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}})...(1-\frac{1}{p_{r}})

这就是欧拉函数的通用计算公式。比如,1323的欧拉函数,计算过程如下:

\Phi(1323) = \Phi(3^3\times7^2) = 1323(1-\frac{1}{3})(1-\frac{1}{7}) = 756

四、欧拉定理

欧拉函数的用处,在于欧拉定理。”欧拉定理”指的是:

如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:

a^{\Phi(n)}\equiv 1(mod\;n)

也就是说,a的φ(n)次方被n除的余数为1。或者说,a的φ(n)次方减去1,可以被n整除。比如,3和7互质,而7的欧拉函数φ(7)等于6,所以3的6次方(729)减去1,可以被7整除(728\div7=104)

欧拉定理的证明比较复杂,这里就省略了。我们只要记住它的结论就行了。

欧拉定理可以大大简化某些运算。比如,7和10互质,根据欧拉定理,

7^{\Phi(10)}\equiv 1(mod\;10)

已知 φ(10) 等于4,所以马上得到7的4倍数次方的个位数肯定是1。

7^{4k}\equiv 1(mod\;10)

因此,7的任意次方的个位数(例如7的222次方),心算就可以算出来。

欧拉定理有一个特殊情况。

假设正整数a与质数p互质,因为质数p的φ(p)等于p-1,则欧拉定理可以写成

a^{p-1}\equiv 1(mod\;p)

这就是著名的费马小定理。它是欧拉定理的特例。

欧拉定理是RSA算法的核心。理解了这个定理,就可以理解RSA。

五、模反元素

还剩下最后一个概念:

如果两个正整数a和n互质,那么一定可以找到整数b,使得 ab-1 被n整除,或者说ab被n除的余数是1。

ab\equiv 1(mod\;n)

这时,b就叫做a的“模反元素”

比如,3和11互质,那么3的模反元素就是4,因为 (3 \times 4) - 1 可以被11整除。显然,模反元素不止一个, 4加减11的整数倍都是3的模反元素 \{...,-18,-7,4,15,26,...\},即如果b是a的模反元素,则 b+kn 都是a的模反元素。

欧拉定理可以用来证明模反元素必然存在。

a^{\Phi(n)} = a \times a^{\Phi(n)-1}\equiv 1(mod\;n)

可以看到,a的 φ(n)-1 次方,就是a的模反元素。

好了,需要用到的数学工具,全部介绍完了。

有了这些知识,我们就可以看懂RSA算法。这是目前地球上最重要的加密算法。

六、密钥生成的步骤

我们通过一个例子,来理解RSA算法。假设爱丽丝要与鲍勃进行加密通信,她该怎么生成公钥和私钥呢?

第一步,随机选择两个不相等的质数p和q。

爱丽丝选择了61和53。(实际应用中,这两个质数越大,就越难破解。)

第二步,计算p和q的乘积n。

爱丽丝就把61和53相乘。

n = 61\times53 = 3233

n的长度就是密钥长度。3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。

第三步,计算n的欧拉函数φ(n)。

根据公式:

\Phi(n)=(p-1)(q-1)

爱丽丝算出φ(3233)等于60 × 52,即3120。

第四步,随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。

爱丽丝就在1到3120之间,随机选择了17。(实际应用中,常常选择65537。)

第五步,计算e对于φ(n)的模反元素d。

所谓“模反元素”就是指有一个整数d,可以使得ed被φ(n)除的余数为1。

ed\equiv 1(mod\;\Phi(n))

这个式子等价于

ed - 1= k\,\Phi(n)

于是,找到模反元素d,实质上就是对下面这个二元一次方程求解。

ex+\Phi(n)y=1

已知 e=17, φ(n)=3120,

17x+3120y=1

这个方程可以用“扩展欧几里得算法”求解,此处省略具体过程。总之,爱丽丝算出一组整数解为 (x,y)=(2753,-15),即 d = 2753。

至此所有计算完成。

第六步,将n和e封装成公钥,n和d封装成私钥。

在爱丽丝的例子中,n=3233,e=17,d=2753,所以公钥就是 (3233,17),私钥就是(3233, 2753)。

实际应用中,公钥和私钥的数据都采用ASN.1格式表达。

七、RSA算法的可靠性

回顾上面的密钥生成步骤,一共出现六个数字:

p\;\;\;\;q\;\;\;\;n\;\;\;\;\Phi(n)\;\;\;\;e\;\;\;\;d

这六个数字之中,公钥用到了两个(n和e),其余四个数字都是不公开的。其中最关键的是d,因为n和d组成了私钥,一旦d泄漏,就等于私钥泄漏。

那么,有无可能在已知n和e的情况下,推导出d?

  (1)ed\equiv 1(mod\;\Phi(n))。只有知道e和φ(n),才能算出d。

  (2)\Phi(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)。

  (3)n=pq。只有将n因数分解,才能算出p和q。

结论:如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。

可是,大整数的因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。维基百科这样写道:

  ”对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。

  假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。

  只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。”

举例来说,你可以对3233进行因数分解(61×53),但是你没法对下面这个整数进行因数分解。

12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413

它等于这样两个质数的乘积:

33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
  ×
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917

事实上,这大概是人类已经分解的最大整数(232个十进制位,768个二进制位)。比它更大的因数分解,还没有被报道过,因此目前被破解的最长RSA密钥就是768位。

八、加密和解密

有了公钥和密钥,就能进行加密和解密了。

(1)加密要用公钥 (n,e)

假设鲍勃要向爱丽丝发送加密信息m,他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意,m必须是整数(字符串可以取ascii值或unicode值),且m必须小于n。

所谓”加密”,就是算出下式的c:

m^e\equiv c (mod\;n)

爱丽丝的公钥是 (3233, 17),鲍勃的m假设是65,那么可以算出下面的等式:

65^{17}\equiv2790(mod\;3233)

于是,c等于2790,鲍勃就把2790发给了爱丽丝。

(2)解密要用私钥(n,d)

爱丽丝拿到鲍勃发来的2790以后,就用自己的私钥(3233, 2753) 进行解密。可以证明,下面的等式一定成立:

c^d \equiv m (mod\;n)

也就是说,c的d次方除以n的余数为m。现在,c等于2790,私钥是(3233, 2753),那么,爱丽丝算出

2790^{2753}\equiv65(mod\;3233)

因此,爱丽丝知道了鲍勃加密前的原文就是65。

至此,”加密–解密”的整个过程全部完成。

我们可以看到,如果不知道d,就没有办法从c求出m。而前面已经说过,要知道d就必须分解n,这是极难做到的,所以RSA算法保证了通信安全。

你可能会问,公钥(n,e) 只能加密小于n的整数m,那么如果要加密大于n的整数,该怎么办?有两种解决方法:一种是把长信息分割成若干段短消息,每段分别加密;另一种是先选择一种”对称性加密算法”(比如DES),用这种算法的密钥加密信息,再用RSA公钥加密DES密钥。

九、私钥解密的证明

最后,我们来证明,为什么用私钥解密,一定可以正确地得到m。也就是证明下面这个式子:

c^d\equiv m(mod\;n)

因为,根据加密规则

m^e\equiv c(mod\;n)

于是,c可以写成下面的形式:

c = m^e - kn

将c代入要我们要证明的那个解密规则:

(m^e-kn)^d\equiv m(mod\;n)

它等同于求证

m^{ed}\equiv m (mod\;n)

由于

ed\equiv 1(mod\;\Phi(n))

所以

ed = h\Phi(n) +1

将ed代入:

m^{h\Phi(n)+1} \equiv m (mod\;n)

接下来,分成两种情况证明上面这个式子。

(1)m与n互质。

根据欧拉定理,此时

m^{\Phi(n)} \equiv 1 (mod\;n)

得到

(m^{\Phi(n)})^h \times m \equiv m (mod\;n)

原式得到证明。

(2)m与n不是互质关系。

此时,由于n等于质数p和q的乘积,所以m必然等于kp或kq。

以 m = kp为例,考虑到这时k与q必然互质,则根据欧拉定理,下面的式子成立:

(kp)^{q-1}\equiv 1 (mod\;q)

进一步得到

[(kp)^{q-1}]^{h(p-1)}\times kp\equiv kp (mod\;q)

(kp)^{ed}\equiv kp (mod\;q)

将它改写成下面的等式

(kp)^{ed} = tq + kp

这时t必然能被p整除,即 t={t}'p

(kp)^{ed}={t}'pq+kp

因为 m=kpn=pq,所以

m^{ed}\equiv m (mod\;n)

原式得到证明。

(完)

0x00 背景

传统的评测模式下,判题机按照固定的顺序执行:运行被测程序,获取运行结果,比对结果数据。由于是严格比较,结果数据和答案属于有任意一个字节(除常用格式字符外)不匹配,都将被判定为WA。

有些时候,这种方式太过于苛刻。在涉及到浮点数运算的题目,如计算圆的面积时,我们不得不面对计算结果的精度误差,这将导致原本正确的程序,被判定为WA,显然这不符合我们的逾期。

在特殊评测功能还没能设计开发出来之前,我们通常的解决办法是固定使用一种数据类型出题,比如要求选手使用double来存储浮点数,这样可以确保最终打印的小数精度和我们设定的答案一致。

我们知道,数据检查工具是判题机的一部分,那么是否能让判题机支持调用出题者编写的数据检查工具呢?

0x01 特殊评测

特殊评测中,判题机在数据检查阶段,将控制权交给出题者预定好的数据检查工具。出题者需要按照判题机的文档编写对应的程序,从运行参数列表里接收判题机传过来的输入数据、用户输出数据、答案数据和日志文件等参数,并进行读写、判定,必要时还可以记录日志。所有工作完成后,返回特定的退出代码。判题机接收到将以退出代码作为判题结果。

当然,作为判题机,也要监控这个检查工具的执行情况。如果长时间没有反馈,或者返回了错误的信息,需要及时进行错误标记,并通知出题者等。特殊评测的实现比较简单,这里不再赘述了,需要深入了解,请直接阅读判题机源码即可。

0x02 交互判题

交互式判题是一种新颖的特殊评测形式,它支持特判程序和选手的程序进行互动。

例如,我们可以出一题猜数字游戏:特判程序随机在[0, 1000]内生成一个数,要求被测程序在10次询问内,告知特判程序这个数是什么。每次询问,判题机会告诉你是“>”、“<”还是“=”。如果10次内没有猜到这个数,那么特判程序会直接返回WA,表示被测程序错误了。

上述问题相信大家都知道怎么解答吧。从技术的角度来看,在这个“猜数字”的过程中,特判程序和被测程序之间建立了一个“数据通道”(标准输入输出流),特判程序只要生成一个数,然后通过scanf获取被测程序发来的数,比对后返回结果。比对成功则返回AC,超过10次错误,直接返回WA。而判题机,只需要作为一个旁观者,无须参与实际的数据判定。但如果特判程序结束了,无论被测程序是否执行完毕,都应该直接结束掉。

// 特判程序

#include <stdio.h>
#define AC 0
#define WA 4

int main() {
    int ans = rand() % 1000;
    int ques = 0;
    int err = 0;
    while(~scanf("%d", &ques) && err < 10) {
        if (ques < ans ) {
            printf("<\n");
        } else if (ques > ans ) {
            printf(">\n");
        } else {
            printf("=\n");
            return AC;
        }
    }
    return WA;
}
// 选手程序

#include <stdio.h>
int main() {
    int left = 0, right = 1000, half = (left + right) / 2;
    char ans;
    printf("%d", half);
    fflush(stdout);
    while(~scanf("%c%*c", &ans)) {
        if (ans == '<') {
            right = half;
        } else if (ans == '>') {
            left = half;
        } else {
            return half;
        }
        half = (left + right) / 2;
        printf("%d", half);
        fflush(stdout);
    }
}

下面来讲这个比较有意思的功能是如何实现的。

0x03 数据重定向

要想实现交互判题功能,我们需要对特判程序和被测程序的输入输出流进行重定向。在Linux中,进程之间进行通讯(IPC)的方式常见的有两种:一种是使用pipe管道,另外一种是sockerpair。前者是半双工的,即只能一个发送一个接收;后者是全双工的,可以同时进行发送和接收工作。我们目前只讨论第一种,即pipe方式。

// int pipe(int pipefd[2]); 

int judger[2], program[2];
pipe(judger);   // 特判程序用于读取的管道
pipe(program);  // 被测程序用于读取的管道

pipe函数将会把参数中列表的值分别设置为对应的文件描述符,其中fd[0]为读取,fd[1]为写入。这个很关键,它决定了数据的流向,即fd[1] —> fd[0]。然后,我们就可以拿出之前的dup2函数,将对应的文件描述符指向对应的输入输出流:

// 被测程序
dup2(program[0], STDIN_FILENO);
dup2(judger[1], STDOUT_FILENO);
// 特判程序
dup2(fdjudge[0], STDIN_FILENO);
dup2(program[1], STDOUT_FILENO);

// 数据流向:
// 被测程序 --judger--> 特判程序
// 被测程序 <--program-- 特判程序

这样,我们就完成了交互评测中最核心的逻辑。当然,除了这些核心逻辑,判题机依然需要监控程序的运行状况。因为特判程序和被测程序都是不稳定的,并不知道谁会出错,也难免存在卡住的情况,都需要进行及时的处理。

0x04 更佳的实践

通常情况下,编写特殊评测、交互评测检查器,对于出题者来说无疑是一项并不容易的工作,出题者需要全方位考虑到问题可能发生的各种情况、数据是否符合题目要求等,还得保证接收到一些奇怪的数据时尽量不崩溃。

在我个人的认知里,交互评测功能应该是出自于著名的ACM竞赛网站CodeForces,而该网站推出了一款很强大的评测辅助工具:Testlib。该工具最早是Pascal语言开发的,后用C++重写。它引入了Generator、Validator、Interactor和Checker四个概念,为了便于理解,我将它们分别描述为:输入数据生成器、输入数据校验器、交互评测检查器、普通特判检查器。

它们可以让出题人更加专注于出题,不会被繁琐的校验工作难倒。这里只是简单的描述一下这个工具,如果你需要开发一套完整的判题系统,我非常推荐你尝试支持这套工具的使用,提前代表出题者感谢你的支持。

支持这套工具并不难,你只需要支持出题者上传相关的程序代码,将代码和testlib.h一同编译并运行即可。对于判题机内核,只需要关心interactor和checker的运行和输出。对于OJ网站(出题),能调用shell执行Generator和Validator即可。具体实现了哪些功能,你可以打开cf的polygon网站了解一下。

0x05 畅想未来

判题这块核心的内容讲的差不多了。总的来说,原理并不复杂,往往开发实现的时候会遇到很多的坑,这是必经的过程,不必惊慌。

在人工智能技术不断突破发展的今天,我们完全可以利用这些技术打造一个更加智能的判题程序。这是我设计和开发WeJudge系统的时候,听过最多的建议。因为WeJudge本身面向的群体是学生、教师团体,而不是ACM的参赛者,学生最需要的是学习代码实现的思路、代码风格,注重过程,而不是仅仅局限在精确无误的数据上。严苛的评测机制本身会对这学生带来心理上的压力,也对教师造成的许多不便,毕竟很多时候出现的莫名其妙的问题,老师也难以向学生解答。

总之,在原有的基础上进行突破和超越,是每一位开发者所追求的共同目标。

非常欢迎有想法的你参与到开源判题机的建设上来。

参考和引用:

Testlib中文简介:https://oi-wiki.org/tools/testlib/
Testlib英文博客:https://codeforces.com/testlib
致谢项目:https://github.com/dojiong/Lo-runner
我开发的判题内核deer-executor:https://github.com/LanceLRQ/deer-executor