エンジニアですよ!

頑張れ俺くん、巨匠と呼ばれるその日まで

facebookの自動テストツールの論文を読んだメモ

Facebook がバグの自動修正ツールを発表したという話があり、 code.fb.com

その紹介記事を見て、 Sapienz のほうは論文が発表されているという話だったので読んでみた。軽く。

バグの自動修正ツールのほうはSapFixというやつで、バグを修正するためにはまずバグを見つけなければいけないが、そのバグを検知するために使われているのがSapienz。

で、SapienzというのはAndroidアプリ向けの自動テストツール。

この論文を書いた一人のMark Harmanという方(とMcMinnさんという方)が2001年にSearch-based software engineering (SBSE) という手法を提案しており(参考: http://a-lifelong-tester.cocolog-nifty.com/publications/STM07_Notes_on_new_software_testing_techniques.pdf)、 曰くSBSEとは、

ソフトウェア工学における各種の課題をヒューリスティックサーチの技法を使って解決を図る

手法であり、

このサーチ技法をテストの分野に適用するのがSearch-based testingと呼ばれる技法

である。そのSearch-based testingの手法をAndroidのテストに応用して成果が出たよんということのようだ.

上で参考にあげた資料に書いてあるようにサーチ技法として用いられるアルゴリズムにはいくつかの種類があるが、Sapienzで用いられているのは Evolutionary Algorigthm (進化的アルゴリズム) である。 また、Androidのテストにおいては、多目的最適化を使ったsearch-based testingの初めてのアプローチだぜ、と言っているし、論文のタイトルからしてMulti-objective Automated Testing for Android Applicationsであるように、多目的最適化問題として扱っている。

進化的アルゴリズムでは、解きたい問題の解を個体として表現する(多分)。

個体の性質は染色体によって決まり、染色体は複数の遺伝子から成る。

そして個体同士で交叉して子を作ったり突然変異したり一部の個体は淘汰されたりして進化をして世代を重ねていくことで、よりいい感じの解を探す。

詳しくや正確にはもちろん他の資料を参考に。

で、Sapienzで具体的にどんな風に問題が表現されているか。

Sapienzで最適化したい問題というのは、

  • より多くの範囲をテストし(coverage)
  • より多くの不具合を(fault revelation)
  • より短い手順で(shorter test sequence)

発見するようなテストを生成したいということ。

この3つを同時に最適化するので、Multi-objectiveな最適化という話。

論文中でも言及されているが、多目的最適化においては一般にパレート最適な解を見つけることが目的になる。 この場合上記の3つの要素についてパレート最適な解を探す。

Sapienzでは、進化的アルゴリズムにおける個体などの表現は下記のようになっている。

  • 個体: テストスイート
  • 染色体:テストケース
  • 遺伝子:なんらかのイベント

で、遺伝子には2種類ある。Atomic genesとMotif genes.

Atomic genesのほうはその名の通りAtomicであってそれ以上分割することのできない単位のイベント。 たとえばなんかのキーを押すとかどこかをタップするとか音量を調節するとかそういうの。

Motif genesのほうはAtomic genesの組み合わせ。

なんで組み合わせを使うのかというと、UIというのは複雑なものなので、状態やその時のコンテクストの知識なしに単純にAtomic genesだけ組み合わせているとちゃんとした動作を組み立てるのが難しいからだそう。まぁそれはそうっぽい感じがする。しかしこの論文の時点では、Motif genesは汎用的なもの1種類しか使っていないようだ。Motif geneをたくさん使うということはそれだけ人間の手がかかるということで、自動化を妨げることになるからということ。

個体や遺伝子についてはそれで、個体を進化させるためのアルゴリズムの話

下記のいずれかを確率的に個体に適用する。

  • 交叉(crossover)
  • 変異(mutation)
  • 繁殖(reproduction)

個体間では一様交叉を行う。個体内では変異するが、変異は少し複雑。

個体はテストケースを複数含むテストスイートなので、まずテストケースの順序をランダムにシャッフルする。このシャッフルは交叉の際の多様性を増すことを目的にしている。シャッフルしたあとに2つの隣合うテストケース同士で, qの確率で1点交叉を行う。 更に、テストケース内のイベントをqの確率でシャッフルする。Atomic eventsにはパラメータがあるので、それを変異させることもできるが、操作を単純にするためにイベントの並び順を変えることにしたようだ。 繁殖は単にランダムに選ばれた個体をそのまま使うらしい。

淘汰(selection)にはNSGA-Ⅱというアルゴリズムを使う。雰囲気しか理解できてない。

個体の評価は、さっきも書いたが下記の組で行われる。

  • カバレッジ
  • テストシーケンスの短さ
  • 発見したクラッシュの多さ

これらが最も望ましいケースと個体との距離で個体がランク付けされ、ランクが良いものが選ばれる。同じランクではより混雑距離が大きいものが選ばれる。混雑距離というのはランク内において隣接する個体への距離の和のこと。より混雑していないもののほうがが多様性を確保することができるため良い。

ここまで読むとなんとなく進化的アルゴリズムを適用してある程度良いものができそうな気がしてくる。むしろ、実際多様なアプリケーションに対してどのようにテストのイベントを生成するのかとかが気になってくるが、そのへんについては特に細かくは触れられてない。多分他にもテストを生成するツールは既にあるのでそこはこの論文にとってはあんまり重要ではないだろう。

ちなみにこのSapienzはDEAPという, python製の進化的アルゴリズムのためのフレームワークを使って構築されていたが、このDEAPはすごく簡単に使えて便利。自分の場合使う予定は特にないけど。NSGA-Ⅱを用いた多目的最適化とかもできる様子。

参考にした資料など

基本的に検索してすぐ出てきたもの

setxkbmapがわからない

xmodmapがもうダメダメなので、 setxkbmap を使うことにした。

しかし、man を読んでも自分で設定する方法がよくわからん…

一応安定のArchLinux wikiで設定方法は載ってるんだが…

Xorg でのキーボード設定 - ArchWiki

XkbOptionsに色々書き足すか、設定ファイルを書き換えるかする方法。

後者はまぁもちろんそれは動くだろう。 /usr/share/X11/xkb以下にxkbで使われるcomponentが用意してある。それを書き換えればまぁ動く。結局わからなかったので最終的にこれで解決した。

前者は、ubuntuだと/etc/default/keyboardのXKBOPTIONSを書き換えてdpkg-reconfiugreすることになる。

これはまぁ動くんだろうけど、問題はoption(というかsymbol)をどうやって自分で定義し、システムに読み込ませるか。

rulesファイルにoptionに関する記述はあり、caps lockを無効にしてctrlとして使うオプションであるctrl:nocapsの定義とかを見て$HOME以下に書いてみたりしたんだけどうーんうまくいかない。

unix.stackexchange.com

-Iでinclude pathを指定する方法でうまくいかないって言ってる人はいるみたい。

ちなみに、 /etc/gdm3/XSession で $HOME/.Xkbdmap が使われるようになっているので、このファイルで -model ctrl:nocaps を指定してみたが効かず。

これは多分、起動後にコマンド叩くのを自動化する系の解決法の場合によく見る sleep 入れないとだめっていう問題のような気がする。わからんけど。

結局何もわからなかった

まぁ こういう方法→Ubuntu 16.04 で XKB を使ってキーマップをカスタマイズする を使えば自分でいくらでも設定をかけるはずだが、なんかなぁ。自分で定義したオプションをさくっと追加してオプションを追加するだけの方法が知りたかった

Brainf*ckのインタープリタとJITコンパイラ

Adventures in JIT compilation: Part 1 - an interpreter - Eli Bendersky's website

Adventures in JIT compilation: Part 2 - an x64 JIT - Eli Bendersky's website

これらの記事を読み、part2まで真似して書いてみた。

brainf*ck jit · GitHub

記事ではC++で書かれているが、自分はC++は全くわからないのでRustで書いた。

まずシンプルなインタープリタを書いて、遅いよねってなって、まずはインタープリタとして徐々に最適化していく。

で、結構速くなったよね、というところで JIT コンパイルしてみる。

そうすると頑張って最適化したインタープリタよりも速いねぇとなり、さらに JIT しつつ最適化もするともっと速くなるよね。となりpart2は終わり。

このあとLLVMをbackendにしてやってみるとかが続くが、まだやってない。

この記事はJIT初心者の練習の題材としてとても良くて、JITといえばなんとなく実行時にコンパイルしてるんだろうな、という程度にしか理解がなく、JITコンパイラを書いてみるとかいうと途端に意味不明になるようなレベルの人ならこれを書いてみるとなるほど、となるところがあるかもしれない。

個人的にはどういうところが良いと感じたかというと、

  • パースしたコードをインタープリタとしてそのまま実行するのではなくて
  • パースした結果を機械語コンパイル
  • 確保しておいた実行可能なメモリ領域に書き込んで
  • そのメモリ領域を実行する

というところを実際にコードを書いて体験できたので理解が進んだ。

ここで書いたのはbrainf*ckであり個々の命令が単純なので全部を変換したが、実際にはまずはインタープリタでブロックの呼び出し回数をトレースしつつ実行し、頻繁に呼び出されるものだけをコンパイルして実行する、とかになるんだろう。

LuaJITとかがまさにそうで、実行回数を数えておいて必要に応じてJITの処理をする。

参考: - LuaJIT 解析 - Non-public jit.* API

むしろ他にどういったものがあるのかとかも興味あるが、まずは雰囲気がわかってきたのでLuaJITとか、最近だとJavaで書かれたGraalとかがあるんでそのへん調べてみたい。

余談だけど機械語を手書きするときは Online x86 and x64 Intel Instruction Assembler がとても便利。 as とか nasm でやってもいいのかもしれないけど、まとまって書くわけでもないときはこれが楽。

Rustで実行可能なメモリを確保

最近JITコンパイラを書いていて、実行可能なメモリ領域に命令列を直接書き込んで実行、ということがしたかった。

cならmmapなどで、PROT_EXECフラグを立ててメモリを確保するか、mprotectでPROT_EXECフラグを立ててやればいいという認識。

まず思いついたのは単純にhttps://crates.io/crates/libcを使う方法で、それは普通に思ったとおりにできて、最終的にそれ以外の方法はわからなかった。

こんなイメージ

Rust Playground

Rust 側で操作ができないと不便なので、 raw pointer として u8 で変数を宣言しておく。

で、別途 mmap でメモリ領域を確保して、 https://doc.rust-lang.org/std/mem/fn.transmute.html で u8 の pointer に coerce する。こうすると u8 を書き込める。

memmove や memcpy 相当の操作として copy_to(nonoverlapping) や copy_from(nonoverlapping) がある。 (cf. pointer - Rust )

https://doc.rust-lang.org/beta/std/primitive.slice.html#method.as_ptrでポインタを取り出して、確保した領域に u8 の配列に書き込んだ命令列をコピーする。

そしてまた transmute を使って命令列を書き込んだメモリ領域を関数ポインタに変換して、関数として呼び出す。 transmute, https://doc.rust-lang.org/nomicon/transmutes.htmlであり、危険で強力。

まぁlibc使うので当然だが、なんとも想定通りな感じ。

で、ちょうど Rust で JIT についての記事であり、メモリを確保して実行するもっとおしゃれでいい感じな方法を書いた記事がこちらにあったので、詳しくはこちら。

Building a simple JIT in Rust

windowsからvirtualboxで別パーティションのubuntuを起動したいけどできない話

やりたいことは、日本語だと

これとか、 Windows 上の VirtualBox で実パーティション上の Linux を起動する:中年の主張:So-netブログ

これとか、 Windons7のVirtualBoxでデュアルブート用のraw partitionにあるLinuxを起動させる | @knok blog

にかかれているようなことで、すでに先人が軽々とやってのけたことをやりたいだけなのである。しかしうまくいかない。

状況としては, windowsから見たとき下記のようなパーティションがあり、

PS C:\Users\takhi> Get-Partition


   DiskPath: \\?\scsi#disk&ven_nvme&prod_samsung_mzvlb1t0#5&2ab59ee0&0&000000#{53f56307-b6bf-11d0-94f2-00a0c91efb8b}

PartitionNumber  DriveLetter Offset                                        Size Type
---------------  ----------- ------                                        ---- ----
1                            1048576                                     260 MB System
2                            273678336                                    16 MB Reserved
3                C           290455552                                522.43 GB Basic
6                            561249255424                             426.37 GB Unknown
5                            1019064877056                              3.81 GB Unknown
4                            1023160614912                              1000 MB Recovery

ちなみにUbuntuからWindowsを起動するのはできてる。これは普通にできた。

しかし、今windowsを使いたいときというのは都合により物理windowsでしか使えない(使っても意味がない)ソフトウェアを使いつつubuntuを使いたいからであり、かつ多くの場合はubuntuをメインで使いたくて必要なときしかwindowsを使うことはないため、VMではなく物理パーティションubuntuを起動したいというわけで、逆ができても意味がない。(わかりにくい)

試したこと

シンプルに createrawvmdk -partitions 5,6

boot media が見つからない。だめ

まぁそりゃそのはずで、 物理では UEFI で起動していてそのシステムパーティションは1なのにそれが含まれていないので、起動できるはずがない。という理解であっているのかはよくわかっていない

createrawvmdk -partitions 5,6 で -mbr を渡す

-mbr オプションで MBR を渡すことができるので、Linux を起動してパーティション1 から

dd if=/dev/nvme0p1n1 of=a.mbr bs=512 count=1

で取得した MBR を渡してみる。

が、だめ。

これもそれはそうで、そもそも正常な MBR ではない。

パーティションテーブルを見ても起動フラグがどのパーティションにも立ってないし、というか「Disk Error…(ry」というメッセージが入っておりもはや MBR の体をなしてない。そんなもの食わせたらエラーになるに決まってる

( UEFIハマりポイント - syuu1228's blog を見るとUEFIブートなので、MBRパーティションテーブルでブートフラグが立っていないのは正しそうである)

createrawvmdk -partitions 1,5,6

UEFI のシステムパーティションを含めてみた形

Virtual Linux envirionments using real partitions for dual boot system にはそのように書いてある

no bootable mediumでだめ

UEFI有効にして起動すると、 required disk isn't connected or cannot access 的なエラーでリカバリー画面になる

createrawvmdk でパーティションを指定しない

安全のためパーティションを指定して起動しようとしていたが、もはやわからないのでパーティションを指定しなければいいのでは?

UEFI は grub2 を起動していて ubuntuwindows かいつも選択して起動しているので、起動画面が出れば ubuntu を指定して起動できるだろう?

と思ったけどもちろん(?)だめ

これもエラーが発生してリカバリが必要です、な画面になる。

同じだけどログ的には書き込みが権限エラーになっている様子。まぁそりゃそうだろう。というかエラーで済んで良かったという。

あとどうするか?

How to Run an Existing Linux Partition in VirtualBox - YouTube

これはあまりに古めかしいが、内容的には起動ディスクを別途作って起動するのはありえそうではある。

WindowsのVirtualboxで物理ディスクのLinuxを起動しようとしたら失敗した話 | ゲームの小ネタメモ帳 > スポンサー広告 > Linux

この方はparition5がespと書いてるように、UEFI で起動するならやはりシステムパーティションはもう1つ?必要か?

はたまた grub-install とかして MBR で起動できるようにすればいいのか…

とか考えてるけどわからん😇

nginx + ngx_mruby を homebrew でインストールしたかった

結論からいうとできたんだけど、ちょっとハマった。

ちょっと、本当にちょっとだけ ngx_mruby 試してみたくて、簡単に入ればいいなーと思って、探して↓を見て喜々として試したわけだけど

ngx_mrubyがHomebrewで超簡単にインストールできるようになった - 人間とウェブの未来

既に issue を上げてる人がいたけど、今 brew install nginx-full --with-mruby-module としても一発でインストールできない。

こんな感じで。どう考えても書き込み権限あるディレクトリに書き込めなくて死ぬ。

brew install nginx-full --with-mruby-module
==> Installing nginx-full from homebrew/nginx
==> Downloading https://nginx.org/download/nginx-1.12.1.tar.gz
######################################################################## 100.0%
==> git init
Last 15 lines from /Users/xxx/Library/Logs/Homebrew/nginx-full/01.git:
2017-08-13 15:21:22 +0900
git
init
error: could not lock config file /usr/local/Cellar/mruby-nginx-module/1.20.0/share/mruby-nginx-module/.git/config: Operation not permitted
fatal: could not set 'core.repositoryformatversion' to '0'

原因は --verbose するとわかるけど homebrew は sandbox-exec を使って sandbox 下でビルドするようになってて、それを想定していないこの formula がおかしくなってしまった様子。

homebrew の 1.0.0 が出たのが2016年9月で、1.0.0 から sandbox を使うようになったから恐らくそれからインストールできなくなってしまったんだろう。(きっと)

mruby の install スクリプトgit 管理されていることを想定されているとかコメントに書かれていたりするし homebrew のことも mruby のことも何も知らないので自分がちょっと調べて直せるってことはなさそうだったので、とりあえず今回は --no-sandbox オプションで回避した。

これでイケると思ったんだけど、まだうまくいかず。

ld でエラーが出てどうも openssl あたりのリンクがうまくいかない。

これもどうすればうまくいくのかわからなかったので、 forkしてオプションを追加してbrew edit してしまうというイケてない方法で回避した。

ちゃんと読んでないけど LIBS で -lcrypto は普通に指定されているような気がするので、これは自分の環境が悪いのかもしれないし、ちょっと今試したいだけで特に真面目にそこを調べるほど時間掛けたくはないのでとりあえず無視…

また使うことがあれば調べる。

あと今回は自宅の mac 上で使いたかったから brew で入れたかったんだけど普通に ngx_mruby 試すだけなら docker とかあるしそっち使うほうがいいだろうね。(というか mac 上でとはいえ docker でできない理由はなかった)

docker で Run `bundle install` to install missing gems になっちゃう件

Docker で Gemfile に変更があったときだけ bundle install を実行するために、 Gemfile と Gemfile.lock を先に ADD しておいて bundle install を先に実行しておくのはもはや常識だと思う。

ちょいちょい例にこういうのがある。(ここでは Dockerfile とアプリケーションが同じリポジトリディレクトリ)にあるとして、そのディレクトリで docker build してるとする)

WORKDIR /tmp
ADD Gemfile Gemfile
ADD Gemfile.lock Gemfile.lock

....

ADD . /app

どういうのかというと、 bundle install を先に実行してキャッシュを作るときのディレクトリと、実際にアプリが動くディレクトリを別にしているという例。

これは通常問題ないんだけど、bundle install の際につけるオプションによっては問題になる。

例えば bundle install –without development test とかする場合。

/tmp 以下には install 時に .bundle/config が作られてそこに BUNDLE_WITHOUT の情報が書き込まれるので、特定の group が除外されていることがちゃんと bundler に伝わる。

しかし、↑でいうと /app 以下で bundle exec とかするときにはその情報は伝わらないので、without オプションを指定して意図的に除外した group の gem がインストールされていないと、タイトルに書いたようなエラーが出てしまう。

解決策としては普通にアプリを動かすディレクトリで bundle install をやっておけばいい ( bundle config --global without development:test[:…] とする手もある )