📝

バイト列が文字列として解釈できるかどうか

2021/04/09に公開

概要

https://qiita.com/heeroo_ymsw/items/c6e15d5f9246b4e842eb

という記事に関連して、kazuhoさんが投げかけた疑問

https://twitter.com/kazuho/status/1378498723936829441?s=20

について考えた以下のTweetについての解説をする。

https://twitter.com/yoichi22/status/1378503149086904321?s=20

ここで考える問題

任意のファイルのコンテンツ、つまりバイト列が与えられた時に、それがあるエンコーディング規則(例えばUTF-8)で文字列として解釈でき、それとは異なるエンコーディング規則(例えばShift_JIS)で文字列として解釈できないことを証明できるか?という問題について考える。

文字列とバイト列

まず、エンコーディング規則を何か一つ選んだ場合に、バイト列を文字列として解釈できるかどうか?について考えてみよう。

文字列をエンコーディング規則に沿ってエンコードするとバイト列が得られる。
言い換えると、エンコーディング規則は、文字列の集合から、バイト列全体の部分集合への写像である。

バイト列が与えられた時、そのバイト列が文字列として解釈できるか?は、対象バイト列がその写像の(エンコードされた文字列の集合)に含まれているかどうか?で判定できる。

2つのエンコーディングの場合

2つのエンコーディング encode1 と encode2 を考える。

前節の説明により、encode1の像Y1、encode2の像Y2はそれぞれ

  • Y1: encode1 で文字列と解釈できるバイト列の集合
  • Y2: encode2 で文字列と解釈できるバイト列の集合

なので、バイト列yは以下のいずれかにあてはまる

  • y \in Y1 \cap Y2 ⇒ encode1 でも encode2 でも文字列と解釈できる
  • y \in Y1 \cap \overline{Y2} ⇒ encode1 では文字列と解釈できるが、encode2 では文字列と解釈できない
  • y \in \overline{Y1} \cap Y2 ⇒ encode1 では文字列と解釈できないが、encode2 では文字列と解釈できる
  • y \in \overline{Y1} \cap \overline{Y2} ⇒ encode1 でも encode2 でも文字列と解釈できない

UTF-8とShift_JIS

2つのエンコーディングとしてUTF-8Shift_JISを選んだ場合、それぞれの定義域と像は以下の図のようになる。

UTF-8でもShift_JISでも文字列と解釈できるバイト列

ASCIIの英数はUTF-8でもShift_JISでも扱いが同じであり、ASCII英数のみからなる文字列をエンコードしたバイト列はUTF-8でもShift_JISでも文字列と解釈できる。

それ以外でも、例えば「コメンメ」という文字列をUTF-8でエンコードした場合、「e382b3(=コ)e383a1(=メ)e383b3(=ン)e383a1(=メ)」というバイト列になる。

$ echo -n コメンメ|xxd
00000000: e382 b3e3 83a1 e383 b3e3 83a1            ............

一方で「繧ウ繝。繝ウ繝。」という文字列を Shift_JIS でエンコードするとやはり「e382(=繧)b3(=ウ)e383(=繝)a1(=。)e383(=繝)b3(=ウ)e383(=繝)a1(=。)」と、全く同じバイト列になる。

したがって、「コメンメ」をUTF-8エンコードしたバイト列をコンテンツとするファイルは、UTF-8でも解釈できるし、Shift_JISでも解釈できる。ただしUTF-8で解釈した文字列とShift_JISで解釈した文字列は異なっており、それぞれ「コメンメ」、「繧ウ繝。繝ウ繝。」と似ても似つかない文字列である。

UTF-8では文字列と解釈できるが、Shift_JISでは文字列と解釈できないバイト列

例えば「コメント」という文字列をUTF-8でエンコードしたバイト列はこれに該当する。

echo -n コメント|xxd
00000000: e382 b3e3 83a1 e383 b3e3 8388            ............

先頭からShift_JISで解釈しようとすると、「e382(=繧)b3(=ウ)e383(=繝)a1(=。)e383(=繝)b3(=ウ)e383(=繝)」までは行けるが、最後に0x88が残り、0x88はShift_JISでは2バイト文字の第1バイトなので、最後までShift_JISで解釈することができない。

したがって、「コメント」をUTF-8エンコードしたバイト列をコンテンツとするファイルは、UTF-8では文字列として解釈できるが、Shift_JISでは文字列として解釈できない。

任意のエンコーディングの中では

前節では2つのエンコーディングのみを考えていた。ここで、対象とするエンコーディング規則の集合を広げて、「特定のエンコーディング規則(例えばUTF-8)のみで文字列として解釈できるバイト列を作れるか?」という問いを考えてみよう。つまり、「文字コード判定を行うと必ず特定のエンコーディングと判定されるようなファイルを作れるか?」という問題。

そのバイト列を文字列として解釈できる何かしらのエンコーディング規則を作れば反例となるため、「そんなバイト列はない」が答えになる。

クライアントから「文字コードがUTF-8としか判定されないもの」を求められていた場合、納品した成果物に対して反例を出されてしまうと費用回収できないので注意しよう。

参考文献

以前書いた記事。

https://qiita.com/yoichi22/items/03198925275d072b7d3f

Discussion