HackThisSite - Programming Mission 4

Posted on Edited on In Views: Disqus:

Challenge

Level 4 — Parse an XML file

随机生成的 XML 描述若干 Line（XStart/XEnd/YStart/YEnd）与 Arc（XCenter/YCenter/Radius/ArcStart/ArcExtend）， 可选 Color（blue/green/red/yellow，缺省 white）。把这些图元画出来，图上会出现五串字符； 提交格式为 蓝,绿,红,黄,白。限时 120 秒。

状态：未通关（partially verified）。解析、绘制、字形分离、逐字去旋转、字符识别五步都已分别验证可行， 卡在最后一步：字形切分。

Solution

实例是在打开关卡页时生成的，之后才拿得到 XML：

1
2
3
curl -sL -b "$CK" -o /dev/null 'https://www.hackthissite.org/missions/programming/4/'
curl -sL -b "$CK" -o xml.bz2 'https://www.hackthissite.org/missions/prog/4/XML/'
file xml.bz2
1
xml.bz2: bzip2 compressed data, block size = 900k

XML/ 需要带尾斜杠（回去重定向到 /XML/）；如果先直接请求 XML 而不先加载关卡页， 服务端只会返回 1 字节的 body（一个换行），ET.parse 会报 no element found。

XML 解压后是标准的 Line/Arc 图元列表。按颜色分组后绘制，可以得到 instance.png。 关键观察：

  • 字符是矢量笔画画的，字符集是十六进制（0-9A-F）；
  • 同一颜色的字符不是水平排列：它们沿一条（微弯的）基线排布，每个字形自身还带旋转。

第二点是这关的真正难点。参考图 exampleSolution.gif（info.html 提供）里的字符明显沿曲线铺开， 所以整串做一次去旋转、再整串读字的方案必然失败。

用端点/采样点距离做连通性聚类（union_find + cluster(tol=3.0)，见 explore_layout.py）， 可以把图元聚成一个个字形；再把被包住的笔画合并回去（merge_contained），得到字形列表。

对每个字形的中心点拟合一条基线：点数 ≥ 4 时先拟圆（_fit_circle）， 残差足够小就认为基线是圆弧，取该字形所在角位置的切线角；否则退化为直线拟合 + 相邻字形中心连线方向。 然后按 -切线角 反旋该字形自己的笔画，再渲染成位图（bitmap(strokes, rows=26)）。

1
2
cd <hts-workspace>/challenges/hts-prog/4
uv run python read4.py live.xml --rows 12
1
2
3
4
5
6
7
8
9
10
[blue] 2 glyph(s), prims=[6, 4]
-- blue[0] alpha= 43.0 tangent=  +45.8 use=  +43.0 circ=False
   .######..
   ########.
   ##.....##
   ##.....##
   ########.
   ##.....##
   ########.
   .######..

反旋之后字形就转正了，位图打印出来人眼可直接读（上面这个明显是个 B）， alpha/tangent/use 三个角度也让反旋旋了多少可复核。

整串去旋转 + 系统字体模板匹配的路子可以直接排除：

1
整串去旋转 + 系统字体（FreeSans/DejaVu/Liberation）模板匹配 → IoU 只有 0.02–0.16

IoU 这么低说明模板与字形根本不是同一个朝向，而不是字体选错。

把反旋后的位图放大 8 倍、加白边，逐字形打成 #/. 点阵，按字形形状直接读，得到每个颜色的候选串：

1
2
3
4
5
blue   -> B5        (2 glyphs)
green  -> 37F0      (4 glyphs)
red    -> 13CAA27F9C  (10 glyphs)
yellow -> 0C01000   (4 glyphs)
white  -> 9E97301   (3 glyphs)

red 读出 10 个字形，与答案长度吻合；yellow/white 的字形数偏少，切分是剩余的问题。

问题集中在切分：glyphs_of() 在部分颜色上会把相邻字符并成一个字形。 最直观的证据是字形数与答案长度对不上：

1
2
[yellow] 4 glyph(s) ...        # 但答案有 10 个字符
[white]  3 glyph(s) ...        # 答案有 10 个以上字符

也就是说：反旋、渲染这条链本身没问题，问题在于切出来的字形里有时是一个、有时是好几个字符。 下一步应该按笔画间距 / x 投影的间隙做二次切分（而不是只靠连通性），或者让连通性聚类的 tol 自适应字形高度； 切分修好后整条链就是 fetch → 切分 → 逐字反旋 → 读字 → POST，单进程执行完毕，远低于 120 秒。

Vulnerabilities

这关本身没有密码学强度：XML 与绘制规则完全下发给客户端，唯一的门槛是解析 + 图像阅读的工程量。 限时与随机化只抬高了自动化成本；真正的修复是不把可直接推导答案的数据下发到客户端， 或者至少让答案只在服务端可判定。

未通关：解析/绘制/字形分离/逐字去旋转/读字均已验证可行，卡在字形切分