上周四、五给BCTF 2016出了两道题。

Misc类型。向解出此题的48支队伍表达祝贺。

选手连接服务器的指定TCP端口后，服务器会要求proof of work：给出challenge，求出使得sha256(challenge+x)前若干bits为0的x。之后即进入到bash交互界面。不难发现里面没有shell utilities，常用命令都没有。下面用0指代服务器IP。

其中输入命令在输出中重复了。如果hexdump流量，可以发现换行符使用\r\n。

Pseudoterminal

Interactive模式下$-包含i。

以上迹象都说明服务端很可能使用了pseudoterminal。考虑用socat stdio,raw,echo=0 tcp:0:2222代替nc 0 2222连接服务端。使用文件名补全可以发现flag文件/home/ctf/flag.ray：

另外也可以用文件名通配符找出flag文件：

没有cat等shell utilities，可以考虑用bash内置的读文件命令，如read /home/ctf.ray、mapfile a < /home/ctf.ray命令，另外可以set -v后source /home/ctf/flag.ray。但这些都不奏效，并且可以发现<重定向不可用。

之后有至少三个方法读取flag：

• bash -v /home/ctf/flag.ray
• history -r /home/ctf/flag.ray; history

ctypes.sh

另一个比较复杂。补全还能显示内置命令，其中多了dlopen、dlcall等非bash自带的命令。另外通过补全查看/usr/lib/下的文件：

libffi.so很可疑，也从另一方面佐证了这个bash做过手脚。dlopen和dlcall等来自fqj1994提到的ctypes.sh，这个项目给bash提供了foreign function interface，可以加载动态链接库，执行其中的函数。因此读取flag的方式很自然：

另外，help和set命令也可以列出dlopen和dlopen命令。

不用终端提供的补全功能也可以列目录：

PPP(Plaid Parliament of Pwning)用了ctypes.sh提供的callback，使用ftw遍历目录：

出题时没有想到history -r /home/ctf/flag.ray; history和bash -v /home/ctf/flag.ray也可以读文件……一方面是太仓促了。治牙搬家搞了很久，一边kelwin一直在催题，周四最后就没剩下多少时间，仓促地patch了bash源码builtins/目录下mapfile.def、source.def、read.def等，本来也想过是不是应该统一地把libc.so中open整个LD_PRELOAD了，似乎有些麻烦就没做。好吧，也不愿意在出题上浪费太多时间。

BetaFour

PPC(Professional Programming and Coding)类型。向解出此题的19支队伍表达祝贺。

选手连接服务器的指定TCP端口后，服务器会要求proof of work，之后可以发现是10局12x12的四子棋，每局胜2分平1分负0分，积14分或以上即可获得flag。服务端每一步思考0.3秒(CPU time)，选手每一步要在4秒内给出。

AI代码来自2013年春季学期清华大学计算机科学与技术系人工智能课的大作业。开赛两天前kelwin说和BrieflyX商量了下可以出一题，正好与几天前的AlphaGo与李世乭5盘围棋的时事关联。我说可以尝试改一下之前大作业的代码。当时看了https://chessprogramming.wikispaces.com/一些资料，苦于实现似乎并不容易……当时询问了几个学长，一致推荐Monte Carlo tree search，后来我们这届计算机系同学似乎好多都用了这个方法。课程作业没有提供Online Judge，如何保证交作业时代码能在助教的Windows Visual Studio上编译通过很痛苦，一不小心就有0分危险。本想把bitboard改成AVX2的256位integer，苦于服务器是Ivy Bridge不支持。似乎扯远了。

服务端每一步都用clock_gettime(CLOCK_THREAD_CPUTIME_ID)计时占足0.3秒CPU time，假设选手1秒(其中含网络延时，延时越大CPU负担越小)下一步，那么(1+0.3)/0.3~=4.33个连接就能达到单核心100%占用。当时感觉CPU资源消耗太大，因此后来又加了proof of work，但依然忧心忡忡。

我们的服务在Google Compute Engine上，它的网络有些问题，刚close的socket之前若紧接write错误消息，此时若对端也有并发发送来的消息，close很可能不会转化为正常情况下的TCP FIN，而会是TCP RST，并且write的错误消息客户端也无法收到。而连接localhost则正常。

解决BetaFour的一种方法是实现一个更强的AI。另一种思路则是左右互搏。

AlphaGo的训练用到了self-play给予本题启示。BetaFour的10局棋，选手交替执先，因此也可以考虑左右互搏，创建两个连接A和B。连接B先随便下一局(输)，之后服务端执先，读取着法后发送给连接A；连接A服务端走子之后把着法发给连接B，如此交替。若一边输则另一边赢。下完模仿的9局后，A再随便下一局(输)。除去A和B随便下的，两个连接的得分和为18，有一定机率会大于等于14，从而得到flag。

代码参见https://github.com/MaskRay/BCTF-2016-hsab-and-BetaFour/blob/master/BetaFour/self-play.py。

服务端AI简述

Monte Carlo Tree Search把博弈树搜索和随机算法结合了起来，domain-specific knowledge是可选的，这意味着无需像minimax那样实现一个对未结束局面估价的函数。

每一回合程序建立一个根节点表示当前局面。每个节点连向孩子的边代表处于该节点表示的局面下可以选择的着法，而相应的孩子就是选择该着法后转移到的局面。树一开始只包含根节点，在之后的expansion过程中节点会被添加到树中。

然后执行若干次迭代过程，每次迭代都会依次执行selection、expansion、simulation和backpropagation四个过程。

• Selection。从根出发，根据tree policy走到一个孩子节点，重复此过程直到碰到一个可扩展的节点为止。
  可扩展的节点指的是带有未访问孩子的节点。
• Expansion。此时我们已经走到了一个可扩展节点。根据tree policy选择未探索过的着法中最有探索价值的，给当前节点添加一个孩子并走到这个孩子节点。
• Simulation。根据default policy在当前节点表示棋盘下模拟双方对弈。
• Backpropagation。根据对弈的结果更新当前节点及其所有祖先的统计信息。

MCTS是这一类算法的统称，通过选取适当的tree policy和default policy就得到了一系列具体算法。对于tree policy，我使用了Upper Confidence Bounds for Trees(UCT)算法，根据公式：

$$
UCT_j = X_j + 2C\sqrt{\frac{2\ln{n}}{n_j}}
$$

来选择具有最大$UCT$值的孩子节点$j$。其中$X_j\in [0, 1]$，是根据统计信息计算出来的表示对应着法是否优秀的量。$n$为当前节点的访问数，$n_j$为孩子节点$j$的访问数，$C$为一个大于0的常数。

公式中第一个加数表示孩子节点的优秀程度(exploitation)，第二个加数表示探索度(exploration)。

• Exploitation高代表选择该孩子节点对应的着法，模拟对弈的结果中有利局面多，所以该孩子节点对应的着法较为优秀。
• Exploration高代表选择该孩子节点对应的着法的尝试次数不够多(因为$n_j$在分母中)，需要进一步探索。

移植时删除了大作业中一些优化。

需要处理的最大棋盘规模为$12\times 12$，可以用一个uint64_t表示四列，那么12列就只需要3个uint64\_t来表示，可以看作一个uint192_t，其各个二进制位对应的棋盘上位置如下：

对于胜负的判定，只需要用移位操作和与运算即可在在$O(1)$时间内求出。比如要判断白棋在竖直方向上是否连成四子，只需要取出其位棋盘$w$，判断\texttt{w \& w>>1 \& w>>2 \& w>>3}，类似地可以判断水平方向、斜线方向上是否连成四子。

另外每一列的高度也可用位运算快速求出，以加速生成候选着法。对于每一列，计算二进制表示里从下到上连续的1的个数，这个通过加1后计算前导0可以算出。

省略父节点指针

父节点指针仅用于backpropagation过程，而在selection阶段下溯时若记录沿路节点，则可得到backpropation需要的祖先节点信息。

题目服务准备

Linux container的文件系统镜像

我下载Alpine Linux的二进制包http://dl-3.alpinelinux.org/alpine/edge/main/x86_64/，只安装必要依赖，以为了创建尽可能小的文件系统镜像。

编译链接时生成position-independent executable。

malloc相关的一些环境变量如MALLOC_CHECK_等。

Resource limits如RLIMIT_NPROC设为0可以阻止该用户创建新进程；RLIMIT_CPU限制CPU time；RLIMIT_FSIZE限制创建文件的最大长度；RLIMIT_DATA限制进程data segment大小。

seccomp限制系统调用，可以考虑使用白名单，阻止一些可能的恶意行为，比如创建进程、写文件、kill/stop服务进程。

prctl PR_SET_SECUREBITS PR_SET_DUMPABLE PR_SET_NO_NEWPRIVS比较复杂。

unshare隔离各类namespace。

对于小型rootfs，感觉最有必要的只有resource limits和seccomp。

#bctf@freenode，把自己配置成了一个autoop和proxy bot，转发选手的问题……znc的autoop模块可以用于自动给加入channel的nick添加op。

https://github.com/MaskRay/BCTF-2016-hsab-and-BetaFour

希望用上Proof of Work as a Service和Captcha as a Service。

如果有更多时间的话，想给BetaFour加上录像，first blood时可以播放下视频，提升展示效果。其他很多服务因为私密性不方便这么做，但Connect Four这么搞还是不错的呢。

比赛承办方人工成本太高了，而收益为零。