ククログ

回帰テストの対象は適切に設定しよう

先日、Bug 1541748 - New tab and restored tab notified via tabs.onCreated can have invalid (too large) index という報告をFirefoxのバグトラッキングシステムに行った結果、提出したパッチがFirefox 68に反映される事になりました。

とはいえ、実はこのパッチで追加されるコードは皆さんのお手元にインストールされるFirefoxには反映されません。何故なら、これは自動テストを追加するだけのパッチだからです。

パッチが投入されるまでの経緯

この報告は、「Firefoxのアドオン開発に使用するWebExtensionsのいくつかのAPIにおいて、タブの位置を示すindexというプロパティが不正な値になる場合がある」という物でした。ただ、これは実はWebExtensions APIの実装の問題ではなく、Firefoxのタブが内部的に持っている対応する情報自体が壊れていたというのが真相でした。

「根本的な原因」の方は Bug 1504775 - Index is wrong for restored tabs という別のBugで取り扱われていました。今回の報告と前後してそちらのBugの作業が進行していたため、そちらの方で修正が行われた事の影響として、報告からあまり間を置かずにWebExtensions APIの不具合も自然解消したという状況になっていました。

一般的に、このような「ある報告の原因が別の報告の修正で解消された」というようなケースでは、その旨を記して修正済み扱いとしたり、もしくは重複する報告であるとして処理する事が多いです。

このような場合、そちら側に提出されたパッチはBugのクローズに伴って破棄されがちです。しかし今回はそうではなく、Bugはクローズされずに留め置かれ、新たに自動テストを加えるだけのパッチを追加投入する事が承認されました。

これは、根本原因の方のBugがFirefox内部の問題のみを取り扱う物であったのに対し、こちらで報告したBugはアドオンという外部アプリケーションに対する互換性の問題を取り扱っていたからです。

テストは目的ごとに必要

根本原因が修正されたパッチでは、Firefox内部のAPIに対するテストケースは追加されていますが、WebExtensionsのテストケースには特に変更は加えられていませんでした。

今回はFirefoxがたまたま「タブの内部的なindexがそのままWebExtensions APIを通じてアドオンに露出する」という実装を取っていたために、WebExtensions API側の問題も偶然解消されました。しかし、それはあくまで現時点の実装がそうであったからというだけで、将来に渡ってそうであるという事の保証はどこにもありません。

よって、今後Firefox内部の実装やWebExtensions APIの実装が変更された場合に、人知れず再び同じ問題が起こるようになるという可能性は依然としてあります。

そのため、今回のパッチでWebExtensions APIのレイヤにおいて後退バグ*1が発生していないかを検出するための回帰テスト*2を追加することで、WebExtensions APIに意図せず影響を与えてしまう（そのような変更が気付かれずに投入されてしまう）という事故の発生を未然に防ぎ、APIの安定性を保証しやすくしたという事になります。

気をつけて欲しいのは、これは「単体テストと結合テストではレイヤが違うので、単体テストで検証済みの事もすべて結合テストで再検証しよう」という話ではない、という事です。同じ事を保証するテストがそれぞれの実装レイヤに含まれるという事はあり得ますが、それはあくまで結果的にそうなっているだけに過ぎません。テストは誰に対して何を保証するか、という観点で整備される事が重要です。

今回は「Firefox内部向け」と「アドオンという外部アプリケーション向け」のそれぞれで修正・互換性を保証する必要があったためにこうなったわけです。

まとめ

Firefoxに投入された自動テストのみのパッチの背景説明を通じて、テストの目的とテストを追加するかどうかの判断基準の一例をご紹介しました。

自動テストの追加は、ドキュメントの修正に次いで「外部のコントリビューターとして開発に参加する最初のステップ」として取り組みやすい作業です。自動テストが全く存在しないプロダクトや、自動テストがあっても特定の機能についてテストが不足しているというケースに遭遇したら、皆さんもぜひテストの追加に取り組んでみて下さい。独りでやりきるには不安があるという方は、スケジュールが合うOSS Gateのワークショップに参加してサポーターの人に相談してみても良いかもしれません。

*1 今まで期待通りに動いていた物が、別の変更の影響で期待通りに動かなくなってしまう事。

*2 ある問題を修正したときに、問題が発生しなくなっている事を検証するテストのこと。

2019-04-23

RubyKaigi 2019 - Better CSV processing with Ruby 2.6 #rubykaigi

RubyKaigi 2019の2日目にBetter CSV processing with Ruby 2.6という話をした須藤です。今年もクリアコードはシルバースポンサーとしてRubyKaigiを応援しました。

Better CSV processing with Ruby 2.6

内容

この1年、 @284km と一緒にcsvを改良していたのでその成果を自慢しました。せっかく2人で話をするので、時間を分割してそれぞれ話をするのではなく、ずっと掛け合いをしながら2人で話をしました。楽しんでもらえたでしょうか？

Ruby 2.6.3に入っているcsvはどんなケースでもRuby 2.5のcsvより高速になっています。この成果を使うためにぜひ最新のRubyにアップグレードしてください。

最後にも少し触れましたが、まだまだcsvやその周辺に改良すべきことがあります。今回の話でcsvの開発に興味がでてきた人は一緒に改良してきましょう。その気になった人はRed Data ToolsのGitterに書き込んでください。どうやって進めるか相談しましょう。

RubyKaigi 2019でまわりの人たちと相談してstrscanのメンテナンスを引き取ることにしたのでそのあたりの改良もできます。

RubyData Workshop

発表の後、RubyData WorkshopでもRed Data Toolsの開発に参加する人を募りました。すでに数人Red Data ToolsのGitterに書き込んでいる人もいます。やったね！

まとめ

RubyKaigi 2019で最近のcsvの開発の成果を自慢しました。今回は2人での発表だったのでやいのやいのした発表をしました。

Red Data Toolsの仲間が増えたのでよいRubyKaigiでした。

2019-04-20

FirefoxやChromiumのアドオン（拡張機能）で効率よくタブを並べ替えるには

この記事はQiitaとのクロスポストです。

Firefox 57以降のバージョンや、Google Chromeをはじめ各種のChromiumベースのブラウザでは、アドオン開発に共通のAPIセットを使用します。タブバー上のタブを任意の位置に移動するAPIとしてはtabs.move()という機能があり、これを使うと、タブを何らかのルールに基づいて並べ替えるという事もできます。実際に、以下のような実装例もあります。

Firefox Multi-Account Containers: コンテナごとにタブを並べ替える。
Sort tabs advanced: URLなどの条件でタブを並べ替える。

このようなタブの並べ替え機能を実現する時に気をつけたいポイントとして、 いかにAPIの呼び出し回数を減らし、効率よく、且つ副作用が少なくなるようにするか？ という点があります。

ソートアルゴリズムの効率とは別の話

「並べ替え」「効率」というキーワードでソートアルゴリズムの事を思い浮かべる人もいるのではないでしょうか。確かにそれと似ているのですが、実際にはこの話のポイントはそこにはありません。

確かに、ソート自体は前述の2つのアドオンでも行っており、

バラバラの順番のタブをコンテナごとに整理する
URLなどの条件でタブの順番を整理する

という処理はまさにソートそのものです。しかし、現代のJavaScript実行エンジンは充分に高速なため、余程まずいアルゴリズムでもない限りJavaScriptで実装されたソートの速度自体は実用上の問題となりにくいです。

それよりも、その後に行う 「実際のタブを移動して、算出された通りの順番に並べ替える」 という処理の方が影響度としては深刻です。「タブ」というUI要素を画面上で移動するのは、純粋なデータのソートに比べると遙かにコストが大きいため、数百・数千個といったオーダーのタブをすべて並べ替えるとなると相応の時間を要します。また、タブが移動されたという事はイベントとして他のアドオンにも通知され、その情報に基づいて様々な処理が行われ得ます*1ので、そのコストも馬鹿になりません*2。

タブの並べ替えには手間がかかる

実際の並べ替えの様子を図で見てみましょう。[i, h, c, d, e, f, g, b, a, j] という順番のタブを、[a, b, c, d, e, f, g, h, i, j] に並べ替えるとします。

ぱっと見で気付くと思いますが、これは a, b, h, i の4つを左右で入れ換えただけの物です。しかし、人間にとっては一目瞭然の事でも、プログラムにとっては自明な事ではありません（それを検出するのがまさにこの記事の本題なのですが、詳しくは後述します）。

最もナイーブな*3実装としては、元の並び順からタブを1つづつ取り出していくやり方が考えられます。その場合、行われる操作は以下のようになります。

というわけで、この場合だと10個のタブの並べ替えに8回の移動が必要となりました。元のタブの並び順次第では、移動は最大で9回必要になります。

ちなみに、tabs.move()は第一引数にタブのidの配列を受け取ることができ、その場合、第一引数での並び順の通りにタブを並べ替えた上で指定の位置に移動するという挙動になります。そのため、

browser.tabs.move([a, b, c, d, e, f, g, h, i, j], { index: 0 });

とすれば、APIの呼び出し回数としては確かに1回だけで済ませる事もできます。ただ、これは内部的には

browser.tabs.move(a, { index: 0 });
browser.tabs.move(b, { index: 0 + 1 });
browser.tabs.move(c, { index: 0 + 2 });
browser.tabs.move(d, { index: 0 + 3 });
browser.tabs.move(e, { index: 0 + 4 });
browser.tabs.move(f, { index: 0 + 5 });
browser.tabs.move(g, { index: 0 + 6 });
browser.tabs.move(h, { index: 0 + 7 });
browser.tabs.move(i, { index: 0 + 8 });
browser.tabs.move(j, { index: 0 + 9 });

といった移動操作と同等に扱われるため、タブが実際に移動されるコストは変わらず、タブが移動された事を通知するイベントもその都度通知されます。

ソートと同時にタブを移動するのではどうか？

ここまではArray.prototype.sort()でソートした結果に従って、後からまとめてタブを並べ替えるという前提で説明していました。では、Array.prototype.sort()を使わずに独自にソートを実装し、その並べ替えの過程で同時にタブも移動する、という形にするのはどうでしょうか？

例えばこちらのクイックソートの実装の過程にtabs.move()を呼ぶ処理を追加すると、以下のようになります。

// 再帰によるクイックソートの実装
function quickSort(tabIds, startIndex, endIndex) {
  const pivot = tabIds[Math.floor((startIndex + endIndex) / 2)];
  let left = startIndex;
  let right = endIndex;
  while (true) {
    while (tabIds[left] < pivot) {
      left++;
    }
    while (pivot < tabIds[right]) {
      right--;
    }
    if (right <= left)
      break;
    // 要素の移動時に、同じ移動操作をタブに対しても行う
    browser.tabs.move(tabIds[left], { index: right });
    browser.tabs.move(tabIds[right], { index: left });
    const tmp = tabIds[left];
    tabIds[left] = tabIds[right];
    tabIds[right] = tmp;
    left++;
    right--;
  }
  if (startIndex < left - 1) {
    quickSort(tabIds, startIndex, left - 1);
  }
  if (right + 1 < endIndex ){
    quickSort(tabIds, right + 1, endIndex);
  }
}
const tabs = await browser.tabs.query({windowId: 1 });
quickSort(tabs.map(tab => tab.id), 0, tabIds.length - 1);

先の [i, h, c, d, e, f, g, b, a, j] を [a, b, c, d, e, f, g, h, i, j] に並べ替えるという例で見てみると、

このように、今度は4回の移動だけで並べ替えが完了しました。先の場合に比べると2倍の高速化なので、これは有望そうに見えます。

……が、そう考えるのは早計です。この例で並べ替えが4回で終わったのは、部分配列の左右端から要素を見ていくというアルゴリズムが、左右の端に近い要素が入れ替わる形になっていた [i, h, c, d, e, f, g, b, a, j] という元の並び順に対して非常にうまく作用したからに過ぎません。例えば入れ替わった要素の位置が左右の端から遠い位置にある [c, d, i, h, e, b, a, f, g, j] のようなケースでは、

と、今度は12回も移動が発生してしまいます。クイックソートは場合によっては同じ要素を何度も移動する事になるため、タブの移動のコストが大きい事が問題となっている今回のような場面では、デメリットの方が大きくなり得るのです。

また、クイックソートには「ソート結果が安定でない」という性質もあります。各要素のソートに使う値がすべて異なっていれば並べ替え結果は安定しますが、Firefox Multi-Account Containersでの「タブのコンテナごとに整理する」というような場面では、同じグループの要素の順番がソートの度に入れ替わってしまうという事になります。このような場合は要素間の比較の仕方を工夫するか、別のソートアルゴリズムを使う必要があります。

どうやら、このアプローチでは一般的に効率よくタブを並べ替えるという事は難しいようです。一体どうすれば「人が目視でするように、可能な限り少ない移動回数で、タブを目的の順番に並べ替える」という事ができるのでしょうか。

diffのアルゴリズムを応用する

このような問題を解決するには、diffや編集距離といった考え方が鍵となります。

Unix系の環境に古くからあるdiffというコマンドを使うと、2つの入力の差を表示する事ができます。Gitなどのバージョン管理システムにおいてもgit diffのような形で間接的に機能を利用できるようになっているため、各コミットで行った変更点を見るために使った事がある人は多いでしょう。例えば、A = [a, b, c, d] と B = [a, c, d, b] という2つの配列があったとして、AとBの差分はdiffでは以下のように表されます。

  a
- b
  c
  d
+ b

行頭に-が付いている行は削除（AにはあってBには無い）、+が付いている行は追加（Aには無くてBにはある）を意味していて、これを見れば、「Aのbを2番目から4番目に移動する」というたった1回の操作だけでAをBにできるという事が見て取れます。このような「最小の変更手順」を求めるのが、いわゆる「diffのアルゴリズム」です。

つまり、これを「タブの並べ替え」に当てはめて、「現時点でのタブの並び順」と「期待される並び順」とを比較し、算出された差分の情報に則ってタブを実際に移動するようにすれば、最小の手間でタブを並べ替えられるというわけです。

JavaScriptでのdiffの実装

diffの実装というとdiffコマンドが真っ先に思い浮かぶ所ですが、diffをライブラリとして実装した物は各言語に存在しており、もちろんJavaScriptの実装もあります。以下はその一例です。

jsdiff：npmのdiffパッケージとして導入可能な物（3条項BSDライセンス）
「ツリー型タブ」に内蔵されているdiff.js：Pythonでの実装をJavaScriptに移植した物（Python Software Foundation License）

diffのアルゴリズムをタブの並べ替えに使うには、こういったライブラリをプロダクトに組み込むのがよいでしょう。ただ、その際には以下の点に気をつける必要があります。

ライブラリのライセンスが他の部分のライセンスと競合しない事。
ライブラリの内部表現を機能として利用できる事。
入力として任意の要素の配列を受け受ける事。

ライセンスの事は当然として、内部表現が利用できるとはどういう事でしょうか。

前述の例の「行頭に-か+が付く」という表現は、git diffなどで目にする事の多い「Unified Diff」形式に見られる表記ですが、これはあくまで最終出力です。ライブラリ内部では、相当する情報を構造化された形式で持っている事が多いです。npmのdiffであるjsdiffの場合は以下の要領です。

[
  { count: 1, value: [a] },                // 共通の箇所
  { count: 1, value: [b], removed: true }, // 削除された箇所
  { count: 2, value: [c, d] },             // 共通の箇所
  { count: 1, value: [b], added: true }    // 追加された箇所
]

先のテキストでの表現をパースしてこのような表現を組み立てる事もできますが、ライブラリの内部表現→出力結果のテキスト表現→内部表現風の表現という無駄な変換をするよりは、素直に内部表現をそのまま使えた方が話が早いです。

また、ライブラリの入力形式には任意の配列を受け付ける物である方が望ましいです。文字列のみを入力として受け付けるライブラリでも使えなくはないのですが、内部ではどの実装も基本的に配列を使っています。こちらも、比較したい配列→ライブラリに与えるための文字列→内部表現の配列という無駄な変換が必要の無い物を使いたい所です。

npmのdiffパッケージであるjsdiffは、これらの点で使い勝手が良いのでおすすめの実装と言えます。

diffのアルゴリズムを使ったタブの並べ替え

diffを使ってタブを並べ替えるには、「ソート前の配列」「ソート後の配列」に「作業中の状態を保持する配列」を加えた3つの配列を使います。

const tabs = await borwser.tabs.query({ currentWindow: true });

const beforeIds = tabs.map(tab => tab.id); // ソート前のタブのidの配列
const afterIds  = tabs.sort(comparator)
                      .map(tab => tab.id); // ソート後のタブのidの配列
let   currentIds = beforeIds.slice(0);     // 現在の状態を保持する配列（ソート前の状態で初期化）

次に、ソート前後のタブのidの配列同士の差分を取り、その結果に従ってタブを移動していきます。

const differences = diff.diffArrays(beforeIds, afterIds);
for (const difference of differences) {
  if (!difference.added) // 削除または共通の部分は無視する
    continue;
  // ここにタブの移動処理を書いていく
}

タブの移動による並べ替えという文脈では、「削除」の差分で操作されるタブは対応する「追加」の操作によっても操作されます。また、「なくなるタブ（＝処理中に閉じなければいけないタブ）」は原則として存在しません。よって、差分情報のうち「共通」と「削除」は無視して、「追加」にあたる物のみを使用します。

「追加」の差分情報を検出したら、まずタブの移動先位置を計算します。tabs.move()はタブの位置をindexで指定する必要がありますが、この時のindexは以下の要領で求められます。

  // 以下、forループ内の処理

  // 移動するタブ（1個以上）
  const movingIds = difference.value;
  // 移動するタブ群の中の右端のタブを得る
  const lastMovingId = movingIds[movingIds.length - 1];
  // ソート後の配列の中で、移動するタブ群の右に来るタブの位置を得る
  const nearestFollowingIndex = afterIds.indexOf(lastMovingId) + 1;
  // 移動するタブ群がソート後の配列の最後に来るのでないなら、
  // 移動するタブ群の右に来るタブのindexを、タブ群の最初のタブの移動先位置とする
  let newIndex = nearestFollowingIndex < afterIds.length ? currentIds.indexOf(afterIds[nearestFollowingIndex]) : -1;
  if (newIndex < 0)
    newIndex = beforeIds.length;

  // 移動するタブ群の左端のタブの現在のindexを調べる
  const oldIndex = currentIds.indexOf(movingIds[0]);
  // 現在の位置よりも右に移動する場合、移動先の位置を補正する
  if (oldIndex < newIndex)
    newIndex--;

タブ群の移動先の位置を求めたら、いよいよtabs.move()でタブを移動します。このAPIは第1引数にタブのidの配列を渡すと複数のタブを一度に指定位置に移動できるので、APIの呼び出し回数を減らすためにもそのようにします。

  // 実際にタブを移動する
  browser.tabs.move(movingIds, {
    index: newIndex
  });
  // 現在の状態を保持する配列を、タブの移動後として期待される状態に合わせる
  currentIds= currentIds.filter(id => !movingIds.includes(id));
  currentIds.splice(newIndex, 0, ...movingIds);

タブの移動はAPIを介して非同期に行われますが、タブの移動指示そのものはまとめて一度にやってしまって構いません。むしろ、途中でtabs.move()の完了をawaitで待ったりすると、タブの並べ替えの最中に外部要因でタブが移動されてしまうリスクが増えるので、ここはバッチ的に同期処理で一気にやってしまうのが得策です。

ただしその際は、2回目以降のtabs.move()に指定するタブの移動後の位置として、前のtabs.move()の呼び出しで並べ替えが完了した後の位置を指定しなくてはならないという点に注意が必要です。そのため、ソート前後の配列とは別に「並べ替えが実施された後の状態」を保持する配列を別途用意しておき、それだけを更新しています。前述のコード中で「タブの現在の位置」を求める際に、tabs.Tabのindexを参照せずにこの配列内での要素の位置を使用していたのは、これが理由なのでした。

実際の並べ替えの様子を、最初と同じ例を使って見てみましょう。[i, h, c, d, e, f, g, b, a, j] を [a, b, c, d, e, f, g, h, i, j] に並べ替えるとします。初期状態は以下のようになります。

beforeIds: [i, h, c, d, e, f, g, b, a, j]
afterIds: [a, b, c, d, e, f, g, h, i, j]
currentIds: [i, h, c, d, e, f, g, b, a, j]
実際のタブ: [i, h, c, d, e, f, g, b, a, j]

この時、beforeIdsとafterIdsを比較して得られる差分情報は以下の通りです。

// 実際にはvalueはタブのidの配列だが、分かりやすさのためにここではアルファベットで示す
[
  { count: 2, value: [i, h], removed: true },
  { count: 2, value: [a, b], added: true },
  { count: 5, value: [c, d, e, f, g] },
  { count: 2, value: [b, a], removed: true },
  { count: 2, value: [h, i], added: true },
  { count: 1, value: [j] }
]

前述した通り、ここで実際に使われる差分情報は「追加」にあたる以下の2つだけです。

{ count: 2, value: [a, b], added: true }
{ count: 2, value: [h, i], added: true }

まず1つ目の差分情報に基づき、aとbを移動します。移動先の位置は、bの右隣に来る事になるタブ（＝c）のcurrentIds内での位置ということで、2になります。

この時、b, aだった並び順も併せてa, bに並べ替えています。タブの移動完了後は、それに合わせる形でcurrentIdsも [i, h, a, b, c, d, e, f, g, j] へと更新します。

次は2つ目の差分情報に基づき、hとiを移動します。移動先の位置は、iの右隣に来る事になるタブ（＝j）のcurrentIds内での位置から求めます。jの位置は9ですが、これはhの現在位置より右なので、そこから1減らした8が最終的な移動先位置になります。

この時も、i, hだった並び順をh, iに並べ替えています。タブの移動完了後は、それに合わせる形でcurrentIdsも [a, b, c, d, e, f, g, h, i, j] へと更新します。

ということで、APIの呼び出しとしては2回、タブの移動回数としては4回で並べ替えが完了しました。冒頭の例の8回に比べるとタブの移動回数は半分で済んでいます。

クイックソートでは却って移動回数が増えてしまった、[c, d, i, h, e, b, a, f, g, j] からの並べ替えではどうでしょうか。この場合、比較結果は以下のようになります。

[
  { count: 2, value: [a, b], added: true },
  { count: 2, value: [c, d] },
  { count: 2, value: [i, h], removed: true },
  { count: 2, value: [e] },
  { count: 2, value: [b, a], removed: true },
  { count: 2, value: [f, g] },
  { count: 2, value: [h, i], added: true },
  { count: 1, value: [j] }
]

前述の通り、このうち実際に使われる差分情報は以下の2つだけです。

{ count: 2, value: [a, b], added: true }
{ count: 2, value: [h, i], added: true }

これは先の例と全く同じなので、APIの呼び出し回数は2回、実際のタブの移動は4回で済みます。

これらの例から、diffのアルゴリズムを用いると安定して少ない移動回数でタブを並べ替えられるという事が分かります。diffのアルゴリズムを用いた差分の計算自体はタブの移動に比べれば一瞬で済みますので、タブの移動回数を少なく抑えられれば充分に元が取れると言えるでしょう。

まとめ

以上、diffのアルゴリズムを用いてブラウザのタブを効率よく並べる方法について解説しました。

冒頭で例として挙げたタブの並べ替え機能を持つアドオンに対しては、以上の処理を実際に組み込むプルリクエストを既に作成済みです。

これらの変更（およびこの記事）は、「ツリー型タブ」での内部的なタブの並び順に合わせてFirefoxのタブを並べ替える処理が元になっています。ツリー型タブではnpmのdiffとは別のdiff実装を使用していますが、diffの結果として得られる内部表現の形式はよく似ており、タブの並べ替え処理そのものは同じロジックである事が見て取れるはずです。

このように「最小の変更内容を計算して適用する」という考え方は、Reactで広まった仮想DOMという仕組みのベースとなっています。コンピューターが充分に高性能となり、富豪的プログラミングが一般化した現代においては、多少の事は力業で解決してしまって問題無い事が多いです。しかし、ネットワーク越しの処理や、携帯端末などデスクトップPCよりも性能が制限されがちな環境などで、何千・何万回といった単位で実行されるような処理にボトルネックがあると致命的な性能劣化に繋がりかねず、そのような場合には「コストの高い処理の実行頻度を減らしてトータルの性能を向上する」という正攻法での性能改善が依然として有効です。

なお、2者間で「変更箇所を検出する」というのは「共通部分を検出する」という事と表裏一体ですが、そのような計算は最長共通部分列問題と呼ばれ、diffのアルゴリズムの基礎となっています。どのような理屈で共通箇所を検出しているのか知りたい人は解説や論文を参照してみると良いでしょう。筆者は理解を諦めましたが……

*1 例えば、タブをツリー状の外観で管理できるようにするアドオンであるツリー型タブでは、親のタブが移動された場合は子孫のタブもそれに追従して移動されますし、既存のツリーの中にタブが出現した場合や既存のツリーの一部だけが別の場所に移動された場合などにも、ツリー構造に矛盾が生じなくなるようにタブの親子関係を自動的に調整するようになっています。

*2 ブラウザ自体のタブの並べ替えにかかる時間の事よりも、むしろ、こちらの副作用の方が問題だと言っていいかもしれません。

*3 愚直な。

2019-04-19

公開中のソフトウェアがWindows Defenderでマルウェアとして判定された場合の対応

当社ではIE View WEというアドオンを開発・公開しています。これはFirefox上で閲覧中のページやマッチングパターンに当てはまるURLのページをIEもしくは任意の外部アプリケーションで開くという物で、Firefox法人サポートでの需要を想定して、既存のアドオン「IE View」の仕様を参考にFirefox 57以降で使用できる形（WebExtensionsベース）でスクラッチで開発したという物です。

WebExtensionsではアドオンが直接任意の外部アプリケーションを起動する事はできず、Native Messaging Hostと呼ばれるヘルパープログラムを介する必要があります。Native Messaging Hostは任意の言語で実装することができますが、IE View WEのNative Messaging Hostの場合はgoで開発しており、一般のユーザのためにコンパイル済みのバイナリも公開・配布しています。

このNative Messaging Hostのバイナリについて、先日、「Windows Defenderでトロイ（マルウェア）と判定されている」というご指摘を頂きました。

結果的にはただの誤判定だったのですが、配布物がそのような警告を受ける状態となった事は当社では過去に無かったため、対応のノウハウが無く手探りでの対応とならざるを得ませんでした。本記事では、本件に際して実際に行った対応の内容をご紹介します。同様の事態に遭遇された方の参考になりましたら幸いです。

第一報〜状況確認〜バイナリ公開停止

最初に受け取ったのは、以下のような内容の指摘のメール（英語）でした。

件名: Native Messaging Host……
本文: Windows 10 32bit版のWindows Defenderで、トロイと判定されます。

これを受け、まず、本当に配布ファイルがWindows Defenderでマルウェアと判定されるのかどうかを確認しました。

IE View WEのNative Messaging Hostのバイナリは、現在の所GitHubのリリースページでのみ配布しています。まず公開中のファイルをダウンロードし、実際にWindows Defenderに判定させてみました*1。その結果、確かに Trojan:Win32/Azden.A!cl として判定される結果となりました。

そこで、公開中のバイナリをリリースページから削除し、以下の文言を表示するようにしました。

Note: ieview-we-host.zip is undistributed due to security reason for now. Please wait for a while.

註：ieview-we-host.zipはセキュリティ上の理由により現在公開を停止中です。しばらくお待ち下さい。

さらなる状況確認

次に確認したのは、ダウンロードした配布ファイルはこちらで作成してアップロードした物と同一なのかどうかという点です。

ダウンロード用のURLはHTTPSとなっており、サーバーからのダウンロード過程でファイルが攻撃者によって置き換えられてしまう可能性はありません。しかし、バイナリ自体に電子署名は施していないため、サーバー上にあるファイル自体がこちらでアップロードした物から差し替えられてしまっている可能性は0とは言えません*2。そのため、次の段階としてダウンロード後のファイルとアップロード前のファイルのハッシュ値をsha256sumコマンドで算出し、両者が一致するかどうかを確認しました。その結果、ハッシュ値は一致し、アップロードの前後でファイルは変化していない事を確認できました。

（なお、仮にこの段階でファイルのハッシュ値が一致しなかった場合、アップロードされた後でファイルが改竄されたという事になります。それが可能となるのは、当社エンジニアが使用しているSSH秘密鍵が流出したか、GitHubのWebサービスが攻撃を受けてファイルが改竄されたというケースにあたり、また別の対応が必要になってきます。）

アップロード前のファイルがマルウェア判定された場合の対応

アップロード前の状態と同一のファイルがマルウェアと判定されるということは、ファイルが作成された時点からそのような内容が含まれていたという事になります。そうなると、今度は以下の可能性が疑われます。

バイナリ作成者のPCがすでに攻撃者によって乗っ取られていた。
バイナリに含まれる外部ライブラリに攻撃コードが混入していた。

作業者のPCが攻撃者によって乗っ取られるというのは、現代でもあり得る脅威です。例えば、いわゆるフリーWi-Fiの使用時は、同一のLAN内に全く素性の知れない他人が接続してきている状況で、攻撃の踏み台として標的にされるという事は十分に起こり得ます。

ただ、今回の事例ではこの可能性はそう高くないと考えられました。作業者のPCはUbuntuのデスクトップ環境が動作しており、外部からの接続も公開鍵認証のSSH以外は受け付けないよう設定されていたからです。絶対数が少ない環境の上、フリーWi-Fiに接続する機会もほぼ無いため、あらかじめ攻撃を受けていて踏み台にされていたという事は考えにくいです。

また、現代のソフトウェアは多数の依存ライブラリを引用する形で成り立っている事が多く、その中にこっそり悪意あるコードが混入していたとしても容易に気付けないという状況にあります。実際、そのような攻撃が行われた事例や、攻撃が行われうる脆弱性が指摘された事例は複数あります。

こちらの可能性を疑い始めると、調査は困難になってきます。依存ライブラリもまた別のライブラリに依存しているという事が多く、場合によっては調査範囲が際限なく広がってしまうからです。

Microsoftへの連絡

ここで初めて、それまで意図的に敢えて除外していた、擬陽性であった可能性を考え始める事にしました。

現代のマルウェアは日々多種多様な亜種が発生しており、単純なパターンマッチングでは「本当はマルウェアなのにマルウェアとして判定されない」というケース（擬陰性）が発生しやすいです。そのため各セキュリティ対策ソフトのベンダーは、機械学習を用いた分析や実際のソフトウェアの動作の様子を監視するなどして、疑わしい振る舞いをするソフトウェアは積極的に脅威判定するようになっています。その結果、本来は無害なソフトウェアであってもマルウェアの疑い有りとして検出されるというケース（擬陽性）が発生してしまう事があります。

Microsoftではこのようなケースを想定して、提出されたファイルを詳細に分析する受付窓口を提供しています。Windows Defenderでマルウェアとして判定されたソフトウェアをここで提出すると、専門家が分析した上で「本当にマルウェアである」あるいは「マルウェアではない」といった判定を行った結果を連絡してくれます。

今回のように自作ソフトウェアがマルウェア判定されたケースでは、「Software Developer（ソフトウェア開発者）」を選択して報告します。実際の報告内容は以下のようにしました。

会社名：ClearCode Inc.
判定名：Trojan:Win32/Azden.A!cl
定義ファイルバージョン：1.289.911.0

追加の情報：

This program is a native messaging host for a Firefox addon "IE View WE", and it provides following features:
1) Read configurations from local config files placed under specific locations, distributed by the system administrator.
2) Read registry to know where the executable file of the Internet Explorer (or Edge) is.
3) Launch the Internet Explorer (or Edge) with some options.
The source codes of the file are published under https://github.com/clear-code/ieview-we/tree/master/host and https://github.com/clear-code/mcd-go

参考訳（※送信した報告は英語の方のみです）

子のプログラムはFirefox用アドオン「IE View WE」用のNative Messaging Hostで、以下の機能を提供します:
1) システム管理者によって特定の位置に置かれたローカル設定ファイルから設定情報を読み取る。
2) レジストリからIE（またはEdge）の実行ファイルの位置を調べる。
3) いくつかのオプションを指定してIE（またはEdge）を起動する。
ソースコードは以下のサイトで公開しています： https://github.com/clear-code/ieview-we/tree/master/host および https://github.com/clear-code/mcd-go

送信した報告内容はキューに溜められ、順次処理されていきます。有償のサポート契約や開発者ライセンスを持っている場合、高い優先度でキューに割り込む事もできるようですが、当社はそのようなライセンスを特に保持していないので、一般的なソフトウェア開発者として報告するに留まりました。

報告者への連絡と、追加の確認

急いで取れる対応はここまでということで、この時点で一旦報告者の方に状況を伝える事にしました。

Hello,

Thank you for the information. We've removed the downloadable file for now, until those files are confirmed as completely safe. We've report those files to Microsoft security researchers, and waiting for responses.

regards,

こんにちは

情報をありがとうございます。安全が確認できるまで、ダウンロード可能なファイルは削除する事にしました。これらのファイルはすでにMicrosoftのセキュリティリサーチャーに報告済みで、返事を待っている状態です。

それでは

また、複数のセキュリティ対策ソフトでの検知結果を横断して確認できるVirusTotalというサイトでも確認を行った所、Windows Defender以外にもいくつかのソフトで脅威判定されている様子が窺えました。具体的な結果は以下の通りです。

32bit版バイナリ：検出率: 2/70（現時点では0/70）
- Cylance: Unsafe （20190312）
- Microsoft: Trojan:Win32/Azden.A!cl （20190307）
64bit版バイナリ：検出率: 1/65（現時点でも変わらず）
- Jiangmin: Trojan.Ebowla.k （20190312）

安全確認〜再公開

そうこうするうちに、Microsoftから分析完了の通知メールが届きました。メールに記載されていたリンクを開くと、以下のように記載されていました。

Submission details
host.exe

Submission ID: xxxx-xxxx-xxxx-xxxx-xxxx

Status: Completed

Submitted by: (送信者のMicrosoftアカウントのメールアドレス)

Submitted: Mar 12, 2019 11:19:43

User Opinion: Incorrect detection

Analyst comments:
We have removed the detection. Please follow the steps below to clear cached detection and obtain the latest malware definitions.

Open command prompt as administrator and change directory to c:\Program Files\Windows Defender

Run “MpCmdRun.exe -removedefinitions -dynamicsignatures”

Run “MpCmdRun.exe -SignatureUpdate”

Alternatively, the latest definition is available for download here: https://www.microsoft.com/en-us/wdsi/definitions

Thank you for contacting Microsoft.

報告の詳細
host.exe

報告ID: xxxx-xxxx-xxxx-xxxx-xxxx

状態: 完了

送信者: （送信者のMicrosoftアカウントのメールアドレス）

送信日時: 2019年3月12日 11:19:43

ユーザーの意見: 誤判定

分析者のコメント:
私達は判定を削除しました。以下の手順で判定結果のキャッシュを消去し、最新のマルウェア定義を入手して下さい。

コマンドプロンプトを管理者として開き、ディレクトリを「c:\Program Files\Windows Defender」に切り替える。

「MpCmdRun.exe -removedefinitions -dynamicsignatures」を実行する。

「MpCmdRun.exe -SignatureUpdate」を実行する。

もしくは、最新の定義ファイルは以下からもダウンロード可能です：https://www.microsoft.com/en-us/wdsi/definitions

表示されている時刻は日本時間です。11時台に報告して、結果が返ってきたのは14時〜16時にかけてでした*3。数日待たされる事も覚悟していたのですが、予想よりずっと早い回答でした。

案内のあった手順の通りに操作して再確認した所、バイナリはマルウェアとは検出されないようになりました。よって、これを以て安全の確認が取れたと見なし、以下の文言を添えて、公開を取り下げていたバイナリを再公開しました

Files named host.exe in ieview-we-host.zip may be detected as Trojan:Win32/Azden.A!cl by Microsoft Windows Defender, but it is false positive and actually safe. Those misdetectons have been reported to Microsoft, and go away after you update the malware definitions.

ieview-we-host.zipに含まれるhost.exeという名前のファイルがMicrosoft Windows DefenderによってTrojan:Win32/Azden.A!clと判定される事がありますが、これは擬陽性で、実際には安全です。この誤判定はMicrosoftに報告済みで、マルウェア定義の更新後は警告されなくなります。

また、報告者の方にも以下の通り連絡しました。

Hello,

The trojan alert was a false positive, and Microsoft researchers decided to remove them from detection. > After you update malware definitions, the alert will go away. Detailed steps described by Microsft:

(中略)

So we've re-published native messaging host binaries. Thanks again!

regards,

こんにちは

トロイ警告は擬陽性で、Microsoftのリサーチャーはこの判定結果を取り除く決定をしました。
マルウェア定義の更新後は、この警告は表示されなくなります。Microsoftによって案内された手順は以下の通りです:

(中略)

よって、Native Messaging Hostのバイナリを再公開しました。重ねてありがとうございます！

それでは

以上を以て、本件へのWindows Defenderに関する対応は完了としました。

まとめ

以上、Windows Defenderでマルウェアとして誤判定された場合の対応フローの例をご紹介しました。

被害の拡大を防ぐ事を第一に置くと、最初に取るべき対応は「実際にマルウェア判定されるか確認する」ではなく「サンプルとしてファイルをダウンロードした上で、バイナリの公開を停止する」だったと言えます。実際にマルウェア判定されるかどうかは公開を取り下げた後で行えば良かったにも関わらず、それを後回しにして「マルウェア判定されるのは事実か？」を先に確認してしまったのは不徳の致すところです。

今回は擬陽性での誤判定という事で決着しましたが、実際にマルウェアだったという場合にはまた別の対応が必要になってきます。そのような事は起こらないに越した事はありませんが、もし万が一そのような事態が発生した際には、被害の拡大を防ぐ事を最優先として対応したいです。

なお、2019年3月18日現在、VirusTotalで確認した限りでは、他の製品では脅威判定はなされない状態になっているようなのですが、Jiangminという製品で依然として脅威として判定されている模様です。Jiangminは中国系企業の製品で、JUSTセキュリティのバックエンドにも採用されているそうなのですが、公式サイトが中国語のみで提供されているため、報告の窓口が分からずお手上げとなっています。もし報告窓口をご存じの方がいらっしゃいましたら、情報をお寄せいただければ幸いです。

*1 この段階でもしマルウェアとして判定されなければ、報告者がファイルをダウンロードしたWebサイトで配布されているファイルが改竄済みの物である（改竄されたファイルが第三者によって配布されている）という事になります。

*2 電子署名を施していた場合、「署名した時点のファイルから改竄されていない事」が保証されるため、この確認は不要になります。

*3 32bit版と64bit版の各バイナリについて、結果が出るまでに若干タイムラグがありました。

2019-03-18

Firefox 67 以降でPolicy Engineによるポリシー設定でPOSTメソッドの検索エンジンを追加できるようになります

Firefoxのポリシー設定では、以下の要領でロケーションバーやWeb検索バー用の検索エンジンを登録することができます。

{
  "policies": {
    "SearchEngines": {
      "Add": [
        {
          "Name":               "検索エンジンの表示名",
          "IconURL":            "https://example.com/favicon.ico",
          "Alias":              "ex",
          "Description":        "検索エンジンの説明文",
          "Method":             "GET",
          "URLTemplate":        "https://example.com/search?q={searchTerms}",
          "SuggestURLTemplate": "https://example.com/suggest?q={searchTerms}"
        }
      ]
    }
  }
}

Firefox 66以前のバージョンではこの時、HTTPのメソッドとしてGETのみ使用可能で、POSTメソッドを要求する検索エンジンは登録できないという制限事項がありました。OpenSearchの検索プラグインではPOSTの検索エンジンも登録できたので、これはPolicy Engineだけの制限ということになります。

RESTの原則からいうと「何回検索しても同じ結果が返る事が期待される検索結果一覧ページを表示するためのリクエストはGETが当然」という事になるのですが、実際にはFirefoxのロケーションバーやWeb検索バーは「検索」に限らず、入力された語句を含む任意のHTTPリクエストを送信する汎用のフォームとして使えます。よって、適切な内容の「検索エンジン」を登録しておきさえすれば、FirefoxのUI上から直接「Issueの登録」や「チャットへの発言」を行うといった応用すらも可能となります。しかし、そういった「新規投稿」にあたるリクエストはPOSTメソッドを要求する場合が多いため、それらは残念ながらPolicy Engine経由では登録できませんでした。

この件について 1463680 - Policy: SearchEngines.Add cannot add effective search engine with POST method として報告していたのですが、最近になって「バックエンドとなる検索エンジン管理の仕組みの改良によって、仕組み的にはPOSTメソッドも受け取るようになったので、パッチを書いてみては？」と促されました。そこでさっそく実装してみた所、変更は無事マージされ、Firefox 67以降では以下の書式でPOSTメソッドとそのパラメータを指定できるようになりました。

{
  "policies": {
    "SearchEngines": {
      "Add": [
        {
          "Name":        "検索エンジンの表示名",
          "IconURL":     "https://example.com/favicon.ico",
          "Alias":       "ex",
          "Description": "検索エンジンの説明文",
          "Method":      "POST",
          "URLTemplate": "https://example.com/search",
          "PostData":    "q={searchTerms}"
        }
      ]
    }
  }
}

"Method"の指定を"POST"にする事と、"URLTemplate"ではなく"PostData"の方に{searchTerms}というパラメータを指定する事がポイントです。

今回の変更自体は別のBugでの改良に依存しているため、ESR60に今回の変更がupliftされるためには、依存する変更も併せてupliftされる必要があります。ESR版自体のメジャーアップデートも視野に入りつつあるこの時期ですので、そこまでの手間をかけてこの変更がESR60に反映されるかどうかについては、現状では何とも言えません。とはいえ、次のESRのメジャーアップデート以降で使用可能になる事は確実です。もしこの機能をお使いになりたいというESR版ユーザーの方がいらっしゃいましたら、期待してお待ちいただければと思います。

2019-03-01

Firefox ESR60でタイトルバーのウィンドウコントロールボタンが機能しなくなる事がある問題の回避方法

Firefox ESR60をWindows 7で使用していると、ウィンドウコントロール（タイトルバーの「最小化」「最大化」「閉じる」のボタン）が動作しなくなる、という現象に見舞われる場合があります。Firefoxの法人サポート業務の中でこの障害についてお問い合わせを頂き、調査した結果、Firefox自体の不具合である事が判明しました。

この問題は既にMozillaに報告済みで、Firefox 67以降のバージョンで修正済みですが、Firefox ESR60では修正されない予定となっています。この記事では、Firefox ESR60をお使いの方向けに暫定的な回避方法をご案内します。

問題の状況とその原因

この現象は、FirefoxのUIの設計に由来する物です。

一般的なWindowsアプリケーションは、タイトルバーなどを含めたウィンドウの枠そのものはWindowsに描画や制御を任せて、枠の内側だけでUIを提供します。それに対し、Firefoxのブラウザウィンドウでは、タイトルバー領域に食い込む形でタブを表示させるため、タイトルバーを含むウィンドウの枠まで含めた全体を自前で制御しています。そのため、タイトルバー領域に食い込む形でタブが表示されている場面では、Windowsが標準で提供しているウィンドウコントロールのボタンは実は使われておらず、それを真似る形で置かれた独自のUI要素で代用しています。

通常、これらの代用ボタンは他のUI要素よりも全面に表示されるため、タブなどの下に隠れる事はなく、ユーザーは見たままの位置にあるボタンをクリックできます。しかし、特定の条件下ではこれらの代用ボタンが他のUI要素の下に隠れてしまう形となり、ボタンをクリックできなくなってしまいます。

この問題が起こる条件は、以下の通りです。

Windows 7で、Windows自体のテーマとして「Classic」テーマを使用している。
ツールバー上の右クリックメニューから「メニューバー」にチェックを入れており、メニューバーが常時表示される状態になっている。
ウィンドウがwindow.open()で開かれ、その際、メニューバーを非表示にするように指定された。

Windowsのテーマ設定とFireofxのツールバーの設定を整えた状態で、w3schools.comのwindow.oepn()の各種指定のサンプルを開き「Try it」ボタンをクリックしてみて下さい。実際に、ボタンが機能しないためウィンドウを閉じられなくなっている*1事を確認できるはずです。

問題が再現した時のFirefoxの内部状態を詳しく調査すると、Classicテーマにおいては、この状況下ではタブバーのz-index（重ね合わせの優先順位）が2になるのに対し、ウィンドウコントロールのz-indexは常に1になるために、タブバーがウィンドウコントロールの上に表示されてしまっている状態である*2という事が分かりました。

なお、ClassicテーマはWindows 7以前のバージョンでのみ使用できる機能で、Windows 10以降では使えません*3。そのため、この問題はWindows 10以降では再現しません。

回避方法

原因が分かれば対策は容易です。

最も単純な対策は、ユーザープロファイル内にchromeという名前でフォルダを作成し、以下の内容のファイルをuserChrome.cssの名前で設置するというものです。

@namescape url("http://www.mozilla.org/keymaster/gatekeeper/there.is.only.xul");

/* WindowsでClassicテーマが反映されている場合、 */
@media (-moz-windows-classic) {
  /* タイトルバーにタブを表示する設定で、フルスクリーン表示でない時は、 */
  #main-window[tabsintitlebar]:not([sizemode=fullscreen]) #titlebar-buttonbox {
    /* ウィンドウコントロールの重ね合わせ順位をタブバーよりも上にする */
    z-index: 3 !important;
  }
}

ただ、ユーザープロファイルの位置はFirefoxの実行環境ごとに異なる*4ため、管理者側でこの対応を全クライアントに反映するのは難しいです。クライアント数が多い場合は、Firefoxのインストール先のchromeやbrowser\chrome配下に置かれたCSSファイルを自動的に読み込むためのスクリプトをMCD用設定ファイルに組み込むなどの方法をとるのがおすすめです。

修正の状況

原因が判明した時点で、本件はFirefox本体の問題としてbugzilla.mozilla.orgに以下の通り報告しました。

1521692 - Unclickable window controls (minimize, maximize and close buttons) on a window opened via window.open() with "toolbar", without "menubar", when the menu bar is configured as always shown and running on Windows 7 with the Classic theme

また、調査を行った時期にちょうどFirefoxのタブバー・タイトルバー周りの実装の仕方が変化していたため、最新の開発版でも状況を確認した所、Firefox 65以降ではWindows 7でなくても同様の問題が起こり、しかも今度はそもそもウィンドウコントロールが表示されなくなってしまっているという、より酷い状況でした。そのため、そちらは別の問題として以下の通り報告しました。

1521688 - Missing window controls (minimize, maximize and close buttons) on a window opened via window.open() with "toolbar", without "menubar", when the menu bar is configured as always shown

Firefox ESR60およびFirefox 64以前での問題（本記事で解説している問題）については、Firefox 65でタブバーの設計が変わったために現象としては再現しなくなった事と、セキュリティに関わる問題ではない事から、修正はされないという決定がなされています。

Firefox 65以降での問題については、既に修正のためのパッチを提供し、Firefox 67以降のバージョンに取り込まれる事が確定しています。Firefox 65に対しては修正はバックポートされず、Firefox 66については特に誰も働きかけなければ修正は反映されないままとなる見込みです。

まとめ

以上、Firefoxの法人向け有償サポートの中で発覚したFirefoxの不具合について暫定的な回避方法をご案内しました。

当社のフリーソフトウェアサポート事業では、当社が開発した物ではないソフトウェア製品についても、不具合の原因究明、暫定的回避策のご提案、および（将来のバージョンでの修正のための）開発元へのフィードバックなどのサポートを有償にて行っております。Firefoxのようなデスクトップアプリケーションだけでなく、サーバー上で動作する各種ソフトウェアについても、フリーソフトウェアの運用でトラブルが発生していてお困りの企業のシステム管理担当者さまがいらっしゃいましたら、メールフォームよりご相談下さい。

*1 そのため、ウィンドウを閉じるにはCtrl-F4などのキーボードショートカットを使うなどの、ボタンを使わない方法を使う必要があります。

*2 タブバーの右端はあらかじめウィンドウコントロールを重ねて表示するために余白領域が設けられていますが、現象発生時には、この余白領域の上ではなく下にウィンドウコントロールが表示されており、「ボタンは見えているのにその手前に透明な壁があってクリックできない」というような状況が発生しているという状況です。

*3 Classicテーマ風のテーマは存在していますが、Windows 7以前のそれとは異なり、単に配色等をClassicテーマ風にするだけの物です。

*4 安全のため、パスにランダムな文字列が含まれる形になっています。

2019-02-15

Web Crypto API で AES-CBC や AES-GCM の初期ベクトルをより安全に生成する

先日の Web Crypto API の基本的な使い方の解説（改訂済み）においては、説明を簡単にするために AES-GCM の初期ベクトルを乱数に基づいて生成しましたが、これはセキュリティの観点からはあまり好ましくありません。本記事では、Web Crypto API で AES-CBC や AES-GCM を用いて暗号化する場合の、より安全な初期ベクトルの生成方法について解説します。

望ましい初期ベクトルとは？

前の記事でも述べていますが、初期ベクトルについて簡単におさらいします。

共通鍵暗号のアルゴリズムである AES にはいくつかの「暗号モード」があり、中でも CBC や GCM といったモードでは、暗号化に際して初期ベクトルというパラメータが必要となっています。これは、データを暗号化する際に添加する無関係のデータのことで、それによって暗号文から元のデータを予測しにくくするという意味があります*1。他の暗号モードの CTR でも、カウンタの nonce 部分がこれと同様の役割を果たします。

暗号の仕様上は、初期ベクトルやnonce*2は一意である事が求められています。そのため、「ランダムなだけの値」を初期ベクトルに使うと困った事になります。

ここで一旦整理してますが、値が一意であるということと値がランダムであるという事は本質的に全く別の事です。

値が一意である＝値が重複しない事が保証されている。
値がランダム（乱雑）である＝値が予想できない、または極めて予想しにくい事が保証されている。

これらは相反する概念ではなく直交する概念なので、「一意で、且つランダムである」「一意でもないし、ランダムでもない」「一意だが、ランダムではない」「一意ではないが、ランダムである」という4つの組み合わせが理論上あり得ます。「ランダムな値」というと、直感的には「一意で、且つランダムである」という事を指していそうに思えますが、実際には「一意ではないが、ランダムである」という値もその範囲に入ってきます。

これを踏まえると、一意である事が求められる初期ベクトルに、ランダムであるというだけの「乱数」を使うのは、本来は間違いであるという事が言えます。前の記事の例では crypto.getRandomValues() を用いましたが、これもあくまで暗号論的に強度の高い疑似乱数*3であって、一意な値であることが保証されているわけではありません。確率は低いですが、生成された値が過去の値と偶然一致してしまうという可能性はあります。

実際、本当は怖いAES-GCMの話 - ぼちぼち日記という記事の中では、疑似乱数で初期ベクトルを大量に生成すると誕生日のパラドックス*4によって初期ベクトルが衝突するという事が述べられています。

その一方で、仕様によれば、初期ベクトルは「一意である」という事は求められているものの、「予測不能である」という事は求められていません。極端な話、重複さえしなければ、「単調増加するカウンタ」という極めて予測しやすい物であっても何ら問題ないという事です。実際、仕様の中でもカウンタが妥当な実装の例として挙げられているほどです。

一意な値というとUUIDがまず思い浮かびますが、UUIDは生成方法が妥当でないと値が衝突する可能性が（低いですが）あります。言語のライブラリによってはUUIDの生成が乱数ベースとなっていて、このような実装では、UUIDという名前なのに一意な結果を得られる事は残念ながら保証されていないという事になってしまいます。

しかし、UUIDが信用できない場合でも、単調増加型のカウンタなら確実に一意な結果を得られます。

同一の鍵での暗号化は、仕様では2の32乗回以上はしてはならないことになっています。そのため、カウンタの長さは32bitあれば事足りるということになります。

幸い、TypedArrayにはUint32Arrayという型があり、これを使うと1桁で32bitまでの数字を表す事ができます。また、JavaScriptの数値は64bit浮動小数点として実装されており、52bitまでの範囲であれば正確さが保証されているため、単純に以下の要領でカウンタとして利用できます。

// Uint32Arrayで一桁だけのカウンタを作成
let counter = new Uint32Array(1);

// カウントを足す
counter[0]++;

JavaScriptで任意の桁数のカウンタを実装する

ということで、実際にそれをJavaScriptで実装してみる事にしました。以下は、Typed Array や Array をカウンタとしてインクリメントする関数の実装例です。

function incrementCount(counter) { // 桁ごとの計算 const increment = column => { // 左端（最上位）の桁からの繰り上がりは無いので、桁あふれした事のみ返す if (column < 0) return true; // 指定された桁の値を1増やす const result = ++counter[column]; // 最大値を超えていないのであれば、そこで終了 if (result <= 255) return false; // 最大値を超えてしまった場合、その桁の値を0にリセット counter[column] = +0; // その後、繰り上がって1つ左（上位）の桁の値を1増やす（再帰） return increment(column - 1); }; // 右端（最下位）の桁を1増やし、左端（最上位）の桁があふれたかどうかを判定 const overflow = increment(counter.length - 1); // 左端（最上位）の桁が溢れた場合、全体を0にリセットする if (overflow) counter.fill(0); return counter; }

この関数は、Uint8Arrayを任意の桁数のカウンタとして使います。1つの桁あたり8bitなので、255になったら桁が繰り上がるという要領です。実際に、4桁のカウンタ（＝32bit）を使って動作を見てみましょう。

const counter = new Uint8Array(4); console.log(counter); // => Uint8Array(16) [ 0, 0, 0, 0 ]

カウンタは、最初はすべての桁が0で埋められています。カウントを進めると、最下位＝右端の桁の値が増えていきます。

incrementCount(counter); console.log(counter); // => Uint8Array(16) [ 0, 0, 0, 1 ] incrementCount(counter); console.log(counter); // => Uint8Array(16) [ 0, 0, 0, 2 ]

これを繰り返すと、いずれ最下位の桁が最大値に達します。

incrementCount(counter); console.log(counter); // => Uint8Array(16) [ 0, 0, 0, 255 ]

ここでさらにカウントを進めると、繰り上がりが発生して次の桁の値が増え、最下位の桁の値が0に戻ります。

incrementCount(counter); console.log(counter); // => Uint8Array(16) [ 0, 0, 1, 0 ]

カウントを進めると、また最下位の桁の値が増えていきます。

incrementCount(counter); console.log(counter); // => Uint8Array(16) [ 0, 0, 1, 1 ]

という事で、確かにカウンタとして動作している事を確認できました。

固定部とカウンタから初期ベクトルを組み立てる形で `AES-GCM` を使う

GCMの仕様では初期ベクトルの望ましい作り方の例がいくつか挙げられており、その中には、初期ベクトルを「前半の固定部」と「後半の変動部」に分けるやり方があります。

この文書では、固定部分は「デバイスの種類」「暗号化対象のコンテキスト」などを表すために使えると書かれています。よって、固定部として「暗号化を行うアプリのインスタンス」ごとに生成した値を使い、変動部に先のカウンタの値を使えば、GCMの仕様を満たす暗号化可能だと言えます。

そこで、前の記事に記載した AES-GCM による暗号化の例を元にして、カウンタを併用して初期ベクトルを組み立てる例を実装してみる事にします。

まず暗号の鍵ですが、これは話を簡単にするため、指定したパスフレーズ（パスワード）の文字列からその都度生成する事にします。鍵を~~自動生成~~ストレージに保管したり自動生成したりする場合については前の記事をご参照下さい。

async function getKey(passphrase, salt = null) {
  passphrase = (new TextEncoder()).encode(passphrase);
  let digest = await crypto.subtle.digest({ name: 'SHA-256' }, passphrase);
  let keyMaterial = await crypto.subtle.importKey('raw', digest, { name: 'PBKDF2' }, false, ['deriveKey']);
  if (!salt)
    salt = crypto.getRandomValues(new Uint8Array(16));
  let key = await crypto.subtle.deriveKey(
    {
      name: 'PBKDF2',
      salt,
      iterations: 100000,
      hash: 'SHA-256'
    },
    keyMaterial,
    { name: 'AES-GCM', length: 256 },
    false,
    ['encrypt', 'decrypt']
  );
  return [key, salt];
}

次は初期ベクトルの組み立てです。固定部の生成は以下の要領です。ここでは、最終的に128bitの長さの初期ベクトルにする前提で、そのうちカウンタに使う32bitを除いた残り96bitを固定部の長さとしています。

function getFixedField() {
  // 作成済みの値を取得する。
  let value = localStorage.getItem('96bitIVFixedField');
  // あれば、それを返す。
  if (value)
    return Uint8Array.from(JSON.parse(value));

  // 無ければ、新しい値（長さ96bit）を作成して保存する。
  // 96bitをUint8Arrayで表すため、96 / 8 = 12が桁数となる。
  value = crypto.getRandomValues(new Uint8Array(12));
  localStorage.setItem('96bitIVFixedField', JSON.stringify(Array.from(value)));
  return value;
}

作成済みの値があればそれを使い、無ければ新たに生成する、という形にすると、固定部の値が各実行インスタンスの識別子を表す事になります。先に述べた通り、乱数から得られた値は一意な値であることが保証されないので、本来は望ましくないのですが、個々の初期ベクトルを毎回乱数で生成するよりは衝突の確率が低いという事で、ここでは乱数を使う事にしました。

初期ベクトルの変動部は、~~前述の実装によるカウントアップ処理を使った単純なカウンタ~~前述の説明の通り32bitのカウンタにします。

function getInvocationField() {
  // 前回の値を取得。
  let counter = localStorage.getItem('32bitLastCounter');
  if (counter) // あればそれを使う。
    counter = Uint32Array.from(JSON.parse(counter));
  else // 無ければ新しいカウンタ（長さ32bit）を生成する。
    counter = new Uint32Array(1); 

  counter[0]++; // 値を1増やす。

  // 結果を保存する。
  localStorage.setItem('32bitLastCounter', JSON.stringify(Array.from(counter)));
}

ここでも、作成済みの値があればそれを使い、無ければ新たに生成する、という形にしており、これによって値が各実行インスタンスごとに固有のカウンタとなります。同じ実行インスタンスにおいて動作する限りは、カウンタの値は一意です。

こうして用意できる固定部と変動部の値は、それぞれ長さが96bitと32bitあります。これらを単純に連結すれば、128bitの長さの初期ベクトルを生成する事ができます。

let fixedPart      = getFixedField();
let invocationPart = getInvocationField();

// 固定部と形式を揃えるため、Uint8Arrayに変換する。
invocationPart = new Uint8Array(invocationPart.buffer);

// 2つのTyped Arrayの各桁をスプレッド構文で並べて、
// 新しい配列を生成
let concated = [...fixedPart, ...invocationPart];
// その配列をTyped Arrayに変換
let iv = Uint8Array.from(concated);

暗号化の際は、このようにして毎回新しい初期ベクトルを生成するようにします。

async function encrypt(input, passphrase) {
  let [key, salt]    = await getKey(passphrase);
  // 初期ベクトルを生成する。
  let fixedPart      = getFixedField();
  let invocationPart = getInvocationField();
  let iv = Uint8Array.from([...fixedPart, ...new Uint8Array(invocationPart.buffer)]);
  let encryptedData = await crypto.subtle.encrypt(
    { name: 'AES-GCM', iv },
    key,
    (new TextEncoder()).encode(JSON.stringify(input))
  );
  encryptedData = Array.from(new Uint8Array(encryptedData), char => String.fromCharCode(char)).join('');
  return JSON.stringify([
    btoa(encryptedData),
    // 暗号化されたデータには、必ず初期ベクトルの
    // 変動部とパスワードのsaltを添付して返す。
    invocationPart[0],
    Array.from(salt)
  ]);
}

関数の戻り値に初期ベクトルの変動部が添付されているという点がポイントです。AES-GCM においては、初期ベクトルは秘密である必要はありません。一方、初期ベクトルは暗号化されたデータの復号時に必要となります。以上の理由から、初期ベクトルは原則として、暗号化されたデータに添付してワンセットで取り扱う事になります。（鍵をパスワードから生成する場合、パスワードのsaltも同様に扱う必要があります。この例では、saltも初期ベクトルと併せてデータに添付しています。）

復号処理では、添付された初期ベクトルの変動部を取り出して固定部と組み合わせる事で、完全な初期ベクトルを復元する、という操作を行います。

// 暗号化されたデータに添付された初期ベクトルの変動部とsaltを得る。
let [encryptedData, invocationPart, salt] = JSON.parse(encryptedResult);
// 固定部を得る。
let fixedPart = getFixedField();
// 変動部をUint32Arrayに戻す。
let invocationPartTypedArray = new Uint32Array(1);
invocationPartTypedArray[0] = invocationPart;
// 変動部をUint8Arrayに変換する。
invocationPart = new Uint8Array(invocationPartTypedArray.buffer);
// 2つのTyped Arrayを連結して、完全な初期ベクトルを得る。
let iv = Uint8Array.from([...fixedPart, ...invocationPart]);

実際の復号処理は以下のようになります。

async function decrypt(encryptedResult, passphrase) {
  // 復号処理は、初期ベクトルが添付されたデータのみを取り扱うものとする。
  let [encryptedData, invocationPart, salt] = JSON.parse(encryptedResult);
  let [key, _] = await getKey(passphrase, Uint8Array.from(salt));
  let invocationPartTypedArray = new Uint32Array(1);
  invocationPartTypedArray[0] = invocationPart;
  // 初期ベクトルを復元する。
  let iv = Uint8Array.from([...getFixedField(), ...(new Uint8Array(invocationPartTypedArray.buffer))]);
  encryptedData = atob(encryptedData);
  encryptedData = Uint8Array.from(encryptedData.split(''), char => char.charCodeAt(0));
  let decryptedData = await crypto.subtle.decrypt(
    { name: 'AES-GCM', iv },
    key,
    encryptedData
  );
  decryptedData = (new TextDecoder()).decode(new Uint8Array(decryptedData));
  return JSON.parse(decryptedData);
}

ところで、ここでなぜ初期ベクトル全体ではなく変動部だけを添付しているかを疑問に思う人もいるのではないでしょうか。前の記事の例のように初期ベクトル全体を添付しておけば、上記のような初期ベクトルの復元処理は不要になるはずです。

初期ベクトルの変動部だけを添付する理由は2つあります。1つ目は、初期ベクトルの固定部は毎回共通のため、そのまま添付すると冗長だからで、これについては特に説明の必要はないでしょう。

2つ目の理由は、より安全性を高めるためです。このように暗号化されたデータ単体では初期ベクトルの全体が揃わないようにしておくと、もし万が一暗号化されたデータを知られたとしても、復元に必要な情報が揃わないため、攻撃はより困難になります。AES-GCM において初期ベクトルは秘密である必要はありませんが、一部だけでも秘密にすればより堅牢な保護が可能になる、という事です。

以上のコードをまとめた物をGistに置いてあります。以下の要領で実行すると、暗号化・復号を行える事、および、暗号化の度にカウンタの値が増加して一意な初期ベクトルを得られている事を確認できます。

(async () => {
  let passphrase = '開けゴマ';


  // 単純な文字列の暗号化と復号

  let encrypted = await encrypt('王様の耳はロバの耳', passphrase);
  console.log(encrypted);
  // => '["KoYoXAWjY1lAheEZrHYwAkbOf4e/kr8wgbVEPwNEjTawg3HTLmvvuXOqNn+R",[1],[122,107,206,161,208,200,58,46,97,139,37,201,101,28,223,203]]'

  let decrypted = await decrypt(encrypted, passphrase);
  console.log(decrypted);
  // => '王様の耳はロバの耳'


  // 複雑なデータの暗号化と復号

  encrypted = await encrypt({ a: 0, b: 1, c: true, d: 'foobar' }, passphrase);
  console.log(encrypted);
  // => '["bkvTkQNfTfnP7uUirivktij4iy66pSbiBDYJ3uNChkIlDJPBdkJ4Tqbe98a+QSujoHME",[2],[107,20,195,6,38,82,99,190,182,19,152,93,139,186,235,69]]'

  decrypted = await decrypt(encrypted, passphrase);
  console.log(decrypted);
  // => Object { a: 0, b: 1, c: true, d: "foobar" }
})();

まとめ

以上、AES-GCM の仕様で求められる性質を満たす形で Web Crypto API を用いて安全な暗号化を行う手順を解説しました。

この記事で実装したサンプルは、前の記事の例よりも、妥当且つ堅牢な物となっています。Web Crypto APIを使ってローカルデータを暗号化してみようという方に参考にしていただければ幸いです。

*1 パスワード認証を実装する際の、パスワードをハッシュ化して保存する時に用いる「salt」と似た役割を果たす物と言えます。

*2 そもそも「nonce」という言葉自体が「number once」つまり一度きりの数字という意味で、一意であるという性質を内包している事になります。

*3 `Math.random()` で生成した結果よりもさらに結果の予想がしにくいという事。

*4 1つの教室の中にいる人達の中で「自分と同じ誕生日の人がいる」確率は低いが、「同じ誕生日の人が二人いる」確率は直感に反してずっと高い、という事実のこと。

2019-02-08

Webアプリや拡張機能（アドオン）で、Web Crypto APIを使ってローカルに保存されるデータを暗号化する

※注記：本文末尾の「公開鍵暗号ではなく共通鍵暗号を使う理由」の説明について、2019年1月30日午前0時から21時までの間の初出時に内容の誤りがありました。また、2019年1月30日午前0時から2月5日20時頃までの間において、本文中での AES-CTR による暗号化処理が、 nonce を適切に指定していないために脆弱な状態となっていました。お詫びして訂正致します。初出時の内容のみをご覧になっていた方は、お手数ですが訂正後の説明を改めてご参照下さい。

クリアコードで主にMozilla製品のサポート業務に従事している、結城です。

FirefoxやThunderbirdがSSL/TLSで通信する際は、通信内容は自動的に暗号化されます。その一方で、Cookieやローカルストレージ、IndexedDBなどに保存されるデータは、平文のままでユーザーの環境に保存される事が多く、必要な場合はアプリ側で内容を暗号化しなくてはなりません。こういった場面でJavaScriptから使える暗号化・復号のための汎用APIが、Web Crypto APIです。

ただ、Web Crypto APIでデータを暗号化するにはある程度の知識が必要になります。「encrypt() という関数に文字列と鍵を渡したらいい感じに暗号化されて、decrypt() という関数に暗号と鍵を渡したらいい感じに復号される」というような単純な話ではないため、全く前提知識がないと、そう気軽には使えません。

この記事では、Web Crypto APIを用いたローカルデータの暗号化の基本的な手順をご紹介します。

Web Crypto APIでの暗号化の基本

Web Crypto APIでは様々な暗号方式を使えますが、それぞれ適切な用途が決まっています。一般的な「データの暗号化と復号」という場面では、以下のいずれかの暗号方式を使うことになります。

共通鍵暗号
- AES-CTR
- AES-CBC
- AES-GCM
公開鍵暗号
- RSA-OAEP

AES や RSA というのが具体的な暗号アルゴリズムの名前で、CTR、CBC、GCM というのは暗号モードの名前です。諸々の理由から、アプリ内部でローカルに保存するデータを暗号化するという場面では、~~AES-CTR~~ AES-GCM が最適と言えるでしょう（詳細は後で述べます）。

JavaScriptで書かれた実装において、暗号化したいデータは普通は文字列や配列、オブジェクトといった形式を取っていることでしょう。しかしながら、Web Crypto APIでこれらのプリミティブな値を直接暗号化する事はできません。Web Crypto APIでは基本的に、データを ArrayBuffer やTyped Arrayと呼ばれる、よりバイナリ形式に近いデータで取り扱います。そのため、これらのデータ型の概念をきちんと理解しておく必要があります。Blob, ArrayBuffer, Uint8Array, DataURI の変換という記事では、これらのデータ型の関係を図を交えて分かりやすく説明してくれていますので、Web Crypto APIを触る前にぜひ読んでおきましょう。

また、Web Crypto APIの多くの機能は非同期処理になっており、処理結果がPromiseとして得られる場合が多いです。Promiseとは、簡単に言えば以下のような物です。

Promiseは値の入れ物と言える。
- 中の値を取り出すには、promise.then(function(value) { ... }) のように、then メソッドにコールバック関数を渡してその中で受け取る必要がある。
- 中の値をすぐに取り出せるとは限らない。通信先のサーバーから結果が返ってきて初めて then メソッドのコールバック関数が呼ばれる、というような事もある。
async function() { ... } という風に async キーワードを付けて定義された関数は、非同期の関数になる。
- 非同期の関数を呼び出すと、関数の中で return した値は、呼び出した側からは常にPromiseとして受け取る事になる（関数の戻り値が常にPromiseになる）。
- 非同期の関数の中では、let value = await promise; のように書くと、その場でPromiseの中の値を取り出せる（then メソッドを使わなくてもよくなる）。

以上の事を踏まえ、実際にデータを暗号化してみることにしましょう。

なお、Web Crypto APIの入出力はPromiseになっている事が多いので、以降のサンプルはすべて以下のような非同期関数の中で実行するものとします。

(async function() {

  // ここで実行

})();

鍵の生成

Web Crypto APIでの暗号化・復号では、Web Crypto APIで生成された CryptoKey クラスのインスタンスを鍵に使います。ここでは以下の2パターンの鍵の作り方を紹介します。

ユーザーが入力したパスワードを鍵に変換する方法
完全に自動で鍵を生成する方法

パスワードを鍵に変換する

パスワードで保護されたOffice文書やPDFを取り扱う時のように、暗号化や復号の時にユーザーによるパスワードの入力を求める形にしたい場合には、入力されたパスワードを CryptoKey クラスのインスタンスに変換する操作を行います。Webブラウザで開発者用のコンソールを開いて、以下のスクリプトを実行してみると、実際に得られた AES-GCM 用の鍵がコンソールに出力されます。

// パスワードとして使う文字列。（ユーザーの入力を受け付ける）
let password = prompt('パスワードを入力して下さい'); // 例：'開けゴマ'

// 文字列をTyped Arrayに変換する。
let passwordUint8Array = (new TextEncoder()).encode(password);

// パスワードのハッシュ値を計算する。
let digest = await crypto.subtle.digest(
  // ハッシュ値の計算に用いるアルゴリズム。
  { name: 'SHA-256' },
  passwordUint8Array
);

// 生パスワードからのハッシュ値から、salt付きでハッシュ化するための素材を得る
let keyMaterial = await crypto.subtle.importKey(
  'raw',
  digest,
  { name: 'PBKDF2' },
  // 鍵のエクスポートを許可するかどうかの指定。falseでエクスポートを禁止する。
  false,
  // 鍵の用途。ここでは、「鍵の変換に使う」と指定している。
  ['deriveKey']
);

// 乱数でsaltを作成する。
let salt = crypto.getRandomValues(new Uint8Array(16));

// 素材にsaltを付与して、最終的なWeb Crypto API用の鍵に変換する。
let secretKey = await  crypto.subtle.deriveKey(
  {
    name: 'PBKDF2',
    salt,
    iterations: 100000, // ストレッチングの回数。
    hash: 'SHA-256'
  },
  keyMaterial,
  // アルゴリズム。
  { name: 'AES-GCM', length: 256 },
  // 鍵のエクスポートを禁止する。
  false,
  // 鍵の用途は、「データの暗号化と復号に使う」と指定。
  ['encrypt', 'decrypt']
);

console.log(secretKey);
// => CryptoKey { type: "secret", extractable: false, algorithm: {…}, usages: (2) […] }

パスワードから鍵への変換に際して、より安全にするためにsaltとストレッチングを使っている事に注意して下さい*1。

この使い方においては、CryptoKey クラスのインスタンスとして得られた鍵はメモリ上に一時的に保持しておくだけでよく、ログアウト時やアプリの終了時にはそのまま破棄する事になります。次回訪問時・ログイン時・アプリ起動時には、再びパスワードの入力を求め、その都度この方法で鍵へと変換します。

なお、saltは次回以降のパスワード→鍵の変換時にも必要になります。保存と復元は以下の要領で行えます。

// saltの保存。
localStorage.setItem('passwordSalt',
  JSON.stringify(Array.from(salt)));

// saltの復元。
let salt = localStorage.getItem('passwordSalt');
salt = Uint8Array.from(JSON.parse(salt));

ところで、上記の例では「平文のパスワード→SHA-256でハッシュ化→AES-GCMの鍵としてインポート」という経路で変換を行っていますが、「パスワードのハッシュ化にsaltは必要じゃないの？」と疑問に思う方もいらっしゃるかと思います。saltが必要かどうかは、ハッシュ化したパスワードを外部や第三者に読み取られる危険性を考慮しないといけないかどうかに依存します。ハッシュ化したパスワードや鍵を一旦ストレージに保存するのであればハッシュ化は必要ですが、この例のようにメモリ上でごく短時間保持されるだけの場合は必要ない、というのが筆者の考えです。ハッシュ化時にsaltを使うという事自体は以下のようにして実現できますが、ストレッチングにそれなりの時間がかかりますので、本当に必要という事が言える場合にのみ使う事をお薦めします。

鍵の自動生成

「何らかの方法で鍵を安全な場所（暗号化したデータとは別の保存先）に保管できる」という前提がある場合には、crypto.subtle.generateKey() を使って鍵を生成し、ユーザーにパスワードの入力を求めずに暗黙的に暗号化・復号を行うという事もできます。この場合、鍵は以下のように生成します。

let secretKey = await crypto.subtle.generateKey(
  // アルゴリズムと鍵長。ここでは最長の256bitを指定している。
  { name: 'AES-GCM', length: 256 },
  // 鍵のエクスポートを許可するかどうか。trueでエクスポートを許可する。
  true,
  // 鍵の用途。
  ['encrypt', 'decrypt']
);
console.log(secretKey);
// => CryptoKey { type: 'secret', extractable: true, algorithm: Object, usages: Array[2] }

生成された鍵は CryptoKey クラスのインスタンスとなっており、そのままでは永続化（保存）できませんが、以下のようにすると、JSON Web Key形式（通常のオブジェクト）として鍵をエクスポートできます。

// JSON Web Key（JWK）形式でのエクスポート。
let exportedSecretKey = await crypto.subtle.exportKey('jwk', secretKey);
console.log(exportedSecretKey);
// => Object { alg: "A256GCM", ext: true, k: "DAvha1Scb8jTqk1KUTQlMRdffegdam0AylWRbQTOOfc", key_ops: (2) […], kty: "oct" }

このようにして得られたJWK形式の鍵は、以下の手順で再び CryptoKey のインスタンスに戻す事ができます。

// JWK形式からのインポート。
let importedSecretKey = await crypto.subtle.importKey(
  'jwk',
  exportedSecretKey,
  // 鍵を生成した際の暗号アルゴリズム。
  { name: 'AES-GCM' },
  // 再エクスポートを許可するかどうかの指定。falseでエクスポートを禁止する。
  false,
  // 鍵の用途。
  ['encrypt', 'decrypt']
);
console.log(importedSecretKey);
// => CryptoKey { type: 'secret', extractable: true, algorithm: Object, usages: Array[2] }

実際には、初回訪問時・初回起動時などのタイミングで生成した鍵をエクスポートして安全な場所に補完しておき、次回訪問時・次回起動時などのタイミングでそれを読み取ってインポートし、メモリ上に鍵を復元する、といった要領で使う事になります。

データの暗号化

鍵の準備ができたらいよいよ本題の暗号化ですが、その前に、「暗号化する対象のデータ」を「暗号化できるデータ形式」に変換するという操作が必要です。

Web Crypto APIの暗号化処理は、データの入出力を ArrayBuffer やTyped Arrayの形式のみで行う仕様になっているため、どんなデータを暗号化するにせよ、何らかの方法でデータをこれらの形式に変換しなくてはなりません。文字列は前出の例の中で行っていたように、TextEncoder を使って以下のようにTyped Arrayに変換できます。

// データをTyped Arrayに変換。
let inputData = (new TextEncoder()).encode('暗号化したい文字列');
console.log(inputData);
// => Uint8Array(27) [ 230, 154, 151, 229, 143, 183, 229, 140, 150, 227, … ]

オブジェクト形式のデータであれば、この直前に「JSON.stringify() で文字列に変換する」という操作を加えればよいでしょう。

入力データが用意できたら、次は初期ベクトルの準備です。

初期ベクトルとは、AES-CBC および AES-GCM においてデータを同じ鍵で暗号化する際に、暗号文から内容の推測を困難にするために付与する値です*2。パスワードのハッシュ化に用いるsaltのようなもの、と言えば分かりやすいでしょうか。本来は一意な値である必要がありますが、ここでは話を単純にするために、とりあえず乱数を使う事にします。実際に使う時は、きちんとした初期ベクトルを生成する手順の解説も併せて参照して下さい。

// 初期ベクトルとして、8bit * 16桁 = 128bit分の領域を確保し、乱数で埋める。
let iv = crypto.getRandomValues(new Uint8Array(16));

入力データと初期ベクトルが用意できたら、ようやく暗号化です。これは以下の要領で行います。

let encryptedArrayBuffer = await crypto.subtle.encrypt(
  // 暗号アルゴリズムの指定とパラメータ。
  { name: 'AES-GCM',
    iv },
  // 事前に用意しておいた鍵。
  secretKey,
  // ArrayBufferまたはTyped Arrayに変換した入力データ。
  inputData
);
console.log(encryptedArrayBuffer);
// => ArrayBuffer { byteLength: 27 }

暗号化後のデータは、非同期に ArrayBuffer 形式で返されます。ここでは27バイトの長さがあるという事だけが分かっているため、このような表示になっています。

データを暗号化できたら、今度はこれをIndexedDBや localStorage などに格納可能な形式に変換します。例えば文字列への変換であれば、以下の手順で行えます。

let encryptedBytes = Array.from(new Uint8Array(encryptedArrayBuffer), char => String.fromCharCode(char)).join('');
console.log(encryptedBytes);
// => �����`Ù�¥ë�`û-Þm#þ'�¾��[�·�

ここでは ArrayBuffer 形式で27バイトの長さのデータとして得られた物を、8bitずつに切り分けて Unit8Array に変換し、さらにその1バイトずつを文字コードと見なして文字に変換しています。

このような文字列はBinary Stringと呼ばれ、コンソールなどに出力しても文字化けした結果になる事がほとんどのため、データを持ち回る過程で破損してしまわないよう、取り扱いには注意が必要です。安全のためには、以下のようにしてBase64エンコード済みの文字列に変換して、文字化けなどが起こりにくい安全な状態で取り回すのがお薦めです。

let encryptedBase64String = btoa(encryptedBytes);
console.log(encryptedBase64String);
// => YPgdHZgguUeHpt9FcYy2IaZTfbTNswbfn93e

AES-GCMで暗号化したデータ*3の復号には、暗号化時に使用した初期ベクトルが必要となります*4。以下のようにして、暗号化したデータとセットで保存しておきます。

localStorage.setItem('encryptedData',
  JSON.stringify({
    data: encryptedBase64String,
    iv:   Array.from(iv)
  }));

データの復号

次は、暗号化済みのデータから元のデータを取り出してみましょう。

Web Crypto APIの復号処理も、暗号化処理と同様、データの入出力を ArrayBuffer やTyped Arrayの形式のみで行う仕様になっています。先の例と逆の操作を行い、まずは暗号化されたデータを ArrayBuffer またはTyped Array形式に変換します。

let encryptedData = JSON.parse(localStorage.getItem('encryptedData'));
let encryptedBase64String = encryptedData.data;
// 通常のArrayとして保存しておいた初期ベクトルをUint8Arrayに戻す
let iv = Uint8Array.from(encryptedData.iv);

// Base64エンコードされた文字列→Binary String
let encryptedBytes = atob(encryptedBase64String);

// Binary String→Typed Array
let encryptedData = Uint8Array.from(encryptedBytes.split(''), char => char.charCodeAt(0));

データの準備ができたら、いよいよ復号です。これは以下の手順で行います。

let decryptedArrayBuffer = await crypto.subtle.decrypt(
  // 暗号アルゴリズムの指定とパラメータ。暗号化時と同じ内容を指定する。
  { name: 'AES-GCM',
    iv },
  // 暗号化の際に使用した物と同じ鍵。
  secretKey,
  // ArrayBufferまたはTyped Arrayに変換した暗号化済みデータ。
  encryptedData
);
console.log(decryptedArrayBuffer);
// => ArrayBuffer { byteLength: 27 }

復号の時には、暗号化時と同じパラメータ、同じ鍵が必要である点に注意して下さい。何らかのトラブルで鍵や初期ベクトルを喪失してしまうと、元のデータは永遠に取り出せなくなってしまいます。

復号されたデータは ArrayBuffer 形式になっています。これを通常の文字列へ変換するには以下のように操作します。

let decryptedString = (new TextDecoder()).decode(new Uint8Array(decryptedArrayBuffer));
console.log(decryptedString);
// => '暗号化したい文字列'

無事に、暗号化する前の平文であった「暗号化したい文字列」という文字列を取り出す事ができました。

疑問

なぜ暗号アルゴリズムに `AES-CTR` `AES-GCM` を使うのか？

冒頭で、Web Crypto APIでデータの暗号化と復号に使えるアルゴリズムは4つあると述べましたが、本記事ではその中で何故 ~~AES-CTR~~ AES-GCM を選択しているのかについて、疑問に思う人もいるでしょう。

暗号アルゴリズムには、大別して「共通鍵暗号」と「公開鍵暗号」の2種類があります。共通鍵暗号は暗号化と復号に同じ鍵を使う方式、公開鍵暗号は暗号化と復号で異なる鍵を使う方式です。公開鍵暗号は~~「暗号化したデータと、それを復号する鍵の両方を、信頼できない通信経路で送り、受信側で復号する」~~「暗号化と復号を別々の所で（別々の人が）行う」という場面に適しています。逆に言うと、「アプリ内部でローカルに保存するデータを暗号化する」という場面のように、~~データや鍵が信頼できない通信経路を通る事がないのであれば~~暗号化も復号も同じ所で行うのであれば、公開鍵暗号（RSA-OAEP）ではなく共通鍵暗号（AES-* 系）で充分に安全だと言えます。

また、AES-* 系の中で AES-CTR を選択する理由は、他の2つが「初期ベクトル」という、鍵とは別の使い捨ての情報を組み合わせて使う（「鍵」と「初期ベクトル」の両方が揃って初めて暗号を復号できる）方式だからです。

AES-CBC と AES-GCM は、1回1回の暗号化・復号ごとに初期ベクトルを変えることで安全性を高める前提の方式です。ネットワークを通じてサーバーとクライアントの間でデータをやりとりするという場面では、暗号化して送られたデータはすぐに受け手の側で復号されます。このようなケースでは、同じ暗号データを何度も復号するという事は起こり得ないため、初期ベクトルは使い捨てにできます。

一方、アプリケーションのローカルデータを暗号化するという場面では、暗号化して保存されたデータを何度も復号する必要があります。データの復号には暗号化した時と同じ初期ベクトルが必要になるため、必然的に、初期ベクトルは使い捨てにできず、何度も使い回す事になります。本当は怖いAES-GCMの話 - ぼちぼち日記などの解説記事で詳しく述べられていますが、初期ベクトルを使い回した場合これらの暗号アルゴリズムは非常に脆弱な物となり、「情報の漏洩を防ぐ」という目的を達成できなくなってしまいます。

~~以上の理由から、このような場面では初期ベクトルを用いない方式である AES-CTR が最適だと言える訳です。~~

AES-* 系の中で AES-GCM を選択した理由は、他の2つには以下のようなデメリットがあるからです。

AES-CTR: カウンタの取り扱いが初期ベクトルに比べて面倒。
AES-CBC: 暗号化の並列処理ができない＝暗号化処理に時間がかかる可能性がある。

Webアプリなどでパスワード認証を実装する際には、パスワードをそのまま保存するのはなく、非可逆的に変換した結果であるハッシュ値を保存する事が一般に推奨されています。この時には、ハッシュ値から元のパスワードを推測しにくくするために、パスワードに余計なデータを加えてからハッシュ化するのが一般的です。この追加するデータを「塩をまぶす」ことに例えてsaltと呼びます。

これと同様にAESにおいても、データには必ずsaltのような一意なデータを付与してから暗号化するようになっています。これは仕様上秘密である必要はなく、一意でさえあればいいという事になっています。AES-CBC および AES-GCM では、そのようなsalt相当のデータを「初期ベクトル」と呼んでいます。

一方、AES-CTR ではsaltにあたるデータを「カウンタ」の一部として与えます。カウンタは最大で16byte＝128bitの長さを指定できますが、そのうち一部をnonce（一意な数字）、残りを0からカウントアップする文字通りのカウンタとして使う事になっています。例えば128bit中の64bitをnonce、残り64bitをカウントアップ部にする、といった要領です。……という具合に長々説明している事自体に顕れていますが、「一意な値を1つ用意するだけでいい」という初期ベクトルに比べて、カウンタは取り扱いが若干ややこしいという事自体が AES-CTR のデメリットと言えます。

では、AES-CTR 以外なら AES-CBC でも AES-GCM でもどちらでも良いのでは？という話になりそうですが、AES-CBC には処理を並列化できないという原理上の制限があります。AES-CTR や AES-GCM にはそのような制限が無く、上手く実装されたソフトウェアであれば、マルチスレッドを活用した並列処理で高速ができます*5。

以上の理由から、この3つの選択肢の中では総合的に見て AES-GCM が最もメリットが大きいと筆者は考えています。

なお、本文中の例のように乱数を使って初期ベクトルを生成するのは、本来は望ましい事ではありません。実際の実装にそのまま組み込む前には、よりセキュアなきちんとした初期ベクトルを生成する手順の解説も併せてご参照下さい。

自動生成した鍵はどこに保存すればよいのか？

鍵を自動生成して暗黙的に暗号化・復号を行うという動作をさせたい場合、鍵は暗号化されたデータとは別の安全な場所に置く必要があります。生の鍵を暗号化されたデータと同じ場所に保存してしまっては、暗号化の意味がありません

鍵の置き場所としては、例えば以下のような例が考えられます。

ファイルとして保存した物をUSBメモリに書き込み、そのUSBメモリを物理的な鍵として使う。
QRコードに変換して表示した物をスマートフォンで撮影し、そのスマートフォンを物理的な鍵として使う。
鍵をICカードに保存し、その都度鍵をICカードリーダー経由で読み取る事として、ICカードそのものを物理的な鍵として使う。
パスワードマネージャの中にパスワードの一種として保管し、パスワードマネージャのマスターパスワードで保護する。

こういった方法で鍵を保存しておくやり方と、都度パスワードの入力を求めるやり方のどちらが安全かについては、専門家の間でも意見が分かれているようです。鍵をデバイス上に保存しておくやり方には、当然ながら、デバイスそのものが盗難された場合にデータを保護できなくなるというリスクがあります。一方で、パスワード入力を頻繁に求める方法は、パスワードの入力の機会が増えるため、キーロガーやショルダーハッキングといった攻撃に遭うリスクが増大します。パスワードマネージャとマスターパスワードを使う方法は、両者の弱点を補うものと言えます。

まとめ

以上、Web Crypto APIを使ってJavaScriptでローカルデータを暗号化する手順をご紹介しました。個人情報のようにクリティカルな情報を取り扱うWebアプリや拡張機能を開発する場合に、参考にしてみて下さい。

*1 saltというとハッシュ化した後のパスワードの流出に備えての物のように思えますが、ここでは暗号化されたデータが流出した時の保護を目的としています。ハッシュ化した後のパスワードを保存していない場合、ハッシュ化されたパスワードの流出については考えなくても良い（JavaScriptのコードから機械語への変換のされ方を制御したり、メモリ上の情報を再配置したり、といった低レベルの対策を取れないJavaScriptという言語の特性上、サイドチャネル攻撃で平文のパスワードやハッシュ化したパスワードを読み取られる事を警戒する事はアプリケーション実装者の側では不可能で、JavaScriptの実行エンジンの実装側が責任を持つことになります。また、平文のパスワードが流出しないようXSSの対策は充分に取られていることを前提とします）のですが、saltを使用していないと、攻撃者は生パスワードからのハッシュ値の計算を省略できるため、暗号化済みデータに対する攻撃がより成功しやすくなります。saltを付与すると、攻撃者はそのような最適化を行えなくなり、結果的に、暗号化されたデータのみが流出した時の攻撃に対する耐性が高まります。

*2 `AES-CBC`、`AES-GCM`だけでなく、`AES-CTR` においても暗号化時のパラメータの1つである「カウンタ」の一部としてこれに相当する情報を指定する必要があります。

*3 `AES-CBC` も同様。

*4 よって、実質的には初期ベクトルも「暗号を解く鍵」の一部と言えるかもしれません。

*5 実際にブラウザのWeb Crypto APIの実装がそのように最適化されているかどうかは、また別の話になります。

この記事の続き

2019-02-08: Web Crypto API で AES-CBC や AES-GCM の初期ベクトルをより安全に生成する

2019-01-30

Gecko Embedded: 60ESR対応のフィードバック

60ESR対応フィードバックの顛末

クリアコードでは Gecko（Firefox）を組み込み機器向けに移植する取り組みを行っています。

Gecko Embedded ESR60

この対応にあたっては OSSystems/meta-browser というYoctoレイヤをフォークして作業を行っていますが、対応が落ちついたバージョンについてはアップストリーム（OSSystems/meta-browser）に成果をフィードバックしています。例えば52ESRへのメジャーバージョンアップの対応はクリアコードの成果が元となっています。

さて、60ESRへのメジャーバージョンアップ対応についてもフィードバックをしていたのですが、最後まで自分たちでは解決できなかった問題が一つありました。今回は、OSSにはこんなフィードバックの仕方もあるのだという事例として紹介したいと思います。

meta-rustへの依存

52ESRから60ESRへの更新にあたって一番大きな問題となったのが、Firefox本体にRustで書かれたコードが導入された点です。通常、Firefoxをビルドする際にはrustupというコマンドでツールチェーンを導入します。クリアコードで60ESRのYoctoへのポーティングを開始した当初も、Rustのツールチェーンについてはrustupで導入したものを使用していました。

しかし、Yoctoでは一貫したクロスビルド環境を提供するために、ツールチェーン類も全てYoctoでビルドするのが基本です。このため、RustのツールチェーンについてもYoctoでビルドした物を使う方がよりYoctoらしいと言えます。調べてみたところ、既にmeta-rustというYoctoレイヤが存在していることが分かりましたので、これを利用することとしました。

ターゲット環境用のlibstd-rsを参照できない問題

meta-rustへの対応作業を進めていく中で、Firefoxのビルドシステムがターゲット環境用のlibstd-rsを発見してくれないという問題に遭遇しました。しかし、我々はRustのビルドの仕組みには不慣れであったため、それがどこの問題であるかをはっきりと切り分けることができていませんでした。一方で、meta-rustでのビルドの際に、libstd-rsのみビルド済みのものを導入することで、ひとまずこの問題を突破できることが分かりました。

その他発生していた問題については解決することができ、Firefoxのビルドが全て通るところまでは到達しました。

上記の回避策が正しい修正方法ではないということは分かっていたのですが、ではどこでどう修正をするのが正しいのかという点については、少し調査をしてみた限りでは判断がつかない状態でした。時間をかければいずれは解明できるのは間違いないのですが、我々には他にも取り組まなければいけない問題が山積していたため、その時点では、これ以上時間をかけることはできませんでした。

ひとまずOSSystems/meta-browserに対しては「こういう問題があってまだ調査中だから、マージするのはもうちょっと待ってね」という形でpull requestを投げておきました。

https://github.com/OSSystems/meta-browser/pull/160

未解決のままマージされる

ところがしばらくすると、 Yocto/Open EmbeddedプロジェクトのKhem Raj氏が、OSSystems/meta-browserのメンテナであるOtavio Salvador氏に働きかけ、上記のlibstd-rsの問題が未解決であるにも関わらず、このpull requestをmasterにマージしてしまいました。上記の回避策はmeta-rustにはマージされていませんので、そのままではビルドを通すことすらできません。私の目から見るとちょっとした暴挙にも見えたのですが、状況についてはKhem Raj氏にも間違いなく伝わっているので、何か算段があるのだろうということでしばらく経過を見守ることにしました。

あとから分かったのですが、ちょうどYoctoの次のリリース向けの開発が始まるタイミングであったため、とりあえずmasterにマージしてCIに組み込んでしまってからの方が問題に取り組みやすいという事情があったようです。しばらく時間はかかりましたが、無事Khem Raj氏から問題を解決するpull requestが投げられました。

https://github.com/OSSystems/meta-browser/pull/202

我々の方ではmeta-rustとmeta-browserのどちらで対処すべき問題なのかすら切り分けることができていませんでしたが、meta-browserで対処すべき問題だったようです。

本事例の感想

今回の件については、以下のような懸念から、ともすればフィードバックを躊躇してしまいがちな事例ではないかと思います。

このような中途半端なpull requestを送ると、アップストリームの開発者から罵倒されたりはしないか?
「この程度の問題すら自分たちで解決できていない」ということを晒すことになるので、恥ずかしいなぁ。

前者については、確かにプロジェクトによってはそのようなpull requestが歓迎されないこともあるでしょう。とはいえ、今回の事例についてはそこそこ工数がかかる60ESRポーティング作業を粗方済ませており、その成果が有益と感じる開発者も多いはずです。また、後者については「聞くのは一時の恥、聞かぬは一生の恥」の良い事例ではないかと思います。結果的にはアップストリームの開発者の協力を得て問題を解決することもできて、成果をより多くの人に使ってもらえる状態にできたので、中途半端でもフィードバックをしておいて良かったなと感じています。

皆さんも「この程度のものは誰の役にも立たないだろう」「この程度のものを世に出すのは恥ずかしい」などと一人で勝手に思い込まないで、手元にある成果を積極的に公開してみてはいかがでしょうか？ひょっとすると、それが世界のどこかで悩んでいる開発者の問題を解決して、感謝してもらえるかもしれませんよ。

2019-01-24

階層構造データ用のGroongaのスキーマ設計方法

Groongaを開発している須藤です。

GroongaにはRDBMS（MySQLやMariaDBやPostgreSQLなど）と同じようにテーブルとカラムがあり、それらに構造化したデータを保存します。しかし、用途が違う（Groongaは検索がメインでRDBMSは検索だけでなくデータの管理も大事）のでスキーマの設計方法はRDBMSでの設計方法と違う部分があります。そのため、RDBMSのスキーマの設計に慣れている人でもGroongaのスキーマをうまく設計できないことがあります。

この記事では少し複雑なデータをGroongaで検索するためのスキーマの設計方法を説明します。

なお、ここで使っている設計を実装したGroongaコマンドはgroonga/groonga-schema-design-exampleにあります。実際に試してみると理解が深まるはずなのでぜひ試してみてください。

データ

まず、検索対象のデータを説明します。

検索対象は次の2つです。

論文
書籍

それぞれのデータがもつ情報は同じものもあれば違うものもあります。

たとえば、「タイトル」は「論文」にも「書籍」にもあります。

しかし、「雑誌」は「論文」だけにあり、「書籍」にはありません。（論文が収録されている雑誌の情報です。）

また、次のような親子関係があります。「論文」はいくつも階層になった親があります。書籍は複数の親を持ちます。少し複雑なデータですね！

出版元
- 雑誌
  - 号
    - 論文
出版社
- 書籍
親カテゴリー
- 子カテゴリー
  - 書籍
シリーズ
- 書籍（シリーズに属さない書籍もある）

検索方法

この少し複雑なデータに対して次のような検索をするためのスキーマを設計します。

「論文」と「書籍」を横断全文検索
複数カラムで横断全文検索
- たとえば「タイトル」と「著者」で横断全文検索
「論文」だけを全文検索
「書籍」だけを全文検索
検索結果を任意の親でドリルダウン
- たとえば「出版元」でドリルダウン
指定した親に属する子レコードを検索
- たとえば「出版元」が発行している「雑誌」を検索

設計の概要

Groongaでは検索対象を1つのテーブルに集めることが重要です。すごく重要です。本当に重要です。

今回のケースでは「論文」と「書籍」が検索対象なので、それらを同じテーブルに格納します。今回の設計では2つ合わせて「文献」と扱うことにし、Literatureテーブルを作成します。

Literatureテーブルの定義は次の通りです。

table_create Literature TABLE_HASH_KEY ShortText

主キーに設定する値は「論文」と「書籍」全体で一意にする必要があることに注意してください。「論文」ではISSNとなにかを使って、「書籍」ではISBNを使うと一意にできる気がします。ここでは、どうにかして一意にできる前提で設計を進めます。

LiteratureでTABLE_HASH_KEYを使っているのは、今回のケースでは主キーで完全一致検索できれば十分だからです。

参考：TABLE_*の特徴の違い

「論文」と「書籍」を同じテーブルに入れるため、区別するための情報も格納します。この設計ではtypeカラムを追加し、そこに"paper"（「論文」）または"book"（「書籍」）を格納することにします。

typeの型はShortTextでもよいのですが、検索効率および空間効率を考慮してTypes型にします。Typesはこの後にすぐ定義しますが、ただのテーブルです。カラムの型にテーブルを指定すると実際のデータ（"paper"と"book"）はTypesテーブルの主キーに入ります。カラムにはTypesテーブルの該当レコードのID（1と2とか）が入ります。各カラムに入るデータは単なる数値なので比較も高速（検索効率がよい）ですし、サイズも小さい（空間効率がよい）です。

column_create Literature type COLUMN_SCALAR Types

Typesは次のように定義したテーブルです。主キーには"paper"または"book"を設定します。主キーは完全一致だけできれば十分なのでTABLE_HASH_KEYにしています。

# "paper"または"book"
table_create Types TABLE_HASH_KEY ShortText

Literatureテーブルにレコードを追加したときにこのテーブルにも自動でレコードが追加されるので明示的に管理する必要はありません。typeカラムに"paper"を格納しようとすれば自動でTypesテーブルに主キーが"paper"のレコードが追加されます。すでにレコードがあればそのレコードを使います。つまり、typeカラムの型にShortTextを使ったときと同じように使えます。

型にテーブルを指定する方法はGroongaではよく使う方法です。用途はいろいろありますが、この使い方はRDBMSでいうenum型のようなものを実現するための使い方です。enum型のように値を制限することはできませんが。。。他の用途は後ででてきます。

Literatureに「論文」と「書籍」の情報をすべて格納します。中には「論文」にしかない情報あるいは「書籍」にしかない情報も存在します。存在しない情報は該当カラムに値を設定しません。

たとえば、「子カテゴリー」情報は「書籍」にしか存在しないので「論文」用のレコードを格納するときは「子カテゴリー」情報のカラムに値を設定しません。

GroongaにはNULLはないので、値を設定しなかったカラムの値はその型の初期値になっています。たとえば、ShortTextなら空文字列ですし、Int32なら0です。

今回の設計ではLiteratureテーブルには次のカラムを用意します。

type (Types): 種類（「論文」（"paper"）か「書籍」（"book"））
title (ShortText): タイトル
authors (Authors): 著者（複数）
volume (Volumes): 号（「論文」のみ）
book_publisher (BookPublishers): 出版社（「書籍」のみ）
child_category (ChildCategories): 子カテゴリー（「書籍」のみ）
series (Series): シリーズ（「書籍」のみ）

titleとauthorsは全文検索のためのカラムです。

検索項目を増やす場合は単にカラムを増やしてインデックスを追加するだけです。追加方法はauthorsを例にして後述します。全文検索用のスキーマ設計の方法もあわせて説明します。

以下のカラムはドリルダウンのためのカラムです。

volume
book_publisher
child_category
series

これらの情報で親子関係を表現します。親の親がある場合でもGroongaでは各レコードは直接の親だけを格納していれば十分です。各レコードに親の情報だけでなく、親の親の情報も格納する必要はありません。これは正規化した状態のままでよいということです。正規化した状態のままで扱えるため情報の管理が楽です。たとえば、「雑誌」の名前を変更する時は雑誌テーブルの該当レコードを変更するだけでよく、「雑誌」情報を持っているすべてのレコードを変更する必要はないということです。

ドリルダウン用のスキーマ設計は後述します。

以上が設計の概要です。ポイントは次の通りです。

横断検索対象の情報はすべて1つのテーブルにまとめる
対象の種類を区別する必要がある場合はカラムにその情報を入れて区別する
検索条件に使いたい情報を増やす場合はテーブルにカラムを追加する
特定のレコードにしかない情報（「論文」にしかない情報や「書籍」にしかない情報）でもカラムを追加してよい
- 情報が存在しないレコードでは単にカラムに値を設定しない
ドリルダウン用の情報は正規化したままでよい

検索項目の追加

著者情報を例に検索項目を追加する方法を示します。

著者は複数存在するので次のようにCOLUMN_VECTORで定義します。

column_create Literature authors COLUMN_VECTOR Authors

型はAuthorsテーブルにしていますがShortTextにしてもよいです。テーブルを使っている理由はtypeカラムのときと同じで検索効率および空間効率がよいからです。著者でドリルダウンするなら（今回は説明しません）テーブルにするべきです。計算効率が全然違います。

今回の設計では著者名を主キーにします。

table_create Authors TABLE_HASH_KEY ShortText

同姓同名の著者を別人として扱いたい場合は著者IDを振ってnameカラムを追加します。今回の説明ではそこは本質ではないので単に著者名を主キーにしています。

著者名で完全一致検索する場合は次のようにすれば効率よく検索できます。

select \
  --table Literature \
  --query 'authors:@山田太郎'

著者名で全文検索する場合は追加のインデックスが必要です。

まず、Authors._keyで全文検索するためのインデックスが必要です。

table_create Terms TABLE_PAT_KEY ShortText \
  --default_tokenizer TokenNgram \
  --normalizer NormalizerNFKC100

column_create Terms authors_key \
  COLUMN_INDEX|WITH_POSITION Authors _key

Termsテーブルは他の全文検索用インデックスでも共有可能です。共有するとトークン（全文検索用にテキストを分割したもの）の情報を共有でき、DB全体の空間効率がよくなります。

TermsテーブルではTokenNgramとNormalizerNFKC100を使っています。他にも指定できるものはありますが、これらがバランスがよいので、まずはこれから始めるのがよいです。必要なら後で調整するとよいです。

Terms.authors_keyは全文検索用のインデックスなのでWITH_POSITIONを指定しています。

これで、著者名で全文検索して該当著者を検索できるようになります。しかし、その著者から該当「論文」を見つけることはまだできません。追加で次のインデックスが必要です。

column_create Authors literature_authors \
  COLUMN_INDEX Literature authors

このインデックスはどの著者がどの「論文」の著者かを高速に検索するためのインデックスです。このインデックスも作ることで「著者名で全文検索して著者を見つけ、さらに、その著者がどの論文の著者かを検索する」を実現できます。

検索クエリーは次のようになります。完全一致検索のときとの違いはauthors:@に._keyが加わってauthors._key:@となっているところです。

select \
  --table Literature \
  --query 'authors._key:@山田'

各インデックスカラムの役割を図示すると次の通りです。

ネストした検索

authorsは複数の著者が存在するためCOLUMN_VECTORを使っています。また、重複した情報が多くなるため型にテーブルを利用しました。そのため、少し複雑になっています。

titleのように単純な情報の場合は次のようにするだけで十分です。

column_create Literature title COLUMN_SCALAR ShortText
column_create Terms literature_title \
  COLUMN_INDEX|WITH_POSITION Literature title

titleとauthorsを両方検索対象にするには次のようにします。

select \
  --table Literature \
  --match_columns 'title || authors._key' \
  --query 'キーワード'

「論文」（typeが"paper"）だけを検索する場合は次のように--filterで条件を追加します。selectでは--queryと--filterで条件を指定できますが、--queryはユーザーからの入力をそのまま入れる用のオプションで--filterはシステムでより詳細な条件を指定する用のオプションです。

select \
  --table Literature \
  --match_columns 'title || authors._key' \
  --query 'キーワード' \
  --filter 'type == "paper"'

参考：select

1段のドリルダウンの実現

検索対象のデータには2段以上の親子関係のドリルダウンがありますが、まずは1段の親子関係のドリルダウンの実現方法について説明します。

例として次の親子関係のドリルダウンの実現方法について説明します。

号
- 論文

効率的なドリルダウンを実現するためにテーブルを型にしたカラムを作成します。（enum型っぽい使い方とは別の型にテーブルを使う使い方。）

今回の設計では「号」用にVolumesテーブルを作成します。

table_create Volumes TABLE_HASH_KEY ShortText

「論文」はLiteratureテーブルなので、Literatureテーブルにvolumeカラムを作成します。型はVolumesテーブルです。

column_create Literature volume COLUMN_SCALAR Volumes

これでvolumeカラムで効率的にドリルダウンできます。次のようにすれば、「号」でドリルダウンし、その「号」には何件の「論文」があるかを検索できます。

select \
  --table Literature \
  --drilldowns[volumes].keys 'volume' \
  --drilldowns[volumes].output_columns '_key,_nsubrecs'

図示すると次の通りです。

1段のドリルダウン

次の親子関係も同様に実現できます。

出版社
- 書籍
シリーズ
- 書籍（シリーズに属さない書籍もある）

2段以上のドリルダウンの実現

続いて2段以上の親子関係のドリルダウンの実現方法について説明します。

まずは、次の2段のケースについて説明します。

雑誌
- 号
  - 論文

その後、次の3段のケースについて説明します。

出版元
- 雑誌
  - 号
    - 論文

2段の場合もテーブルを型にしたカラムを作成するのは同じです。

今回の設計では「雑誌」用にMagazinesテーブルを作成します。

table_create Magazines TABLE_HASH_KEY ShortText

「号」が所属する「雑誌」を格納するカラムをVolumesテーブルに追加します。

column_create Volumes magazine COLUMN_SCALAR Magazines

これで「号」から「雑誌」をたどることができます。

「号」と「雑誌」でドリルダウンするには次のようにします。ポイントは、.tableでvolumesを指定しているところと、calc_target・calc_typesです。

select \
  --table Literature \
  --drilldowns[volumes].keys 'volume' \
  --drilldowns[volumes].output_columns '_key,_nsubrecs' \
  --drilldowns[magazines].table 'volumes' \
  --drilldowns[magazines].keys 'magazine' \
  --drilldowns[magazines].calc_target '_nsubrecs' \
  --drilldowns[magazines].calc_types 'SUM' \
  --drilldowns[magazines].output_columns '_key,_sum'

--drilldowns[${LABEL}]は高度なドリルダウンのためのパラメーターです。

参考：高度なドリルダウン関連のパラメーター

このselectでは以下の2つのドリルダウンを実行します。

--drilldowns[volumes]: 「号」でドリルダウン
--drilldowns[magazines]: 「雑誌」でドリルダウン

--drilldowns[magazines].tableで他のドリルダウンの結果を指定できます。指定するとドリルダウン結果をさらにドリルダウンできます。今回のように親子関係がある場合は子のドリルダウン結果から親のドリルダウン結果を計算します。

ただ、普通にドリルダウンすると、カウントした件数は「論文」の件数ではなく、「号」の件数になります。孫（「論文」）でドリルダウンしているのではなく、子（「号」）でドリルダウンしているからです。孫（「論文」）の件数をカウントするには子（「号」）でカウントした件数をさらにカウントする。その設定が次のパラメーターです。

--drilldowns[magazines].calc_target '_nsubrecs'
--drilldowns[magazines].calc_types 'SUM'

_nsubrecsには子（「号」）でカウントした孫（「論文」）の件数が入っています。それのSUM（総計）を計算するので孫の件数になります。出力する時は_nsubrecsではなく_sumで参照します。

--drilldowns[magazines].output_columns '_key,_sum'

図示すると次の通りです。

2段のドリルダウン

3段になった次のケースも同様です。

出版元
- 雑誌
  - 号
    - 論文

まず、出版元を効率よくドリルダウンするためにPaperPublishersテーブルを作ります。

table_create PaperPublishers TABLE_HASH_KEY ShortText

Magazinesテーブル（「雑誌」）に出版元を格納するカラムを追加します。

column_create Magazines publisher COLUMN_SCALAR PaperPublishers

これで「雑誌」から「出版元」をたどることができます。

「号」と「雑誌」と「出版元」でドリルダウンするには次のようにします。ポイントは、「出版元」のドリルダウンのcalc_targetで_nsubrecsではなく_sumを使っているところです。「出版元」のドリルダウンで「論文」の件数をカウントするには「雑誌」のドリルダウンでカウント済みの「論文」の件数の総計を計算します。そのカウント済みの「論文」の件数が_nsubrecsではなく_sumにあるので_sumを使います。

select \
  --table Literature \
  --drilldowns[volumes].keys 'volume' \
  --drilldowns[volumes].output_columns '_key,_nsubrecs' \
  --drilldowns[magazines].table 'volumes' \
  --drilldowns[magazines].keys 'magazine' \
  --drilldowns[magazines].calc_target '_nsubrecs' \
  --drilldowns[magazines].calc_types 'SUM' \
  --drilldowns[magazines].output_columns '_key,_sum' \
  --drilldowns[paper_publishers].table 'magazines' \
  --drilldowns[paper_publishers].keys 'publisher' \
  --drilldowns[paper_publishers].calc_target '_sum' \
  --drilldowns[paper_publishers].calc_types 'SUM' \
  --drilldowns[paper_publishers].output_columns '_key,_sum'

図示すると次の通りです。

3段のドリルダウン

次のケースも同様に実現できる。

親カテゴリ
- 子カテゴリ
  - 書籍

子の一覧

親子階層の情報を使って子のレコードを検索する方法を説明します。

ここでは、対象の「出版元」内の「雑誌」の一覧を返すケースを例にして説明します。

まず、対象の「出版元」を絞り込む必要があります。ここでは「出版元」の名前（主キーに入っています）を全文検索して絞り込むとします。

全文検索用のインデックスのテーブルはAuthors._key用に作ったTermsテーブルを流用します。

column_create Terms paper_publishers_key \
  COLUMN_INDEX|WITH_POSITION PaperPublishers _key

これで「出版元」の名前で全文検索できます。しかし、authorsのときと同じで、「出版元」は絞り込めますが、絞り込んだ「出版元」を元に「雑誌」を絞り込むことはできません。「雑誌」も絞り込めるようにするには追加で次のインデックスが必要です。

column_create PaperPublishers magazines_publisher \
  COLUMN_INDEX Magazines publisher

このインデックスは「出版元」をキーにどの「雑誌」がその「出版元」を参照しているかを高速に検索するためのインデックスです。このインデックスがあることで、絞り込んだ「出版元」を元に「雑誌」を絞り込めます。

次のようなクエリーで「出版元」の名前で全文検索し、絞り込んだ「出版元」が発行している「雑誌」を出力できます。

select \
  --table Magazines \
  --match_columns 'publisher._key' \
  --query 'おもしろ雑誌' \
  --output_columns '_key, publisher._key'

他の親子関係のケースも同様に実現できます。

まとめ

Groongaで以下の機能を効率的に実現するためのスキーマ設計方法について説明しました。

「論文」と「書籍」を横断全文検索
複数カラムで横断全文検索
- たとえば「タイトル」と「著者」で横断全文検索
「論文」だけを全文検索
「書籍」だけを全文検索
検索結果を任意の親でドリルダウン
- たとえば「出版元」でドリルダウン
指定した親に属する子レコードを検索
- たとえば「出版元」が発行している「雑誌」を検索

今回の設計を実装したGroongaコマンドはgroonga/groonga-schema-design-exampleにあります。実際に試してみると理解が深まるはずなのでぜひ試してみてください。

クリアコードではGroongaのスキーマ設計もサポートしています。Groongaをもっと活用したい方はお問い合わせください。

2019-01-16

«前10日分

年・日ごとに見る

2008|05|06|07|08|09|10|11|12|

2009|01|02|03|04|05|06|07|08|09|10|11|12|

2010|01|02|03|04|05|06|07|08|09|10|11|12|

2011|01|02|03|04|05|06|07|08|09|10|11|12|

2012|01|02|03|04|05|06|07|08|09|10|11|12|

2013|01|02|03|04|05|06|07|08|09|10|11|12|

2014|01|02|03|04|05|06|07|08|09|10|11|12|

2015|01|02|03|04|05|06|07|08|09|10|11|12|

2016|01|02|03|04|05|06|07|08|09|10|11|12|

2017|01|02|03|04|05|06|07|08|09|10|11|12|

2018|01|02|03|04|05|06|07|08|09|10|11|12|

2019|01|02|03|04|

ククログの記事はCC BY-SA 4.0とGFDLのデュアルライセンスで自由に利用できます。
クリアコードはプログラミングが楽しいソフトウェア開発者を1名募集しています。
クリアコードは「クリアコードをいい感じにする人」を1名募集しています。
クリアコードはフリーソフトウェア開発で培った技術力を提供しています。特にMozilla製品（Mozilla FirefoxとMozilla Thunderbird）とRubyとGroonga（全文検索）に関連した開発を得意としています。

パッチが投入されるまでの経緯

テストは目的ごとに必要

まとめ

関連記事

内容

RubyData Workshop

まとめ

関連記事

ソートアルゴリズムの効率とは別の話

タブの並べ替えには手間がかかる

ソートと同時にタブを移動するのではどうか？

diffのアルゴリズムを応用する

JavaScriptでのdiffの実装

diffのアルゴリズムを使ったタブの並べ替え

まとめ

関連記事

第一報〜状況確認〜バイナリ公開停止

さらなる状況確認

アップロード前のファイルがマルウェア判定された場合の対応

Microsoftへの連絡

報告者への連絡と、追加の確認

安全確認〜再公開

まとめ

関連記事

関連記事

問題の状況とその原因

回避方法

修正の状況

まとめ

関連記事

望ましい初期ベクトルとは？

JavaScriptで任意の桁数のカウンタを実装する

固定部とカウンタから初期ベクトルを組み立てる形で AES-GCM を使う

まとめ

関連記事

Web Crypto APIでの暗号化の基本

鍵の生成

パスワードを鍵に変換する

鍵の自動生成

データの暗号化

データの復号

疑問

なぜ暗号アルゴリズムに AES-CTR AES-GCM を使うのか？

自動生成した鍵はどこに保存すればよいのか？

まとめ

この記事の続き

関連記事

60ESR対応フィードバックの顛末

meta-rustへの依存

ターゲット環境用のlibstd-rsを参照できない問題

未解決のままマージされる

本事例の感想

関連記事

データ

検索方法

設計の概要

検索項目の追加

1段のドリルダウンの実現

2段以上のドリルダウンの実現

子の一覧

まとめ

関連記事

固定部とカウンタから初期ベクトルを組み立てる形で `AES-GCM` を使う

なぜ暗号アルゴリズムに `AES-CTR` `AES-GCM` を使うのか？