2018-12-13

RustでArm Cortex-Mプログラミングをする 2018

この記事は自作OS Advent Calendar 2018およびRust その2 Advent Calendar 2018の記事です。

ベアメタルプログラミングといえばC言語であったが、C言語でプログラミングするのはつらい、ということでその代わりとなる言語としてRustが注目されてきている。
Rust+Armのベアメタルプログラミングに関しては去年のRustアドベントカレンダーにも記事があったほか、自分も何件かすでにブログを書いているが、今年はRust Embeded Working Groupが発足し、資料も充実してきた（参考：This Year in Embedded Rust）

Rustでベアメタル

Rust Embeddedチームがすでにドキュメントをつくっているので（執筆中の章も存在するが）、これに従えば誰でもCortex-Mのベアメタルプログラミングできる
The Embedded Rust Book
ベースとなっているのはjaparic氏のブログなので、それの正式版と思ってもらえば良い。
チュートリアルはSTM32F3DISCOVERYをハードウェアと用いていて、秋月電子通商などで日本でも2000円程度で手に入る。
以前、QEMUで実行する方法もブログにしたが、タイマーなどの一部ペリフェラルが動かない他、やはりLEDが手元で光っている方が楽しいと思うので、がっつりとやりたいのなら実機の購入をおすすめする
一応、後述する通り他のcortex-mボードを用いても十分に開発できると思われる。現に僕はSTM社製の他のボードを使っている。

cortex-m-quickstart

では実際にArm Cortex-Mでのベアメタルプログラミングの話に入ろうと思うのだが、
ベアメタルプログラミングするための手順だけであればThe Embedded Rust Bookがよくまとまっているので、それを読め、で終了してしまう。

なので今回はThe Embedded Rust Bookでも用いられているcortex-m-quickstartからサンプルコードを抜粋して大体なにをしているかを見ていくことにする。

hello world

example/hello.rsを見てみよう。いわゆるhello worldである。
hprintln関数はセミホスティングを利用した出力を利用している。セミホスティングとはSVC命令などを利用することでデバッガに対してメッセージを送る機能である（参考:https://developer.arm.com/products/software-development-tools/compilers/arm-compiler-5/docs/dui0471/f/semihosting/what-is-semihosting）。
なので、UARTなどを利用したものでないため、本来ならデバッガをボードにつなぐ必要がある。が、DISCOVERYボードは基板にデバッガも内蔵しているので簡単に利用できる。

この#[entry]というアトリビュートがついたものが実質的なmain関数となる。ブートコードはどこにあるか、というとこのcortex-m-quickstartが依存しているライブラリの一つ、cortex-m-rtが担っている。
このライブラリはビルド時のリンカスクリプトの生成もしていて、このアトリビュートをつけた関数を展開し、ブートのための処理を行った後呼び出す、という流れになっている。
大まかな仕組みとしてはライブラリに含まれるlink.x.inというスクリプトをベースにbuild.rsがスタックサイズのチェックや必要に応じて他のライブラリのリンカスクリプトを読み込んだりしている。
その他、例外発生時のハンドラの登録用マクロも用意されている。
詳しい仕組みはドキュメントを参照。

このテンプレートが依存しているもう一つのライブラリであるcortex-mライブラリはアセンブラ命令を呼び出すためのラッパやシステムレジスタの抽象化レイヤなどがふくまれている。
インラインのアセンブラはまだ安定版ではないため、対応していない場合、予めコンパイルしてあるアセンブラを関数をextern Cで呼び出している
その際のArmのバージョンごとの違いはbuild.rsが指定されたターゲットを見てどのバイナリをリンクするかで吸収している。

panic

example/panic.rsはpanicを発生させるだけのコードである。no_std環境でもpanicが発生した際の処理を実装しておかなければならない。
これは最近安定化されたfeatureのひとつでもある。
このサンプルコードではpanicハンドラを実装したクレートを読み込むことで動作を決定している。

allocator

example/allocator.rsは自前で動的メモリ確保を実装することでno_std環境下でも動的配列を利用する例である。
基本的に組込みで動的メモリ確保は行わないほうがいいのだが、どうしても必要というケースは出てくる。
これも最近安定化されたfeatureのひとつでもある。
外部クレートで実装されたallocであるが、中身は空き領域をリスト形式で持っておき、要求に応じて空き領域リストを探索して返す、というシンプルなものになっている。
ただし、stdに含まれるvecは使えないので、allocクレート内のvecを使ってあげる必要がある。こちらはまだunstableなfeature。 allocクレートの中にはBoxやArcなど、所有権周りの問題を解決するのにおなじみの構造体も含まれている。

device

マイコンのペリフェラルを使う例。stm32f103xxというクレートを使っているが、これはチップのMMIOのマッピングを記述したSVDファイルからsvd2rustを使って自動生成されたものである。
そのため、他のタイプのボードを使ってもSVDファイルさえ手に入れれば割と簡単に再現できる。
svd2rustはペリフェラルからの割り込みハンドラをリンクするためのcortex-m-rt用のリンカスクリプトもつくっている。
これはsvd2rustの生成したライブラリがCARGO_FEATURE_DEVICEというフラグをオンにすることで、device.xをcortex-m-rtが持つリンカスクリプトをインクルードさせている。

その他の資料

Armではないが、RISC-V向けの記事が今年の自作OS Advent Calendarに上がってる
RustでRISC-V OS自作！はじめの一歩

また、以前も紹介したが、別のアプローチとしてTockという組込みOSが存在しており、そちらのデザインはなかなか工夫されている。
Tock
ただし、こちらは専用ボード向けの実装しかないため、始めるにはハードルが高かったため、自分はまだ手が出ていない。

また、Cortex-Mではないが、Rasberry Pi 3でのチュートリアルも提供されている
Bare Metal Rust Programming on Raspberry Pi 3

2018-10-31

SECCON 2018 参戦記

SECCON 2018予選にnegainoidoで参加して、ReversingのSepecial Device FileとSpecial Instructionsを解きました。

Special Instructions

バイナリファイルが与えられ、それを実行してフラグを得る。いろいろなアーキテクチャのクロスコンパイラも与えられる。
とりあえず、そのツールチェーンをビルドしつつ、バイナリを眺める。fileコマンドではアーキテクチャを特定できなかったが、stringsコマンドを使うと、

This program uses special instructions.
SETRSEED: (Opcode:0x16)
    RegA -> SEED
GETRAND: (Opcode:0x17)
    xorshift32(SEED) -> SEED
    SEED -> RegA
GCC: (GNU) 4.9.4
moxie-elf.c

というのが見えるので、moxieというアーキテクチャだということがわかる。
ツールチェーンにはエミュレータも含まれているが、stringsの結果にもあるとおり、xorshift専用の命令が組み込まれている。
xorshiftのアルゴリズムについてはwikipedia参照。xorとshiftによって簡単かつそこそこ質のよい乱数が生成できるらしい。
この専用命令を関数としてどこかにねじ込み、命令をその関数の呼び出しに書き換えるという戦略も考えられるが、今回はやっていることがバイナリ内のロジックが比較的シンプルなので、
それを適当なプログラミング言語に再実装して手元で走らせるのが楽。
moxieのアーキテクチャマニュアルはその時は見つけられなかったが、割と素直な構成なので、ある程度他のアセンブラを触った人ならなんなく読めるはず。
やっていることは、初めになんやかんやputsで文字列を出した後、decode関数で暗号化されたflagをデコードし、それをputsしている。
デコードの仕組みは暗号化された文字に対して、更に別のrandvalという埋め込まれている定数とxorshiftによって生まれる乱数とのxorをとっているだけ。

乱数の初期シードをコピペミスするとかして無駄に時間を浪費してしまったが、なんとか提出できた

Special Device File

今度はaarch64のバイナリが与えられる。今度は/dev/xorshift64というデバイスを叩いているためそのままでは実行できない。
xorshift64は名前から察するにxorshiftで乱数を生成しているだけであろうと予想できる。

ARMv7-Aのアセンブラは読み書きしたことがあるが、aarch64ははじめてだったので、少々戸惑ってしまったが、
ちょっと公式ドキュメントを読めば理解できた。64bitアーキテクチャのため、馴染みのない命令がそこそこあったが、
Arm公式で提供しているドキュメントがそこそこ親切なので調べれば大丈夫。
やっていることはSpecial Instructionと大差ない。xorshift64の初期シードを探すのに多少手間取ったが、よく見ると初めにスタックに64bitの定数を積んで、スタックポインタをwrite関数に渡していたのに気がつき、それがシードだった。

取り組んだが解けなかった問題

Needle in a haystack

恒例(?)の動画問題。題名から察するにどこか数フレームにフラグがあるのかなあ、とチームメイトがいろいろ試行錯誤。
自分もいろいろアイデアを出したが、結局何も掴めず。

結論はビルの一室のあかりがモールス信号になっていたらしい。まあ、この問題は解けなくても仕方ないかなあという気分。

GhostKingdom

唯一のWeb問題。ウェブサービスが与えられていて、/FLAG以下のアドレスのどこかにフラグがあるらしい。
そのウェブサービスでできることは

ユーザーの登録とログイン
メッセージの送信フォーム
URLを与えて、そのページのスクリーンショットの取得

メッセージの送信フォームにはプレビュー機能があって、そこにcssという名前の怪しいパラメータがあった。
適当な値を入れると、プレビュー部分のstyleタグに壊れた文字が入っていたので、何らかの形式でエンコードされたcssであろうと考え、base64を試したら見事正解。

他にはスクリーンショットの取得部分で、自分で適当なページをつくって、その中でlocalhostにリダイレクトさせることで、ページにlocalhostとしてアクセスすることで画像アップロード機能を使える、というところまでは掴んだ。
ログインはiframe内でログイン用のURLを叩かせた。

しかし、それ以上をつかむことができず終了。
答えとしてはCSS injectionとして知られている技法でフォームの値を抜き出し、セッションIDを取得すること、
その後、画像アップローダーで使われているImageMagicの脆弱性をつくことだったらしい。
参考：http://hakatashi.hatenadiary.com/entry/2018/10/28/211034

CSS injectionのことを知らなかったほか、セッションIDがcsrfトークンとしてフォームに埋め込まれていたことに気がつけなかった。
たとえそれらに気がついたとして、ImageMagicの脆弱性までたどり着けるかどうかも怪しい。
任意CSSを埋め込めることに気がつけた時点で、もっとCSSを利用したテクニックについて調べていればよかった。
常日頃CTFをやっている人間でないのでその場で知識を調達してこなければならないのが厳しい。

2018-09-26

ISUCON8 予選延長戦

ISUCON8予選はみごと惨敗に終わったのだが、運営とスポンサーのご厚意により一週間予選のサーバーへのアクセスが開放されたので、予選時のトラブルの検証とどうすれば今年の予選を突破できたのかをいろいろ追加実装して試してみた。

トラブルの原因

前回の記事で終了間際、初期実装に戻してもfailし続ける謎の現象に見舞われたことについて。
結論は、IPアドレスが書き換わっていた、というのが一番近い答えでした。
ISUCONの予選用のページにチームが使えるサーバーとそのIPアドレス一覧のページがあり、そのページでどのサーバーに対してベンチマークを走らせられるかも選べます。
我々はこのリストの一番上からisucon1,isucon2,isucon3と名前をつけて、ssh_configに設定をしておきました。
しかしなんと終了1時間前あたりにそのリストの順番がアナウンスなしに入れ替わっていたのです。
今回はisucon3を対象にベンチを走らせているつもりだったのですが、その入れ替わりの過程でisucon3が一番上に来ていたの気が付かず、実はisucon1を選んでいたのでした。
ただ、こんなのはアクセスログを見れば一発でわかったことなので、焦りは禁物ですね。

また、たまにfailする問題ですが、なんと初期実装にバグがあり、高負荷時に予約時間等の整合性がとれなくなることがありました。
具体的にはデータベースを叩くときにトランザクションをつくる前にクエリを発行して予約対象の座席を決定している部分です。
さらに、他のエンドポイントもトランザクションをつくらずに複数のクエリを発行しているため、書き込み処理がそのクエリ群にはなくても、他のエンドポイントからの処理を並列で実行していた場合にデータベースの内容が書き換わり、APIのレスポンスの内容がおかしくなりfailするパターンもあるようでした。
具体的に満たすべき仕様が与えられないコンテストで、高負荷時にはじめて発現するとはいえ、初期実装にバグがあるっていうのはいかがなものなのか…とは個人的には思うのですが、こういうこともあると今後は気を配ったほうが良さそうです。

予選通過のための戦略

今年のエントリまとめから予選通過したチームの戦略を読み解きたいと思います。

戦略その１: データベースの情報をすべてメモリ上に落とす

今回の問題の初期実装はとにかくデータベースのアクセスの仕方が非効率な部分が多く、これらを解決しなければなりません。
そこで、データベースアクセスをそもそもやめて、すべてメモリ上で操作すれば処理を格段に減らせるという戦略が考えられます。
参考: ISUCON8予選参加記 - math314のブログ

こちらの戦略、予選後の開放期間でためされた方もいて、なんと50万点を叩き出したようです（予選期間中での最高得点は9万点代）。
しかし、この戦略はデータベースアクセス全てを書き換えるため実装量がとても厳しいことになり、整合性をとるのが非常に難しい戦略でもあります。
また、サーバーは1台しか使えないことになります。
さらに、アプリケーションを終了させた後の整合性も検査対象のため、データベースへの書き込みも行わないと失格になります。
確かに、今回は非常に効果のある戦略だったようですが、実装力がないチームがうかつに手を出すと破滅しかねない危険な戦略です。

戦略その２；とにかく地道にクエリを改善し、3台フル活用する

初期実装には大量のN+1クエリが存在しているため、これらを地道に潰し、3台の与えられたサーバーに適切に役割を与える、でも十分に得点は叩き出せます。
多くのチームはこちらの戦略をとっていたようです。

特に、イベント情報取得の際のreservationsテーブルの叩き方は非常に非効率なので、ここをどう改善するのかが1つの鍵だったようです。また、予約時のreservationsテーブルへの書き込みも、ロックを取得するため、効率化が必要となります。

具体的には

N+1になっている箇所はJOINなどで潰す
sheetsテーブルは不変なので、初期化時にメモリに展開しておく
reservationsテーブルに適切なindexをつくる
- event\idとcanceled_atに対してなど
予約時にランダムに席をとってくる際のSQLでのORDER BY RAND()をやめて言語実装のランダムでおこなう
- ランダムに返す事自体は要求仕様なので変えてはいけない

また、複数台の活用ですが、初期実装の状態では1つのAPIリクエストに対して複数回データベースクエリを投げるため、そのオーバーヘッドが大きいためデータベースとウェブサーバーを別にした瞬間、タイムアウトで落ちるようになります。
しかし、データベースサーバーのCPUリソースはかなりかつかつの状態なので、データベースアクセスの最適化がある程度行われたのち、複数台の実装にすることでスコアが伸びることが期待されます。
特に/admin以下にあるCSVを出力するエンドポイントはCPUを大きく消費するため、複数台化は必須となったでしょう。

今回の罠

延長戦の中で気がついた罠についていくつか紹介したいと思います

初期実装のSQLクエリ

戦術の通り、トランザクションをつくるタイミングがおかしい、そもそもトランザクションをつくっていない、などの罠もありましたが、他にも初期実装にはバグではないが不要な文がいくつかありました。

HAVING節

初期実装に

1	SELECT * FROM reservations WHERE event_id = ? AND sheet_id = ? AND canceled_at IS NULL GROUP BY event_id, sheet_id HAVING reserved_at = MIN(reserved_at)

という部分がありました。
気持ちとしては同じsheet_idに対して複数のキャンセルされていない予約があった場合、reserved_atが最も小さいものを有効な予約とみなす、としたかったのでしょうが、このクエリは正しくありません。
なぜかというと、HAVING節はGROUPED BYされた後のエントリに対してフィルターをかけるものであり、その集約前のデータに対して、あるいは集約の仕方を指定するものではないからです。
MariaDBの公式ドキュメントにも

1	To filter grouped rows based on aggregate values, use the HAVING clause

とあります。
では、複数の予約があった場合はどうなるか。
その際ような際の仕様は不定で、今回のMariaDBで実験したところ、そのカラムはそもそも集約されず無視されていました。
標準のSQLではそもそもGROUP BYで指定していないカラムに関してはSELECT節で引っ張ってこれません。しかし、MySQLではその仕様が拡張され、そのようなカラムの場合、集約されたエントリ全てにおいて、そのカラムは同一であるならば、その同一の値が入ります。しかし、同一でない場合の値は未定義です。
参考: https://dev.mysql.com/doc/refman/5.6/ja/group-by-handling.html

そもそも、予約時のトランザクションの作り方が正しければ、同じsheet_idとevent_idに複数の予約が入ることはありません（トランザクションをつくる前のSELECT文で予約のない席を探しているため）。
なので、このHAVING節は完全にいらないものです。

FOR UPDATE

いろいろなところで使われていたFOR UPDATE文ですが、きちんと検証はしていないですが、これらは全く無意味だったと思われます。

MariaDBの公式ドキュメントを見てみましょう。
このFOR UPDATEがあると、次のデータベースの書き込みが発生するまで、他のトランザクションからの書き込みやロックの取得を防ぐことができます。
しかし、ドキュメントにあるように、この節はautocommitがオフになっている場合またはトランザクション外でないと効果がありません。
autocommitはデフォルトでは有効で、サーバーの元々のmy.cnfでは特に指定していないので、autocommitが有効だったようです。
そもそも、autocommitが無効だったとしたら、FOR UPDATEしたあとにデータベースをUPDATEやINSERTがないとCOMMITを実行しない限りロックを取得したままになるのですが、今回、COMMITをしていない箇所が結構ありました。

大量の外部からのアクセス

予選中でもあったのですが、外部からの攻撃が確認できました。これはそれなりにネットワークのリソースを食っていたようなので、場合によってはそれなりにパフォーマンスが低下していた可能性があります。
具体的には、アクセスログを見たところ、phpadminなどの怪しげなアクセスが記録されていたこと、journalctl -xeでsshでの認証失敗がたくさんあったことです。
今回のsshdの設定はパスワードログインを許可していたため、このような攻撃があったのでは、と思います。
denyhostsの導入や、アクセスログを見て一部IPアドレスをファイアウォールで弾くなどの設定が必要だったと思われます。

h2oプロキシが502 Gatewayエラーを返す

これはちゃんと検証できなかったのですが、h2oで80番ポートから8080番ポートへのプロキシで502が帰ってくることがあり、502を返してしまうとベンチマークがfailする、という問題が確認できました。
8080を直接叩くと問題は起きず、同じ内容のリクエストを投げても502が帰ってくる場合とそうでない場合もあり、原因はよくわかりませんでした。
予選中はそのような問題は起きませんでしたが、アクセスログに関する設定を外した他のサーバーでなぜか頻発しました。
エラーログのデフォルト設定では特に原因がつかめず、何が悪かったかはわかりませんでした。
他のチームは早々にnginxに切り替えていたので、延長戦では僕もnginxに切り替えて深くは原因追求しませんでした。

まとめ

来年はもうちょっと環境整備をしたうえで、SQLを早く最適化できるようになりたいですね

2018-09-17

ISUCON2018予選敗戦記

isucon2018予選、一日目にガラスボッチとして参加して見事惨敗しました。大会の感想と来年に向けての準備について書いていきたいと思います。
懺悔の用意はできてるか

事前準備

もともとはボッチ参戦予定でしたが、なんだかんだでなり（@iwa_tatsu）くんと一緒に出場しました。ガラスボッチだがボッチではない。
僕自身は初参加で、なりは去年のISUCONにも出ていたので、去年の問題とそのときにやったこと、上位陣のブログ記事などを参考に勉強会をやって役に立ちそうなことはprivate wikiにまとめておくなどしておきました。

去年のエントリまとめ

去年の予選は複数台構成で、3台のマシンにどうロードバランシングしていくのかが1つのキーだったらしいので、今年も複数台構成であろうということで、そのへんを意識しながら資料を漁っていました。
今年の環境はsshでCentOSの環境にアクセスしてやるということは事前に公開されていたので、僕の方でansibleを使ってgitやvimなどの基本的なソフトウェアは開始と同時に勝手に入るように用意しておきました。

言語選択についてですが、おそらくgo言語が実装が公開されている中では高速で有利であろうとは思ったのですが、去年はそうでもなかったらしく、
また、二人ともgoについての知識はなかったのでnodejsで勝負することにしました。
あと、僕の個人的趣味でScalaが好きだったので、スキがあればPlayに移植する計画も立てていました。
sbtが起動するために必要なものはansibleで入るように準備しておきました。

当日

mixiさんが会場提供してくれるとのことだったので、それに参加させていただきました。

問題開始と同時にsshキーの登録、ansibleをつかってのツールインストールはすんなりできました。
今回サーバーは3台与えられていて、初期状態でアプリケーションとDBが1台のみで稼働し、残りは何もしていない状態でした。
スコアはそのうち1台を対象に大量のリクエストを飛ばすので、整合性を保ちつつたくさんリクエストを返せばよい、という内容でした。

ウェブアプリケーションの構成を把握しようとしたが、どうもnginxの設定が見当たらない…と思ったら今年はなんとh2oという全く別のアプリケーションで動いていました。
DBもMySQLではなくMariaDBでしたが、これは想定の範囲内（多少設定に躓いた部分もありますが多分誤差程度）。

ログ解析

予定通りnodejsの実装に切り替えた後、ベンチマークを走らせました。初期状態ではせいぜい1000くらいのスコアしかでません。
では、ボトルネックはどこかな…とログ解析を開始しようとしたのですが、まずSQLのスロークエリが全くない。
あせりましたが、どうやら今年は一つ一つのクエリはそんなに重くないようです。
では、どのエンドポイントが重いのか。alpというのツールで一気にやってしまおう、と計画していたのですが、これを使うにはログのフォーマットをツールの期待する形に整形する必要があります。
nginxで予想していたため、h2oで同じようなconfigを書くかnginxに切り替えるかしかありません。

nginx用の資料はいろいろ集めていたため、はじめはnginxに切り替えようとしたのですが、csvファイルを出力するエンドポイントにて何故かレスポンスが途中までしか出ないという問題が発生したため、最終的にh2oでがんばることに。
格闘の末、ようやくalpが使い物になる状態に。
わかったことは

トップページへのアクセスがそれなりに多い上、一番時間を食う
/admin/api/reports/salesがアクセス回数が数回なのにめちゃくちゃ時間を食う
/api/users/:idもアクセスが多く時間がかかる

また、netdataをつかってのパフォーマンス監視もしていました。こちらはansibleで事前準備しておいたのでiptablesでポートを開けさえすればすぐに使えたのですが、
CPUがめっちゃ動いている、くらいの情報しかわからなく、実際にどこを改善させればいいのかを確定させるためにはalpのアクセスログが必要でした。

複数台構成

netdataの情報からCPUがかつかつでトラフィックも相当というのがわかったので、他のサーバーでもアプリケーションが稼働できるように設定しようとしました。
データベースは1台のみで動かし、残りはリモートからアクセス、という形に。初期化のときに使うコマンドと、アプリケーションが参照するDBの設定が分離されているのがちょっと罠ですが、割とすぐに稼働できるようなりました。
しかし、ベンチマークを走らせるとfailしてしまい、メッセージを見るとタイムアウトとなっている。
どうやら、大量のDBリクエストがあるため、リモートにDBがある状態だとそのオーバーヘッドでタイムアウトしているようでした。
そのため、単にロードバランスするだけではかえって遅くなる危険性があると思い、データベースのアクセスが少ないがCPUリソースを大量に消費する/admin/api/reports/salesのみ他のサーバーにプロキシすることに。
これはかなりきいて、いくつかのアプリケーションコードの改善と合わせてスコアは一気に10000点台に。

しかし、その後は後述するトラブルに見舞われ、思うように構成の見直しはできませんでした。

アプリケーションコード改善

トップページのアクセスから見ていったのですが、N+1問題のオンパレードという感じでした。しかし、いきなり全部変えるのは整合性を保つのが難しくなるので、細かい改善を積み重ねつつリファクタリングする、という感じにしました。
最終的にできたのは

getEvent関数中のreservationsテーブルのアクセスをsheet_idごとではなく一括で行う
sheetsテーブルは不変なので、初期化時にメモリに落としておく
ログインが必要とされるページの処理でnicknameを取得するために余計にDBを叩いていたのでcookieに保存
getEvent関数で取得されるreservationsテーブルの情報は/api/users/:idの表示に不要なので、専用関数をつくってに切り替えてそもそも叩かない
/admin/api/reports/salesはgzip圧縮して返す
くらいです。

とにかくDBへのアクセスを減らすことに注力しました。

謎のトラブル

10000点台を叩き出し、アプリケーションコードの改善を進めていたのですが、何故か良くなる変更のはずなのに10000点を大きく下回る、ということが連続してきました。
よくnetdataの画面を見ると、何もアクセスのないはずのサーバーのnetworkの使用率がやたら高いことに気が付きます。
実は複数台構成にしたり、手元環境からアクセスしやすいようにiptablesでかなり緩い設定をいろいろと仕込んでいました。これはまずいと思い、iptablesの設定を慌てて変更。これで多少スコアは持ち直したのですが、それでも低い。
どうも、このスコア、ブレブレなのは日常茶飯事らしいいので、これは仕方ないと思い、最後の調整を進めました。

ところが、終了30分前あたりから、なぜかベンチマークがfailになり続け全く通らなくなる、という事態に陷ってしまいました。iptablesの設定がおかしかったのか、と思いいろいろ再起動をかけましたが治らず。
アプリケーションコードを初期状態にするをしても治らず。/etc以下はetckeeperで管理していたのですが、それも正常だった頃と差分なし。
DBの内容を初期状態に戻すのも効果なし。そもそも今回は/initializeというエンドポイントを叩くとDBとが初期化されるようにデフォルトでなっていて、そこはかえていません。
結局この謎のトラブルを解決できないまま競技終了となってしまいました。
原因として考えられるとしたら

アプリケーションコードのバグ
- randomなケースも混ざっていたのだろうが、それでも10回くらい連続で落ちていたのはおかしい
- 初期実装にも戻したがfailした説明にはならない
h2oのバグを踏んでおかしな状態になっていた
- そういえばh2oの再起動を試していなかった
IPアドレスが変わるなどネットワーク環境がおかしくなっていた
- ベンチマークの実行はssh用のグローバルIPではなく、別の専用プライベートIPを利用していた
ベンチマークがバグっている
- これは他のチームでそういう報告がないのでほとんどありえない
永続化されていない初期設定が存在した
- 運営は再起動後、追試のためベンチマークを走らせるという作業をするため、これもなさそう

ベンチマークを走らせていると、全く同じアプリケーション・同じ構成なのになぜかfailするということが稀にありました。その時は単になんかネットワークの調子が悪かったのかな、程度に考えていたのですが、
もしかしたら何か関係があったのかもしれません。

結局、何が起きていたのかは特定できませんでしたが、このトラブルに遭遇してしまったとき終了間際ということもあり、パニックになってログを見返すなどのエラー特定作業ができませんでした。
仮に外部の影響だったとしてもそれを冷静に分析して、これは外部のせいであると断定するにいたれなかったのは問題でしょう。
いずれベンチマークコードも公開されると思うので、環境を再現して自分で追試してなにか原因をつかめれば、と思います。

Scala

実は/admin/api/reports/salesはScalaにすれば速くなるのでは、みたいな話はしていたのですが、さすがに余裕がありませんでした。
でも、勝ちを捨ててそういう方向性に走るのも悪くなかったかなあ

昼食

Uber Eatsで海鮮丼的なものを食べて優勝しよう（ここでいう優勝は競技での優勝ではない）という話になっていたのですが、そもそも店の選定をしていないという状態で、おまけに店を選定している最中にUber Eatsのサーバーが落ちるとかいうことに見舞われ、ろくな昼食が取れませんでした。
一応、SOYJOYを事前に買っていたのでそれでごまかしましたが、やはり海鮮丼には大きく劣り優勝には程遠い感じになってしまいました。

その代わり、夜は焼肉っしょ！！！ということで夜はいい感じの焼肉を食べたのですが、その焼肉屋に傘を置き忘れるとかいうトドメを刺されてとてもつらい

感想・懺悔

ベストスコアは13000くらいだったと思うのですが、1日目のトップチームが50000点台であったことを考えると、トラブル云々がなくても予選通過は無理があろう思われます。

問題について

非常に良い問題だったと思います。初期実装ではかなり改善するところが多い状態ですべてを解決するのは短時間では無理なので、ちゃんとボトルネックを見極め、改善する箇所の優先度を見極められる能力が求められたものだと思います。
やるべきことが多い分、3人目がほしかった。

あと、ベンチマークスコアのブレ幅は……去年も言われていたようですし、この手のコンテンストでは難しいのでしょうか

準備不足

ある程度の準備はしてきたつもりでしたが、ログ解析周りの準備はかなりずさんでした。alpの使い方も十分に把握できていなく、また、alpはかなりログの形を限定してくるため、
もっと軽量で使いやすい解析手段の用意も考えるべきでした。
細かいところで言うと、.bashrcや.vimrcなども多少はいじっておいたほうがよかったかもしれません。
普段であれば僕はdotfilesレポジトリに自分好みの設定を上げておきそれを入れているのですが、他の人も使うのに結構ゴテゴテしているので好みが分かれるかなと思って入れるのを見送りました。

また、firewallの設定方法も確認しておくべきでした。今回僕はiptablesでポート開放を行っていましたが、CentOSはfirewall-cmdで操作するのが普通です。いい加減なセキュリティ設定はやめるべきでした。
ここらへんは踏み台サーバー的なものを用意しして置くと更に楽できたかもしれません。そうすれば初めのssh-copy-idは1サーバーあたり1回ですみますし、ポートもsource IPで制限して開放すればリスクをかなり軽減できたと思います。

あと、keepalivedなんかも使えるかなあとか画策していたのですが、事前にまともに使う練習をしなかったので、結局使えず仕舞いでした。

ansibleはよかったです。ローカルのPCさえきちんと設定していれば動くし、単なるssh経由でshell scriptを走らせるラッパ程度の使い方でもかなり役に立つと思います。

整合性を保ちつつ改善する

今回の問題ではDBにアクセスする→結果を元にオブジェクトをつくる→足りない情報を別テーブルから複数のクエリを投げて取得するといういわゆるN+1問題が多く、仕込まれていました。
ただ、これを解決するにはコードが何をしているかをちゃんと把握して、書き換える必要があり、その際気をつけないと仕様を満たさなくなる恐れがあります。

今回、僕らのチームは変更したらいきなりベンチマークを走らせてそれでテストするというやり方をとっていて、非常にヒヤヒヤしながら開発していました。テストケースのようなものは特に与えられていなかったので。
できれば、自前の小さなテストケースを用意しておいて、それを変更ごとに走らせて整合性を確認する、とかができるとよかったかもしれません。
ただ、この短時間・少人数のコンテストでそれができるかはかなり疑問ではあります。

来年に向けて

そもそも来年開催されるかどうかは不明ですが…本当に面白いコンテストなので来年もあればぜひ参加したいですが、
運営はチーム数x3のサーバーを手配して参加費も取らないので相当大変だったと思います。本当にお疲れ様でした。

まず3人チームをつくる
今年の問題のトラブルの検証と延長戦
もっとansibleでいろいろ入るようにする
ログ解析手法の洗練化
firewall-cmdの勉強
昼食はちゃんと決める

2018-09-02

ベトナム旅行記

ベトナムのハノイに2泊3日に行ってきた

ホテル

Little Hanoi Deluxe Hotelに宿泊した。かなり狭めのホテル。日本のビジネスホテル程度のクオリティ。
しかし、値段はその分安いし、英語も通じる。特にスタッフの対応はすごく親切で、外出する際の注意事項（道の渡り方とか）をアドバイスしてくれたり、チェックアウト時にはコーヒー粉とそれを淹れるためのフィルターをお土産としてくれたりしてくれた。

ネット環境

一応、FreeのWi-fiはいろいろなところで使えるようなのだが、かなり不安定でつらい。
SIMフリーの端末を持っていたので、格安のSIMカードが空港で買えるので、今回はそれを利用した。Viettelという会社でデータ通信のみ30日間で3.5GB利用可能のプランで、正確な値段は忘れてしまったが日本円で600円程度だったと思う。
電波の範囲もかなり広く届いていた印象。

また、SIMカードはamazonで日本からでも購入可能なようだ。信頼性は分からないが、万が一ダメでも1000円もしないので、こっちで思い切って買ってしまうのも手であろう。

通貨

ベトナムドン（VDN）が使われている。1円≒210VDNとかなりインフレしている。1000ドン以下は切り捨てされるし、場合によっては1000ドンすらお釣りとして出すのを躊躇されることもある。
物価は全体的にかなり安い。ホテル代を除いて15000円両替したが、かなり良いレストランとかに入ったりしたが、ちょうど使い切るくらいだった。

交通

車社会。バイクも車も多く、交通ルールもめちゃくちゃ。スピードは出しまくるし、信号も少なく、前の車を追い越すには対向車線にでることも厭わず進んでいく。
バスや電車は安いがそこまで多くはないので、タクシーを使うことになる。ただし、タクシーのボッタクリ業者には要注意。
また、Grabという配車アプリを使う手もある。こちらは信頼性も高く安いのだが、ベトナムで有効な電話番号が必要なのと、運転手にはベトナム語しか通じないことも多いのに要注意。

歩道は狭く、バイクに占拠されていたり、なぜか道端でものを燃やしていたりして、横断歩道も少なく車も割と容赦してくれないので、歩き回るのには苦労した。

お土産

ハノイタワー1階にあるイオンシティマートで買った。お土産専門店ではないので輸入品も多い点には注意。
コーヒー（ベトナムは輸出量世界一らしい）やお菓子類、インスタントラーメン系などいろいろ買える。

空港で買おうとするとここの3倍近い値段で買う羽目になるので注意。

まとめ

ひさびさの海外旅行で楽しかったのだが、もうしばらくはベトナム行きたくない

2018-05-28

Arm Cortex-MのRustベアメタルをQEMUでデバッグ

前回記事で紹介したTockのように、RustでもArmでのベアメタルプログラムができるようになってきた。
ベアメタルプログラミングで複雑なことをやろうとするとやはりエミュレータが欲しいな（以前、ハイパーバイザをつくった時はエミュレータなしでつらかった）、と思ったのでやってみた。

STM32 Nucleo

省電力な組込み向けのアーキテクチャのCortex-MシリーズのMCU評価ボードは様々あるのだが、今回はSTM32 Nucleoをターゲットとすることとした。
理由としては

以前、STM32 Discoveryを使用していたことがある
日本でも比較的安価な評価ボードが購入できる（3000円くらい）
Mbedに対応しているため、C/C++ベースではあるがサンプルコードが豊富なため

なお、Tockは独自の評価ボードを提供し、それを利用している。

GNU MCU Eclipse QEMU

今回使うことにしたQEMUは本家のではなく、そのフォークであるGNU MCU Eclipse QEMUを用いる。

参考: QEMUでCortex-M3/M4マイコンボードをエミュレーションしてLチカする話

Eclipseのプラグインのためのものであるが、コマンドラインから直接叩いて動かすのも可能。
本家QEMUより多くのボードをサポートしており、ボードの画像を表示してLチカのデバッグも可能なようだ。
xpmを用いて簡単に導入することができる。

詳しい導入は公式ドキュメントに従えば良い。

サンプルコードの入手

参考: ARM Cortex-M 32ビットマイコンでベアメタル “Safe” Rust

今回動かしたコードはjaparic氏が提供しているcortex-m-quickstartを用いた。
参考にしたブログ記事は微妙に古いのでこちらのcrateのドキュメントを参照した。

実行

cortex-m-quickstartをドキュメント通りにビルドする。ただし、このQEMUはFPUのサポートがないため、targetはFPUなしのものを（hfで終わらないもの）を選ぶ必要がある。
生成物はcargo build --releaseの後、target/thumbv7em-none-eabi/releaseにできる。以下のようなシェルスクリプトを用意してQEMUを実行した。

qemu-system-gnuarmeclipse.sh

#!/bin/sh

qemu_command=$HOME/opt/xPacks/@gnu-mcu-eclipse/qemu/2.8.0-3.1/.content/bin/qemu-system-gnuarmeclipse
board_name=NUCLEO-F411RE
mcu_name=STM32F411RE

$qemu_command \
--verbose --verbose --board $board_name --gdb tcp::3333 \
    --mcu $mcu_name -d unimp,guest_errors  \
    --image $1 \
    --semihosting-config enable=on,target=native \
    --semihosting-cmdline $1

gdbのポートはcortex-m-quickstartの.gdbinitで3333になっているので3333を指定した。
実行結果は以下の通り。

$ ./qemu-system-gnuarmeclipse.sh target/thumbv7em-none-eabi/release/cortex-m-quickstart

GNU MCU Eclipse 64-bits QEMU v2.8.0-3 (qemu-system-gnuarmeclipse).
Board: 'NUCLEO-F411RE' (ST Nucleo Development Board for STM32 F4 series).
Board picture: '/home/garasubo/opt/xPacks/@gnu-mcu-eclipse/qemu/2.8.0-3.1/.content/share/qemu/graphics/NUCLEO-F411RE.jpg'.
Device file: '/home/garasubo/opt/xPacks/@gnu-mcu-eclipse/qemu/2.8.0-3.1/.content/share/qemu/devices/STM32F411xx-qemu.json'.
Device: 'STM32F411RE' (Cortex-M4 r0p0, MPU, 4 NVIC prio bits, 86 IRQs), Flash: 512 kB, RAM: 128 kB.
Image: 'target/thumbv7em-none-eabi/release/cortex-m-quickstart'.
Command line: 'target/thumbv7em-none-eabi/release/cortex-m-quickstart' (54 bytes).
Load  16028 bytes at 0x08000000-0x08003E9B.
Cortex-M4 r0p0 core initialised.
'/machine/mcu/stm32/RCC', address: 0x40023800, size: 0x0400
'/machine/mcu/stm32/FLASH', address: 0x40023C00, size: 0x0400
'/machine/mcu/stm32/PWR', address: 0x40007000, size: 0x0400
'/machine/mcu/stm32/SYSCFG', address: 0x40013800, size: 0x0400
'/machine/mcu/stm32/EXTI', address: 0x40013C00, size: 0x0400
'/machine/mcu/stm32/GPIOA', address: 0x40020000, size: 0x0400
'/machine/mcu/stm32/GPIOB', address: 0x40020400, size: 0x0400
'/machine/mcu/stm32/GPIOC', address: 0x40020800, size: 0x0400
'/machine/mcu/stm32/GPIOD', address: 0x40020C00, size: 0x0400
'/machine/mcu/stm32/GPIOE', address: 0x40021000, size: 0x0400
'/machine/mcu/stm32/GPIOH', address: 0x40021C00, size: 0x0400
'/machine/mcu/stm32/USART1', address: 0x40011000, size: 0x0400
'/machine/mcu/stm32/USART2', address: 0x40004400, size: 0x0400
'/machine/mcu/stm32/USART6', address: 0x40011400, size: 0x0400
'/peripheral/led:green' 8*6 @(316,307) active high '/machine/mcu/stm32/GPIOA',5
'/peripheral/button:reset' 30*30 @(312,214)
'/peripheral/button:user' 30*30 @(204,219) active low '/machine/mcu/stm32/GPIOC',13
GDB Server listening on: 'tcp::3333'...
Cortex-M4 r0p0 core reset.

Hello, world!
^Cqemu-system-gnuarmeclipse: terminating on signal 2

Rust on baremetal Armの現状

cortex-m-quickstartの作者であるjapric氏はXargoをつくった人でもあり、かなり積極的にこの分野に貢献している人である。

@rustlang, stability without stagnation, taken to robotics

Probably the first WIP self-balancing robot coded in 100% Rust#RustyRobots 1/ pic.twitter.com/MGRPgKVCsS
— japaric @ Rustfest (@japaricious) 2017年3月25日

彼が今年初めに去年あったベアメタルArmのRustで起きたバグと今年の展望をまとめている。
Embedded Rust in 2018 | Embedded in Rust

現状、ベアメタルArmでプログラミングするためにはunstableなfeatureを使わざるを得ないため、完全に安定とは言えないものの、かなり状況はよくなってきているようだ。

2018-05-23

論文紹介：Multiprogramming a 64kB Computer Safely and Efficiently

元論文：Multiprogramming a 64 kB Computer Safely and Efficiently

以前の記事でも少し紹介したRustで書かれた組み込みハードウェア向けのOSの設計についての論文である。

実際のOSのプロダクトのサイトはこちら： Tock Embedded Operating System

論文概要

タイトル：Multiprogramming a 64 kB Computer Safely and Efficiently
著者：Amit Levy (Stanford University) et al.
会議：The 26th ACM Symposium on Operating Systems Principles (SOSP 17)

目的

同年のAPSysで発表した論文がRustという言語でどのようにOSを書くかを論じているのに対して、こちらはタイトルからもわかるようにCPUが貧弱でメモリが非常に少ない環境でのOSデザインについて論じている。
著者らが対象としてるのはCortex-MシリーズのようなRAMが数10kB程度、MMUのような高度なメモリ保護機能がないマイクロコントローラ（MCU）である。
このようなMCUでも、例えばスマートウォッチのように複数の独立したアプリケーションを動かすためOSが必要になってくる。
もちろん、MCU向けのOSというのは多く存在しているが、並列性やメモリの効率、Fault isolationなどの要件を同時に満たすのは容易ではない。

著者らTockというOSをRustで実装し、これらの課題に取り組んだ。

CapsulesとGrants

Tockを構成するキーとなる概念がこのCapsulesとGrantsである。

Capsulesはカーネルに組み入れられるコンポーネントとなるユニットたちで、Rustの構造体として現される。
このCapsuleを用いてデバイスのインターフェースやシステムコールのインターフェースをつくる。それぞれのCapsuleはRustの型システムによって互いのメモリに直接は干渉できないようにできる。
Capsuleのメモリ安全性は型システムによる所有権により検証される、つまりコンパイル時に検証されるので実行時のオーバーヘッドを最小限にできる。
カーネルのスケジューラはイベントドリブンで駆動し、Capsulesと直接やりとりする。Capsules自体はイベントを発行することはないため、スケジューラを介す必要はない。単純な関数であればインライン化されることも期待されるのでこれも実行時のオーバーヘッドを減らすことになる。
ただし、プリエンティブされることはないことになるので、実行時間の長い処理をさせるとシステム全体を止めることとなり得る。

Tockにも通常のOSのようにプロセスの概念が存在する。それぞれ独立のヒープ領域とスタック領域を持ち、カーネルやその構成要素のCapsulesとはシステムコールイベントを発行することでやりとりする。
ただし、MCUはMMUを持たないため、全て絶対アドレスでのメモリアクセスとなる。そこで代わりにMemory Protection Unit(MPU)を用いてメモリ領域を保護する。
プロセス自体はどんな言語でも書け、またスケジューラによってプリエンティブされる。

プロセスがCapsulesに処理を依頼する場合、そのリクエスト毎にメモリが必要となることがある。例えばタイマーであれば、どの時間にどの関数を呼び出すか、のようなメタデータを格納する必要がある。
ただし、システム実行中にそのメタデータを最大いくつまで保持しなければならないかを予想するのは難しい。そのため、単に静的に確保した配列に情報を格納すれば、並列に実行できるリクエストの数を制限することになるし、
動的にメモリを確保しようとすれば、カーネルのヒープ領域が突然足りなくなることが考えられる。
そこでTockではプロセス毎にGrantsと呼ばれる領域を持たせて、このメモリ領域をCapsulesに渡す、というテクニックを用いる。カーネル領域のヒープ領域に対して、Grantsはプロセス内の一種のヒープ領域みたいなものなので（プロセスの通常のヒープは別に存在している）、
動的にメモリを確保することにはなるが、メモリが足りなくなっても、そのプロセス1つのみが困るだけなのでシステム全体が困るという自体は避けられる。
Grants領域はMPUで保護されているため、プロセス自身がこの領域を直接アクセスすることはできない。

評価

Tock自体、全く新しい構成のOSなので従来OSとの単純比較はできない。
そこで、Case StudyとしてTock上で実際にアプリケーションを実装した時のCase Studyと、新たに導入された概念であるCapsulesとGrantsによるパフォーマンスの検証を行っている。
ボードはArmのCortex-M4を用いた評価ボード上で構成している。
CapsulesやGrantsの各種インターフェースは当然ある程度のメモリオーバーヘッドと実行時オーバーヘッドを伴うが、それがモノリシックなシステムや既存のプロセスベースのシステムと比べて少なくてすむことを検証ている。
ただ、Grantsの導入はカーネルのアルゴリズムの変更を強要する。例えば、タイマーの例であれば、ハードウェアからの割り込みが発生した際、どの処理を行うか登録されたイベントから探さなければならないが、
その情報は各プロセスの各Grants内に入っているためそれを全て走査しなければならない。ただし、そもそもMCU上でのシステムで大量にプロセスが発生することはあまりないので大きい問題にはならないと主張している。

まとめ・感想

Rustの型システムを活用することで、新たな概念を利用しつつ組み込みOSに適した並列性、メモリの効率性、Fault isolationをTockは達成した。

まだ実際の実装を追うところまではできていないので、進捗ダメです

2018-02-23

Rustでプログラミングコンテスト

最近は熱心にプロコンをやる気力が起きないが、Rustの勉強として気が向いた時にちょくちょくAtCoderの問題をRustで解くということをしている。
AtCoderではRust 1.15.1とちょっと古めのバージョンしか対応していないため（今だとstableが1.24.0）、ちょくちょく不便なこともあるがまあなんとかなっている。
コンパイル言語でJavaやScalaのようなJVMの初期化処理もないおかげで、理不尽なTLEを食らうことは今のところない（とは言ってもABCのD問題程度ではそんなことはそもそも稀か）

最近解いた問題を貼ってみる。まだまだRustには不慣れなので、めちゃくちゃなコードも結構混ざっている。

D - Wide Flip | ARC088

方針を考察するのが辛いが実装はシンプルにすむ。自分の提出

D - 2017-like Number | ABC084

前処理で2017-like Numberの数を数えればおしまい。なのだが、前処理のテーブルをつくる関数がひどい。make_memoの引数は借用にするべきだった。
自分の提出

C - 駆引取引 | みんなのプロコン2018

メモ化再帰。前処理のテーブルをつくるときに18182^18になる解法
手元では最適化をかけずにコンパイルしたせいか結構遅く感じたが、蓋を開けてみれば比較的余裕だった。　自分の提出

D - Grid Repainting | ABC088

よく考えると（というかネタバレツイートを見てしまった）最短距離を求めるだけなのでダイクストラしている。
隣接マスへの移動をループで表現するためdx[] = {-1,0,1,0}という感じの配列をつくるというのを他の言語ではやるのだが、Rustだと配列のインデックスの指定はusize型で行わなければならないため、キャストを連発している。
i32やusize、i64へのキャストはC++では暗黙でやってくれたが、Rustでは明示的にやらないといけないのはいろいろなところで辛い。
もちろん、それで未然に気がつくミスというのもあるのだろうが、多分プロコンでは足を引っ張ることのほうが多そう
自分の提出

2018-01-29

spectreとmeltdownの対策

前回のブログでspectreとmeltdownの原理についてまとめたので、今度はその対策についてまとめる。

そもそもspectreとmeltdownはすべてハードウェアそのものに原因があるが、これらの対策はソフトウェアでなんとか防ごうというものである。
また、これらの対策はパフォーマンス低下を伴うが、最終的にはその影響はそこまで大きくなかったようだ。

Variant 1 (Spectre)

特権レベルで動くソフトウェアが、ユーザーのコードを実行する際の配列境界チェックをかいくぐるというものだった。
対策としてはそもそもそのようなコードを特権環境で動かさないといものがまず挙げられる（LinuxではeBPFを無効化するなど）。
また、コンパイラレベルでこのような脆弱性を生むコードを防ぐというものも挙げられる。
ARMの場合は配列境界チェック用のbuiltin関数を提供している。
https://developer.arm.com/support/security-update/compiler-support-for-mitigations
Windowsもコンパイラを変更し、再コンパイルしたものを配布しているようである。

Variant 2 (Spectre)

間接ジャンプ予測先をインジェクションすることで、KVMのモジュールなどのアドレスを抜き出し、ゲストOSのメモリの内容を盗み出す攻撃であった。

こちらも特権レベル中で動く既存のコードを利用するものなので、その部分のコードを変更することになる。最も単純な方法としては分岐予測を無効にすることであるが、当然コストがかかる。
これらの方法よりお手軽な方法としてRetpolineという手法も公開され、gccやllvmにも実装された。
これは間接ジャンプ命令を書き換え、逆に間接分岐先を予めコントロールしてしまおうといものである。
Intelのプロセッサの場合、普通の間接ジャンプと関数呼び出しから戻る時の間接ジャンプ（スタックに戻り先が記録されているので、その値を読む間接ジャンプによって呼び出し元に戻る）では、使う分岐予測のバッファーが違うことを利用する。
普通の間接ジャンプ命令を、関数呼び出しとスタックの戻り先の書き換えにより実現することによって、分岐予測器を騙し投機実行を止める、というのがRetpolineの概要である。

Variant 3 (Meltdown)

この脆弱性は、Spectreと違い特権レベルで動くコードに依存せず、完全にユーザーレベルで完結してしまう。
そもそもの原因はカーネルとユーザープログラムの間で同じページテーブルを使っているということなので、これを分離することで解決できる。
LinuxではKPTI（Kernel page-table isolation）と呼ばれる。もともとはKAISERというパッチがmeltdown発覚より前に公開されていて、それをベースとしたもののようだ。
KAISERも同様にカーネルとユーザープログラムの間でのページテーブルを分けるというものであったが、想定していたのはKASLR（kernel address layout randomization）が破られるというものであった(参考：https://gruss.cc/files/kaiser.pdf)。
ページテーブルを分けるということは、TLBフラッシュの頻度を増やすため、アプリケーションによってはパフォーマンスが低下する恐れがあるはずだが、パフォーマンス低下を軽減する方法について言及している資料は自分はまだ見つけていない。

参考

2018-01-07

spectre and meltdownまとめ

IntelのCPUの重大なバグが発覚した、のような騒ぎから話題になったspectreとmeltdownについて調べた。

基本的にはGoogle Project Zeroチームによるブログポストが最も信頼性の高くかつまとまっているので、この記事はそれのまとめ的なもの
https://googleprojectzero.blogspot.jp/2018/01/reading-privileged-memory-with-side.html

発端

おそらくここの記事でIntelのCPUにバグが発覚したと報じ他のメディアがこれを拡散。
ただ、情報がかなり曖昧で、本当にIntel固有なものなのか、従来から指摘されている攻撃の可能性（現実的には不可能だから対処する必要はない）のことではないかなど様々な憶測が飛び交い
最終的にはGoogleやIntelが声明を発表し、去年から発覚していた攻撃手法で近日発表する予定だったが情報がリークしてしまったので、前倒しで詳細を公表するとのことだった。

概要

spectreとmeltdownは３つの攻撃手法のことを指す。どれもCPUの性質を利用することによりカーネルによって保護されている領域に対してユーザースペースからアクセスしようというものである。

当初、Intel CPUのバグと言われていたが、CPUが誤動作するため保護が破れる、という類のものではない。
これらはキャッシュや分岐予測といった様々なCPUで広く用いられている高速化手法により発生するCPUのある種の癖を利用してメモリを読みだそうとするものである。
よって、Intel固有のものではなく、AMDやARMでも起こりうると明記されている。
しかし、影響を受ける可能性が高いのはIntelのCPUでProject Zeroのブログでも主にIntelアーキテクチャでの話を元に進められている。

攻撃の原理

spectreとmeltdownの原理について簡単にブログから要約する。spectreがvariant 1と2を指し、meltdownがvariant 3を指す。

Variant 1: 境界チェックバイパス

カーネル内の境界チェックをすり抜けて、アクセスが禁止されている領域の値を読みだす方法。
この方法はユーザーがカーネルに処理を依頼して、カーネル内で処理を実行するアプリケーションを利用した攻撃である。
今回のProof of Concept(PoC)ではeBPF（extended Berkeley Packet Filter）というユーザーによってパケットフィルターを定義するインターフェースを利用している。

この攻撃で肝になるのは投機的実行である。
これはif文などの条件分岐の結果が決定する前に、どちらの結果になるかを予想して処理を進めてしまうCPUの高速化手法である。
本来であればその予想が外れた場合、投機的実行による変更は巻き戻されそれが外部に漏れることはない。
しかし、この失敗した投機的実行内でメモリアクセスが行われていた場合、そのメモリの結果はキャッシュに残る。
キャッシュに残るだけではユーザーがその値の中身を読み取ることはできないが、キャッシュにデータが残っている場合、そのアドレスへのアクセス時間は短くなる。これを利用する。

具体的なコードのスニペットをProject Zeroのブログポストより引用する

struct array {
    unsigned long length;
    unsigned char data[];
};
struct array *arr1 = ...; /* small array */
struct array *arr2 = ...; /* array of size 0x400 */
/* >0x400 (OUT OF BOUNDS!) */
unsigned long untrusted_offset_from_caller = ...;
if (untrusted_offset_from_caller < arr1->length) {
    unsigned char value = arr1->data[untrusted_offset_from_caller];
    unsigned long index2 = ((value&1)*0x100)+0x200;
    if (index2 < arr2->length) {
        unsigned char value2 = arr2->data[index2];
    }
}

untrusted_offset_from_callerというのが読まれたくないメモリ領域のアドレス。本来であればif文による境界チェックによって処理は実行されないはずだが、
arr1->lengthの値がキャッシュに載っていない場合、メモリロードによる待ちが発生しその間に投機的実行によってif文の中身が実行される。
untrusted_offset_from_callerの値がキャッシュに乗っていた場合、valueの値がすぐに読みこまれ投機的実行が進む。
index2の値はvalueの値によって0x200か0x300となり、このアドレスのメモリ領域のアドレスはユーザーがアクセスできる。
投機的実行によってこのメモリ領域もキャッシュに乗る。
最終的にこの投機的実行の結果は破棄されるのだが、0x200がキャッシュに乗っているか0x300がキャッシュに乗っているかでvalueの1bitが読み込めてしまう。
キャッシュ乗っているか否かは、メモリロードの時間によって分かってしまう。

Variant 2: 分岐ターゲットインジェクション

この攻撃では、KVM上でのゲストマシンから同じCPU上での他のゲストマシンのページアドレスやKVMのモジュールがどこにロードされているかを特定するものである。
当然、アドレスが分かっただけではMMUによって保護されているはずなのでそのまま中身を知ることはできない。が、PoCではeBPFを使うことによってデータを取り出している
（ここの詳細は理解できなかった。ROPの要領でコードを実行させて、Variant 1と同じ方法でキャッシュからデータを引き出す？）。

この攻撃ではindirection branch（分岐先のアドレスがメモリ上にあるような分岐）の分岐予測を利用する。indirection branchの分岐先がキャッシュされていない場合、そのロードの時間がかかる。
そのため、投機的実行のためにどのアドレスに分岐するか、その命令アドレスに対してどこに分岐したかの履歴をもとに予測する機構がついている。
この機構の詳細は公開されていない。そのため、この機構のリバースエンジニアリングから説明されている。
そのリバースエンジニアリングの結果を元に、予め分岐予測機構の状態を設定し、hyper callなどの実行時間の差から分岐予測が失敗したかどうかを知ることでアドレスを知る、というのが概要である。

正直、ここの説明は自分では理解できない点も多かった。

Variant 3: Rogue data cache load

（1/13　補足）cyber.wtfのブログ内容についても言及を加え、ARMプロセッサの例についても補足

ユーザースペースからカーネル空間のメモリを直接読む攻撃。これがMeltdownと呼ばれるもので、今回の騒動で最も広い範囲に影響が出ると考えられているようだ。

詳細はこちらのブログ参照
https://cyber.wtf/2017/07/28/negative-result-reading-kernel-memory-from-user-mode/

基本的なアイデアとしては、メモリの権限設定のチェックが完了する前にプロセッサはメモリの読み込みを投機に実行していて、Variant 1と同じ要領でメモリの値が読めるというもののようだ。
コードのスニペットを上記ブログより引用する

1
2
3

Mov rax, [somekerneladdress]
And rax, 1
Mov rbx,[rax+Someusermodeaddress]

カーネル空間からのメモリ呼び出しの直後にその値に依存するユーザー空間アドレスへの読み込みを行い、その後、どこがキャッシュされているかでそのカーネル空間のメモリの値を確定させようというものである。
ページテーブルによる例外が発生する前に、後ろの2つの命令が投機的実行されると可能になってしまうというわけである。
ここで後ろ2つの命令が投機的実行されてしまうとVariant 1と同じように、どのアドレスがキャッシュされているかによってユーザー空間からカーネル空間のメモリの値が読める。

しかし、cyber.wtfではこのような不正なアクセスをした場合は投機的実行中raxの値が常に0になるような挙動をしたので結果的には失敗した、としている。
Googleのチームは、cyber.wtfチームがやっていたカーネル空間をキャッシュするために呼び出していたprefetch命令を使うのを辞めたところうまくいった、としている。

また、ARMプロセッサの場合、この攻撃の亜種としてカーネルモードでしか読めないシステムレジスタを読み出せてしまうことがある。
ARM社のwhite paperよりコードを引用する。

LDR R1, [R2] ; arranged to miss in the cache
CMP R1, #0
BEQ over ; This will be taken
MRC p15, 0, R3, c2, c0, 0 ; read of TTBR0
LSL R3, R3, #imm
AND R3, R3, #0xFC0
LDR R5, [R6,R3] ; R6 is  an PL0 base address
over

4行目のコードがTTBR0というページテーブルに関する情報が格納されているシステムレジスタをR3レジスタに格納して、
その結果を使ってユーザー空間のアドレスを決定してロードする、ということをしている（PL0とはARMでのユーザーモードを意味する）。
3行目が分岐命令で、本来ならばoverまで飛ぶのだが、分岐予測が失敗すると4行目以降が投機的に実行され、
最終的にVariant 1と同じようにどのユーザーアドレスがキャッシュされているかでシステムレジスタの値が読めてしまう。

まとめ

とりあえずProject Zeroのブログポストのうち、攻撃原理に関わるところを中心にまとめてみた。
Intelプロセッサのアーキテクチャやセキュリティ分野にそこまで詳しいわけではないので、誤りも多々含まれるかもしれないが、見つけたらご指摘お願いします。

ARMなどからも発表があるのでそちらの方も読み込んだらまた補足をしていきたいと思う。