Probability Calculation in Bayesian Networks

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

I'm currently working on a formula to calculate the Mean Time To Compromise (MTTC) for specified attack graphs (In Figure 1 you can see an example). So I'm searching for an efficient way to calculate the total Probability to reach the condition "root(2)" = goal. My idea was to use a Bayesian Network to make the calculations possible.


exploit:= ovals in Figure 1 e.g ssh(0,1) means that the attacker 0 exploits ssh on host 1

condition := text without ovals in Figure 1 e.g ssh(1) means that ssh is installed on host1

E := set of exploits

C := set of conditions

$R_r subseteq C times E$

$R_i subseteq E times C$

Rr is conjunctive meaning that all the pre-conditions denoted by $R_r(e)$ (that is c R_r e$) of an exploit e must be satisfied before e can be executed.

Ri is disjunctive meaning that executing any of those exploits is sufficient to satisy that condition. A condition can be either initially satisfied (initial condition) or satisfied as the post-condition of some exploits.

Here's the link to Figure 1

Conditions need only 1 of the Exploits to be executed in order to be reached. If both Exploits get executed then $P(E_1cap E_2)$ is added to $P(E_1 cap not E_2)$ if $P(E_1) > P(E_2)$

Exploits need all pre-conditions to be satisfied in order to be executed.

After long research i came across an algorithm that claims to be an answer for my problem: Unfortunately i do not understand the pseudo code. Could anyone try to explain what the code does especially the mathematical parts as I'm not really experienced in that field? e.g
U : U ⊆ c ∈ Ri(ei) , p(s) = p(s = T | ∀u ∈ PS st s ⊂ u, u = F) and foreach set s ∈ PS st (ek ∈ s) ∧ (|s| > 1) do

Input : condition c| c ∈ Ri(ei)
Input : set of exploits ej 
Input : set of exploits ri descendants of c
Input : an exploit ei
Output : pr(ei)
Method:
PS = U : U ⊆ c ∈ Ri(ei)
foreach set s ∈ PS do
 p(s) = p(s = T | ∀u ∈ PS st s ⊂ u, u = F)
end
pr(ei) = p(ei);
foreach set s ∈ PS st (ek ∈ s) ∧ (|s| > 1) do
 pr(ei) = pr(ei) + pr(c) if p(ei) < p(ej ) ∀ej != ei ∈ ej
end
pr(ei) = pr(ei) ∗ sum(p(ri));
return pr(ei)

Or could anyone try to explain how to calculate Probabilities in a Bayesian Network in general.

My Approach was following:

Possibilties to reach condition $user(1)$:

1) ssh(0,1) = F = 0,92 and rsh(0,1) = T = 0,75 which requires ftp_rhosts(0,1) also to be T = 0,46 $rightarrow$ $P(rsh | ftp_rhosts)$ = 0,75*0,46 = 0,345. Therefore $P(user1) = 0,92 * 0,345 = 0,3174$

2) ssh(0,1) = T = 0,08 and rsh(0,1) = F = 1 - 0,345 = 0,655 $rightarrow$ $P(user1)$ = $0,08 * 0,655 = 0,6524$

3) ssh(0,1) = T and rsh(0,1) = T which requires ftp_rhosts(0,1) also to be T etc.

Is this the correct way of doing the calculations in a Bayesian Network? And is there any algorithm that can do it efficiently? Maybe the pseudo code from above?

bayesian bayesian-network computational-science

share|cite|improve this question

asked Jul 30 at 13:08

koapsi

206

add a comment | 

up vote
0
down vote

favorite

I'm currently working on a formula to calculate the Mean Time To Compromise (MTTC) for specified attack graphs (In Figure 1 you can see an example). So I'm searching for an efficient way to calculate the total Probability to reach the condition "root(2)" = goal. My idea was to use a Bayesian Network to make the calculations possible.


exploit:= ovals in Figure 1 e.g ssh(0,1) means that the attacker 0 exploits ssh on host 1

condition := text without ovals in Figure 1 e.g ssh(1) means that ssh is installed on host1

E := set of exploits

C := set of conditions

$R_r subseteq C times E$

$R_i subseteq E times C$

Rr is conjunctive meaning that all the pre-conditions denoted by $R_r(e)$ (that is c R_r e$) of an exploit e must be satisfied before e can be executed.

Ri is disjunctive meaning that executing any of those exploits is sufficient to satisy that condition. A condition can be either initially satisfied (initial condition) or satisfied as the post-condition of some exploits.

Here's the link to Figure 1

Conditions need only 1 of the Exploits to be executed in order to be reached. If both Exploits get executed then $P(E_1cap E_2)$ is added to $P(E_1 cap not E_2)$ if $P(E_1) > P(E_2)$

Exploits need all pre-conditions to be satisfied in order to be executed.

After long research i came across an algorithm that claims to be an answer for my problem: Unfortunately i do not understand the pseudo code. Could anyone try to explain what the code does especially the mathematical parts as I'm not really experienced in that field? e.g
U : U ⊆ c ∈ Ri(ei) , p(s) = p(s = T | ∀u ∈ PS st s ⊂ u, u = F) and foreach set s ∈ PS st (ek ∈ s) ∧ (|s| > 1) do

Input : condition c| c ∈ Ri(ei)
Input : set of exploits ej 
Input : set of exploits ri descendants of c
Input : an exploit ei
Output : pr(ei)
Method:
PS = U : U ⊆ c ∈ Ri(ei)
foreach set s ∈ PS do
 p(s) = p(s = T | ∀u ∈ PS st s ⊂ u, u = F)
end
pr(ei) = p(ei);
foreach set s ∈ PS st (ek ∈ s) ∧ (|s| > 1) do
 pr(ei) = pr(ei) + pr(c) if p(ei) < p(ej ) ∀ej != ei ∈ ej
end
pr(ei) = pr(ei) ∗ sum(p(ri));
return pr(ei)

Or could anyone try to explain how to calculate Probabilities in a Bayesian Network in general.

My Approach was following:

Possibilties to reach condition $user(1)$:

1) ssh(0,1) = F = 0,92 and rsh(0,1) = T = 0,75 which requires ftp_rhosts(0,1) also to be T = 0,46 $rightarrow$ $P(rsh | ftp_rhosts)$ = 0,75*0,46 = 0,345. Therefore $P(user1) = 0,92 * 0,345 = 0,3174$

2) ssh(0,1) = T = 0,08 and rsh(0,1) = F = 1 - 0,345 = 0,655 $rightarrow$ $P(user1)$ = $0,08 * 0,655 = 0,6524$

3) ssh(0,1) = T and rsh(0,1) = T which requires ftp_rhosts(0,1) also to be T etc.

Is this the correct way of doing the calculations in a Bayesian Network? And is there any algorithm that can do it efficiently? Maybe the pseudo code from above?

bayesian bayesian-network computational-science

share|cite|improve this question

asked Jul 30 at 13:08

koapsi

206

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

I'm currently working on a formula to calculate the Mean Time To Compromise (MTTC) for specified attack graphs (In Figure 1 you can see an example). So I'm searching for an efficient way to calculate the total Probability to reach the condition "root(2)" = goal. My idea was to use a Bayesian Network to make the calculations possible.


exploit:= ovals in Figure 1 e.g ssh(0,1) means that the attacker 0 exploits ssh on host 1

condition := text without ovals in Figure 1 e.g ssh(1) means that ssh is installed on host1

E := set of exploits

C := set of conditions

$R_r subseteq C times E$

$R_i subseteq E times C$

Rr is conjunctive meaning that all the pre-conditions denoted by $R_r(e)$ (that is c R_r e$) of an exploit e must be satisfied before e can be executed.

Ri is disjunctive meaning that executing any of those exploits is sufficient to satisy that condition. A condition can be either initially satisfied (initial condition) or satisfied as the post-condition of some exploits.

Here's the link to Figure 1

Conditions need only 1 of the Exploits to be executed in order to be reached. If both Exploits get executed then $P(E_1cap E_2)$ is added to $P(E_1 cap not E_2)$ if $P(E_1) > P(E_2)$

Exploits need all pre-conditions to be satisfied in order to be executed.

After long research i came across an algorithm that claims to be an answer for my problem: Unfortunately i do not understand the pseudo code. Could anyone try to explain what the code does especially the mathematical parts as I'm not really experienced in that field? e.g
U : U ⊆ c ∈ Ri(ei) , p(s) = p(s = T | ∀u ∈ PS st s ⊂ u, u = F) and foreach set s ∈ PS st (ek ∈ s) ∧ (|s| > 1) do

Input : condition c| c ∈ Ri(ei)
Input : set of exploits ej 
Input : set of exploits ri descendants of c
Input : an exploit ei
Output : pr(ei)
Method:
PS = U : U ⊆ c ∈ Ri(ei)
foreach set s ∈ PS do
 p(s) = p(s = T | ∀u ∈ PS st s ⊂ u, u = F)
end
pr(ei) = p(ei);
foreach set s ∈ PS st (ek ∈ s) ∧ (|s| > 1) do
 pr(ei) = pr(ei) + pr(c) if p(ei) < p(ej ) ∀ej != ei ∈ ej
end
pr(ei) = pr(ei) ∗ sum(p(ri));
return pr(ei)

Or could anyone try to explain how to calculate Probabilities in a Bayesian Network in general.

My Approach was following:

Possibilties to reach condition $user(1)$:

1) ssh(0,1) = F = 0,92 and rsh(0,1) = T = 0,75 which requires ftp_rhosts(0,1) also to be T = 0,46 $rightarrow$ $P(rsh | ftp_rhosts)$ = 0,75*0,46 = 0,345. Therefore $P(user1) = 0,92 * 0,345 = 0,3174$

2) ssh(0,1) = T = 0,08 and rsh(0,1) = F = 1 - 0,345 = 0,655 $rightarrow$ $P(user1)$ = $0,08 * 0,655 = 0,6524$

3) ssh(0,1) = T and rsh(0,1) = T which requires ftp_rhosts(0,1) also to be T etc.

Is this the correct way of doing the calculations in a Bayesian Network? And is there any algorithm that can do it efficiently? Maybe the pseudo code from above?

bayesian bayesian-network computational-science

share|cite|improve this question

asked Jul 30 at 13:08

koapsi

206

I'm currently working on a formula to calculate the Mean Time To Compromise (MTTC) for specified attack graphs (In Figure 1 you can see an example). So I'm searching for an efficient way to calculate the total Probability to reach the condition "root(2)" = goal. My idea was to use a Bayesian Network to make the calculations possible.


exploit:= ovals in Figure 1 e.g ssh(0,1) means that the attacker 0 exploits ssh on host 1

condition := text without ovals in Figure 1 e.g ssh(1) means that ssh is installed on host1

E := set of exploits

C := set of conditions

$R_r subseteq C times E$

$R_i subseteq E times C$

Rr is conjunctive meaning that all the pre-conditions denoted by $R_r(e)$ (that is c R_r e$) of an exploit e must be satisfied before e can be executed.

Ri is disjunctive meaning that executing any of those exploits is sufficient to satisy that condition. A condition can be either initially satisfied (initial condition) or satisfied as the post-condition of some exploits.

Here's the link to Figure 1

Conditions need only 1 of the Exploits to be executed in order to be reached. If both Exploits get executed then $P(E_1cap E_2)$ is added to $P(E_1 cap not E_2)$ if $P(E_1) > P(E_2)$

Exploits need all pre-conditions to be satisfied in order to be executed.

After long research i came across an algorithm that claims to be an answer for my problem: Unfortunately i do not understand the pseudo code. Could anyone try to explain what the code does especially the mathematical parts as I'm not really experienced in that field? e.g
U : U ⊆ c ∈ Ri(ei) , p(s) = p(s = T | ∀u ∈ PS st s ⊂ u, u = F) and foreach set s ∈ PS st (ek ∈ s) ∧ (|s| > 1) do

Input : condition c| c ∈ Ri(ei)
Input : set of exploits ej 
Input : set of exploits ri descendants of c
Input : an exploit ei
Output : pr(ei)
Method:
PS = U : U ⊆ c ∈ Ri(ei)
foreach set s ∈ PS do
 p(s) = p(s = T | ∀u ∈ PS st s ⊂ u, u = F)
end
pr(ei) = p(ei);
foreach set s ∈ PS st (ek ∈ s) ∧ (|s| > 1) do
 pr(ei) = pr(ei) + pr(c) if p(ei) < p(ej ) ∀ej != ei ∈ ej
end
pr(ei) = pr(ei) ∗ sum(p(ri));
return pr(ei)

Or could anyone try to explain how to calculate Probabilities in a Bayesian Network in general.

My Approach was following:

Possibilties to reach condition $user(1)$:

1) ssh(0,1) = F = 0,92 and rsh(0,1) = T = 0,75 which requires ftp_rhosts(0,1) also to be T = 0,46 $rightarrow$ $P(rsh | ftp_rhosts)$ = 0,75*0,46 = 0,345. Therefore $P(user1) = 0,92 * 0,345 = 0,3174$

2) ssh(0,1) = T = 0,08 and rsh(0,1) = F = 1 - 0,345 = 0,655 $rightarrow$ $P(user1)$ = $0,08 * 0,655 = 0,6524$

3) ssh(0,1) = T and rsh(0,1) = T which requires ftp_rhosts(0,1) also to be T etc.

Is this the correct way of doing the calculations in a Bayesian Network? And is there any algorithm that can do it efficiently? Maybe the pseudo code from above?

bayesian bayesian-network computational-science

share|cite|improve this question

asked Jul 30 at 13:08

koapsi

206

share|cite|improve this question

share|cite|improve this question

asked Jul 30 at 13:08

koapsi

206

asked Jul 30 at 13:08

koapsi

206

asked Jul 30 at 13:08

koapsi

206

206

add a comment | 

add a comment | 

active

oldest

votes

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867006%2fprobability-calculation-in-bayesian-networks%23new-answer', 'question_page');

);

Post as a guest

Name Email

active

oldest

votes

active

oldest

votes

active

oldest

votes

active

oldest

votes

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867006%2fprobability-calculation-in-bayesian-networks%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email