日本オペレーションズ。リサーチ学会 2005年春季研究発表会
2−『−3
確率的SISモデルによる罰ンぼユロタウイルス増殖過程の推定
岡村寛之（01013754）†，立石和也‡，土肥正（01307065）ナ †広島大学大学院工学研究科情報工学専攻 ‡広島大学工学部第二頬（電気系） 1．はじめに④←①④。。。
き包
机 叛 い3 い〃 図1：SISモデルの状態遷移図． コンピュータウィルスは1980年代から猛威を振るうよう になりコンピュータセキュリティ確保において考慮すべき重 要な問題となっている．近年では．インターネット利用者の 増加に伴って，ワームをはじめとするコンピュータウィルス の爆発的増殖が多く報告されている．コンピュータウィルス の増殖を発見初期の段階で定量的に予測することは，セキュ リティ戦略上重要な指針となりうる．そのため，コンピュー タウィルスの増殖の様子を数理モデルによって表現する試み が行われている【1，2，3，4】・特にコンピュータウィルスの増 殖における確率的要因を考慮した研究の多くは出生死滅過程 とよばれる確率過程によってウイルスの増殖を表現している 【5，6，7】・ 実際に，出生死滅過程によって表現された確率モデルを用 いてコンピュータウィルスの増殖を予測・評価する場合，観 測された実データ（感染報告データ）から確率モデル内のパ ラメータを推定する必要がある．しかしながら，コンピュー タウィルスのように多くの被害が報告されるデータを用いて， 出生死滅過程のパラメータを推定することは膨大な星の計算 を必要とするため実用的でないことが多い． そこで本稿では出生死滅過程を内部状態にもつマルコフ変 調ポアソン過程（MMPP）を考える．これにより，感染報告 データからウイルス増殖を表現する確率モデルのパラメータ 推定を行うことが可能となる． 2．出生死滅過程によるウイルス増殖モデル そこで本稿では，SISモデルによって内部状態が表現され るMMPPを考える．つまり，感染報告が内部状態に依存し て発生するようなウイルス増殖モデルを提案する．このモデ ルでは，内部状態におけるパラメータⅣを感染報告数と対応 させる必要がなくなるため，より少ない状態でウイルスの増 殖過程を表現することが可能となる． いま，J￠）を内部状態を表す確率過程と考え，その無限小 生成行列をCとする．また，内部状態に対応した感染報告発 生率に関する行列を皿とすると，それぞれ 0 0 〝1−レ1 入1 〃2 −レ2 入2 〃〃−1−レ〃−1入Ⅳ−1 〃〃 ￣〝〃（0∴）
（1） 且〉＝ 最も単純な出生死滅過程によるウイルス増殖モデルはSIS （Susceptible−In鈷cted−Susceptible）モデルと呼ばれる．SIS モデルでは全ての端末は状態S（感染しうる状態）と状態Ⅰ （感染している状態）で表現される・確率過程（J（畑土≧0〉 を時刻亡において感染している端末数とすると，感染端末数 は図1の状態遷移図で表される連続時間マルコフ連鎖となる． SISモデルを用いてウイルスの増殖を予測。評価する場合， 推移率に関するパラメータに加えて，感染しうる端末台数Ⅳ を推定する必要がある．ところが近年のインターネット利用 者の増加に伴って，コンピュータウィルスに関する感染報告 数が1日で1，000件あるいはそれ以上起こることは少なくな い．このような場合，感染しうる端末台数Ⅳは少なくとも1 日で報告される感染端末数以上，すなわちⅣ＝1000以上が 要求される．しかしながら，図1で見るようにパラメータ〃 はマルコフ連鎖における状態数を直接表現するものであるた めノバラメ一夕〃を大きくすることは他の推移率に関するパ ラメータを推定することでさえ困難な状況を引き起こす． となる．ここで￠は報告発生率である．また， ． ト．1 がい 朗▼ 紘．ん こr ﹁∴ ∴∴ ︶ ︶ ︶ 3 4 5 ︵ ′し ︵ ん ．●■ ．●︳ 〃 レ であり，βはウイルスの増殖率，∂は除去率を表す． 累積のウイルス感染報告数に関する確率過程を（月（t）；電≧ 0）とし，（豆，j）要素が riメ（r，り＝Pr（月（り＝町叩）＝ブけ（0）＝査〉 （6） である行列屈（m，りを定義すると， 抑）＝抑）￠， （7） ヱ・二・こ・ 屈（れ，f）C＋児（れ−1，り皿 払＝l＝1，2，… （8）−258−
© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.次に，Eステップで算出した期待値を用いて．Mステップ は推定すべきパラメータβ，∂，￠に対して， となる．時刻0において内部状態を決定する初期ベクトルを 打とすると，時刻￡における期待累税感染報告数は， ∑≡1∑㌫1E【硬；し11p】 上土 E【尺（用＝汀 exp（（C＋β）β）dβかe （9） （16） ∑ニ1∑ニ1ペ〃一明rZJu廟’ ∑≡1∑ニ1E【咄し1】p】 で与えられる．ここでeは全ての要素が1である列ベクトル である． 3．パラメータ推定手法 （17） ∑監1∑ニ1呵4u廟’ ∑≡1∑ニ1E【℃【ご1lpl （18） ∑≡1∑ニ1呵オ】lp】 前節で構築したモデルを用いてウイルスの増殖の一㌢測をす るためには，感染報告データに適合するようにモデルパラメー タの推定を行う必要がある． いま，〝個のウィルス感染報告に関する時間間隔データ p＝（ェ1，エ2，…，〇〝）が与えられているもとで，パラメー タ の推定値を算出する手続きについて考える．特に，ここでは 最尤推定値を算出する手続きとしてEMアルゴリズム【8】を 用いる．EMアルゴリズムは観測されていないデータ（不完 全データ）に対して最尤推定値を求める手続きであり．期待 対数尤度を算出する手続き（Eステップ）とそれを最大化す る手続き（Mステップ）を持つ反復アルゴリズムである． 以下の記号を定義する． 岬：祝−1番目の感染報告から祝番目の感染報告が発生す るまでに内部状態が曳からJへ推移する回数 げ：内部状酎で祝番目の感染報告が発生し，かつその直 後に内部状態がブに推移する回数 柑：u−1番目の感染報告から加番目の感染報告が発生す るまでに内部状態宜に滞在する時間 感染報告データ かが与えられたとき，それぞれの期待値 E［Nl；JID］，E【専）JD］，E【Zl；IID】を算出する手続きがEス テップに対応する・これは，文献【9】にある一般的なMMPP に対するEMアルゴリズムにおけるEステップと同じであり、， となる．また，初期確率ベクトル汀＝（汀0，れ，‥．，汀〃）に対 するMステップにおける更新式は （19） となる． 参考文献 【1】Z．Chen，L．GaoandK．Kwiat，Modelingthespreadof activeworms，PrDCeedings qfIEEEINFOCOM2003， 2003． 【2】S・ChenandY・Tang，SlowingdownInternetworms，
P和Ceedれタβ 扉 班e 2イ兢 血亡emα￡われαJCo†重代托Ce o乃β由亡わ♭u±ed Co叩p≠加夕 勒βt印び 〝CDC方 gβ叫ノ， pp．312−319，2004． t3】J．0・KephartandS・R・White，Measuringandmodel− ingcomputervirusprevalence，Proceedin9SP／the1993 J官ββCα汀軍規‡ergoc乞e￡y勒mpoβれmo花月eβeα化ん哀れ∫e一 仇椚砺＝mdPれMC弘pp．2−15，1993． 【4】H．TbyoizumiandA．Kara，Predators：gOOdwi1lcodes
COmbatagainstcomputerviruses，ACMSIGSACNew
gecIJわ毎夕αmd乞タm5Ⅳorたβ加p，2002． 【5】W・H・Murray，Theapplicationofepidemi0logytocom− Puter Viruses，Computers andSecurity，Vol．7，■No・2， pp．139−145，1988・【6］J・C・Wierman and D・J．Marchette，Modelingcom− Puter virus prevalence with a susceptible−infected− SuSCePtiblemodelwith reintroduction，Cbr叩utationaL 5ねt由t豆c∂伊βαねAれαヱy由，Vol．45，pp．3−23，2004・ 【7卜小林，岡村，土肥，確率モデルによるコンピュータウィル スの絆微分帆情報処理学会論文誌，Vo145，No．5，pp． 1432−1441，2004． 【8】G・J・McLachlanandT・Krishnan，TheEMAlgorithm
and Extensions，John Wiley＆Sdns，NewYork，NY，
1997． 【9］T．Ryd6n，AnEMalgorithmfbrestimation．isMarkov− modulatedPoissonprocess，ComputationaLStatistics＆ 仇血AM廟埼Vol．21，pP．431−447，1996． 軋jC押） 訂bl’ ∈りげu】itb叫1】ブ （10） ， （11） （12） として算出される・ここで，〃りおよび∈りはそれぞれ行列 Cおよび刀の（豆，j）要素・またト1iはベクトルの豆．要素を 示す・さらに，これらの式において左，むuは， ft．＝ 汀eXp（Cxl）D・‥eXp（Cxu）， （13） bu ＝ eXP（CxtL）D…eXp（CxK）De， （14） であり，Cぎ（りは C；（豆）＝ （fu＿1Dexp（Cy）】i［exp（C（xu−y））Db．L＋1】jdy （15） で与えられる． −259− © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.
