21-12-2012, 04:55 PM
How Bad Are Selfish Investments in Network Security?
1How Bad Are Selfish.pdf (Size: 696.12 KB / Downloads: 16)
Abstract
We study a network security game where strategic
players choose their investments in security. Since a player’s investment
can reduce the propagation of computer viruses, a key feature
of the game is the positive externality exerted by the investment.
With selfish players, unfortunately, the overall network security
can be far from optimum. The contributions of this paper are as
follows. 1) We first characterize the price of anarchy (POA) in the
strategic-form game under an “Effective-investment” model and a
“Bad-traffic” model, and give insight on how the POA depends on
individual players’ cost functions and their mutual influence. We
also introduce the concept of “weighted POA” to bound the region
of payoff vectors. 2) In a repeated game, players have more incentive
to cooperate for their long term interests. We consider the socially
best outcome that can be supported by the repeated game,
as compared to the social optimum. 3) Next, we compare the benefits
of improving security technology and improving incentives,
and show that improving technology alone may not offset the price
of anarchy. 4) Finally, we characterize the performance of correlated
equilibrium (CE). Although the paper focuses on network security,
many results are generally applicable to games with positive
externalities.
INTRODUCTION
NETWORK security depends not only on the security-related
investment made by individual users, but also on
the interdependency among them. If a careless user puts in
little effort in protecting his computer system, then it is easy for
viruses to infect this computer and through it continue to infect
others. On the contrary, if a user invests more to protect himself,
then other users will also benefit since the chance of contagious
infection is reduced. Therefore, each user’s investment has a
“positive externality” on other users. Since selfish users do not
consider the externality when choosing their investments.
Related Works
In [1], Gordon and Loeb presented an economic model to determine
the optimum investment of a single player to protect a
given set of information. The model takes into account the vulnerability
of the information and the potential loss if a security
breach occurs. The externalities among different players, or the
game-theoretical aspects, were not considered.
Varian studied the network security problem using game
theory in [2], where each player decides on a level of investment,
and the players’ investments affect the security of each
other. Reference [2] identifies network security as a public
good and shows that there is a free-riding problem that can
significantly reduce the social welfare. However, in the models
of [2], each player’s investment is assumed to be equally
important to all users (i.e., a symmetric case). In [3] and [4],
Kunreuther and Heal proposed a model of interdependent security
(IDS) for a range of problems including computer security.
In this model, a player decides on whether or not to invest in a
security mechanism, and he can suffer from “direct loss” and
“indirect loss” as determined by the decisions of himself and
others. However, the studies in [2]–[4] were not focused on the
analysis of POA as in this paper.
PRICE OF ANARCHY (POA) IN THE STRATEGIC-FORM GAME
In this section, we consider the POA in the strategic-form
game. We first formulate a general model that reflects the positive
externality of security investment and give a generic bound
of the POA. Then, we study an EI model and a BT model, both of
which are special cases of the general model, but describe more
specifically how the players’ investments benefit each other.We
show that the POA under these models tends to increase with the
dependencies among the players, the network size, and the imbalance
of network traffic.
REPEATED GAME
Unlike the strategic-form game, in repeated games the players
have more incentives to cooperate for their long-term interests.
For example, in an internal network in a university, or a local
area network, the security level of one user has a big impact on
others: If a user is poorly protected against external attacks and
is infected, the viruses/worms can explore/scan the internal links
and pose threats to others. Instead of playing a strategic-form
game with a large POA, it is possible for the users to play a
repeated game to achieve a better outcome. In this section, we
consider the performance gain provided by the repeated game.
Since there is a set of equilibriums in the repeated game.
CORRELATED EQUILIBRIUM (CE)
CE [18] is a more general notion of equilibrium than NE (the
set of CEs contains the set of NEs). CE is closely related to
mechanism design [19] that can be used to coordinate the actions
of the players to achieve better outcomes. As we explain
later, CE can also arise from simple and natural dynamics of the
players. In this section, we consider the performance bounds
of CE. Specifically, we are interested to know whether CE can
outperform NE in our security game, and what is the worst-case
performance of CE.
CONCLUSION
We have studied the equilibrium performance of the network
security game. Our model explicitly considered the heterogeneous
cost functions of the players and their influence to each
other. We showed that in the strategic-form game, the POA can
be very large and tends to increase with the network size, the dependency,
and imbalance among the players. This indicates severe
efficiency problems in selfish investment. Not surprisingly,
the best equilibrium in the repeated games usually gives much
better performance, and it is possible to achieve social optimum
if that does not conflict with individual interests. Implementing
the strategies to support a SPE in a repeated game, however,
needs more information and cooperation among the players.
We have compared the benefits of improving security technology
and improving incentives. In particular, we have shown
that the POA of pure-strategy NEs is invariant with the improvement
of technology under the EI model and the BT model,
and the benefit of technology improvement may not offset the
price of anarchy. Finally, we have studied the performance of
correlated equilibrium (CE). We have shown that although CE
cannot achieve SO in general, it can be much better than all
pure-strategy NEs. In terms of the worst-case bounds, the POAs
of discrete CE are the same as the POAs of pure-strategy NE
under the EI model and the BT model.