ホストログの分析3 : 推移確率行列の算出

 第1回で求めた「wls_day-07_all.csv」に対して、推移確率行列を求めていきます。まず、状態空間を何にするかを検討する必要がありますが、第2回でEnvetIDに対して頻出回数を求めました。今回もEventIDを状態空間として、時系列にどのような推移があるかをカウントし、推移確率に直していきます。

・ライブラリの利用：mpi4py

今回のプログラムは利用者が数万人ですので、一人一人の推移を確認していくと、かなりの時間がかかってしまいます。そのため、並列計算を用いて、各プロセスに計算する利用者を割り振り、計算時間の短縮をはかります。注意として、並列計算をすると各プロセスでメモリを消費するので、今回プロセス数は8で実施しました。計算時間は約1時間ほどでした。

・工夫している点：状況をファイルに書き込み

並列計算をしていると、mpi4pyではターミナルへの標準出力が途中ではされなくなってしまいます。実行の状況を確認するために、プロセス0ではファイルの書き込みを行い、どのような段階にあるかをファイルを見ることで確認できます。Linux系OSでは、「tail -f ファイル名」で更新している様子が自動更新されわかりやすいです。

最後に、各プロセスでカウントした推移をプロセス0で集約して、行和を1にすることで正規化しています。これで推移確率行列ができています。

ソースコードリンク：https://github.com/smzn/CyberSecurity_MarkovChain/blob/main/HostEventsTransition.py

ネットワークログの分析3 : 同値類の算出

 デバイス間の推移確率が求められたので、次はこの推移確率から同値類とその同値類中の中心ノードを算出していきます。利用するファイルは以下のファイルです。transition_count_non0_rate.csv

このファイルを取り込んでいきます。

この推移確率行列から、デバイスを状態として、状態を同値類に分類していきます。同じ同値類であることは、相互到達可能であることを意味します。デバイス間で相互到達可能の集合がいくつあるかを調べていきます。次の関数を利用します。

getEquivalence4(th, roop, p)関数

	def getEquivalence4(th, roop, p):
	reachable = np.zeros((len(p), len(p))) #全て0のpと同じ大きさの行列を用意
	equivalence = [[] for i in range(len(p))] #同値類を最大数用意
	list_number = 0
	for ix in range(roop): #n乗まで実施
	pn = np.linalg.matrix_power(p.copy(), ix+1) #累乗
	for i in range(len(pn)):
	for j in range(len(pn)):
	if(pn[i][j] > th): #推移確率が閾値より大きいかチェック
	reachable[i,j] = 1
	# print('到達行列 = \n{0}'.format(reachable))
	# communicate = np.zeros((len(p), len(p))) #全て0のpと同じ大きさの行列を用意
	# for i in range(len(reachable)):
	# for j in range(len(reachable)):
	# if(reachable[i][j] == 1 and reachable[j][i] == 1):
	for i in range(len(pn)):
	for j in range(i+1, len(pn)):
	if(reachable[i][j] == 1 and reachable[j][i] == 1):
	# print('reachable {0} <-> {1}'.format(i, j))
	find = 0 #iでfind -> 1, jでfind -> 2
	idx = len(pn)
	for k in range(len(pn)):
	if i in equivalence[k]: #iが同値類k番目に存在している
	find = 1 #iは同値類k番目に存在
	idx = k
	# print('{0} find in {1}'.format(i, equivalence[k]))
	break
	elif j in equivalence[k]:
	find = 2
	idx = k
	# print('{0} find in {1}'.format(j, equivalence[k]))
	break
	if find == 1:
	if j not in equivalence[idx]: #jは同値類kには存在しない (他のリストにもないことを確認する!!!他のリストにあった場合は移動がいい？ -> communicateがずれないように最後に集合で演算する)
	equivalence[idx].append(j) #jを追加
	# print('{0}に{1}を追加'.format(equivalence[idx], j))
	# print('リスト全体 {0}'.format(equivalence))
	#break
	elif find == 2:
	if i not in equivalence[idx]: #(他のリストにもないことを確認する!!!)
	equivalence[idx].append(i)
	# print('{0}に{1}を追加'.format(equivalence[idx], i))
	# print('リスト全体 {0}'.format(equivalence))
	#break
	elif(find == 0): #新規に追加
	equivalence[list_number].append(i)
	# print('{0}に{1}を追加'.format(equivalence[list_number], i))
	# print('リスト全体 {0}'.format(equivalence))
	if(i != j):
	equivalence[list_number].append(j)
	# print('{0}に{1}を追加'.format(equivalence[list_number], j))
	# print('リスト全体 {0}'.format(equivalence))
	list_number += 1
	#4. Communicateにならないノードを登録
	for i in range(len(pn)):
	find = 0
	for j in range(len(pn)):
	if i in equivalence[j]:
	find = 1
	break
	if find == 0:
	equivalence[list_number].append(i)
	# print('Non Communication node {0} add'.format(i))
	# print('リスト全体 {0}'.format(equivalence))
	list_number += 1
	#5. エルゴード性の確認(class数が1のとき)
	class_number = 0
	for i in range(len(pn)):
	if len(equivalence[i]) > 0:
	# print('クラスの長さ : {0}, {1}'.format(len(equivalence[i]), equivalence[i]))
	class_number += 1
	for i in range(class_number):
	for j in range(i+1, class_number):
	s1 = set(equivalence[i])
	s2 = set(equivalence[j])
	if s1 & s2 :
	# print('重複 {0} & {1}'.format(i, j))
	# print('重複ノード {}'.format(s1 & s2))
	equivalence[i] = equivalence[i] + equivalence[j]
	equivalence[j].clear()
	#print('修正クラス数 {0}'.format(modify_class_number))
	for i in range(class_number):
	# print(equivalence[i])
	equivalence[i] =list(set(equivalence[i]))
	#再度クラス数チェック
	class_number = 0
	for i in range(len(pn)):
	if len(equivalence[i]) > 0:
	class_number += 1
	#再度リストを構成
	modify_equivalence = [[] for i in range(class_number)] #同値類をクラス数用意
	l_index = 0
	for i in range(len(pn)):
	if len(equivalence[i]) > 0:
	modify_equivalence[l_index] = equivalence[i]
	l_index += 1
	return modify_equivalence, class_number, reachable

view raw def getEquivalence4(th, roop, p): hosted with ❤ by GitHub

この関数は3つの引数(th, roop, p)を持ちますが、thは推移しているとみなすことができる閾値です。つまり、この値より推移確率が大きいとき、推移があると考えます。roopは何回で到達可能かを示す値です。pは推移確率行列です。戻り値はmodify_equivalence, class_number, reachableがあります。modify_equivalenceは同値類ごとにデバイスが分類されています。class_numberは同値類の数、reachableは状態間で推移が可能かどうかを{0,1}で表した接続行列です。

もう一つ関数を作っていきます。

getDegreeMax(equivalence, reachable)関数

	def getDegreeMax(equivalence, reachable):
	degree_max_value = [] #クラスの中で最大次数のものをクラス0から順番に入れる
	degree_max_index = []
	reachable_sum = np.sum(reachable, axis=0) + np.sum(reachable, axis=1) #到達行列から行和と列和の和
	for i in range(len(equivalence)): #クラス数だけ回す
	deg_max = -1 #最大値の初期値
	deg_max_index = -1 #最大値を持つノード番号
	for j in equivalence[i]: #ノード番号を一つずつ取り出す
	if deg_max < reachable_sum[j]:
	deg_max = reachable_sum[j]
	deg_index = j
	degree_max_value.append(deg_max)
	degree_max_index.append(deg_index)
	return degree_max_index, degree_max_value

view raw def getDegreeMax(equivalence, reachable): hosted with ❤ by GitHub

これは、同値類の中で中心性のノードがどれかを計算しています。次数中心性で求めています。

今回の計算結果では、

同値類数が6964個、

最大クラス数 : 18090、

最大クラスを持つindex : 0 

最大クラスの最大次数を持つノード番号 : 6947、

デバイス名 : Comp186884

となりました。ここまでの結果で同値類数、同値類の中の中心性デバイスの情報がわかるようになりました。

全体のソースコード : https://github.com/smzn/CyberSecurity_MarkovChain/blob/main/EquivalentClass.py