研究速報
表 1 Linux カーネルの規模
Table 1 The scale of Linux Kernel

コードクローン検出技術を用いた Linux カーネル進化の調査
リビエリシモネ†
松下肥後 芳樹†（正員）

誠†井上 克郎†（正員）

An Investigation on Linux Kernel Evolution using Code Clone
Detection Technique
Livieri SIMONE† , Nonmember, Yoshiki HIGO† , Member,
Makoto MATSUSHITA† , Nonmember, andKatsuro INOUE† , Member†

大阪大学大学院情報科学研究科，豊中市

Graduate School of Information Science and Technology, Osaka University,1-3, Machikaneyama-cho, Toyonaka-shi, 5608531 Japan

あらましバージョン 行数 (LOC)
1.0141,361
1.2.0∼
234,704
1.2.13
237,888
2.0.0∼
564,360
2.0.40768,061
2.2.0∼
1,310,698
2.2.26
1,970,123
2.4.0∼
2,366,218
2.4.33.4
3,864,539
2.6.0∼
4,120,925
2.6.18.3
5,475,540
総バージョン数
総ファイル数
総行数 (LOC)
総サイズ (KBytes)

サイズ (KBytes)
3,926
6,534
6,596
16,076
21,95237,05658,812
69,200112,148
120,030
157,290バージョン数
114412734
19
136
376,596
266,943,565
7,760,910

本論文では，コードクローン検出技術を用いた Linux カーネル進化の調査結果について述べ

出対象のソースコード量が大規模であるために，安直る．本論文の実験は，著者らが過去に開発した分散処に検出処理を行うのは現実的ではない．効率よくコー

理型コードクローン検出システム D-CCFinder を用ドクローンを検出することが重要である．そこで，著いて行われた．検出結果は，ヒートマップとして可視者らが過去に開発した分散処理型コードクローン検出化された．

システム D-CCFinder [2] を用いる．D-CCFinder は，キーワード

コードクローン，ソフトウェア進化，可視化

ネットワークで接続された複数台のマシンで分散してコードクローン検出を行い，検出処理の終了後にその1. は じ め に結果を 1 つにまとめて可視化を行う [3]．

コードクローンとは，ソースコード中の同一または類似したコード片を表す．近年，コードクローン検出技術が注目を集めており，著者らはこの技術がソフトウェア進化の理解に役立つと考えている．つまり，バージョン間でコードクローン検出を行うことにより，ソフトウェアがどのように進化したのかを調査することができる [1]．

本論文では，以下の理由により，ソフトウェア進化の調査対象として Linux カーネルを選択した．

•

各バージョンが充分に大規模であり，進化の調査を行う価値があると判断したため．

•

充分に多くのバージョンが公開されており，進化の調査を行うことができると判断したため．
本 論 文 で 調 査 に 用 い た の は ，Linux カ ー ネ ル

コードクローン検出は，ソースコード以外のプロジェクトの成果物を必要としない．長期間保守されて1.0∼2.6.18.3 の計 136 バージョン，総行数は約 2 億 6千万行 (総サイズは約 7.8GBytes) である．

おりドキュメントが存在しないレガシーシステムや，2. 調 査 方 法存在していても更新されておらずソースコードとの対Linux カーネルの各バージョンのペアにつき，類似応が取れていないような場合でも適用できる．
また，適切に検出結果の抽象化を行うことにより，度を算出した．バージョン Vi とバージョン Vj の類似度 Coverage(i, j) は以下の式で表される．

素早く大まかに進化の様子を知ることもできるであろう．現行プロジェクトに新規に投入された人員がソーCoverage(i, j) =スコードの理解をしなければならない場合や，運用ソLOC(CVi (Vj )) + LOC(CVj (Vi ))LOC(Vi ) + LOC(Vj )フトウェアの保守管理者が交代した場合など，分析者

ただし:が対象ソースコードに対してあまり知識を持たない

Cx0 (x1 ): x0 の中で，x1 と重複している部分，場合に特に有効ではないかと思われる．本論文では，LOC(x): x の行数．

コードクローン検出をソフトウェア進化の調査に用いバージョン Vi と Vj が完全に重複している場合，Coverage(i, j) は最大値 1 となり，全く重複していなた一例を示す．
しかし，バージョン間のコードクローン検出は，検い場合は，最小値 0 となる．

電子情報通信学会論文誌 X Vol. Jxx–X No. xx pp. 1–3 xxxx 年 xx 月

1

電子情報通信学会論文誌 xxxx/xx Vol. Jxx–X No. xx

図 1 Linux カーネルのヒートマップ
Fig. 1 Heatmap of Linux Kernel

本実験では，連続して 50 字句以上一致している部マップである．このヒートマップでは，類似度が高い分をコードクローンとして検出した．D-CCFinder をほど赤に近い色になり，低いほど白に近い色になる．

80 台のワークステーション上で実行したところ，コー

この図より，ひと目で主対角線に近い部分，つまり近ドクローン検出に約 6 時間，類似度の算出に約 50 分

いバージョン間では類似度が高いことが分かる．まを要した．進化の調査が目的であるため，バージョンた，ヒートマップ上では近い位置にあるバージョン間間のみのコードクローンを検出しており，バージョンであっても，メジャーバージョンを跨いでいる場合は，内については検出を行っていない．

そうでない場合に比べて類似度が低くなっている．こ

類似度の算出後，進化の様子を俯瞰的に表すために，ヒートマップを用いて可視化を行った．

3. 結果のことから，メジャーアップグレードはマイナーアップグレードに比べて，多くの変更が施されていることが分かる．

3. 1 主対角線に近いほど類似度が高い

3. 2 2.0 系，2.2 系，2.4 系に共通の進化パターン

図 1 は，全バージョン間の類似度を表したヒート

2.0 系，2.2 系，2.4 系の各内部には，類似度の変化

2レター

レードの違いやバックポートの特徴を効率よく確認すdriver90000

fsarchnet

ることができた．これらは，ドキュメント等を精査することにより把握することも可能であろうが，本シス

D

80000
70000

テムを利用することにより，効率よく視覚化でき，容60000

易に把握することができた．

50000

コードクローン分析はドキュメント等が存在しなく40000ても適用することができるため，その利用可能範囲は30000広いといえるであろう．

20000
10000

今後は，他のソフトウェアの進化についても調査を0行い，コードクローン検出を用いた進化分析の有益性

.0
1.42.
1.9
2.
1.00.
2.50.
20.1.025.1.0
20.2.02

5.2.0
20.3.025.3.020.4.0
2.4
2.
2.92.
2

4.1.2
2

9.1.2
24.2.2
2.2
4.
2.7
4.
2

2.1.4
2

7.1.4
22.2.4
2

7.2.4
2

2.3.4
2.3
6.
2.1
8.
.6
2.5
3.1.6
2.3
8.1.6
2を明らかにしたいと考えている．
文献

図 2 drivers，fs, arch, net の行数の変遷
Fig. 2 LOC transition of drivers, fs, arch, and net[1]

川口真司，松下誠，井上克郎，“版管理システムを用いたクローン履歴分析手法の提案，” 電子情報通信学会論文誌に共通の進化パターンが表れている．図 1 の A，B，

[2]

S. Livieri, Y. Higo, M. Matsushita, and K. In-D，vol.J89-D，no.10，pp.2279-2287，Oct 2006.

C は 2.4 系内でのパターン部分を表している．B と Coue, “Very-large scale code clone analysis and visu-の部分は類似度が高いが，A の部分はそれほど類似度

alization of open source program using distributed
ccﬁnder:が高くなっていない．

2.0 系，2.2 系，2.4 系の類似度が低くなっている各部分について詳しく調査を行ったところ，新しいハードウェアドライバ，新しいアーキテクチャ，新しい機

D-ccﬁnder,” Proc. of the 29th Interna-tional Conference on Software Engineering, pp.106115, May 2007.
[3]

S. Livieri, Y. Higo, M. Matsushita, and K. Inoue,“Analysis of the linux kernel evolution using code
clone coverage,” Proc. of the 4th Workshop on Min-能 (ネットワークプロトコルやファイルシステム) のた

ing Software Repositories, pp.22.1-22.4, May 2007.

めのコードが追加されていることがわかった．それら（平成 xx 年 xx 月 xx 日受付）の追加によるソースコード行数の変化を図 2 に示す．
図 2 から，2.0 系，2.2 系，2.4 系において，大きく行数が増加しているバージョンアップがあることが分かる．この図の D の部分は，新しいドライバとアーキテクチャの追加により行数が大きく増加している．このため，図 1 の A の部分は類似度がそれほど高くなっていない．
ソースコード中のコメントより，大きく行数が増加
している部分のコードはバックポート（注 1）によるもの
であることがわかった．このことから，2.0 系，2.2 系，2.4 系の共通進化パターンは，バックポート型開発の特徴を表しているといえるであろう．一方，2.6 系はバックポート型開発ではないために，同様のパターンが表れなかったと推測される．

4. お わ り に
本論文では，コードクローン検出を用いた Linuxカーネルの進化の様子について調査を行った．調査の結果，マイナーアップグレードとメジャーアップグ（注 1）：Linux 開発におけるバックポートとは，unstable ブランチにおいてある程度テストされ安定したと思われるコードを stable ブランチに移植する作業を指す．

3

Abstract This paper describes an investigation on Linux kernel evoluation. As a tool for analyzing it,
D-CCFinder, which is a distributed-computing code clone detection system, was used. The result is shown
as a heat map.
Key words Code clone, Software Evolution, Visualization