Windows could not update the computer’s boot configuration

Windows Server 2016 が GA になったので、週末を利用して、仕事で使っているマシン 2 台の OS を Windows Server 2016 TP5 から RTM に入れ替えたのですが、インストーラーの怪しげな動作でハマったので書いておきます。強引にインストールは終わらせましたが、完全に直っていない上に根本原因が確認できていないので、時間を見つけて調べて追記する予定です。

(2016/10/30 追記)
最終確認はまだですが、NVRAM へのアクセスが失敗していることが原因っぽいです。(詳細は後述)

インストールを行った二台は HP Z420 Workstation と HP Z440 Workstation。前者がメインの開発機で、コードを書いてビルドする以外に、デバッグ用の Hyper-V 仮想マシンを動かしたり、メールを書いたりもします。後者はサブの開発機で、ほぼビルドと仮想マシンのみ。なお Windows 10 ではなく Server 2016 を入れるのは、Universal App などの煩わしい機能が嫌いだからです。サーバー SKU おすすめです。

家で使うマシンも仕事のマシンも同じですが、OS の入れ替えでは常にクリーン インストールを行います。インプレースアップグレードはいまいち動作が信用できないのです。

作業は、サブ機の Z440 から行いました。これには光学ドライブがないので、USB ドライブで Windows PE を起動して、別の USB ドライブに入れておいた Windows Server 2016 のインストーラー (MSDN からダウンロードした ISO を単にコピーしたもの) である setup.exe を起動して行います。前の OS が入っていたパーティションを消して、新しくパーティションを作って入れるだけです。作業としては普通です。

Z440 の作業は何の問題もなかったのですが、同じ USB ドライブを使って Z420 に Server 2016 をインストールしたところ、インストールの最後のフェーズで "Windows could not update the computer’s boot configuration. Installation cannot proceed." が出ました。

01-error
じゃじゃーん

これけっこう深刻なエラー・・・。メッセージの内容を信用するならば、インストーラーの wim イメージをボリュームにコピーした後、ブート情報を書き換えるところが失敗しているわけす。当然マシンは起動しなくなります。Windows RE も起動できません。ちなみにインストールが失敗したディスクからシステムを起動すると "Your PC/Device needs to be repaired – The Boot Configuration Data file is missing some required information. File: \BCD Error code: 0xc0000034" 画面が出ました。BCD 情報を書けなかったのはお前んところのインストーラーなんだけどな!

02-bcd
起動失敗の図

慌てず騒がず、とりあえず以下の作業を順番に試してみました。

  1. まったく同じ作業 (同じ USB ドライブを使って、同じハードディスク (以降ディスク A) をインストール先として指定) を試す → 現象変わらず
  2. 別のハードディスク (以降ディスク B) を使ってみる → 現象変わらず
  3. ディスク B を diskpart の clear コマンドでクリアしてからインストール → 現象変わらず

おいおい・・。一台目の Z440 で上手くいっていることからして、USB ドライブに問題はないはず。ハードディスク側にも問題があるとは思えない。ぱっと思いつくのは、BIOS/UEFI の起動方式とディスク形式の MBR/GPT。ディスクをクリアしても同じ現象が出る時点でインストーラーのバグくさいが、だとすると Z440 でうまくいった説明がつかない。Z420 も Z440 も UEFI のはずなのに。

しばらく悩んだ結果、Z420 と Z440 とで、パーティション構成に唯一の違いがあることに気づきました。Z440 のインストール先ディスクは 150GB なので、まるまる OS 用のパーティションを入れています。一方、Z420 のインストール先ディスク A は 1TB なので、後ろ半分の 500GB はデータ用にして、先頭の 500GB を OS 用にしていました。今回の作業では、前の OS のパーティションだけを消して、インストーラーから新しくパーティションを作り直していました。また、上記作業 2. と 3. の作業でも、インストーラー経由でパーティションを作ってからインストールをしていました。そこで、新しいディスク C を用意して、パーティションを作らず、ディスク全体を指定して OS をインストールしたところ・・・成功。謎は深まるばかり。

そしてすぐに次の問題が発生。インストール後に再起動がかかっても、またも "Your PC/Device needs to be repaired" エラーで Windows 起動しない・・・。インストール成功したんじゃなかったのかよ。

試行錯誤の末、Boot menu を開いてインストール先のディスクを明示的に選択すれば起動することが判明。これで何が起こっているのかは分かった、気がする。

03-boot

Z420 のブート メニュー
(Legacy Boot Sources の WDC WD2500AA.. を選択すれば起動できた)

起動がうまくいったあと、以下の情報を確認しました。

  • ディスク A は GPT 形式になっていて、EFI System Partition は作成されている
    → インストーラーの最後で BCD 情報の書き換えに失敗した理由が不明
  • ディスク B は MBR 形式になっている
  • Z420 の msinfo32 を見ると、BIOS Mode は Legacy
  • Z440 の起動ディスクは GPT 形式
  • Z440 の msinfo32 で、BIOS Mode は UEFI

上記を整理すると・・

  1. Windows インストーラー、及び OS 本体は Z420 を Legacy BIOS だと思っているので、MBR 形式のディスクを対象にしたインストールを試みる。
  2. しかし、インストーラーの中のパーティションを作る部分では、システムを UEFI と認識しているためか、MBR ではなく GPT 形式でパーティションを作る。
  3. Z420 のブートの順番は、UEFI を試してから各ディスクの MBR を使って起動しようとする。このとき、UEFI の Windows Boot Manager がなぜか中途半端に実行できてしまうため、MBR の実行を試そうとしない。
  4. システムは MBR 形式でインストールされているので当然起動できない。

不可解なのは以下の点。

  • そもそも最初に試したときに、BCD 情報が更新できなかった理由
    → 諸悪の根源。これが上手くいっていれば問題はここまで拗れない。
  • インストーラーでパーティションを作るとディスクが GPT になるくせに、実際にシステムをインストールするときは MBR でディスクを切っている。インストーラーがシステムの BIOS モードをチェックするコードが少なくとも二ヶ所あって、一方は Legacy BIOS、他方は UEFI だと認識してしまうっぽい・・?

確か似たような現象を調べたときに、Windows のインストーラーにはディスクをクリアしてディスク形式を変更する機能がないので、インストーラーは Legacy BIOS のシステムでは GPT 形式のディスクを認識せず、逆に UEFI のシステムでは MBR のディスクを認識しなかった記憶があります。この場合、diskpart などを使ってあらかじめディスク形式を変えておく必要があります。

今回の場合は不可解で、GPT と MBR の扱いがかなり混在してしまっている印象がです。そもそもインストーラーやシステムがシステムを Legacy BIOS として認識しているのであれば、GPT で切れたディスクは認識できるべきではないし、インストールが始まる前にエラーになって欲しいものです。イメージのコピーはうまくいって、最後にこけるのは一番タチが悪い。これが Server 2016 のメディアで新しく発生するのか、もっと前の OS のディスクから発生するのかどうかは確かめていません。

今のところ、マシンを再起動するたびに boot menu を起動してディスクを選択しないといけない。超不便。

(2016/10/30 追記)

まだ最終確認は取れていませんが、どうやら NVRAM への読み書きができないハードウェア障害のような気がしてきました。調べた内容を以下に記します。

まず、Windows インストール時のログはインストール先ディスクの $WINDOWS.~BT\Sources\Panther\setupact.log に残っているので、失敗している箇所を確認。

log

2016-10-22 16:46:58, Info       [0x060228] IBS    Callback_UpdateBootFiles:Successfully updated Windows boot files.
2016-10-22 16:46:58, Info                  IBSLIB ModifyBootEntriesLegacy: Not in first boot. No actions to perform. SetupPhase[2]
2016-10-22 16:46:58, Info                  IBSLIB ModifyBootEntriesBCD:Setup phase is [2]
2016-10-22 16:46:58, Info                  IBSLIB BfsInitializeBcdStore flags(0x00000008) RetainElementData:n DelExistinObject:n
2016-10-22 16:46:58, Info                  IBSLIB VolumePathName for H:\Windows is H:\
2016-10-22 16:46:58, Info                  IBSLIB Opening template from \Device\HarddiskVolume7\Windows\System32\config\BCD-Template.
2016-10-22 16:46:58, Info                  IBSLIB System BCD store does not exist, creating.
2016-10-22 16:46:58, Error      [0x064230] IBSLIB Failed to create a new system store. Status = [c0000001]
2016-10-22 16:46:58, Error      [0x0641b8] IBSLIB ModifyBootEntries: Error modifying bcd boot entries. dwRetCode=[0x1F][gle=0x0000001f]
2016-10-22 16:46:58, Info       [0x060216] IBS    CallBack_MungeBootEntries:Failed to modify boot entries; GLE = 31
2016-10-22 16:46:58, Info       [0x0640ae] IBSLIB PublishMessage: Publishing message [Windows could not update the computer’s boot configuration. Installation cannot proceed.]
2016-10-22 16:46:58, Info       [0x0a013d] UI     Accepting Cancel. Exiting Page Progress.

やはり BCD の新規作成に失敗している模様。

とりあえず BIOS の設定 (Advanced –> Device Options) を確認。もともとはこんな設定だった。後で触れるがこの時点でちょっと変。

bios01

とりあえず Option ROM を Legacy から EFI に変えて試してみる。

bios02

なお、ここで Video Options ROMS を EFI に変えてはいけない。間違って変えてしまうと、ビープ音が 6 回鳴ってシステムが起動しない悲しい状態になります。

Advisory: HP Z1, Z220, Z420, Z620, Z820 Workstation – 6 Beeps After Changing BIOS Settings
http://h20564.www2.hp.com/hpsc/doc/public/display?docId=emr_na-c04045903

お決まりだが、見事にこの罠を踏んでしまったのだ。上記 Resolution にあるように、CMOS リセットを行って無事復活。PXE Option ROMS と Mass Storage Option ROMS だけを EFI にして再起動。そして同様にインストーラーを動かすが、状況は変わらず、結局 "Windows could not update the computer’s boot configuration. Installation cannot proceed." で失敗する。

埒が明かなくなってきたので、真面目に setup.exe をデバッグしてみることに。最近の Windows PE では NIC の標準ドライバーが入っているので TCP/IP ネットワークで簡単にユーザーモードのリモート デバッグができます。Windows PE 起動後に以下のコマンドを実行すると、ネットワークが有効になるので dbgsrv.exe を起動できます。

> wpeutil initializenetwork
> wpeutil disablefirewall

詳細は省きますが、問題となっているインストーラーの最終フェーズでは、まず空の BCD を作ってから、インストール イメージ内にある windows\system32\config\BCD-Template と NVRAM の状態を元に BCD にデータを入れていくようなことをやっているようです。空の BCD を作るところは問題なく成功して、NVRAM の内容を取ってくると思われるシステム コールから c0000001 が返ってきていました。カーネル デバッグまではやっていないので、カーネルの中で何が失敗しているのかはまだ不明のままです。

NVRAM がおかしいとすると、Option ROM が Legacy 設定だったにも関わらず "Your PC/Device needs to be repaired – The Boot Configuration Data file is missing some required information. File: \BCD Error code: 0xc0000034" が出る理由も分かるような気もします。NVRAM の内容が Server 2016 を入れる前の状態のまま変わっていない可能性が高く、本来であれば Option ROM を Legacy に変えたら NVRAM はクリアされて、MBR からの起動を自動的に試すのではないだろうか。

デバッガーを使って、NVRAM にアクセスしてエラー コードを返している箇所 (4 箇所あった) で、片っ端からエラーコードを変更してエラーがなかったように見せかける禁断の領域に踏み込んだところ、インストールは終わりましたが、初回起動で OOBE が始まる前の段階で "Windows could not complete the installation. To install Windows on this computer, restart the installation." というポップアップが出て結局起動できず。どうやら Windows 起動時にも NVRAM へのアクセスを行なっているようだ。まあそりゃそうだろう。

image

Z420 で NVRAM をクリアする方法を探してみたが、どうにも見つからない。意図せずして行なった CMOS クリアではクリアされなかった。システム設定で ROM をクリアするオプションはあるのだが、何が消えるか分からないためちょっと恐くて試していない。びびり。

(2016/11/6 追記)

次は、何とかして NVRAM がおかしいという確証が欲しいところです。以下の資料を見ると、実は bcdedit /enum で出力される値は NVRAM variable から来ているらしい。

Presentations and Videos | Unified Extensible Firmware Interface Forum
http://www.uefi.org/learning_center/presentationsandvideos

上記ページからダウンロードできる "Windows Boot Environment" という PDF の 20 ページ目によると

– BCD has 1:1 mappings for some UEFI global variables

– Any time {fwbootmgr} is manipulated, NVRAM is automatically updated

さらに、以下のページによると

Remove Duplicate Firmware Objects in BCD and NVRAM
https://technet.microsoft.com/en-us/library/cc749510(v=ws.10).aspx

When bcdedit opens the BCD, it compares entries in NVRAM with entries in BCD. Entries in NVRAM that were created by the firmware that do not exist in BCD are added to the system BCD. When bcdedit closes the system BCD, any boot manager entries in BCD that are not in NVRAM are added to NVRAM.

同様のことは以下の日本語のブログにもまとめられています。詳しくていい感じ。

PC-UEFI – DXR165の備忘録
http://dxr165.blog.fc2.com/blog-category-45.html

何はともあれ、Windows PE を起動して bcdedit を実行してみます。

X:\windows\system32> bcdedit /enum {fwbootmgr}
The boot configuration data store could not be opened.
A device attached to the system is not functioning.

あっさり失敗。インストーラーを起動するまでもないですね。Server 2016 のメディアが悪いのではなく、やはりハードウェアがおかしいくさい。

さて、次のステップはいよいよ Windows PE のカーネル デバッグだろうか。幸い、Z420 と Z440 を 1394 ケーブルで繋げられたので、これでデバッグすることにする。最近だとイーサネットも使えるらしいが、試したことはない。

上記の bcdedit /enum {fwbootmgr} を実行すると、NT カーネルから HAL を経由し、EFI のランタイム サービス テーブルにおける GetNextVariableName が指すアドレスの関数を呼んで変数名を列挙し、GetVariable で値を取ってきます。ランタイム サービス テーブルの定義は、↓ のファイルにおける EFI_RUNTIME_SERVICES という構造体です。

TianoCore EDK2: MdePkg/Include/Uefi/UefiSpec.h Source File
http://www.bluestop.org/edk2/docs/trunk/_uefi_spec_8h_source.html

ランタイム サービス テーブルは、EFI システム テーブルの一部であり、EFI システム テーブルは efi_main 関数が取る 2 つのパラメーターのうちの一つらしい。

Programming for EFI: Using EFI Services
http://www.rodsbooks.com/efi-programming/efi_services.html

GetNextVariableName のプロトタイプ宣言は分かっているので、呼び出し部分から変数名を GUID を確認しました。102 個ありますが、とりあえず全部載せておきます。

ffffd000`208578a0  "CurrentDevicePath"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "BootCurrent"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "LangCodes"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "PlatformLangCodes"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "SSID"
ffffd000`20857868  707c9176 4e27a4c1 371c1d85 c873cab7
ffffd000`208578a0  "UsbMassDevNum"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "SetupFeatureSupport"
ffffd000`20857868  b6ad93e3 4c8519f7 c58072aa c7db9471
ffffd000`208578a0  "ErrOut"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "ErrOutDev"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "RstSataV"
ffffd000`20857868  193dfefa 4302a445 3aefd899 c6041aad
ffffd000`208578a0  "PNP0510_0_VV"
ffffd000`20857868  560bf58a 4d7e1e0d 80293f95 31e061a2
ffffd000`208578a0  "RstScuV"
ffffd000`20857868  193dfefa 4302a445 3aefd899 c6041aad
ffffd000`208578a0  "BootOptionSupport"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "ConInDev"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "UsbMassDevValid"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "PNP0501_1_VV"
ffffd000`20857868  560bf58a 4d7e1e0d 80293f95 31e061a2
ffffd000`208578a0  "PNP0400_0_VV"
ffffd000`20857868  560bf58a 4d7e1e0d 80293f95 31e061a2
ffffd000`208578a0  "PNP0501_0_VV"
ffffd000`20857868  560bf58a 4d7e1e0d 80293f95 31e061a2
ffffd000`208578a0  "ConOutDev"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "VgaDeviceInfo"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "VgaDeviceCount"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "RstScuO"
ffffd000`20857868  193dfefa 4302a445 3aefd899 c6041aad
ffffd000`208578a0  "DebuggerSerialPortsEnabledVar"
ffffd000`20857868  97ca1a5b 4d1fb760 90d14ba5 902c0392
ffffd000`208578a0  "SerialPortsEnabledVar"
ffffd000`20857868  560bf58a 4d7e1e0d 80293f95 31e061a2
ffffd000`208578a0  "DriverHlthEnable"
ffffd000`20857868  0885f288 4be1418c ad8bafa6 fe08da61
ffffd000`208578a0  "DriverHealthCount"
ffffd000`20857868  7459a7d4 44806533 e279a7bb c943445a
ffffd000`208578a0  "S3SS"
ffffd000`20857868  4bafc2b4 410402dc f1d636b2 849e8db9
ffffd000`208578a0  "RSCInfoAddresss"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "PlatformLang"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "AMITSESetup"
ffffd000`20857868  c811fa38 457942c8 e960bba9 34fbdd4e
ffffd000`208578a0  "UsbSupport"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "SlotEnable"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "FrontUsbEnable"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "RearUsbEnable"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "InternalUsbEnable"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "PowerOnTime"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "MSDigitalMarker"
ffffd000`20857868  c43c9947 4a343578 f38e5fb9 8e43c7a5
ffffd000`208578a0  "NotFirstBoot"
ffffd000`20857868  70040abc 45886387 cdddb187 f57a7d6c
ffffd000`208578a0  "ONBOARD_DEVS_PRESENT"
ffffd000`20857868  d98397ee 457a7a9d 68e5dfa9 18cc87ae
ffffd000`208578a0  "MemoryInfo"
ffffd000`20857868  7ee396a1 431bff7d cd8c53fa c5447c12
ffffd000`208578a0  "MEMajorVersion"
ffffd000`20857868  59416f8c 48c4b82d cb107e88 bbc38ec4
ffffd000`208578a0  "PciSerialPortsLocationVar"
ffffd000`20857868  560bf58a 4d7e1e0d 80293f95 31e061a2
ffffd000`208578a0  "HeciErrorReset"
ffffd000`20857868  31d2fce0 11e164b3 00086cb8 669a0c20
ffffd000`208578a0  "MeInfoSetup"
ffffd000`20857868  78259433 4db37b6d c436e89a 7da1c3c2
ffffd000`208578a0  "NetworkStackVar"
ffffd000`20857868  d1405d16 46957afc 454112bb a295369d
ffffd000`208578a0  "HSTime"
ffffd000`20857868  ae601ef0 11e0360b 0008429e 669a0c20
ffffd000`208578a0  "LastHDS"
ffffd000`20857868  ae601ef0 11e0360b 0008429e 669a0c20
ffffd000`208578a0  "ConsoleLock"
ffffd000`20857868  368cda0d 4b9bcf31 d1e7f68c 7e15ffbf
ffffd000`208578a0  "SetupAmtFeatures"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "SlotPresent"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "MMIOR."
ffffd000`20857868  3b2158f5 48c039d3 530384aa dbc6ba65
ffffd000`208578a0  "SysBuses"
ffffd000`20857868  55e6fc89 40763e74 e9d4c298 10e8c413
ffffd000`208578a0  "ThermalErrorLog"
ffffd000`20857868  707c9176 4e27a4c1 371c1d85 c873cab7
ffffd000`208578a0  "ConOut"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "SetupCpuSockets"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "FrontUsbPresent"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "RearUsbPresent"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "InternalUsbPresent"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "Lang"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "SBRealRevID"
ffffd000`20857868  707c9176 4e27a4c1 371c1d85 c873cab7
ffffd000`208578a0  "TdtAdvancedSetupDataVar"
ffffd000`20857868  7b77fb8b 4d7e1e0d 80393f95 76e061a2
ffffd000`208578a0  "HP_CTRACE"
ffffd000`20857868  707c9176 4e27a4c1 371c1d85 c873cab7
ffffd000`208578a0  "NBRealRevID"
ffffd000`20857868  707c9176 4e27a4c1 371c1d85 c873cab7
ffffd000`208578a0  "MeBiosExtensionSetup"
ffffd000`20857868  1bad711c 4241d451 3785f3b1 700c2e81
ffffd000`208578a0  "HpWriteOnceMetaData"
ffffd000`20857868  707c9176 4e27a4c1 371c1d85 c873cab7
ffffd000`208578a0  "PBRDevicePath"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "TrueStruct"
ffffd000`20857868  7349bea7 420bc95c 1e6dcd8d a88b4d9d
ffffd000`208578a0  "PNP0501_11_NV"
ffffd000`20857868  560bf58a 4d7e1e0d 80293f95 31e061a2
ffffd000`208578a0  "PNP0501_12_NV"
ffffd000`20857868  560bf58a 4d7e1e0d 80293f95 31e061a2
ffffd000`208578a0  "SetupLtsxFeatures"
ffffd000`20857868  ec87d643 4bb5eba4 3e3fe5a1 a90db236
ffffd000`208578a0  "ucal"
ffffd000`20857868  707c9176 4e27a4c1 371c1d85 c873cab7
ffffd000`208578a0  "HpPassphraseStructureVariable"
ffffd000`20857868  707c9176 4e27a4c1 371c1d85 c873cab7
ffffd000`208578a0  "EfiTime"
ffffd000`20857868  9d0da369 46f8540b 5f2ba085 151e302c
ffffd000`208578a0  "Setup"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "PlatformLang"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "Timeout"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "AMITSESetup"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "IDESecDev"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "SystemIds"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "UsbSupport"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "PNP0501_0_NV"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "PNP0501_1_NV"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "PNP0400_0_NV"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "PNP0510_0_NV"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "HpMfgData"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "SlotEnable"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "FrontUsbEnable"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "RearUsbEnable"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "InternalUsbEnable"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "PowerOnTime"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "MSDigitalMarker"
ffffd000`20857868  8173aefa 4574adf0 377139a0 1af24aab
ffffd000`208578a0  "PNP0501_0_NV"
ffffd000`20857868  560bf58a 4d7e1e0d 80293f95 31e061a2
ffffd000`208578a0  "PNP0501_1_NV"
ffffd000`20857868  560bf58a 4d7e1e0d 80293f95 31e061a2
ffffd000`208578a0  "PNP0400_0_NV"
ffffd000`20857868  560bf58a 4d7e1e0d 80293f95 31e061a2
ffffd000`208578a0  "PNP0510_0_NV"
ffffd000`20857868  560bf58a 4d7e1e0d 80293f95 31e061a2
ffffd000`208578a0  "HpMor"
ffffd000`20857868  707c9176 4e27a4c1 371c1d85 c873cab7
ffffd000`208578a0  "PBRDevicePath"
ffffd000`20857868  a9b5f8d2 42c2cb6d ffb501bc 5e33e4aa
ffffd000`208578a0  "PetAlertCfg"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "ConIn"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "Timeout"
ffffd000`20857868  8be4df61 11d293ca e0000daa 8c2b0398
ffffd000`208578a0  "CurrentPolicy"
ffffd000`20857868  77fa9abd 4d320359 f42860bd 4b788fe7
ffffd000`208578a0  "a8ff1f3f4a8c94074056b76e9d7fab3a862c68d3"
ffffd000`20857868  ffffffff ffffffff ffffffff ffffffff

GetNextVariableName からの戻り値は 0 なのですが、最後の変数は名前、GUID ともに明らかに変です。このあと、最後の "a8ff1f3f4a8c94074056b76e9d7fab3a862c68d3" に対して GetVariable すると、戻り値が 14 (= EFI_NOT_FOUND) になります。呼び出し元は hal!HalEnumerateEnvironmentVariablesEx なのですが、GetVariable が失敗すると、この関数は見慣れたエラー コード c0000001 (= STATUS_UNSUCCESSFUL) を返すようになっていました。

というわけで、EFI の GetNextVariableName で列挙された変数名がなぜか GetVariable できないためインストールが上手くいかない、ことが分かりました。アセンブラでどうやって NVRAM にアクセスしているのか分かりませんが、やはり NVRAM が怪しいです。

それにしても HAL の動作には不満が残ります。GetNextVariableName で列挙された値が GetVariable 出来なかった場合は、全体をエラーにするのではなく、その変数だけをスキップして欲しいですね。

広告

Brute-force attack against NTLMv2 Response

2016 年 9 月の Windows Update で、NTLM SSO の動作に関連する脆弱性 CVE-2016-3352 が修正されたようです。

Microsoft Security Bulletin MS16-110 – Important
https://technet.microsoft.com/library/security/MS16-110

An information disclosure vulnerability exists when Windows fails to properly validate NT LAN Manager (NTLM) Single Sign-On (SSO) requests during Microsoft Account (MSA) login sessions. An attacker who successfully exploited the vulnerability could attempt to brute force a user’s NTLM password hash.

To exploit the vulnerability, an attacker would have to trick a user into browsing to a malicious website, or to an SMB or UNC path destination, or convince a user to load a malicious document that initiates an NTLM SSO validation request without the consent of the user.

CVE – CVE-2016-3352
http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2016-3352

Microsoft Windows 8.1, Windows RT 8.1, and Windows 10 Gold, 1511, and 1607 do not properly check NTLM SSO requests for MSA logins, which makes it easier for remote attackers to determine passwords via a brute-force attack on NTLM password hashes, aka "Microsoft Information Disclosure Vulnerability."

"NTLM SSO" などのキーワードで適当にインターネット検索すると、今年 8 月に書かれた以下の記事が見つかります。

The Register – Reminder: IE, Edge, Outlook etc still cough up your Windows, VPN credentials to strangers
http://www.theregister.co.uk/2016/08/02/smb_attack_is_back/?mt=1474231650819

画面キャプチャーを見ると、なんと Microsoft アカウントのパスワードが解析されてしまっています。そして Youtube の埋め込み動画では、SMB パケットがブラウザーからリークしていることを示しています。つまり、SMB パケットに埋め込まれた NTLM メッセージに対して brute-force 攻撃をしかけることで Microsoft アカウントのパスワードを解析できる、ことを示しているようです。

これは理論的に可能でしょう。が、もしそれが 「簡単に」 できるのであれば、それは NTLM プロトコルの死を意味するべきであり、パッチとして一朝一夕に対応できるものではないはずです。SSLv3 や RC4 と同様にそのプロトコルの使用を止めるべきですが、非ドメイン環境において NTLM の代わりとなるような認証プロトコルは Windows には実装されていないはずです。

というわけで、NTLM に対する brute-force がどれぐらい簡単なのかを調べることにしました。まず、NTLM プロトコルがどうやってユーザー認証を行っているかを説明します。と言っても以下の PDF を読み解くだけです。

[MS-NLMP]: NT LAN Manager (NTLM) Authentication Protocol
https://msdn.microsoft.com/en-us/library/cc236621.aspx

NTLM が混乱を招く点として、一つのプロトコルが複数のプロトコル バージョン (LanMan, NTLMv1, NTLMv2) に対応していることです。Wiki の情報を見ると NTLMv2 は NT 4.0 SP4 から採用されているので、 NTLMv2 だけで現在は問題なく生きていけるはずです。ただし XP などの古い OS において、さらに古い OS との互換性のために NTLMv1 や Lanman に fallback するような動作が有効になっている場合があります。このへんの細かい話は長くなりそうなので、以下の KB に丸投げします。

NT LAN Manager – Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/NT_LAN_Manager

How to prevent Windows from storing a LAN manager hash of your password in Active Directory and local SAM databases
https://support.microsoft.com/en-us/kb/299656

Security guidance for NTLMv1 and LM network authentication
https://support.microsoft.com/en-us/kb/2793313

NTLM は Challenge Reponse Authentication の一つで、簡単に書くとサーバーとクライアントが以下 3 つのメッセージを交換することで認証が行われます。(仕様によると Connectionless モードの場合は Negotiate が存在しないようですが、見たことがないのでパス。)

Client: "I want you to authenticate me."
(= Negotiate Message)

Server: "Sure. Challenge me. Use 0x0123456789abcdef as a ServerChallenge."
(= Challenge Message)

Client: "My response is !@#$%^&*()_+…"
(= Authenticate Message)

NTLM は単体で使われるプロトコルではなく、必ず別のプロトコルに埋め込まれて使われます。例えば SMB の中で使われる場合には、SMB Session Setup コマンドに埋め込まれます。ダイレクト SMB ポートである 445/tcp をキャプチャーしたときの Network Monitor 上での見え方は以下の通りです。

01
SMB packets over 445/tcp (Lines highlited in purple contain NTLM messages)

02
NTLM Negotiate Message

03
NTLM Challenge Message

04
NTLM Authenticate Message

セクション 3.3.2 NTLMv2 Authentication から、パスワードを解析するのに必要な疑似コードの計算式だけを抜き出すと以下の通りです。

[MS-NLMP]: NTLM v2 Authentication – 3.3.2 NTLM v2 Authentication
https://msdn.microsoft.com/en-us/library/cc236700.aspx

Define NTOWFv2(Passwd, User, UserDom) As
  HMAC_MD5(MD4(UNICODE(Passwd)),
           UNICODE(ConcatenationOf(Uppercase(User), UserDom)))
EndDefine

Set temp to ConcatenationOf(Responserversion,
                            HiResponserversion,
                            Z(6),
                            Time,
                            ClientChallenge,
                            Z(4),
                            ServerName, Z(4))
Set NTProofStr to HMAC_MD5(ResponseKeyNT,
                           ConcatenationOf(CHALLENGE_MESSAGE.ServerChallenge,
                                           temp))
Set NtChallengeResponse to ConcatenationOf(NTProofStr, temp)

使用しているハッシュ関数は HMAC_MD5 と MD4 のみ。入力データはいろいろあって面倒そうに見えますが、それほど難しくありません。特に、疑似コードの中で temp として扱われているバージョンやタイムスタンプなどのメタ情報が、ハッシュ値である NTProofStr と連結してそのまま Authenticate Message の NtChallengeResponse になっているからです。図示したものを ↓ に示します。図中の Metainfo が、上記擬似コードで言うところの temp です。

実際に処理するときは、パスワードを UTF-16 に変換する点と、ユーザー名を大文字に変換する点に注意が必要です。

05
Calculation of NtChallengeResponse in NTLMv2

これで材料が出揃ったのでコードを書きます。まずサーバー側のコードとして、Samba サーバーが NTLM メッセージを処理しているときに、brute-force に必要となる情報をテキスト ファイルとして書き出すようにします。これによって、前述の Youtube 動画がやっていることとほぼ同じことができます。

Yandex SMB hash capture on IE with email message – YouTube
https://www.youtube.com/watch?v=GCDuuY7UDwA

msmania/samba at ntlm-hack
https://github.com/msmania/samba/tree/ntlm-hack

テキスト ファイルと同じ内容をレベル 0 のデバッグ メッセージとしても出力するようにしました。gdb を使って smbd を実行しておくと、SMB 経由で NTLM 認証が行なわれたときにコンソールにログが記録されます。出力される情報はこんな感じです。後でまとめて grep できるようにあえてテキスト ファイルにしました。

Domain:
User: ladyg
Client: LIVINGROOM-PC
UserAndDomain=4c004100440059004700
Challenge=ae65c9f0192d64b9
Auth=0101000000000000b62acefc2d11d201ea3017d2f290d64e00..(長いので省略)
Response=39329a4a4e9052fe3d4dea4ea9c79ac5

次に、Samba サーバーが書き出したテキスト ファイルに対して実際に brute-force を行うプログラムを書きます。hashcat に新しいモードを付け足すことができればベストだったのですが、OpenCL を勉強する時間がなかったので、OpenSSL の関数を呼び出すだけの簡単なプログラムになりました。

msmania/ntlm-crack
https://github.com/msmania/ntlm-crack

このプログラムは Samba が生成したテキスト ファイルに対して、別の引数として指定したのテキスト ファイルの各行をパスワードとして NTLMv2 Reponse を生成し、Samba が出力したデータと一致するかどうかを比較します。パスワード一覧ファイルは、ネット上で探せば簡単に見つかります。ntlm-crack リポジトリにサンプルとして入れてある 10_million_password_list_top_1000.txt は、以下のリポジトリからコピーしたものです。

GitHub – danielmiessler/SecLists
https://github.com/danielmiessler/SecLists

では実際にコマンドを実行して brute-force の速度を計測します。マシン スペックは以下の通り。Windows マシンであればもっと新しいマシンで hashcat をぶん回せたのですが・・無念。

  • OS: Ubuntu 16.04.1 LTS (GNU/Linux 4.4.0-36-generic x86_64)
  • CPU: Intel(R) Core(TM) i5-2520M CPU @ 2.50GHz (Sandy Bridge)

とりあえず 100 万通りのパスワードを試してみます。

$ ./t -f sample.in -l /data/src/SecLists/Passwords/10_million_password_list_top_1000000.txt
No matching password in /data/src/SecLists/Passwords/10_million_password_list_top_1000000.txt.
Tried 999999 strings in 3343 msec.
$ ./t -f sample.in -l /data/src/SecLists/Passwords/10_million_password_list_top_1000000.txt
No matching password in /data/src/SecLists/Passwords/10_million_password_list_top_1000000.txt.
Tried 999999 strings in 3372 msec.
$ ./t -f sample.in -l /data/src/SecLists/Passwords/10_million_password_list_top_1000000.txt
No matching password in /data/src/SecLists/Passwords/10_million_password_list_top_1000000.txt.
Tried 999999 strings in 3344 msec.

大体 3 秒ちょいです。特に工夫をしたわけでもないのですが、予想していたより速いです。UTF-16 変換の処理を予め済ませて、かつ並列処理をすれば 1M/s は軽く越えられそう。

もちろん実際に使われているのはこんな子供騙しではありません。参考として 4 年前の記事ですが、25-GPU を使って 95^8 通りのハッシュを 5.5 時間で生成できたと書かれています。ここでいう NTLM cryptographic algorithm が厳密に何を意味するのかは書かれていません。巷では、UTF-16 エンコードしたパスワードの MD4 ハッシュを NTLM ハッシュと呼ぶことが多く、仮にそうだとすると、5.5 時間という数字には HMAC-MD5 を 2 回計算する部分が含まれていません。試しに、今回作った ntlm-crack から HMAC-MD5 の演算を飛ばして再度実行してみます。

$ ./t -f sample.in -l /data/src/SecLists/Passwords/10_million_password_list_top_1000000.txt
No matching password in /data/src/SecLists/Passwords/10_million_password_list_top_1000000.txt.
Tried 999999 strings in 347 msec.
$ ./t -f sample.in -l /data/src/SecLists/Passwords/10_million_password_list_top_1000000.txt
No matching password in /data/src/SecLists/Passwords/10_million_password_list_top_1000000.txt.
Tried 999999 strings in 347 msec.
$ ./t -f sample.in -l /data/src/SecLists/Passwords/10_million_password_list_top_1000000.txt
No matching password in /data/src/SecLists/Passwords/10_million_password_list_top_1000000.txt.
Tried 999999 strings in 346 msec.

計算時間が約 1/10 で済んでしまいました。この比率が 25-GPU マシンにも適用されるとすると、8 文字のパスワードをクラックするのに 4 年前は 55 時間かかっていたはずです。怪しい概算ですが。

25-GPU cluster cracks every standard Windows password in <6 hours | Ars Technica
http://arstechnica.com/security/2012/12/25-gpu-cluster-cracks-every-standard-windows-password-in-6-hours/

今年は AlphaGo のニュースが衝撃でしたが、そのときの Nature 論文では 1,920 CPUs + 280 GPUs のマシンで AlphaGo を動かしたという実績が書かれているので、個人での所有は難しいにしても、あるべきところ (Google や NSA?) には 4 桁のプロセッサーを動かせるマシンが存在していると仮定できます。これで 2 桁分稼げるので、10 桁程度のパスワードであれば数日で解ける恐れがあります。12 桁のパスワードにしておけば年単位の時間が必要になるので安心かも・・・?

話が逸れておきましたが、冒頭の CVE-2016-3352 の話に戻ります。Security Bulletin には、以下のような修正がなされたと書かれています。つまり、誰彼構わず NTLM SSO 認証のための SMB パケットを送るのは止めた、ということでしょうか。

The security update addresses the vulnerability by preventing NTLM SSO authentication to non-private SMB resources when users are signed in to Windows via a Microsoft Account network firewall profile for users who are signed in to Windows via a Microsoft account (https://www.microsoft.com/account) and connected to a “Guest or public networks” firewall profile.

この修正ができたということは、 「不特定多数のサーバーに SMB パケットを送ってしまう動作があったため、本来できないはずの brute-force 攻撃の標的になってしまう」 ことが問題とされていたわけです。これでようやく、Security Bulletin の "An attacker who successfully exploited the vulnerability could attempt to brute force" という部分が腑に落ちました。この件に関して言えば、brute-force の成功が現実的かどうかは関係なく、brute-force が可能であることそのものが問題だったわけです。NTLM はまだ生きていていいんだ。

あえてケチをつけるならば、CVE の方の記述における "to determine passwords via a brute-force attack on NTLM password hashes" でしょうか。NTLM は複数のハッシュ (MD4 と HMAC-MD5) を使いますが、NTLM password hash と書くと、パスワードのハッシュ、すなわち一段階目の MD4 ハッシュを想定するのが普通です。しかし、MD4 ハッシュは一回目の HMAC-MD5 の鍵として使われるだけで、ネットワーク上を流れることはなく、brute-force の攻撃対象にはなりません。Microsoft 側の Security Bulletin では "attempt to brute force a user’s NTLM password hash" となっており、こちらの記述のほうがより正確な気がします。最近の流行は pass-the-hash 攻撃なので、平文のパスワードに替えて、ハッシュ値が brute-force の標的であってもおかしくはありません。

ところで、なぜ Microsoft アカウントに関する言及があるかというと、冒頭で紹介した The Register の記事にもありますが、Microsoft アカウントのユーザー名がユーザーのメール アドレスであり、OneDrive や MSDN などのサービスのアカウントとしても使われているからです。世界のどこかにあるパソコンのユーザー アカウント "Mike" のパスワードが分かってもできることは限られていますが、Microsoft アカウントのパスワードが解析されると大変なことになります。だからこそ今までこの古いバグが放置されてきたのかもしれません。ただ、ユーザー名が平文で SMB として流れるのは気持ち悪いですが。

(2016/9/19 追記)

9 月のアップデート後に、LAN ディスクや SAMBA にアクセスできなくなったというツイートやフォーラムを幾つか見つけましたが、おそらく CVE-2016-3352 に対する修正が原因と思われます。どうするんでしょうかね。

update kb3185614の不具合について、LANDISKへの接続やリモートアクセスができなくなる – マイクロソフト コミュニティ
http://answers.microsoft.com/ja-jp/windows/forum/windows_10-update/update/f5219540-a2a5-4b09-b9b6-e944dcbbed38

SUDO for Windows

Windows で動く Linux の sudo コマンド的なものを作って GitHub で公開しました。

msmania/sudo: SUDO for Windows
https://github.com/msmania/sudo

Windows でコンソールを使った作業をする場合、必要がない限りは、管理者権限のない制限付きトークンのコマンド プロンプト (もしくは PowerShell) で作業すると思います。Windows の困ったところは、管理者権限が必要なコマンドを実行するときには、新しいコンソールを別途起動しないといけないことです。しかし、1 コマンド実行したいだけなのに、わざわざ新しくコンソールを開いて使い終わったら閉じるのは時間がもったいないのです。というわけで、通常のコンソールと管理者権限のコンソールの二窓体制で作業する、というのが日常かと思います。しかし、最近の Windows は無駄にグラフィカルで、ウィンドウを切り替えるときの Alt+Tab やタスクバー アイコンのプレビューがいちいち大袈裟です。今度はこれをレジストリで無効にしておく、というような具合に、理不尽なカスタマイズが次々と必要になります。そこで、sudo を作ることにしました。

代替策も探しましたが、意外とありません。例えば、runas.exe を使って built-in の Administrator ユーザーでログオンすれば管理者権限は使えます。しかし次の 2 点において不満があり使えません。

  • runas.exe で cmd.exe を起動すると、結局新しいコンソールが起動する
  • Build-in の Administrator 以外では管理者権限にならない

SysInternals の psexec.exe を使うと runas みたいなことができますが、こちらはそもそも管理者権限がないと実行できないので本末転倒です。

sudo に求めたい要件は以下の通りです。

  1. 通常のコンソール上でそのまま作業できる (= 新しいコンソールは開かない)
  2. Administrator ではなく、管理者グループに所属している作業ユーザーで管理者権限を使える
  3. .NET やスクリプト経由ではなく、ネイティブの sudo.exe が欲しい

GitHub 上を "sudo windows" などで検索すると、幾つかそれっぽいプロジェクトは見つかりますが、1. の要件を満たしてくれません。

maxpat78/Sudo: Executes a command requesting for elevated privileges in Windows Vista and newer OS.
https://github.com/maxpat78/Sudo

jpassing/elevate: elevate — start elevated processes from the command line
https://github.com/jpassing/elevate

どちらも動作原理は同じで、ShellExecute API を lpVerb="runas" で実行しています。UAC プロンプトを表示させて管理者権限を得るには一番簡単な方法なのですが、コンソールから cmd.exe を起動すると別のコンソールが開いてしまうのでこれは使えません。

ShellExecute function (Windows)
https://msdn.microsoft.com/en-us/library/windows/desktop/bb762153(v=vs.85).aspx

ShellExecute が駄目となると CreateProcess でプロセスを作るしかありません (他に WinExec という化石のような API もありますが)。が、以下のブログに記載があるように、CreateProcess で権限昇格が必要なプロセスを起動することはできません。

Dealing with Administrator and standard user’s context | Windows SDK Support Team Blog
https://blogs.msdn.microsoft.com/winsdk/2010/05/31/dealing-with-administrator-and-standard-users-context/

CreateProcess() and CreateProcessWithLogonW do not have new flags to launch the child process as elevated. Internally, CreateProcess() checks whether the target application requires elevation by looking for a manifest, determining if it is an installer, or if it has an app compat shim. If CreateProcess() determines the target application requires elevation, it simply fails with ERROR_ELEVATION_REQUIRED(740). It will not contact the AIS to perform the elevation prompt or run the app.

最後の AIS というのは Application Information Service (AppInfo サービス) という UAC を司る憎いやつです。いや、実際はお世話になっているのですが。

Understanding and Configuring User Account Control in Windows Vista
https://technet.microsoft.com/en-us/library/cc709628(v=ws.10).aspx

となると残された道は 1 つしかなく、sudo.exe を昇格させて実行し、そこから CreateProcess で子プロセスを作る方法です。権限は自動的に継承されるので、子プロセスも昇格されたままになるはずです。

さらに要件 1. を満たすためには、もう一捻り必要です。sudo.exe をコンソール アプリケーション、すなわち /SUBSYSTEM:CONSOLE オプションを使ってリンクした場合、そのコンソール プログラムを昇格していないコンソール上から起動すると、UAC プロンプトの後にやはり新たなコンソールが起動して、プログラム終了時にコンソールが破棄される動作になるので、標準出力が見えません。したがって、sudo.exe は /SUBSYSTEM:WINDOWS を使ってリンクしなければなりません。この場合、単純にプログラムから printf などで標準出力に文字を出力しても、データは破棄されるだけでどこにも表示されません。そこで、プログラムの標準出力を親プロセスのコンソールに関連付けて、小プロセスからの標準出力を受け取って親プロセスの標準出力にリダイレクトするようにします。うう面倒くさい・・。

小プロセスの標準入出力をパイプとして受け取る部分は、以下のサンプルのコードを流用できます。

Creating a Child Process with Redirected Input and Output (Windows)
https://msdn.microsoft.com/en-us/library/windows/desktop/ms682499(v=vs.85).aspx

親プロセスのコンソールを自分の標準出力に関連付ける部分は、AttachConsole API に ATTACH_PARENT_PROCESS を渡すことで簡単に実現できます。

AttachConsole function (Windows)
https://msdn.microsoft.com/en-us/library/windows/desktop/ms681952(v=vs.85).aspx

sudo.exe 起動時に UAC プロンプトを表示させるには、マニフェスト XML で requestedExecutionLevel を highestAvailable に設定するだけです。Mt.exe を使うと、exe にマニフェストを埋め込むことが出来るので、Makefile の中でリンカーの後に Mt.exe を実行するように記述します。

Mt.exe (Windows)
https://msdn.microsoft.com/en-us/library/aa375649(v=vs.85).aspx

これらを組み合わせれば、基本の動きはほぼ達成できますが、最初の MSDN のサンプルには若干問題があります。サンプルをそのままコピーして標準出力に文字を出力するだけの簡単なプロセス (ipconfig.exe など) を実行すると、文字は出力されるのですが、ipconfig.exe が終了しても sudo.exe が終わりません。ReadFromPipe における ReadFile の呼び出しで、子プロセスが終了しているにも関わらず制御が返ってこないためです。原因は、STARTUPINFO 構造体に渡した子プロセス用のパイプへのハンドル、すなわち g_hChildStd_OUT_Wr と g_hChildStd_IN_Rd を閉じていないためと考えられます。ちゃんと確かめていないのですが、STARTUPINFO 構造体に渡したハンドルは、複製されてから小プロセスに渡されるので、子プロセス側で標準入出力のハンドルを破棄しても、複製元の g_hChildStd_OUT_Wr と g_hChildStd_IN_Rd を自分で保持している限りパイプが有効で、ReadFile はそれを待ち続けているのだと思います。じゃあ単純に CreateProcess の後でをさっさとハンドルをクローズしてしまえばよいかというと、大方のシナリオでは動くとは思いますが、微妙だと思います。子プロセスによっては、すぐに標準出力にデータを出力しない動作をするものがあってもおかしくありません。しかし、sudo.exe 側はパイプにデータが残っているかどうかだけで出力を続けるかどうかを判断しているので、子プロセスが動作中にも関わらずループを抜けてしまうかもしれません。

現時点のバージョンの sudo.exe では、単純に CreateProcess のあと子プロセスが終了するまで WaitForSingleObject で待って、その後でじっくりとパイプの中を読み出すようにしました。この実装も微妙で、子プロセスの出力量が膨大であったときにパイプが溢れる可能性がありますし、そもそも子プロセスが終わるまで待っているのは美しくありません。そのうち、子プロセスの状態を監視するようなスレッドを作って対応します。

WaitForSingleObject は使うものの、INIFINITE を渡して永遠に待ち続けるのはさすがに嫌だったので、タイムアウト値を設けることにしました。初め、このタイムアウト値は環境変数経由で設定しようと思っていました。そうすれば、CreateProcess の第二引数には WinMain の引数の pCmdLine をそのまま渡すだけで済むので、楽ができるのです。しかし、ここでも Windows のコマンド プロンプトの困った仕様が立ちはだかります。コマンドを実行している時だけに有効になる一時的な環境変数が使えないのです。正式に何というのかわかりませんが、つまり以下のようなことができません。make を実行するときによく使いますね。

$ cat test.sh
echo $HOGE

$ echo $HOGE

$ HOGE=1 ./test.sh
1

$ echo $HOGE

$

一応、似たようなことはできます。それが以下のフォーラムで出てきているやり方で、cmd /C を使って子プロセスの中で set コマンドを実行してから目的のコマンドを実行する方法です。

Setting environment variable for just one command in Windows cmd.exe – Super User
http://superuser.com/questions/223104/setting-environment-variable-for-just-one-command-in-windows-cmd-exe

ちなみにこの中で紹介されている、/V オプションを使った環境変数の遅延評価は、子プロセスでは必要ですが孫プロセスでは不要です。マニアックですが、こんな感じです。

> cmd /C "set HOGE=1 && echo %HOGE% !HOGE! && cmd /c echo %HOGE% !HOGE!"
%HOGE% !HOGE!
1 !HOGE!

> cmd /V /C "set HOGE=1 && echo %HOGE% !HOGE! && cmd /c echo %HOGE% !HOGE!"
%HOGE% 1
1 1

したがって、sudo.exe を使って cmd /c "set TIMEOUT=10 && sudo ipconfig" 的なことをやれば一応は環境変数からタイムアウト値を取れる、と思えますが結局駄目でした。UAC 昇格を要求するコマンドを起動した場合、環境変数が引き継がれません。これは Linux の sudo のデフォルト動作と同じですが、sudo に -E オプションを付加すると環境変数を引き継ぐことができます。

$ echo $HOGE

$ HOGE=1 sudo ./test.sh

$ HOGE=1 sudo -E ./test.sh
1

上記の理由で、環境変数を使うのは諦めて引数を取ることにしました。空白などの扱いを自分で決めたかったので pCmdLine をパースするステート マシンを 1 から書きました。それが CCommandOptions クラスですが、無駄に長いです。たぶんもっとまともな実装方法があると思います。アルゴリズムは苦手・・。

とりあえずこれで要件を満たすコマンドができました。出力例は ↓ の通りです。ここまで書いて言うのもなんですが、UAC ポップアップの表示が遅いので、もっさりした動作にしかなりません。なんだかんだスピードを求めるなら二窓体制が無難かも。

> sudo /t 10 powershell "get-vm | ?{$_.State -eq ‘Running’} | select -ExpandProperty networkadapters | select vmname, macaddress, switchname, ipaddresses | fl *"
[sudo] START
Spawning a process (Timeout = 10 sec.)

VMName : VM1
MacAddress : 00155DFE7A01
SwitchName : External
IPAddresses : {10.124.252.117, fe80::8d2d:7dca:4498:82f9, 2001:4898:200:13:fc0e:945e:ffce:2bb5,
2001:4898:200:13:8d2d:7dca:4498:82f9}

[sudo] END
Press Enter to exit …

L1 ビザ更新手続き

気づけばアメリカに来て丸 3 年が経とうとしています。技術力が成長しているかどうかは正直微妙なところですが、総合すると、日本よりは仕事がしやすい環境です。そんなことはいいのですが、私は未だに L1 ビザで、初回の有効期間が 3 年だったので日本で更新してきました。グリーンカード取得のプロセスとの兼ね合いや、社内での書類の準備などでバタバタしたので、まとめておこうと思います。

まず大前提ですが、L1 ビザの期限は 3 年です。正確に言うと、ビザ スタンプの期限は、パスポートに添付されているビザの Expiration Date として書かれており、2012 年以降に発行されたビザの場合は発行日から 5 年後のはずです (2016 年現在)。しかしこれは罠で、実際の滞在期限は、ビザ上に PED (= Petition End Date) として示されている日付で、こちらは発行日から 3 年後になっています。この日付が、アメリカ入国時に発行される I-94 の有効期限と一致するはずです。

L-1ビザの就労(滞在)期限とビザスタンプの期限について | SWLG P.C. Immigration News
http://www.swlgpc.com/jp/blog/2015/05/employment-period-and-visa-stamp-expiration-date-for-l-1-visas/

Lビザでの有効期限と滞在期限の違いについて | American Business Creation
http://abctny.com/immigrationnews/%EF%BD%8C%E3%83%93%E3%82%B6%E3%81%A7%E3%81%AE%E6%9C%89%E5%8A%B9%E6%9C%9F%E9%99%90%E3%81%A8%E6%BB%9E%E5%9C%A8%E6%9C%9F%E9%99%90%E3%81%AE%E9%81%95%E3%81%84%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6/

L-1 は駐在員ビザなので、基本的にはアメリカでの勤務先が移民局への延長申請などを行ってくれるはずです。ただし、ビザを更新する大前提として一度アメリカから出ないといけないこともあり、旅費や仕事上のスケジュール調整は自分でやらないといけません。したがって、まずは延長申請の全体のプロセスを理解しておくことが重要と思います。

簡単な流れは以下の通りです。基本的には新規申請と同じです。

  1. 勤務先が移民局への延長申請を行ない、その petition の Receipt Number が発行される。
    (https://egov.uscis.gov/casestatus/landing.do でステータスを確認できる)
  2. Receipt Number をもらって、申請者がオンラインで DS-160 フォームを送信し、領事館での面接を予約。
  3. 面接前に、勤務先から必要な申請書類を受け取っておく。I-129S, G-287, I-797, サポート レターなど。
  4. アメリカ出国。
  5. 領事館で面接を受け、パスポートを預ける。面接の最後に承認されたかどうかを教えてくれる。
  6. 滞在先でパスポートを郵送で受け取る。
  7. アメリカ入国。新しい PED で I-94 が発行される。

ポイントは、前述のようにアメリカを出ないといけないことです。アメリカ入国の時に I-94 が発行されるので、そもそも一度出国しないと新しい I-94 を発行してもらうことができないのです。では、我々日本人の場合は日本に帰らないといけないか、というと必須ではなく、基本的にはアメリカ以外ならどこでも OK です。例えばここシアトルの場合、最寄りの領事館であるカナダのバンクーバーで延長申請を行なうことは可能らしいです。ただし私の場合は、グリーンカード申請との兼ね合いもあって、リスクを最低限に抑えたかったので、高い旅費を犠牲にしても日本で延長することにしました。ちなみに社内のガイドには以下のように書かれています。

Visa stamps can be obtained at United States Consulates or Embassies outside of the United States. Procedures vary depending on consular location, so it is important that you familiarize yourself with the procedures at the location where you intend to apply well in advance of submitting the application. Most consulates require that an appointment be made in advance and that the application be submitted in-person by the visa applicant.

The general rule is that you should apply for a US visa stamp at a US consulate located in your home country. Some US consulates will accept visa stamp applications from persons who are not citizens or residents of the nation in which they are located. However, because the consulates have wide discretion in these matters and most will usually not accept applications from “third country nationals”, we generally recommend that you apply for US visa stamps in your home country.

Qualifying applicants renewing select US nonimmigrant visa types, whose most recent visa was issued in India, may be able to obtain a waiver allowing them to skip the process of scheduling an interview appointment at US consulates in India.

また、ある人がこんなことを言っていました。L-1 はあくまでも駐在員ビザであり、日本の会社に所属している人がアメリカの会社に駐在している、という体を取っている。書類に不備があった場合などは、領事館がそれを関係機関に確認しないといけないが、その場合は日本の会社に連絡が行くことが多い。このとき、第三国の領事館はそもそも日本の会社と連絡を取る必要があることを好ましく思わない、また、言語や時差の関係で連絡に時間がかかることが予想されるので、万が一に備えるならば日本の領事館に行ったほうがスムーズ。

ちなみに、トルコ人の上司は、初回の延長はトルコに行ったけど、二度目以降はバンクーバーで何の問題もなかったとも言っていました。

なお、日本で面接を受けることの欠点としては、旅費に加えて、発給までの期間が若干遅いことがあります。以下のページで、領事館ごとの面接の空き具合と、ビザ発給までの日数の目安を一応確認できます。

Visa Appointment & Processing Wait Times
https://travel.state.gov/content/visas/en/general/wait-times.html/

Petition の Receipt Number をもらって、どの国で面接を受けるかを決めたら、DS-160 のオンライン フォームを自分で記入して、面接の予約を行なうのが次のステップです。当然ながら飛行機のチケットや、日本での滞在先も自分で手配しないといけません。ここで問題になるのが、面接後何日でビザが発給されるかは決まっていないことです。一応上記のサイトで目安は確認できますが、最大日数が保証されているわけではありません。これについては、滞在期間を長めに確保する以外の方法はなく、滞在費が嵩むことは避けられません。そこで、上記サイトよりも遥かに役に立つのが↓の掲示板です。

ビザ取得情報データベース
http://www.kenkyuu.net/cgi-visa-survey/fvote-visa.cgi

各領事館で、発給にどれぐらいかかったかの投稿がまとめられています。大学の研究者向けのサイトなので、ほとんどが J1 ビザで、L1 とは勝手が違うとは思いますが、東京の場合で基本的に 1 週間、バッファーを含めて 10 日から 2 週間確保しておけば安全っぽいです。月曜か火曜日に面接を受けて、次の週の後半まで滞在するのが無難だと思います。領事館は土日休みですが、パスポートはレターパックで送られてくるので、土日に受け取ることもできます。私の場合は、面接を受けたのが水曜で、2 日後の金曜にパスポートが発送されて、日曜の朝に滞在先のホテルに届きました。

以下のような順番で手配を行うのが普通だと思います。まあお金がある人は適当でいいと思いますが・・。

  1. DS-160 を埋めて送信する (この中に Receipt Number を記入する欄があります)
  2. 面接の予約可能日を確認する
  3. 予約可能日をもとにフライト、ホテルの空きを検索
  4. 面接を予約
  5. フライト、ホテルを予約

DS-160 オンライン フォームの記入は以下のページからできます。最初のページで領事館の場所を選択します。

Nonimmigrant Visa – Instructions Page
https://ceac.state.gov/GenNIV/Default.aspx

DS-160 記入における特記事項は以下の通り。

Travel のページでビザの種類を L1 を選択すると、Application Receipt/Petition Number という項目が出てくるので、そこに勤務先から通知された Petition Number を入力します。

Previous U.S. Travel のページの最初の質問が "Have you ever been in the U.S.?" で、延長の場合は当然 Yes になります。すると、過去 5 回のアメリカ入国日と滞在期間を聞かれます。ビザの 3 年間で、日本への一時帰国を含めて何度アメリカを出入りしているわけですが、そんな小旅行をいちいち入力するのが面倒だったので、直近は 3 年間アメリカに滞在したことにしました。特に面接で聞かれることもなかったので、それでいいと思います。アバウトです。

同じ Previous U.S. Travel のページの最後の質問が、"Has anyone ever filed an immigrant petition on your behalf with the United States Citizenship and Immigration Services?" です。移民ビザやグリーンカードの申請を同時に行っている場合は Yes を選択します。ただし、petition という段階は I-140 の提出であり、PERM の申請は petition にはならないことに注意が必要です。私の場合は、グリーンカードの申請プロセスで PERM は承認済みで、AOS はまだファイルされていない状態でした。社内のガイドを見ると以下のように書かれていたので、No を選択しました。もし AOS、特に I-140 が既に申請されている場合は Yes を選択し、Explain の欄に以下に書いてあるようなコメントを書いておきます。

If any US employer has ever submitted a Form I-140 Immigrant Visa Petition for you to USCIS, then you should answer "yes." In the box that will appear under "Explain," you should enter: "[Company’s name] filed an I-140 for me with USCIS." For most employees, the I-140 is the second stage of the employment-based green card process, following the PERM labor certification.

次に迷ったのが Additional Work/Education/Training のページの "Do you have any specialized skills or training, such as firearms, explosives, nuclear, biological, or chemical experience?" という質問です。該当する人は少数だと思いますが、私の場合、学部が生物化学科だったので Yes に該当します。社内のガイドを見ると、以下のように書かれていました。したがって Yes を選択し Explain の欄には "I was a student of the Department of Biophysics & Biochemistry at The University of Tokyo." とか書いておきました。この回答について面接で質問来るかなと思いましたが、何も聞かれませんでした。補足資料の中に大学の成績証明書が入っていたので、特に不明な点はなかったのでしょう。よかった。

Answer this question truthfully. If you have ever taken any classes in the shooting of firearms, detonation of explosives or have studied the nuclear, biological or chemical sciences at any time, answer yes to this question and detail on a separate sheet of paper where and when you received this training, who trained you and why.

あとは特に引っかかる部分はありませんでした。DS-160 フォームを送信すると、確認番号 (DS-160 Confirmation Number) が発行されます。この番号を面接予約の時に入力するのでメモっておきます。

面接の予約は以下のサイトから行います。アカウントを作るときに国を聞かれるので、日本で面接を受ける場合は日本を選んでアカウントを作ります。

https://cgifederal.secure.force.com/

この段階で初めて正確な面接の空き日程を確認できるようになります。いきなり面接を予約してしまう前に、念のためフライトやホテルの空き状況をチェックしておきましょう。

日本のアメリカ領事館の場合、いくつかの条件を満たすと、面接なしの郵送だけでビザ更新の申請ができます。ただし、更新の際に本人が日本にいなければならないことに変わりはなく、郵送申請の場合、日本について成田などからすぐにパスポートを領事館に郵送し、あとはひたすら待つという流れになります。メリットはわざわざ領事館まで出向かなくてよい、という点ですが、面接の場合よりも時間がかかることが多いようです。また面接の場合には、面接終了時に結果がすぐ通知されるので安心感があります。

米国ビザ申請 | ビザを更新する – 日本 (日本語)
http://www.ustraveldocs.com/jp_jp/jp-niv-visarenew.asp

私はもともと面接ありのプロセスにしたかったのですが、面接予約のポータルが少々使いにくく、2 点ほど注意が必要でした。

まず、面接予約をしようとしている段階では、まだホテルを予約していません。しかし面接予約を完了するときに、日本の滞在先である住所を求められます。最終的にそれがパスポートの返送先になるわけですが、空欄のままだと面接を予約することができません。以下のページにあるように、面接当日まで住所を変更することはできるので、まずは適当な住所を入力して予約を完了させる必要があります。かといって嘘の住所を入力するのも憚られるので、最初は勤務先の住所を入れておきました。

米国ビザ申請 | 書類の郵送先住所を変更する – 日本 (日本語)
http://www.ustraveldocs.com/jp_jp/jp-niv-deliveryaddressmodify.asp

もう一つ注意点がありました。予約の際、郵送申請が可能かどうかを判別するための質問を聞かれ、条件がマッチすると勝手に郵送申請にカテゴライズされてしまい、面接日を選択することができなくなります。困った仕様です。この場合、New Application/Schedule Appointment をクリックして最初からやり直して下さい。このとき、新たに料金を支払ってしまわないように注意してください。最後の質問が確か、「今日本にいますか」的ものなので、No を選ぶと面接が必須になります。

面接の予約が終われば一安心で、あとはフライトとホテルを適当に予約します。私の場合は月火が空いていなくて水曜日が面接になりました。さすがに翌週の金曜日までにはビザは発送されるだろうと推測し、面接の翌々週の月曜日に帰る便を予約しました。日曜日でもよかったのですが、月曜のフライトが安かったのです。お金ないんで・・。ホテルを予約したら、もう一度面接予約のページに戻って、住所を変更します。スムーズにパスポートを受け取るためには、正確に住所を記述することがとても大事です。上記ページからの引用ですが、住所記述に際してよくあるミスは以下の通りです。

  • 自宅を選択した場合:マンション・アパート名、部屋番号、受取り人氏名がない。
  • 本人以外への配達を希望した場合:宿泊先(ホテル)名、大学および学部名がない。
  • 勤務先を選択した場合:社名、建物名(階数も含む)、受取り人氏名がない。
  • APO/FPO/DPOアドレスのみ記載され日本国内の住所がない(郵送は日本国内のみ可能)。
  • 郵送先住所ではなくメールアドレスが登録されている。

日本国内の郵送で使うのだから住所は日本語表記のほうがいいような気もするのですが、そのような記載が全くないので英語表記で書きます。このときはヴィラ・フォンテーヌ日本橋三越前に 14 泊する予定だったので、住所は以下のように書きました。

Address Line 1:
1-7-6 Honcho Nihombashi
Hotel Villa Fontaine Tokyo – Nihombashi Mitsukoshimae

City: Chuo-ku

State: Tokyo

Postal Code: 1030023

Contact Information の Phone Number のところは、日本の携帯番号がないので、+1 で始まるアメリカの携帯番号を書いておきました。日本滞在中はその番号に出られないのであまりよろしくないのですが。

面接の予約が終わったら、あとは日本へ行くだけ・・・なのですが、実はその前に必要な書類を受け取らないといけません。私の場合、これが一番厄介でした。というのも、次のようは不毛なメールのやり取りをしていたためです。意見食い違いすぎ。今見返すと、弁護士 (Attorney) の言っていることも分かるのですが、情報を小出しにされている感があります。

[2016/5/13 Fri.]

Me: "I’ve submitted DS-160. How can I get an approved I-129?"

Attorney: "You are applying for your L-1 visa at the Consulate, so the officer will approve your I-129S (L-1 application). The petition number for blanket L applications is the receipt number highlighted in the previous thread.
Please let me know your finalized travel plans and visa appointment date when finalized."

Me: "After I submitted DS-160 to the consulate in Tokyo/Japan, I received the confirmation card attached, which says I must bring an approved I-129. Do you mean it is not needed? Only passport is good enough for L-1 extension?"

Att: "We are preparing all of the documents that you need for the interview."

Me: "When you say ‘We are preparing’, is it expected I can receive those documents before the interview whenever I schedule it?"

Att: "Yes – which is why we need to know when you are departing and your appointment date."

Me: "That’s what I wanted to confirm. I thought I would schedule an interview *after* getting all required documents."

[2016/5/16 Mon.]

Me: "Below is my finalized travel plan:
Departure: May-29-2016
Interview: June-1-2016
Arrival to the US: June-13-2016"

Att: "Thank you. We will finalize your paperwork next week."

このメールの後この週は一切音沙汰なし。月曜なのに next week かよ意味分からん・・とか思いながら大人しく待ってたわけです。で、翌週の月曜の朝に電話がかかってきて、今からサポートレター送るからレビューしてくれ、みたいな感じ。でそのあとのメール。

[2016/5/23 Mon.]

Att: "As part of the application, we have prepared a support letter (attached). Please review the support letter for accuracy…
In order to finish preparing the petition to be ready before his departure this weekend, we kindly request that you review the letter at your earliest convenience."

ここで添付されてきたレター、なんと別の人の名前が書いてある。たぶんコピペミス。仕事が杜撰すぎ。この弁護士クビだろもう・・。その上、3 年前と違って更新の条件が厳しくなっているから正確なジョブ ディスクリプションを提出しろ、とかいろいろ言われる。いやそれ以前にお前が正確なレター送ってこいよ。この後不毛なやり取りが 2 日続く。そしてようやく。

[2016/5/25 Wed.]

Att: "I have incorporated the information provided in the previous threads to the draft of the support letter…"

Me: "This looks great to me. I can sign off."

[2016/5/26 Thu.]

Me: "Can I receive documents today?"

Att: "We will not have the packet ready for collection until around 1pm tomorrow. Please send me a meeting invite for after 1pm to collect your paperwork from my office."

翌日にやつのオフィスに直接出向いてようやく書類をゲット。この日が金曜で出発が日曜だから間一髪。面接の予約がもっと早かったらどうなっていたのか不明。まさに US クォリティ。

さらに、この週はアメリカ出国に対して、グリーンカードの AOS をどうするかという話を別の弁護士と不毛なやり取りをしていました。その弁護士には一度送った写真を紛失されるなど、同様に杜撰な仕事をされていたわけですがそれはまた別の機会に。

ここまで来ればあとは日本に行って面接を受けてくるだけです。以下のサイトを読んでおけば大丈夫でしょう。携帯の持ち込みができないので、時間を潰すための本や雑誌などを持っていったほうがいいです。あと、前に並んでいる人がライターの廃棄を余儀なくされていたので、タバコを吸う人は気を付けてください。

非移民ビザ | 東京, 日本 – 米国大使館
http://japanese.japan.usembassy.gov/j/visa/tvisaj-nivinterview-procedures.html

新規の時と違って、大使館に入ってから 5 分ほどで料金を支払うように言われて、その後 10 分ほどで面接に呼ばれました。面接で聞かれたのは、アメリカでの仕事内容と、今まで何年勤めているのか、の 2 点だけ。領事館がその場で I-129S にスタンプと署名をしてくれました。大使館の中にいたのは合計 30 分ぐらい。

アメリカ入国の際には、念のため承認済み I-129S などの書類は預け入れずに手荷物にしておきましょう。とはいうものの、初回の入国のときと同様、今回もパスポート以外の書類は不要で、入国審査官にビザを更新して一回目の入国であることを伝えると "Welcome back!" と言われて一瞬でスタンプを押されました。

なお、アメリカに戻ってきて 2 日後に AOS がファイルされました。さっさとグリーンカードが欲しい。

Evaluate search engine quality

ある日曜日にふと思いついたアイディアを実装して GitHub で公開してみました。それがこれ。

msmania/searchquality: Evaluate search engine quality
https://github.com/msmania/searchquality

検索エンジンの品質を数値化してみよう、という試みです。既に議論しつくされている話題であり、面接で聞かれる質問の定番でもありそうな問題です。私は検索エンジンの専門家ではないため基礎知識は全くなく、以下は単なる思いつきです。

さて、私は日常的に Bing と Google を検索エンジンとして使っていますが、どうにも Bing の検索結果は Google より劣っているように思えることが多々あります。最近明らかにおかしいと思った検索結果事例が↓の 2 つ。

  1. Bing で "seattle consulate japan" を検索したときに、領事館の公式サイト (http://www.seattle.us.emb-japan.go.jp/itprtop_ja/index.html) がトップに出てこないどころか、最初のページのどこにも出てこない。トップは yelp、2 番目は www.embassypages.com とかいう怪しいサイトになる。
  2. Bing で "gnu debugger" を検索したときに、GDB のプロジェクトのトップ https://www.gnu.org/software/gdb/ が最初のページに出てこない。

ちなみに Google 検索では、1. のケースは領事館のページがトップ、2. で GDB は最初のページの 2 番目に出てきます。

いずれの例にも共有していると考えられるのは、「ある検索キーワードに対して、大多数が正解と認めるような URL が定義できる」ことではないかと。基本的には、キーワードに対して、万人に共通する正解としての検索結果は定義できません。さらに同じユーザーであっても、検索するに至った目的やタイミングによって、その人が検索結果から最初にジャンプする URL 、もしくは最終的に満足を得た URL は変わるはずです。しかし上記の例については、その差異を加味したとしても最初のページに入っているべきなのではないかと思うのです。(ただし、広告からの収益と連動する今のビジネスモデルの場合、大人の事情によって公式サイトよりも優先しないといけないサイトがあって最初のページが埋まってしまうのかもしれませんが。)

結果の良し悪しを議論するのはさておいて、ある程度の確度で "正解っぽい URL" が定義できる検索キーワードのセットがあれば、それぞれの正解 URL が置かれた順位を集計して全体としての "品質" を数値化できるのではないか、というのが今回の思いつきです。そこで選んだのが Windows API の関数名と、その関数について記載している MSDN のページです。理由は以下の通り。

  • 関数名のみをキーワードとして検索するとき、MSDN で使い方を調べたいパターンが多い。もし使用例を調べたいのなら "example"、トラブルシューティングならエラーコードなどの追加キーワードが入るはず。
  • .NET のメソッドや POSIX 関数などの名前と重複するものが少ない。
  • API はたくさんあるので、データ数を稼ぎやすい。
  • Bing と MSDN はどちらも Microsoft のサービスであるが、MSDN に関しても経験上 Google の方がいい検索結果を出す気がする。Bing の場合、Windows CE の同名の関数のページに飛ぶことがある。

簡潔に言えば、この結果を受けて「Bing だめじゃん。ぷぷっ。」みたいなことをやりたいのです。

というわけで上記 GitHub のコードを使って、100 個の Windows API を選んで Google と Bing でそれぞれ検索してみました。本当は中国のBaidu (百度) でも試したかったのですが、中国語が読めなくて全然わからん・・。Yahoo は、どうせ中身が Google か Bing だったはずなのでパス。

で、結果なのですが、N=100 の検索結果に対して算術平均を取って Google が 0.119489、Bing が 0.1144965。あれ、ほとんど変わらない。この差がどのぐらいかというと、Google が最善解を 1 ページ目の 1 番目、次善解を 1 ページ目の 7.5 番目ぐらいに表示するのに対し、Bing は 1 番と 10 番あたりにに表示することを示しています。ちなみにこれは、検索結果ページがそれぞれ 10 の結果を表示する場合です。要は、検索結果ページの下の方の順位がちょこちょこっと変わっただけに過ぎないのです。なんか期待外れ・・・。もう少し別のデータセットで試してみたいところです。

いずれにしろ、定量的な議論はできるようになりました。以下、どうやってその数値を計算したかについて説明します。ただし、冒頭にも書いたように思い付きでやっているので、学術的に正しいかどうかは不明です。誰かこの記事をコピペして大学のレポートとして出して欲しい・・・。あと、詳しい人からのお便りは歓迎です。

まず、検索とは次のような操作であると定義します。

  • インターネット上にある無数の URL を、検索キーワードによって「いい感じに」並び替える
  • 検索結果は、有限個の URL を表示する「ページ」単位に分かれている

その結果を、ユーザーは以下のように判断します。

  • ユーザーは、欲しい情報が載っている URL を開きたい
  • ユーザーは、その URL を開くまでその URL に欲しい情報が載っているかどうか分からない
  • ユーザーにとって、ページ間を移動する操作とページ内をスクロールする操作はともに面倒くさい
  • ユーザーは、少ない操作で欲しい URL が開けるほど、その検索エンジンが高品質であると判断する

今回は、1 つの検索結果から品質を表すスコアとして 1 つのスカラー値を算出するものとします。

上述のように、今回は検索した関数名に対する MSDN の URL を正解と仮定するので、その正解の URL が上に来れば来るほど高得点になるような関数、例えば x 番目に来た時には逆数の 1/x をスコアとする、ことも可能です。しかし、1 番目に来たら 1 点で、2 番目に来たら 0.5 点、のように 2 倍も差が開いてしまうのは直感的に開きすぎているように思えます。

こういうときに機械学習などの分野でよく出てくるのが、確率密度関数です。というか t-SNE の論文やベイズ理論の本のせいで、確率密度がマイブームになっているので使ってみたかったのです。

Van der Maaten, L. J. P. & Hinton, G. E. Visualizing high-dimensional data using t-SNE. J. Mach. Learn. Res. 9, 2579–2605 (2008)

確率密度といえば、最初は何も考えずに標準正規分布から始めるのが(たぶん)流儀です。つまり、平均の付近で関数が極大になる性質を、検索結果の順位が上になるほど高いスコアを付加するという性質に適用します。そこで、まずページ内順位は無視して、とある検索結果が 1 ページ目に出たときのスコアを、確率変数が平均値の近傍にくる確率、2 ページ目に出たときのスコアをその外側の確率、というように適用することにします。すなわち数学的には、結果がページ i のどこかに存在するときのスコア p を

rankequations

と定義します。確率密度関数を使う利点は、標準偏差 (もしくは分散) をパラメーターとして、スコアを簡単に調整できることです。いわゆる 68–95–99.7 rule というやつです。

68–95–99.7 rule – Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/68%E2%80%9395%E2%80%9399.7_rule

式 (2) に含まれる σ1 がパラメーターとなる標準偏差であり、σ1 = 1 と設定した場合、1 ページ目に検索結果が来るスコア p1 = 0.68、2 ページ目のスコア p2 = 0.95-0.68 = 0.27、となります。つまり σ1 は、そのユーザーがいかに最初のページを重要視するか (= ページ遷移を嫌がるか)、という目安になります。σ1 = 0.5 と設定すると、p1 = 0.95 になり、全体の検索結果のほとんどを占めます。

次にページ内順位を評価する方法ですが、これはベイズ理論でいうところの事後確率として考えるのが自然で、ページ i に検索結果が来た後に、もう一つ別の標準正規分布に従う確率を考慮します。ただし、ページ数とは異なって 1 ページにおける URL の数は有限です。そこで、正規分布グラフの山のうち、確率が低い麓の部分を切り捨てて、残った有限の面積を全体の確率の 1 として考えます。すなわち、ページ サイズが n で、ページ i の順位 j におけるページ内ランク q を

rankequations

と定義します。式 (3) における偏差 σ2 は、そのユーザーがページ内の相対位置を重要視する程度 (= スクロールを嫌がるか) の目安になります。σ1 と同様、偏差はユーザーの性質の目安であるところがポイントです。別の方法として、ページ内ランクの偏差をページサイズ n と連動させる方法も考えられます。これは、同じユーザーがページ サイズの設定を変えて検索した時に、ページ内ランクに対する捉え方が変わるかどうか、という問題に帰結します。

長くなりましたが、上記のようにスコアの付け方を定義すると、総合的なランクは

rankequations

と定義できます。

例えば、2 ページはほとんど閲覧せず、ページ サイズは 10 でページ内は末尾までちゃんと見るユーザーとして (σ1, σ2, n) = (0.5, 10, 10) というパラメーターを使って、これを R でプロットすると以下のようになります。コードは GitHub の rank.R です。

image

ちなみに Google も Bing も、既定のページ サイズは 10 です。仮にページ サイズを 100 にしたところでほとんどのユーザーは 10 位以降の検索結果はクリックされないのかもしれません。

ただし、例えばパソコンに詳しいパワー ユーザーの場合、もしくは仕事でどうしても必要な情報がある場合は、1 ページ目に結果が出ないからといって諦めずに次のページ、さらにその次のページをチェックする確率が高くなることが予想されます。そういったユーザーを想定する場合は、1 つ目の偏差を大きく設定します。

ページ遷移とスクロールのどちらを面倒くさがるか、という問題もあります。もしスクロールしながら結果をちまちま確認するのを嫌がって、さくさくページ遷移をしていくユーザーがいる場合、1 ページ目の最下位にある結果より、2 ページ目の先頭にある結果のほうが注目されやすいかもしれません。例えば、(σ1, σ2, n) = (1, 5, 20) のグラフは以下の通りです。

image

これで、検索結果内の位置をランクに変換する式ができました。グラフを見ても、わりとそれっぽい形をしています。この後残っているのは、実際の検索結果のタイトルと URL を見て、それが正解だったかどうかを判断することです。これは以下の Python の関数で判断しています。

def EvaluateSearchResultForMSDN(keyword, pair):
    o = urlparse(pair[1])
    titlelow = pair[0].lower()
    return 1.0 if (o.hostname == ‘msdn.microsoft.com’) \
                   and (titlelow.startswith(keyword.lower())) \
                   and (‘(windows)’ in titlelow) \
               else .0

URL のホスト名とタイトルをチェックしているだけの簡単なもので、正解なら 1、それ以外は全て 0 点にします。この点数と、位置毎のランクの積の合計を検索結果全体のスコアと定義しました。

もともとは、1 つのキーワードに対して正解は 1 つで、それを 1 点として計算する予定だったのですが、上記の関数だと、検索結果に正解が 2 つ含まれるキーワードがあることに気付きました。例えば "CreateWindow" を検索したときに CreateWindow だけでなく、CreateWindowEx の MSDN ページにも 1 点を与えるためです。この判断は迷いますが、経験上 CreateWindowEx も CreateWindow と同程度参考になると判断して、このまま同じ価値を持つ正解として扱うことにしました。

こうして算出したスコアの平均が、冒頭に書いた Google = 0.119489, Bing = 0.1144965 です。このときのパラメーターは (σ1, σ2, n) = (0.5, 10, 10) と設定したため、1 位のランクは 0.111370 になるのですが、平均がこれを超えているのは、正解が 2 つ以上あるキーワードが多かったからです。

以上が、冒頭のように Bing と Google を評価した理由です。より一般的には、MSDN だけでなく全ての検索結果にスコアを定義できるはずです。というか、検索エンジン自身がそう言ったスコア (Relevancy Ranking とか言うのがそれだと思う) を使っているはずです。コンピューター将棋やチェスでいうところの局面の評価値にも似ています。ある人が、人間の活動はほとんど評価値アルゴリズムに基づいている、みたいなことを言っていましたが、まさにそんな感じ。

ここから余談です。検索結果を REST API で得たあと、さてどうやってスコアを組み立てようか考えているときにふと思ったのが、映画 「ソーシャル ネットワーク」 の冒頭のこのシーン。

Eduardo Saverin: Hey, Mark.
Mark Zuckerberg: Wardo.
Eduardo Saverin: You guy’s split up?
Mark Zuckerberg: How did you know that?
Eduardo Saverin: It’s on your blog.
Mark Zuckerberg: Yeah.
Eduardo Saverin: Are you all right?
Mark Zuckerberg: I need you.
Eduardo Saverin: I’m here for you.
Mark Zuckerberg: No I need the algorithm you used to rank chess players.

Eduardo Saverin: Are you okay?
Mark Zuckerberg: We’re ranking girls.
Eduardo Saverin: You mean other students.
Mark Zuckerberg: Yeah.
Eduardo Saverin: You think this is such a good idea.
Mark Zuckerberg: I need the algorithm. I need the algorithm.

The Social Network Quotes – ‘I invented Facebook.’
http://www.moviequotesandmore.com/social-network-quotes/

"I need the algorithm" と主張するザッカーバーグの気持ちが分かった。それが書きたかっただけです、はい。

もう一つまともな話を付け加えるとすれば、t-SNE の論文を最初に読んだときに、もともとの SNE の考え方で、高次元空間上における距離を条件付確率で表す発想の意味と、そのときの分散を恣意的に選べる理由が全く意味不明だったのですが、自分でやってみて何となくイメージが掴めるようになりました。t-SNE も自分で計算してみたいのですが、積分計算で躓いているダサい状況・・・。なんとかせねば。

WorkQueue Model with POSIX Threads

少し前の記事で書きましたが、MNIST を MDS で処理する計算は、全て Python で書いたせいかパフォーマンスが悪く、N=10000 のデータにも関わらず N=200 程度で 6 分もかかってしまい、話になりませんでした。

MNIST with MDS in Python | すなのかたまり
https://msmania.wordpress.com/2015/12/13/mnist-with-mds-in-python/

しかし、ここまでやってようやく気づいてしまったのは、Field クラスは C++ で書いてしまったほうがよかったかもしれない、ということ。Sandy Bridge だから行列計算に AVX 命令を使えば高速化できそう。というか Python の SciPy は AVX 使ってくれないのかな。ノードにかかる運動ベクトルをラムダ式のリストにしてリスト内包表記で計算できるなんてエレガント・・という感じだったのに。

そこで、AVX 命令を使って演算するモジュールを C++ で書いて Boost.Python 経由で読み込むように書き換えてみました。(ばねの力を計算する部分で少しアルゴリズムも少し変えています。) 結果、期待していたよりもパフォーマンスが上がり、N=1000 でも 1 分弱、N=10000 の場合でも 1 時間程度で結果を得ることができました。

パラメーターをいろいろ変えて試しているので動きが統一されていませんが、結果はそれなりに統一されています。例えば、青色 (=1) のデータは、データ間の距離がかなり短いらしく収束が早いことがすぐに分かります。逆に、灰色 (= 8) や白色 (= 7) のデータは他の数字と混じっており、ユークリッド距離だけだと区別が難しそうです。緑 (= 4) と紺色 (= 9) は同じエリアを共有しがちですが、確かに数字の形を考えると、似ていると言えなくもありません。。

http://ubuntu-web.cloudapp.net/ems/cmodule.htm

image

結果の考察はさておいて、もう少し欲を出してみたくなりました。そこで試みたのは 2 点。

  1. ノードを動かす前に、各ノード間をばねで繋ぐ際のユークリッド距離の計算が遅い
  2. オイラー法の計算の並列化

1. は未だ Python でやっており、N=10000 の場合だと、C(10000, 2) = 49,995,000 回も 784 次元座標のユークリッド距離を計算していることになるので、馬鹿にならない時間がかかります。入力データは変わらないので、予め全部の距離を計算してファイルに書き出しておくことにしました。おそらく、ファイルを読むだけの方が距離を計算するのよりは早いはずです。

2. はそのままマルチスレッド化です。1 時間も 1 CPU だけが仕事をしているのは何かもったいないので、何とか並列化したいところ。アイディアとしては、扱っている 2 次元データを次元毎にスレッドを分けて計算したい、というものです。

結果から書くと、1 は成功、2 は失敗です。1. だけ実装して、N=10000 で 1 時間を切ることはできました。

計算の大部分を占めるのが、Field::Move で、最初にばねの力を足し合わせるためのループから Field::Spring::load を呼んでいます。次元毎に処理を分けるのは Move() 後半のループで、コード自体は簡単に書けましたが、パフォーマンスはほぼ同じか、少し悪くなりました。前半のばねの計算のところでは、ばね毎の計算を分けて各スレッドに割り振ってみましたが、こちらのパフォーマンスは最悪で、2 倍以上落ちました。

void Field::Spring::load() {
    std::valarray<double> diff(_field->_dim);
    int i, n = _field->_m.size();
    double norm = .0;
    for (i = 0 ; i < _field->_dim ; ++i) {
        diff[i] = _field->_position[_n2 + i * n] – _field->_position[_n1 + i * n];
        norm += diff[i] * diff[i];
    }
    norm = sqrt(norm);
    for (i = 0 ; i < _field->_dim ; ++i) {
        double f = _k * (1 – _l / norm) * diff[i];
        _field->_accel[_n1 + n * i] += f / _field->_m[_n1];
        _field->_accel[_n2 + n * i] += -f / _field->_m[_n2];
    }
}

void Field::Move(double dt) {
    int i, j, n = _m.size();
    _accel = .0;
    for (auto &f : _forces) {
        if (f != nullptr) {
            f->load(); <<<< この呼び出しを WorkItem にする
        }
    }
    for (i = 0 ; i < _dim ; ++i) {
        for (j = 0 ; j < n ; ++j) { <<<< このループを WorkItem にする
            int idx = j + i * n;
            _velocity[idx] += dt * _accel[idx];
            _velocity[idx] -= _velocity[idx] * _friction[j] / _m[j];
            _position[idx] += dt * _velocity[idx];
        }
    }
}

コードは dev-mt ブランチにまとめています。コミットの順番を間違えた上、マージのやり方も微妙でコミット履歴がぐちゃぐちゃ・・

msmania/ems at dev-mt · GitHub
https://github.com/msmania/ems/tree/dev-mt

Linux でマルチスレッドのプログラムをまともに書いたことがなかったので、最善か分かりませんが、Windows でよくある、WorkQueue/WorkItem モデル (正式名称が分からない) を POSIX Thread を使って一から書きました。もしかすると標準や Boost に既にいいのがありそうですが。

ヘッダーの workq.h

class WorkQueue {
public:
    class Job {
    public:
        virtual ~Job() {}
        virtual void Run() = 0;
    };

private:
    enum WorkItemType {
        wiRun,
        wiExit,
        wiSync
    };

    class Event {
    private:
        pthread_mutex_t _lock;
        pthread_cond_t _cond;
        int _waitcount;
        int _maxcount;

    public:
        Event(int maxcount);
        virtual ~Event();
        void Wait();
    };

    class WorkItem {
    private:
        WorkItemType _type;
        void *_context;

    public:
        WorkItem(WorkItemType type, void *context);
        virtual ~WorkItem();
        virtual void Run();
    };

    int _numthreads;
    std::vector<pthread_t> _threads;
    Event _sync;
    pthread_mutex_t _taskqlock;
    std::queue<WorkItem*> _taskq;

    static void *StartWorkerthread(void *p);
    void *Workerthread(void *p);

public:
    WorkQueue(int numthreads);
    virtual ~WorkQueue();
    int CreateThreads();
    void JoinAll();
    void AddTask(Job *job);
    void Sync();
    void Exit();
};

ソースの workq.cpp

#include <pthread.h>
#include <unistd.h>
#include <vector>
#include <queue>
#include "workq.h"

#ifdef _LOG
#include <stdio.h>
#define LOGINFO printf
#else
#pragma GCC diagnostic ignored "-Wunused-value"
#define LOGINFO
#endif

WorkQueue::Event::Event(int maxcount) : _waitcount(0), _maxcount(maxcount) {
    pthread_mutex_init(&_lock, nullptr);
    pthread_cond_init(&_cond, nullptr);
}

WorkQueue::Event::~Event() {
    pthread_cond_destroy(&_cond);
    pthread_mutex_destroy(&_lock);
}

// Test Command: for i in {1..1000}; do ./t; done
void WorkQueue::Event::Wait() {
    LOGINFO("[%lx] start:wait\n", pthread_self());
    pthread_mutex_lock(&_lock);
    if (__sync_bool_compare_and_swap(&_waitcount, _maxcount, 0)) {
        pthread_cond_broadcast(&_cond);
    }
    else {
        __sync_fetch_and_add(&_waitcount, 1);
        pthread_cond_wait(&_cond, &_lock);
    }
    pthread_mutex_unlock(&_lock);
}

WorkQueue::WorkItem::WorkItem(WorkItemType type, void *context)
    : _type(type), _context(context) {}

WorkQueue::WorkItem::~WorkItem() {}

void WorkQueue::WorkItem::Run() {
    switch (_type) {
    case wiExit:
        LOGINFO("[%lx] exiting\n", pthread_self());
        pthread_exit(nullptr);
        break;
    case wiSync:
        if (_context) {
            ((Event*)_context)->Wait();
        }
        break;
    case wiRun:
        ((Job*)_context)->Run();
        break;
    default:
        break;
    }
}

void *WorkQueue::StartWorkerthread(void *p) {
    void *ret = nullptr;
    if (p) {
        ret = ((WorkQueue*)p)->Workerthread(p);
    }
    return ret;
}

void *WorkQueue::Workerthread(void *p) {
    while (true) {
        WorkItem *task = nullptr;
        pthread_mutex_lock(&_taskqlock);
        if (!_taskq.empty()) {
            task = _taskq.front();
            _taskq.pop();
        }
        pthread_mutex_unlock(&_taskqlock);
        if (task != nullptr) {
            task->Run();
            delete task;
        }
        else {
            usleep(10000);
        }
    }
}

WorkQueue::WorkQueue(int numthreads) : _numthreads(numthreads), _sync(numthreads) {
    pthread_mutex_init(&_taskqlock, nullptr);
    _threads.reserve(numthreads);
}

WorkQueue::~WorkQueue() {
    if (_threads.size() > 0) {
        JoinAll();
    }
    pthread_mutex_destroy(&_taskqlock);
}

int WorkQueue::CreateThreads() {
    int ret = 0;
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
    for (int i = 0; i<_numthreads ; ++i) {
        pthread_t p = 0;
        ret = pthread_create(&p, &attr, StartWorkerthread, this);
        if (ret == 0) {
            _threads.push_back(p);
        }
        else {
            LOGINFO("pthread_create failed – %08x\n", ret);
            break;
        }
    }
    pthread_attr_destroy(&attr);
    return ret;
}

void WorkQueue::JoinAll() {
    for (auto &t : _threads) {
        pthread_join(t, nullptr);
    }
    _threads.clear();
}

void WorkQueue::AddTask(Job *job) {
    pthread_mutex_lock(&_taskqlock);
    _taskq.push(new WorkItem(wiRun, job));
    pthread_mutex_unlock(&_taskqlock);
}

void WorkQueue::Sync() {
    pthread_mutex_lock(&_taskqlock);
    for (int i = 0 ; i<_numthreads; ++i) {
        _taskq.push(new WorkItem(wiSync, &_sync));
    }
    pthread_mutex_unlock(&_taskqlock);
    _sync.Wait();
}

void WorkQueue::Exit() {
    pthread_mutex_lock(&_taskqlock);
    for (int i = 0 ; i<_numthreads; ++i) {
        _taskq.push(new WorkItem(wiExit, nullptr));
    }
    pthread_mutex_unlock(&_taskqlock);
}

WorkQueue クラスがキューを持っていて、各ワーカー スレッドが放り込まれた WorkItem を逐次処理します。それに加えてある種の同期処理を付け加えました。今回の例で言えば、ばねの力を計算する WorkItem を全部投げ終わった後、速度や位置の計算をするためには、全てのばねの計算が完了していないといけません。つまり、WorkItem が全て処理されたかどうかを WorkQueue 側で判断できる機構が必要になります。

同期処理は、pthread に加えて条件変数 (condition varialbe) を使って実現しています。これは Windows のカーネル オブジェクトの一つであるイベントに似ています。WorkQueue::Sync() を呼ぶと、条件変数のシグナル待ちを引き起こす WorkItem をワーカー スレッドの数だけ投げ込んで、待機状態になったスレッドの数がワーカー スレッドと同じになるまで、Sync() を呼び出しているスレッドもを待機させておく、という動作を行ないます。

話を戻して、ばねの力の計算、すなわち Field::Spring::load() の並列化が失敗した原因は明白で、個々のワークアイテムが細かすぎたことと、ばねの力を加速度のベクトルに代入するときに排他ロックを獲得する必要があるからでしょう。これのせいで、WorkItem を出し入れしているコストがだいぶ高くついてしまいます。もし double をアトミックに加算する命令があれば排他ロックしなくてもいいのですが・・・。アルゴリズムでカバーするとすれば、ばねにつながっているノードがスレッドごとに重複しないように WorkItem を分ける方法がありますが、これだと、全部で C(10000, 2) = 49,995,000ある計算を C(5000, 2) 12,497,500 分は 2 スレッドで処理して残りの 25,000,000 は 1 スレッドで処理する、という感じになって、大して得しなそうなので断念しました。他にもっとうまい分け方を思いついたら試してみます。

速度と位置の計算は、単純に次元毎にスレッドを分けられるため排他ロックの必要はありませんが、やはり WorkItem が細かいので並列化のコストのほうが高くなってしまったのだと考えられます。3 次元プロットだったら使えるのかもしれませんが、まだそこまで手を出す段階じゃない・・。

こんなので土曜日が無駄になってしまった。もったいない。

Use matplotlib in a virtualenv with your own Python build

真っ新の状態の Ubuntu 15.10 に、Python 2.7 をソースからビルドして、matplotlib を virtualenv で動かせるようになるまで一日ぐらいハマったので、コマンドをまとめておきます。

まず、ビルドに必要なパッケージを入れます。

sudo apt-get update
sudo apt-get install build-essential git openssh-server vim

今回インストールするパッケージは以下の通り。2016/1/4 時点での最新バージョンです。

名前 URL バージョン 依存関係
OpenSSL http://www.openssl.org/source/ 1.0.2e なし
zlib http://zlib.net/ 1.2.8 なし
Tcl http://tcl.tk/software/tcltk/download.html 8.6.4 なし
Tk http://tcl.tk/software/tcltk/download.html 8.6.4 Tcl
libx11-dev
Python https://www.python.org/downloads/ 2.7.11 OpenSSL
zlib
Tcl
Tk

Python 以外にソースからビルドが必要になるコンポーネントの理由は↓。もちろん apt-get でインストールすることもできます。

  • numpy/scipy/matplotlib をインストールするときに pip を使う
  • pip は HTTPS で zip をダウンロードしてくるので、OpenSSL と zlib が必要
  • matplotlib でプロットを GUI 表示するために ビルトイン モジュールである _tkinter が必要

まずは OpenSSL。コードは GitHub からクローンします。

$ git clone https://github.com/openssl/openssl.git
$ cd openssl/
$ git checkout refs/tags/OpenSSL_1_0_2e
$ ./config shared –prefix=/usr/local/openssl/openssl-1.0.2e
$ make
$ sudo make install
$ sudo ln -s /usr/local/openssl/openssl-1.0.2e /usr/local/openssl/current

次 zlib。

$ wget http://zlib.net/zlib-1.2.8.tar.gz
$ tar -xvf zlib-1.2.8.tar.gz
$ cd zlib-1.2.8/
$ ./configure –prefix=/usr/local/zlib/zlib-1.2.8
$ make
$ sudo make install
$ sudo ln -s /usr/local/zlib/zlib-1.2.8 /usr/local/zlib/current

次 Tcl。

$ wget http://prdownloads.sourceforge.net/tcl/tcl8.6.4-src.tar.gz
$ tar -xvf tcl8.6.4-src.tar.gz
$ cd tcl8.6.4/unix/
$ ./configure –prefix=/usr/local/tcl/tcl-8.6.4 –enable-shared
$ make
$ sudo make install
$ sudo ln -s /usr/local/tcl/tcl-8.6.4 /usr/local/tcl/current

そして Tk。

$ sudo apt-get install libx11-dev
$ wget
http://prdownloads.sourceforge.net/tcl/tk8.6.4-src.tar.gz
$ tar -xvf tk8.6.4-src.tar.gz
$ cd tk8.6.4/unix/
$ ./configure –prefix=/usr/local/tk/tk-8.6.4 –enable-shared \
–with-tcl=/usr/local/tcl/current/lib
$ make
$ sudo make install
$ sudo ln -s /usr/local/tk/tk-8.6.4 /usr/local/tk/current

ちなみに libx11-dev がインストールされていないと、以下のコンパイル エラーが出ます。

In file included from /usr/src/tk8.6.4/unix/../generic/tkPort.h:21:0,
                 from /usr/src/tk8.6.4/unix/../generic/tkInt.h:19,
                 from /usr/src/tk8.6.4/unix/../generic/tkStubLib.c:14:
/usr/src/tk8.6.4/unix/../generic/tk.h:96:25: fatal error: X11/Xlib.h: No such file or directory
compilation terminated.
Makefile:1164: recipe for target ‘tkStubLib.o’ failed

ここまでは余裕です。次に Python をビルドします。

$ wget https://www.python.org/ftp/python/2.7.11/Python-2.7.11.tgz
$ tar -xvf Python-2.7.11.tgz
$ cd Python-2.7.11/
$ export LDFLAGS=’-L/usr/local/openssl/current/lib -L/usr/local/zlib/current/lib -L/usr/local/tcl/current/lib -L/usr/local/tk/current/lib’
$ export CPPFLAGS=’-I/usr/local/openssl/current/include -I/usr/local/zlib/current/include -I/usr/local/tcl/current/include -I/usr/local/tk/current/include’
$ export LD_LIBRARY_PATH=/usr/local/openssl/current/lib:/usr/local/zlib/current/lib:/usr/local/tcl/current/lib:/usr/local/tk/current/lib
$ ./configure –prefix=/usr/local/python/python-2.7.11 \
–enable-shared –enable-unicode=ucs4
$ make
$ sudo make install
$ sudo ln -s /usr/local/python/python-2.7.11 /usr/local/python/current

make の最後に以下のようなログが出力されるので、必要なビルトイン モジュール (_ssl, _tkinter, zlib) がコンパイルされ、ログに表示されていないことを確認してください。

Python build finished, but the necessary bits to build these modules were not found:
_bsddb             _curses            _curses_panel
_sqlite3           bsddb185           bz2
dbm                dl                 gdbm
imageop            readline           sunaudiodev
To find the necessary bits, look in setup.py in detect_modules() for the module’s name.

失敗例を示します。以下の例では、zlib と _ssl がコンパイルされていないので、後続の手順を実行できません。

Python build finished, but the necessary bits to build these modules were not found:
_bsddb             _curses            _curses_panel
_sqlite3           bsddb185           bz2
dbm                dl                 gdbm
imageop            readline           sunaudiodev
zlib
To find the necessary bits, look in setup.py in detect_modules() for the module’s name.

Failed to build these modules:
_ssl

Python ビルド時のポイントは以下の通りです。

  • ヘッダーやライブラリの有無を自動的に確認し、存在する場合のみモジュールが インストールされる
    (Apache の configure のように、–with-xxx というオプションは存在しない)
  • 予めビルドしておいた zlib や tcl/tk のパスを認識させる必要がある
  • configure 前に環境変数 LDFLAGS, CPPFLAGS を設定しておくと、configure で Makefile に値が反映される
  • ビルトイン モジュールがロードされたときに、依存関係のある共有モジュール tcl/tk を正しく見つからければならないため、環境変数 LD_LIBRARY_PATH で対応
    (後述するが、LD_LIBRARY_PATH ではなく ldconfig でグローバルに追加しておいてもよい。というかその方が楽。)

ここでハマりやすいポイントは共有モジュールの検索パスの追加です。共有モジュールが見つからないと、ビルド後のエクスポート関数のチェックで失敗して、以下のようなエラーが出ます。

// OpenSSL の共有モジュールが見つからない場合
*** WARNING: renaming "_ssl" since importing it failed: build/lib.linux-x86_64-2.7/_ssl.so: undefined symbol: SSLv2_method

// Tcl/Tk の共有モジュールが見つからない場合
*** WARNING: renaming "_tkinter" since importing it failed: build/lib.linux-x86_64-2.7/_tkinter.so: undefined symbol: Tcl_GetCharLength

余談になりますが、./configure –help でパラメーターを確認すると、–with-libs オプションと LIBS 環境変数を使って、追加のライブラリをリンクすることができるように書かれています。今回は共有ライブラリなので、これらのオプションを使ってライブラリを追加する必要がありませんが、実は LIBS 環境変数は罠で、–with-libs オプションを使わないと駄目です。configure を実行すると、–with-libs の値を含めて LIBS 変数を一から作るので、configure 前に LIBS を指定しても上書きされてしまいます。また、ヘルプの書式も分かりにくいのですが、configure は –with-libs の値をそのまま LIBS に追加し、それがリンカのパラメーターの一部になります。したがって、仮に –with-libs を使うときは –with-libs=’-lssl -lz’ というように -l オプションをつけないといけません。実に紛らわしいヘルプです。

$ /usr/src/Python-2.7.11/configure –help
`configure’ configures python 2.7 to adapt to many kinds of systems.

Usage: /usr/src/Python-2.7.11/configure [OPTION]… [VAR=VALUE]…

(snip)

  –with-libs=’lib1 …’  link against additional libs

(snip)

  CFLAGS      C compiler flags
  LDFLAGS     linker flags, e.g. -L<lib dir> if you have libraries in a
              nonstandard directory <lib dir>
  LIBS        libraries to pass to the linker, e.g. -l<library>
  CPPFLAGS    (Objective) C/C++ preprocessor flags, e.g. -I<include dir> if
              you have headers in a nonstandard directory <include dir>
  CPP         C preprocessor

(snip)

これで Python の準備はできました。次に pip をインストールします。方法は幾つかありますが、ここでは get-pip.py を使います。

Installation — pip 7.1.2 documentation
https://pip.pypa.io/en/stable/installing/

ダウンロード時になぜか証明書エラーが出るので –no-check-certificate オプションをつけていますが、基本的には不要です。

$ wget –no-check-certificate https://bootstrap.pypa.io/get-pip.py
$ sudo -H /usr/local/python/current/bin/python get-pip.py

今までの手順通りにやると、ここでエラーが出るはずです。

$ sudo -H /usr/local/python/current/bin/python get-pip.py
Traceback (most recent call last):
  File "get-pip.py", line 17759, in <module>
    main()
  File "get-pip.py", line 162, in main
    bootstrap(tmpdir=tmpdir)
  File "get-pip.py", line 82, in bootstrap
    import pip
  File "/tmp/tmpuPVaWi/pip.zip/pip/__init__.py", line 15, in <module>
  File "/tmp/tmpuPVaWi/pip.zip/pip/vcs/subversion.py", line 9, in <module>
  File "/tmp/tmpuPVaWi/pip.zip/pip/index.py", line 30, in <module>
  File "/tmp/tmpuPVaWi/pip.zip/pip/wheel.py", line 35, in <module>
  File "/tmp/tmpuPVaWi/pip.zip/pip/_vendor/distlib/scripts.py", line 14, in <module>
  File "/tmp/tmpuPVaWi/pip.zip/pip/_vendor/distlib/compat.py", line 31, in <module>
ImportError: cannot import name HTTPSHandler

理由は、sudo で実行している python には LD_LIBRARY_PATH によるライブラリの検索パスが反映されていないためです。sudo -H LD_LIBRARY_PATH=*** /usr/local/python/current/bin/python *** というように一行で実行することもできますが、システム ワイドに検索パスを追加しておいた方が後々楽です。

ここでは /etc/ld.so.conf.d/local.conf というファイルを新しく作って ldconfig を実行します。

john@ubuntu1510:/usr/src$ sudo vi /etc/ld.so.conf.d/local.conf <<< 作成
john@ubuntu1510:/usr/src$ cat /etc/ld.so.conf.d/local.conf
/usr/local/openssl/current/lib
/usr/local/zlib/current/lib
/usr/local/tcl/current/lib
/usr/local/tk/current/lib

john@ubuntu1510:/usr/src$ sudo ldconfig
john@ubuntu1510:/usr/src$ ldconfig -v | grep ^/ <<< 確認
/sbin/ldconfig.real: Path `/lib/x86_64-linux-gnu’ given more than once
/sbin/ldconfig.real: Path `/usr/lib/x86_64-linux-gnu’ given more than once
/usr/lib/x86_64-linux-gnu/libfakeroot:
/usr/local/lib:
/usr/local/openssl/current/lib:
/usr/local/zlib/current/lib:
/usr/local/tcl/current/lib:
/usr/local/tk/current/lib:

/lib/x86_64-linux-gnu:
/sbin/ldconfig.real: /lib/x86_64-linux-gnu/ld-2.21.so is the dynamic linker, ignoring

/usr/lib/x86_64-linux-gnu:
/usr/lib/x86_64-linux-gnu/mesa-egl:
/usr/lib/x86_64-linux-gnu/mesa:
/lib:
/usr/lib:
/sbin/ldconfig.real: Can’t create temporary cache file /etc/ld.so.cache~: Permission denied

これで get-pip.py はうまく実行できるはずです。

$ sudo -H /usr/local/python/current/bin/python get-pip.py
[sudo] password for john:
Collecting pip
  Downloading pip-7.1.2-py2.py3-none-any.whl (1.1MB)
    100% |????????????????????????????????| 1.1MB 204kB/s
Collecting setuptools
  Downloading setuptools-19.2-py2.py3-none-any.whl (463kB)
    100% |????????????????????????????????| 466kB 693kB/s
Collecting wheel
  Downloading wheel-0.26.0-py2.py3-none-any.whl (63kB)
    100% |????????????????????????????????| 65kB 5.4MB/s
Installing collected packages: pip, setuptools, wheel
Successfully installed pip-7.1.2 setuptools-19.2 wheel-0.26.0

pip がインストールされたので、これを使って virtualenv をインストールします。本来であれば、この時点で /usr/local/bin/pip のようなスクリプトが作られて、pip コマンドを実行できるはずなのですか、これまでの手順だとなぜか作られません。それほど支障にはならないので、pip コマンドの代わりに python -m pip <command> という風に python を直に実行します。

$ sudo -H /usr/local/python/current/bin/python -m pip install virtualenv
Collecting virtualenv
  Downloading virtualenv-13.1.2-py2.py3-none-any.whl (1.7MB)
    100% |????????????????????????????????| 1.7MB 333kB/s
Installing collected packages: virtualenv
Successfully installed virtualenv-13.1.2

virtualenv 環境を作ります。

$ /usr/local/python/current/bin/python -m virtualenv ~/Documents/pydev
New python executable in /home/john/Documents/pydev/bin/python
Installing setuptools, pip, wheel…done.
$ cd ~/Documents/pydev/
$ source bin/activate
(pydev)$

virtualenv 内では pip コマンドが使えます。依存パッケージを予めインストールし、普通に pip を使うだけです。

$ sudo apt-get install libblas-dev libatlas-dev liblapack-dev \
gfortran libfreetype6-dev libpng12-dev
$ pip install numpy scipy matplotlib

依存パッケージが存在しなかった時のエラーは以下の通りです。

// scipy インストール時のエラー (1)
  File "scipy/linalg/setup.py", line 20, in configuration
    raise NotFoundError(‘no lapack/blas resources found’)
numpy.distutils.system_info.NotFoundError: no lapack/blas resources found

// scipy インストール時のエラー (2)
building ‘dfftpack’ library
error: library dfftpack has Fortran sources but no Fortran compiler found

// matplotlib インストール時のエラー
* The following required packages can not be built:
* freetype, png

最後に、scatter plot のサンプルを使って動作確認をします。

shapes_and_collections example code: scatter_demo.py — Matplotlib 1.5.0 documentation
http://matplotlib.org/examples/shapes_and_collections/scatter_demo.html

(pydev)$ export TK_LIBRARY=/usr/local/tk/current/lib/tk8.6
(pydev)$ wget
http://matplotlib.org/mpl_examples/shapes_and_collections/scatter_demo.py
(pydev)$ python scatter_demo.py

以下のようなプロットが表示されれば成功です。

scatterdemo

ここで環境変数 TK_LIBRARY を設定しているのは、python からは Tcl が呼ばれているらしく、tk.tcl の検索パスが /usr/local/tcl であり、/usr/local/tk を検索してくれないためです。ファイルは tk 以下にあります。

$ find /usr/local -name tk.tcl
/usr/local/tk/tk-8.6.4/lib/tk8.6/tk.tcl

具体的には、以下のようなエラーが出ます。

  File "/usr/local/python/current/lib/python2.7/lib-tk/Tkinter.py", line 1814, in __init__
    self.tk = _tkinter.create(screenName, baseName, className, interactive, wantobjects, useTk, sync, use)
_tkinter.TclError: Can’t find a usable tk.tcl in the following directories:
    /usr/local/tcl/tcl-8.6.4/lib/tcl8.6/tk8.6 /usr/local/tcl/tcl-8.6.4/lib/tk8.6
/home/john/Documents/pydev/lib/tk8.6 /home/john/Documents/lib/tk8.6 /home/john/Documents/pydev/library

環境変数で対応するのが気持ち悪い場合は、Tcl と Tk を同じディレクトリにインストールしてしまうという手があります。tcl と tk の代わりに、tktcl というディレクトリを作った場合の例を以下にします。こっちのほうがシンプルになってよいかもしれません。

$ wget http://prdownloads.sourceforge.net/tcl/tcl8.6.4-src.tar.gz
$ tar -xvf tcl8.6.4-src.tar.gz
$ cd tcl8.6.4/unix/
$ ./configure –prefix=/usr/local/tktcl/tktcl-8.6.4 –enable-shared
$ make
$ sudo make install
$ sudo ln -s /usr/local/tktcl/tktcl-8.6.4 /usr/local/tktcl/current

$ sudo apt-get install libx11-dev
$ wget
http://prdownloads.sourceforge.net/tcl/tk8.6.4-src.tar.gz
$ tar -xvf tk8.6.4-src.tar.gz
$ cd tk8.6.4/unix/
$ ./configure –prefix=/usr/local/tktcl/tktcl-8.6.4 –enable-shared \
–with-tcl=/usr/local/tktcl/current/lib
$ make
$ sudo make install

$ cat /etc/ld.so.conf.d/local.conf
/usr/local/openssl/current/lib
/usr/local/zlib/current/lib
/usr/local/tktcl/current/lib

$ wget https://www.python.org/ftp/python/2.7.11/Python-2.7.11.tgz
$ tar -xvf Python-2.7.11.tgz
$ cd Python-2.7.11/
$ export LDFLAGS=’-L/usr/local/openssl/current/lib -L/usr/local/zlib/current/lib -L/usr/local/tktcl/current/lib’
$ export CPPFLAGS=’-I/usr/local/openssl/current/include -I/usr/local/zlib/current/include -I/usr/local/tktcl/current/include’
$ ./configure –prefix=/usr/local/python/python-2.7.11 \
–enable-shared –enable-unicode=ucs4
$ make
$ sudo make install
$ sudo ln -s /usr/local/python/python-2.7.11 /usr/local/python/current

今回紹介した matplotlib を virtualenv で使う方法は、ずいぶんとハマっている人が多いです。最初につまずくのは、plt.show() を実行しても何も表示されないという現象です。ほとんどの場合において、Python の _tkinter モジュールが正しくインストールされていないため、matplotlib の backend が non-interactive の agg になっていることが理由と考えられます。これは matplotlib をインポートした後に get_backend() を実行することで確認できます。

// GUI が表示される場合
>>> import matplotlib
>>> matplotlib.get_backend()
u’TkAgg’

// GUI が表示されない場合
>>> import matplotlib
>>> matplotlib.get_backend()
u’agg’

Matplotlib のページを見ると、virtualenv を作るときに –system-site-packages オプションを使うと解決できる、とも書かれていますが、少なくとも今回紹介した手順では、このオプションを使わなくても GUI 表示が可能でした。

Working with Matplotlib in Virtual environments — Matplotlib 1.5.0 documentation
http://matplotlib.org/faq/virtualenv_faq.html