/
カテゴリー

ICTSC8参加者の皆様、二日間お疲れ様でした。

大阪工業大学3年の矢田一樹です。

この記事では私が担当した、「研究の国 第二のトラブル」を解説します。

コア技術:OSPF,VyOS,GREトンネル

問題文

トラブルを解決し、女の子との距離が縮まった。

女の子「ありがと~ さっきは助かったわ。私は、B組のパトリシア・トライよ。パトリシアって呼んでね? ところであなたたちはどこのクラスの人なの?」

エイト「実は私たちここの学校の生徒じゃないの。学校がどんなところか知りたくてきたのよ」

パトリシア「そうなんだ……お礼と言ってはなんだけど、学校を案内しようか?」

エイト「わーい! ありがと~」

パトリシア「あっ忘れてた! 魔法陣学入門の課題をやらなくちゃ。OSPFを動かしたいんだけど……」

エイト「え〜! 早く学校を見て回りたいのに〜! あんたたち、なんとかしてあげて!」

トポロジ図

  • 各ルーター(R1~R5)はVyOSを使っています。

 

今回のテーマ

  • VyOSでは設定しても、virtual-linkのneighborの関係しか張れずExchange状態で止まっていることに気づく。
  • 代替策としては、静的ルートかGREトンネルのどちらかですが、GREトンネルを使って、動的にルートを周す方がスマートです。

 

原因と解決方法

原因

  • Cisco機器の場合は、virtual-linkを張った際は正常に働きます。
  • ですが、VyOSの場合はneighborの関係を作った後にルート交換をしてくれません。

解決方法

  • 方法としては、2つあります。
  • 静的ルートで各ルーターの足りないルートに合わせて設定する。
  • virtual-linkの代わりに、GREトンネルを使うことで疑似的に全てのエリアがバックボーンエリアに繋がるようにする。
  • GREトンネルを使った具体的な設定は以下のようになります。

R2

delete protocol ospf area 1 virtual-link 4.4.4.4
set interface tunnel tun0 address 192.168.9以外の数.x/x(ここのアドレスは自由)
set inter tun tun0 encapsulation gre
set inter tun tun0 local-ip 192.168.9.68
set inter tun tun0 remote-ip 192.168.9.131
set proto ospf area 0 network 192.168.9以外の数.x/x(上記のアドレスに沿ったネットワークアドレス)

R4

delete prot ospf area 1 virtual-link 2.2.2.2
set inter tun tun0 address 192.168.x.x/x(R2のトンネルのアドレスと同じネットワークの範囲)
set inter tun tun0 encapsulation gre
set inter tun tun0 local-ip 192.168.9.131
set inter tun tun0 remote-ip 192.168.9.68
set proto ospf area 0 network 192.168.9以外の数.x/x(上記のアドレスに沿ったネットワークアドレス)

採点基準

  • R1からR5にpingが出来ている(60%)
  • 各ルータに動的 にルートが回っている(60%+40%)
  • 各ルータに静的にルートが回っている(60%+10%)

報告書にtracerouteによるルーティングテーブルの確認とR1->R5のpingの結果で判断します。

講評

  • virtual-linkをGREトンネルで代替することはVyOSでも出来ることを知ってもらえると嬉しいです。
  • 是非、ネットワークの勉強にVyOSを使ってみてください。
 /
カテゴリー

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

この問題はdockerのimageをpullする時にバージョンを指定しないことによるバージョントラブル、及びdocker構築の際のトラブルとなっております。

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

続きを読む

 /
カテゴリー

問題文

一行はギルドの依頼で、サーバーを構築しているホビットカンパニーを訪れた。

エイト「さすがにカンパニーっていうだけあって、ホビットの国でも建物は大きいわね。とりあえず入りましょ。社長が待っているわ」

最上階の社長室に入ると、少しふくよかな体型をしたホビットが待ち構えていた。

ホビット社長「やーよく来てくれた。 現在とあるトラブルがカンパニー内で起きている。それを解決して欲しいんだ」

エイト「あんたたちにかかれば簡単な話よね?」

ホビット社長「実は、サーバーが一台重くて全く動かないんだ。原因もわかっていなくてな。お願い出来るかな?」

達成すべき事項

benchサーバにあるbenchmarkerコマンドが正常終了する。

問題内容

benchサーバとserverサーバが存在しており、serverにはApacheとheavenと呼ばれるアプリケーションが動いていました。

このheavenというのは、golang製のHTTPサーバです。やってきたHTTPリクエストに対して、10秒待機した後にリクエストを返答するお行儀の悪いアプリケーションです。WordPressやGitLabなどのバックエンドアプリケーションで処理に時間がかかっている現象を模倣しています。

「達成すべき事項」で触れられている benchmarker コマンドというのは、golang製のHTTPベンチマーカでした。server上にて動作しているApacheに対して、高速にHTTPリクエストを送信します。

benchmarkerコマンドで発行された多くのHTTPリクエストに対して、Apacheが非常に多くのコネクションを持ってしまい、捌ききれなくなってしまう現象が発生していまう、というのが今回発生していたトラブルでした。

回答例

サーバのリソースには余裕があるため、Apacheのチューニングを行い、捌くことができるコネクションの数を増やします。
具体的には、以下の値を apache2.conf など読み込まれる部分に入力します。

ServerLimit         100
StartServers         100
MaxRequestWorkers         3000
MinSpareThreads     25
MaxSpareThreads     75
ThreadsPerChild     25
MaxRequestsPerChild  3000

この値は一例であり、実際にbenchmarkerコマンドを用いて解決出来ていれば問題無い、という判断でした。

講評

今回のトラブルが発生している際に、Apacheのエラーログには下記のような出力がありました。

[mpm_prefork:error] [pid 14998] AH00161: server reached MaxRequestWorkers setting, consider raising the MaxRequestWorkers setting

エラーログに対処方法がそのまま出力されており、比較的容易に解ける問題として出題しました。

結果としては8割ほどのチームが基準点を超える解答を提出しており、比較的狙い通りになったのではないかと考えています。

おわりに

Apacheなどのミドルウェアのトラブルシューティングには出力されるログが非常に重要です。
毎回ログを読む問題が出題されていますが、それぐらい重要な事項となりますので、是非ログを読む力を鍛えてもらえればと思います。

また、使用したソースコードは以下で公開されています。

https://github.com/whywaita/sleep-princess

もしbenchmarkerコマンドの実行に失敗した場合にはsugyan/termburnによって炎が出たかと思いますが、正しく動いていたなら幸いです。

 /

問題文

一行は妖精を研究している学者のところへやってきた。長年研究している学者でさえも、妖精についてはまだわからないことが多いらしい。学者が持つ貴重な妖精の文字や、書物に残る記録を見せてもらうことができた。

学者「そうだ、あなた方は凄腕のトラブルシューターと聞きました。是非あなた方にお願いしたいことがあります」

エイト「色々教えてもらったし、もちろん良いわよ!」

妖精のことを話してもらったお礼として、依頼を引き受けることにした。

学者「試しに妖精の国の言葉を使ってサーバのアドレスを設定してみたのですが、アクセスできないんです。DNSサーバに書き込む呪文をどこか間違えたと思うのですが……調べてみてくれませんか」

アクセスできるサーバ

| ServerName | Hostname   | Address       | User  | Password   | Note       |
| ---------- | ---------- | ------------- | ----- | ---------- | ---------- |
| nsd-master | ns1.2.fy   | 192.168.22.53 | admin | ByeByeBind | DNS master |
| nsd-slave  | ns2.2.fy   | 192.168.22.54 | admin | ByeByeBind | DNS slave  |
| cache      | cache.2.fy | 192.168.22.70 | admin | ByeByeBind | DNS cache  |

Webサーバ一覧

| ドメイン名          | IPアドレス    |
| ------------------- | ------------- |
| χητηολλψ.fy | 192.168.22.81 |
| ιτηεα.fy       | 192.168.22.82 |
| νεπηρεν.fy   | 192.168.22.83 |
| ρηαντολκ.fy | 192.168.22.84 |
| νοπητ.fy       | 192.168.22.85 |
| τιατ.fy         | 192.168.22.86 |

注意事項

セキュリティ周りの設定を無効化せずに解決すること。ただし、トラブルシューティングの間、検証目的での無効化は行っても良い。

達成すべき事項

192.168.22.70 をリゾルバに設定したPCからドメインを引き、ブラウザ上でそのドメイン名が書いてあるページを開くことができる。

解説

Punycode問題です。

国際化ドメイン名をPunycodeに変換していないままレコードを登録したため、レコードを引けないという状態になっています。
解決するには各ドメイン名をPunycodeに置き換える必要があります。

変換方法はlibidnなどのパッケージに含まれるidnコマンドを使用する方法もありますが、Punycodeでググると変換を行ってくれるWebサイトが引っかかるので、そちらで変換しても問題ありません。

変換を行うと以下のようになります。

χητηολλψ.fy → xn--sxaamas2ato.fy
ιτηεα.fy → xn--mxahfh9c.fy
νεπηρεν.fy → xn--qxaafwdpi.fy
ρηαντολκ.fy → xn--mxalkdjmk1a.fy
νοπητ.fy → xn--sxalgev.fy
τιατ.fy → xn--mxap6ac.fy

後はこれに合わせてzoneファイルを書き換えればいいです。
また、Slaveにも変更を適応させるため、SOAレコードのインクリメントも行います。

最後にDNSSECの再署名を行います。
鍵ファイルは/etc/nsd/内に、Kfy.+007+40373といった名前で二種類置いてありましたが、ファイルの中身を見ればZSK、KSKのどちらの鍵ファイルか分かるようになっていました。

鍵ファイルの中身はこのようになっています。(当日の問題で使用されていたファイル名と内容とは若干違いがあります)
(zsk)(ksk) という記載があり、ここで判別できます。

$ cat Kexample.com.+007+15443.key
example.com. IN DNSKEY 256 3 7 AwEAAdPhQCgp0125MKKcYGwQMjUg9H12gk70eZDoLHDYYR25nEQ5rTY296E9+9sl91Q6QmbAz5XA9lWwB+oJYGU1+DZA6S3c4ZxAz8ib1yuiWOmKCGiT+xIunULcMEMKP05eDddOf+6kouxazSFMmRjlB4CwWfxWnWGG1aevwOuMoK3H ;{id = 15443 (zsk), size = 1024b}

$ cat Kexample.com.+007+12753.key
example.com. IN DNSKEY 257 3 7 AwEAAdvhV55tAUr/CgnxSGw+Zfaj+OxxKiUskreYqrImF4YIHCpAGxBQgisC1MsaAxXz6gY8IZdtnOdf7+XOo2If4H1wnvwAIBuf7/Jw2z2qVAso6u1ok4xGDcUxA1WAnmqFWAGyEEEAQITnqT2gGN5TBN/UeM4WagcC8efuYXZJRm81oMhCg8jS/0U62VEu0HZb3fjauBVXBV7wug02SlohwVe2+JrdY9U59O5FdxOeGU1WWYYwpSCOnYUAG6ijWIv2KjPfK4o0B+Mn+jECwk9pvrHg7HwnP7cwNidWqRLzO49KklakhcwSrjMEoPYcsfZ7O/j/RxBKqv4NqsuanMoDxGE= ;{id = 12753 (ksk), size = 2048b}

署名を行うコマンドは以下のとおりです。
署名を行うと、 fy.zone.signed ファイルが再生成されます。

sudo ldns-signzone fy.zone $ZSK $KSK

ちなみに、解答してくれたチームはどのチームもPunycodeへの変換部分までは解答してくれていましたが、DNSSECの再署名まで行っているチームは2チームだけでした。

 /

問題文

旅を続ける一行は、通りかかった小さな村に一夜の宿を借りることにした。一軒一軒民家を回っていたが、泊めてもらえるどころか人の姿さえ見当たらなかった。
半ば諦めながら最後の民家の戸を叩くと、赤い帽子を被った男が出てきた。

男は快く一行を受け入れてくれた。家の中で男にこれまでの冒険を話すと、かなり興味を持ったようだった。

男「色々な国でトラブルを解決してきたようだな。それなら、君たちの実力を見せてほしい」

男はそういって銀色の平たい箱を取り出した。

エイト「それは?」

男「これは俺が昔遊んでたサーバさ。CentOSが大好きでね。ちょうどいい、webサーバを構築して見せてくれないか」

エイト「セントオーエス…遷都を応援してるのかしら?」

サーバへのアクセス情報

  • サーバ名: centos
  • アドレス: centos.1.fy
  • ユーザー名: centos
  • パスワード: CentOSL0ve

達成すべき事項

  • Apache をインストールする。
  • hello world! と書かれたファイルを用意し、hello world! をブラウザで表示させる。

解説

この問題文を要約すると、「CentOSが大好きな赤い帽子を被った男に、昔遊んでいたサーバーにWebサーバーを構築してくれと腕試しをされた。」という問題です。

この問題はトラブルシュートというより、おまけの知識問題となっています。

おそらくApacheのインストールを行おうと yum コマンドを叩くとエラーが返ってきたと思います。

そこでおもむろに cat /proc/version を叩くと以下の内容が返ってきます。

Linux version 4.13.3-1-ARCH (builduser@tobias) (gcc version 7.2.0 (GCC)) #1 SMP PREEMPT Thu Sep 21 20:33:16 CEST 2017

そうです、実はこのサーバーのOS、CentOSではなくArchLinuxだったのです。
問題文を見ると、CentOSが大好きと言ってはいますが、サーバーのOSがCentOSだとは言ってないですね。

男「これは俺が昔遊んでたサーバさ。CentOSが大好きでね。ちょうどいい、webサーバを構築して見せてくれないか」

サーバ(CentOSとは言ってない) というのに気づければokです。

ArchLinuxでは pacman をパッケージマネージャとして利用しているので、以下のコマンドを使用することでインストールすることが出来ます。

$ pacman -Syyu apache

また、ArchLinuxではsystemdをinitとして使用しているので、systemctlを使用してサービスを起動します。

$ systemctl start httpd
$ systemctl enable httpd

hello world! ページですが、 httpd.conf から DocumentRoot を探せばindex.htmlを置く場所が分かります。
今回は /srv/http ですので、そこに index.html を置けば完成です。

$ grep DocumentRoot /etc/httpd/conf/httpd.conf
# DocumentRoot: The directory out of which you will serve your
DocumentRoot "/srv/http"
    # access content that does not live under the DocumentRoot.

$ sudo sh -c "echo 'hello world!' > /srv/http/index.html"
 /

問題文

ホビットカンパニーの社長からの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に参加して頂いた皆さま、本当にありがとうございました。
競技中、一部の問題が回答できない状態、及び、問題出題などに利用していたコンテストサイトにアクセスできない状況が発生しました。
ご迷惑をおかけして申し訳ありませんでした。

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

続きを読む

最近のコメント