Intrusion Tolerance as a Two-Level Game (Visit to Melbourne University)

Visit to the Prof. Tansu Alpcan at the University of Melbourne.

1. 1/43
Intrusion Tolerance as a Two-Level Game
1
Visit to the University of Melbourne
Kim Hammar
[email protected]
KTH Royal Institute of Technology
June 20, 2024
1
Paper to appear in International Conference on Dependable Systems and Networks, IEEE DSN 2024, June
24-27, Brisbane, Australia

2. 2/43
Use Case: Intrusion Tolerance
::: ClientsapigatewaysCompute nodesStorage nodes
Service
replica 1
Service
replica 2
Service
replica 3
Service
replica 4 Client interface & load balancer
IAreplicated systemoers a service to a client population.
IThe system should provide.

3. 2/43
Use Case: Intrusion Tolerance
::: AttackerClientsapigatewaysCompute nodesStorage nodes
Service
replica 1
Service
replica 2
Service
replica 3
Service
replica 4 Client interface & load balancer
IAn
IThe system shouldtolerate intrusions.

4. 3/43
Intrusion Tolerance (Simplied)
Intrusion eventTime of full recoveryTimeRecovery timeSurvivabilityLoss
Normal
performanceSystem performanceTolerance
Cumulative
performance loss
(want to minimize)

5. 4/43
Increasing Demand for Intrusion-Tolerant Systems
IAs ourreliance on online services grows, there is an
increasing demand for intrusion-tolerant systems.
IExample applications:
Flight control
computer
Sensors and
actuators
Power grids
e.g.,scadasystems
2
.
Safety-critical IT systems
e.g., banking systems,
e-commerce applications
3
,
healthcare systems, etc.
Real-time control systems
e.g., ight control computer
4
.
2
Amy Babay et al. 2018 48th
Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 2018, pp. 255266.doi:
10.1109/DSN.2018.00036.
3
Jukka Soikkeli et al. IEEE
Transactions on Dependable and Secure Computing20.2 (2023), pp. 11541168.doi:
10.1109/TDSC.2022.3151462.
4
J.H. Wensley et al.
Proceedings of the IEEE66.10 (1978), pp. 12401255.doi:10.1109/PROC.1978.11114.

6. 5/43
Theoretical Foundations of Intrusion Tolerance
L. LamportW. WeibullR.E. BarlowW.ShewhartL. AdlemanA. ShamirR. RivestD. DolevN. LynchE. DijkstraJ. GrayB. LiskovReliabilityTheoryDistributedSystemsCryptography
Intrusion-
tolerant
systems

7. 6/43
Our Contribution
ReliabilityTheoryDistributedSystemsCryptographyGameanddecisiontheory
Intrusion-
tolerant
systems
This
presentation

8. 7/43
Building Blocks of An Intrusion-Tolerant System
HC;CrashedHealthyCompromisedCrashCrashRecoveryCompromise204060801000:20:40:60:8125 replicas50 replicas100 replicastReliability : : :Replicated systemClient interfaceRequestResponse Consensus protocol12345
1. Intrusion-tolerant consensus protocol
A quorum needs to reach agreement
to toleratefcompromised replicas.
2. Replication strategy
Cost-reliability trade-o.
3. Recovery strategy
Compromises will occur ast! 1.

9. 8/43
Prior Work on Intrusion-Tolerant Systems
- Fixed number of replicas
- No recoveries
Published 1995

10. 8/43
Prior Work on Intrusion-Tolerant Systems
- Fixed number of replicas
- No recoveries
Published 1998

11. 8/43
Prior Work on Intrusion-Tolerant Systems
- Fixed number of replicas
-Periodicrecoveries
Published 2002

12. 8/43
Prior Work on Intrusion-Tolerant Systems
- Fixed number of replicas
- Periodic recoveries
Published 2004

13. 8/43
Prior Work on Intrusion-Tolerant Systems
-Adaptive replicationbased on heuristics
- Periodic recoveries
Published 2006

14. 8/43
Prior Work on Intrusion-Tolerant Systems
- Fixed number of replicas
- Periodic recoveries
Published 2006

15. 8/43
Prior Work on Intrusion-Tolerant Systems
- Fixed number of replicas
-Supports both periodic and reactive recoveries
- Does not provide reactive recovery strategies
Published 2007

16. 8/43
Prior Work on Intrusion-Tolerant Systems
- Fixed number of replicas
- Periodic recoveries
Published 2011

17. 8/43
Prior Work on Intrusion-Tolerant Systems
- Fixed number of replicas
- Periodic recoveries
Published 2018

18. 8/43
Prior Work on Intrusion-Tolerant Systems
- Fixed number of replicas
- Periodic recoveries
Published 2023

19. 8/43
Prior Work on Intrusion-Tolerant Systems
- Fixed number of replicas
- Periodic recoveries
Published 2023Can we do better by leveraging game-theoretic strategies?

20. 9/43
ThetoleranceArchitecture
Two-levelrecoveryand replicationcontrol with feedback.
toleranceNode 1Privileged domain Application domain
Service
replicaNode controller
ids
alerts
reco-
veryVirtualization layerHardwareNode 2Privileged domain Application domain
Service
replicaNode controller
ids
alerts
reco-
veryVirtualization layerHardwareNodeNtPrivileged domain Application domain
Service
replicaNode controller
ids
alerts
reco-
veryVirtualization layerHardware: : :Consensus protocolSystem controllerState estimateEvict or addState estimateEvict or addState estimateEvict or add : : :Service requestsResponsesClients AttackerIntrusion attempts

21. 10/43
Denition 1 (Correct service)
The system providescorrect serviceif the healthy replicas satisfy
the following properties:
Each request is eventually executed: (Liveness)
Each executed request was sent by a client. (Validity)
Each replica executes the same request sequence. (Safety)

22. 11/43
Proposition 1 (Correctness oftolerance)
A system that implements thetolerancearchitectureprovides
correct serviceif
Network links are authenticated.
At most f nodes are compromised or crashed simultaneously.
Nt2f+1.
The system is partially synchronous.

23. 12/43
Intrusion Tolerance as a Two-Level Game
: : :1(b1)2(b2)3(b3)4(b4)Nt
(bNt
)
Belief
transmissionsNode controllers
Replicated
systemSystem controller(b1; : : : ;bNt
)b1b2b3b4bNt
: : :AttackerClients
IWe formulate intrusion tolerance as a two-level game.
IThe.
IThe.

24. 12/43
Assumption 1
The probability that the system controller fails is negligible.
Assumption 2
Compromise and crash events are statistically independent across
nodes.
Assumption 3
The attacker can infer the observations of the controllers.
: : :1(b1)2(b2)3(b3)4(b4)Nt
(bNt
)
Belief
transmissionsNode controllers
Replicated
systemSystem controller(b1; : : : ;bNt
)b1b2b3b4bNt
: : :AttackerClients

25. 13/43
The Local Recovery Game
IPartially observed stochastic gamei.
IPlayers: (C)ontroller and (A)ttacker.IController actions: (R)ecover and (W)ait.
IAttacker actions: (A)ttack and (F)alse alarm.
IStates:SN=fH;C;;g.
IpC;i: crash probability,pA;i: attack success probability.
IObservationoi;tzi(ja
(A)
):idsalerts at timet.
HC;CrashedHealthyCompromisedpC;ipC;ia
(C)
i
=Ra
(A)
i
=A

26. 13/43
The Local Recovery Game
IPartially observed stochastic gamei.
IPlayers: (C)ontroller and (A)ttacker.IController actions: (R)ecover and (W)ait.
IAttacker actions: (A)ttack and (F)alse alarm.IStates:SN=fH;C;;g.
IpC;i: crash probability,pA;i: attack success probability.
IObservationoi;tzi(ja
(A)
):idsalerts at timet.
HC;CrashedHealthyCompromisedpC;ipC;ia
(C)
i
=Ra
(A)
i
=A

27. 13/43
The Local Recovery Game
IPartially observed stochastic gamei.
IPlayers: (C)ontroller and (A)ttacker.IController actions: (R)ecover and (W)ait.
IAttacker actions: (A)ttack and (F)alse alarm.IStates:SN=fH;C;;g.
IpC;i: crash probability,pA;i: attack success probability.IObservationoi;tzi(ja
(A)
):idsalerts at timet.
HC;CrashedHealthyCompromisedpC;ipC;ia
(C)
i
=Ra
(A)
i
=A

28. 14/43
Node Controller Strategy
IThe controller computes thebelief
bi;t(s),P[Si;t=Cjh
(C)
t]:
h
(C)
t,(bi;1;a
(C)
i;1
;oi;2;a
(C)
i;2
;oi;3; : : : ;a
(C)
i;t1
;oi;t):
IController strategy:

(C)
: [0;1]!(fW;Rg):
ControllerBelief

29. 15/43
Node Controller Objective
ICost:Ji,T
(R)
i
+F
(R)
i
. (Zero-sum game)
IT
(R)
i
is the averagetime-to-recovery.
IF
(R)
i
is therecovery frequency.
I >1 is a scaling factor.
IBounded-time-to-recovery constraint: The time between two
recoveries can be at mostR.
1020304050607080901000:51p=0:1p=0:05p=0:025p=0:01p=0:005tFailure (crash or compromise) probability.
pis the failure probability per time-step.

30. 16/43
Threshold Structure of the Controller's Best Response
0:10:20:30:40:50:60:70:80:910:40:60:81alpha vectorsE[Jijbi;1]bi;1
?
wait regionrecovery region
The controller's best response value.
Theorem 2
There exists a best response strategy that satises
~
(C)
i;t
(bi;t) =R()bi;t
?
i;t 8t;
where
?
i;t
2[0;1]is a threshold.

31. 17/43
Ecient Computation of Best Responses
Algorithm 1:Threshold Optimization
1Input:Objective functionJi, parametric optimizerpo.
2Output:A approximate best response strategy^
(C)
i;
.
3Algorithm
4 [0;1].
5 For each2, dene
(C)
i;
(bi;t)as
6
(C)
i;
(bi;t),
(
R ifbi;t
W otherwise.
7 J E

(C)
i;
[Ji].
8 ^
(C)
i;
po(;J).
9 return^
(C)
i;
.
IExamples of: CEM, BO,
CMA-ES, DE, SPSA, etc.

32. 18/43
Ecient Computation of Best Responses
51015202510
0
10
1
10
2
10
3
cemdebospsadynamic programmingRTime (min)
Mean compute time to obtain a best reponse for dierent values of the
bounded-time-to-recovery constraintR.

33. 19/43
Denition 3 (Perfect Bayesian equilibrium (PBE))
LetBdenote the belief operator. Then(
?
;B)is apbei
1.Optimality:

?
is a Nash equilibrium (ne) inj
h
(C)
i;t
8h
(C)
i;t
, wherej
h
(C)
i;t
is
the subgame starting fromB(h
(C)
t;
?;(A)
i;t
).
2.Belief consistency:
For anyh
(C)
i;t
withP[h
(C)
i;t
j
?
;b1]>0, then
B(h
(C)
i;t
;
?;(A)
i;t
)
=B(B(h
(C)
i;t1
;
?;(A)
i;t
);
?;(C)
i;t
(B(h
(C)
i;t1
;
?;(A)
i;t
));ot;
?;(A)
i;t
):

34. 20/43
Theorem 4 (Existence of equilibrium and best response)
1.For each strategy pairiini, there
responses.
2.ihas a perfect Bayesian equilibrium pbe).
3.If si;t=0()bi;t=0, thenihas a unique purepbe.
4.The value ofiis not larger than1.

35. 21/43
Idea Behind the Proof of Equilibrium Existence
j
h
(D)
2
j
h
(D)
2
j
h
(D)
2
j
h
(D)
2
j
h
(D)
2
j
h
(D)
2
j
h
(D)
2
j
h
(D)
2
j
h
(C)
i;2
N:h
(C)
i;1
si;1=Hsi;1=Csi;1bi;1C:h
(C)
i;1
C:h
(C)
i;1
A:(h
(A)
i;1
;si;1=H)A:(h
(A)
i;1
;si;1=H)A:(h
(A)
i;1
;si;1=C)A:(h
(C)
i;1
;si;1=C)
N:(h
(C)
i;1
;
si;2=H)
N:(h
(C)
i;1
;
s2=H)
N:(h
(C)
i;1
;
(ai;1= (W;A))
N:(h
(C)
i;1
;
si;2=H)
N:(h
(C)
i;1
;
si;2=H)
N:(h
(C)
i;1
;
si;2=H)
N:(h
(C)
i;1
;
si;2=C)
N:(h
(C)
i;1
;
si;2=C)
N:(h
(C)
i;1
;
si;2=C)
N:(h
(C)
i;1
;
si;2=H)a
(C)
i;1
=Ra
(C)
i;1
=Wa
(C)
i;1
=Ra
(C)
i;1
=Wa
(A)
i;1
=Aa
(A)
i;1
=Fa
(A)
i;1
=Aa
(A)
i;1
=Fa
(A)
i;1
=Aa
(A)
i;1
=Fa
(A)
i;1
=Aa
(A)
i;1
=Foi;2z(jA)oi;2z(jF)oi;2z(jA)oi;2z(jF)oi;2z(jA)oi;2z(jF)oi;2z(jA)
oi;2
z(jA)
oi;2
z(jA)pA;i1pA;i
IFix the time horizonT. Then we can
extensive form, and hence it has a value.
IAsT! 1, thediscount factor2[0;1)implies that
limt!1
P
t

t
Ct=0, which means that a value exists.

36. 22/43
Value of the Local Recovery Game
0:10:20:30:40:50:60:70:80:910:20:40:60:81=1=4=8pA;iGame value.
Game value in function of the intrusion probabilitypA;i.
IWe can compute the game value usingHeuristic Search
Value Iteration(hsvi).

37. 23/43
The Benet of Strategic Recovery24681012141618200:20:30:4Equilibrium strategyPeriodic strategyDKL(no intrusionkintrusion)Ji(4)Benet of strategic recovery
Strategic recovery
given that anintrusion detection model is available.
Key insight

38. 24/43
Intrusion Tolerance as a Two-Level Game
: : :1(b1)2(b2)3(b3)4(b4)Nt
(bNt
)
Belief
transmissionsNode controllers
Replicated
systemSystem controller(b1; : : : ;bNt
)b1b2b3b4bNt
: : :AttackerClients

39. 25/43
The Global Replication Game
IConstrained stochastic game.
IPlayers: (C)ontroller and (A)ttacker.IStates:SS=f0;1; : : : ;smaxg, the number of healthy nodes.IController actions: Add a
(C)
t2 f0;1gnodes.
IAttacker actions: a
(A)
t2 fF;Ag
Nt
.
IMarkovstrategies:

(C)
:SS!(f0;1g)

(A)
:SS!(fF;Ag
Nt
):
: : :1(b1)2(b2)3(b3)4(b4)Nt
(bNt
)
Belief
transmissionsNode controllers
Replicated
systemSystem controller(b1; : : : ;bNt
)b1b2b3b4bNt
: : :AttackerClients

40. 25/43
The Global Replication Game
IConstrained stochastic game.
IPlayers: (C)ontroller and (A)ttacker.IStates:SS=f0;1; : : : ;smaxg, the number of healthy nodes.IController actions: Add a
(C)
t2 f0;1gnodes.IAttacker actions: a
(A)
t2 fF;Ag
Nt
.IMarkovstrategies:

(C)
:SS!(f0;1g)

(A)
:SS!(fF;Ag
Nt
):
: : :1(b1)2(b2)3(b3)4(b4)Nt
(bNt
)
Belief
transmissionsNode controllers
Replicated
systemSystem controller(b1; : : : ;bNt
)b1b2b3b4bNt
: : :AttackerClients

41. 25/43
The Global Replication Game
IConstrained stochastic game.
IPlayers: (C)ontroller and (A)ttacker.IStates:SS=f0;1; : : : ;smaxg, the number of healthy nodes.IController actions: Add a
(C)
t2 f0;1gnodes.IAttacker actions: a
(A)
t2 fF;Ag
Nt
.IMarkovstrategies:

(C)
:SS!(f0;1g)

(A)
:SS!(fF;Ag
Nt
):
: : :1(b1)2(b2)3(b3)4(b4)Nt
(bNt
)
Belief
transmissionsNode controllers
Replicated
systemSystem controller(b1; : : : ;bNt
)b1b2b3b4bNt
: : :AttackerClients

42. 26/43
System Controller Objective
IZero-sumgame.ICost:J,limT!1
P
T
t=1
a
(C)
t
T
.
IConstraint: T
(A)
A, whereT
(A)
is the availability.
A Allowed service downtime per year
0:9 36 days
0:95 18 days
0:99 3 days
0:999 8 hours
0:9999 52 minutes
0:99999 5 minutes
1 0 minutes

43. 27/43
System Reliability Analysis
ITheMean-time-to-failure(mttf) is the
of a state wherestf:
E[T
(F)
jS1=s1] =E
(St)t1
h
infft1jStfg jS1=s1
i
:
102030405060708090100100200300pi=0:05pi=0:025pi=0:01N1E[T
(F)
]
Themttfin function of the number of initial nodesN1and failure
probability per nodepi.

44. 28/43
Theorem 5 (Best Response Existence and Computation)
Assuming
(A)The Markov chain induced by each strategy pairis
unichain.
(B)The.
Then the following holds.
1.For each strategy pair, there
responses.
2.Best responses can be computed by usinglinear
programming.

45. 29/43
Ecient Computation of Best Responses
481632641282565121024204810
0
10
2
Maximum number of nodessmaxTime (s)
Mean compute time to obtain a best response in the replication game.

46. 30/43
Denition 6 (Markov perfect equilibrium (MPE))
A strategy pair
?
= (
(C);?
;
(A);?
)is aMarkov perfect
equilibriumif

?
is a Nash equilibrium

47. 31/43
Theorem 7 (Existence of equilibrium in the global game)
Assuming
(A)The Markov chain induced by each strategy pairis
unichain.
(B)The.
Then the following holds.
1.A constrained, stationary mpe)
exists.
2.Computing the equilibrium isppad-complete.

48. 32/43
Equilibrium computation is intractable in general.
Challenge

49. 32/43
Equilibrium computation is intractable in general.
Challenge
Theorem 8
Given any attacker strategy, there exists a best responsecontrol
strategy that is decreasing ins.

50. 32/43
Ecient Computation of Equilibria
Equilibrium computation is intractable in general.
Challenge
Theorem 9
Given any attacker strategy, there exists a best responsecontrol
strategy that is decreasing ins.
Corollary 10
Given that the controller strategy is decreasing in s, a weakly
dominating strategy for the attacker is to minimizeE[S].

51. 33/43
The Benet of Strategic Replication2004006008001;0000:51EquilibriumN1= 10N1= 100tAvailabilityBenet of strategic replication
Strategic replication canguarantee a high service avail-
ability in expectation. The
is mainly prominent for long-running systems.
Key insight

52. 34/43
Summary of the Game-Theoretic Model
IPartially observed stochastic game
IThreshold structureof best responses.
IExistence ofperfect Bayesian equilibria.
IConstrained stochastic game
IThreshold structureof best responses.
IExistence ofMarkov perfect equilibria.
: : :1(b1)2(b2)3(b3)4(b4)Nt
(bNt
)
Belief
transmissionsNode controllers
Replicated
systemSystem controller(b1; : : : ;bNt
)b1b2b3b4bNt
: : :AttackerClients

53. 35/43
Experiment Setup - Testbed

54. 36/43
ThetoleranceArchitecture
Two-levelrecoveryand replicationcontrol with feedback.
toleranceNode 1Privileged domain Application domain
Service
replicaNode controller
ids
alerts
reco-
veryVirtualization layerHardwareNode 2Privileged domain Application domain
Service
replicaNode controller
ids
alerts
reco-
veryVirtualization layerHardwareNodeNtPrivileged domain Application domain
Service
replicaNode controller
ids
alerts
reco-
veryVirtualization layerHardware: : :Consensus protocolSystem controllerState estimateEvict or addState estimateEvict or addState estimateEvict or add : : :Service requestsResponsesClients AttackerIntrusion attempts
IA replicated
IAreadoperation that returns the service state.
IAwriteoperation that updates the state.

55. 37/43
Intrusion-Tolerant Consensus Protocol (minbft)
ClientReplica 1(leader)Replica 2Replica 3requestpreparecommitreplyReplica 1(leaderv)(leaderv+1)Replica 2Replica 3crash
request
view-changeview-changenew-viewReplica 1Replica 2Replica 3checkpointControllerReplica 1(compromised)Replica 2Replica 3recover
request
statestateNew replicaReplica 1(leaderv)(leaderv+1)Replica 2Replica 3join-requestjoinnew-viewjoin-reply
System
controllerReplica 1(leaderv)(leaderv+1)Replica 2Replica 3evict-requestevictnew-viewexit-replya) Normal operationb) View changec) Checkpointd) State transfere) Joinf) Evict

56. 38/43
Intrusion-Tolerant Consensus Protocol
3456789102040601 client20 clientsNumber of nodes (N)Avg throughput (req/s)
Average throughput of our implementation ofminbft.

57. 39/43
Experiment Setup - Emulated Intrusions
Replica ID Intrusion steps
1 tcp synscan,ftpbrute force
2 tcp synscan,sshbrute force
3 tcp synscan,telnetbrute force
4 icmpscan, exploit ofcve-2017-7494
5 icmpscan, exploit ofcve-2014-6271
6 icmpscan, exploit ofcwe-89 ondvwa
7 icmpscan, exploit ofcve-2015-3306
8 icmpscan, exploit ofcve-2016-10033
9 icmpscan,sshbrute force, exploit ofcve-2010-0426
10 icmpscan,sshbrute force, exploit ofcve-2015-5602
Table 1:

58. 40/43
Experiment Setup - Background Trac
Background services Replica ID(s)
ftp,ssh,mongodb,http,teamspeak1
ssh,dns,http 2
ssh,telnet,http 3
ssh,samba,ntp 4
ssh 5;7;8;10
dvwa,irc,ssh 6
teamspeak,http,ssh 9
Table 2:

59. 41/43
Estimated Distributions of Intrusion Alerts0 2000 4000 6000 8000
bz
i
(
o
i
j
a
(A) i
)
cve-2010-0426
0 2000 4000 6000 8000
cve-2015-3306
0 2000 4000 6000 8000
bz
i
(
o
i
j
a
(A) i
)
cve-2015-5602
0 2000 4000 6000 8000
cve-2016-10033
0 2000 4000 6000 8000
bz
i
(
o
i
j
a
(A) i
)
cwe-89
0 2000 4000 6000 8000
cve-2017-7494
0 2000 4000 6000 8000
oi2 O
bz
i
(
o
i
j
a
(A) i
)
cve-2014-6271
0 5000 10000 15000 20000
oi2 O
ftp,ssh,telnetbrute force
attack (a
(A)
i
=A) false alarms (a
(A)
i
=F)
IWe estimate the observation distributionzwith the
empirical distribution
b
Zbased onMsamples.
Ibz!
a.s
zasM! 1(Glivenko-Cantelli theorem).

60. 42/43
Comparison with State-of-the-art Intrusion-Tolerant
Systems
00:5110
1
10
2
00:10:200:5110
1
10
2
00:10:200:511525110
1
10
2
equilibriumbest-responseno-recoveryperiodicperiodic-adaptive1525100:10:215251Maximum time-to-recoveryRMaximum time-to-recoveryRMaximum time-to-recoveryRAverage availabilityT
(A)
Average time-to-recoveryT
(R)
Average recovery frequencyF
(R)
N1=3N1=6N1=9
Comparison between our game-theoretic control strategies and the
baselines; x-axes indicate values ofR; rows relate to the number of
initial nodesN1.

61. 43/43
Conclusion
IWe present agame-theoretic model of intrusion tolerance.
IWe establish.
IWe.
IOur game-theoretic strategies have
guarantees and signicantly better practical performance
the control strategies used in state-of-the-art
intrusion-tolerant systems.
: : :1(b1)2(b2)3(b3)4(b4)Nt
(bNt
)
Belief
transmissionsNode controllers
Replicated
systemSystem controller(b1; : : : ;bNt
)b1b2b3b4bNt
: : :AttackerClients