思路

这个项目是我的本科毕业设计,其实今年年初整个项目就做完了,对它还是挺满意的,想起来好几个月没写过博客了,正好分享一下,嘿嘿。

模仿我们学校OJ来做(HUSTOJ),功能包括题目、作业以及各种信息的的展示,提供学生源代码的在线提交和运行判题,代码的相似度检测以及教师后台资源管理等。

学生教师Web端的各种内容基本就是增删改查,目前的逻辑不算复杂,类似项目做过一些,所以难度不大。后端就采用Spring全家桶,因为之前从来没有彻底前后端分离地做过项目,所以这次打算改变一下,前端使用了Vue.js框架开发,页面单独发布。

主要的难点就在于判题内核的实现,包括代码的编译运行、测试点数据的处理、资源监控、结果判定等,还有源代码的查重,以及如何保证系统安全性等等。首先用户提交代码,系统编译执行肯定不能采用同步的方式(如果学生们聚集在DDL之前同时大量提交,系统很可能因此崩溃),我认为比较好的方式是使用队列,把项目拆分为三个子系统:Web API服务、判题服务、查重服务,并分布式部署,其中判题服务做成判题集群,保证判题功能高效和高可用。服务间的通信使用消息队列中间件。判题和查重两个服务属于内部服务,不提供外部调用入口。整个系统是一个类似垂直型的应用架构。

方法和技术

  • JDK 1.8
  • MySQL
  • Redis
  • RabbitMQ
  • Spring Boot
  • Spring Data
  • Vue.js
  • Semantic-UI
  • Nginx
  • JMeter
  • Jenkins
  • Docker
  • SIM(A software and text similarity tester)

项目不小,框架的部分就不再介绍了,本篇主要就是分享一些关键部分的解决思路和实现方式。

代码的编译运行

编译

以Java代码为例,直接通过Process执行命令 javac Main.java 生成类文件:

private int java(String[] strings) throws IOException, InterruptedException {
        Process compileProcess = Runtime.getRuntime().exec("javac "+strings[0]+strings[1]+strings[2]);
        int result = compileProcess.waitFor();
        return result;
    }

这个方法可以返回目标文件的编译结果,返回0代表通过编译。

其实有一个现成的方法,是通过使用javax.tools.JavaCompiler类来处理文件编译,会方便许多,不过使用命令的方式也不复杂,两种方式都可以。

运行

除了要处理可执行程序的调用,还需要处理程序的输入输出,使用比较贴近操作系统的方式比较好,所以用了C++来写,sys库有许多现成系统API可供调用,方便处理输入输出、耗时内存监控等等。(一开始其实还是用Java做的,需要处理输入输出流以及父子进程,太不方便就放弃了)

处理过程:

开始 -> 创建子进程 -> 设置进程运行用户(低权限)-> 设置子进程IO重定向到文件 -> 父进程启动监控,子进程开始执行Run -> 子进程结束,父进程收集信息并返回。

fork()方法创建子进程

bool createProcess(pid_t& pid, sigset_t& sigset) {
    sigset_t originalSigset;
    sigemptyset (&sigset);
    sigaddset (&sigset, SIGCHLD);
    if ( sigprocmask(SIG_BLOCK, &sigset, &originalSigset) < 0 ) {
        return false;
    }
 
    pid = fork();
    if ( pid == -1 ) {
        return false;
    }
    return true;
}

为子进程设置运行用户uid=1000(这个Linux用户提前创建好并查到它的uid)

void setupRunUser() {
    while ( setgid(1000) != 0 ) {
        std::cout <<  "[WARN] setgid(1000) failed." << std::endl;
        sleep(1); 
    }
    while ( setuid(1000) != 0 ) {
        std::cout <<  "[WARN] setuid(1000) failed." << std::endl;
        sleep(1); 
    }
    while ( setresuid(1000, 1000, 1000) != 0 ) {
        std::cout <<  "[WARN] setresuid(1000, 1000, 1000) failed." << std::endl;
        sleep(1);
    }
}

dup2()方法设置I/O重定向到文件

void setupIoRedirection(
    const std::string& inputFilePath, const std::string& outputFilePath) {
    if ( inputFilePath != "" ) {
        int inputFileDescriptor = open(inputFilePath.c_str(), O_RDONLY);
        std::cout << "[DEBUG] Setup I/O Redirection: InputFilePath = " << inputFilePath << ", InputFileDescriptor = " << inputFileDescriptor << "." << std::endl;
        dup2(inputFileDescriptor, STDIN);
        close(inputFileDescriptor);
    }
    if ( outputFilePath != "" ) {
        int outputFileDescriptor = open(outputFilePath.c_str(), O_CREAT | O_WRONLY);
        std::cout << "[DEBUG] Setup I/O Redirection: OutputFilePath = " << outputFilePath << ", OutputFileDescriptor = " << outputFileDescriptor << "." << std::endl;
        if (outputFileDescriptor==-1) {
            std::cout << "[ERROR] Setup I/O Redirection: " << strerror(errno) << std::endl;
        }
        chmod(outputFilePath.c_str(), S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH);
        dup2(outputFileDescriptor, STDOUT);
        dup2(outputFileDescriptor, STDERR);
        close(outputFileDescriptor);
    }
}

程序运行并返回结果

执行预先准备好的命令(如Java就是java Main),并返回exitcode.

对于程序执行时资源占用的监听,方式比较多,我使用的是父进程访问/proc/{pid}/statm文件,得到子进程的内存占用情况。时间的统计就通过结束时毫秒数减去开始时毫秒数。

由于这部分代码使用C++写,所以要先单独编译成.so文件,然后提供给Java通过JNI的方式调用。Java拿到执行结果后,首先根据题目要求判断是否时间超限、内存超限,通过后再逐行比较程序输出的文件 以及 题目测试用例的输出文件,如果不完全一致,那就标记为答案错误。

测试点数据的处理

教师提供的题目测试用例都是保存在MySQL数据库中的,一个题目包含多条测试用例。处理方式是本题收到首次提交时,就把本题的所有测试用例通过一定的路径持久化到评测机硬盘上。题目运行时,首先检查测试用例输入输出文件是否存在,若不存在则创建。

public void save(Submission s, List<TestPoint> testPoints) throws IOException {
        //e.g. /data/tests/7/input7.txt
        String[] strings = {sysTestsPath+s.getId()+ File.separator};
        Path testPath = Paths.get(strings[0]);
        if (Files.exists(testPath)) {
            return;
        }
        Files.createDirectory(testPath);
        for (TestPoint t: testPoints) {
            Path inPath = Paths.get(strings[0] + "input" + t.getIndeex() + ".txt");
            Files.createFile(inPath);
            try(BufferedWriter writer = Files.newBufferedWriter(inPath, StandardCharsets.UTF_8, StandardOpenOption.WRITE)){
                writer.write(t.getInput());
                writer.flush();
            }
            Path outPath = Paths.get(strings[0] + "output" + t.getIndeex() + ".txt");
            Files.createFile(outPath);
            try(BufferedWriter writer = Files.newBufferedWriter(outPath, StandardCharsets.UTF_8, StandardOpenOption.WRITE)){
                writer.write(t.getOutput());
                writer.flush();
            }
        }
    }

代码查重

这个功能许多OJ系统没有提供,但是我们学校的OJ有,我觉得非常不错。和我们学校OJ的实现方式一样,使用开源工具SIM来查重,它提供一个命令行工具,可以返回两个文件(文本或源码)的内容相似度,可以检测多种编程语言。

它的项目首页、下载以及文档在此:Similarity Tester

它的原理我看了一下,基本上,不怎么懂。。简单的看就是基于语法树的比较,把代码处理成语法树,然后比较两棵树的距离,由于语法树可以得到代码的Tokens(比如符号,关键字,操作符,变量名,值等等),那么查重的结果应该是非常准确的,因为可以抵抗变量重命名,注释,代码重排等等,就非常合适。(原本还想用字符串匹配算法或者编辑距离算法来做,还是太年轻了,检测检测字符串还行,想做得好还要处理分词,统计什么的,有点难,还是上开源工具吧!)

我写了一个Shell脚本用来简化调用命令,对于已经保存在磁盘上的学生提交文件,提供题目ID以及学号就可以直接返回对应代码相似度。比较简单,就是命令拼接+结果提取并返回。

#!/bin/bash
EXE_PATH=/usr/local/sim302/bin
SUBS_PATH=/data/subs
EXT=$1
PROBLEM_ID=$2
SUBMISSION_ID1=$3
SUBMISSION_ID2=$4
result=`$EXE_PATH/sim_$EXT -p $SUBS_PATH/$PROBLEM_ID/$SUBMISSION_ID1/Main.$EXT $SUBS_PATH/$PROBLEM_ID/$SUBMISSION_ID2/Main.$EXT`
echo $result | egrep -o '[[:digit:]]+[[:space:]]+%' | egrep -o '[[:digit:]]+'

(这是个非常尬的脚本)

然后还做了一个相似代码分组的功能,就是一个班里30个人的作业,交上去其实最多也就5、6个版本,都懂,嘿嘿~ 这个功能可以展示出哪些同学的提交属于同一个组(版本),某个组内原创者是谁。

如A和B相似度超过85%,B和C相似度超过85%,A和D相似度超过85%,可以简单认为A、B、C和D属于同一分组,也就是图论算法中的连通,同时它是无向的。所以计算分组可以查询出所有相似度大于85%的条目并构成无向图,然后计算它的极大连通子图的数量,也就是最大连通分量。这个部分使用深度优先遍历实现,比较简单。

系统安全保障

其实一开始这个问题我根本没考虑到,如果某个很皮的学生提交的代码里包含比如关机,删除文件这种会对系统造成破坏的命令,那就非常麻烦了。所以OJ一般都会把判题核心做成一个沙箱,代码的运行无法影响到其他地方。经过调查,普遍的实现方式就是设置运行用户权限非常低,并且还维护一个敏感命令、词汇的表,如果代码里包含这些敏感内容,就直接判定为非法提交。

这两年容器技术有点火,为了能跟上时代的步伐,学了Docker,就用它来做虚拟化,所有判题机、查重机,包括整个系统各个服务都运行在Docker之上,这种天然的沙箱机制用在这个项目里非常合适。

用了Docker,就可以很轻松的实现教师后台直接操作服务集群的功能,直接使用DockerRemote API,Docker守护进程会绑定一个所在宿主机的套接字,也就是unix:///var/run/docker.sock,把守护进程绑定到一个端口上:

docker -d -H unix:///var/run/docker.sock -H 0.0.0.0:9009

访问https://foohost:9009/info,会返回容器的运行信息。

可玩性很高,之后打算把评测节点做成弹性的。

总结

一开始确实低估了它的难度,做起来遇到了各种坎,各种坑,好在都解决了。十几个关系型数据表,除了无聊的各种增删改查以外,还是学到了包括许多关于前后端开发、操作系统和进程相关的新知识,带来了不错的个人成长。其中我自己比较满意的是用户认证授权部分,感觉自己的思路和做法还行,分享下:关于用户认证,这个项目是设计成无状态的(因为要做集群,会话存到Redis有点成本,系统交互性也不强,所以直接无状态)。我用了类似JWT的一种Token,比较简单,也挺安全,就是登录时对“#用户身份#用户ID#过期时间”做个AES加密,然后Base64编码。用户登陆成功直接签发并返回,前端存到LocalStorage里,之后每次用户请求都带在Headers里,注意这个Token是不需要统一保存数据库的,只需要保存一个AES密钥,服务端只需要负责签发和验证,因为Token不仅用来验证,还用来传递身份信息过期信息,还能防范CSRF攻击。关于权限,只有学生和教师两种角色,资源的划分也比较明显,这个权限粒度已经相当粗了,用户鉴权用AOP实现,先编写一个@TeacherRequired自定义注解标记需要教师权限的接口,再编写一个AOP通知检查当前请求的用户角色,这么做起来感觉很清爽干净。

项目做完还压测了一波,项目用了4个1核1G2M的服务器,最复杂的接口平均500+ms,90Line700ms左右,应该还算可以,嘿嘿。


项目暂时没有开源,如果有需要参考源码的朋友,请发邮件给我,我会尽快回复你。