文字の検査を全部通っても、図の並べ方から答えが漏れる
Passing every text check, the answer still leaked through the figure's layout
D11-4-T22-leak-through-figure-layout・技術・日本語入力でプレイする仕組み
まだ言ってはいけない答えを、画面の文が先に言っていないか。それは機械で調べています。
ところが、文字を一つも使わずに、点を二つ並べるだけで答えを教える図が描けてしまう。その穴の名前は二つありました。
『霧走町 流氷に眠る』には、手帳に入った証言や物を並べ直して見せる「事件の図」があります。
今夜は、その図を作るときに踏みかけた漏れの話です。
文字の検査は全部緑のまま、図の座標が答えを語る。
監視していない経路を通る漏れ、という意味で、暗号の世界の言葉を借りました。
この回の位置と、前後の回#
区切り: T03〜T24 日本語入力を解いて返すまで（22 回のうち 20 回目）
先に読むとよい回: T21（出所つきの手帳）
次に読む回: T23（同じ入力に同じ出力）
名前 — side channel#
- 正式名
- side channel（サイドチャネル）と、Illusion of Causality in Visualized Data（論文の題）
- 略称
- side channel attack は SCA と略されることがある
- 日本語
- サイドチャネル、サイドチャネル攻撃。後者は「可視化されたデータの因果の錯覚」くらいの意味
- 初出・代表
- side channel の代表例は Kocher, "Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems"（CRYPTO '96）。語の初出ではありません。可視化の側は Xiong, Shapiro, Hullman & Franconeri, "Illusion of Causality in Visualized Data"（IEEE VIS 2019。TVCG の巻としては 2020 年とする記録もある）
検索の注意が一つあります。
"illusion of causality" だけで検索すると、心理学の「因果の錯覚」の研究がたくさん出てきます。偶然の一致から因果を感じてしまう、人の判断の研究です。
図の並置の話にたどり着くには、論文の題をそのまま "Illusion of Causality in Visualized Data" で引くのが確実です。
side channel とは#
暗号の実装は、数学としては安全でも、動いている機械から秘密が漏れることがあります。
Kocher（1996）は、秘密鍵の演算にかかる時間を測るだけで、Diffie-Hellman の固定の指数を見つけたり、RSA の鍵を因数分解したりできる場合があることを示しました。
多くの場合、知られた暗号文だけで足り、計算も安い。
その後、消費電力・電磁波・キャッシュの当たり外れ・音と、漏れる経路は次々に見つかっています。
共通しているのは構図です。
安全性を考えるとき、私たちは「入力と出力」という正規の経路だけを見ています。
秘密は、その外側の、見ていない経路から出ていく。
だから正規の経路をどれだけ厳しく検査しても、気づけません。
対策も構図で分けられます。
一つは経路の情報量を消すこと。秘密によらず同じ時間で終わる定数時間の実装（constant-time）がその代表です。
もう一つは、漏れたものを無意味にすること。値に乱数を混ぜるマスキングなどです。
いちばん強いのは、経路そのものを作らないことです。
よく知られた弱点は、経路の数え上げが終わらないことです。
新しい経路は、たいてい「そこから漏れるとは思っていなかった」所に見つかります。
Illusion of Causality in Visualized Data とは#
Xiong らは、同じ相関のデータを、文章・棒グラフ・折れ線・散布図など見せ方を変えて人に示し、どれくらい「因果がある」と読まれるかを測りました。
クラウドソーシングの実験を 3 つ。
相関の強さは正しく読めている人でも、因果を感じてしまう。
因果の評価が高かったのは文章と棒グラフで、散布図では弱かった。
データを集約して見せるほど、因果と読まれやすかった。
棒よりも、線や点で描いた方が因果と読まれた、という結果も出ています。
可視化の分野では、これは「誤った読みを防ぐ」文脈で語られます。
相関しかないのに、図が因果を言ってしまう危険です。
後の研究では、図の種類を変えるだけでは避けきれない、という報告もあります。
うちの文字の検査（L19）#
先に、文の側の守りです。
作品データには insights.json という宣言があり、推理の「鍵となる結合」を書いておきます。
今日の版で、鍵となる結合は 5 件、仮説の転換点は 2 件です（中身は第一章の決着に関わるので写しません）。
一つの結合は、観察の事実の語群（a 群）と、結論の側の語群（b 群）と、その結合が成り立ったことを表すフラグでできています。
lint の L19 は、そのフラグが立つ前に読める文に、a 群と b 群の語が同時に出ていないかを見ます。
出ていたら、その文はプレイヤーの代わりに推理してしまっている、という判定です。
adv-sim の main.cpp から、本文の検査の芯を写します。
auto CheckBlock = [&](const char* Label, const std::string& Owner,
const std::string& Text, const Insight& In)
{
if (Text.empty()) { return; }
const std::vector<char32_t> Hay = NormalizeText(Text);
if (HitAny(Hay, In.a) && HitAny(Hay, In.b))
{
std::printf("L19: %s %s: %s の結合語（a群とb群）が %s 成立前に同時出現\n",
Owner.c_str(), Label, In.id.c_str(), In.flag.c_str());
++Errors;
}
};
語は、入力の照合と同じ正規化（norm/1）を通してから、部分一致で探します。
対象は段の台本・言い直し・手帳の一文など、プレイヤーが読める文です。
そのフラグを前提（requires）か結果（sets）に持つ段は「成立した後にしか読めない」ので外します。
意図の言い換え（paraphrases）はプレイヤーが言う側の文なので、検査しません。
この検査は、文字の上では十分に厳しく働きます。
ただ、見ているのは文字だけです。
文字を一つも使わずに、答えを言う#
図を設計していたとき（8 月 28 日）に、この検査の外側に穴があると気づきました。
一般の例で書きます（作品の実データではありません）。
時刻の目盛りを持った図を描くとします。
Aさんが店を出た時刻を、目盛りの上に点で置く。
被害者が亡くなったと見られる時間帯を、同じ目盛りの上に帯で描く。
ラベルは「Aさん」と「被害者」だけで足ります。
決め手の語は、どちらも画面に一つも出ていない。
だから L19 は何事もなく通ります。
でも、絵ははっきり言っています。
Aさんが出た直後の時間帯に、事件が起きた、と。
重なり、前後、距離が、語の代わりに結合を語ってしまう。
構図は side channel と同じです。
監視している経路は文字で、図の座標はその外を通る。
そして読む側の頭の働きが、Xiong らの論文の現象です。
並べて置かれただけの二つから、人は関係を読み取る。
二つを合わせると、一文になります。
数値の軸を持つ図は、語を一つも出さずに結合を教える。
対処: 経路を塞ぐのではなく、作らない#
設計で考えた対処は三つでした。
- 数値の軸を持つ図を採らない。座標に意味が無ければ、幾何は何も語らない。
- 図に同時に見える全部のラベル（点と辺）を連結して、L19 に通す（設計の名前は C6）。
- 名前を伏せた点を図に置かない（C7）。伏せ字の点があると「そこに誰かが入る」という数の情報が漏れる。
位置の漏れそのものに効くのは 1 だけです。2 と 3 は、文と同じ種類の漏れに効きます。
side channel の対策で言えば、1 は経路を作らないこと、2 は経路の情報を正規の経路の検査に引き戻すことです。
採った図と、採らなかった図です。
今日の版の図は 7 つの見え方を持っています。
- 町（場所ごとに、そこで分かったことをぶら下げる）
- 人（誰から何を聞いたか）
- 見たこと（人に聞かずに分かったこと）
- 物（何について分かったことか）
- 足取り（どこへ行って戻ったか。横が手順の順、縦が場所）
- 筋道（何が何を開けたか。依存の深さで積む）
- 相関（証言の話者と、その証言が挙げたものを結ぶ）
時刻の目盛りで並べる時系列は、封印しました。
町の地図も採っていません。場所の隣り合いがデータに無く、事件の骨格でもないからです。
クリアに要るものだけを骨組みにした図も採りませんでした。一つ落とすと進めない所が目立ち、それ自体が攻略情報になります。
図の点を押すと、詳しい説明が出ます。
開くのは同時に一つだけです。
点ごとに開く・閉じるを別々に持たせると、開き方の組み合わせは 2 の N 乗になります。点が 10 なら 1,024 通り。
一つずつなら「何も開いていない」と「どれか一つ」の N＋1 通りで、全部の状態で同時に見える文を並べられます。
これも、検査を回せる大きさに状態を保つための決まりです。
もう一つの対処: 図を見せる時期#
10 月 9 日に、もう一段強い決まりを足しました。
事件の図は、章の決着のあとにだけ見せる。
遊んでいる最中は、図の画面に案内の一行だけを出す。
体験版の試遊で、図から先の展開が分かってしまったことがあったからです。
図の種類を選んでも、図があること自体が、何が大事かを語りうる。
それなら、推理している間は図を見せない。図は振り返りの道具にする。
章ごとの図は、その章までに立ちうるフラグの手掛かりだけで組みます。
「立ちうる」の計算は Scripts/lib/adv-derive.mjs の chapterFlags です。
export function chapterFlags(D, n) {
const avail = new Set();
for (const [, ps] of D.producers) for (const p of ps) for (const x of p.need) if (!D.producers.has(x)) avail.add(x);
for (let ch = 1; ch <= n; ch++) {
for (let grew = true; grew;) {
grew = false;
for (const [f, ps] of D.producers) {
if (avail.has(f)) continue;
if (ps.some((p) => (!p.phase.length || p.phase.includes(ch)) && p.need.every((x) => avail.has(x)))) { avail.add(f); grew = true; }
}
}
}
return avail;
}
フラグを立てうる手（段・場所の入場・出来事）を producers に集め、章を 1 から順に進めます。
その章で動く手のうち、前提が全部そろったものが立てるフラグを、増えなくなるまで足す。
前提に出てくるのに誰も立てないフラグは、初めから立っているとみなします。
不動点まで回す、素朴な到達可能性の計算です。
今日の版で数えると、手掛かりのフラグは全三章で 102。
第 1 章までに立ちうるのは 35、第 2 章までが 65、第 3 章までで 102 でした。
第一章の図には、この 35 だけが載ります。
どの図を開くかは、画面の側が決めます。UE の SKaedeAdvShell.cpp から写します。
for (const std::string& F : Session->data().work.clearFlags) { if (St.flags.count(F) > 0) { bCleared = true; break; } }
if (bCleared) { Name = TEXT("case-figure-") + CaseFigureView; }
for (int32 N = St.phase - 1; !bCleared && N >= 1 && Name.IsEmpty(); --N)
{
const FString Cand = FString::Printf(TEXT("case-figure-%s-ch%d"), *CaseFigureView, N);
if (FigureCache.Find(Cand) || !ResolveUiScreen(Cand).IsEmpty()) { Name = Cand; }
}
if (Name.IsEmpty()) { Name = TEXT("case-figure-locked"); }
作品をクリアしていれば全体の図。
そうでなければ、いまの章の一つ前から下へ探し、決着した最後の章の図。
どれも無ければ、案内の画面です。
ブラウザ版も同じ規則で、規則を変えるときは両方を直す約束にしています。
さらに引っかかりの検査の C-02 が、章ごとの図に、その章までの手帳に出てこない人の名前が入っていないかを見ます。
後の章の名前が図に紛れ込む事故を、人物単位で落とす検査です。
名前どおりでない所 — side channel#
side channel は、ふつうは攻撃者が意図して秘密を抜く話です。
うちの「攻撃者」はプレイヤー自身の推理で、抜こうとしていません。図を見れば、自然に読めてしまうだけです。
借りたのは「監視している経路の外を通る漏れ」という構図で、攻撃のモデルではありません。
設計の文書では「位置の side channel」と呼んでいます。
Illusion of Causality in Visualized Data は、相関しかないのに因果と読まれる誤りの研究です。
うちで起きるのは逆で、正しい結合が、プレイヤーが自分で気づく前に読めてしまうことです。
誤りの錯覚ではなく、正しい答えの先出し。
並置から関係を読むという頭の働きが同じなので、名前を借りました。向きが逆なことは、借りるときに書いておく約束です。
弱点と、採らなかった案 — side channel#
いちばんの弱点は、位置の漏れを機械で見ていないことです。
文字は連結すれば数えられますが、座標に意味があるかは、図の種類を選ぶ段階で人が決めています。
数値の軸を足したくなったときの手順（作品の設定に宣言と理由を書き、決め手が図に乗っていないことを人が確かめた記録を残す）は設計に書きましたが、宣言と記録でしか守れない、弱い守りです。
もう一つ、正直に書きます。
設計で決めた C6（図のラベルを連結して L19 に通す）と C7（伏せ字の点を禁じる）は、今日のソースを探しても実装が見つかりませんでした。
いま図の文を守っているのは、図を章の決着の後にしか見せないことと、C-02 です。
その C-02 にも穴があります。
章ごとの図は生成物で、git に入れていません。
今日この作業コピーで回すと C02=0 でしたが、ここには章ごとの図が一枚も無いので、何も見ずに 0 件です。
配る前の工程では図を作り直してから C-02 を回すので、本番の経路では空振りしません。
けれど、検査が緑であることと、検査が何かを見たことは別です。対象が無いときに失敗する作りにはなっていません。
足取りの図は、横の軸が手順の順になっています。
時刻の目盛りではありませんが、順序の軸ではあります。
章の決着の後にしか見せないので、推理の最中の漏れにはなりません。
採らなかった案です。
- 図にも L19 と同じ語の検査をかけて、図はいつでも見せる。語の漏れは塞げますが、位置の漏れは残ります。
- 時刻の目盛りを残し、点を少しずらして近さを消す。ずらし方そのものが作り手の意図を語ります。
- クリアに要る手掛かりだけに絞って、図をすっきりさせる。絞った時点で「どれが要るか」が漏れます。
- 「全部で何件のうち何件」と分母を出す。残りの数が分かります。
検査を厳しくするより、経路を作らない方が強い。
暗号の人たちが何十年も前に通った道を、図の設計で辿り直しました。
検索語#
side channel attack
Illusion of Causality in Visualized Data
timing attacks Kocher
correlation causation visualization
第一章を解き終えると、その章の図が開きます。ブラウザで入力して最後まで解いてみてください。プロフィールのリンクから遊べます。