「Trusting Trust」攻撃に対抗する

シュナイアーさんによるblogエントリ( https://www.schneier.com/blog/archives/2006/01/countering_trus.html )は、もう10年も前ですので、その世界では特に新しい話題というわけではないようですが、私が知ったのは今年のはじめのことでしたので*1、この機会に紹介する文章を書いてみたいと思います。

Unixを作ったケン・トンプソンさんがチューリング賞を受賞された際の講演「信用を信用することができるだろうか」( Reflections on Trusting Trust )は、その暴露的な部分(UNIXのloginコマンドにバックドアがあった、とする)の真偽はさておき、もしコンパイラバイナリが「信用できない」ものだったら、という場合における、潜在的な脅威の可能性を否定することの難しさの指摘でした。

以下で述べる話題は、直接的な「コンパイラバイナリを精読する」といった手段と比べると、大幅に省力的で、また、そのような可能性に対してある種の「相対的」安全性という考え方を示すものにもなっています。

詳細は、デイヴィッド・ホイーラーさん*2D論 Fully Countering Trusting Trust through Diverse Double-Compiling( http://www.dwheeler.com/trusting-trust/dissertation/html/wheeler-trusting-trust-ddc.html )となっていて、だいぶ大部ですが(私も全部は追いきれていません)、基本的なアイディアのスケッチは、けっこう以前からUSENETで議論されていたという程度には、簡単なものです。

まず基本的な問題について確認

トンプソンさんの講演の詳細を知っている方は、この節は飛ばして問題ありません。

しばしば、オープンソースのプロダクトは、たくさんの目でソースコードがチェックされているのだから安心だ、と主張されます。その当否はともかくとして、その大前提に、コンパイラは絶対に信用できるものだ、という仮定があります。

しかし、本当にコンパイラは信用できるのでしょうか? 噂では、性能比較に使われるベンチマークプログラムはその目的上、共通のものが広く公開されているので、そのパターンを検出して特別な最適化を掛ける、というチートが仕込まれていたコンパイラがあった、といいます。もしそれが単なる最適化ではなく、対象にバックドアを仕込むようなものだったら?

コンパイラだってオープンソースコンパイラなんだから大丈夫! でもそのコンパイラコンパイルするコンパイラに何か仕込まれていたら? 理屈では、一種の自己再生プログラム(いわゆるクワイン)のテクニックを利用して、ソースコードには何の痕跡も残さずに、コンパイラバイナリから、それによってコンパイルされた、次の世代のコンパイラバイナリへ、と、悪意を持ったコード片を「感染」させ続けることが可能です(プログラムのテクニック自体としては、一種のパズルのようなものとして知られていたものではあるものの、そのようにセキュリティに対する深刻な脅威として、可能性があると(広く注目されるような場で)示したのが、トンプソンさんのチューリング賞講演でした)*3*4

すぐに思いつく対抗法

コンパイラバイナリを精読してチェックする(ブラックボックスチェック)、あるいはソースコードとの対応が取れているかチェックする(ホワイトボックスチェック)というあたりが、まず思い浮かぶでしょう。それができればそれに越したことはありませんが、たとえばGCCなど、実際に使われているコンパイラはそれなりに大きく、大変な作業です。プログラムでできないか、と考えるかもしれません。いい着目点ではありますが、やはりそのプログラムは信頼できるのか、ということになります。

あるいは、コンパイラではなくインタプリタを使おう、と思うかもしれません。しかし、そのインタプリタコンパイルするコンパイラが、ということになります。問題の場所は移動しますが、必要な作業はそんなに変わらない、ということになります。

ここで、GCCの昔話を

今では多くのUnixライク環境で、バイナリパッケージによるインストールは当たり前のものとなりました。何らかのプログラミング言語の処理系を「野良ビルド」するにあたり、いわゆるセルフホスティングであったり、そうでなくても自分自身のビルドに自分自身が必要であっても、まずバイナリパッケージを使って簡単に必要な環境を作ることができます。

昔は、なんでも野良ビルドが当然であり、わざわざ「野良」などと付けるようになったのもある時代以降ではなかったか、というような記憶があります。そして、難しさの点で大物*5のひとつが「プロプライエタリUNIX環境へのGCCの導入」でした。

普通のやりかたとしては、GCCバイナリを、同じ環境を使っている他のユーザからGNUの助け合いの精神にもとづきコピーしてもらってくれば良いわけですが、全く同じ環境というのもなかなか無かったりするわけで、いわゆる「言語処理系のブートストラップ」の一種のような作業で「最初のGCCバイナリ」を得ることになります。

今でもGCCのビルドの説明には、ステージという表現が使われていますが、この時代には次のような意味がありました。

stage1で得られるのはGCCによるコンパイル結果ではありませんから、バイナリ的にも違ったものなはずです(一種のキメラ的存在と言えるかもしれない)。一方、stage2とstage3は、どちらもGCCによるコンパイル結果ですから、結果は一致するはずです(理論的には一種の「不動点」)。結果が一致しても、必ずしも問題が無いとは言い切れませんが、結果が一致しなければ高い確率で問題が存在するはずです。

ここで注目すべきなのは、このプロセスは「何らかの既存のGCCバイナリ」に依存していない、という点です。これを利用したのが Diverse Double-Compiling による、Trusting Trust 攻撃への対抗だ、ということになります。

図法の導入

伝統的な「T図式」( T diagram )というものもありますが、ここでの議論には少し向いてない面があるので、次のような図法を使います( Fully Countering Trusting Trust through Diverse Double-Compiling の、§4.1 にある図)。

中央の四角がコンパイルプロセスを表現していて、上からの矢印がそのコンパイルに使用するコンパイラバイナリ、左からの矢印がコンパイル対象のソースコード、右からの矢印がコンパイルオプションなどの「ソースコード以外」のコンパイル結果に影響を与える要素(以下では省略します)、下に出ている矢印がコンパイル結果であるバイナリ生成物、という感じになります。

この図法で、前節で話題にした、プロプラUNIX環境へのGCCの導入をあらわすと、次のようになります。

Diverse Double-Compiling

提案手法では、次の図のような手続きで、調査対象のコンパイラの2種類のバイナリを作ります。

右側は、自分自身をコンパイルできる(セルフホスティングな)コンパイラの、通常のコンパイル手続きです。対称性のために2回コンパイルしていますが、原理を示す上では1回でかまいません(2回とも、同じ結果が得られているはずです。説明のため、ここではGCCとします)。

左側は、GCCの導入において「プロプライエタリUNIX付属のcc」であった部分を「何らかの信頼できるコンパイラ」に変えたもの、という感じになります。最初のコンパイラが信頼できるコンパイラですから、stage1のコンパイラソースコードときちんと対応しているはずです。ですからstage2のコンパイラは、(ソースコードGCCだとすれば)最初の「信頼できるコンパイラ」と「GCCソースコード」を信じられる限りにおいて、信じられるはず、ということになります。

そして、この信じられるコンパイラは、右のほうのプロセスで作られたコンパイラと、バイナリ的に一致するはずです。もし一致しなければ、何らかのおかしな仕掛けが仕込まれている可能性がある、ということになります(もちろん、これまで触れてきませんでしたが、コンパイルされた時刻を埋め込む、などといった特異な要因が無ければ*6*7)。

ここで大事なことは、GCCのような大きなCコンパイラバイナリコードをチェックする、というような大変な仕事ではなく、「信頼できて、GCCをとにかくコンパイルできれば良い(コンパイルが遅くても、最適化が全く無くても)コンパイラを用意すること」と「2つのファイルの単なるバイナリ比較」という、(比較すればそれなりに)単純な仕事で、問題点の検出が可能になった、ということです。

相対的な信頼性

またこの手法は、LLVM clangでGCC(ここではコンパイラコレクションの意)のCコンパイラをビルドする、あるいはGCCのCコンパイラLLVM clangをビルドする、といったようなプロセスで、「絶対に信頼できるCコンパイラ」が無くても、ある程度相対的には信頼できると確認できる、ということも示しています。

まとめ

現実的には考えにくいとはいえ、その危険性から脅威と考えられる「Trusting Trust」攻撃に対して、(世界的なセキュリティ界隈では以前から知られていたもののようですが)有効な対抗手段があることを紹介しました。

世界にコンパイラの実装が1種類ではまずく、少なくとも2つ以上、できればもっと多数あるべき、という「多様性の善」を示すものにもなっているように思います。また、セルフホスティングができると、自分の非標準なオレオレ拡張を、自分自身の実装に使いたくなるんじゃないか、という気がしますが、それをやってしまうとこのような検証ができなくなる、ということもわかります*8。あと、極小Cコンパイラとして8ccという実装がありますが( https://github.com/rui314/8ccGCCコンパイルできれば、もしかして「最初の信頼できるコンパイラ」として有用だったりしないでしょうか? (これについては全く私は手を付けてません)

*1:追記1: どうも10年前に、こちら http://www.radiumsoftware.com/0603.html#060329 の最後の段落で、話題自体は読んでいたようです。

*2:BW変換のWであるデイヴィッド・ホイーラーさんとは特に無関係のようです。

*3:講演録では、トンプソンさんが知ったネタ元は、Multicsのセキュリティに関する空軍の文書とありますが、その後確認されたところによれば Karger, P.A., and Schell, R.R. Multics Security Evaluation: Vulnerability Analysis. ESD-TR-74-193, Vol II, June 1974, p 52. という文献だとネットの情報にはあります。

*4:余談ですが、Multicsは高水準言語をOSの記述に使おうとしたという点でも先進的でした(言語はPL/I)。日本でその影響を受けて開発されたHITAC 5020 TSSも、PL/IWというPL/IのサブセットをPL/IWで書いて、人力コンパイルでブートストラップしたと伝えられていますから、この記事とも少々関係があります。

*5:現代と違って、昔はC言語処理系の標準準拠もいろいろ怪しかったりすると、けっこう一筋縄ではなかったりした。

*6:あるいは、近年のセキュリティ技術という観点からは、アドレスを決め打ちするような攻撃に対抗するべくランダム化を掛ける手法がありますが、そういうのとも相性が悪いでしょう。

*7:追記2(参): Debianプロジェクトなどによる、ReproducibleBuilds日本語解説)として、バイナリ再現性の重視について推進するプロジェクトがあります。

*8:追記3: これも http://www.radiumsoftware.com/0603.html#060329 で指摘されているのを、どこかで覚えていたようです。

POSIXとのつきあいかた

コンピュータ関係の技術的なものや技術的でないもの(標準規格とかいったようなものの半分は技術仕様ですが、もう半分は業界政治で出来ていると言えるでしょう)との「つきあいかた」にはいろいろあります。

私のこれまでの経験などから、POSIXとのつきあいかた、といったようなことについて、いくつかの事例を示してみたいと思います。

Bashismとのたたかい

まぁ、Bashismとの戦いという点では、おまえらPOSIXを守ってくれ、と言いたい側ではあります。日常生活しているシェルはbashであるとはいえ、shebang が #! /bin/sh となっているのにFreeBSD/bin/sh (ash系)で盛大にコケるようなものが生態系として定着してしまうのはなんだかんだ言って脅威なわけで、過去にいくつかのプロダクトに向けてチケットを投げたりパッチを書いたこともあります。Bashismではないですがseqコマンドの代替をシェル関数として実装したりだとか。

とは言え、自分自身、FreeBSDの環境で動いてしまうものについては見逃しているだろうことも多く(シェル(シェルスクリプト)の構文では、微妙な所でashではエラーにならないが、bash含め一般にはエラーになる例、というのを引っ掛けていたこともある)、一応それなりにチェックしたい時には、FreeBSDのベースシステムの実装、GNUの実装、Plan9由来の実装(portsにいくつかある)、Heirloom Project(heirloomとは遺産のこと)がメンテしている伝統的Unix由来の実装(これもportsから入れられる)、それぐらいを確認手段にしています。

GNU AWK

と、言ったそばから逆のことを言うようですが、AWKの ** 演算子は非標準として有名ですけども、AWKは言語仕様上、言語処理系側で拡張されてないとなんだかんだで色々なことができませんから、必要であればGNU AWK依存だと割り切って書く、ということも必要でしょう。今の所自分がAWKで書いたプログラムにはありませんが、gawkを使いたくなりそうな点というとまずは多言語対応とかそのあたりでしょうか。

GNU Coding Standards

GNU/Linuxシステムでよく使われているcoreutilsのユーティリティには、POSIXLY_CORRECTという環境変数を設定することによって、(おそらく各ツールの製作者がrationalと考えたものである)通常の挙動から、POSIXにより厳格に従った挙動に挙動を変更するものがあります。

あるいはもっと一般に、GNU Coding Standards ( https://www.gnu.org/prep/standards/standards.html )の中には多くの場所で、POSIXへの言及があります(重複を除いてざっと二十数箇所ぐらい)。これはある意味で「GNUプロジェクトという立場からの『POSIXとのつきあいかた』」と言えるでしょう。

(以下余談。その「POSIX」という名前をsuggestしたのはリチャード・ストールマンさんだ、という話があります*1。また、GNUのコーディング規則は、すごく古いもの http://think-gnu-distribution.appspot.com/html/tga04.html#h.2 も比較して読むと、時代の変遷や「GNUのコアな所」が見えて面白い)

paxコマンド

アーカイブユーティリティのpaxコマンド( http://pubs.opengroup.org/onlinepubs/9699919799/utilities/pax.html )は、POSIXの性格を示すコマンドの一つだと思います。tarとcpioという乱立に乱立を重ねた状態にあったアーカイブユーティリティについて標準化するにあたり、既存のものを標準化するのは諦め、さらにもう一つの(願わくば、混乱の収拾に至る道となってほしい)種を播いた、と言えるでしょうか。その種は、混乱の収拾に向けて、育っていると言えるでしょうか。paxコマンド、使ってますか? ちなみに私は使って(使えて)いません。

dateコマンドのオプションの無さ

標準Cライブラリ(libc)にはいくつかの便利な関数がありますが、それをちょっと使いたい、といった時に、Cのコードを書いて試すのは少々ではありますが、手間です(Cインタプリタ、たとえばCINT*2などを使うことで少しは手間を減らせるかもしれませんが)。

そういった時、類似した機能が使えるコマンド、というのは結構便利です。たとえばちょっとした整数値の十六進表記を確認したい時には、

$ printf '%x\n' 12345
3039

といった感じです。

多機能なlibcの関数のひとつに、strftime( http://pubs.opengroup.org/onlinepubs/9699919799/functions/strftime.html )があります。そして、普通にドキュメントを読んだだけではいったいなんのことやらよくわからない、「 %G と %V 」「 %W と %u 」「 %U と %w 」という、あまりメジャーでないフォーマット文字列があります*3

以前、dateコマンドの機能を使ってあれこれと実例を試して確認したことがあるのですが( http://ksmakoto.hatenadiary.com/entry/2014/10/12/132048 )、実はこのような実験に必要な、任意の時刻を指定してその時刻の文字列表示を得るためのdateコマンドの機能は、POSIXでは全く決められていません( http://pubs.opengroup.org/onlinepubs/9699919799/utilities/date.html を見ればわかる通り -u オプションと、フォーマット文字列を指定する、という引数しか標準にはない)。後から指摘されたのですが、特に何かうまい代替手段も無さそうだったので、記事には注意書きを追加したのみです。

これはPOSIXを追求しなかった例、という話でした。

bcコマンドの曖昧なエラー対処

本題とは無関係ですが、私はMacr055*4というテキストマクロプロセッサを作っています。M4という標準的な(POSIXにもあります http://pubs.opengroup.org/onlinepubs/9699919799/utilities/m4.html )マクロプロセッサではevalという組込みマクロで四則演算などの算術式の計算ができるので、同様の機能を実装したのですが、自分で実装するのは面倒だったので、外部のbcコマンドを利用することにしました。

算術式の計算は、ベンチマークに利用するのに便利ですから、あまり重いのも嫌です。そんなわけでbcには、標準入力から入力を得て逐次その結果を標準出力に吐くモードがありますから、それを利用しました。

処理対象が数式なのですから、ゼロ除算のような意味的エラーは別としても、構文エラーに対してはエラーを検出したいものです。そして、bcがそのようなエラーを検出した時、そのメッセージが標準出力に出力されるのか、標準エラー出力に出力されるのか、実装によってまちまちになっています。手元で確認したところでは、FreeBSDのベースシステムに入っているbcはstdoutに、GNU bc( https://www.gnu.org/software/bc/ )はstderrに吐いてきます。

これは困った、ということでPOSIXで確認( http://pubs.opengroup.org/onlinepubs/9699919799/utilities/bc.html )したところ、この点に関して明示が意図的に存在しないような(としか思えない)書き方になっている、ということを見つけました。

上から順番に関係しそうなものを見てゆきます。まず STDOUT の節には、「正常の場合の出力」のことのみが書いてあります。次の STDERR の節では「shall be used only for diagnostic messages」とあります。ここで「diagnostic messages」とあるのは何か、ということになりそうです。

その後は、bcが処理できる言語の仕様が書かれた EXTENDED DESCRIPTION の節が長く続いた後、最後にわずかにエラーに触れた記述があります。

CONSEQUENCES OF ERRORS の節の1つ目の段落で、引数で指定された名前のファイルにアクセスできなければ「diagnostic message」をstderrに吐け、とあるので、前述の STDERR の節で出力されるとされているのは、こちらのエラーのみということになりそうです。

次の段落の記述が問題の、入力中のエラーについて触れている所ですが、「インタラクティブな起動中は should print an error message」とのみあります。それをstderrに吐くべきかstdoutに吐くべきか、を示すような情報はどこにもありませんし、「should」ですから、絶対にそうしなければならないわけではない、ということでもあります。また EXIT STATUS についても、0 になるのは「All input files were processed successfully.」とあって、標準入力からの入力についてはやはりボカしているような感じがあります。

unexpandコマンドに-tオプションを付けると-aを付けたような挙動が強制抱き合わせになる変な仕様

タブは行頭にだけ使い、expandコマンドとunexpandコマンドで展開したり戻したりすれば、タブ幅の変換は普通はちゃんとできるはずです...が、実際には4タブだと解釈してハードタブ化しようと unexpand -t 4 とすると、なぜか -a オプションを付けていなくても、付けられているかのように動作しろ、と POSIX にはあります( http://pubs.opengroup.org/onlinepubs/9699919799/utilities/unexpand.html )。POSIX内で回避する手段は無さそうだったので、GNU版を使って非標準のオプション --first-only で回避しました(この項、思い出したので追記)。

まとめ

そういったわけで、他には、カーネルとのAPIに関してはLKML周辺の人々をウォッチしていれば、やはり時々、「POSIXとのつきあいかた」が見られるような話題を見ることができるでしょう。POSIXは、明確な参照実装が存在したりするような「仕様」とは、違うタイプの「標準」ではないか、と私は捉えています、というのが本稿の結論めいたもの、となるでしょうか。日本語と英語がうまく対応しないのですが、「標準」「規格」「仕様」、「standard」「specification」、それぞれ微妙にニュアンスが違いますし、現実に存在しているものは、たとえば似たように「標準」と銘打っていても、それぞれ違った位置づけだったりするものです。

numo-lapack というブロジェクトを作りました(始めました)

numo-lapack というブロジェクトを作りました(始めました)。

Numo::Linalg( https://github.com/ruby-numo/linalg )からのフォークをベースに、column-major ←→ row-major 相互の変換をライブラリ側では行わないなど、LAPACKを直接使うのに近い方向性で、早い時期に、多くのLAPACKの関数を利用できる、動く実装を完成させることを目標とする予定です。
現状で、名前等の変更の他、linalgに実装されていた既存メソッドについて新方針で再実装したコードがありますが完全にドラフト版ですので、もし試す方は注意してください(LAPACKの、入力を壊すような関数を使っている場合は、入力のNArrayが壊れる、など)。それと、もしかしたらlinalgと同時にrequireするとどこかが壊れるかもしれません。

2016年11月21日追記

Ruby Associationのほうからアナウンスが出ましたので追記ですが、

こちらのアナウンスにありますように、当プロジェクトは「2016年度Ruby Association開発助成」に応募し、採択されました。約半年弱ですが、ご期待に応える結果を目指します。岸本へのコンタクトは各種可能ですが、多分最も反応が早いのは、SciRuby-JP の Slack からのメッセージになると思います。

同名だが(違う場所にあって)異なるダイナミックリンク(共有)ライブラリの問題(適切な解決法を求む)

FreeBSDにおいて、プログラムの起動時に次のようなエラーで起動に失敗することがあります。

/lib/libgcc_s.so.1: version GCC_4.6.0 required by /usr/local/lib/gcc48/libgfortran.so.3 not found

GCCgcc-4.8 を使っている場合)

原因は、libgcc_s.so.1 として /usr/local/lib/gcc48/libgfortran.so.3 が本来期待している /usr/local/lib/gcc48/libgcc_s.so.1 ではなく、/lib/libgcc_s.so.1 をロードしてしまっていることにあります。

実行ファイルが libgfortran のみに依存していれば、libgfortran.so.3 に埋め込まれている依存性によって正しいライブラリが読み込まれます。

(参考)

$ ldd /usr/local/lib/gcc48/libgfortran.so.3
/usr/local/lib/gcc48/libgfortran.so.3:
	libquadmath.so.0 => /usr/local/lib/gcc48/libquadmath.so.0 (0x801717000)
	libm.so.5 => /lib/libm.so.5 (0x801952000)
	libgcc_s.so.1 => /usr/local/lib/gcc48/libgcc_s.so.1 (0x801b7b000)
	libc.so.7 => /lib/libc.so.7 (0x800821000)

しかし、実行ファイル自身が libgcc_s に依存している場合、通常の libgcc_s は /lib/libgcc_s.so.1 ですから、そちらへの依存が優先されてしまい、前述のようなエラーになります。以下のようにして再現できました。

$ cat sample.c
#include <stdio.h>

extern void *__deregister_frame;
extern void *_gfortran_matmul_l4;

int
main(void)
{
  printf("%p\n", __deregister_frame);
  printf("%p\n", _gfortran_matmul_l4);

  return 0;
}

$ cc sample.c -L/usr/local/lib/gcc48 -lgfortran

$ ldd ./a.out
./a.out:
	libgfortran.so.3 => /usr/local/lib/gcc48/libgfortran.so.3 (0x80081f000)
	libgcc_s.so.1 => /lib/libgcc_s.so.1 (0x800b36000)
	libc.so.7 => /lib/libc.so.7 (0x800d44000)
	libquadmath.so.0 => /usr/local/lib/gcc48/libquadmath.so.0 (0x8010f0000)
	libm.so.5 => /lib/libm.so.5 (0x80132b000)

$ ./a.out
/lib/libgcc_s.so.1: version GCC_4.6.0 required by /usr/local/lib/gcc48/libgfortran.so.3 not found

一応は「混ぜるな危険」ということであるわけですが(ワークアラウンドとしては LD_LIBRARY_PATH=/usr/local/lib/gcc48 を付ければ一応は動く)、

しかし、可能であれば、それぞれの場所にあるライブラリが別々にロードされるようにすべきかと思います。が、可能でしょうか?

「ISLISPを使うべきでないたった1つの理由」に関して

「ISLISPを使うべきでないたった1つの理由」( http://d.hatena.ne.jp/Isuzu_T/20130623/1372003378 )が誤解している点について、簡単にまとめておこうと思います。

要点

上記はてなダイアリーから引用しますが、

マクロは,実行準備時に展開される,いかなる実行時情報も使えない.

仕様にあるこの一文が悲しみです.「実行時情報」が使えないということは,つまり,自分で定義した関数によるマクロの展開は行えない,ということです.なぜなら,関数が定義されるのは,実行時だからです.

ひとつめの引用の、規格票中の文は意訳などではなく、原文(英語)の仕様にもきっちり対応する文がありますので翻訳の問題などではありませんが、もしこのような誤解が多いようであれば削ったほうが良いような気もします。「実行準備」については仕様がある表現ですが、「実行時情報」(runtime information)という表現は仕様の中でここ以外には出てきません。

ユーザーが定義した関数をマクロの定義中で使うことの、このような視点(実行準備と実行)から見た可否については、類推っぽくなりますが、マクロの定義とその使用の関係から考えることができるでしょう。

マクロの展開は全て実行準備時に行われるわけですが、最上位のdefmacro形式によるマクロの定義は実行準備(時)ではなく、実行されて定義されるわけです。ですから、別の箇所でそのマクロが使用されて「実行準備時に展開され」る時に、そのマクロはそれ以前に「defmacro形式が実行されて、定義されたもの」ということになります。

同様にして、マクロの展開関数中で、それ以前にdefun形式により定義されている関数を使用することも問題ないと考えることができるでしょう。以下はこの話題に関するぐだぐだした話です。

その他

規格票中の最初の文と似たような表現が、PCL(『実践 Common Lisp』)中にあります。同書の §8.2 「マクロ展開時 vs. 実行時」に、

 マクロ展開時に動作するコードは実行時とはまったく異なる環境で動作するので、両者の違いを常にしっかりと区別することが大切だ。これはつまり、マクロ展開時は実行時に存在するデータにはアクセスできないってことでもある。(後略)

参考のため原文も見ておくと、

It's important to keep this distinction firmly in mind because code running at macro expansion time runs in a very different environment than code running at runtime. Namely, at macro expansion time, there's no way to access the data that will exist at runtime. (後略)

http://www.gigamonkeys.com/book/macros-defining-your-own.html

ここで言っている「実行時」というのは、そのコード片(式)を含んでいる関数が実引数に適用され評価される時、という意味であって、「実行時に存在するデータ」(the data that will exist at runtime)というのは、式中にあらわれる仮引数の値、といったようなものを指しており、Lispプログラマの常識的にいってごくあたりまえのことを言っているに過ぎません。

なぜほぼ同様の表現なのに、ISLISPの規格票の解釈では、前述のような誤解をもたらしたか、ということを考えるに、おそらくISLISPのミニマリズムに起因する実行モデルの不在ではないかと思います。以下で説明します。

JISの規格票では §1.1 の「適用範囲」の b) 適用外事項 の 3) に

ISLISPテキストを実行準備する方法,及び実行のために準備されたISLISPテキストを起動する方法。

とあり、実行準備→実行というフェーズがどう(いかにして)進行するのか、という点の詳述が範囲外となっています。

そのため、それについての記述は、§1.3 の「オブジェクトは、実行のために準備される (prepared for execution) 。」から始まる段落で述べられている以外には、まとまって存在していませんが、これが原因ではないでしょうか。

ここで、冒頭が「オブジェクトは、」となっていることに注意が必要かと思います。これがもし「ISLISPテキストは、」となっていたら、プログラム全体がまずいっぺんに実行準備され、そして実行される、という意味になるでしょう(つまり、冒頭で引用したような、マクロ中でユーザーが定義した関数が使えない、と考えてしまうことにつながります)。しかし、「オブジェクトは、」となっていますから、ISLISPの「テキスト」(§1.7.37を参照)を構成する個々の「最上位形式」(§1.7.38を参照)について述べているのであって、「最上位形式の並び」は(仕様上は)オブジェクトにはなりませんから、「プログラム全体がまずいっぺんに実行準備され」という解釈は妥当ではない、ということになります。

そういうわけで、仕様では(それぞれの最上位形式に対応する)オブジェクトについて「実行準備され、実行される」ということのみが述べられているということは確認できたとしてよいと思いますが、最後にもう少し、マクロについて考えます。

規格票中の 8. マクロ には、その順序として「マクロは,実行準備の段階で,それを使用する前に定義しなければならない。」とありますが、もしこれに加えるなら、「展開関数中で使用する関数も、そのマクロを使用する前に定義しなければならない。」ということになるかと思います。(あるいはコンパイルの都合を考えると、マクロ定義より前に定義を必須としたほうが良い?)

crubyのFloatにFast inverse square rootを(モンキーパッチで)追加する話

Fast inverse square root自体については「30のプログラミング言語でFast inverse square rootを実装してみました!」( http://itchyny.hatenablog.com/entry/2016/07/25/100000 )を参照してください。

せっかくの高速な手法ですから、高速な実装を考えてみます。Rubyの場合、まっとうに実装するのであれば Math モジュールに追加するべきですが、性能のことを考えると関与するオブジェクトが少ないほうが良いですから、Float クラスにモンキーパッチで追加することにしました。

こんな感じになります。

#include <stdint.h>
#include <float.h>
#include "ruby.h"

static VALUE
fast_inv_sqrt(VALUE v)
{
  double d = RFLOAT_VALUE(v);
  if ((d > 0.0) && (d <= DBL_MAX)) {
    //NOP
  } else {
    rb_raise(rb_eFloatDomainError, "out of domain");
  }
  union u_di {
    double d;
    uint64_t i;
  } d_i;
  d_i.d = d;
  d_i.i = 0x5fe6eb50c7b537a8ULL - (d_i.i >> 1);
  double d2 = d / 2.0;
  double g = d_i.d;
  d_i.d = g * (1.5 - d2*g*g);
#if 0
  d_i.i += 0x4e1c39a47a8ULL;
  g = d_i.d;
  d_i.d = g * (1.5 - d2*g*g);
  d_i.i += 0x14b9e8a78ULL;
#endif
  g = d_i.d;
  return DBL2NUM(g);
}

void
Init_fisqrt(void)
{
  rb_define_method(rb_cFloat, "fast_inv_sqrt", fast_inv_sqrt, 0);
}

ポイントとなる点をいくつか説明してゆきます。

まず Init_fisqrt が拡張ライブラリのエントリポイントで、これは見たままかと思います。

関数 fast_inv_sqrt が本体で、最初と最後にある VALUE と double の相互変換は拡張ライブラリの書き方の定番通りです。

続いて引数の範囲チェックですが、浮動小数点数のチェックは「真になる条件」でチェックするのがセオリーです(比較に NaN が関わるると偽になるため)。

ビットパターンを保存した浮動小数点数と整数の変換に union を使っているのも、この手のトリックの定番と言っていいでしょう(標準において、未定義ではなく処理系定義のため、気休め程度だがマシ)。

単精度の時の 0x5f3759df に相当するマジックナンバーは、妥当と思われる方法で私が探索(詳細は略)したものです。

#if 0 でコメントアウトしてある部分は、せっかくなので高精度化を図ってみたコードですが、これがあると **(-0.5) で正確な値を計算するよりも遅くなってしまったのでコメントアウトしました。単にニュートン法をもう1回繰返すだけではなく、誤差で必ず負の側に予測可能な範囲でズレることがわかっているので、それを調整する加算も入れてあります。

続いてベンチマークに使ったスクリプトを示します。

#! /usr/local/bin/ruby23

require 'benchmark'

require_relative 'fisqrt'

a = 1.0

result = Benchmark.realtime {
  (0..10000000).each {|i|
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
    a.fast_inv_sqrt
  }
}
print "result: #{result}s\n"

result = Benchmark.realtime {
  (0..10000000).each {|i|
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
    a**(-0.5)
  }
}
print "result: #{result}s\n"

result = Benchmark.realtime {
  (0..10000000).each {|i|
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
    1.0 / Math.sqrt(a)
  }
}
print "result: #{result}s\n"

次のようになります。わずかですが速いという結果が出ています。

result: 6.402902246918529s
result: 7.31780265388079s
result: 9.100973834982142s

4004のブートストラップキャパシタ

この記事で言及する「ブートストラップ」は、電気(電子)回路の技法のそれであり、コンピュータの電源投入時やリセット時などの起動シーケンスのことではありません。

(回路技法の)ブートストラップとは

既にご存じの方は飛ばしてください。

以下の2つの回路図は、『定本 トランジスタ回路の設計』(ISBN:9784789830485)の、第8章の 図2 と 図21 ですが、


赤い線で囲んだ部分に注目すると、1つめの回路ではグランド(0V)が基準となって動作する部分が、2つめの回路では自分自身の動作によって電位が決まる部分が基準になって動作するようになっています。

このように「自分自身の動作を利用して、動作電位が決まるような、電気(電子)回路の技法」は「ブートストラップ」と呼ばれています。語源はコンピュータの起動時の動作を指すそれとほぼ同じと思われますが、コンピュータのほうはプログラム内蔵方式のコンピュータができた戦後の頃にできた言葉であるのがほぼ確実であるのに対し、こちらはどうも戦時中(真空管回路)に、おそらくレーダーの研究開発などといったような秘密の下で考案されたものではないだろうかと思うのですが、由来を先日ざっと追ってみたものの、よくわかりませんでした。*1

最初に示した例はカスコード(cascode)方式の増幅回路のベース-エミッタ間の電位差を一定にするものでしたが、他に、ブートストラップの技法が使われる例としては、スイッチング電源のハイサイドがあります。

パワーMOSFETを電源などドライバ回路に使う場合、グランド側はNチャネルMOSFETを使えば、ゲート電圧が Vdd に近ければオン、グランド(Vss)に近ければオフ、という動作になるのでそれで良いわけですが、ハイサイド(電源側、Vdd 側)をそれと対称に構成しようとすると、PチャネルMOSFETが必要になります。しかし、Pチャネルは良い特性があまり得られず、品種も少ないですから、ハイサイドもNチャネルMOSFETで構成するわけですが、そうするとそのFETのソースの電位が Vdd に近くなっても十分に駆動するには、ゲートを駆動する電圧について Vdd + 2V~3V 程度のゲタを履かせる必要があります。

MOSFET のゲートですから、電流(電力)はたいして必要ないので、簡単なDCDCコンバータで電圧を作ったりするわけですが(『定本 続 トランジスタ回路の設計』の第10章に例があります)、スイッチング電源の場合は常に矩形波でパタパタしている電力を扱うわけですから、それをうまくキャパシタで利用してやる方法があります。

電源用モジュールの製品などで、外付け部品としてキャパシタが必要なものがありますが(ロームによるスイッチングレギュレータの解説 http://micro.rohm.com/jp/techweb/knowledge/dcdc/dcdc_sr/dcdc_sr01/829 や、TIによる降圧型スイッチングDCDCコンバータの解説 http://www.tij.co.jp/analog/jp/docs/analogsplash.tsp?contentId=54765 を参照)、そのキャパシタは「0V <=> Vdd」の矩形波を利用して「Vdd <=> Vdd+α」というような電圧を作ってやるのに使われているわけです。

1970年代のMOSプロセス

21世紀の現代ではもっぱらCMOSが使われているわけですが、1970年代~1980年代、なじみのある製品でいうと電卓戦争の時代から8~16ビットマイクロプロセッサの時代は、初期のメタル1層から2層へ、ロジックも PMOS → NMOS → CMOS と変遷があり、表向きにはスペックの向上として現れていますが、その裏にはいくつかのプロセスにおける変革があります(嶋さんによるこちらのコラム http://itpro.nikkeibp.co.jp/article/Watcher/20060323/233069/ が具体例に詳しい証言になっている)。

インテル4004(以下、ICの名前は単に4004等と呼ぶ)では、まだPMOSの時代で、しかもイオン注入によって部分的にディプリーション(ノーマリーオン)のMOSFETを作ることができるようになったのはもっと後であり(前述の嶋さんのコラムを参照。8080でもNMOSになっただけであり、イオン注入はZ80で採用された)*2、ブートストラップ方式によるちょっとしたトリックのような回路が使われています。

4004のブートストラップキャパシタ

4004では負電源とPMOSだったわけですが、それでは慣れない我々には少々非直感的なので、以下では正電源・NMOSで考えることにします。

相補型(CMOS)でないMOSで一般的な論理方式は ratioed logic と呼ばれるもので、NMOSの場合はハイサイドに小さめのトランジスタを置いて、プルアップする能動負荷とし、反対側に大きめのトランジスタでnotやnandやnorといった論理を作るものになります。

こんな感じです。上の能動負荷となっているFETについてですが、ディプリーション型であればゲートはソースかグランドに直結するわけですが、ここではエンハンスメント型ですから Vdd に直結されます。すると、出力が Low の時はロジック側の大きなトランジスタで引き下げられるわけですから問題ないわけですが、出力が High の時のプルアップが問題で、Low の時の電圧が上がりすぎないように小さめのトランジスタで駆動している上に、ゲート-ソース間の電圧として Vth 程度の電圧が必要ですから、Vdd まで出力を引き上げることができない、いわゆるフルスイングでない出力ということになってしまいます。

それでも問題ないように論理を工夫したりする方法もあるわけですが、4004では、以下で説明するようなちょっとトリックっぽいブートストラップの手法で、一時的に電源を越えるような電位を作って問題を回避しています。

4004の回路図は3枚に分かれていますが、そのうちの1枚「4004 ADDRESS REGISTER, INCREMENTER AND INDEX」というタイトルの図の片隅に、次のような注記があります。

ここで重要なのは下の2つで、プルアップ抵抗のように描かれているのは、実際にはMOSFETによる能動負荷だよ、ということを示すものです。上にあるほうは前述のような、単純にゲートをドレインに短絡したFETですが、トリックがあるのは下のFET2個とキャパシタを組み合わせたものです。「B」という記号は「ブートストラップ」の意でしょう。

この信号は時分割のバスなど、常に(矩形波による)オンオフがある信号であることが前提です。4004はレジスタに静的ではない回路を使っているため、動作をハードウェア的に完全に止めてしまうことはできない、完全には静的でない論理回路ですが、(実は)この部分も完全に静的ではなくある程度の動作が常に必要です。

まず、出力が Low で定常的だとする所から始めます。上のFETにより下のFETのゲートは Vdd-Vth 程度の電位になっています。出力は Low で、下のFETのゲート-ソース間電圧は十分にありますから、下のFETもオンになっていますが、前述のように ratioed logic のためにロジック側で出力は Low に引き下げられている、というような状態になっています。キャパシタがあるわけですが、ICの中に作れる程度ですから、定常状態で放置されれば電荷はそう長くは保ちません。

次に、ロジックの入力が変化して、出力が High に変化し始めた、とします。するとキャパシタが、いわゆる「スピードアップコンデンサ」のそれと似たような働きをすることになって、上のFETのソース=下のFETのゲートの電位が、出力電圧の変化に合わせて上がってゆき、2*Vdd-Vth 程度まで上がることになります。これにより下のFETがオンに保たれるため、普通であれば Vdd まで上がらないはずの出力が、Vdd まで上がります。

また、上のFETはゲート電圧よりもソース電圧のほうが高いため、オフ状態になります。

(普通のディスクリートMOSFETで似たような回路を作ろうとした場合、ソース電極がサブストレート(バルク)にも接続されていて寄生ダイオードが存在するため(よく使われる右のような記号はそれを表現したものです)、ソースの電位をドレインより上げても電荷が抜けていってしまいますが、ICの中ではソースとサブストレートを別にすることができます)

以上のようにして、4004ではブートストラップの手法により、動的な一部の信号線の( High への)駆動力が強化されています。

実装

マスクパターンでは、以上で説明したキャパシタが、余計な面積を必要としないように巧妙に形成されているはずです(が、力不足で説明できる所まで理解できていません)。

文献

嶋さんの本、

マイクロコンピュータの誕生―わが青春の4004

マイクロコンピュータの誕生―わが青春の4004

には、この手法に関して直接的な言及はありません。嶋さんは4004チップに関して論理設計だけでなく回路やマスクの作業もやっておられますから、それ自体については承知のはずですが、おそらく、フェデリコ・ファジンさんの功績であることから(自分のそれと混同されることを避けるために)言及しなかったのかもしれません。Z80においてイオン注入法を採用したことで、ディプリーション負荷FETが使えるようになった、という間接的言及といえる記述はあります(イオン注入法がデッドコピー対策のトラップのためにも使われた、という記述も興味深い所です)。

近年出たドキュメンタリー、

インテル 世界で最も重要な会社の産業史

インテル 世界で最も重要な会社の産業史

には、次のような記述があります( p. 183 )。

このなかでいわば「副産物」*3のように生まれた発明が、やがて半導体史上シリコンゲートと並ぶ意義を持つことになった。ファジンは個々のゲートを、相方となるトランジスタの上側にブートストラップしたのだ。それまで不可能と思われていたことである。この手法はすぐに普及し、それから四〇年にわたってほぼすべての種類のチップに利用された。(この段落後略)

というようにあるのですが、ここまでで説明したように4004で使われたブートストラップは、イオン注入法によるディプリーション負荷FETが使えるようになるまでの「つなぎ」的な色の濃い手法であり、CMOSになってからは忘れられたような手法ではないかと思いますので、何か違う感じもします。もしかしたら翻訳の際の影響かもしれませんが、もうひとつの鍵となった技術である buried contact が関係あるかもしれません。

なお同書は、(『電子立国』ではあまり語られなかったため、日本などではあまり知られていない)当時の、また他の多くの時代のインテルの内情が書かれており、「マイクロプロセッサは誰の功績か」などといった話題についても(他社への言及が無い点を除けば)フェアかつ背景に踏み込んだ記述もあり、必読の1冊ではないかと思います。

*1:1955年に出願された特許の中に出てくるのが確認できるのだが、あたりまえの技術として言及されているように見える https://www.google.com/patents/US2850629

*2:4004の回路の素子について、デプレッション型、と言及している記事があるが http://www.atmarkit.co.jp/fsys/zunouhoudan/139zunou/4004_40thanv.html 誤解ではないかと思われる。

*3:原文では傍点