JAIST Repository
https://dspace.jaist.ac.jp/

Title

ネットワーク成長によるメール型ウイルスの再流行と重点的なハブの免疫化の効果

Author(s)林,幸雄; 箕浦,正人; 松久保,潤Citation

情報処理学会論文誌, 44(SIG14): 9‑19

Issue Date

2003‑11Type

Journal Article

Text version

publisher

URL

http://hdl.handle.net/10119/3414

Rights社団法人 情報処理学会, 林幸雄／箕浦正人／松久保潤, 情報処理学会論文誌 : 数理モデル化と応用,
44(SIG14), 2003, 9‑19. ここに掲載した著作物の利用に関する注意: 本著作物の著作権は（社）情報処理学会に帰属します。本著作物は著作権者である情報処
理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。 The copyrightof this material is retained by the Information
Processing Society of Japan (IPSJ). This material
is published on this web site with the agreementof the author (s) and the IPSJ. Please becomplied with Copyright Law of Japan and the Codeof Ethics of the IPSJ if any users wish to
reproduce, make derivative work, distribute or
make available to the public any part or whole
thereof. All Rights Reserved, Copyright (C)Information Processing Society of Japan.

Description

Japan Advanced Institute of Science and Technology

Vol. 44

No. SIG 14(TOM 9)

Nov. 2003

情報処理学会論文誌：数理モデル化と応用

ネット ワーク成長によるメール型ウイルスの再流行と重点的なハブの免疫化の効果
林

幸

雄†

箕

浦

人†

正

松 久 保

潤†

電子メールの送受信数の実測分布に基づく接触関係を考えた，コンピュータウイルスの拡散モデルを提案する．その基本特性として，ウイルスの実行率や発見率に対する，総感染 PC 数（ 潜伏から増殖状態に移行した数），総感染メール数（ウイルス感染が発見されたものを含む），絶滅までの時間をシミュレーション解析する．特に，感染の鎮静化後の再流行現象が新規ユーザの加入によって起こることを，開放系の本モデルは示唆する．経験上典型的なこの現象は，従来モデルでは説明できないものである．さらに，重点的なハブ頂点のアンチウイルスによる免疫化の効果を明らかにする．

Recoverable Prevalences of Viruses via E-mails in a Growing Computer
Network and Eﬀectiveness of the Prior Immunization for Hubs
Yukio Hayashi,† Masato Minoura† and Jun Matsukubo†
We propose a model of computer viruses via electronic mails, based on the contacts in real
distributions of the sent and receive mails. As the fundamental properties for the rates ofexecution and detection, we analyze the numbers of total infectious computers (executed fromthe hidden to the propagatable state), total infected mails (including detected viruses), andthe extinction time by simulations. In particular, this model in an open system suggests thata growing computer network with new mail users causes the recoverable prevalences froma low level of disease. This phenomenon is typical in experiences but not explained by theconventional models of computer viruses. Moreover, we verify the eﬀectiveness of the prior
immunization by anti-viruses for hubs in the scale-free network.

1 件のウイルスあたりでは 10〜20 億ド ルと推定され

1. ま え が きている☆ .

インターネットの急速な普及にともなって，コン

一方，増え続けるウイルスの中で本当に問題となる

ピュータウイルスの浸透度，脅威とも年々増大し，まのは，わずか数%の 10 種類程度にすぎない9) が，そすます深刻な社会問題となっている．なかでも，電子れらの時間的な挙動や被害の大きさに関する個々の観

メールによるウイルス感染は被害全体の 70〜80%以上

測データすら，現状では十分に得られているとはいい6),7),9)，日常的な情報の交換や共有の際の添付ファがたい（ 複合的な要因の累計が多い）．そこで，少しイルなど を悪用するため，フロッピなど を介し た感でも被害を抑えるためには観測のみならず，ウイルス染経路とは比べものにならないほど強い感染増殖力を亜種の系統解析やシミュレーションによる増殖力の予持っている．また，感染によるハードディスクのフォー

測なども用いて，対策を検討する必要がある．

でマット（データの破壊）やファイルの削除などの直接コンピュータウイルスの対策に関する研究には，個々的な被害のみならず，感染の発見や駆除，復旧作業にのウイルスの発見と駆除を目的としたミクロレベルの要する業務停滞，増殖活動による機密情報の漏洩やウ

研究と，ネットワーク上のウイルスの拡散伝搬特性のイルス散布による社会的信用の低下などの間接的被害

解明や効果的なネットワークの免疫方法を探るマクロをもたらし，その損害額は想像以上に大きい．たとえレベルの研究があり21) ，本論文では後者を扱う．

ば，米国における，ウイルス駆除，生産能力の損失，

これまで，コンピュータウイルスの拡散モデルにお復旧作業による損害額の合計は年間 100〜200 億ドル，いて，シミュレーションによるランダムネットワーク† 北陸先端科学技術大学院大学知識科学研究科
School of Knowledge Science, Japan Advanced Institute of Science and Technology☆

9

http://itpro.nikkeibp.co.jp/free/ITPro/USNEWS/
20010907/10/

10

情報処理学会論文誌：数理モデル化と応用

Nov. 2003の直径と拡散速度や定常状態の感染数，完全グラフ上

まず 2 章では，電子メールによるウイルスの典型的の理論解析による駆除率の限界が報告されている21) ．

な行動パターンと，送受信数の分布に関して説明した

また，電子メールによる拡散の特徴を考慮したモデル

後，その実測データに基づいた接触関係を表す具体的では，1 次元格子上の限定ケースの理論解析と，よりなネットワークモデルの構成手段を提示する．3 章で一般的な 1 次元格子上のシミュレーションによる接続

は，ウイルスの実行率や発見率に対する，総感染数や数と感染率の関係，アンチウイルスによる拡散抑止効

絶滅時間に関する基本特性を明らかにする．4 章では，果などが示されている16) ．しかしながら，一様ラン

開放系のモデルにおける，再発的な流行現象とハブのダムや完全グラフは，均一なウイルスとの接触機会を免疫化の効果を示す．最後に 5 章では得られた結果を表すため現実的なモデルとはいいがたく，あくまで比まとめ，今後の課題について述べる．

較のための指標を与えているにすぎない．格子モデルには接触機会の局所的な偏りが多少あり，アンチウイ
ルスの配置箇所の重要性が指摘されている16) ものの，現実的なネットワーク構造上の効果的な配置方法は検討されていない．

2. 電子メールによるウイルス感染
2.1 ウイルスの行動パターン
コンピュータウイルスには，感染するターゲットによる分類で，実行ファイル型，マクロ・スクリプト型，一方，社会的な知人関係などを表す SF（ Scale-Free ）3)

ブートセレクタ型などがあり，また，その挙動によるの特徴として，絶滅の主な分類で，他のプ ログラムに感染するプ ログラム

しきい値が存在しないこと，すなわち，感染率をどんなとしての狭義のウイルス，ネットワークを介して増に小さくしても広がっていくことが SIS（ Susceptible-

殖するワーム，正規ソフトを装った単体で動作すると呼ばれるネットワーク構造

Infected-Susceptible ）モデルの平均場解析から最近示

不正な（ 他のプ ログラムに感染はしない ）トロイのされ 19) ，従来の疫学の常識を覆した．また，感染の発見

木馬などがある．その典型的な行動パターンは，未と駆除の後に永続的な免疫を持つ，SF ネットワーク，潜伏（ Hidden Infected ），増殖
感染（ Susceptible ）上の SIR（ Susceptible-Infected-Recovered ）モデル

，発病の順に遷移する14) ．
（ Infectious ）11),15)．さらに，SF ネッ

本論文では，電子メールによるウイルスの拡散伝搬トワークにおいてはハブがアキレス腱となる（出次数に焦点を絞っているので，ワーム活動を行うものを対の拡散特性も解析されているが大きいハブ頂点が故障するとネットワークが極度に象とするが，感染したことの発見を逃れるための潜伏分断される）こと1) を逆に利用して，重点的なハブのの仕方や，発病後の個々のコンピュータ（以後 PC と免疫化によって拡散が抑えられることが SIS モデルの呼ぶ）におけるファイル削除やメモリ浪費などの破壊理論解析から示されている4),20) ．
上記のモデル 11),15),16),19),21) ではネットワークの規的行為に関しては議論しない．また，ターゲットとしては主にファイルやマクロ・スクリプトを考え，ユー，ウイル
模は固定され（あるいは N → ∞ において）

ザ操作による実行や時限起動などの細かな区別をしな

スが広く蔓延するか絶滅するか，どちらかの定常状態

いかわりに，アドレス帳などを介して増殖するウイル

しか議論されてないが，実際の観測データはこれらとスを広く扱う．しかも，メールの受信や履歴閲覧の際は少し異なる．すなわち，ネットワークは日々成長しに，特定のタイトルや添付ファイルなどからウイルスているし，少数の感染源から拡散伝搬によって徐々にを発見した場合，駆除操作の後には再度感染しない免

広がり，感染数の上昇下降のしばらく後に再流行する

疫（ Recovered，Immune ）状態を考慮する．

という共通のパターンがある8),9),23) ．
本論文では，実際の電子メールの送受信関係が SF

さて，電子メールの送受信関係を表すネットワーク
を考える．その頂点 i = 1, . . . , N は各 PC を，有向ネットワーク構造となることを示し，その現実的な接辺はアドレス帳などに登録された PC 間のメールの送

触機会上の拡散伝搬の特性を明らかにする．特に，定受信関係を表す．個々の PC の状態は，実際の挙動に常的な蔓延や絶滅ではなく，従来のモデルでは説明で近いよう，図 1 に従って確率的に遷移する16) ものと

きない，いったんは感染が鎮静化した後に再流行するする．ここで，λ は潜伏状態 H から感染状態 I への現象8),9),23) を，（ 開放系の上記のモデルにおける）新実行率，δ は感染の発見率とする．また，頂点 i にお規ユーザによるネットワーク成長が引き起こすことをける PC が保持する ni 個のウイルス（ 感染メール ）示唆する．さらに，この開放系のモデルにおいても，から，どれか 1 つでもウイルスが発見される確率は重点的なハブの免疫化によってウイルスの拡散が効果

1 − (1 − δ)ni , ni 個の潜伏状態からどれか 1 つでも増殖状態に移行する確率は 1 − (1 − λ)ni となる．これ

的に抑えられることを示す．

Vol. 44

No. SIG 14(TOM 9)
detection fromreceive-mails

ネットワーク成長によるメール型ウイルスの再流行

11

1 − (1 − δ) n i

propagation by sent-mails
receive-mails

.
.
.

. . .

Susceptible

Hidden infected

Recovered(Immune)Infectious

execution(1 − δ)n i

1 − (1 − λ) n i

1 − (1 − δ) n i

detection by
infected diseases

detection befor the infectionsin the latents 1 − (1 − δ) n i

図 1 S-H-I-R 状態遷移図
Fig. 1 S-H-I-R state transition diagram.

図 2 送信メール数のべき乗分布
Fig. 2 Power law distribution for sent-mails.

らの状態遷移は確率的に行われるが，時間の経過にともなって各頂点はいずれは免疫状態 R となる点に注意しよう．

• 未感染状態 S の PC は，感染した相手からメールを受信した時点でウイルスに感染する．
• 受信の際，複数の相手からの受信メール（ ni 個）のうち，どれか 1 つでもウイルスが発見されれば，免疫状態 R になって，その後，再感染することはない．

図 3 受信メール数のべき乗分布
Fig. 3 Power law distribution for receive-mails.

• 一方，受信メールから感染しても，すぐにウイルスの増殖活動（ 感染メールの送信）を始めず，潜伏状態 H となる．

数がある偏った分布となることが報告されている．実• 潜伏状態 H から次のステップで，ni 個のうちでどれか 1 つでも増殖状態 I になれば，通信相手にと，図 2 と図 3 のようなべき乗則☆☆ に従う．これらか

感染メールを送る（ただし，発見されにくいよう，ら，送受信数の分布のべき係数はそれぞれ γout = 2.5，

際，これらの送受信数の分布を両対数のグラフで表す

同じ相手には 2 度以上感染メールを送信しない）．

γin = 1.9，平均送受信数 k̄ は 5〜20 通程度と推定さ

あるいは，潜伏状態 H でウイルス感染したことれる．

が発見されて，免疫状態 R となる．

• 増殖状態 I でもウイルス感染したことが発見されれば，免疫状態 R となる．各 PC が状態 I や H
で保持するウイルスの個数 ni はステップごとに増加し うるが，最大でも各頂点 i の入次数分である．

2.3 構成的な (  ) モデル

前節の実測データに内在するべき乗則に従った送受
信関係を表現する，ネットワークモデルの具体的な構成手段を述べる．
べき乗則は，インターネットのルータ，WWW のリンク，電力網，知人関係など 現実の大多数のネット

2.2 電子メール送受信数の分布
次に，実測データに基づいて，電子メールの送受信関係を表すネットワーク構造（ 平均辺数 k̄ や次数分ワークは以下の単純かつ自然な 2 つの生成原理に従布）を考える．

う3) ．

通信総研と東大社会情報研による’00 年 10〜11 月のワークに共通する普遍特徴としてきわめて重要である2) ．驚くことに，このような特徴を持つ SF ネット

Growth： 新しい頂点を追加しながら，時間的にグ調査12) では，1 日の送受信数の最頻度は 1〜10 通，平均送信数は 16.3 通，平均受信数は 27.7 通で ，送受信☆

☆

他の調査では，情報通信総研によって’99 年 4 月に行われた，郵送によるアンケート結果では 1 日の平均送受信数は 6.2 通，インターネットによるアンケート結果では 14.8 通となっている．
http://www.commerce.or.jp/result/sp3/index.html’02 年 2 月に 発表され た電通によるデジ タルラ イフ 調査では，平均送信数は 2.9 通，平均受信数は 5.1 通となっている．

ラフが成長していく．

Preferential Attachment： 新しく追加された頂点よりも，すでに存在している頂点の方が，辺が張☆☆

http://www.dentsu.co.jp/marketing/digital life/
各頂点の辺数を表す，次数 k を持つ頂点の頻度が，k −γ に比例すること．係数 γ の値は対象とするネットワークごとに多少異なるが，実測値でおよそ 2 から 3 である2) ．

12

情報処理学会論文誌：数理モデル化と応用

Nov. 2003

表 1 α-β コインによる辺の生成
Table 1 Edge generation by the α-β coin.
確率

α

1−α

β
1−β

新頂点の自己ループ
終点は新で，始点は既存

終点は既存で，始点は新頂点
ともに既存の頂点

られやすく，その頻度は辺の数に比例する（ rich-get-richer 現象）．
SF ネットワーク構造上のウイルスの拡散伝搬のシ
ミュレーションを行うため，平均場近似による解析向きモデル 3) よりも，上記の生成原理に従いつつ，べき乗の傾きが制御できる構成的な (α, β) モデル 10) に着

図 4 総感染 PC 数の比
Fig. 4 Rate of the total infectious PCs.

目する．(α, β) モデルでは，頂点の追加（ Growth ）ごとに κ 本の辺を，表 1 のようにパラメータ α，β の値

γin =

1
,
1−α

γout =

1,
1−βに従って確率的に生成することを，ある頂点総数 N になるまで繰り返す18) ．ただし，生成途中で仮に作られた孤立点，自己ループ，多重辺は削除する☆ . また，既存の頂点を追加辺の始点あるいは終点とする場合，各頂点の入次数と出次数に比例した頻度（ Preferential

Attachment ）でそれぞれの頂点が選ばれるものとする．

3. 拡散伝搬と絶滅時間の基本特性
確率的な実行や発見のない拡散伝搬のみの特性とし

図 5 総感染メール数の比Fig. 5 Rate of the total infected mails.

て，一様ランダムなネットワークでは平均辺数が 3 本
以上あれば任意の初期頂点から全体の 90%以上に蔓延するが，収束までの時間（ ステップ数）は規模 N に比例するのに対して，SF ネットワークでは平均辺数が 5 本以上で蔓延する一方，収束までの時間はほとん
ど 規模によらないことが明らかになっている13),18) ．
本章では，確率的な状態遷移に基づく拡散伝搬と絶滅状態への収束に関する特性を述べる．具体的には，前章の手順で構成した N = 2000 の SF ネット
ワーク上の SHIR モデル（図 1 ）において，最も伝搬しやすい出次数最大のハブを初期感染源 I とし（ 他，実行率のすべての頂点の初期状態は未感染状態 S ）λ = 0.1, . . . , 0.9, 発見率 δ = 0.1, . . . , 0.9, 平均辺数

図 6 絶滅までのステップ数
Fig. 6 Number of steps until the extinction.

k̄ = 6.8〜19.7 のそれぞれの組合せに対して，絶滅するまでの確率的な状態遷移を 100 回試行した．
図 4，図 5，図 6 は，総感染 PC 数（増殖状態 I における，菱形，四角，三角，× の各記号は平均辺数する比，総感染メール数（感染が発見されたものを含k̄ = 6.8, 10.1, 15.2, 19.7 に，黒線，青線，赤線は発見
率 δ = 0.1, 0.5, 0.9 にそれぞれ対応する．
図 4 に示す総感染 PC 数は，実行率 λ が大きくなむ）の比，絶滅までのステップ数（日数に相当）につるほど増加するが，線色で区別した発見率 δ が大きくいての，100 回試行の平均値をそれぞれ示す．図中になるに従って抑えられる．ただし，各記号の平均辺数ゆえに，平均辺数は k̄ < κ となり，その値も確率的に決まる．

k̄ には，ほとんど依存しない．一方，図 5 に示す総感
染メール数は，平均辺数 k̄ が大きいほど増加する．実

移行した数）の δ = 0 の場合の最大感染 PC 数に対☆

Vol. 44

No. SIG 14(TOM 9)

ネットワーク成長によるメール型ウイルスの再流行

図 7 固定規模における感染数の変化
Fig. 7 Time-series of num. of the infected at a fixed size.

13

図 8 線形成長における感染数の変化
Fig. 8 Time-series of num. of the infected in a linear
growth.

行率 λ が大きくなるほど ，また，発見率 δ が小さくなるほど ，増加する点は総感染 PC 数と同様である．
図 6 に示す絶滅までの時間には，黒線の δ = 0.1 の場合以外は，平均辺数 k̄ に対する依存性はほとんど見られず，線色で区別した発見率 δ の値のみに依存したほぼ一定値となっている．発見率が低い δ = 0.1 のときは，実行率 λ が大きくなるに従って絶滅までの時間が減少し ，平均辺数 k̄ が大きいほど 早い段階で収束している．λ や k̄ が大きいほど 早く絶滅するのは，いったん広がった複数の感染メールから発見され
図 9 指数成長における感染数の変化
Fig. 9 Time-series of num. of the infected in an
exponential growth.

やすくなるためと考えられる．
図 7 は，ネットワーク規模 N を固定した場合の
感染数

N

i=1

ni（各時刻の状態 H+I の保有ウイルス数）の典型的なパターン（感染が広がった後，比較的る再流行現象の典型例を示す．再流行の原因は，絶滅

緩やかに絶滅状態に収束すること ）を示す．ここで，しかけたほんのわずかな感染 PC が未感染の新規ユー

次章に示すネットワーク成長モデルとの比較のため，

ザ PC を介して，再度増殖する機会を得ていくためとN = 18934，λ = 0.1，δ = 0.04，k̄ = 6.6 とし ，感染源 I をランダムに選んだ 5 個の頂点とした．

考えられる．
次に，重点的なハブの免疫化の効果を図 10，図 11

4. 開放系のウイルス伝搬モデルに示す．グラフの上から順に黒線：ウイルス発見のみ

4.1 確率論的 SHIR モデル

従した頂点の免疫率 10%，青線：20%，赤線：30%に初期規模 N = 400 で構成した SF ネットワークか

対する，100 回の試行☆☆ の平均感染数（ 状態 H+I のら，ウイルスの拡散伝搬をともなう確率的な状態遷移数）の変化をそれぞれ表す．ただし，ウイルス発見にによる Normal な駆除，緑線：ネットワーク成長に追の各ステップごとに，2.3 節で述べた手続きに従って，

よって免疫状態になった頂点とは別に，30 ステップ

線形成長：

ごとに成長した規模に対する比率で，出次数が大きい+50 個ずつの頂点と対応する辺を追加，指数成長： ×1% ずつの頂点と対応する辺を追加，（ハブ ）順にあるいはランダムに頂点を免疫化する☆☆☆ ．

のど ちらかの方法で成長していく 開放系のモデルを

図 10，図 11 の線形成長と指数成長ともに，ハブ考える．その際，パラメータなどは図 7 と同じ 条件

頂点の免疫率を上げるに従って感染数が減少し，免疫とし，ステップ数 400 回で線形成長と指数成長のネッ

率 30%（赤線）ではほぼ絶滅させるまでに至っている☆

トワーク規模 N がそれぞれ同程度（ 20350 と 18934 ）となる．以後，400 ステップまでで議論するが，図 8，
図 9 はそれ以降を含めた，線形成長と指数成長におけ☆

実際は，線形成長と指数成長の中間的な成長の仕方と考えられる．

ランダムな 10 種類のネットワーク生成 ×10 回の確率的な拡散伝搬による 100 回の試行．
☆☆☆
計算時間の節約以外，30 という数自体には日数程度の意味しかないが，アンチウイルスのインストールや更新など の作業が必
要な免疫化よりも，（ 毎ステップごとの）ウイルスの状態遷移の方が進行が速いことを表す意味で，妥当と考えられる．
☆☆

14Nov. 2003

情報処理学会論文誌：数理モデル化と応用

図 10 線形成長におけるハブ免疫化
Fig. 10 Hub immunization in a linear growth.

図 12 線形成長におけるランダム免疫化
Fig. 12 Random immunization in a linear growth.

図 11 指数成長におけるハブ免疫化
Fig. 11 Hub immunization in an exponential growth.

図 13 指数成長におけるランダム免疫化
Fig. 13 Random immunization in an exponential growth.

（ただし ，完全絶滅ではなく数個のウイルスは存在す

表 2 線形成長（ 上）と指数成長（下）の不完全絶滅頻度
Table 2 Frequency of non-complete extinctions in a
linear (top) and exponential (bottom) growth.

る）．一方，図 12，図 13 に示すランダムな頂点の免疫化では，免疫率を上げるに従って感染数が若干減少するものの，30%でも絶滅から程遠い．
ここで，ウイルスの実行や発見は確率的に行われるため，なかには 400 ステップ までに完全に絶滅する場合も存在する17) ．図 10〜13 の線形成長と指数成長の場合において，100 回の試行中で完全に絶滅しな

ImmuneHubRandomNormal
100
100

10%
92
96

20%
35
92

30%
6
70

ImmuneHubRandomNormal
50
50

10%
77
38

20%
73
29

30%
10
23

かった頻度を表 2 にそれぞれ示す．指数成長におけるハブに対する免疫率 10%や 20%で不完全絶滅頻度が回試行の平均値を図 16，図 17 に示す．図 16 では，Normal よりも増え，免疫化が逆効果のようにも見え免疫化されたハブの頂点数（三角印）がウイルス発見

るが，図 14，図 15 に示すように 400 ステップまでのによる状態 R の頂点数（ 四角印）よりも圧倒的に多（ 100 試行の平均の）総感染数は，免疫率を上げるにく支配的で，特にその傾向はステップ数が大きくなる

従って大きく減少している．図中，Hub と Ran はそほど顕著になっている．ここで，点線は免疫化するハ

れぞれハブとランダムに選んだ頂点に対する免疫化，ブとして（ 図 17 ではランダムに ）選ばれた頂点がす

括弧内の記号は（ H や I の）状態数を表し，Ex は前でに状態 R になっていた場合を表し，ステップ数によ記の再流行以外の完全に絶滅した場合を示す．完全にらず免疫化されたハブ全体の 1 割以下（ 図 17 では半

絶滅していない（再流行する）場合の総感染数におい分程度）となっている．一方，ランダムな免疫化の場ても，せいぜい半分に減少のランダムな免疫化より，

合の図 17 では，ステップ数を大きくするに従ってそ

1/6 以下の減少を示すハブの免疫化に効果がある．
上記の免疫率 30%の線形成長の場合で，30 ステッ
プごとに免疫化された頂点数とウイルス発見数の 100の比率は減少するものの，ウイルス発見数（ 四角印）
がランダムに免疫された頂点数（三角印）と同程度になっている．

Vol. 44

No. SIG 14(TOM 9)

ネットワーク成長によるメール型ウイルスの再流行

図 14 線形成長における総感染数の比較
Fig. 14 Comparison of the total infected in a linear
growth.

15

図 18 免疫状態の頂点数（ ハブ免疫化 10% ）Fig. 18 Number of vertices in state R (hub immunization
10%).

図 15 指数成長における総感染数の比較
Fig. 15 Comparison of the total infected in an
exponential growth.

図 19 免疫状態の頂点数（ランダム免疫化 10% ）Fig. 19 Number of vertices in state R (random
immunization 10%).

図 16 免疫状態の頂点数（ ハブ免疫化 30% ）Fig. 16 Number of vertices in state R (hub immunization30%).
図 20 免疫状態の頂点数（ ハブ免疫化 20% ）Fig. 20 Number of vertices in state R (hub immunization20%).

図 17 免疫状態の頂点数（ランダム免疫化 30% ）Fig. 17 Number of vertices in state R (random
immunization 30%).

図 18，図 19 に示す免疫率 10%の場合は，ウイル
ス発見数と免疫化された頂点数の大小関係が逆転する．図 20，図 21 に示す免疫率 20%の場合は，10%と図 21 免疫状態の頂点数（ランダム免疫化 20% ）Fig. 21 Number of vertices in state R (random
immunization 20%).

16

Nov. 2003

情報処理学会論文誌：数理モデル化と応用
a=0.1, b=0.1, c=0.7, S(0)=1.8, I(0)=0.2

a=0.01, b=0.1, c=0.7, S(0)=1.8, I(0)=0.2

15

15
S(t)
I(t)

S(t)
I(t)
10
S(t) and I(t)S(t) and I(t)

10

5

0

5

0

0

100

200

300

400

500

0

100

200

Time

300

400

500

Time

図 22 線形成長における S(t) と I(t)Fig. 22 S(t) and I(t) in a linear growth.

図 24 指数成長における S(t) と I(t)Fig. 24 S(t) and I(t) in an exponential growth.

a=0.1, b=0.1, c=0.7, S(0)=1.8, I(0)=0.2

a=0.01, b=0.1, c=0.7, S(0)=1.8, I(0)=0.2

50

300

40

250
200
R(t)

R(t)

30
150

20
100

10

0
0

50

100

200

300

400

0
0

500

100

200

300

400

500

Time

Time
図 23 線形成長における R(t)Fig. 23 R(t) in a linear growth.

図 25 指数成長における R(t)Fig. 25 R(t) in an exponential growth.

30%の中間的な結果となった．指数成長の場合も上記的な振動現象が例示されている8) が，例示以外ではどと同様で，特にウイルス発見数に対する免疫化されたんなトポロジーに起因するのか明らかになっていない．

ハブの頂点数の比率がさらに大きくなる．これら図 16，

本 節で は ，前 節の 確 率 論 的モデ ル に 対 応 す る ，

図 17 を先の結果（ 図 10〜15 ）と合わせて考えると，

ネット ワーク成長をともなう決定論的な Kermack-

感染数の激減や絶滅にはウイルス発見よりもハブの免

McKendrick モデルについて議論する．その際，潜疫化が効果的であることがより鮮明になる．

伏状態 H を省略し，接触関係を homogeneous に近似

4.2 決定論的 homogeneous 近似

して単純化することで，再流行現象がネットワーク構伝染病に おけ る理論解析のための ，決定論的な造より成長に起因することを示唆する．

Kermack-McKendrick モデルにおいて，規模を固定

まず，線形成長の SIR モデルは，した場合は感染率があるし きい値以上ならいったん

制もなく成長し続けているコンピュータネットワーク

dS(t)= a − bS(t)I(t),
(1)
dt
dI(t)
= bS(t)I(t) − cI(t),
(2)
dt
dR(t)
= cI(t)(3)dtと表される．ここで，未感染数 S(t)，感染数 I(t)，免疫数 R(t)，ネットワーク規模 N (t) = S(t)+I(t)+R(t)，にはそのままではあてはまらない．

係数 a, b, c > 0，初期値 S(0), I(0) > 0，R(0) = 0 と広がった後に絶滅する挙動しか表現できないが，出生（ネットワーク成長）を考慮すると再発的な流行現象が起こることが知られている22) ．ただし，出生率と死亡率を同一とした総人口が一定の場合や，競合項（縄張り争い）を持つモデルが主に議論され，特に何の規一方，接触関係の空間的な局所性の観点から，再発する．

Vol. 44

No. SIG 14(TOM 9)

ネットワーク成長によるメール型ウイルスの再流行

上記の連立微分方程式 (1)〜(3) を，ステップ幅 ∆t =10−4 とした 4 次の Runge-Kutta 法によって求めた

17

5. む す び

結果を，図 22，図 23 に示す．S ，I が dI/dt = 0 とコンピュータウイルスの被害の中で，電子メールに

dS/dt = 0 にそれぞれ対応する平衡解 S ∗ = c/b とI ∗ = a/c に収束し，R > 0 は減衰振動しながら線形よるものは 70〜80%以上で 6),7),9) ，その損害も大きい．
そこで，個々の駆除のためのアンチウイルスの開発のに増加している．

みならず，その効果的なネットワーク上の配置から拡

また，解 N (t) = N (0) + at を持ち，S(t) と I(t)の級数展開は，

散伝搬による被害を抑えることが望まれる．
従来のコンピュータウイルスの拡散モデルでは，解S(t)≈ 1.8 + 0.08t + 0.00856t2 − 0.0014501t3
45

6+0.0002008t − 0.0000250t + O(t ),I(t)≈ 0.2 − 0.104t + 0.02784t2 − 0.0050458t3+0.0006821t4 − 0.0000704t5 + O(t6 ),となる（ R(t) は N (t) − S(t) − I(t) ）．
一方，指数成長の SIR モデルは，

dS(t)= aN (t) − bS(t)I(t),
(4)
dt
dI(t)
= bS(t)I(t) − cI(t),
(5)
dt
dR(t)
= cI(t)(6)dtと表される．同様に式 (4)〜(6) を 4 次の Runge-Kutta
法によって求めた結果を図 24，図 25 に示す．S のみ
が dI/dt = 0 に対応する平衡解 S ∗ = c/b に収束し ，I, R > 0 は減衰振動しながら指数的に増加している．

析に適した一様ランダムや完全グラフ21) ，一次元格子などのネットワーク構造が扱われ，電子メールによるウイルス感染の接触機会の偏りが指摘されている16)
ものの，実際の送受信数に基づいたネットワーク構造
や，アンチウイルスの配置方法は明らかでなかった．
一方，社会的な知人関係などを表す SF ネットワーク
構造上の SIS モデルでは，絶滅のしきい値が存在しな
いこと19) や，重点的なハブの免疫化によって拡散が抑えられることが，平均場解析から最近示された4),20) ．
しかしながら，これらのモデルではネットワーク規模が固定され（あるいは N → ∞ ），ウイルスの蔓延か絶滅の定常状態しか議論されておらず，観測データに見られる再流行現象8),9),23) を説明できなかった．
本論文では，電子メールによる拡散モデル 16) を基に，

• 実際の送受信関係12) がべき乗分布に従う SF ネッ
トワーク構造となる☆ ことを示し，その現実的な接触関係上の拡散伝搬の基本特性を明らかにした．

また，解 N (t) = N (0)eat を持ち，特に，増殖状態への実行率 λ や平均辺数 k̄ が大S(t)きいほど ，いったん広がった複数の感染メールか≈ 1.8 − 0.16t + 0.0962t2 − 0.0173206t3+0.0002487t4 − 0.0000308t5 + O(t6 ),らウイルスが発見されやすくなって結果的に早くI(t)≈ 0.2 − 0.104t + 0.02688t2 − 0.0045339t3+0.0005457t4 − 0.0000453t5 + O(t6 ).

に増えると思われる平均送受信数に相当するので，一時的な被害範囲の拡大が起こりうる．
• また，新規ユーザによるネットワーク成長によっ

前節の確率論的 SHIR モデルとの対応では，t ≈ 300て，再流行現象が引き起こされることを，確率論で線形成長と指数成長が同程度の規模となり，図 22，

的および決定論的な双方のモデルから示唆した．

図 24 の実線の I(t) は 0 ≤ t < 300 において，それ絶滅することが分かった．ただし，k̄ は今後さらな再流行現象を表している．一般に確率論的モデルの• さらに，重点的なハブの免疫化によって，再流行する可能性があるウイルスの拡散伝搬も効果的に抑えられることを示した．

平均値は決定論的モデルに対応するものの，個々の挙ランダムな免疫化では再流行が防げない場合でも，

ら確率論的モデルにおける図 8，図 9 と定性的に同様

動では必ずしも大小関係が一致しないこと17) や，初ハブの免疫率を 30%以上にすればほとんど 絶滅

期感染数は 0 でなく I(0) = 0.2 であることに注意さし（ 表 2 より 9 割は完全絶滅），総感染数も大幅

れたい．また，決定論的モデルにおける再流行のタイ（図 14 より 1/6 以下）に減少することが分かった．

ミングや大きさが，確率論的モデルにおける+50 や以上，実際の送受信関係に基づくウイルスの拡散伝

×1%などのネットワーク成長率に対応する係数 a，ウ
イルスの実行率 λ や発見率 δ に対応する係数 b や c

搬の基本特性，新規ユーザによる再流行現象，重点的なハブの免疫化の効果が明らかになった．また，ハブ（平均辺数 k̄ の影響は b に含まれる）に依存する点も同様である．

☆

独 Kiel 大のメールサーバのログ解析でも同様な報告がある5) ．

18

情報処理学会論文誌：数理モデル化と応用を見つけるには，接続辺を順にたどる単純な幅優先探索ではうまくいかないことを我々は経験的に見つけ，より効率的な探索法についてもすでに検討しているが，その内容に関しては別の機会に報告したい．
本論文のモデルでは，ウイルスの実行率や発見率は時間的に一定で，さまざまな送受信相手を表現できる
よう確率的に生成されたネットワークが成長するものの，辺の付け換えは行っていない．一方，電子メール
によるウイルスの特徴をさらに詳細にとらえれば，たとえば ，送受信リスト中の相手が大きく変わったり，
広く蔓延したウイルスには特に注意して対策を講じるなど 発見率も変化することなどが考えられる．また，誰もがメーリングリストを利用すれば広範囲に送信可能であり，ハブとなるヘビーユーザも固定できないかもしれない．いたずらに詳細化することは好ましくな
いが，こうした電子メールの特徴を必要に応じてさらにふまえた検討や，感染数の観測データの整備，それらデータとの比較によるモデルの洗練化などが今後の課題として考えられる．
謝辞 本研究の 一部は ，文部科学省科学研究費

13680404 の援助を受けている．

参

考 文

献

1) Albert, R., Jeong, H. and Barabási, A.-L.: Error and attack tolerance of complex networks,
Nature, Vol.406, pp.378–382 (2000).
2) Albert, R. and Barabási, A.-L.: Statistical Mechanics of Complex Networks, arXiv: condmat/0106096v1 (2001).
3) Barabási, A.-L., Albert, R. and Jeong, H.:
Mean-ﬁeld theory for scale-free random networks, Physica A, Vol.272, pp.173–187 (1999).
4) Dezsö, Z. and Barabási, A.L.: Halting virusesin scale-free networks, Physical Review E,
Vol.65, 055103 (2002).
5) Ebel, H., Mielsch, L.-I. and Bornholdt, S.:
Scale-free topology of e-mail networks, Physical Review E, Vol.66, 035103(R) (2002).
6) 情報処理振興事業協会：平成 12 年度国内におけるコンピュータウィルス被害状況調査，平成 13
年 2 月 (2001).
7) 情報処理振興事業協会セキュリティセンター：
国内におけるコンピュータウィルス被害状況調査，
平成 14 年 3 月 (2002).
8) Kephart, J.O. and White, S.R.: Measuringand Modeling Computer Virus Prevalence,
Proc. 1993 IEEE Comp. Soc. Symp. on Res.
in Security and Privacy, pp.2–15 (1993).
9) Kephart, J.O., Sorkin, G.B., Chess, D.M. andWhite, S.R.: コンピュータウィルス vs. デジタル

Nov. 2003

免疫系，日経サイエンス (Feb. 1998).
10) Kumar, R., et al.: Extracting large-scale
knowledge bases from the web, Proc. 25th
VLDB Conf., pp.7–10 (1999).
11) May, R.M. and Lloyd, A.L.: Infection dynamics on scale-free networks, Physical Review E,
Vol.64, 066112 (2001).
12) 三上俊治：日本人とインターネット生活—ワー
ルド インターネットプロジェクト (2001).
http://sophy.asaka.toyo.ac.jp/users/mikami/
info&media/
13) 箕浦正人，林 幸雄：さまざ まなネットワーク
における情報伝播と構造の特徴，電気関係学会北陸支部連合大会，講演論文集 C-49, p.185 (2002).
14) 日経 NETWORK：感染，潜伏，増殖，発病 —典型的な行動パターンとは，特集ウィルス大図鑑
Part 1 生態，pp.062–069 (Aug. 2001).
15) Newman, M.E.J.: Spread of epidemic diseaseon networks, Physical Review E, Vol.65, 016128(2002).
16) 岡本 剛，石田好輝：電子メールにより拡散する
コンピュータウィルスの拡散モデルの解析，信学
論 D-I，Vol.J84-D-I, No.5, pp.474–482 (2001).
17) 大 久 保 明：生 態 学 と 拡 散 ，緒 論 ，筑 紫 書 館(1975).
18) 大久保和彦，林 幸雄，蜷川 繁：Web 的ネッ
トワークにおける情報伝搬率と速度，信学論 D-I，Vol.J85-D-I, No.2, pp.241–244 (2002).
19) Pastor-Satorras, R. and Vespignani, A.: Epidemic dynamics and epidemic states in complex networks, Physical Review E, Vol.63,
066117 (2001).
20) Pastor-Satorras, R. and Vespignani, A.: Immunization of complex networks, Physical Review E, Vol.65, 036104 (2002).
21) 千石 靖，岡本栄司，満保雅浩，植松友彦：コンピュータウィルスの拡散と消滅の大域的振る舞いについて，情報処理学会論文誌，Vol.37, No.4,
pp.579–587 (1996).
22) 重定南奈子：侵入と伝播の数理生態学，第 8 章
伝染病の侵入と伝播，東大出版会 (1992).
23) White, S.R., Kephart, J.O. and Chess, D.M.:
Computer Viruses: A Global Perspective, Proc.
5th Virus Bulletin Int. Conf. (1995).

(平成 15 年 2 月 2 日受付)
(平成 15 年 3 月 18 日採録)

Vol. 44

No. SIG 14(TOM 9)林

ネットワーク成長によるメール型ウイルスの再流行

幸雄（ 正会員）

19

箕浦 正人

昭和 37 年生．昭和 60 年豊橋技昭和 54 年生．平成 13 年名古屋工術科学大学工学部電気電子工学科卒

業大学工学部応用化学科卒業．平成

業．昭和 62 年同大学院修士課程修

15 年北陸先端科学技術大学院大学

了．富士ゼロックス（株）
（株）
，
ATR

知識科学研究科前期課程修了．

視聴覚機構研究所，（ 株）ATR 人間
情報通信研究所等の研究員を経て，現在，北陸先端科
学技術大学院大学知識科学研究科助教授．工学博士．

松久保 潤

数理工学，情報幾何学，力学系，Web 生態系，ニュー

昭和 51 年生．平成 9 年北九州高

ラルネットの研究に従事．日本応用数理学会，電子情等工業専門学校電子制御工学科卒業．

報通信学会，日本神経回路学会，INNS 等各会員．

平成 11 年同校専攻科制御専攻卒業．
平成 13 年北陸先端科学技術大学院
大学知識科学研究科前期課程修了．
現在，同後期課程在学中．電子情報通信学会学生会員．