不指定 类别: 其他 | felix021 @ 2013/07/26 14:02 | 评论(0) | 阅读(9549)
Land项目 写完三年多了,期间各种小修小补,比较大的变动主要有两个,都是针对SPJ的,一个是安全方面的:原先SPJ程序是以root权限运行的,现在给限制成nobody了;另一个是优化了SPJ的实现方式,给了一个template,把源码也作为一个参数传了进来,于是在 Starter系统 里面,我可以限制学生们以预期的方式来完成作业(比如学习指针时程序里不允许出现数组的 [ ] 标记)。

这两天重新回到nth_element算法上来,发现如果要针对nth_element算法来出题目的话,现有的OJ功能不是很合适,主要是对于这类O(N)甚至O(NlogN)算法的题目,I/O的时间往往与实际算法运行时间相当甚至相比更长,所以需要将这一部分时间从最终的程序运行时间中扣掉。因此在添加题目时,需要在OJ上先执行一个仅输入、输出该题所需数据的程序,将它的运行时间作为标准I/O时间。

更激进一点的想法是,在题目里约定好接口,提交的代码里只需要实现该接口,而数据则由预先提供的主程序读取好。但是这样工作量比较大,不同的题目需要的数据不同,接口也就不同;而且一个OJ往往支持多种语言,从而需要为每一个语言提供一个主程序。

此外,由于CPU效率的不同,同一个程序在不同系统上运行的时间也不同,但是应当大致与标准程序成比例(刨开IO)。现在WOJ上的题目多是05/06前后两年出的题目,而现在WOJ则是在一个11年的服务器上运行,导致一些当时还比较难的题目,现在可以通过暴力的方式AC,这一点很蛋疼。因此需要一个参考值来校准,例如写一个C程序空循环10亿次所需的时间。在新增一个题目、为其设置运行时间时,可以将该题目对应的参考时间值也给出来。这样当OJ换到新硬件上( 也可能是旧硬件:'( )以后,只需要简单的计算就可以得到在新硬件上的对应时间。

虽然有了想法,但是估计没有足够的动力去实现了。前面SPJ的两个问题,是去年上半年当C教辅的时候要用到,所以才顺便解决了的,希望WHUACM以后有谁能接过去吧...
其他 | 引用(0) |
不指定 类别: 其他 | felix021 @ 2011/01/14 16:37 | 评论(1) | 阅读(5210)
@2011-01-19  邮件系统已经更新,下文不适用于新系统,老系统从 http://202.114.64.181 登录。

acm @ whu.edu.cn 在 http://whu.edu.cn 登录。由于垃圾邮件太多,删除的时候很累,所以我写了一点代码,将

删除邮件

这个链接拖到浏览器的书签栏保存,进入邮箱 收件箱 或者 废纸篓 后只要点击该书签,就会将该页面的所有邮件删除。

在这个地址 http://202.114.64.181:8080/nda/default/zh-CN/login.htm 可以登录了设置一些过滤器。
其他 | 引用(0) |
不指定 类别: 其他 | felix021 @ 2010/10/29 21:02 | 评论(1) | 阅读(4854)
这个词组在ACM/ICPC的各大OJ出现频率还是很高的,意思是使用了“受限制的函数”。

而且几乎没有准确的文档可以定义什么是"Restricted Function"(RF,非彼“RF”)。因为开发者也很郁闷。一个大致可以接受的解释是,任何可能威胁到系统安全的代码都不应该被执行。更严格一点,任何解题所不需要用到的函数都不应该调用。但是这两个解释都不够准确。

作为一个需要编译并运行用户任意代码的系统,必然需要对用户的代码/程序进行额外的处理,过滤可能对服务器产生危险的操作。在woj-land ( http://code.google.com/p/woj-land ) 的实现中,是采用运行时监控程序的执行,通过ptrace来拦截并检查每一个系统调用,如果发现系统调用不在白名单中,即出现RF。具体的代码可参见:http://code.google.com/p/woj-land/source/browse/trunk/code/judge/rf_table.h

白名单机制是最安全的了,但是有缺陷。

首先是很难考虑到所有的情况。举例来说,你用C语言写的A+B来测试的话,需要的系统调用只有几个。大多数情况下能够满足要求,但是有时候却发现不对。比如说SYS_futex这个系统调用,如果不被允许,glibc写的程序在执行时可能会出问题。

其次是过于严格,导致部分常用且不影响系统安全的函数被限制死。比如说fflush,只需要用到SYS_lseek调用即可。

再次是有些异常情况。一个典型的情况是使用 qsort(arr, N, sizeof(arr), cmp); 这样的代码。实际上应当是sizeof(int),不小心写错了,访问出错。这时glibc会open("/dev/tty",...),write()一些错误信息,然后open("/proc/self/maps", ...)把进程的内存映射表输出。于是本来应该是运行时错误(段访问异常),即Runtime Error(SIGSEGV)的情况也被误判为Restricted Function了。

終り.

source: http://www.felix021.com/blog/read.php?1948
其他 | 引用(0) |
不指定 类别: 其他 | acm @ 2009/01/26 00:00 | 评论(0) | 阅读(2649)
在牛年之初

祝各位老师,各位ACMer、各位大牛,新春快乐!
      
WHUACM
其他 | 引用(0) |
分页: 1/1 第一页 1 最后页 [ 显示模式: 摘要 | 列表 ]