日本ソフトウェア科学会第 36 回大会 (2019 年度) 講演論文集

プロセス仮想マシンにおけるシステムコール実装支援
手法
片貝 惇哉

福田 浩章

現在の情報工学教育では，機械語やアセンブリ言語等は抽象化して享受されるため，組み込みのデバッグなどで知識を利用することが困難である．そこで我々は，学生自身が仮想マシンを実装する学習法と支援機構を提案してきた．
この学習法では，CPU 命令とシステムコールで構成されるプログラムに対して，それら動作を模擬するプロセス仮想マシンを実装するまた，支援機構は正しいリソースの値を提供し，学習者が実装する仮想マシンの値と比較することで，CPU 命令の実装の誤りを検出する．しかし，システムコールは割り込み命令の呼び出しであり，それぞれのシステムコールをどのように実装するかは，学習者に委ねられている．そのため，リソースの比較では誤りを検出することができず，学習における問題となっていた．そこで本研究では，仮想的なファイルシステム等，OS の一部機能を提供し，それらにアクセスする API をシステムコールの実装に利用してもらう．また，従来のリソース比較を拡張することで，システムコールの実装の誤りを検出する．

バイナリからプログラムの動作を特定する必要があ

1 はじめにるため，バイナリの振る舞いを理解し，動作を追う能オペレーティングシステムやコンパイラなど，ハー力が求められる．また，組み込み開発では，メモリやドウェアを制御しそれら機能をアプリケーションソ

CPU の状態を観察しながらプログラムをステップ実フトウェアに抽象化して提供するシステムソフトウェ

行するなどで，機械語・アセンブリ言語の経験が必要

ア (以降，低レイヤーと呼ぶ) は，情報工学教育におとされる．このように，特定の分野では機械語の動ける主要科目の一部となっており，多くの大学で教育作を理解し，推測する能力も求められるため，大学が行われている．しかし，新たな科目の導入や他分野教育で行われる抽象化された知識では不十分である．の高度化によって，最もハードウェアに関わる機械語現在，低レイヤーを学習する方法として，多くの研究やアセンブリ言語の学習は他のコースに取って代わらやツールが存在する [9] [3] [11] [7] [2] [4] [8]．それらはコれている [9]．そのため，十分な教育時間を設けるこ

ンピュータ内部の動作や状態を可視化し，機械語やとができず，多くの場合抽象化した概念に焦点を当てアセンブリ言語などの理解をサポートする．しかし，ている．概念を抽象化することで，機械語やアセンブこれらのツールは内部の状態や動作を可視化するにリ言語の複雑な部分を隠蔽できるが，隠蔽された知識留まるため，機械語やアセンブリ言語を用いる経験を必要とする分野も存在する．例えば，セキュリティが不足しており，機械語で動作を推測する，デバッグの分野では，マルウェアの解析やプログラムの脆弱性するといった能力を身につけることは難しい．一方，検査のために，ソフトウェアの解析が行われている．

OS やコンパイラの実装を通した学習では，機械語，バイナリで配布されるプログラムを解析する時には，アセンブリ言語を用いて学習できるが，ハードウェアとソフトウェアの幅広い知識が求められるため，実用

A method of supporting system call implementation
for process virtual machine
Junya Katagai Hiroaki Fukuda, 芝浦工業大学, Dept.
of , Shibaura Institute Technology.

レベルの実装は難しい．我々はこれまで，経験を通した機械語の理解を目指し，2 章に述べるように学生自身で仮想マシンを実装する学習方法を実践してきた．

この学習では，特定の CPU，OS で実行可能なバイ用できる知識を習得できる．また，機械語やアセンブナリを課題として配布し，その動作を模擬するプロセ

リ言語だけでなく，オペレーティングシステムの理解

ス仮想マシンを学生自身が実装する．プロセス仮想マを促すため，システムコールを含んだバイナリを実行

シンの実装には，CPU，OS の動作をエミュレートすの対象としている．このバイナリを正しく実行するたる必要があり，機械語やアセンブリ言語，OS の理解めに，学生はシステムコールをエミュレートする必要が求められる．これまでの教育の実践では，支援機構があり，OS とアプリケーションプログラムのインタを用いてプロセス仮想マシンの実装を行っていたが，フェースであるシステムコールの仕組みとその振る舞

OS のエミュレーションにおいては，その実装支援がいを学習することができる．我々は学習対象の OS と十分でなく，学習における問題となっていた．そこでして，minix2 [10] を選択した．システムコールのエ本研究では，仮想的なファイルシステムなど OS の一ミュレーションでは，学生はシステムコールの仕様や部機能を提供し，それらにアクセスする API をシス

OS のソースコードから動作を推測する．そのため，テムコールの実装に利用してもらうことで，学生のシ

OS のソースコードは学生にとって読みやすいことがステムコール実装を支援する手法を提案する．以降，望ましい．minix2 は POSIX に準拠し，教育用に作

2 章ではこれまで行ってきた学習方法と問題点を概説成された OS であり，ソースコードは学生にとって読し，3 章で提案手法の詳細，4 章で評価について述べみやすいものであると考えられる．また，minix2 のる．その後 5 章で関連研究，6 章でまとめと今後に予システムコールを学ぶことで，POSIX 準拠の OS の定について述べる．

仕組みを学ぶことができる．

2 学習方法2. 2 プロセス仮想マシンの仕様

この学習方法では，特定 CPU，OS のバイナリにプロセス仮想マシンは実際のコンピュータと同様に，対して，その動作を模擬するプロセス仮想マシンを，メモリや CPU など複数の要素で構成される．8086

学生自身が実装することで，機械語，アセンブリ言は 16 ビット CPU であるため，表 1 に示す 2byte レ

語，OS の学習を行う．本章ではその学習方法の詳細

ジスタやフラグ，メモリを持つ．8086 には上記のリと問題点について述べる．まず，2.1 節で仮想化の対ソース以外にも複数リソースが存在するが，それらは象 (e.g. CPU)，2.2 節で実装するプロセス仮想マシ

OS から操作されるリソースである．我々の学習方法

ンの仕様に関して述べる．その後，2.3 節でこれまで

ではシステムコールをエミュレートするため，バイナ実施した教育手法について述べた後に，2.4 節で現状リに含まれる機械語が表 1 以外のリソースを変更すの問題点について考察する．

ることはない．仮想マシンの実装は，これらリソースを変数として定義し，実行するバイナリに従ってそれ2. 1 学習する対象の選択らを書き換えていけばよい (以後，内部状態の書き換学習する対象の CPU は，学んだ知識をデバッグやえと呼ぶ)．ここで，バイナリ (プログラム) の実行例

解析に応用することを考慮し，教育用に簡略化されたとして，Listing 1 を仮想マシンで実行することを考ものではなく，実際の CPU を学習対象にする．そのえる． Listing 1 はアセンブリ言語で書かれたプログ候補として，現在広く利用されている Intel の x86-64ラムであり，命令部とデータ部で構成される．前半 4などが考えられるが，x86-64 は複雑であり，学生が行は text セクション (以下 text) であり，ここにプロ最初に学習する CPU としては適切ではない．そこで，グラムを記述する．後半 4 行は data セクション (以学習における難易度と価値を考慮し，Intel の 8086

下 data) であり，ここに記述したデータはメモリに格を学習対象の CPU とする．8086 は x86 の元となる

納され，text に記述するプログラムから参照するこCPU であり，後方互換性は維持されている．そのたとで値の書き換えや読み込みを行う．仮想マシンでプ

め，8086 を学ぶことで，現在の x86 や x86-64 に応

ログラムを実行するには，まず text と data をメモ表1123456789

プロセス仮想マシンの構成

レジスタ (各 2byte)

フラグレジスタ (16bit)

メモリ (64kb)

AX,BX,CX,DX,SP,BP,SI,DI,IP

flags(OF,ZF,SF,CF)-Listing 1
mov bx, #message
int 0x20
mov bx, #exit
int 0x20

MMVM 動作例.sect .data
message: .data2 1, 4, 1, 6, 0, hello, 0, 0
exit: .data2 1, 1, 0, 0, 0, 0, 0, 0
hello: .ascii "hello\n"リに配置した後，text から，命令をフェッチし実行していく．一行目の mov bx, #message は，data に格納された message の先頭アドレスを 2byte の即値として，BX レジスタに代入する．つまり，仮想マシン

123456789101112131415161718Listing 2 vmiss 利用例
struct{unsigned char memory[0x10000]; //memory
unsigned short regs[9]; //registers
unsigned short flags; //flag} sdata;void run(){while(true) {switch(opcode) {case 0x20: ...// int
case 0x88: ...// mov}if(!rsccmp(sdata)){//内部状態比較
showErrorMessage();exit(1);}}}の BX レジスタを message の先頭アドレスに書き換
える．二行目の int 0x20 はシステムコールの実行をえられたバイナリを正しく実行する仮想マシンを内意味する．minix2 ではシステムコールが呼び出され包しており，Relative Debugging [1] の手法を用いて，ると，カーネルが BX レジスタで指定されたメモリ一命令ごとに学生が実装する仮想マシンと，VMISSを参照し対応する処理 (システムコールの実体) を呼の正解となる仮想マシンで内部状態を比較するインタ

び出す．BX レジスタには message が指定されていフェースを利用者 (学生) に提供する．内部状態の比るため，message のアドレスから必要な値を読み取

較は，表 1 で述べた全リソースを比較することで行わり，システムコールを実行する．この例では，writeれ，プログラム終了まで内部状態を 1 命令毎に比較しシステムコールが実行され，その後のメモリの内容続けることで，誤った命令の特定を行う．CPU 命令である”hello” という文字列が出力される．このようの仕様は [6] に規定されており，一命令ごとのリソーに，リソースの内部状態を書き換える (e.g. BX の書

スの内部状態の遷移は一意に定まる．そのため，内部き換え) ことで仮想マシンはプログラムを実行する．

状態が一致しない場合，直前の命令に誤りがあると即座に判断できる．ここで VMISS の利用例として，

2. 3 これまでの教育手法

Listing 2 に VMISS を利用する仮想マシンの擬似コー

学生が仮想マシンを実装するためには，機械語の構

ドを示す． Listing 2 のように，仮想マシンの実装は，造と対応する動作を理解する必要がある．そこで，こCPU の実行を模擬する無限ループ (while) と各命令の学習方法では 8086 の CPU の仕様書 [5] [6] を参照の処理を記述する分岐命令で構成され，VMISS の利する．これらの仕様書は，機械語とアセンブリ言語の用は命令実行毎に比較用ブレークポイント (rsccmp)対応，各アセンブリ言語の動作を規定しており，学生を挿入して行う．rsccmp では，1 から 4 行目の形式

は仕様書から，機械語の動作を推測し仮想マシンを実で内部状態の送信した後，比較結果の受信を行い，内装していく．しかし，この仕様書だけでは実装が正し部状態が正しい場合は TRUE，誤りの場合は FALSEいか否かを確認することが難しいため，VMISS と呼が返される．そのため，FALSE が返された場合のみばれる支援機構を用いて実装を行う．VMISS は，与エラー内容を出力することで，実装の誤りを特定すの動作は検証できず学習における問題となっていた．
そこで本研究では，ファイルシステムなど OS の一部機能と，それらを利用する API を提供することで，システムコールの実装を支援する手法を提案する．学生は API を利用して OS の管理情報 (ファイルの実体やオフセットなど) を操作し，システムコールをエミュレートしていく．また，従来のリソースの比較に加え，OS の管理情報の比較を行うことで，システム
図1

通知情報コールの実装の誤りを特定する機能を提供する．

る．ここで，そのエラー内容の例を図 1 に示す． 図

3 提案手法

1 では，int 0x20 の実装が誤っていることを示してお本研究では，学生のシステムコール実装を支援す

り，同時に比較結果が異なるメモリやレジスタ名，おるため，ファイル管理に関連した OS の機能とそれらよび内部状態の通知を行う．各リソースの内部状態はを利用するための API を提供する．学生はこの API

図 1 では，AX レジスタの内部状態が 0000 になるのから，ファイルのパーミッションやオフセットなど，が正しい動作であるのに対し，学生の仮想マシンでOS が持つファイルの管理情報を操作することで，シは 0001 であることを示している．同様に，BX レジステムコールを実装していく．API を通して操作さスタや Memory に関しても値が異なることがわかる．

れるファイルの管理情報は node データ，file データ，このように内部状態の詳細な差分のみを通知するこ

fdm データの３つに大別されそれぞれ役割が異なる．とで，学生は自らのマシンがどのように誤っているの

まず node データは，単一のファイルを表すデータでか推測でき，誤った命令の修正していく．

あり，Listing 3 に示す構造体で表される． Listing 3のように，ファイルの実体に加え，ファイルサイズや2. 4 現状の課題

パーミッションを保持しており，これらの node デー

2. 3 節で述べたように，VMISS ではリソース比較

タを操作する API はファイルシステムから提供されによって，CPU 命令の実装の誤りを特定することがる．ここで，node 操作を行う代表的な API を，表 2できる．しかし，システムコールは割り込み命令の呼に示す．学生はこれらの API 通して，ファイルの読び出しであり，VMISS のリソース比較では，十分がみ書き (read, write) や状態の取得 (getattr) を行う支援が受けられないという問題があった．ここで，そことで，システムコール (e.g. read, write, stat) を実の原因の考察としてシステムコール実行の流れを述べ装していく． 次に，プロセスのファイル操作状態をる．システムコールの実行では，割り込み命令が呼び出されると，表 1 のリソース郡から，システムコールの番号や引数がカーネルへ渡される．その後，カーネルはそれらの番号，引数を元にシステムコールの実体を呼び出し，システムコールの成否や返り値がリソース郡に返される．VMISS では，命令実行毎にこれらリソースの比較を行っているため，カーネルから返されるシステムコールの成否や返りのみ検証される．そのため，従来のリソース比較では，open・wrirte シ
ステムコールの実装が誤っておりファイルや標準出力に正しく出力されないといった，システムコール内部

1011121314151617181920

Listing 3 node 構造体
struct node{
int size; //ファイルサイズ
int type; //data の内容を規定(file or dir)unsigned char∗ data; //ファイルの実体
int mode; //パーミッション
char uid; //ユーザ ID
char gid; //グループ ID
int atime; //参照実行
int mtime; //更新時刻
char nlink; //ディレクトリからの参照数}

表2node データに関連した API

API 名機能概要

open

指定したパスから node を取得するreadnode からデータを読み取る

write

node にデータを書き込む

getattrnode の状態を取得する

accessnode の実行権限を調べる

26
27
28
29

Listing 5 fdm 構造体
struct fdm {int fd; //ファイルディスクリプタ
struct file ∗entry; //file データのエントリ}

表4

fdm データに関連した API

API 名

機能概要

表す file データに関して述べる．file データは Listing

pfalloc

新たに fdm データを取得する

4 の要素で構成され，ファイルのオフセットやモードregister

fdm をテーブルへ登録するに加え，node データと 1 対 1 で対応するエントリをunregister

fdm をテーブルから削除する

持つ．

clone

fdm をコピーする

この file データを操作するために，表 3 に示す APIを利用する．これら API を通して，ファイルのオフセットの変更など (seek)，ファイルの操作状態を変更していくことで，file データに対応する node デー
タの取得や，システムコール (e.g. lseek) の実装が行える． 最後に，もう一つのファイルの管理情報である fdm データについて述べる．ファイル操作のシス
テムコールでは，ファイルディスクリプタと呼ばれる識別子を用いて，ファイルの操作を行っており，この

図2

通知情報

ファイルディスクリプタと file データを対応付ける組を fdm データと呼ぶ．fdm データは Listing 5 の形式

タを登録・削除する API を提供している (表 4)．こで表され，その管理のために，テーブルへ fdm デー

れらを API を用いて，ファイルディスクリプタに対応する file データの取得，システムコール (e.g. dup,fcntl) の実装を行う．
Listing 42122232425

file 構造体

struct file{char flag; //オープンしたモード
int oﬀset; //ファイルのオフセット
struct node ∗entry; //node へのエントリ}

これら 3 つのファイル管理情報は図 2 に表す対応関係になっており，fdm データが file データのエントリを持ち，file データが node データ (ファイル情報を含む) のエントリを持っている． そのため，学生はAPI を通してこれらの３つの管理情報の要素を操作し，これらの管理情報の対応づけを行うことでシステ
表3

file データに関連した API

ムコールを実装する．
また，システムコールの実装を支援する手法とし

API 名

機能概要

falloc

新たな file データを取得するて，VMISS による支援と同様に，正しく動作する仮seek

ファイルのオフセットを変更する

想マシンと状態を比較することで，誤りを検出する機

getn

node へのエントリを取得する能を提供する．システムコールの実装は，Listing 3，Listing 4，Listing 5 で述べた３つのファイルの管理情報を操作することで行われる．そのため，それら全イルが保存される場合は想定されない．そのため，学ての管理情報を正しい動作時のものと比較すること

習においては，従来の比較手法に比べ大幅に支援時間で，実装の誤りを特定できる．また，この支援手法が増加することはなく，システムコールの実装支援機

は，2. 3 節で述べた従来のリソース比較に，ファイル能は教育に適用可能だと考える．の管理情報の比較を拡張したものであり，使用方法はListing 2 と同様，比較用ブレークポイントを挿入することで行われる．比較の結果が異なっていた場合は，正しいファイルの管理情報と学生の仮想マシンの誤ったファイルの管理情報が通知され，その差分を元に実装の修正を行っていく．

5 関連研究低レイヤーの学習を目的とした研究では，内部の動作や状態の可視化が主に行われている．

Cpu sim [8] は CPU の学習を目的としており，学生自身で独自アーキテクチャの設計や既存のアーキテクチャの変更ができる学習環境である．また，対象の4 評価

アーキテクチャで機械語やアセンブリ言語プログラム

本研究で提案したシステムコール実装支援手法のを実行することができ，実行時の内部状態の可視化

評価として，提供する API の表現力と性能の測定をを行なっている．この学習方法では，実践的に CPU行った．minix2 は 56 のシステムコールをサポートしアーキテクチャを学習することができるが，簡略化さており，本研究で提供する API を用いて表 5 に示すれた CPU を用いているため，知識を実際のデバッグ25 種類のシステムコールを実装できることを確認しや解析に応用することは困難である．

た． これは，基本的なファイル管理，入出力を行う上で十分な機能である．

MieruCompiler [4] はコンパイラの学習を目的にしたツールである．MieruCompiler では高水準言語のまた，システムコールの実装支援機能の評価として，ソースコードから，アセンブリ言語，AST，シンボファイル関連のシステムコールを含むプログラムを仮ルテーブルなどを視覚化している．i386 のような実想マシンで実行する場合の，支援にかかる時間を測定際の CPU のアセンブリ言語を確認でき，高水準言語した．ファイルシステムには，合計 2077696byte(約と低水準言語の関係を理解することが可能であるが，2MB) のファイルが保存されている状態で，実行時間コンパイラの教育を目的にしており，機械語やアセンの計測を行い，評価プログラムとして，minix の基本ブリ言語は，コンパイラの動作などを理解するためにコマンドから選択した規模の異なるプログラムを用い提供される．そのため，機械語やアセンブリ言語を実た．実行したプログラムの詳細や支援時間を表 6 に際に使用できるレベルで身につけることはできない．

示す．表 6 から，従来の CPU 命令の検証時間と比較

MieruCompiler と同様に，i386 のような実アーキして，極端な実行時間の増加は見られない．また，保テクチャに対応した可視化ツールとして，Frances [9]存するファイルのサイズによって実行時間は大きく変がある．Frances では C 言語，C++，FORTRAN な動すると推測されるが，このファイルシステムは学習ど，高水準言語の制御構造がアセンブリ言語でどう用のファイルを保存するものであり，現状大きなファ表されるかを可視化している．そのため，高水準言語

表5実装した minix システムコールと低水準言語の関係を理解することが可能であるが，可視化に留まり，その知識をデバッグや解析などに応

3read

4write5open

6close8creat9link

10unlink

15chmod

16chown

18stat

これらのように，既存研究では可視化に焦点を当て

19lseek

21mount

22unmount

23setuid

24getuidている．可視化は概念や動作の理解を支援することは28fstat33access

38rename

39mkdir

40rmdir可能であるが，実際に利用できる知識を提供する上で

41dup

46setgid

47getgid

60umask

61chrootは，機械語やアセンブリ言語を用いる経験が不足して用することは困難である．

表6

支援時間の測定

コマンド名

実行命令数

CPU 命令の検証時間

yes

140 命令 (１回の表示のみ)

0.01s

0.01s

hello

stat

35835 命令

0.85s

0.90s

stat

crc

115791 命令

2.59s

2.66s

crc

nm553722 命令

12.79s

13.55snm

いる．これら既存研究と比較し，本研究の学習方法では，仮想マシンの実装という実践的な学習を通して，経験を伴った知識を提供できる．

6 まとめと今後の予定
情報工学教育では，コンパイラや OS といった低レイヤー教育は抽象化した概念だけを知識として教授することも多く，それらの経験が求められる組込みシステム開発やセキュリティ分野に関わる技術者の育成は十分とは言えない．また，教育すべき分野は年々増加しているため，それらの教育に十分な時間を確保することも難しい．これらの問題に対し，我々は CPU
命令とシステムコールをエミュレートする仮想マシンの実装を通して，経験を伴った深い知識を提供する学習方法を実施してきた．しかし，これまでの学習では，仮想マシンのシステムコール実装について，その支援が十分でなく学習における問題となっていた．そこで本研究では，ファイルシステム等の OS の一部機能を API を通して利用してもらうことで，システムコールの実装を支援する手法を提案した．また，提供する API では，実装できるシステムコールがファイ
ル関連のシステムコールのみに制限されているものの，基本的なファイル入出力など，ファイル関連のシステムコールの多くを表現可能であることを確認した．今後の予定としては，支援機能を用いた教育の実践を行い，ファイル管理だけでなく，プロセス管理などのシステムコールも実装できるよう，機能の拡張を行う予定である．

参 考 文 献[ 1 ] Abramson, D., Foster, I., Michalakes, J., andSosič, R.: Relative Debugging: A New Methodology for Debugging Scientific Applications, Com-

システムコールを含む検証時間

引数mun. ACM, Vol. 39, No. 11(1996), pp. 69–77.
[ 2 ] Black, M. D. and Komala, P.: A Full System
x86 Simulator for Teaching Computer Organization,
Proceedings of the 42Nd ACM Technical Symposium on Computer Science Education, SIGCSE ’11,New York, NY, USA, ACM, 2011, pp. 365–370.
[ 3 ] Borunda, P., Brewer, C., and Erten, C.: GSPIM:
Graphical Visualization Tool for MIPS Assembly
Programming and Simulation, Proceedings of the37th SIGCSE Technical Symposium on Computer
Science Education, SIGCSE ’06, New York, NY,USA, ACM, 2006, pp. 244–248.
[ 4 ] Gondow, K., Fukuyasu, N., and Arahori, Y.:
MieruCompiler: Integrated Visualization Tool with
”Horizontal Slicing” for Educational Compilers,
Proceedings of the 41st ACM Technical Symposiumon Computer Science Education, SIGCSE ’10, New
York, NY, USA, ACM, 2010, pp. 7–11.
[ 5 ] Intel: 8086 16-Bit Microprocessor, 1990. http://www.ece.cmu.edu/~ece740/f11/lib/exe/fetch.php?
media=wiki:8086-datasheet.pdf.
[ 6 ] Intel: Intel 64 and IA-32 Architecture Software
Developer’s Manual, 2018. https://software.intel.com/
sites/default/files/managed/39/c5/325462-sdm-vol1-2abcd-3abcd.pdf.
[ 7 ] Nikolic, B., Radivojevic, Z., Djordjevic, J., andMilutinovic, V.: A Survey and Evaluation of Simulators Suitable for Teaching Courses in Computer
Architecture and Organization, IEEE Transactions
on Education, Vol. 52, No. 4(2009), pp. 449–458.
[ 8 ] Skrien, D.: CPU Sim 3.1: A Tool for Simulating Computer Architectures for Computer Organization Classes, J. Educ. Resour. Comput., Vol. 1,
No. 4(2001), pp. 46–59.
[ 9 ] Sondag, T., Pokorny, K. L., and Rajan, H.:
Frances: A Tool for Understanding Computer Architecture and Assembly Language, Trans. Comput.
Educ., Vol. 12, No. 4(2012), pp. 14:1–14:31.
[10] Tanenbaum, A. S. and Woodhull, A. S.: Operating Systems Design and Implementation (3rd Edition), Prentice-Hall, Inc., Upper Saddle River, NJ,USA, 2005.
[11] Urquiza-Fuentes, J. and Velázquez-Iturbide,J. A.: A Survey of Successful Evaluations of Program Visualization and Algorithm Animation Systems, Trans. Comput. Educ., Vol. 9, No. 2(2009),
pp. 9:1–9:21.