Skip to content

WasmAudit.md

Latest commit

 

History

History
302 lines (236 loc) · 11.4 KB

WasmAudit.md

File metadata and controls

302 lines (236 loc) · 11.4 KB
Raw

Littleman WASM 逆解析・差分監査

調査日: 2026-07-24 UTC
対象: 公式 https://icfpcontest2026.com/littleman.wasm と公式 Web editor bundle
SHA-256: 93e809dd32f91154e65d5b9e556014bc13d03224900d7245ece11ee4b462161b
size: 4,008,775 byte

結論

確認できた重要事項は次の 3 点。

  1. 公開 Language Reference にない Y（runner split）は、WASM 内では完成度の 高い命令として実装されている。register と Backpack を複製し、runner 上限 65,536 まで動作する。問題によっては tick 短縮に使える可能性があるが、 公式仕様に掲載される前の提出利用には規則・互換性上のリスクがある。
  2. 公式 Web runner は WASM の JSON を通常の JSON.parse で読むため、 |value| > 2^53-1 の register、pipe、output を丸める。実測では 16677181699666569 が 16677181699666568 に化け、Web 上の public-test 判定を false fail / false pass にできた。これは Web runner の確認済み 不具合だが、server grader も同じ JavaScript 比較を使う証拠はない。
  3. 文書化済みの算術、floor 除算、剰余、shift、overflow は、境界 test と seed 固定 1,000 件の BigInt 差分 test で不一致 0 件だった。現時点で 算術意味論を利用した score exploit は見つかっていない。

したがって、現時点で score 短縮に直結し得る候補は Y。int64 問題はまず ローカル/Web 判定の信頼性問題であり、server score exploit としては未確認。

調査範囲と安全性

  • 公開配信された WASM、JavaScript bundle、公開 API とローカル実行だけを使用。
  • submission API、private tests、他 team、運営 infrastructure への攻撃は 行っていない。
  • server grader の実装は取得できないため、Web runner と server の一致は 仮定していない。

調査中の 13:41 UTC に WASM が 2cd118c50945c37a2597483200641c1ec1d29f1c00e34d5fca43e7292acc5623 から上記 SHA へ再更新された。size と section 構成は同一。新版へ差し替えた後も 21 regression tests、算術 fuzz 1,000 件、65,536-runner 上限、int64 精度欠落を すべて再検証した。

静的解析

WABT 1.0.37 で section、name section、対象関数を逆アセンブルした。WASM は Go 1.25.7 で build され、次の元 source path が残っている。

littleman/interp/world.go
littleman/interp/ops_register.go
littleman/interp/dispatch.go
littleman/interp/literal.go
littleman/interp/room.go
littleman/interp/display.go
littleman/interp/parse.go
littleman/interp/frame_judge.go
littleman/interp/expect.go
littleman/interp/io.go
littleman/interp/parking.go
littleman/interp/recorder.go
littleman/interp/session_io.go
littleman/interp/systems.go
littleman/editorproto/analysis.go
littleman/editorproto/flow.go
littleman/editorproto/session.go
littleman/cmd/wasm/main.go

binary の概要:

functions: 2,374
code:      0x270c2c byte
data:      0x14da1c byte
name:      0x1259d byte

復元できた主要関数:

dispatchOp
RegOps
parseDisplays / parseRooms / parsePipes / walkPipe
analyzeLiterals / scanRow / scanCol
PipeTransportSystem.Step
IORoomSystem.Step
DisplaySystem.Step
WallSystem.Step
OpDispatchSystem.Step
AdvanceSystem.Step
RunnerCollisionSystem.Step
StepCounterSystem.Step
World.JudgeSettled / judgeFrameCommit
Session.Step / StepN / Back / Reset

World には runner、pipe queue、park/wake heap、frame judge、step/op/time cap の state が独立して存在する。pipe queue には head, count, lastPop, settle, wakeAt があり、block を毎 tick 全探索するだけでなく wake-up 時刻を管理している。

Y split 命令

WASM 内の説明文字列:

split: the runner turns CW and a copy of it (same A, B, and Backpack)
emerges one cell to the CCW side, heading that way; the incoming heading
is lost

確認した動作:

  • 東向きで Y を踏むと original は南、copy は北へ進む。
  • A, B, Backpack は exact に copy される。
  • original と copy は同じ tick の movement で隣 cell へ出る。
  • split 後の runner も再び Y を実行できる。
  • 同じ destination へ進もうとした runner は、移動前の位置に留まって両方 halt する。
  • 最大 runner 数は 65,536。65,537 人目を作ろうとした tick で split-limit fatal になった。

上限 test は衝突しない二分木 room を生成した。depth 16 の 65,536 runners は 正常終了し、depth 17 は次の結果になった。

{
  "sourceCells": 10223733,
  "step": 131104,
  "reason": "split-limit",
  "fatal": {
    "reason": "split-limit",
    "pos": [34, 262143],
    "cell": "Y"
  },
  "runners": 65536
}

score 短縮への使い方

Y の利点は、複数 room と複数 @ を用意せず、計算途中の state を複製して 並列な control path に分けられること。

  • 同じ前処理結果から複数の独立計算を始める。
  • producer/consumer を一つの room 内で分岐させる。
  • 複数 branch の最遅 path までの tick に変換できる計算を並列化する。

ただし footprint-tick では無条件に有利ではない。

  • Y 自体と branch routing が footprint を増やす。
  • score の footprint 部分は max(width,height)^2 なので、二分木を一方向へ 広げると特に不利。
  • 同じ outgoing pipe へ送る runner を増やしても pipe source は 1 cell で、 output は直列化される。
  • 合流を collision に頼ると両 runner が halt する。
  • S の backpressure と pipe capacity は split しても残る。

まず「並列化で減る平均 tick」と「最大辺の二乗増加」を計算し、積が減る場合だけ 使うべきである。

仕様上の扱い

2026-07-24 の Language Reference には Y がない。一方で:

  • validOps() は Y を返す。
  • editor palette も Y を命令として扱う。
  • /split 用 frontend chunk と /api/v1/split/docs client が配信済み。
  • 調査時点で docs API は 404。

Lightning Round 後の公開予定機能が先行配信された可能性が高い。server が現在の 同一 library を使えば受理される可能性は高いが、正式公開前の使用を正当化する 一次資料はない。

int64 JSON 精度欠落

Go interpreter 内部の値は正しい int64。しかし WASM API は snapshot を JSON number として返し、公式 Web bundle は次のように読む。

JSON.parse(wasmResponse)

JavaScript number が exact に表せる整数は ±(2^53-1) まで。次を実測した。

VM が emit した exact value: 16677181699666569
通常の JSON.parse:             16677181699666568
lossless parse:                 16677181699666569

公式 Web runner はさらに String(output[i]) === expected[i] で比較する。この ため、Web public-test runner では:

  • expected 16677181699666569 → 実際は正しいのに fail
  • expected 16677181699666568 → 実際は 1 違うのに pass

となる。A/B/Backpack、pipe values、Display buffer に大きな int64 が出た場合の 表示も丸められる。

local CLI の修正

littleman-runtime.js に lossless JSON 読み込みを追加した。safe integer は 従来通り number、範囲外 integer token は decimal string として保持する。 これにより座標や tick の既存 API を変えず、int64 の比較と表示だけを exact に できる。

この修正後、上記 exact value の local judge は pass、隣接 value は fail。

exploit 評価

Web editor の表示・public-test 判定を騙せることは確認済み。しかし submission で送るのは program source だけであり、最終 score は server grader が決める。 server が Go の []int64 を直接比較するならこの問題は存在しない。したがって、 現時点では score exploit ではなく、Web runner oracle の不正確さとして扱う。

算術・literal 差分 test

境界 test で確認した代表例:

-7 /  3 = -3, remainder  2
 7 / -3 = -3, remainder -2
-7 %  3 =  2
 7 % -3 = -2
B=0 の /: A=0, B=元 dividend
B=0 の %: A=0
1 << 63: -9223372036854775808
1 << 64: 0
-8 >> 64: -1
8 >> -1: 0
MAX_INT64 + 1: MIN_INT64

numeric literal は両方向で int64 に収まるか load 時に検査され、empty literal と spaces-only literal は nop になった。MAX_INT64 の保持も lossless parser 修正後は確認できる。

npm run audit:fuzz は seed 0x1cf02026 で 1,000 ケースを生成し、BigInt reference model と A/B を比較する。今回の結果は mismatch 0。

layout/parser の観察

  • editor の footprint は non-space cell の bounding box: w=maxX-minX+1, h=maxY-minY+1。
  • copy/save/paste は JavaScript の code point 単位だが、WASM parser は non-ASCII を含む行で byte/rune 幅が一致しない。é や emoji を置いた probe は room を認識できなかった。
  • tab は 1 cell として WASM へ入り、踏まなければ load 自体は通る。
  • ただし公式仕様は ASCII grid で、非 ASCII や制御文字に score 上の利点は 確認できない。
  • 壁を完全共有した二つの room を書くと load error ではなく片方だけが room として認識された。二つの実行 room を重ねる手段にはならない。
  • room 外の @ は runner を生成しない。

これらは parser の厳密さに関する差だが、bounding box を短縮しつつ有効な program を増やす exploit にはならなかった。

resource cap

WASM には step-cap, op-cap, time-cap reason が実装されているが、local Web session の通常 load では server 用 cap は設定されない。

単一 runner の loop に stepN(6,000,000) を一度に与えると 6,000,000 tick まで継続した。公式 Web runner の通常 5,000,000 tick は JavaScript loop 側の 上限。問題固有 tickCap と server 内部 cap は public problem metadata / server 設定に依存し、ローカル WASM だけでは再現できない。

候補一覧

候補 再現 score 短縮可能性 判断
未公開 Y で state を複製 確認済み 中〜高 問題別に footprint と tick を計算。正式公開前は risky
Web JSON int64 rounding 確認済み server は不明 local/Web oracle bug。server exploit と主張しない
算術 overflow / floor 差 不一致なし 低 仕様通り
Unicode で幅を偽装 有効 program にならない 低 ASCII 制約内では使えない
room 壁共有 片方が無視される 低 並列 room 圧縮にならない
runner collision の合流 両方 halt 限定的 計算結果を保持した合流には使えない

再現方法

cd littleman-wasm-cli

sha256sum littleman.wasm
npm test
npm run audit
npm run audit:fuzz
npm run audit:deep

audit:deep は約 10.2 million cell の一時 grid を memory 上に作るため、通常の 回帰 test には含めていない。

未確認事項

  • server grader が Web runner と同じ JSON round-trip を使うか。
  • private tests と server 固有 op/time/memory cap。
  • Y の正式公開時刻、最終仕様、既存 submission への version pinning。
  • contest 中の次回 WASM 更新で挙動が変わるか。

重要な submission 候補は WASM SHA、problem JSON、source、local test 結果を 一緒に保存し、WASM 更新後に再実行すること。