hello today i'm here to talk about
understanding strategy and deception
using game theory
a little bit about me my name is juno i
work as a red team consultant and also
do security research i moved to texas in
2018 from alaska and since then have
become really involved with the local
hacker community i currently run dc214
dallas's defcon group and i've been very
involved in the dallas hackers
association which is where i actually
got my start speaking about game theory
outside of the hacker community i also
volunteer and teach through girls who
code black girls code and at some other
local schools i've got my bachelor's
degree in computer science and economics
and i'm getting my master's degree in
cyber security from nyu and my contact
information is up on the screen if you
have any questions or comments or just
want to know more
just a little bit of a road map first
we're going to start by talking about
what is game theory and how has it been
used previously
and from there we're going to look at
the prisoner's dilemma which is one of
the most popular game theory examples
we're going to look at how to find a
simple equilibria and then look at a
repeated game where
the play where the players repeat the
same interaction more than once
next we'll look at brinksmanship how
drastic action can force your opponent's
strategy to change
and a signaling game where players have
the opportunity to trade information
that may or may not be true
using a very simple attack defense
scenario and we'll look at finding an
equilibria there as well and there are a
couple of definitions to keep in mind
the first of which game is the term i'm
going to use to refer to the interaction
that we're modeling and players is the
term we'll use for the ones doing the
interaction whether or not they're human
and rationality is defined by economists
is a little bit different it's defined
as doing what is best for oneself 100 of
the time now
that's quite a different definition than
i'd say most of us have but in this
scenario but we need this
in order to prove why or we need this as
a as a rule in order to explain why
players choose the highest payoffs in
our models moving forward
so we're actually going to start with
one of the most common game theory
examples the prisoner's dilemma
you're probably familiar with it it's
pretty popular either in the pilot
episode of half a dozen cop shows or
intro to psych in philosophy textbooks
but if you're not familiar it's
really where two individuals are
arrested after committing a crime
they're separated and offered the same
plea deal
uh the
that gives them two choices the first
choice we'll call defect
confess and you will go free only your
partner will be charged or cooperate
stay silent don't say anything
however if both players choose to defect
both will be charged if both cooperate
without communicating both will get a
lighter sentence
now obviously that's the best option but
is that what really happens
so here i have a payoff matrix for our
two prisoners alice and bob
and alice and bob
both have the option to cooperate or
defect
the the numerical values i have assigned
is the payoff just represent the amount
of good to each individual player
for example if alice chooses to defect
while bob chooses to cooperate she gets
that highest payoff of two the best
possible outcome for alice getting off
free
while bob gets that payoff of negative 1
the worst possible outcome for him which
is
getting the maximum sentence
now
because alice and bob are separated
they're essentially making their
decisions independent of each other this
is a simultaneous game
so all each player has to go off of is
what they believe their opponent will
choose to do
so
if alice believes that bob will choose
to cooperate she'll choose to defect for
that higher payoff
similarly if she believes bob will
choose to defect she'll choose to defect
as well again for the higher payoff
and because bob's in the exact same
situation and has the exact same payoff
he'll make the same choices choosing to
defect if he believes alice is going to
choose to cooperate
or choosing and choosing to defect if he
believes she'll choose to defect
this leaves us with a logical outcome of
the game or the nash equilibrium where
both players defect
now obviously this isn't the best
outcome of the game for either player
if both players choose to cooperate we
have what's called a pareto optimal
outcome an outcome that's better for
both players
however in real life this doesn't just
happen in a vacuum nothing in my
previous model addressed any of the
potential consequences of these
decisions outside of the direct
interaction
so we can start to make the model more
realistic by looking at a repeating game
where alice and bob end up in the same
situation over and over and end up
having to choose whether to cooperate or
defect each and every time again and
again
and when the same interaction happens
repeatedly players can begin to use a
punishment strategy to motivate each
other to make the choices
that they would want
and there are many types of punishment
strategy but we're going to look at the
great what's called the grim trigger
punishment strategy cooperate until the
trade and then choose to defect forever
after that now obviously this leaves the
player open to betrayal at the beginning
but there's
retribution if the player is betrayed
one thing we have to keep in mind when
we're looking at the math for this
though is the discount factor which is a
measure of patience
essentially future payoff is worth less
than present payoff
ten dollars now is worth
ten dollars ten dollars
two days in the future is worth ten
times d a number from zero to one that
represents the decrease in payoff
so
if you're in if you're in a scenario
and you believe that your opponent is
using a grim trigger punishment strategy
you know that as long as your
you haven't defected your opponent will
cooperate with you
so we can find the payoff to cooperate
is going to be equal to 1 minus the
discount factor
multiplied by one the best possible
payoff you can get in the scenario if
you're
or sorry multiplied by one the payoff
you get
for cooperating
plus one the payoff you get for
cooperating multiplied by the discount
factor on out in repeating out into the
future
and this actually just simplifies down
to one
and
then if you choose to defect your payoff
is going to be equal to one minus the
discount factor multiplied by two that
payoff you get for defecting
right now plus
zero multiplied
the best zero which is the best possible
payoff you can get after choosing to
defect now that you know your opponent
is choosing to defect every single time
multiplied by the discount factor on out
into the future and this simplifies down
to two minus one d
and so when we
and when we
put these equations together we find
that the payoff to cooperate is greater
than the payoff to defect
as long as the discount factor is
greater than one half so for cooperation
to have a higher payoff than defecting
the future payoff must be worth at least
half of the current payoff
however
if you do choose to trade your opponent
you know that they will play defect
indefinitely
so then your payoff to cooperate is
going to be equal to 1 minus the
discount factor
my multiplied by negative one the payoff
you get for cooperating when you know
your opponent is going to defect plus
zero the best possible payoff you'll get
the next round
uh with your opponent defecting
multiplied by the discount factor on out
into the future which simplifies down to
d minus one
and the payoff to defect is going to be
one minus d
multiplied by zero the payoff you get
for defecting along with your opponent
plus zero the best possible payoff you
can get multiplied by the discount
factor again on out into the future
and so the payoff to cooperate in this
scenario is only greater to the payoff
to defect
when d is greater than one which isn't
possible because it's a percentage so
if you believe your opponent is using a
grim trigger strategy once you have
defected it is better to continue to
defect
so
next we're going to talk about
brinksmanship which is defined as the
practice of trying to achieve an
advantageous outcome by pushing
dangerous events to the blink of a brink
of active conflict
so here we have another scenario between
alice and bob where alice and bob are
playing a game of chicken
and each player has the option to swerve
or to stay
and if both players swerve they tie
if one player swerves while the other
one stays the one that stays wins the
game of chicken
however if both players stay and neither
of them swerve they crash and so again
like in our last model we can translate
this into a payoff matrix essentially
ranking the outcomes for each player
so
like our previous game this is a
simultaneous game
and
all our players can base their decisions
off of is what they believe that their
opponent will do
so if alice believes that bob will
choose to swerve she'll choose to stay
to win the game for that highest payoff
of two
and if she believes that bob will choose
to stay she'll choose to swerve for to
avoid the crash and for that higher
payoff of zero
and
bob is in the same situation and has the
same payoffs
choosing to
stay if he believes alice will swerve
and swerve if she stays so our two
national nash equilibriums
are where alice stays and bob swerves
and alice swerves and bob stays
now
what if they had different motivations
what if instead of bob being alice's
opponent alice's opponent opponent was
say a stuntman in a stunt car who could
take a crash without as much damage as
she could
in this scenario our stuntman would
choose to stay
whether or not he believed alice choose
to swerve or stay
so this makes our nash equilibrium an
outcome where alice chooses to swerve
and the stuntman would choose to stay
instead of what we saw with two equally
matched opponents like alice and bob
so going back to the alice and bob
example
here we have a decision tree that models
the same payoff matrix we showed for
alice and bob
alice has the choice to stay or swerve
and then next bob has the choice to stay
or swerve now because this is a
simultaneous game
bob doesn't actually know whether alice
has chosen to stay or swerve swerve he
doesn't know which node on our decision
tree he's at and so this is
and this uh dotted line between our two
bob nodes denotes that lack of
information
so
enrinksmanship is essentially the act of
removing one of these options
so let's say
as alice is driving she calls out hey i
cut my brakes i can't stop
what alice essentially does in that
scenario
is she removes half of the tree she says
i am not going i cannot swerve
i'm going to stay
you have to make your choice based on
that and so then bob knows exactly where
he is he has to choose to stay or swerve
based on
his knowledge that alice will choose to
stay and that spreadship is is
essentially removing half of the
decision tree using a dangerous action
to force your opponent into making a
decision based on that
so next we're going to look at a very
simplified down attack defense scenario
between
two players an attacker and a defender
and essentially the defender has the
choice to choose to monitor their stuff
or not
and the attacker has the choice to
attack a system they come across or to
ignore it and move on to the next thing
and
so and if
an attacker believes the defender is
going to be monitoring a system they're
not they're going to pass on attacking
it
however if they believe the system is
not monitored they're going to choose to
attack
likewise
if a defender believes their systems
will be attacked they'll choose to
monitor but if they believe they won't
they won't choose to monitor
so unlike in our previous games we don't
have a nash equilibrium or a logical
outcome to the game
so to start to find an equilibrium we're
going to look at p the likelihood the
defender will choose to monitor their
systems in the first place
and so for an attacker the expected
value of attacking something they come
across is equal to p the likelihood the
system is monitored
multiplied by the payoff
the system they attack they get if the
system they attack is monitored that
payoff of negative 10
plus 1 minus p or the likelihood the
system is not monitored plus 10 which is
the payoff of attacking a system that's
not monitored so the expected value of
attacking is going to be equal to
negative 10 p plus 10 multiplied by one
minus p
and the expected value of passing is
always going to be equal to zero
so when we set those equal to each other
we get p is equal to one half this means
that p is equal to one half or if it's
50 50 whether
system is monitored the attacker is
indiff is forced into indifference about
whether or not they attack
and we can see this with this graph that
i have here essentially the expected
value to the attacker goes down
as the likelihood that this uh the
system is being monitored increases
and so
and so by uh by changing p
defenders can actually force the
attackers into indifference
or into making a different decision
now
what happens when one player can lie
how
we saw how information can change an
outcome of a game
but how do we actually change that
information
well using a signaling game we can start
to look at what happens when a player
starts to use or starts to
signal with information that may or may
not be false
in order to in order to force their
opponent into a different outcome
so for our signaling game we're going to
look at the same game with two players
attackers and defenders but this time
our defenders are either high or low
quality
and attackers want to attack low quality
defenders
now any defender can signal that it's a
high quality defender and its systems
are secure
but signaling comes at a cost and this
cost is higher for low quality defenders
and i should talk for a minute about
what a signal actually looks like
because there is a big difference
between a credible signal and one that's
not for example
if a company tweets on twitter
we're unhackable we're gonna see them go
down in probably the next three hours
um but a lot of signals we see are
things like
buying
buying overpriced you know security
systems that never actually get properly
implemented stuff like that and this is
a bit of an abstract example but
or the uh this model is a bit abstract
but it's good to keep those real world
examples in mind
now one thing to keep in mind is the
attacker does not know what capabilities
the defender it comes across has this
makes this game a game with incomplete
information
so here i have another decision tree for
our signaling game
and the first move is just a move by
nature determining whether any given
defender is high or low quality and
we're going to say high quality
defenders appear at a percentage of
one third or 33 percent of the time
and uh low quality defenders who can't
monitor their stuff
appear at a percentage of 66 percentage
of the time
next is the choice by the individual
defender to signal that they're a high
quality defender or not and of course
that signal comes at a cost
and finally the choice by the attacker
to attack or pass and the dotted line
between these attacker nodes here
signals that the attacker does not know
which part of the tree that it's on
the attacker knows only that they've
seen a signal not whether or not
the defender is high or low quality
so first we're going to look for a
separating equilibria where different
players do different things
so
we're going to say if a defender is high
quality
they'll choose to signal and if a
defender is low quality they'll choose
not to signal
in this scenario if an attacker sees a
signal they'll choose to pass
knowing that
high quality defenders are signaling 100
of the time
and if they see no signal they'll choose
to attack knowing that low quality
defenders are not signaling 100 of the
time
now this doesn't this uh this equilibria
actually fails
because
if we see our low quality defenders are
choosing not to signal and are getting
attacked for that payoff of negative ten
however
if attackers are passing on 100 of
signals
it's worth it for low quality defenders
to choose to choose to pay to signal for
that payoff of 10 instead
and so uh so this does so this
separating equilibria doesn't work
so next we're going to look for a
pooling equilibrium where all defenders
choose to signal
if all defenders are signaling attackers
are going to attack x percent of the
time based on the probability the signal
is coming from a high or low quality
defender
and the probability of the signal coming
from a high quality defender is
one-third the rate at which they appear
based on nature and the probability of
signals coming from a low quality
defender is going to be equal to
two-thirds based on the rate they appear
in nature
so
if attackers attack x percentage
oh and the
and the payoff for attacking a high
quality defender is negative 10 the
payoff for attacking a low quality
defender is 10.
so
the expected value to an attacker of
signaling or of attacking given that
they've seen a signal
is going to be equal to the probability
the signal is coming from a high quality
defender multiplied by that payoff of
attacking a high quality defender that
negative 10
plus the probability the signal is
coming from a low quality defender
multiplied by the payoff of attacking a
low quality defender
and this ends up being equal to three
and a third
the expected value of passing is always
going to be equal to zero
so in this scenario a hundred percent of
the time the expected value of attacking
is greater than the expected value of
passing so attackers will attack 100 of
the time
so next we're going to look for
semi-separating equilibrium and that's
where if a defender is high quality
they'll choose to signal and if the
defender is low quality they'll choose
to signal x percentage of the time
and so attackers if they given that
they've seen a signal will choose to
attack why percentage of the time and
given that they've seen no signal will
attack a hundred percent of the time
so
the problem
and uh here i have the equations for the
probability that the signal comes from a
high quality defender and the
probability if it comes from a low
quality defender which we'll need later
but i won't get into
how how i found that just right now
so first we're going to choose or we're
going to find why the probability the
attacker will attack a defender given
that they've seen a signal so
and to find that we're going to look at
the expected value to a low quality
defender
the expected value to a low quality
defender of signaling is going to be
equal to y
the probability they get attacked
multiplied by the payoff of sending a
signal and getting attacked that
negative 13.
plus one minus y the likelihood the
player is not attacked multiplied by the
payoff of sending a signal and getting
passed on which is that payoff of seven
and we'll compare that to the expected
value
of not sending a signal which is the
payoff of
getting attacked
or negative 10. and when we set those
equal to each other y is going to be
equal to
17 over 20 meaning that attackers will
attack if they see a signal 17 times out
of 20.
and so what this
uh what this ends up looking like is the
expected value of s of signaling
decreases
as uh as the as as y increases and when
y is equal to 17 over 20 low quality
defenders are
indifferent about whether or not they
signal
and so from there
we're going to do the same thing to find
x the probability a defender
with
low qual or a low quality defender will
signal will signal that they're high
quality and that's going to be based on
the expected value
to an attacker of attacking which is
going to be equal to the probability the
signals coming from a high quality
defender multiplied by the payoff of
attacking a high quality defender plus
the probability the signal is coming
from a low quality defender multiplied
by the payoff of attacking a low quality
defender
and the expected value of passing is
always equal to zero
so when we set those equal and solve for
x x is going to be equal to one fourth
so in this scenario
a quarter of low quality defenders will
signal that they can monitor their
systems
and so again we can graph the expected
value to an attacker as
as x the likely uh the likelihood that
a low quality defender is choosing to
signal increases
the expected value of attacking
increases along with it and when x is
equal to 1 4 attackers are forced into
indifference
so
when we see when we see or is so when we
run through this game with these with
these numbers
we find uh we find a semi-separating
equilibrium where a quarter of low
quality defenders will signal will
signal that they're high quality and
attackers will attack given that they've
seen a signal 17 times out of 20.
so where do we go from here
i hope to have given you a good
demonstration of how we can break down
conflict into steps
and by going through those steps and
determining the payoffs each step of the
way we can start to model the outcomes
using game theory
i also we can also watch how strata
strategies interact and can change each
other
and i want you to think about where do
you see some some examples of some of
these similar strategies being used on a
regular basis what do you think you can
start to apply this to
now obviously there are some limitations
i'd say one of the biggest limitations
of game theory is determining payoffs
and motivation in a realistic fashion
the numbers i used in these examples
were just that examples to make the math
come out you know relatively nicely
how uh however when determining payoffs
i often try to look at it is
essentially ranking the outcomes for
each uh for each of the players or
doing amount and from that doing the
amount of net positive or negative but
there are a lot of different ways
and it's often hard it's often hard when
uh
with some of these more complex games
when there are motivations you
potentially may not have been able to
account for
and as these games get more and more
complex of course they're they're harder
they're harder to model especially
without the use of a computer
but we've been using game theory to
model conflict throughout centuries and
i believe when applied to cyber security
we can create complex and robust models
of threat behavior
anyways my name is juno thank you so
much i have my contact information below
please feel free to reach out with
questions and i have some of my sources
and further reading reading up there
thank you so much