/

問題文

ホビットカンパニーの社長からの1つ目のトラブルを解決した後、社長が嬉しそうに話かけてきた。

ホビット社長「やっぱり君たちにお願いしてよかったよ」

エイト「褒められてるわよ、やったじゃない!」

すると社長が独り言のように呟いた。

ホビット社長「もしかしたら…君たちならあのトラブルを解決してくれるかもしれないな」

エイト「何かあるんですか?」

ホビット社長「実は我が社でOpenStackを構築したのだが、何故かログインできないのだ。もしよければ解決してくれないか?」

アクセスできるサーバ

  • OpenStack All-in-One がセットアップされたサーバ1台のsshのアクセス情報 (sudo権限あり)

達成すべき事項

  • OpenStack Horizon のダッシュボードを開ける状態にする

問題内容

ICTSC7 の運営側で実際に起きたトラブルを(厳密ではないですが)再現したものです。今回は電源に関するトラブルがありましたが、ICTSC7 ではこのようなトラブルがおきており、しかもその際には HotStage 期間に3日を費やすも原因が究明できず、お蔵入りとなったのでありました。

OpenStack Horizon は Python で書かれた WSGIアプリケーションで、OpenStack の各コンポーネントのフロントエンドとしての機能を果たすコンポーネントです。
Horizon の設定ファイルは主に /etc/httpd/conf.d/15-horizon_vhost.conf と /etc/openstack-dashboard/local_settings に記述されていますが、今回は一方のみを変更しています。

この中で、認証サーバである Keystone のエンドポイント等を指定しているのですが、その際に Keystone の API バージョンを誤って指定したことによりトラブルが発生していました。

具体的には、以下の部分を変更して出題しました。

/etc/openstack-dashboard/local_settings 200行目付近

OPENSTACK_KEYSTONE_URL = "http://10.0.0.20:5000/v2.0"

変更後 (問題が起きている状態) は以下です。

OPENSTACK_KEYSTONE_URL = "http://10.0.0.20:5000/v3.0"

回答例

まず、認証情報ですが /root/keystonerc_admin に openstack コマンドを使用する際に使用する認証情報(IDとパスワード等) が記述されています。

問題内容の節にて述べた設定ファイルの変更を元に戻し、た上で、Apache のリスタートを行うことで問題が解決します。
また、Apache をリスタートしてもブラウザからログインができず、エラーもでずにログイン画面からログイン画面にリダイレクトし続ける状態になることがありますが、これはブラウザのセッション(クッキー)を削除することで解決します。
(これについては Keystone 等にも特にエラーログが流れないので、解決に苦労した方もおられるかもしれません。)

想定解は上記の通りでしたが、OPENSTACK_KEYSTONE_URL = "http://10.0.0.20:5000/v3" にすることでも問題が解決するようでした。このあたりは OpenStack のバージョンにも依存してきますね。

講評

/root/keystonerc_admin を使用してのopenstack コマンドを用いた操作は正常に行えることから、 Keystone 側の設定がおかしいわけではないということがある程度予想できます。

その上で、Horizon にのみログインできないという挙動から Horizon の設定における Keystone 関連のエンドポイントのパスやバージョンを確認するというのが運営側の想定解答方針でした。

本問のトラブルは、 OpenStack Ocata では起きないため、意図的に OpenStack Newton を使用して構築された OpenStack 上でのトラブルでした。このバージョンからトラブルに気が付いた方もおられたのでは無いでしょうか。

前回の運営委員が解決できなかったということを踏まえ 、配点がかなり高い問題でしたが、6チームから解答を受け、4チームが正解されました。

おわりに

なかなか OpenStack を手で構築したという方は少ないかもしれませんが、そのような経験があると、全体のコンポーネントの関連性や設定についても理解が深まるため、一度行われてみると良いかもしれません。

 

 

 /
カテゴリー

まずはこちらの資料をご覧下さい.

中国ではインターネットの検閲を行うため,また国内のネットワークを世界中の攻撃から守るため,政府が様々な企業の協力の下に強力なファイアーウォールを構築しています.このファイアウォールにより中国国民はインターネット上での安全がある程度保証されるわけですが,同様にインターネット上での自由を制限されることがしばしばあります.このネットワーク環境はなかなか挙動が興味深く,実際に中国に行ってみると上記の資料にあるような現象に直面します.


さて,今回ICTSC8の謎の国で出題した問題ですが,他の問題とは異なりこの国の問題だけ全て同じ作問者によるものです.上記のような環境で起こりうる問題 (3問目は除く) を順番に解決してもらうことをテーマに作問しました.

全体の概要

参加者に与えられたVM (以降client) は必ず特定のゲートウェイを通るようになっており,ここでLinuxマシン (以降routerとする) が動いていました.そしてこのrouter上でnetfilterを用いてパケットをチェックし,特定の通信しか許可しないLKM (Greatfirewall daemon, 以下GFD) が動いていたため,参加者のVMは自由にインターネットが使用できない状態にありました.
なお,GFDのソースコードおよび他に使用したファイルはこちらにあります.
GFDでは次のような処理を行っていました.

  • UDP
    • ポート53番宛のパケットをrouter自身のdnsmasqによって返答 (DNS)
  • TCP
    • ictscをデータ部分に含むパケットをDROP
    • DNSまたはHTTPではないパケットをDROP
  • その他
    • 制限なし

ここでclientへのDNS応答は本来のサーバーから返ってきたように見せるため,パケットの送信元アドレスを偽装する必要があります.そこでGFDは内部にテーブルを持ち,書き換えたパケットの本来の宛先アドレスを保持し,送信元のIPアドレスとポート番号が,(dnsmasqから)返ってきたパケットの送信先IPアドレスとポート番号に一致したらそれに対する応答である,と判断し,返るパケットの送信元アドレスを本来のアドレスに書き換えます.これによって,clientでは 「8.8.8.8 に問い合わせているのに何を聞いても 127.0.0.1 が返ってくる」という状況を作り出すことができます.

第1のトラブル

最初のトラブルは名前解決ができないというものでした.標準のLinuxではDNSの名前解決にudp/53を使用しますが,GFDによりこのパケットは宛先を問わずrouterのdnsmasqによって解決されてしまい,ほぼすべてのドメインが 127.0.0.1 に向いているため,ドメインを用いた通信が見かけ上できないようになっていました.
DNSではUDPの他にTCPも問い合わせに利用して良いとRFC7766で定められています.試しにTCPで名前解決を行うと,

~$ dig +tcp @8.8.8.8 icttoracon.net
...

;; ANSWER SECTION:
icttoracon.net. 3591 IN A 59.106.171.95

...

ちゃんと名前解決可能であることが確認できます.よって,OSがTCP経由で名前解決をするように設定すれば良いということがわかります.
Linuxでは resolv.conf に名前解決関連の設定を書きますが,ここに RES_USEVC オプションを加えることでシステムがTCPで名前解決をするようになります (man参照) .よって,
/etc/resolv.confoptions use-vcを追記するとトラブルが解決できます.

第2のトラブル

次のトラブルはHTTPSのサイトが見られないというものでした.こちらもGFDによりHTTPとDNS以外のパケットはDROPされてしまうことによるものです.また,この問題ではプロキシ用途として検閲の影響を受けないサーバー (以降server) が与えられているため,与えられたVM (client, server) 同士でトンネルを張るのがゴールとなります.
解法はいくつかありますが,ここでは唯一の解答チームであるuecmmaの方法を紹介します.

  • tinyproxyを用意する (@server)
      • sudo apt-get install tinyproxy
      • /etc/tinyproxy.conf に追記
        • Allow 192.168.18.130/25
        • ConnectPort 22
  • proxyを使って外部サーバーにssh接続, SOCKSプロキシを建てる (@client)
    • ssh -o 'ProxyCommand=ncat --proxy 192.168.18.130:8888 %h %p' 192.168.18.130 -D 9979
  • tsocksを用いて外部サーバー経由で通信 (@client)
    • /etc/tsocks.conf を編集
      • server = 127.0.0.1
      • server_type = 4
      • server_port = 9979
    • tsocks firefox &

以上の手順により, clientとserver間でtunnel over ssh over httpが作成され,自由に通信ができるようになります.

その他の解法としては,HTTPの代わりにDNSやICMPを用いるなどの方法が考えられますが,ICMPはデータ部分が小さいため速度面に問題があります.またDNS tunnelの場合はiodineなどを使うと実現できます.

第3のトラブル

最後のトラブルはGFDに攻撃が仕掛けられ,検閲機能がダウンしてしまうというものでした.参加者にはrouterへのアクセス権が与えられ,検閲機能を構成するGFDのバグ修正を行うことがゴールとなります.この問題を見るためには第2のトラブルを解決する必要がありますが,到達したのはuecmmaのみでした.
この問題が開いてしばらくするとUDPでの名前解決ができるようになり,またTCP/UDP全ての通信が通ります.router上でパケットキャプチャをすると 192.168.18.100 から不審なパケットが飛んできており,どうやらこれが原因ということがわかります.パケットの内容は以下の通りです.

  • UDP
    • srcが 192.168.18.253 に偽装されたDNS問い合わせ
  • TCP
    • SYNフラグが立ったパケットがひたすら送られてくる

GFDのソースコードを読むと,これらの攻撃は全て dns_table および tcp_table を溢れさせるためのものということがわかります.そしてこの脆弱性の原因はレスポンスがあるという前提で,書き換えたパケットの情報をテーブルに保持していることにあります.つまり,応答が存在しないようなパケットを送りつけることでどんどんテーブルにエントリが蓄積されていき,dns_table_push および tcp_table_push ができなくなることでパケットの書き換えが行われなくなるのがポイントです.

これを修正するにはレスポンスが存在しないことを想定して,タイムアウト処理を加えます.まずは時間を保持するtimestampをメンバに加えます.

typedef struct {
uint32_t saddr;
uint32_t daddr;
uint16_t sport;
uint64_t timestamp;
} DNS_ENTRY;

typedef struct {
uint32_t saddr;
uint32_t daddr;
uint16_t sport;
uint16_t dport;
uint8_t state;
uint64_t timestamp;
} TCP_ENTRY;

次にpush時にエントリを全て参照するタイミングで,時間のチェックを行います.カーネル空間では do_gettimeofday を用いて時刻を取得できます.また同様にして,pushするエントリにも現在の時刻を付与します.

// dns_table
struct timeval tv;
do_gettimeofday(&tv);
uint64_t cur = tv->tv_sec * 1000000 + tv->tv_usec;

while (start != (dns_idx&(TABLE_SIZE-1))) {
...
  if (table[dns_idx].timestamp + TIMEOUT < cur) { // timeout
    table[dns_idx].sport = 0;
  }
  ...
  if (!table[dns_idx].sport) { // push entry
    ...
    table[dns_idx].timestamp = cur;
  }
}

これにより,push時に古いエントリが削除されるためテーブルが溢れにくくなります.また dns_table および tcp_table はリングバッファになっているため,局所的にエントリが書き込まれるといったことが起こらず,定期的に全てのエントリがチェックされます.

また,このLKMではレースコンディション対策がされていないため,各テーブルを参照するタイミングでロックが必要です.

static DEFINE_MUTEX(dns_table_mutex);
static DEFINE_MUTEX(tcp_table_mutex);

...
  mutex_lock(&dns_table_mutex);
  ...
  mutex_unlock(&dns_table_mutex);
...

この問題においては以上の対策で十分ですが,膨大なリソースを使った攻撃をされた場合処理が追いつかない可能性があるため,テーブルのサイズを大きめに取る,という方法でもある程度対策ができます.

#define TABLE_SIZE (1<<12)

講評

やや特殊な問題設定だったこともあり,第1のトラブルの時点で7チームしか回答を提出しておらず,通過チームについては3チームにとどまりました.最初に述べたような環境の存在を知っていればゴールが見えやすかったと思いますが,実際に経験してみないと対処方法がわからないというトラコンの特徴を体感できたのではないでしょうか.また,第2のトラブルで用いる技術は制限を回避するためだけでなく,信頼できない環境で安全な通信路を確保する手段でもあります.公衆無線LANなどの環境では,いつ誰が個人情報を狙っていてもおかしくない時代です.今回の問題で,途中経路に攻撃者がいる場合は簡単に通信を改竄することが可能であるということがご理解頂けたと思います.
第3のトラブルですが,これはネットワークに加えてLinuxの知識が多少必要になる問題なので,他の問題とは全くコンセプトが異なります.「インフラ系のコンテストでまさかLKMに触れる問題が出るとは思わないだろう」という邪な考えから作成した問題なので,あまり解かれることを想定していませんでした.
この問題を通して検閲ネットワークの雰囲気を少しでも体感して頂けたのであれば幸いです.

 /
カテゴリー

こんにちは。この記事では第8回で出題された始まりの国 第三のトラブルを解説します。

この問題はrootユーザーが一般ユーザーになっていたため、sudoが上手く動作しないという問題でした。

以下からが問題の解説です。

続きを読む

 /
カテゴリー

問題文

村で様々なトラブルを解決したあなた達の評判を知り、トラブルを抱えているエルフの長の妻から依頼が来た。

長の妻「わざわざ来てもらってありがとう。今、娘の勉強用に新たな魔法を試してみているんだけど、何故か失敗しちゃうの。実験のときには動いていたんだけど……お願いできるかしら?」

エイト「この魔法っていうのはPHPのプログラムのことみたいね。長の奥様の頼みなんだからいつも以上に頑張りなさい!」

注意事項

  • プログラムの編集は許可されている。ただし、プログラムで求めた平方根の二乗と真の値が、小数点以下8桁まで一致することを保証しなければならない。
  • プログラムは最適化されている方が望ましい。

達成すべき事項

  • プログラムを正常に動作させ、原因を特定する。

問題内容

サーバのアドレスにアクセスすると、以下のソースコードの Web ページが動作しています。

これは、トップページでフォームに値を入力するとその平方根を計算する PHP のプログラムです。平方根の計算にはニュートン法を使っています。

しかし、このプログラムのままではうまく動作しません。フォームに値を入力すると画面遷移が起こるのですが、ページが真っ白なまま何も出力しません。これが解決すべきトラブルになっています。

解説

メモリが枯渇している

まず、 /etc/php.ini で log_errors = Off になっているため、エラーログが出力されません。これを On にすると /var/log/httpd/error_log でエラーの内容を見ることができます。

PHP Fatal error: Allowed memory size of 33554432 bytes exhausted

このようなエラーが出るはずです。メモリが枯渇して確保できなかったと言っていますね。ここで Allowed memory size というのは、 php.ini で設定する PHP が使用できるメモリ量です。

というわけで、 php.ini を編集して memory_limit を適当に大きな値にしてやれば問題は解決する……のですが、トラブルの本質はここではありません。確かにそれで動作はするのですが、これではトラブルの原因を特定したことにはなっていません。

循環参照が起きている

では、なぜメモリの枯渇が起こるのでしょうか。その答えはソースコードにあります。 result.php を読んでください。これは、繰り返し計算の途中の値を画面に出力するための Result クラスを定義しているファイルです。

result.php の10行目を見ると、$this->val = $this; という部分があります。これはコンストラクタの中に書かれているので、 output.php の22行目で実行されます。ソースコードを読めばわかるように、これはプログラムの動作にとって論理的にはなんの意味もありません。うっかりミスで残ってしまった書き損じ(という設定)です。

論理的には意味がないこの文ですが、実はメモリ枯渇の原因になっています。というのは、ここで循環参照が発生してしまっているからです。循環参照とは、オブジェクトからオブジェクトへの参照を辿っていくと元のオブジェクトに戻ってしまうような状態です。オブジェクトが自分自身を参照している時や、複数のオブジェクトが相互に参照し合っている時に発生します。このプログラムでは Result クラスの val フィールドに $this が入ることでオブジェクトが自分自身を参照するので、循環参照になっています。

循環参照によってメモリリークが発生し、メモリの枯渇が起こってしまうプログラミング言語もあります。今回のトラブルで用いられている PHP 5.2 もそんな言語の一つです。よって result.php の10行目を削除するだけで問題は解決します。

参照カウント法では循環参照しているオブジェクトを回収できない

Ruby や Python をはじめとして多くのプログラミング言語にはガベージコレクション(GC)の機能がついています。 GC とは、いらなくなったメモリを自動的に解放する仕組みです。その手法はいくつかありますが、 PHP 5.2 には「参照カウント法」というアルゴリズムのみが実装されています。

参照カウント法では、全てのオブジェクトについて、それを参照するオブジェクトの数を数えメモリのどこかに保存しておきます。このカウントが 0 になった時、そのオブジェクトの使用していたメモリを解放するというアルゴリズムです。つまり C++ でいう shared_ptr にあたります。

参照カウント法は単純で実装しやすい手法なのですが、循環参照を起こしているオブジェクトのメモリを回収できないという欠点があります。そのオブジェクトのメモリが解放されない限りは、そのオブジェクトへの参照の数が 0 にならないからです。

PHP 5.3 以降ではこの循環参照に対する対策として、別の GC 手法を実装しています。したがってこのトラブルは PHP をアップデートするだけでも解決します。

ループによってメモリリークが蓄積する

今回、メモリの枯渇を発生させたかったので、プログラムは少々無理のあるものとなっています。ニュートン法で平方根を求めるプログラムですが、ループの回数が100000回と異常に多いです。さらに、10000回に1回しか途中経過を出力しないのに、毎ループで Result オブジェクトを作成しています。 Result オブジェクトは循環参照を起こしているので、ループの次の繰り返しで $result 変数の中身が置き換わってもメモリが回収されません。これによってメモリリークが蓄積し、メモリが枯渇します。

ループ回数を減らせばメモリが枯渇するほどはメモリリークが起こらなくなります。ニュートン法は収束が速いので、小数点以下8桁までなら10回程度のループで十分です。あるいは while ループにしても良いでしょう。

解答

ここまでをまとめると、解答は以下のようになります。

  • 循環参照の起こる文を削除する
  • 循環参照によるメモリリークを指摘する

加えて、ループの回数を減らしてプログラムの動作を速くすれば得点が追加されます。

参考

PHP: ガベージコレクション

講評

永遠の国 第二のトラブルを解けたチームが uecmma だけであったため、解答は一つしかきませんでした。 uecmma の解答は満点の出来でした。また、プログラムの最適化をかなり頑張っていくれていました。

ただ欲を言えば、この問題が PHP 5.2 だけで発生するということを指摘してしてもらえると嬉しかったです。

トラブルシューティングコンテストでプログラミング言語を主題とした問題を出すのは場違いな感じがあります。しかし、メモリリークとその解決というのはトラブルとして面白いかなと思い出題しました。

 /
カテゴリー

こんにちは。ICTSC8にて問題リーダーを務めました、中西です。

ICTSC8に参加して頂いた皆さま、本当にありがとうございました。
競技中、一部の問題が回答できない状態、及び、問題出題などに利用していたコンテストサイトにアクセスできない状況が発生しました。
ご迷惑をおかけして申し訳ありませんでした。

本エントリでは、この事象が発生した原因、及び解決に至った流れを紹介させていただきます。

続きを読む

最近のコメント