Concolic Testってなんだ？

自分が常日頃考えている課題として「組込ソフトウェアのユニットテストを自動化できないか」という課題があるのですが、ここ数日テストの自動化に関する論文やオープンソースの情報を漁ったりして少しですがインプットがたまったので整理の為にアウトプットしておきたいと思います。だらだらと書いてしまった感があるのでまとまりは微妙です。

目次

Concolic Testとは

そもそもConcolicとはなんでしょうか。調べてみるとSymbolicとconcreteを書けた造語のようです。Symbolicというのはシンボリックテスト・シンボリック実行のことで、動的テスト手法の１つです。
そもそも私はシンボリック実行を知りませんでしたので以下の3サイトの情報を参考にさせて頂きました。

はじめてのコンコリックテスト
http://jasst.jp/symposium/jasst15tokai/pdf/S4-1.pdf

ntddk.github.io

www.kzsuzuki.com

参考にさせて頂きまして、ありがとうございます！

さて、シンボリック実行についてですが、シンボリック実行では実際に実効対象のコードが実行されるわけではありません。SATソルバが制約条件を満たす値を求める計算が行われるだけです。*1

かいつまんでの私の理解ですが、シンボリック実行が抱える課題として、シンボルだけでは経路を求める計算が発散してしまい実用的でないという課題があるようです。
そこで登場したのが入力値に具体的な値を入れてみるという手法でシンボリック実行と組み合わせるといい感じになるということで

Symbolic + concrete = concolic

ということでConcolic Testという手法が出てきたそうです。

テストは金がかかる

そもそも自分がなんでconcolinic testに関心を持ったかというと、テストは面倒で時間がかかるからでした。時間がかかる＝金がかかるということでもあります。
組み込みの製品開発におけるテスト工程にはとても時間がかかります。組み込みソフトウェア開発での単体テストの場合、実機で動かすことが求められ、オシロ・ロジアナといった測定機器を使用してハードウェアレベルでの確認が必要な場合もあります。通信の場合はWireShark等を使ってパケットの確認なんかも必要です。

実機で動かす都合上、テストの自動化がとても難しく、他のソフト開発と違って回帰テストは容易に実施できません。

またカバレッジは基本的にC2カバレッジを満たすことが求められるので呼び出し側のコードを書くのにも多少頭を使う必要があります。
実行はともかくとしてC2カバレッジを満たすテストコードを書くというのは関数内に存在する条件分岐などの制約(constraint)に従って書くわけですが、ちょっと面倒なパズルみたいなものでこれはソルバーでも解ける問題です。ということで自動化ツールを探していていました。なかなか情報が見つからないので自分で作ってしまいたいと思っていました。

論文・参考記事等

情報収集にあたって読んだ論文などの一覧をここに残しておきたいと思います。

CUTEというConcolic Test Toolに関する論文

http://mir.cs.illinois.edu/marinov/publications/SenETAL05CUTE.pdf

CUTEというC言語向けConcolic Testツールに関する論文です。Concolic Testで検索すると上位に出てきました。
論文の概要ですが、

CUTEというツールを使ってSGLIBという汎用的なデータ構造を提供してくれるライブラリをテストしてみた結果...

という感じでしょうか。もちろんconcolic testのアプローチの手法についてきちんと述べられています。ただしCUTEのソースコードはどうも非公開のようです。

詳細は詳しく読んでいないところもありますが、

• 有限の深さ優先探索でシンボリック実行を行い、必要に応じて具体値を代入するアプローチをとった。
• この検証作業によってSGLIBのバグを2件検出した(うち1件は割と深刻なバグだった)
• テストデータの動的な作成・削除の有効な方法をしめすことができた
• Java版もつくって並行して試してる
• 暗号プロトコルや脆弱性に対して代数的なアプローチで攻撃を行うソフトについても調べてる

論文中で面白かったのはC言語だとポインタ型を引数に取ることがしばしばありますが*2ポインタ引数をテストする手法は既に先行事例が存在していてCUTEではそれらの事例を参考に実装したそうです。

Automated Testing Based on Java Predicates

https://web.eecs.umich.edu/~bchandra/publications/issta02.pdf

Test Input Generation with Java PathFinder

http://laserweb.cs.umass.edu/courses/cs521-621.Fall10/documents/visserpasareanu.pdf

A Framework for Generating Object-Oriented Unit Tests using Symbolic Execution

http://mir.cs.illinois.edu/marinov/publications/XieETAL05Symstra.pdf

私もRubyでC言語のテストコードの生成ツールを書いていた時期があったのですがポインタ型はどうすればいいのかで躓きました。*3

はじめてのコンクリックテスト

http://jasst.jp/symposium/jasst15tokai/pdf/S4-1.pdf

CRESTの活用事例

http://sea.jp/ss2015/paper/ss2015_C1-4(2).pdf

この論文は株式会社デンソーの方が発表された論文です。実際に社内でCRESTを活用された事例を紹介されています。2015年に発表されたようですのでもう3年も前です...
「7.おわりに」でテストケースの作成作業の効率化にCRESTが活かせた旨が記載されています。変数のサイズによってテストケースの生成時間が長くなることが課題として挙げられています。*4

http://debugeng.com/concolic%20testing.pdf

C言語で使えるConclonic Test Tool

CREST

ユニットテストのコードを自動生成してくれる(Conclonic Test)
http://www.burn.im/crest/

CUTEと違ってこちらは公開されています。まだ試していません...

CS453 Automated Software Testing

KAISTの先生のテスト自動化に関する講義資料です。
http://swtv.kaist.ac.kr/courses/cs453-fall14/

LLVM/Clangを使ってカバレッジツールを作ったりする宿題があるみたいで面白そうです。
ちょっと前ですが、私もこちらで紹介されている内容を参考に、Clangのライブラリを使ってC言語のASTを拾うサンプルを書いてみました。
Clangは直交性の高いクラス設計を意識しているのか、ASTだけでたくさんクラスが切られていて出力内容を理解しきれずに挫折しています・・・*5

github.com

感想

ソフトウェア工学の強さと現場への浸透

少しですが論文とかGithubとか見た感じではシステム工学・ソフトウェア工学の分野でもやはりアメリカの大学が強そう。日本の大学でも研究している研究室はあるのかも知れないけど、開発の現場までそれがリーチしているという感覚は少なくとも自分の知っている範囲ではあまりない。

[追記]
ICSE勉強会なる勉強会が開催されていることを知りました。面白難しそう。concolic testも取り上げられているようなので日本でも研究している方はそれなりにいらっしゃるようです。

アメリカ人はなんでもシステマチックに問題を解決しがちで、日本人は職人魂に頼りがちというかそういうイメージがある。計算機が普及した時代にどちらが有利なのかはいうまでもない気がする。

計算機でも意外と簡単に解けない問題があって、現実な解決策としてどう落とし込んでいくかを考えるというのは好きな分野かもしれない。

日本はモノ作りの国とか言われるけど、膨大な時間がかかる作業を人手に頼るというのは女工哀史とか蟹工船的なイメージがあるのでどうかと思う...

計算機にも人権があるみたいな考え方をした場合、自動化は道徳的に悪になると思うけど「何を大切にしたいか」という問いへの答えがアプローチの分かれ目になっていると思う。

自動化や工学的アプローチをどれくらいリスペクトするかというのは「どれくらい、人間もしくは人間の時間をリスペクトするか？」と相関しているのではないだろうか...

何をassertするか

先日のkernelvm関西のときに

テストコードの生成というのは現実的なレベルで実現できるけど、じゃあ自動でコードをテストするときにどこにassertを入れるかというのは計算機では解決できない

という話を聞いた。

それはその通りで「仕様」というのは計算機が決めるものではないので仕方がない気がする。「仕様」まで計算機が想定してくれるというのはパターンマッチのようなことをすればできるようになるかもしれないけど精度は期待できない気がする。

組み込みソフト開発現場ではデンソーの事例にもあったようにテストコードの生成が自動化されるだけでもめちゃめちゃ効率があがる。というのもC2カバレッジを狙ってテストコードを書くというのはコードを書いた本人でも頭を使って考える必要がある。テストケースを考えはじめると異常系とかの入力なんかは基本的にはなんでもいいのについつい現実的なケースを考えてしまったりする。要するに頭が勝手に動いて疲れる。テストコード考えて書くのはやはり面倒だ。何をassertするかは計算機が判断できなくても構わない。むしろ自動で出来上がったカバレッジの結果を解釈して意味を見出していくというのが人間の仕事なんだと思う。

開発プロセスに関して現在では、コードレビュー→単体テストという流れが一般的だが、テストコードの生成が自動化され、テストの実行コストが下がれば、単体テスト→コードレビューという順番での開発も可能になる気がする。そうなるとレビューする観点も変わって面白いんじゃないだろうか。*6

動的なテストの研究の歴史は浅い

論文や論文中の参考文献の発表時期を見てもテストの自動化に関する研究はまだまだ浅いように感じた。2000年代の論文はテスト手法に関する論文が多いようなので、静的解析によるテストが研究されていた時期かもしれない。動的テスト手法に関する論文が出てきたのは2000年半ば～2010年代にかけてっぽい。違ってたらすいません。

[追記]
書き終わった後でさらにネット漁ってたらこちらの記事に「シンボリック実行は1970年代から広く知られている」と書かれていました。そうなのか・・・ごめんなさい、まぁ産まれてなかったということで許してください(涙)

d.hatena.ne.jp

話はそれるけど、仕事でcoverityのテストツールを使わして貰ったことがあって、非常に便利で出来の良いテストツールだった。*7

あのcoverity社は設立されたのが2009年11月とのことなのでまだ10年にも満たないのですね。coverityはスタンフォード大学のテストに関する研究からスタートしたそう。
スタンフォードは特にそういう印象があるけど、アメリカの大学のこういった研究をビジネスにして成功していく実学的なスタイルは好き。

日本人もアメリカ人のこういった気質はもう少し見習ってもよいようにも思うけどあまりそういう事例を聞かないのはなぜでしょうか。

まぁ答えはある程度分かってはいるのですが、せめてもう少し一般の人や企業の経営者がテクノロジーに対するリスペクトと好奇心を持つようになってもいいのではないかと思う。

追記

[2019/4/12]
この記事でカバレッジの指標をC0と書いておりましたが、C2の誤りです。本文のC0をC2に訂正致しました。
組込のテストでは一般的にC2(条件網羅 コンディション・カバレージ)の網羅が求められます。
*8

*1:将棋で実際に駒を動かさずに「こうすればああなる」を先読みするのと同じようなイメージかと思います。

*2:特に構造体や文字列はポインタで渡しますね

*3:変数名から想像して解決すればいいのではとか思ってました...

*4:これは実際に自分でもCRESTを使って確認してみたい

*5:ClangでASTを出してゴニョゴニョしたい人には少しは参考にして頂けるのではないかと思います

*6:テストが自動化されても実装漏れは検出できないのでレビューが必要なのは変わりない

*7:年間100万円くらいのライセンス費が必要なので、「使えない窓際社員を首にしてうちの会社でもこれ買いましょうや！」と言って上司に白い目で見られた

*8:会話とかでもよくC0とC2を逆の状態で話してしまいます...

低レイヤプログラミングのためのRubyの拡張モジュール開発入門

この記事は、低レイヤのコードをRubyで書きたいという人のための拡張モジュール作成入門記事です。

Rubyが好きでC言語がある程度分かる方には読んで頂けると参考になるかと思います。※ただし、私が真面目に拡張モジュールを書いていたのはもう5年以上前なので知識が古くなっている可能性があります。

この記事を書いた動機ですが、RXマイコンのリンカをRubyで書いていて、Rubyで書いているとC言語の構造体へのアクセスが辛くなってきたので、FFIや拡張モジュールを使うべきだったと感じました。

久しぶりに拡張モジュールの書き方など復習してみたので記事にしてみました。

FFIも拡張モジュールもちょこちょこと触っているのですが、私のように

「やる気はないけど、進捗は欲しい」

という方には、RubyとC言語を上手く組み合わせて開発をするというのは悪くない実装方針ではないでしょうか*1
この記事を含めて、できれば低レイヤのプログラミングの為に拡張モジュールやFFIを上手く使う方法として整理したいと思います。

目次

Rubyの拡張モジュールとは何か

拡張モジュールはC言語・C++言語で実装したRuby用のライブラリです。
誰かに挨拶するコードをRubyで書く場合、

def hello name
  puts "hello " + name + "!"
end

hello("simotin") # => hello simotin!

のように .rb の拡張子のファイルに Ruby の文法に則って書くのが普通のRubyのプログラミングです。

これに対して拡張モジュールで実装する場合、

*1:私も試行錯誤中な感じですが・・・

C言語でEthernetFrameをpcap形式でダンプしてみる。

ネットワークの勉強のためだいぶ前に買っていた「ルーター自作でわかるパケットの流れ」を読んでいます。

ルーター自作でわかるパケットの流れ

書籍の中で、pcap形式について触れられていて、随分とシンプルなフォーマットだったので自分でもpcap形式のファイルをダンプしてみました。

準備

pcapに関する宣言などは、pcap.hでされているらしいのですが、pcap.hは標準ではインストールされていません。libpcap-dev のパッケージインストールを行います。

$ sudo apt install libpcap-dev 

で pcap.hが/usr/includeにインストールされます。

pcap形式で出力するには struct pcap_file_header というファイルのヘッダ情報と
struct pcap_pkthdrというパケット単位のヘッダを付与し、後はフレームの中身を出力すればいいそうです。

ところで、struct pcap_file_header にいろいろ値を設定する必要があるがどこで定義されているかよくわかりません。
例えばEthernetフレームであれば、linktypeには LINKTYPE_ETHERNETとかを入れるようだがLINKTYPE_ETHERNETはpcap.hには見つからない。DLT_EN10MBでもよいらしいがこちらも見つからない。

いろいろ情報をあさっているとこちらのサイトがlibpcapの本家らしいということで、
www.tcpdump.org

とりあえずlibpcapのソースをダウンロードして調べてみます。
https://www.tcpdump.org/release/libpcap-1.9.0.tar.gz

grep してみると、
LINKTYPE_ETHERNETはpcap-common.cで宣言されている。ということはこの定義は非公開のようです。

一方、DLT_EN10MB は pcap/dlt.h で宣言されています。
こちらのファイルは apt で libpcap-dev をインストールしたときに /usr/include/pcap/dlt.h
としてインストールされていました。

ということで、ヘッダに必要な情報を適当に詰め込んで適当に動かしてみたところちゃんとwiresharkでも表示できました。

とりあえずキャプチャできてそうなコード

https://github.com/simotin13/packetcapture/blob/master/main.cgithub.com

#include <stdio.h>
#include <net/if.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/socket.h>
#include <sys/ioctl.h>
#include <sys/time.h>
#include <arpa/inet.h>
#include <net/ethernet.h>
#include <linux/if_packet.h>
#include <pcap.h>

#define TCPDUMP_MAGIC (0xA1B2C3D4)

static int openNetworkInterface(char *ifname);

int main(int argc, char **argv) {
	int sock;
	unsigned char recvBuf[1024*128];
	FILE *fpPcap;
	struct pcap_file_header pcapHeader;

	if (argc < 2) {
		fprintf(stderr, "must specify interface name.\n");
		exit(EXIT_FAILURE);
	}

	fprintf(stdout, "%s\n", argv[1]);
	sock = openNetworkInterface(argv[1]);
	if (sock < 0) {
		fprintf(stderr, "Open Interface [%s] failed.", argv[1]);
		exit(EXIT_FAILURE);
	}

	fpPcap = fopen("dump.pcap","wb");
	if (fpPcap == NULL)
	{
		fprintf(stderr, "Open Interface [%s] failed.", argv[1]);
		close(sock);
		exit(EXIT_FAILURE);
	}

	memset(&pcapHeader, 0, sizeof(struct pcap_file_header));
	pcapHeader.magic = TCPDUMP_MAGIC;
	pcapHeader.version_major = PCAP_VERSION_MAJOR;
	pcapHeader.version_minor = PCAP_VERSION_MINOR;
	pcapHeader.snaplen = 2048;
	pcapHeader.sigfigs = 0;
	pcapHeader.linktype = DLT_EN10MB;
	fwrite(&pcapHeader, sizeof(struct pcap_file_header), 1, fpPcap);
	while(1) {
		int recvSize;
		struct pcap_pkthdr pktHeader;

		recvSize = read(sock, recvBuf, sizeof(recvBuf));
		if (recvSize < 0)
		{
			fprintf(stderr, "read error [%d]\n", recvSize);
			continue;
		}

		fprintf(stdout, "recvSize:[%d]\n", recvSize);
		memset(&pktHeader, 0, sizeof(struct pcap_pkthdr));

		gettimeofday(&(pktHeader.ts), NULL);
		pktHeader.caplen = recvSize;
		pktHeader.len = recvSize;

		fwrite(&pktHeader, sizeof(struct pcap_pkthdr), 1, fpPcap);
		fwrite(recvBuf, recvSize, 1, fpPcap);
	}

	close(sock);
	fclose(fpPcap);
	exit(EXIT_SUCCESS);
}

int openNetworkInterface(char *ifname) {
	int ret;
	int sock;
	struct ifreq ifreq;
	struct sockaddr_ll sa;

	sock = socket(PF_PACKET, SOCK_RAW, htons(ETH_P_ALL));
	if (sock < 0) {
		fprintf(stderr, "socket failed %d\n", sock);
		return -1;
	}

	memset(&ifreq, 0, sizeof(struct ifreq));
	strncpy(ifreq.ifr_name, ifname, sizeof(ifreq.ifr_name)-1);

	ret = ioctl(sock, SIOCGIFINDEX, &ifreq);
	if (ret < 0) {
		fprintf(stderr, "ioctl failed [%d]\n", ret);
		close(sock);
		return -1;
	}

	sa.sll_family=PF_PACKET;
	sa.sll_protocol=htons(ETH_P_ALL);
	sa.sll_ifindex=ifreq.ifr_ifindex;

	ret = bind(sock, (struct sockaddr *)&sa, sizeof(struct sockaddr_ll));
	if (ret < 0) {
		fprintf(stderr, "bind failed [%d]\n", ret);
		close(sock);
		return -1;
	}

	return sock;
}

できていないこと

1. フレームのタイプのチェックとかしてないけどいいんだろうか(ARPとかICMPとか・・・)
2. 異常系あまりケアしてません。Ctrl-Cとかで止めると多分最後のパケットは適切にダンプされない。

関連書籍

著者の小俣さんの続編的な書籍!?が出版されていて、この本も買ってみたのですが、積本になってしまっています。
せっかく買ったので読みたいけど読めていない・・・

ソースコードで体感するネットワークの仕組み ~手を動かしながら基礎からTCP/IPの実装までがわかる

感想

自分でパケットキャプチャしてみて、ゴニョゴニョするのってなんかかっこいい。

マグネットペイントを使って木製ボードでタスク管理ができるようにしてみた

メモの付箋を貼ったりして使おうとだいぶ前に壁掛けの木製のボードを買っていたのですが、付箋紙が直ぐにはがれてしまい全然活用できていませんでした。

最近嫁さんと話していると「マグネットペイント」なるものがあって、それを塗ると磁石がくっつくようになるということで、マグネットペイントを使ったタスク管理ボードの制作に挑戦してみました。

目次

マグネットペイントとは何か

マグネットペイントとは文字通り「塗れる磁石」です。今回の私のケースのようにボードに塗って磁石が使えるようにしたり、壁紙に塗ったりすることもできるようです。

ユダヤ式Why思考法を読んだ

ここ最近、ユダヤ人というものに興味があり時々ユダヤ人・ユダヤ教に関する本を読んでいるのですが、ユダヤ人に関する本の読書録を書けていなかったので書いておきたいと思います。

目次

ユダヤ人のイメージ

私は歴史が大好きなのでユダヤ人という集団のことは当然知ってました。ユダヤ人のイメージというと、

• とにかく優秀
• とにかく金持ち
• 医者とか弁護士
• アウシュビッツ
• 差別されてきた歴史
• イスラエル
• パレスチナ問題

といったイメージがあります。

例えばアメリカの映画とかを見ていても上記のような優秀な人、お金持ちの人という人物像で登場することが多いように思います。ユダヤ人の成功者という面と受難者という面がとても興味深い存在です。

ユダヤ人に興味を持ったきっかけ

最近になって自分のユダヤ人に対する興味が強くなってきた理由ですが、お客さんと画像処理・顔認証に関する雑談をしていて、

今の時代、顔認証はイスラエルには勝てないよ。うちで使ってる商品も顔認証はライブラリをイスラエルの会社の製品を買っているんだ。

という一言を聞いたからでした。
*1

そこから、

どうしてユダヤ人には勝てないんだろう。ユダヤ人の強さの根源は一体何なんだろう？

という疑問や興味が強く自分の中で湧いてきたのでした。

読んでみた本

ということでいくつかユダヤ人に関する本を読んでみたのですが、今回はタイトルにある通り、「ユダヤ式Why思考法」という本を読んだので読書録を書いておきたいと思います。

ユダヤ式Why思考法

概要

実はこの本を読む前に「ユダヤ人の成功哲学「タルムード」金言集」という本を読んでいました。

ユダヤ人の成功哲学「タルムード」金言集

この本はタイトルの通り、ユダヤ人の聖典とされるタルムードについてエピソードなどを交えて紹介する書籍です。
結構面白かったです。*2
著者の石角さんは日本人でありながらユダヤ教徒に改宗!?された方ということで今回「ユダヤ式Why思考法」も読んでみました。

「ユダヤ式Why思考法」は、様々な問い・質問が著者から出され、それに対し「あなたはどう考えるのか？」「なぜそう思うのか？」が読者にも求められながら、「ユダヤ人はこう考える」という解説と教訓が語られるというスタイルです。

登場する質問というのはクイズではありません。どちらかというと答えのないような問いが多いように思います。
例えば、「水はなぜ透明なの？」と子供に聞かれたらあなたなら何と答えるだろうか？
というような質問が著者から投げかけられます。

著者の石角さんが訴えたいことはそれぞれの問に対して正解となる答えを期待しているというよりも、

自分の頭で考え抜く習慣を持つべきだ

ということを主張されているように全体を通して感じました。

日本批判

本書を読んでいて気になった点として全体的に現在の日本人に対する批判が多くみられます。*3
指摘の内容は確かにもっともな内容で、愛ゆえの指摘なのかもしれませんが、私には少し論点がずれているように感じる点もありました。

例えば「日本人はiphoneをなぜ作れなかったのか？」章が最後に書かれています。
iphoneににたザウルス(シャープ)を作っていた日本人がiphoneを作れなかった理由を、開発者や企業「日本社会の空気を読みすぎたためではないか」という風に分析されています。
それは確かに理由の一つとしてそのような理由はあるかもしれませんが、iphoneを作れなかったのは日本人だけではなくフランス人もドイツ人もイギリス人も中国人も同じです。ユダヤ人も作れていません。

iphoneをアップル以外のアメリカの企業はなぜ作れなかったのでしょうか。

という疑問がわきます。*4

物つくりというのは個人の才能や能力によるところが大きいのでiphoneのような一商品と日本人という集団を比較に出すのは例として説得力に書けるように思いました。

感想

ユダヤ人のものの考え方、習慣を知ることができて面白い書籍でした。

なんとなくですが、ユダヤ人に優秀な人が多い理由が分かった気がします。あと差別されてきた理由も・・・

ユダヤ人のように自分の頭で考え抜くということにこだわる姿勢は自分も真似していきたいです。

他にもユダヤ人について書かれた本をいくつか読んだので少しずつ読書録とかまとめの記事を書いてみたいと思います。

*1:たしか日本の自動車メーカーが自動運転のための認識用ソフトの自社開発を諦めたみたいなニュースを聞いたのもこのころだったと思います。

*2:今回読んだ「ユダヤ式Why思考法」の内容と少しですが被る部分もありました

*3:これは「ユダヤ人の成功哲学「タルムード」金言集」でも同様でした

*4:アップル以外のアメリカ企業では日本人をたくさん雇っていたのかもしれませんね・・・