俺たちのセキュリティはこれからだ!雰囲気セキュリティ勉強会#3 (https://4tmosphere-sec.connpass.com/event/238394/) に LT 枠として参加した。今まで参加したことのないような勉強会に名前に惹かれただけで申し込んだ状況だったけれど、あまり怖い雰囲気でもなくて助かった。
ということで使った資料をアップロード。どうやら SlideShare とか Speaker Deck を利用するのがスタンダードなようだけど、アカウント作るのも面倒だしここで。
俺たちのセキュリティはこれからだ!雰囲気セキュリティ勉強会#3 (https://4tmosphere-sec.connpass.com/event/238394/) に LT 枠として参加した。今まで参加したことのないような勉強会に名前に惹かれただけで申し込んだ状況だったけれど、あまり怖い雰囲気でもなくて助かった。
ということで使った資料をアップロード。どうやら SlideShare とか Speaker Deck を利用するのがスタンダードなようだけど、アカウント作るのも面倒だしここで。
『コンピュータシステムの理論と実装』に取り組むなかで、Jack という高級言語のコンパイラを Haskell で書いた。該当する章は 10 章と 11 章。このなかで、自分で作ったモナドをあとから mtl スタイルのトランスフォーマーに書き換えるという作業を行った。おかげでモナドおよびトランスフォーマーのイメージを少しつかむことができた気がする。
まず 10 章で構文解析を行い、次の 11 章でコード生成という流れでプログラムを作成した。10 章では純粋に Jack の構文を解析するために、以下のような構成になった。
tokenize :: Text -> [Token]
parse :: [Token] -> Text
本からのサンプルそのままだけど、以下のような入力が与えられたとき:
class Bar {
method Fraction foo(int y) {
var int temp; // a variable
}
}
以下のような XML を出力するのが 10 章の内容。
<class>
<keyword>class</keyword>
<identifier>Bar</identifier>
<symbol>{</symbol>
<subroutineDec>
<keyword>method</keyword>
<identifier>Fraction</identifier>
<identifier>foo</identifier>
<symbol>(</symbol>
<parameterList>
<keyword>int</keyword>
<identifier>y</identifier>
</parameterList>
<symbol>)</symbol>
<subroutineBody>
<symbol>{</symbol>
<varDec>
<keyword>var</keyword>
<keyword>int</keyword>
<identifier>temp</identifier>
<symbol>;</symbol>
</varDec>
...
ここで 2 番目のパーサ、[Token]
をパースするために使えるパーサライブラリが見つからなかったので自分で作ることにした。おそらく自分のレベルだと、適当なライブラリが見つからなかったというのは以下のいずれかを示しているのだと思う。
とはいえ、自分で作ることは理解の最高の方法であるということで、今回はパーサ作りに挑戦した。自分で作ると言っても山本氏のブログ記事 (https://kazu-yamamoto.hatenablog.jp/entry/20080920/1221881130) を写しただけのものである。
import Control.Applicative
newtype Parser s a = Parser { parse :: [s] -> [(a, [s])] }
item :: Parser s s
item = Parser $ \ss -> case ss of
[] -> []
(s:ss') -> [(s, ss')]
instance Functor (Parser s) where
-- fmap :: (a -> b) -> f a -> f b
fmap f p = Parser $ \ss -> [(f a, ss') | (a, ss') <- parse p ss ]
instance Applicative (Parser s) where
-- pure :: a -> f a
pure a = Parser $ \ss -> [(a, ss)]
-- (<*>) :: f (a -> b) -> f a -> f b
f <*> p = Parser $ \ss ->
[ (f' a, ss'') | (f', ss') <- parse f ss
, (a, ss'') <- parse p ss'
]
instance Monad (Parser s) where
-- (>>=) :: forall a b. m a -> (a -> m b) -> m b
p >>= q = Parser $ \ss ->
concat [parse (q a) ss' | (a, ss') <- parse p ss]
これと Alternative の実装くらいで 10 章のパーサに必要な機能は実装することができた。余談だけど、これを自分で書くことでようやくモナドのイメージをつかむことができた気がする。あと「リストは非決定性計算を表す」というのも。
ここからが本題。11 章ではコードを生成するにあたり、パーサに追加の機能が必要になってくる。たとえば以下のようなもの。
これはもう明らかに State だ Reader だ、となるのだけれど、この Parser はすでにモナドだから合成しないといけない。ということでこちらもよくわかってなかったトランスフォーマー化に取り組んだ。実際に取り組んだときには主に StateT の実装を参考にした: https://hackage.haskell.org/package/transformers-0.6.0.2/docs/src/Control.Monad.Trans.State.Strict.html
まずはトランスフォーマー対応版として ParserT を定義する。
newtype ParserT s m a = ParserT { parseT :: [s] -> m [(a, [s])] }
意味合いとしては前の Parser のと違いはもちろん m
の部分で、「ある他のモナド m
の文脈において使用可能な Parser」ということになると思う。ParserT におけるアクションは、型が示すとおりに m [(a, [s])]
を返す関数を ParserT
で包んでやれば良いはず。以下はリストの最初の要素を取る item
の実装。
item :: (Applicative m) => ParserT s m s
item = ParserT $ \ss -> case ss of
[] -> pure []
(s:ss') -> pure [(s, ss')]
ParserT
の中で使用している pure
は m
としての pure
である。
これをモナドにしていく。まずは Functor のインスタンス実装。
instance (Functor m) => Functor (ParserT s m) where
-- fmap :: (a -> b) -> f a -> f b
fmap f m = ParserT $ \ss ->
fmap (map (\(a, ss') -> (f a, ss'))) $ parseT m ss
さて、これを書いたは良いものの意味はまったくわかっていなかった。そもそもどうしてこのコードに辿りついたかというと、StateT からの類推である。StateT では Functor インスタンスが以下のように実装されている。
instance (Functor m) => Functor (StateT s m) where
fmap f m = StateT $ \ s ->
fmap (\ (a, s') -> (f a, s')) $ runStateT m s
runStateT m s
は m (a, s)
, parseT m ss
は m [(a, [s])]
であるから、fmap
に渡している関数を map
すれば型が合うだろう……と試したところ、コンパイラの型チェックが通った。実装しているときは何がなんだかわからないまま次に進んだ。
今振り返ってみるとわかってきた気がする。まず少し書き方を変えて見やすくする。
fmap
の型注釈に出てくる f
は ParserT s m
のこと。なので型宣言をより具体的に書くと (a -> b) -> ParserT s m a -> ParserT s m b
. もしくは (a -> b) -> ([s] -> m [(a, [s])]) -> [s] -> m [(b, [s])]
m
の型は ParserT s m a
. 注釈の型とまぎらわしいので p
に変えるinstance (Functor m) => Functor (ParserT s m) where
-- fmap :: (a -> b) -> ParserT s m a -> ParserT s m b
fmap f p = ParserT $ \ss ->
fmap (map (\(a, ss') -> (f a, ss'))) $ parseT p ss
少しわかりやすくなった気がする。結局のところやろうとしていたことは以前の Parser モナドと同じで、p
を適用して出てきた結果の [(a, ss')]
を [(f a, ss')]
にしようとしている。違いはこれが m
の文脈に入っていることなので、この適用する部分の関数を fmap
で m
の文脈に持ち上げてやる必要があった、ということであった。Parser の実装を以下のように書き直してみたらわかりやすかった。
-- Parser
fmap f p = Parser $ \ss ->
map (\(a, ss') -> (f a, ss')) $ parse p ss
-- ParserT
fmap f p = ParserT $ \ss ->
fmap (map (\(a, ss') -> (f a, ss'))) $ parseT p ss
さて次は Applicative.
import Control.Monad
instance (Functor m, Monad m) => Applicative (ParserT s m) where
-- pure :: a -> ParserT s m a
pure a = ParserT $ \ss -> pure [(a, ss)]
-- (<*>) :: ParserT s m (a -> b) -> Parser s m a -> Parser s m b
f <*> p = ParserT $ \ss -> do
fs <- parseT f ss
fmap concat . forM fs $ \(f', ss') ->
fmap (map (\(a, ss'') -> (f' a, ss''))) $ parseT p ss'
pure
は良いとして、 (<*>)
はもうちょっとなんとかならんのかと自分でも思うくらいわかりづらい。これも StateT を参考に頑張って型を合わせた結果。ひとつずつ見ていくと以下のようになるだろう。
f <*> p = ParserT $ \ss -> do -- m の文脈で
-- f は ParserT s m (a -> b) なので parseT すると m [((a -> b), [s])] を得る
fs <- parseT f ss
-- forM: 上で得たそれぞれの (関数, 残り) に対して実行
-- fmap concat :: m [[(b, [s])]] -> m [(b, [s])]
fmap concat . forM fs $ \(f', ss') ->
-- この部分は fmap と同じ。m [(b, [s])] が返る
fmap (map (\(a, ss'') -> (f' a, ss''))) $ parseT p ss'
fmap
が 2 回出てくるようなところはもう少しすっきりできそうな気がするのだけど、とりあえず動いたので先に進む。
最後に Monad. これは Applicative と似ている。
instance (Monad m) => Monad (ParserT s m) where
-- (>>=) :: forall a b. ParserT s m a -> (a -> ParserT s m b) -> ParserT s m b
p >>= q = ParserT $ \ss -> do
ps <- parseT p ss
fmap concat . forM ps $ \(a, ss') ->
parseT (q a) ss'
これで ParserT をモナドにすることができた。
この時点で、ParserT をもとにした Parser を作っておこう。m
に Identity モナドを使うだけ。
import Control.Monad.Identity
type Parser s a = ParserT s Identity a
parse :: Parser s a -> [s] -> [(a, [s])]
parse p = runIdentity . parseT p
ここまでやると、最初にトランスフォーマー非対応の Parser を使うコードがそのまま動いた! 期待していたことであったが実際コンパイルが通って動いたときはすごい爽快感だった。
さて、実際にこれを他のモナドと合成して使うためには関連する関数をうまく取り扱えるように定義する必要がある。まず lift
を使うために MonadTrans のインスタンスにする。このあたりも StateT を参考にしながら進めた。
import Control.Monad.Trans.Class
instance MonadTrans (ParserT s) where
-- lift :: Monad m => m a -> ParserT s m a
lift act = ParserT $ \ss -> do
a <- act
pure [(a, ss)]
つまり合成対象 m
モナドのアクション act
を、ParserT の文脈で使えるようにするラッパーである。act
から取り出した値 a
を、ParserT の文脈においても <-
で取り出したりできるようにセットしてやる。
おそらく、この段階で transformer スタイルの合成は可能なのではないか (試していないので推測のみ)。transformer スタイルだと明示的に lift
を使用してアクションの持ち上げをするので、MonadTrans のインスタンスになっていれば他のモナドとの合成が可能であるような気がする。対して mtl スタイルではもう少し仕事が必要で、合成対象のモナドのアクションをあらかじめインスタンスとして実装しておくことで、この lift
の手間を省いている、と理解している。
ということでまずは StateT から。MonadState のインスタンスとするのだが、実装はいたって単純。
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE UndecidableInstances #-}
import Control.Monad.State.Strict
instance (MonadState t m) => MonadState t (ParserT s m) where
get = lift get
put = lift . put
state = lift . state
これらの関数は単純に lift
するだけで良いようだ。get
を例に取って見てみる。左辺の get
は ParserT のアクション。右辺の get
が合成対象モナド m
のアクションで、それを lift
で持ち上げることで ParserT のアクションとしている。言語拡張についてはまったく理解していなくて、コンパイラに言われるがまま追加した。Control.Monad.State.Class
でもこれらの拡張が使われているので間違いではないだろう。
次に ReaderT を使えるようにする。
import Control.Monad.Reader
instance (MonadReader r m) => MonadReader r (ParserT s m) where
ask = lift ask
local f p = ParserT $ local f . parseT p
reader = lift . reader
local
が他とは少し違うが、これもやはり他のモナドの実装を参考にした。他の処理と同じように、ParserT の中身、m
の文脈で local
を適用するということ。
これで、ParserT は StateT および ReaderT と合成可能である。以下のように利用できる。
type TokenParser a = ParserT Token (StateT ParseState (Reader Env)) a
compile :: Env -> [Token] -> Text
compile env tokens = fst . head $ -- 雑
runReader (execStateT (parseT parseClass tokens) initialState) env
parseClass :: TokenParser Text
parseClass = ...
これで 11 章で必要なシンボルテーンブル等の状態やその他パラメータを TokenParser 内で使えるようになった。めでたし。
StateT を例にとると、今回作ったのは ParserT s (StateT t Identity) a
という形の合成モナドである。これは StateT t (ParserT s Identity) a
とは違う。モナドの入れ子の順番は処理の結果に影響して、例えば try
などでバックトラックが発生した時に状態が巻き戻るか否かという違いが出るらしい。なお、後者を実現しようとする場合には StateT に手を入れる必要が出てくる。ParserT を中に入れるための型クラス、たとえば MonadParser と使いたいアクションを定義したうえで、StateT を MonadParser のインスタンスにすることになる。
今回オリジナルの Parser をトランスフォーマー対応の ParserT にするにあたり、型を合わせる程度の自然な修正ではあるものの、それなりに多くの箇所に手を入れる必要があった。なので、もともとトランスフォーマーに対応していないモナド (例: attoparsec) を他のモナド (例: State) と合成して使う、というのは骨の折れる作業になると思った。
前の PC の具合が悪くなった等で新しい環境が AArch64 Gentoo になった。新しい環境でも Haskell および Stack を使いたいけれど、記事作成時点では AMD64 のようには整っていなかったのである程度自前でやった。そのときのメモ。
GHC には AArch64 Debian のバイナリディストリビューションがあって、Gentoo でのそのまま動くのだけれど、libtinfo 絡みのなにかの警告メッセージがうるさいので自前で GHC をビルドする。
まずは普通に GHC と Cabal をインストール。GHC のバージョンは 8.10.7, インストール先は ~/.cabal
とした。Cabal でインストールしたコードを含めてあとでまとめて消せるため。ダウンロード元と手順:
$ tar xf ghc-8.10.7-aarch64-deb10-linux.tar.xz
$ cd ghc-8.10.7
$ ./configure --prefix=$HOME/.cabal
$ make install
$ tar xf cabal-install-3.6.0.0-aarch64-linux-deb10.tar.xz -C $HOME/.cabal/bin
$ export PATH=$HOME/.cabal/bin:$PATH
GHC は何のひねりもなくビルドできた。普通の Gentoo インストールから追加で sys-process/numactl を emerge する必要があった程度。以下では C コンパイラに Clang を使っているが、GCC でも問題ない。今回この環境では Clang を使っているので合わせただけ。
$ rm -rf ghc-8.10.7 # 前のバイナリディストリビューション
$ tar xf ghc-8.10.7-src.tar.xz
$ cd ghc-8.10.7
$ CC=clang ./configure
$ make -j4
$ make binary-dist
ここでできあがった GHC が今後 Stack で使うことになるもの。ghc-8.10.7-aarch64-unknown-linux.tar.xz
を適当なディレクトリ (自分は ~/ghc
にした) に置いておく。
Stack は記事作成時点では AArch64 のビルドが提供されていないので、自前でコンパイルする必要がある。ただ、既に GHC/Cabal があるのでそれで問題なくできる。一点だけ、Pantry モジュールのバージョンを指定する必要があった (https://github.com/commercialhaskell/pantry/issues/43)。
$ cabal update
$ cabal install --constraint='pantry < 0.5.3' stack
これで ~/.cabal
以下に (暫定の) Stack が入る。早速使ってみようとするとコンパイラが見つからないというエラーになる。
$ stack setup
Writing implicit global project config file to: /home/dr/.stack/global-project/stack.yaml
Note: You can change the snapshot via the resolver field there.
Using latest snapshot resolver: lts-18.19
Unable to find installation URLs for OS key: linux-aarch64-tinfo6
Stack のみならず適切な GHC のバージョンも提供されていない。ということで先ほど作った GHC を使うように設定する。
# ~/.stack/config.yaml
setup-info:
ghc:
linux-aarch64-tinfo6:
8.10.7:
url: "/home/dr/ghc/ghc-8.10.7-aarch64-unknown-linux.tar.xz"
ここまで来ればもう使える。まずは Stack を。
$ stack --resolver lts-18.19 setup
$ stack install stack
これで ~/.local/bin
に Stack が入る。~/.cabal
への依存はもうないので丸ごと消しても良し。普通の使用感で Stack が使える。バージョンを増やしたいときにはそれぞれの GHC バージョンをビルドして binary-dist を ~/.stack/config.yaml
から参照すれば ok.
RISC-V の VM イメージを作って、QEMU で動かしてみた。特にそれを使って何かをしようというわけではないけれど、『RISC-V 原典』を読み進められなかった (2 回目) 腹いせにやってみた。
そんなに大げさなことをやるわけではなく、既に RISC-V 用の stage 3 を作っている方々がおられる (https://wiki.gentoo.org/wiki/Project:RISC-V) ので、ありがたくそれを使ってインストールするのみである。ステップとしては以下のようになる。
環境は以下のとおり。
RISC-V stage 3 は 2021 年 1 月現在 RV64GC/lp64d, RV64IMAC/lp64 の 2 種類の命令セット (拡張)/ABI で用意されている。RV64GC が汎用 OS 向けのようなので、RV64GC/lp64d (OpenRC) の環境を作ることにする。
今回作業するにあたり、とても Debian に頼っている。Gentoo 固有でない部分は Debian のガイド (https://wiki.debian.org/RISC-V) をベースにしているし、あとブートローダの部分を自分でうまく構築できなかったので、Debian の U-Boot バイナリを流用している。
Gentoo Wiki の記事 (https://wiki.gentoo.org/wiki/Embedded_Handbook/General/Compiling_with_qemu_user_chroot) を参照しながら RISC-V chroot 環境を作る。
chroot 環境で構築している時はユーザエミュレーション、仮想マシンとしてブートするときにはシステムエミュレーションということで、双方で RV64 エミュレータを作っておく必要がある。勢いで対応しているアーキテクチャは全部有効にした。
# /etc/portage.use/gentoo
app-emulation/qemu static-user QEMU_SOFTMMU_TARGETS: * QEMU_USER_TARGETS: *
emerge. これで RISC-V ELF バイナリを実行できるようになるが、このあとの手順のために、qemu-riscv64
コマンドを指定せずとも透過的に実行できるように (RV64 用の) binfmt_misc の設定をしておく。
# echo ':riscv64:M::\x7f\x45\x4c\x46\x02\x01\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02\x00\xf3\x00:\xff\xff\xff\xff\xff\xff\xff\x00\xff\xff\xff\xff\xff\xff\xff\xff\xfe\xff\xff\xff:/usr/bin/qemu-riscv64:' > /proc/sys/fs/binfmt_misc/register
# rc-service qemu-binfmt start
/mnt/gentoo
に stage 3 を展開。chroot 後に RISC-V ELF バイナリを実行するためには、qemu-riscv64
が chroot 環境内で実行できる必要がある。Gentoo Wiki の記事では chroot 環境にもういちど app-emulation/qemu を emerge する手順が書かれているが、どうせ user target は static でコンパイルしてるのだしということで直接 /usr/bin/qemu-riscv64
を chroot 環境にコピーした。
# mkdir /mnt/gentoo
# cd /mnt/gentoo
# wget https://dev.gentoo.org/~dilfridge/stages/stage3-rv64_lp64d-20210109T142246Z.tar.xz # 記事作成時点
# tar xpvf stage3-*.tar.xz --xattrs-include='*.*' --numeric-owner
# cp -a /usr/bin/qemu-riscv64 /mnt/gentoo/usr/bin
これで、AMD64 の Handbook でも見ながら chroot すれば RISC-V 環境ということになる。
# chroot /mnt/gentoo /bin/bash
(chroot) # file /bin/uname
/bin/uname: ELF 64-bit LSB pie executable, UCB RISC-V, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux-riscv64-lp64d.so.1, for GNU/Linux 4.15.0, stripped
(chroot) # uname -a
Linux x1e 5.4.80-gentoo-r1 #1 SMP Sun Jan 3 19:36:07 JST 2021 riscv64 GNU/Linux
Handbook (AMD64) を見ながら粛々とインストールを進める。カーネルオプションはデフォルトのままにした。ところで、異なるアークテクチャをエミュレートしているので当然だけれど非常に遅い。カーネルのコンパイルにはこれくらい時間がかかかった (Intel(R) Core(TM) i7-8850H CPU @ 2.60GHz)。
# time make -j6
...
Kernel: arch/riscv/boot/Image.gz is ready
real 51m57.461s
user 299m57.397s
sys 7m7.268s
ほとんど他アーキテクチャと手順は変わらなくて、今回気をつけるのはブートローダ以外はシリアルコンソール (ttyS0
) を開けておくことくらい。普通の TTY および GUI は使えるのかよくわらかないし、自分の場合は使う予定もない。
# /etc/inittab
# SERIAL CONSOLES
s0:12345:respawn:/sbin/agetty -L 9600 ttyS0 vt100
#s1:12345:respawn:/sbin/agetty -L 9600 ttyS1 vt100
ブートローダは、うまく自分で構築することができなかった。選択肢としてはいくつかあって U-Boot がメインの模様。ただ、どうもうまく U-Boot にうまくカーネルを選ばせることができなかった。仕方なしに、Debain の u-boot-qemu パッケージ (https://packages.debian.org/sid/u-boot-qemu) のバイナリをそのまま使うことにした。どうして動くのかよくわからないのだけど、QEMU 実行時にこの U-Boot バイナリを指定すると、/boot/extlinux/extlinux.conf
にもとづいてカーネルを読み込んでくれる。ということで以下が chroot 環境内に作成したファイル。
# /boot/extlinux/extlinux.conf
default 10
menu title U-Boot menu
prompt 0
timeout 50
label 10
menu label Gentoo Linux
linux /boot/vmlinuz-5.10.2-gentoo
append ro root=/dev/vda1
label 10r
menu label Gentoo Linux (recovery mode)
linux /boot/vmlinuz-5.10.2-gentoo
append ro root=/dev/vda1 single
ここまでやって、chroot 環境から抜ける。
virt-make-fs
コマンド (app-emulation/libguestfs) で chroot ディレクトリをディスクイメージにまとめる。今回なぜか環境変数を手動で渡す必要があった。
$ sudo LIBGUESTFS_PATH=/usr/share/guestfs/appliance/ virt-make-fs --format=qcow2 --partition=gpt --type=ext4 --size=40G /mnt/gentoo/ gentoo-riscv64.qcow2
いよいよ VM を実行。前述のとおりブートローダに Debian の u-boot-qemu の U-Boot バイナリを使っている。-kernel
パラメータに u-boot.elf (./usr/lib/u-boot/qemu-riscv64_smode/uboot.elf)
を指定する。
$ qemu-system-riscv64 -nographic -machine virt -m 2G \
-kernel uboot.elf \
-object rng-random,filename=/dev/urandom,id=rng0 -device virtio-rng-device,rng=rng0 \
-device virtio-blk-device,drive=hd0 -drive file=gentoo-rscv64.qcow2,format=qcow2,id=hd0 \
-device virtio-net-device,netdev=usernet -netdev user,id=usernet
ログインプロンプトが出てきたら嬉しい。最後にクリーンアップ。
# rm /stage3-*.tar.*
# rm /usr/bin/qemu-riscv64
久しぶりに VMware Fusion を使ったときに少しはまったことをメモ。
ホストとのクリップボード共有を動作させるには、app-emulation/open-vm-tools の gtkmm
USE flag を有効にして vmware-user-suid-wrapper
を実行する必要があった。vmware-user-suid-wrapper
は .xinitrc
にでも書いておく。
以下のエラーが出てゲストから外部に SSH できないという問題があった。
$ ssh x.x.x.x
packet_write_wait: Connection to x.x.x.x port 22: Broken pipe
おそらく VMware の NAT 周りの処理の関係で問題が発生しているみたい。これは ssh
に IPQoS=throughput
というオプションを渡してやれば解決した。
$ ssh -o 'IPQoS=throughput' x.x.x.x
~/.ssh/config
に書いておく。
# ~/.ssh/config
Host *
IPQoS=throughput
Blogger (https://blog.drmn.jp/) から移転してきました。記事の移行もそのうちするかも。