2019-11-13

所属判定問題を解くBloomFilter

これは30日チャレンジの15日目（2019/09/23）に書かれた文章です

「ある要素 $a$ が集合 $A$ に含まれているか否かを判定する」問題（以下、所属判定問題）が与えられたとき、どのような実装を考えるだろうか。素朴な方法として「集合 $A$ に含まれる要素を走査して判定する」方法が考えられるが、これは $O(|A|)$ 時間必要なため効率的だとは言えない。本文では所属判定問題に対するひとつの解として、確率的データ構造BloomFilterをみていく。

なお、本文章で説明するBloomFilterをgolangで実装したのでコードと見比べてて読みすすめると理解が捗るかもしれない。

A BloomFilter implementation · GitHub

まずはじめに、確率的データ構造とは一体何を指すのだろうか。

2019-11-12

進化可能なGraphQL Schema設計

これは30日チャレンジの13日目（2019/09/21）に書かれた文章です

GraphQLのスキーマ設計において進化可能なデザインを実践するためにxuorig氏が記事を残している。本文はxuorig氏の記事の要約である。

blog.apollographql.com

GraphQLではAPIクライアント側が必要となるフィールドを明示するため、サーバー側が意図しない（突然フィールドを消すなど）限り、自然と後方互換性を保った開発ができるように設計されている。また、将来的に削除したいフィールドには “Deprecated” の追加情報を与えることもできる。そうすることで、スキーマ定義を通してクライアント側に古いフィールドを使い続けないよう促すことができる。

それでもなお、後方互換性を保ちながら開発を進めていくことは難しい。 xuorig氏の記事では、例を交えながら３つのTipsが提案されている。

2019-11-11

読み書き禁止ファイルを変更できてしまう謎

これは30日チャレンジの9日目（2019/09/17）に書かれた文章です

Linuxで開発したことがあるエンジニアならpasswdコマンドを知っているだろう。コマンド名が示すとおり、ログインパスワードを変更するコマンドだ。

ではパスワードを記したファイルは一体どこにあるのだろうか。これも知ってるエンジニアは多いだろう。 /etc/passwd にはユーザー名、（暗号化された）パスワード、ログインシェルなどログイン時に必要な情報が一行ごとに保存されている。また最近のLinuxディストリビューションでは、もはやパスワードは/etc/passwdに保存せずに/etc/shadowに移すことで安全性を高めているようだ。

無論、上記ファイルが一般ユーザから不要に読み書きされるようなことがあってはならない。パーミッション設定によれば、/etc/passwdと/etc/shadowともにrootのみ読み書きが許され、 /etc/shadowに至っては一般ユーザは読み込みさえ禁止されている。

root@be281876e6b0:/app# ls -al /etc/shadow /etc/passwd
-rw-r--r-- 1 root root   1236 Sep  4  2018 /etc/passwd
-rw-r----- 1 root shadow  652 Sep  4  2018 /etc/shadow

しかしここでひとつ疑問が浮かんでくる。読み込みできないはずの/etc/shadowがどうして一般ユーザが実行したpasswdコマンド(/usr/bin/passwd)によって変更されるのだろうか。

一般に、ユーザが実行したプロセスは実行ユーザの権限をもってファイル読み書きを行う。したがって、例えば読み込み権限のないファイルを表示しようとしても当然エラーが発生する。それにもかかわらずpasswdコマンドで/etc/shadowの書き換えが可能なのだとしたら、なにか全く別の機構が隠れているのかもしれない。

sat0yu@b61abff74dc3:/$ ls -al hoge 
-rw------- 1 root root 0 Sep 17 14:19 hoge 
sat0yu@b61abff74dc3:/$ cat hoge 
cat: hoge: Permission denied

じつはこの隠れた機構こそが、本文を書くに至った今日の学びである。答えから先に記すと、それは「セットユーザID (SUID)」と呼ばれる機構だ。

SUIDは読み/書き/実行と並ぶ特殊なアクセス権である。このアクセス権をもつ実行ファイルは、実行ユーザではなく所有ユーザのアクセス権限で処理を行う。すなわち、まさに我々がpasswdで抱えていた疑問に対する回答となる。

実際にpasswdコマンドのアクセス権限を確認してみると、通常は実行権限「x」が埋まる箇所（passwdコマンドの所有者権限）には代わりに「s」が記されている。

sat0yu@b61abff74dc3:/$ ls -al /usr/bin/passwd 
-rwsr-xr-x 1 root root 59680 May 17 2017 /usr/bin/passwd

SUIDはpasswdコマンドが代表格としてあげられるが、その他にもWebサーバーのような常時稼働する実行形式にも利用されることがある。すなわち「起動時にポート80をListenするにはrootが必要だが、一度起動してしまえば権限を降格しても構わない」といったユースケースにも有用なのだ。

ちなみにSUIDは下記コマンドで設定することができる。あまり頻繁に使うことはないかもしれないが、知識として持っておくと便利だろう。

chmod u+s file

ちなみに、本文を書くきっかけとなった今日の学びは「詳解UNIXプログラミング」から得た。 Webエンジニアとして普段からアプリケーションコードを書いていると、自ずと学びの範囲が狭まってきてしまう。「詳解UNIXプログラミング」のような色褪せない名著は、知識の外縁を広げて新しい学びを得るための格好の材料となるだろう。