UOJ Logo mcfxmcfx的博客

博客

部分交互题的通用 hack 方法

2020-12-05 08:57:59 By mcfxmcfx

背景

对于一部分交互性题目,他们的考点是调用某个函数的次数。对于某些题目,如果询问次数足够大,那么暴力算法(或者比正解简单的多的做法)也可以通过。

假设交互器不是 adaptive 的(即数据是预先确定的),那么我们可以考虑调用询问函数,然后再把询问次数改回去。这其实很容易做到,比如在程序中内嵌一个 qemu 之类的模拟器,把询问函数模拟执行一遍,并记录下他改动过的内存,事后再改回去。

实现

qemu 体量太大,比较难修改,并且修改完可能也压不进代码长度限制。所以需要找一个比较简单的 x86_64 模拟器。

我经过一番搜索,找到了 https://github.com/blbogdan/x64vcpu 这个项目,他的体量就比较小。去除 FPU 和 SSE 等一些用处不大的东西(这里其实埋了个坑,之后会讲到),再去掉 asm(为了满足 uoj 的要求),得到了 https://github.com/mcfx0/x64vcpu 这样一个东西。

接下来就可以去 hack 交互题了,比如 https://uoj.ac/submission/441760

不过对于其他一些题目,比如 https://uoj.ac/problem/165 ,他的交互次数非常多,暴力本身的运行时间就已经接近时限,这种情况下如果还是每次询问都模拟,显然会 TLE。所以可以在最开始模拟一次询问,获取他修改的内存位置,最后再把这些内存改回去,于是询问次数也被改了回去(比如 https://uoj.ac/submission/441773 )。

至于前面说到的坑,其实是 libc 的 memset 用到了 SSE,这导致询问函数中用到 memset,这份代码就失效了。(但是只要把 SSE 的实现加回来,就没有这个问题了)

可能的防范方法

  • 让交互器变得 adaptive(比如 https://uoj.ac/problem/486 )。不过这并不意味着完全防住了本方法。比如也许可以在最开始进行若干次随机询问,使得数据固定,之后再使用本方法。

  • 算询问次数使用一些累加之外的手段,比如第 $i$ 次询问把 $a[i]$ 设为 $1$。这样做可以防住只在最后把内存改回去(因为中间询问改了哪是完全不知道的),但是不能防范每次都暴力模拟。

  • 在 grader 中使用各种奇怪的指令集。治标不治本。

  • 使用 IO 交互。

  • 让代码段不可读取。其实我不太清楚这样会不会影响程序运行,有机会的话可以试试。不过这样搞的话,评测机那边可能也需要相应做出一些调整。

  • 不在网络赛出这样的交互题。线下赛应该不可能有人背的住这样的板子。

12.07 更新:修了个 bug,改了改 api,可以见 github,也可以见 https://uoj.ac/submission/441827

评论

YuHaoXiang
IO 交互 txdy!
EtaoinWu
可以想个办法让交互库跑在内核态...?不过这样要对评测机os做duck.ac级别的修改了
immortalCO
如果交互库每被调用若干次就会随机重置内存布局(比如交互库变量全放在一个 struct 里,定期把所有数组和变量都移动到新的内存上),可以防住这个 hack 吗?比如如果 struct 很大,至少可以卡 MLE 之类?

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。