スライド 1

A Survey of
VM’04 and OSDI’04
Kenji Kaneda
1
今回サーベイする論文






Towards Scalable Multiprocessor Virtual
Machine
Using Model Checking to Find Serious File
System Errors
Enhancing Server Availability and Security
Through Failure-Oblivious Computing
Recovering Device Drivers
CP-Miner: A Tool for Finding Copy-paste and
Related Bugs in Operating System Code
Configuration Debugging as Search: Finding
the Needle in the Haystack
2
Towards Scalable Multiprocessor
Virtual Machines
Volkmar Uhlig
Joshua LeVasseur
Espen Skoglund
Uwe Dannowski
(Universitat Karsruhe)
3
Background
~ Multiprocessor Virtual Machine ~

複数の仮想MPマシンを一台のMPマシン上に構築
E.g.) VMWare ESX server, cellular disco
PU
Virtual
PU
Memory
PU
PU
Memory
PU
PU
Memory
Physical
PU
PU
PU
Memory
PU
4
Background
~ Multiprocessor Virtual Machine ~

Multiplexing multiple virtual PUs
on one physical PUs
PU
Virtual
PU
Memory
PU
PU
Memory
PU
PU
Memory
Physical
PU
PU
PU
Memory
PU
5
Problems with
Scheduling of VMs (1/2)
 spin-lock中にPUの横取りが発生しうる
 Lock-holderが横取りされると、Lock保持時
間が長くなる

その間lockの開放を待っているPUは何もできない
Lock開放待ち
Virtual
PU
Lock保持中
PU
PU
Physical
PU
PU
PU
横取り
PU
PU
PU
PU
6
Problems with
Scheduling of VMs (2/2)
各PUの性能がasymmetricになる
 Guest OSのschedulingの性能が低下する

物理PUを100%
シェア
Virtual
PU
物理PUを
50%シェア
PU
PU
PU
PU
PU
Physical
PU
PU
PU
PU
7
Research Goal

Scalable multiprocessor VM
Avoids lock-holder preemption
 Schedules jobs with knowledge of
asymmetric CPU speed

8
Lock-holder Preemption
Avoidance

Intrusive approach


Guest OSを改変する
Non-intrusive approach

Guest OSを改変しない
9
Intrusive Approach
元のゲストOSのコード
改変後のゲストOSのコード
…
lockの取得
critical sectionの実行
lockの開放
…
…
割り込み禁止をVMに通知
lockの取得
critical sectionの実行
lockの開放
割り込み許可をVMに通知
…
10
Non-intrusive Approach

以下の条件のうちいずれかが満たされたとき
のみpreemptionを許可する
user-levelで実行中
 HLT命令実行中
 protocol handlerがinvokeされたとき

11
Scheduling with Knowledge of
Asymmetric CPU Speed

Time ballooning

物理PUの割り当てに応じて、仮想的な
workloadを生成
物理PUを100%
シェア
Virtual machine
PU1のrunqueue
PU1
PU2
物理PUを
50%シェア
仮想workload
PU2のrunqueue
12
Experiments
L4Kaというmicro-kernelの上に実装
 Apache2 benchmark上でspin-lockの
性能を測定


数10%の性能向上
13
Summary

Scalable multiprocessor VM

Avoids lock-holder preemption
 Intrusive and non-intrusive approach

Schedules jobs with knowledge of
asymmetric CPU speed
 Time ballooning
14
Using Model Checking to Find
Serious File System Errors
Junfeng Yang
Paul Twohey
Dawson Engler
Madanlal Musuvathi
(Stanford University)
(Microsoft Research)
15
File System Checker (Fisc)

ファイルシステムのモデルチェッカー
C Model Checker (CMC)というモデルチェッ
カーを利用
 Abstract specificationではなくプログラムから
直にチェックを行う

16
Model Checkの概要

状態


ディスク、カーネルデータ、…
状態遷移
テストドライバによるファイルの作成、削除、…
 カーネルスレッドによるバッファのフラッシュ


チェックするinvariant

fsckでrecoverできること
 データがディスクにどんなタイミングで書き込まれても
…
17
Experiments

ext3, JFS, ReiserFSをモデルチェック

約600秒で10Kの状態を探索 (ext3)
 メタデータを破壊するという深刻なバグを発見
18
Enhancing Server Availability
and Security Through
Failure-Oblivious Computing
Martin Rinard
Cristian Cadar
Daniel Dumitran
Daniel M. Roy
Tudor Leu
William S. Beebee, Jr.
(MIT, Cambrige)
19
Background

Memory errors are a common source of
program failures
E.g.) Buffer overflow
数多くの研究がなされている
E.g.) safe-C compilers
20
Problems

多くのsafe-C compilerの実装では、
memory errorが発生すると実行がstuckする
21
Fail-Oblivious Computing (1/2)

memory errorが起きても実行し続ける
という戦略をとる計算
※ An instance of Acceptability-oriented
computing [M. Rinard OOPSLA’03]
 Replaces
the concept of program correctness
with a set of acceptability properties
22
Fail-Oblivious Computing (2/2)

Benefits
Availability
 Security
 Minimal adoption cost
 Reduced administration overhead


Drawbacks
Unanticipated execution paths
 Bystander effect

23
Implementation (1/3)

全ての文字列操作にチェックコードを挿入

以下の論文を元にしている
 R.
Jones and P. Kelly. “Backwards-compatible
bounds checking for arrays and pointers in C
programs.” In intl. workshop On Automatic
Debugging, 1997.
 O. Ruwase and M. S. Lam. “A Practical
Dynamic Buffer Overflow Detector.” In Annual
Network and Distributed System Security
Symposium, 2004.
24
Implementation (2/3)
不正なメモリ書き込み  無視する
 不正なメモリ読み込み 小さな整数値を返す


返す値を毎回変える
 無限loopに陥るのを避けるため
25
Implementation (3/3)

プログラムの一部を手動で改変

pointer in-equality comparison
26
Experiments

Applications


Apache, Sendmail, Pine, Midnight commander
Results
最大で約8倍のオーバヘッド
 実際にサーバを外部に数ヶ月公開しても大丈夫だった

27
Summary

Fail-Oblivious Computing

Enhances availability, resilience, and
security by continuing to execute through
memory errors
28
CP-Miner: A Tool for Finding
Copy-paste and Related Bugs in
Operating System Code
Zhenmin Li
Shan Lu
Suvda Myagmer
Yuanyuan Zhou
(University of Illinois)
29
Background

Copy-pasteされたコードがバグの温床とな
りやすい
E.g.) 変数名の変更し忘れ
30
Copy-pasteに起因するバグの例
…
…
for (iter = 0; iter<num_regs; iter++) {
for (iter = 0; iter<num_regs; iter++) {
prom_phys_total[iter].start_adr =
prom_prom_taken[iter].start_adr =
prom_reg_memlist[iter].phys_addr;
prom_phys_total[iter].num_bytes =
prom_reg_memlist[iter].reg_size;
prom_phys_total[iter].theres_more =
&prom_phys_total[iter+1];
prom_reg_memlist[iter].phys_addr;
prom_prom_taken[iter].num_bytes =
prom_reg_memlist[iter].reg_size;
prom_prom_taken[iter].theres_more =
&prom_phys_total[iter+1];
}
}
…
prom_prom_takenの間違い
…
31
CP-Miner

data-miningの手法を利用して、
copy-pasteによるバグを発見する
32
Overview of Algorithm (1/4)
1. ソースコードをparseし、各statementに整
数値を割り当てる

statementをtokenに分解
E.g.) 同じ型の変数には同じtokenを割り当て
E.g.) 異なる演算子には異なるtokenを割り当て

tokenの組を整数値へハッシュする
67651256
133862016
prom_phys_total[iter].start_adr = prom_reg_memlist[iter].phys_addr;
prom_phys_total[iter].num_bytes = prom_reg_memlist[iter].reg_size;
133862016
prom_phys_total[iter].theres_more = &prom_phys_total[iter+1];
8258917133
｝
for (iter = 0; iter<num_regs; iter++) {
Overview of Algorithm (2/4)
2. 各ベーシックブロックを一つのsequenceと
してまとめる

プログラム全体で得られるsequenceの集合を、
sequenceデータベースと呼ぶ
34
Overview of Algorithm (3/4)
3. あるsubsequenceで、
それを含むsequenceがデータベース中に
2つ以上存在するものを求める

CloSpanというデータマイニングのアルゴリズ
ムを用いる
35
Overview of Algorithm (4/4)
4. 色々最適化をする
E.g.) 複数のベーシックブロックを一つに結合
36
Experiments

copy-pasteされたコード断片を20分以内に
発見
Linux: 190,000個
 FreeBSD: 150,000個


copy-pasteによるバグを発見
Linux: 28個
 FreeBSD: 23個

37
Recovering Device Drivers
Michael M. Swift
Muthukaruppan Annamalai
Brian N. Bershad
Henry M. Levy
(University of Washington)
38
Background

Device Driverが原因となってシステムが落
ちることが多い
E.g.) 85% of Windows XP crashes
39
Recovering Device Drivers
デバイスドライバが落ちても、それをアプリや
OSに見せない
 ドライバを自動復旧する

40
System Overview

Shadow Driverを
新たに追加
Shadow
Sound Driver
Kernel Sound Driver
Interface Class Interface
OS Kernel
Kernel Interface
Sound Driver
Class Interface
Sound Card
Device Driver
Sound Card
41
System Overview

個々のドライバを別々の保護ドメインで実行する
Nooksという仕組みを利用
 不正なメモリアクセスが検知されたら故障とみなす

42
通常時の動作

通信のログを取得
E.g.) ioctl呼び出しを記録
Shadow
Sound Driver
Kernel Sound Driver
Interface Class Interface
OS Kernel
Kernel Interface
Sound Driver
Class Interface
Sound Card
Device Driver
Sound Card
43
故障時の動作

ログを元にドライバの復旧を行う

その間、カーネル・ドライバ間の通信
は止める
Shadow
Sound Driver
Kernel Sound Driver
Interface Class Interface
OS Kernel
Kernel Interface
Sound Driver
Class Interface
Sound Card
Device Driver
Sound Card
44
Configuration Debugging as
Search: Finding the Needle in the
Haystack
Andrew Whitaker
Richard S. Cox
Steven D. Gribble
(University of Washington)
45
Background

Configuration errors
E.g.) ファイアーウォールのポリシーの変更

いつシステムがおかしくなったかを知ることが
できれば、デバグが楽になる
46
Chronus

ユーザがprobeを与えると、故障がいつ発生
したか特定してくれるツール
47
System Overview

Time-travel disk
書きこみのログを取得する
 ある時におけるディスクの状態を復元することが
できる


μDenali virtual machine
48
故障箇所の特定

Binary search
Time-travel diskにより、ある時点でのディスク
の状態を復元
 そのディスクの状態でVMをbootして、
probeを走らせる

故障以前
故障以後
時間の流れ
49

Download Report