谷甚论Hack交互库（上篇）——搜索关键变量
鏡音リン
2020-06-09 21:13:36
# 谷甚论Hack交互库（上篇）——搜索关键变量
## 零 写在前面
**在练习或比赛中通过Hack交互库获得AC属于作弊行为。** 恶意Hack交互库是违反洛谷社区规则的。本文所讲述内容仅供学习交流使用。
**用Hack交互库的方法能过题仅仅属于侥幸。** 本文介绍了一种方法，并不代表它是能用来通过大部分的交互题的通用方法。这种Hack其实很容易防御。
本文所附带代码仅仅在写本文时可以通过对应题目。如果交互库有更新，这些代码可能会失效。同时因为上一条的原因，这种方法随时可能失效。
Hack交互库的方法很多，本篇是上篇，仅介绍其中一种。下篇会讲解其他的方法（其实是一篇杂谈）↓
[谷甚论Hack交互库（下篇）——杂谈](https://www.luogu.com.cn/blog/nederland/how-to-hack-interactive-lib-2)
## 一 什么是交互题？
```
交互题既用户提交的程序，通过出题人提供的交互库，与判题程序（SPJ）进行交互并获得输入、解答问题。
```
——引自[洛谷官方博客《交互题功能说明》](https://www.luogu.com.cn/blog/luogu/interactive-problems)
交互库的实现可以分为两种：**函数交互**和**IO交互**。
- **函数交互**是将你提交的代码和交互库代码**一起编译成一个程序**，你可以调用交互库中的函数，交互库也可以调用你实现的函数。你的代码和交互库代码在同一个程序中运行，共享内存、运行时间等。
- **IO交互分别编译你的代码和交互库代码，两个程序**通过标准输入流的重定向交换数据。这两个程序的内存是独立的。
注意，在洛谷也可以同时使用这两种交互方法。
本文介绍的这种方法用于Hack**函数交互**。（实际上，IO交互通常也很难Hack，相当于你要Hack SPJ）。所以以下只讨论这一种交互方法。
接下来我们以[P1947 猜数](https://www.luogu.com.cn/problem/P1947)为例，介绍搜索关键变量的方法。
## 二 什么是关键变量？
我们所说的关键变量，应该满足以下几点：
- 是交互库所定义的
- 在交互过程中起关键作用
- 有足够明显的特征让我们认出它
所谓搜索关键变量，就是找到这样的变量，通过读取或者修改它来达到我们的目的的一种方法。
那么，我怎么知道交互库都定义了什么变量呢？
如果你有交互库的参考实现，你可以通过阅读其代码来猜测真正的交互库中都定义了什么变量。如果你没有，你可以思考：假如自己来写这个交互库，应该怎么写？从而猜测交互库中都有什么变量。
例子：[P1947交互库的参考实现](https://www.luogu.com.cn/paste/uimmq4nj)
在这份代码中，我们可以看到交互库定义了这几个变量：```n```，```c```，```k```和```cnt```。
其实我们最想找到的变量是```k```。如果我们能读取这个变量，直接返回它就可以AC了。很遗憾的是，这个变量并不满足上面的第三个条件。
只有```cnt```满足这三个条件。它代表了我们调用交互库的次数，并输出给SPJ处理。如果我们能把这个数修改成一个较小的值，那就可以无视交互库的调用次数限制从而用$O(n)$的暴力算法通过此题啦~
所以我们现在的目的很清晰：找到```cnt```，并且修改它。如果你看到这里已经开始迷惑/出现不理解的地方了，不用担心，请继续往下读。
## 三 如何搜索？
前面讲到，函数交互将你提交的代码和交互库代码一起编译成一个程序。由于这两者的代码在不同的文件中，你的代码是无法直接访问交互库定义的变量的。然而，代码无法访问，可不代表程序无法访问。
由于是同一个程序，你的内存和交互库的内存是直接共享的，而C/C++的指针提供了访问任意内存的方法。这里简单介绍一下C++中的内存模型，大致分成三类：
- **全局内存**包括全局变量，和用```static```声明的变量。
- **栈内存**包括函数中声明的局部变量、函数的参数和返回值（有时候）。栈内存的分配是从高向低的。
- **堆内存**是动态分配的内存，如使用```malloc```函数、```new```关键字分配的内存，和一些STL使用的内存。
这只是一个简化的内存模型，实际的实现会更加复杂，也与编译器、运行环境、O2优化等有关。总之，大概有一个原则，就是同类内存放一起。
那么我们看到```cnt```是一个全局变量，应该在全局内存的空间内。我们尝试在全局内存中找到这个变量的地址。那么哪里是全局内存的空间呢？咱也开个全局变量然后它附近的空间就是了。（（（
解决了搜索范围的问题，我们还需要知道搜什么。这就是我们上面说的「明显的特征」的问题了。**变量值随操作的变化是最明显的特征**，其他的如数值范围、数字的性质等也可以作为识别变量的特征。在本例中，每次调用交互函数```cnt```的值就会递增，我们可以依据这一点识别该变量。
重新整理一下我们的思路。
1. 确定全局内存的位置（栈内存/堆内存同理）
2. 使用指针扫描附近适当大小的内存
3. 找到一个满足我们要找的关键变量特征的变量位置
4. 读取或修改这个值
剩下的就是代码问题了，以下为P1947的Hack交互库解法的参考实现。截至本文写作时这份代码可以AC。
```cpp
#define S 1000
extern "C" int Seniorious(int);
int x; // 定义一个全局变量，用来确定全局内存的位置
extern "C" int Chtholly(int n, int c) {
int *i = &x - 500, *rcnt;
int a[S];
for (int j = 0; j < S; j++) {
i++;
a[j] = *i;
}
// 指针i扫描x附近1000个int的内存，把内存的值缓存到数组a里。我们确信cnt就在这块内存里
if (Seniorious(1) == 0) return 1;
// 调用交互库。此时cnt的值已经变化了
i = &x - 500;
for (int j = 0; j < S; j++) {
i++;
if (*i == 1 && a[j] == 0) break;
// 再次扫描内存，寻找一个调用交互库前为0，之后变成1的内存位置。我们可以认为这个位置就是找到的cnt
}
for (int j = 2; j <= n; j++) {
*i = 0; // 每次操作前把cnt设置成0，调用次数限制去他妈
if (Seniorious(j) == 0) return j;
}
}
```
## 四 进阶
例题：[P6541 \[WC2018\]即时战略](https://www.luogu.com.cn/problem/P6541)
和刚才的例题相似，我们仍然可以把交互次数作为关键变量，通过修改它来绕过交互次数限制。但是这个变量不够关键。如果你只会$O(n^2)$的算法，就算调用次数限制限制不了你，也会因为时间复杂度而TLE。
我们大胆猜测，交互库可能定义了一个数组（假定它叫```a```），用来记录每个点是否被发现的状态。我们只需要找到这个数组并把它全改成```true```，就可以快乐AC啦~（实际上，当你打开样例交互库实现的时候发现确实是这样的）
这种比较大的数组通常都是定义在全局内存的，所以我们仍然要在全局内存里找。不过这有点困难，因为我们要查找一个数组的位置。
我们可以先扫描一遍内存，然后维护一个这个数组可能在的位置的列表。每次更新时筛去这个列表中不合法的元素，筛到只剩一个时就算找到了。（如果筛到最后一个都不剩，说明你失败了）
伪代码：
```
list<some_type*> b;
扫描内存，把所有符合a的初始状态的位置加入b
while (b.size() > 1) {
随机探索，设这次修改把a[z]变成了v
foreach (x in b) {
if (x[z] != v) {
remove x from b
}
}
}
a = b.front()
```
另外，如果你不知道扫描内存应该扫多大范围，你可以捕获段错误然后无脑扫描到出现段错误为止。本文的下篇有讲这个内容。[链接](https://www.luogu.com.cn/blog/nederland/how-to-hack-interactive-lib-2)
题外话：Hack了一晚上终于A了，感觉踩交互库比正解都难写（）于是就成为了本题最快+最短AC代码（（（（（
## Extra 练习题（Hack交互库这种东西真的有练习的必要么）
这种东西就没啥推荐题目了（）可以去洛谷主题库里找一些函数交互题来做。
在尝试做这些练习题之前，请谨记本文「写在前面」一节中的内容。