Beyond the Void

3.judger核心设计

评测系统最重要部分就是评测核心了(judger)。核心judger负责了编译、执行、检查三大部分，也就是评测系统的灵魂所在，因此judger设计的好坏，直接影响到整个评测系统的整体水准。judger的设计要考虑到几个方面，首先是对安全性要求很高。别忘了，这是一个在线评测系统，任何人都可以提交任何代码，并在服务器上执行，这意味着给骇客们提供了方便之门。骇客们（注意，不是黑客）总是希望得到一个Shell，并在上面执行想要的命令。而评测系统直接允许了源码的提交，如果我是骇客的话简直乐坏了。当然，只有傻瓜才会对用户提交的代码直接编译、运行，就像编译自己的程序一样，限制是必不可少的。

不当的方法

一个愚蠢的方案是直接对代码进行扫描，然后过滤掉某些字符串，如”system”。当然这个过滤列表可能长得匪夷所思，就像某墙，然而绕过它却是很容易的，例如以下代码：

#include <stdlib.h>
#define dosomething sys##tem
int main()
{
	dosomething("shutdown");
	return 0;
}

怎么办呢？有人会继续想到，我可以用g++的-E命令，将预处理以后的代码输入到一个文件中，然后再检查关键字。这样的话上面的方法就不行了，不过更厉害的骇客还有办法。什么办法呢？直接按地址调用函数，代码如下：

#include <stdlib.h>
int main()
{
	int (*func)(char *);
	func = (int (*)(char*))134513676;
	func("ls");
	return 0;
}

上述代码中的数值就是 system函数的绝对地址，在不同的环境中不一样，不过获取这个数值并不困难的。由此可见，依靠过滤源代码的方式几乎是行不通的安全性解决方案。如果不依赖检查源代码，就要监控程序的“行为”，这就需要比较复杂的调试器技术了。在Linux下，有一个ptrace函数，可以在程序运行时监测程序的行为，捕获接收到的信号。

解决方案

vakuum的执行器executor，就是用的ptrace的原理。主程序为两个进程，子进程用来执行用户程序，父进程用来监视子进程。子进程每进行系统调用的时候，运行就被中断，由父进程检查子进程的行为是否合法，如果不合法就杀掉子进程。对于open调用，还要检查用户打开的文件是否被允许。有了这个程序，监控程序的用户时间和内存也就不难了，用户时间的监测需要在每个系统调用后检查，对于内存，在任何一个与内存分配相关的系统调用后检查一下/proc/{pid}/statm即可。

如此还有一个问题容易被忽略，就是如果用户程序中长时间不进行系统调用，只是在做一些运算的时候，如何让程序暂停下来判断是否超时呢？设置CPU_Limit为时间限制显然是不行的，因为在监控下的用户程序可能会运行时间更久。不知道大家在用Cena的时候是否发现过一个现象，例如某个程序本来运行0.8秒，设为1秒时限以后显示超时，设为2秒时间反而显示成了0.8秒。这是怎么回事呢？很可能就是设定了不合适的CPU_Limit。稳妥的方法是设置为时间限制的若干倍，但是到底是几倍不好估计，而且很多时候还会浪费时间。思考问题的根源还在于长时间没有被暂停，我的解决方法是给父进程设置一个alarm，每秒向子进程发送一个信号，设置子进程接收到信号以后也会暂停，并检查时间是否超时。这样的话，超时的程序最多会在不超过时限1秒的情况下被终止。

在这种严密的监控下，很难找到突破的方法，至少我至今还没有想到如何攻破executor的监控。其代价就是降低执行效率了，不过由于我监视的是用户时间，用户程序不会被误判超时，尽管感觉实际执行时间多了不少。如果你有什么攻破监控想法，欢迎与我联系做安全性测试。

潜在的缺陷

虽然我并不了解，但是我还是担心，如果用户程序中有汇编代码嵌入，是否可以获得底层的权限。如果真的可以，我还没有想到应对的方法。

在竞赛中，遇到大数据时，往往读文件成了程序运行速度的瓶颈，需要更快的读取方式。相信几乎所有的C++学习者都在cin机器缓慢的速度上栽过跟头，于是从此以后发誓不用cin读数据。还有人说Pascal的read语句的速度是C/C++中scanf比不上的，C++选手只能干着急。难道C++真的低Pascal一等吗？答案是不言而喻的。一个进阶的方法是把数据一下子读进来，然后再转化字符串，这种方法传说中很不错，但具体如何从没试过，因此今天就索性把能想到的所有的读数据的方式都测试了一边，结果是惊人的。
Read the rest of this entry »

写程序跟踪发现，在Linux i386中，一个程序体完全为空的C语言程序启动时要进行近100个系统调用，如下所示。

[ 1]syscall: 11 //execve
[ 2]syscall: 45 //brk 改变进程的数据段边界
[ 3]syscall: 45 //brk
[ 4]syscall: 33 //access 确定文件的可存取性
[ 5]syscall: 33 //access
[ 6]syscall: 192 //mmap2 映射虚拟内存页
[ 7]syscall: 192 //mmap2
[ 8]syscall: 33 //access //access
[ 9]syscall: 33 //access //access
[10]syscall: 5 //open 打开文件
[11]syscall: 5 //open
[12]syscall: 197 //fstat64 取文件系统信息
[13]syscall: 197 //fstat64
[14]syscall: 192 //mmap2
[15]syscall: 192 //mmap2
[16]syscall: 6 //close 关闭文件描述字
[17]syscall: 6 //close
[18]syscall: 33 //access
[19]syscall: 33 //access
[20]syscall: 5 //open
[21]syscall: 5 //open
[22]syscall: 3 //read 读文件
[23]syscall: 3 //read
[24]syscall: 197 //fstat64
[25]syscall: 197 //fstat64
[26]syscall: 192 //mmap2
[27]syscall: 192 //mmap2
[28]syscall: 192 //mmap2
[29]syscall: 192 //mmap2
[30]syscall: 192 //mmap2
[31]syscall: 192 //mmap2
[32]syscall: 6 //close
[33]syscall: 6 //close
[34]syscall: 33 //access
[35]syscall: 33 //access
[36]syscall: 5 //open
[37]syscall: 5 //open
[38]syscall: 3 //read
[39]syscall: 3 //read
[40]syscall: 197 //fstat64
[41]syscall: 197 //fstat64
[42]syscall: 192 //mmap2
[43]syscall: 192 //mmap2
[44]syscall: 192 //mmap2
[45]syscall: 192 //mmap2
[46]syscall: 6 //close
[47]syscall: 6 //close
[48]syscall: 33 //access
[49]syscall: 33 //access
[50]syscall: 5 //open
[51]syscall: 5 //open
[52]syscall: 3 //read
[53]syscall: 3 //read
[54]syscall: 197 //fstat64
[55]syscall: 197 //fstat64
[56]syscall: 192 //mmap2
[57]syscall: 192 //mmap2
[58]syscall: 192 //mmap2
[59]syscall: 192 //mmap2
[60]syscall: 192 //mmap2
[61]syscall: 192 //mmap2
[62]syscall: 6 //close
[63]syscall: 6 //close
[64]syscall: 33 //access
[65]syscall: 33 //access
[66]syscall: 5 //open
[67]syscall: 5 //open
[68]syscall: 3 //read
[69]syscall: 3 //read
[70]syscall: 197 //fstat64
[71]syscall: 197 //fstat64
[72]syscall: 192 //mmap2
[73]syscall: 192 //mmap2
[74]syscall: 192 //mmap2
[75]syscall: 192 //mmap2
[76]syscall: 192 //mmap2
[77]syscall: 192 //mmap2
[78]syscall: 6 //close
[79]syscall: 6 //close
[80]syscall: 192 //mmap2
[81]syscall: 192 //mmap2
[82]syscall: 243 //set_thread_area 设置线程入口
[83]syscall: 243 //set_thread_area
[84]syscall: 125 //mprotect 设置内存映像保护
[85]syscall: 125 //mprotect
[86]syscall: 125 //mprotect
[87]syscall: 125 //mprotect
[88]syscall: 125 //mprotect
[89]syscall: 125 //mprotect
[90]syscall: 125 //mprotect
[91]syscall: 125 //mprotect
[92]syscall: 125 //mprotect
[93]syscall: 125 //mprotect
[94]syscall: 125 //mprotect
[95]syscall: 125 //mprotect
[96]syscall: 91 //munmap 去除内存页映射
[97]syscall: 91 //munmap
[98]syscall: 252 //exit_group 结束

程序很简单

1
2
3
4

int main()
{
	return 0;
}

想进行Linux系统开发已经很久了，一直没有付诸实践。今日终于开始学习Linux下的C语言编程，研究一天，终于大概弄明白了Linux系统进程管理的一些基本概念和编程方法，总结下来以方便大家学习和自己实践。

进程系统

Linux是个多任务多用户的操作系统，系统直接管理的每个任务的最小单位，就是进程(process)。每个进程都有一个惟一的标识符pid，不同的进程pid不相同，在Shell下输入ps -A，可以显示当前的所有进程。一个进程不代表一个应用程序(application)，因为一个应用程序可能对应多个进程，也不代表一个可执行文件(executable file)，因为一些可执行文件可以被同时运行多个，它们是互不相干的。

在Linux中，进程不是相互独立的，每个进程（除了init进程）都有一个父进程(parent process)，同时每个进程可以有0个1个或多个子进程(child process)。换句话说，Linux的进程是一个树形结构，在Shell下输入pstree可以查看这个树的形状。下图为pstree返回结果的一部分。

init─┬─NetworkManager─┬─dhclient
│                └─{NetworkManager}
├─SystemToolsBack
├─avahi-daemon───avahi-daemon
├─bonobo-activati───{bonobo-activati}
├─console-kit-dae───63*[{console-kit-dae}]
├─hald───hald-runner─┬─hald-addon-acpi
│                    ├─hald-addon-cpuf
├─pulseaudio─┬─gconf-helper
│            └─2*[{pulseaudio}]
├─rsyslogd───2*[{rsyslogd}]
├─seahorse-daemon
├─telepathy-gabbl
├─telepathy-haze─┬─telepathy-haze
│                └─{telepathy-haze}
├─trashapplet
└─wpa_supplicant

在C语言中，获得当前进程的pid的函数是pid_t getpid(void);，获得当前进程的父进程的pid的函数是pid_t getppid(void);，两者都在unistd.h中声明。

用户和权限

因为Linux是多用户的系统，所以内核中有着强大的用户控制，因此每个进程还有一个所有者，即实际用户ID(uid)。系统uid是一个整数，不同于用户名。默认情况下进程的uid继承于父进程。例如我用所有者为byvoid(uid为1000)的bash终端启动了一个进程，那么这个进程的uid也是1000。用户uid可以通过uid_t getuid(void);函数获得。如果权限满足，程序在运行时可以修改uid，C语言函数为int setuid(uid_t uid);，如果成功执行返回0，否则返回-1。只有具有root用户权限的进程可以设置uid。

除此以外，进程还有一个有效用户ID(euid)。euid是决定进程文件系统权限的身份，一般情况下进程euid和uid是相同的。在C语言中可以通过uid_t geteuid(void);函数获得进程euid。同样euid也可以修改，函数为int seteuid(uid_t uid);仅当当前uid和euid中至少有一个为0(root)时，才可以设置euid。有一种特殊情况，就是一个二进制可执行文件所有者为root，并且被chmod +s后，在一般用户身份下执行，这时产生的进程uid为一般用户，而euid为0(root)，这种情况下该进程具有和root一样高的权限。

进程生成

fork函数

Linux允许用户创建用户进程的子进程，在C语言中通过pid_t fork(void);函数实现。fork函数的基本功能是生成一个子进程，并复制当前进程的数据段和堆栈段，子进程和父进程共用代码段。因为复制了堆栈段，所以父进程和子进程都停留在fork函数的栈帧中，fork函数要返回两次，一次在父进程中返回，一次在子进程中返回，但是两次的返回值是不一样的。在父进程中，fork函数返回值为子进程的pid（如果成功调用的话），在子进程中，fork函数的返回值为0。因此可以根据返回值的不同确定程序的运行流程。父进程和子进程默认情况下是同步执行的，由系统内核调度，哪个先执行是未知的。因为父子进程的数据段和堆栈段都是独立的，所以两者互不干涉，各行其是，内存不能直接共享。

执行程序

Linux中要执行一个外部程序，必须生成一个子进程，因为内核执行程序的命令exec会替换掉当前进程的地址空间的所有内容并继续执行，执行另一个程序意味着当前程序不再执行。在C语言中，并没有exec这样的一个函数，而是有下列一组函数。

int execl (const char * file,const char * arg,…);
int execlp(const char * file,const char * arg,…);
int execle(const char * file,const char * arg,…,NULL,char * const envp[ ]);
int execv (const char * file, char * const argv[ ]);
int execvp(const char *file ,char * const argv []);
int execve(const char * filename,char * const argv[ ],char * const envp[ ]);

其中以execl开头的函数，第一个参数file为可执行文件名，接下来有若干个参数，分别为传入的argv[0],argv[1],argv[2],…，最有以NULL结束。如果file参数为路径名(其中包含’/')，execl函数会直接定位到文件并执行，否则仅在当前目录下寻找文件，而execlp函数遇到文件名则会按照环境变量PATH的顺序寻找。execle最后一个参数为二维字符数组，表示传递给程序新的环境变量列表。execv，execvp，execve和前三者用法相似，只不过不以可变参数列表的方式传递参数，换以二维字符数组。上述函数执行失败后会返回-1，如果执行成功的话将会不返回，因为代码段已经被新的可执行程序替换。

进程阻塞

wait函数

在实际的应用中，有时候需要让父进程停下来等待子进程的执行完毕，这时候就需要进行进程阻塞(process blocking)。C语言中使用pid_t wait(int *statloc)函数可以得到子进程的结束信息。调用wait函数的进程会阻塞，直到该进程的任意一个子进程结束，wait函数会返回结束的子进程的pid，结束信息保存在statloc指针指向的内存区域。如果该进程没有活动的子进程，那么立即出错并返回-1。如果statloc指针为NULL，那么表示不关心进程结束的状态。如果有多个子进程，wait函数返回哪个数不确定的，需要通过pid来判断。

如果我们需要等待特定的一个进程，可以使用pid_t waitpid(pid_t pid,int *statloc,int options)函数。waitpid函数的第一个参数指定了要等待的进程pid，并且有更多的选项。

僵尸进程

当一个子进程退出时，如果没有被父进程通过wait取得状态信息，这些信息会一直保留在内核内存中，子进程的pid也不会被消除，直到父进程退出，这时候这些子进程被称为僵尸进程（zombie process）。虽然僵尸进程只占用很少的一点内存，但如果是长期运行的服务器，积累大量的僵尸进程会导致系统进程表被塞满，以至于无法创建新的进程。产生一个僵尸进程很容易，只需要让子进程先于父进程退出即可，在父进程退出之前，子进程将会成为僵尸进程。

孤儿进程

与僵尸进程相反，如果父进程没有阻塞并先于子进程退出，那么子进程将会成为孤儿进程(orphan process)。Linux系统中init进程负责领养所有孤儿进程，也就是说，孤儿进程的父进程会被设为init进程。init进程作为系统守护进程(daemon process)，会不断调用wait函数等待领养的孤儿进程退出，不会产生僵尸进程。

利用孤儿进程避免僵尸进程

许多时候我们不能让父进程阻塞下来等待子进程处理完以后再继续，例如在多用户的服务器程序上。这时如果让子进程处理事务，就会产生大量僵尸进程。避免僵尸进程出现的一个经典方法就是利用孤儿进程，具体方法为首先用父进程产生一个子进程，然后让子进程立刻产生一个孙子进程，用孙子进程来处理事务。同时父进程阻塞等待，并让子进程则立刻退出。这时候由于子进程已经退出，孙子进程就变成了孤儿进程，被init领养。而子进程立刻退出后，父进程收到信号并正确销毁了子进程，相比之下父进程只阻塞了可以忽略不计的一瞬间。下面程序是一个例子避免僵尸进程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
 
int main(void)
{
	if(fork() == 0) //启动一个子进程
	{
		printf("the child\n");
		if(fork() == 0) //启动一个孙子进程
		{
			printf("do something you want\n");
			sleep(5);
			printf("done\n");
			exit(0);
		}
		else //子进程立刻退出
			exit(0);
	}
	else
	{ //父进程立即阻塞
		wait(NULL);
		printf("the parent\n");
		sleep(10);
	}
	return 0;
}

BYVoid 原创作品。

在C/C++中，64为整型一直是一种没有确定规范的数据类型。现今主流的编译器中，对64为整型的支持也是标准不一，形态各异。一般来说，64位整型的定义方式有long long和__int64两种(VC还支持_int64)，而输出到标准输出方式有printf(“%lld”,a)，printf(“%I64d”,a)，和cout << a三种方式。

本文讨论的是五种常用的C/C++编译器对64位整型的支持，这五种编译器分别是gcc(mingw32)，g++(mingw32)，gcc(linux i386)，g++(linux i386)，Microsoft Visual C++ 6.0。可惜的是，没有一种定义和输出方式组合，同时兼容这五种编译器。为彻底弄清不同编译器对64位整型，我写了程序对它们进行了评测，结果如下表。

上表中，正确指编译通过，运行完全正确；错误指编译虽然通过，但运行结果有误；无法编译指编译器根本不能编译完成。观察上表，我们可以发现以下几点：

1. long long定义方式可以用于gcc/g++，不受平台限制，但不能用于VC6.0。
2. __int64是Win32平台编译器64位长整型的定义方式，不能用于Linux。
3. “%lld”用于Linux i386平台编译器，”%I64d”用于Win32平台编译器。
4. cout只能用于C++编译，在VC6.0中，cout不支持64位长整型。

表中最后一行输出方式中的printint64()是我自己写的一个函数，可以看出，它的兼容性要好于其他所有的输出方式，它是一段这样的代码：

void printint64(long long a)
{
	if (a<=100000000)
		printf("%d\n",a);
	else
	{
		printf("%d",a/100000000);
		printf("%08d\n",a%100000000);
	}
}

这种写法的本质是把较大的64位整型拆分为两个32位整型，然后依次输出，低位的部分要补0。看似很笨的写法，效果如何？我把它和cout输出方式做了比较，因为它和cout都是C++支持跨平台的。首先printint64()和cout(不清空缓冲区)的运行结果是完全相同的，不会出现错误。我的试验是分别用两者输出1000000个随机数，实际结果是，printint64()在1.5s内跑完了程序，而cout需要2s。cout要稍慢一些，所以在输出大量数据时，要尽量避免使用。