

small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution


USING NONCOOPERATIVE POTENTIAL GAMES TO IMPROVE NETWORK SECURITY By PATRICK D. HARRINGTON Bachelor of Arts, English Oklahoma Baptist University Shawnee, OK 1996 Bachelor of Science, Computer Science Northeastern State University Tahlequah, OK 1999 Masters of Science, Computer Science University of Tulsa Tulsa, OK 2002 Submitted to the Faculty of the Graduate College of the Oklahoma State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY July, 2010 ii USING NONCOOPERATIVE POTENTIAL GAMES TO IMPROVE NETWORK SECURITY Dissertation Approved: Dr. Johnson Thomas Dissertation Adviser Dr. George Hedrick Dr. Nohpill Park Dr. Marilyn Kletke Dr. Mark E. Payton Dean of the Graduate College iv ACKNOWLEDGMENTS I would like to first and foremost thank my wife, Rayna, for her unfailing support during my graduate career. I would also like to thank my advisor, Dr. Johnson Thomas, for his guidance, wisdom, and perspective for my work, as well as Drs. Hedrick, Kletke, Park, and Chandler for their help. I would also like to express thanks to the Department of Mathematics & Computer Science at Northeastern State University in Tahlequah, and in particular my department chair, Dr. Darryl Linde, for arranging my work schedule to facilitate making progress toward a PhD. This would also not have been possible without the support of the faculty, in particular Dr. Rick Matzen, Bill King, Gordon Shamblin, and Dr. Rad Alrifai. I would also like to especially acknowledge Bill, Gordon, and Rick for their lending of books and advice on mathematics. I would also like to thank my parents, Drs. Doug Harrington and Elisabeth WentzHarrington, for encouraging me to pursue a career in computer science and in teaching; and my late mother, Martha Harrington, who inspired me to live life fully. v TABLE OF CONTENTS Chapter Page I. INTRODUCTION ......................................................................................................1 II. REVIEW OF LITERATURE..................................................................................10 III. SECURITY METRICS ..........................................................................................33 3.1: Problem definition ..........................................................................................37 3.2: Security metrics ..............................................................................................40 3.3: Cryptography ..................................................................................................40 3.4: Data sensitivity ...............................................................................................41 3.5: Access control .................................................................................................42 3.6: Security metrics example ................................................................................43 IV. CONSTRAINT SATISFACTION.........................................................................47 4.1: Constraint satisfaction problems .....................................................................47 4.2: Costs................................................................................................................52 4.3: Side payments .................................................................................................54 4.4: Objective function...........................................................................................56 4.5: Constraint satisfaction problems and game subset solvability .......................56 4.6: Utility ..............................................................................................................63 4.7: Equilibrium in a game.....................................................................................64 V. GAME THEORETIC ANALYSIS .........................................................................67 5.1: Coalition formation for a weighted potential game ........................................67 5.2: Attack tree analysis to improve security .........................................................74 5.3: Pareto optimization .........................................................................................84 5.4: Game to optimize network security ................................................................90 5.5: Pure strategy game ..........................................................................................90 5.6: Mixed strategy game .......................................................................................92 5.7: Gamebased architecture .................................................................................94 VI. VALIDATION ....................................................................................................101 6.1: Comparing our algorithm to an established algorithm .................................101 6.2: O(n) analysis .................................................................................................112 vi Chapter Page VII. FINDINGS .........................................................................................................117 7.1: Prototype One ...............................................................................................121 7.2: Prototype Two...............................................................................................145 7.3: Prototype Three.............................................................................................156 7.3.1: Prototype Three Version Two..............................................................169 7.4: Prototype Four ..............................................................................................185 7.4.1: Prototype Four Version Two ...............................................................195 7.5: Kerberos comparison ....................................................................................197 7.6: Varying network size: a comparison ............................................................210 7.7: Detailed summary of results .........................................................................225 VIII. CONCLUSION .................................................................................................231 8.1: Future work ...................................................................................................235 REFERENCES ..........................................................................................................237 vii LIST OF TABLES Table Page 1.1: Prisoners’ dilemma ..............................................................................................8 3.1: Cartesian product of security metrics converted to real values .........................46 5.1: Security levels with coalitions ...........................................................................72 5.2: Security levels and changes brought about by removing coalitions ..................73 5.3: Noncoalition security levels .............................................................................73 7.1: Overview of all prototypes’ similarities and differences .................................119 7.2: Average security comparison, Prototype one ..................................................142 7.3: Average utility improvement comparison, Prototype one ...............................145 7.4: Table of Prototypes and General Results .........................................................224 viii LIST OF FIGURES Figure Page 2.1: Komali [4] simulation: Utility improvement ...................................................21 5.1: Attack tree analysis and vulnerability reduction example diagram .................76 5.2: Game layer diagram .......................................................................................100 7.1: Utility improvement, candidate nodes, prototype one ...................................123 7.2: Average utility improvement of network with homogeneous minimum security, prototype one ...................................................................................125 7.3: Comparison of candidate nodes' security, prototype one ..............................126 7.4: Average network security, same minimum, prototype one ...........................128 7.5: Average network security, different minima, prototype one .........................128 7.6: Average security, prototype one ....................................................................129 7.7: Average network utility improvement, prototype one ...................................130 7.8: Candidate nodes' security, different vs. same minimum security, prototype one .................................................................................................131 7.9: Average utility improvement of three networks, prototype one ....................134 7.10: Average security of three networks, prototype one .......................................136 7.11: Percent of achieved maximum security for three networks, prototype one ................................................................................................138 7.12: Average security, selected networks, prototype one......................................140 7.13: Average utility improvement, selected networks, prototype one ..................143 7.14: Average security, prototype two ....................................................................148 7.15: Average local neighborhood count, prototype two ........................................151 7.16: Average utility improvement, prototype two .................................................152 7.17: Average number of nodes forming a coalition, prototype two ......................153 7.18: Percentage of coalition members with sensitive data access, no side payments .................................................................................................154 7.19: Average security, prototype three ..................................................................158 7.20: Average local neighborhood count, prototype three ......................................161 7.21: Average utility improvement, prototype three ...............................................162 7.22: Average number of nodes forming a coalition, prototype three ....................163 7.23: Percentage of local neighborhood that is in coalition, prototype three .........164 7.24: Percentage of coalition members with sensitive data access, prototype three................................................................................................................165 7.25: Percent of nodes making side payments, prototype three ..............................167 7.26: Average security, prototype three v.2 ............................................................170 7.27: Average security, prototype three v.1 and v.2, max security = hetero min+5 .................................................................................172 ix Figure Page 7.28: Average security, prototype three v.1 and v.2, max security = hetero min+6 ................................................................................173 7.29: Percent of nodes making side payments, prototype three v.2 .......................175 7.30: Average local neighborhood count, prototype three v.2 ...............................176 7.31: Average local neighborhood count, prototype three v.1 and v.2 ..................178 7.32: Average maximum security, prototype three v.1 and v.2 .............................179 7.33: Average utility improvement, prototype three v.1 and v.2 ...........................180 7.34: Average number of nodes forming coalition, prototype three v.1 and v.2 ...........................................................................................................181 7.35: Average percentage of coalition members granted sensitive data access, prototype three v.1 and v.2 ...............................................................182 7.36: Best performing networks per respective prototype .....................................184 7.37: Average security, pure and mixed strategies ................................................187 7.38: Average security, prototype four ..................................................................189 7.39: Average utility improvement, prototype four ...............................................191 7.40: Percent of nodes making side payments, prototype four ..............................193 7.41: Average local neighborhood count, prototype four ......................................194 7.42: Average security, prototype four v.2 ............................................................196 7.43: Average security, Kerberos...........................................................................198 7.44: Percent of all nodes able to participate in Kerberos .....................................199 7.45: Average security for all prototypes, n=43 ....................................................202 7.46: Security comparison, max = hetero min plus 3 network ..............................204 7.47: Security comparison, max = hetero min plus 4 network ..............................205 7.48: Security comparison, max = hetero min plus 5 network ..............................206 7.49: Security comparison, max = hetero min plus 6 network ..............................207 7.50: Security comparison, max = hetero min plus 7 network ..............................208 7.51: Security comparison, max = hetero min plus 8 network ..............................209 7.52: Prototype 1 security, varying n .....................................................................212 7.53: Prototype 2 security, varying n .....................................................................213 7.54: Prototype 3 v.1 security, varying n ...............................................................214 7.55: Prototype 3 v.2 security, varying n ...............................................................215 7.56: Prototype 4 v.1 security, varying n ...............................................................217 7.57: Prototype 4 v.2 security, varying n ...............................................................218 7.58: Kerberos security, varying network size n....................................................219 7.59: Average security for all prototypes, n=20 ....................................................221 7.60: Average security for all prototypes, n=60 ....................................................222 7.61: Average security for all prototypes, n=80 ....................................................223 x SYMBOLS A partition on graph G that divides it into coalitions c cost c (si ) cost of security value si for vertex vi c ((sij), σij (sij )) cost of security value sij for edge eij given constraints σij d (j) data of node j E set of edges eij edge from vertex i to vertex j eij all other edges besides vertex i to vertex j G graph composed of the set of vertices and set of edges Γ game of G i node (player) i, represented in the graph by vertex vi j node (player) j, represented in the graph by vertex vj Π potential function rij (d(j)) read access from i to j set of positive real numbers S nondecreasing sequence of nonnegative security levels si security level of player i si security levels of all other players besides i sij security level of eij sij security level of eij s*i optimal action for player i s*i optimal action for all other players besides i xi s* action profile in equilibrium (sij , σij (sij )) security of sij given constraint σij ; also known as move sij for player i , suboptimal move for player i , optimal (equilibrium) move for player i cij(sjk , σjk (sjk )) side payment move for player i to j to induce change in sjk σi constraint of player i σi constraints of all other players besides i σi (si ) constraint of security value si for player i σi (si ) constraint of security value si for all other players besides i σij (sij ) constraint σij of sij u utility function V set of vertices vi vertex i, also referred to as node i or player i vj vertex j, also referred to as node j or player j wij (d(j)) write access from i to j yij current encryption strength of connection eij xii DEFINITIONS • Action: assigning a value to a variable. • Action profile: a sequence of actions for each player in the game; there is one action corresponding to each player in the sequence. • Coalition: a group of players who share a common security level and preferences. • Constraint: a function which maps the domain of possible values a variable may take to the codomain or range of values that do not violate the constraints. • Constraint satisfaction problem: abbreviated CSP, it is a problem defined by a set of variables and corresponding constraints on the variables. • Cooperative game: a game in which players make binding commitments that require the consent of all parties to break the commitment. • Cost: a measure of lost utility. Cost is denominated in units of security. • Edge: see Link • Equilibrium: the best possible move a player can make based on the assumption that all other players also make their best possible moves. Equilibrium maximizes utility, and is a partial order on the actions: they are reflexive, antisymmetric, and transitive with respect to one another. xiii • Finite Improvement Property: all potential games possess this property whereby there is a best possible move for each state of the game. Neither the game nor the improvement can go on forever, and there can be no repeated states, as the game must have a finite end with unique moves and finite utility. • Game: a game consists of the Players, Information, Actions, and Utilities. • Game theory: the study of actions by decisionmakers who are aware that their actions have an impact on others. • Information: a player’s knowledge about the set of variables describing the game, which includes constraints on what actions can and cannot be taken. • Incomplete Preferences: see Partial Preferences • Link: a oneway directed connection between nodes. • Metric: see Security metric • Mixed Strategy: a plan that maps a player’s information to a probability distribution (ranging from 0 to 1) over the set of pure strategies. • Nash equilibrium: see Equilibrium • Node: nodes in graph G represent computers in the network. Nodes are the players in the game. • Noncooperative game: a game in which any commitments made can be unilaterally broken. • Objective function: describes a function to be maximized by all variables in the constraint satisfaction problem. Not all constraint satisfaction problems have an objective function. xiv • Pareto optimized: a state in which a player can take no action deviating from this state without decreasing utility for itself or some other player. • Partial Preferences: equations in which a set of variables may have intermediate or unassigned values. • Partition: to form coalitions, the network is divided into nonoverlapping subsets according to a pairwise disjoint function known as a partition. • Pay: compensation measured in utility to or from another node. • Player: an individual making decisions and taking actions in the game. See also Node, as players are represented by nodes or computers in the network. • Potential function: the potential function takes the same input as the utility function, and returns a calculation that is either the same sign (for an ordinal potential function) or equal to (for an exact potential function) the value calculated by the utility function of each player. The exact potential function is defined as applicable when players move according to mixed strategies, while the ordinal potential is defined to be applicable when players move according to pure strategies. • Potential game: a game possessing a potential function. • Preferences: the current best values for the variables in the game. Since the variables in the game represent security levels, the preferences are the current optimal security levels. They correspond to the environment and its current state. • Problem state: some, but not necessarily all, variables have values assigned to them. • Pure strategy: a plan that maps a player’s information to a single action. • Security: the opposite of vulnerability. In our game, security is optimized by minimizing vulnerability. xv • Security metric: quantitative measurement of some aspect of security. Our metrics are cryptography, data sensitivity, and access control. • Side payment: an action that consists of a payment made from node i to node j to induce j to change the security of its link sjk to another node k. • Solution: a complete assignment of values to variables in a constraint satisfaction problem that do not violate the respective constraints. • Strategy: a plan to take a specific action in a game. Each player has a set of strategies that govern the player’s actions in every conceivable situation. • Utility: the quantity of positive feedback (which in our game is security) which a player receives for taking an action. Utility is denominated in units of security. • Utility function: the utility function takes as input the set of possible actions available to a player and determines a player’s preference over the given set of possible actions. These preferences enable a player to choose the best values that can be assigned to the game variables and maximize its utility at each turn in the game. • Vulnerability: a weakness whereby an outsider may destroy, alter, or steal one’s possessions, which is the data possessed by the nodes as well as the nodes themselves. Vulnerability is the opposite of security. • Weighted potential game: a type of potential game that possesses a utility function which is directly related to other players’ utility functions. A weighted potential game possesses a potential function for either mixed or pure strategies. We use a weighted potential game to optimize network security. 1 CHAPTER I INTRODUCTION Computer networks have changed significantly since their first invention. In the early days of the Internet, the network was composed of nearly identical computers connected to one another by wire, whereas today’s wireless network consists of increasingly heterogeneous devices ranging from PCs to iPhones to servers. Not only are today’s networks more complex to secure, but the attacks on the network are far more sophisticated. The advent of cloud computing and of cyberphysical systems composed of sensor networks, actuators, and control systems has only increased the heterogeneity and complexity of securing such a network. While a great deal of work has been reported on security for individual computers or devices, very little work has been done to optimize security for the overall network when all devices forming the network are not only heterogeneous but also autonomous. The security of the entire network itself is critical and cannot be done piecemeal. The problem considered in our work is how to maximize an entire network’s security when it is made up of computers or devices that may be very different from one another. The computers act independently and autonomously, with no broad or central coordinator. There has been previous research with focus on individual components 2 forming the network, such as Agah [26,27] and Demirbas [29], but these approaches are limited as they fail to optimize security for the entire network. In these approaches, network security is only as good as the security of the weakest component. Our work proposes to allow individual computers to work together to achieve the optimum security for the entire network using game theory. The problem considered in our work centers on a general representation of heterogeneous computers, each with different hardware and software. We consider hardware to include all physical, nonsoftware related computer components such as CPU, RAM, and available power or battery life. Software thus includes both system software, which refers to the operating system, and application software, which includes all other software. The hardware and software of a computer will subsequently restrict its ability to sustain maximum security, which is only possible in an ideal world. The network under consideration is a wireless network, where connections between nodes are assumed to exist a priori. The nodes themselves are not physically mobile, but we assume connections change. These connections change during the network security optimization process. Game theory is one solution to address the problem of maximizing security within a system’s limitations. Game theory, as defined by Rasmusen [8], is the study of actions by decisionmakers who are aware that their actions have an impact on others. A game consists of the players, information, actions, and utilities. The players are defined as the individuals making decisions and taking actions in the game. We define the computers in the network as nodes, and these nodes are the players in our game theoretic security solution proposed in our thesis. In this situation, the players are the computers, or nodes, 3 in the network. The information is defined as the players’ knowledge about the set of variables describing the game, which includes constraints on what actions can and cannot be taken. These variables are input to a player’s utility function, which determines a player’s preference over a given set of possible actions. The utility function takes as input the set of possible actions available to a player and determines a player's preference over the given set of possible actions. These preferences enable a player to choose the best values that can be assigned to the game variables and maximize its utility at each turn in the game. This plan of action is its strategy. The player then takes the best action by assigning these best values to its variables, resulting in a new state of the game. At each turn in the game the player applies new information to its utility function, determines its preference over a given set of possible actions, chooses the best values that can be assigned to the game variables, and maximizes its security. Game theory as an optimization technique offers several advantages over other rulebased, linear programming, treepruning or backtracking algorithms, as well as artificial intelligence (AI) techniques. Game theory allows the game designer to arrive at a solution by developing the model and evaluation criteria for players so they can determine the optimal next move to make in the game to maximize their utility; as the game plays out, the solution evolves, giving the optimal configuration for the network. The designer of the game need only model the moves of the game and their context, allow the players to act autonomously according to these rules, and an optimization results. Furthermore, game theory has the advantage of finding solutions to problems that would otherwise be difficult to solve using other approaches. Game theory can be used 4 to model complex interactions and environments, which in our problem is a heterogeneous network. The use of mixed strategies is unique to game theory and allows for modeling more complex decisionmaking processes than could be done by other techniques. Through the use of mixed strategies, the game designer is able to model the possibility of mistakes made by game players. With pure strategies, players always choose the optimal strategy. With mixed strategies, however, a player chooses a move according to a probability distribution over the set of pure strategies, thus taking the optimal action some percentage of the time and less than optimal otherwise. In our thesis, we will examine the methodology behind how certain game subsets have been proven to have mathematical advantages over others and how such game subsets make it easier to prove a solution is optimal. Furthermore, our thesis will take advantage of the modeling techniques exclusive to a game theoretic problemsolving approach through mixed strategies. It will also allow coalitions, which are otherwise known as groups, to be formed among the game players as part of the game optimization process. Coalitions can be used to improve efficiency as well as give a broader and greater overall security than would be possible in the absence of coalitions. We will develop a heterogeneous game theoretic distributed security model in which game players choose the move that optimizes security; once a player acts on its choice of moves, the state of the game changes, and game play leads to security optimization of the network. An important aspect of our work is that the security optimization found can be validated as opposed to existing or traditional solutions, whose effectiveness is subjective. Traditional security definitions such as “works as expected” [31] are no 5 longer sufficient. An April 2009 report by the Homeland Security Newswire [34] revealed that because they are now connected to the Internet, a significant number of US power plants have, over the past few years, had their systems compromised by intruder programs, and that these potential sleeper agents are still in place in the systems across the entire US electrical grid. Furthermore, these programs have become embedded in other parts of the US infrastructure, which includes water treatment plants. To date, no one is certain how to remove them, or what these programs' function truly serves beyond gathering intelligence, but the sophistication with which they are embedded suggests a wellfinanced organization with skilled members, and is thus most likely related to a foreign government. If so, it is likely that these programs indeed will become active if the US goes to war with the foreign government that put the sleeper software there, and can potentially devastate the US infrastructure. Still, the systems are continuing to work "as expected," and "officials...do not see an immediate danger" [34]. We believe that statements such as these are representative of the traditional security paradigm and do not preclude the possibility that these programs will prevent our power plants to continue to work "as expected" in the future. Clearly, there is a significant need for paradigm shift in the definition of security from a qualitative definition to one that can be measured quantitatively. Security metrics can be used as means to accomplish this paradigm shift. Security metrics is a new field of computer security and its viability as a field of study was first recognized as serious work only a few years ago, but it is beginning to become more widely used. The goal of security metrics is to be able to better analyze security by evaluating a system and quantitatively representing its inner workings and relationships between entities that form the system 6 itself. Security metrics can thus be used as a basis to give quantitative meaning to the qualitative definition. To use metrics in our security solution, we must devise a method of introducing security metrics themselves to a game. To date, no one has done so. However, we believe defining the problem itself as a game possessing a system of variables and constraints on security and energy can allow for the introduction of security metrics. This type of problem, with constraints and variables, is referred to as a constraint satisfaction problem. We define constraints as functions that restrict the domain of values a variable may take to a subset that forms a codomain or range. Constraint satisfaction problems are a traditional AI approach and can represent a multivariable problem with varying domain and ranges. Constraint satisfaction problems are traditionally solved using backtracking, tree pruning, or linear programming. In our work, however, game theory will be used to solve the constraint satisfaction problem, allowing us to model optimal and suboptimal decisions along with problem constraints, and validate our work using security metrics. To further validate the security optimization by our algorithm, we will compare its results with that of the established Kerberos algorithm, which is similar to our own algorithm in that it is designed to provide security for an entire network and uses methods of encryption and access control. For a more complete description of Kerberos, we refer you to [35]. Our work can be generalized to optimize security for almost any network or system because it can be applied to a network made up of computers that possess any 7 degree of heterogeneity. With regard to the sleeper software in the article mentioned earlier, since the parties responsible for securing the power plant have not divulged the manner in which the sleeper agent programs were detected, our only conclusion can be that their method is not one they wish to divulge to protect classified security methods or the programs were discovered by accident. We believe that since the past definition of security is based on the "works as expected" definition in [31], those individuals responsible for power plant security were simply following this definition. Since even today there have been no deviations in power plant expected performance, by this old definition the power plant is secure, and authorities even attest this when they say that there is "no immediate danger" [34]. We believe this event exemplifies the need to improve and redefine security; a first step in doing so would be to ensure that definitions of security are no longer quite as qualitative, as in the "works as expected" definition, but can be measured quantitatively. Our work is the first of which we are aware that uses a weighted potential game for a network security optimization solution. We will use a noncooperative instead of a cooperative game because it better fits our problem definition: noncooperative games focus on strategy and utility maximization, whereas cooperative games do not. Noncooperative games model relationships that may be unilaterally changed by players; there are thus no binding contracts. At each turn of a game, a player chooses its best move to maximize its utility. The best possible move a player can make versus all best possible moves of all other players is defined as an equilibrium, which is also known as Nash equilibrium. This equilibrium is not necessarily the best outcome, because there could still be multiple equilibrium or even a solution that goes beyond what is achievable 8 by equilibrium using traditional noncooperative game analysis. Such improved outcomes and “best” equilibrium are defined as Pareto optimal equilibrium. Potential games are a subset of the class of noncooperative games that indeed do find these Pareto optimal solutions to game theoretic problems. Pareto optimization goes beyond the definition of equilibrium. It is, informally, the best of the equilibrium or more optimal solution than equilibrium. Pareto optimized is defined as a state in which a player can take no action deviating from this state without decreasing utility for itself or some other player. That said, the best way to illustrate the difference between Pareto optimal and equilibrium is by the example of the game known as the Prisoners’ dilemma. In the Prisoners’ dilemma, two players are accused of committing a crime. The players are separated and cannot communicate with one another. The following Table 1.1 illustrates the respective utilities for each action, with units measured in years of imprisonment: Player 1 Player 2 Stay silent Blame Stay silent 1,1 10,0 Blame 0,10 8,8 Table 1.1: Prisoners’ dilemma Clearly, the solution in equilibrium is for each player to Blame the other and accept 8 years imprisonment because of the real possibility of being blamed while staying silent, 9 thus receiving 10 years in prison. However, the Pareto optimal solution is for both to Stay silent because it gives the most utility for all players. If prisoners could cooperate and had incentive to do so, they could get better than equilibrium. Shapley is recognized as being the first to develop a technique that can lead to a Pareto optimal solution for all players and games [2], which will be discussed in greater detail in Chapter II below. Chapter II contains the literature related to our security solution. In Chapters III  VI, we present the methodology of our solution and illustrate its improvements over previous work. Chapter VII contains our prototype simulation and its results, and Chapter VIII contains our conclusions. 10 CHAPTER II REVIEW OF LITERATURE Game theory is the analysis of games. Games can range from simple games, such as chess or checkers, to more complex games used in economic or strategic planning. While some roots of game theoretic strategy can be found in the philosophical writings of Plato and Kant [33], the first real work studying games themselves did not begin until the 19th century. This initial exploration into game theory was very simple and straightforward. Working separately, Cournot and Bertrand analyzed simple games where players chose the optimal move to maximize their utility [32]. While both made only initial contributions to game theory, Cournot is more widely recognized today due to his work on games that have an economic application. Regardless, nothing went beyond initial examination due to the lack of formal mathematical specification. True game theory began in the 20th century with the work by four men: Von Neumann and Morgenstern, Nash, and Shapley. In 1944, Von Neumann and Morgenstern wrote the groundbreaking “The Theory of Games and Economic Behavior” [17], which contained the analysis techniques, general formula for calculating utility to a player, and game terminology still in use today. VonNeumann and Morganstern’s work created the tools necessary to successfully analyze games, which led to a number of future discoveries. In addition, their work ensured that future explorations of game theory to solve problems were 11 restricted to situations and problems that could be fully described by mathematics. For example, using games to model computer problems has been largely successful for the reason that the factors affecting a problem with computers can be modeled with a great degree of certainty. As we know, although computers can malfunction, they are not capable of panic. Modeling a computer problem using game theory thus has greater likelihood of reaching an optimal result. Building upon VonNeumann and Morganstern’s work, John Nash developed the noncooperative game and defined game equilibrium in the 1950s. At the same time, Shapley [21]  [22] took VonNeumann and Morganstern’s work and used it to define the field of cooperative games. Cooperative games tend to spend little effort focusing on the strategy of each player in the game; noncooperative games do the exact opposite. While noncooperative games are now more widely studied than cooperative games, with [8] devoting an entire textbook to them, Shapley is the only living member of the four founders of game theory, and he continues to publish to this day. His efforts have turned toward noncooperative games, but they contain new ideas of how to create noncooperative games that go beyond their traditional definition, giving these games cooperative characteristics. His most recent work [6] developed a game that allows coalitions to form even though variables possess intermediate values. Furthermore, Shapley has made significant improvements on the class of noncooperative games known as potential games [2]; this work is one of the foundations of our thesis. A potential game is a game possessing a function, called a potential function, which is similar to a players' utility function. The potential function takes the same input as the utility function and outputs a value; in the case of an exact potential function, the 12 output is equivalent to that of the result given by the utility function; in the case of an ordinal potential function, the output has only the same sign (positive or negative) as the result output by the utility function. When players move according to mixed strategies, games possessing a potential function can have only an exact potential function; when players move according to pure strategies, the game possesses an ordinal potential function. Let us give the definition of a potential function in its relationship with a utility function as given by Shapley [2]. Given utility function u and potential function v, move m in the game is an element in the set of moves M, denoted (2.1) where M is a member of the set of positive real numbers, denoted (2.2) When move m is input to the ordinal potential function and also to the utility function, the value calculated by the ordinal potential function is positive or zero ifandonlyif the value calculated by the utility function is positive or zero, denoted 0 0 (2.3) For the same utility function u, let us give the definition for the exact potential function according to [2]. For the exact potential function, which is also denoted v, the value calculated by the utility function u is equivalent to the value calculated by the exact potential function v for input m, denoted (2.4) 13 Before delving further into Shapley’s work with potential games, we must examine the history of the potential game and its definition. In 1973 Rosenthal [14] did the earliest work with a type of potential games called congestion games. These games built upon Cournot’s initial work on analyzing oligopolies, whereby all players are selling the same item at different prices, and no new players are introduced once the game begins. The game players were all identical, and contained a finite set of actions. The utility was dependent upon the actions of other players. A linear inverse demand function, with respect to the item being sold in the game, was used to calculate utility. All moves in Rosenthals’ work were considered to be “pure” and were not subject to a probability distribution. Prior to Shapley’s proof in 1996 [2], showing that congestion games were an isomorphism of noncooperative games, a considerable amount of work on potential games was still done using Rosenthal’s work as a foundation. Even today, much of the research still focuses on Rosenthal’s work [11], [13] to the point that it contains the flaws that Shapley has pointed out in 1996. In this respect, it is somewhat myopic; it still follows the pattern of excluding mixed strategies and does not reference Shapley’s recent work in 1996 [2], with the exception of the recent work by Komali [4]. Shapley’s work with potential games [2] is significant. It improves on Rosenthal’s work by adding proofs that give enhanced definitions of potential games and their requirements, making it easier to design a game that has equilibrium and is also Pareto optimal. Shapley’s research deals with mixed and pure strategies and heterogeneous players, which was something that Rosenthal was unable to solve. 14 Shapley was also able to develop an improved type of potential game, the weighted potential game. Defined by Shapley [2], a game that possesses a utility function which is directly related to each of the players’ utility functions is a weighted potential game. A weighted potential game possesses a potential function for either mixed or pure strategies, and has efficiency and convergence improvements over other potential games or myopic, greedy strategy games. Weighted potential games possess at least one equilibrium, and are easier to prove Pareto optimal. Furthermore, the weighted potential game is valid for both mixed or pure strategies and players with any degree of heterogeneity. Shapley’s work with potential games extends to graph theory as well, containing a proof that any game containing a network using weighted potential for utility evaluation is connected, at minimum, by a simple cycle. Shapley explains why the weighted potential game gives a result that is more likely to be optimal than other types of potential games. Because the utility function that determines the weight of benefit between two players is piecewise continuously differentiable, results can be mathematically analyzed prior to any empirical simulations by using the equation of the potential. Nonweighted potential games do not possess this property, as was also proven by Shapley in [2]. Furthermore, the weighted potential game will lead to an optimal solution regardless of the weight used. Besides these improvements, Shapley also recognized and established rules for what leads to optimal solutions for a potential game, which is something not studied by Rosenthal. Foremost is what Shapley defined as the Finite Improvement Property: all 15 potential games possess this in that there is a best possible move for each state of the game, but this alone is not enough to guarantee an optimal solution. In addition, neither the game nor the improvement can go on forever, and there can be no repeated states; the game must have a finite end with unique moves and finite utility. This particular property contradicts Rosenthal and Shapley has a mathematical proof to back it up. In addition, Shapley defined the requirements for nonweighted mixed and pure strategy potential games. As a result of his work Shapley discovered that a potential game admits a cooperative solution to noncooperative game; in theory this would allow the players in the Prisoners’ dilemma to collaborate indirectly by maximizing the potential function. To explain this further, the incorporation of a potential function gives the noncooperative players, which have no binding contract to one another by the nature of the noncooperative game, a type of motivation and nonverbal collusion which creates a unique hybrid of noncooperative and cooperative games; if all players try to jointly maximize the potential function it effectively acts as a binding contract between the players. Hence in the case of the Prisoners’ dilemma, instead of each accusing the other, both players play the move to remain silent by jointly maximizing the potential function between them. The Pareto optimal solution would thus be reached concurrently by both players because the potential function changed the conditions of the game, allowing for a more beneficial solution for both players to be reached. Our understanding of Shapley’s work in [2] is that Paretooptimality supersedes equilibrium by its definition. While it is not spelled out in English words, but in equations, much of his most groundbreaking work takes this form. We have not found 16 any other works that reference this point about Pareto optimality, although the work by [4] implies that he understands it. However, despite the lack of other sources found, based upon the fact that much of Shapley’s work is purely in the form of an equation with little written Englishlanguage explanation, and that no authors found thus far are aware of Shapley’s contributions until referenced secondhand by another author who does understand Shapley’s equations, we believe that we are correctly reading his work. Shapley goes on to say in [2] that the existence of a potential function guarantees the existence of equilibrium. However, there may be several local equilibrium in addition to the best equilibrium overall. Rosenthal had previously postulated that the way to find the best equilibrium, which yields the Pareto optimal solution, is to solve for the maximum of the function, known as the argmax. While it seems obvious, it is not game theoretic, and defeats the purpose of the game. Still, other authors [4], [11], follow Rosenthal’s bad example despite this, and even go so far to use it as a method of proof as suggested by Rosenthal. Shapley’s work in [2] sheds light on Rosenthal’s shortcomings: experimental results showed that solving for the argmax could be used to determine which equilibrium is the optimum, but formal proofs demonstrate why solving for argmax is an invalid proof or predictor of the game itself. If one considers it logically, Shapley’s reasoning becomes obvious: solving for the maximum value of an equation is insufficient to describe the complexities of a game. Instead, Shapley said, argmax should be used as a refinement tool to identify and eliminate any possible false equilibrium. As stated earlier, authors such as [4], [11] have ignored much of Shapley’s work in this area, correctly using argmax as a refinement tool but incorrectly using it as a proof of equilibrium. 17 Komali’s proof for Pareto optimality of the equilibrium is similar to [11]. The optimal point is examined; once reached, change in utility would result in a player disconnecting from the network and subsequently cause the player to no longer be optimal or in equilibrium, which is correct. Ironically, parts of the Pareto optimality proofs by [4] and [11] are both logically unsound. Our understanding of logical equivalence leads us to believe that the proofs on Paretooptimality in [4], [11] are overworked via proof by contradiction to the point that they do not prove their original goal; these Pareto optimal proofs instead prove a logical inequivalence of their original statement. We refer the reader to [4] and [11] for the proofs themselves. We select the proof in [4]. To help clarify our own argument, we reproduce their statements; a game that meets these criteria is considered Pareto optimal: If the potential function will converge to equilibrium in the game, then no player can deviate from an action in equilibrium without violating its constraints and thus decrease utility and make the action not in Pareto optimal equilibrium. Let us examine the logical statements used in their proofbycontradiction of a Pareto optimal game to explain our reasoning. Let the statement p represent the first logical statement of the proof in [4] p: the potential function will converge to equilibrium in the game. Let the statement q represent the first part of the second logical statement of the proof in [4] 18 q: no player can deviate from its equilibrium action without violating its constraints. Let the statement r represent the second part of the second logical statement of the proof in [4] r: no player can deviate from Pareto optimal equilibrium action without decreasing its utility. Let the statement s represent the third logical statement of the proof in [4]. We understand the action causing deviation from equilibrium to mean “deviates from equilibrium action,” giving s: if a player deviates from its Pareto optimal equilibrium action, then the action is not in equilibrium. Note that statements q, r, and s are negations of statements. The first part of statements q, r and s address deviating from an equilibrium action, which is the opposite of playing an equilibrium action. The second part of the statements addresses violating constraints and decreasing utility, which is the opposite of preserving constraints and maximizing utility, respectively. Let us now break up q, r, s even smaller using the following statements: t: player plays action in Pareto optimal equilibrium u: player preserves constraints of its action v: player maximizes utility 19 We can now write q, r, and s symbolically: , , The latter statement is what [4], [11] focus their proofbycontradiction upon. However, proofbycontradiction works when the hypothesis and conclusion are different, which is not what we have here in statement s. Proofbycontradiction works by assuming the hypothesis true and conclusion false, and using this to arrive at a contradiction of the negated conclusion. We understand statement s above to be vacuous as it literally reads, “if a player plays an action in equilibrium, then a player does not play an action in equilibrium.” The authors in [4], [11] did not break down statement s into its substatements. Writing the statements symbolically has exposed the overcomplexity of this proofbycontradiction approach. This work by Komali in [4] focuses optimizing communications energy consumption in a network with game theory. In combination with ordinal potential functions, Komali constructs a game with graphs and greedy strategies where all players are identical and use pure strategies only. This work builds upon a proof by Shapley stating that said graphs are connected, at minimum, by a simple cycle. Specifically, Shapley states [2] that a graph representing a game is connected if the function used to calculate utility and thereby determine the best strategies is a potential function. Komali’s resulting game is noncooperative, and achieves an equilibrium that is Pareto optimal. However, its game 20 only addresses homogeneous players and ordinal utility with pure strategies, and does not examine heterogeneous players or mixed strategies. Its equation to calculate utility using linear inverse demand is a variation on Shapley’s [2] and Rosenthal’s [14] work: each player receives diminishing utility for every other player to whom it is connected, but also receives additional constant utility for maintaining network connectivity. Our understanding of the utility equation in Komali [4] is that it differs from the work in [2] because Komali has tailored his solution to fit his greedy strategies that determine player moves in the game; the utility calculations are only part of the players’ strategy. The proof that Komali’s algorithm in [4] is in equilibrium is in his earlier work [30]: however his proof ignores Shapley’s instructions [2] and instead uses argmax as a method of proof, which is invalid according to [2]. Thus Komali’s work leaves open the possibility of a subset of solutions not in equilibrium. In our own simulations of Komali’s algorithm in [4], its utility improvement fluctuates back and forth in a sinewavelike pattern around a threshold, never completely reaching the Pareto optimal equilibrium; see Figure 2.1 below. These results indicate Komali is indeed taking argmax of the final set of utilities fluctuating around a threshold to distinguish between optimal and suboptimal equilibrium. We believe this should have been incorporated into his algorithm; as it stands, this inability to distinguish between Pareto and suboptimal equilibrium is a flaw. We conclude the flaw is most likely caused by Komali’s greedy strategy used by players, which Shapley [2] says can tend to a suboptimal solution for potential games. However, Komali’s earlier work in [30] acknowledges that the optimal utility indeed does transition around a threshold and that this is sufficient for him for convergence. Regardless, we do not agree as mentioned 21 earlier, and believe improvements could be made in his work. Our own simulation of the energy optimization algorithm in Komali [4] is shown in Figure 2.1 below. Figure 2.1: Our own simulation of the energy optimization algorithm in [4] Besides the work by Komali, other work has been done in the area of tying noncooperative games to Pareto optimality. Heikkinen [11] examines a qualityofservice bandwidth allocation scheme in a distributed homogeneous network within the framework of a purestrategy noncooperative game, and uses Pareto optimality to prove that the equilibrium reached is best overall. It also shares a common approach to [4] in that the algorithm used by the players to maximize utility is a greedy one, and was successful at achieving results for equilibrium that is also Pareto optimal for the examined cases. However, the work is applicable to homogeneous players and pure 6.00% 4.00% 2.00% 0.00% 2.00% 4.00% 6.00% 0 2 4 6 8 10 12 14 Utility Improvement Iterations Komali [4] simulation: Utility improvement 22 strategies only, as it does not build upon Shapley’s work in [2] despite its publication at a later date. In addition to his work with potential games, Shapley also determined how to combine players in a game into coalitions by using a function that became known as the Shapley value [8], [21]. The Shapley value ensures that an individual player receives, as utility, an average of the utilities that other players receive for the player's actions; it acts as a sort of "golden rule" for players, and it was discovered by Shapley [2] that it is required for a game to have a potential function. In doing so, Shapley discovered additional requirements for all games using potential functions that were not listed before Shapley’s 1996 work. The game must also have a finite end with unique moves and finite utility. These requirements were not even hinted at in Rosenthal’s work. Shapley's 2008 work on multiplayer utility [6] continues this, examining forming coalitions without negotiation when only partial player preferences are known. This work assumes that that preference can be quantified. Preferences are the current best values for the variables in the game. Since the variables in the game represent security levels, the preferences are the current optimal security levels of the connections in the graph. Partial preferences, which are sometimes called incomplete preferences, are equations in which a set of variables may have intermediate or unassigned values. In the case of a game, the variables correspond to the players or variables maximized by the players, and the partial preferences themselves refer to the intermediate states of the game prior to equilibrium. Coalition formation in [6] is done by quantitatively comparing partial and complete preferences of players and coalitions. 23 Individual preferences are used to facilitate coalition formation. These preferences are combined using the mathematical fact that equilibrium is a partial order, and any remaining unknowns are combined using a weighted sum. This technique is able to aggregate individual preferences to coalition preferences without needing to arbitrate between the players. While Shapley does not explain it in words, we understand his equations to indicate that the reason the coalition formation algorithm works so well with partial preferences is that it takes advantage of the mathematical foundations of game theory to form coalitions. Specifically, Shapley’s coalition formation algorithm uses the property that an equilibrium is a partial order on the strategies as established in the mathematics of VonNeumann and Morganstern [17]. In addition, Shapley proves in [6] that because the design of a weighted potential game means the players are already receiving utility based upon the weight used, it leads more easily to coalition formation because of the collaboration already inherent in the weighted potential game. Coalition formation involves forming what are known as coalition preferences. We understand that these coalition preferences are quantified from a Cartesian product, which defines the actions of the game as described earlier, to a real number by using a weighted sum of the individual preferences that already exist prior to coalition formation. This is not the game theoretic weight as defined earlier in the context of a potential game, but refers to the algebraic definition, whereby a number is multiplied by each of the elements in the Cartesian product, and then the elements are added together. Shapley points out that there is no formula given in past work indicating how to best determine these weights for coalition preferences, but if there is an already existing 24 schema then it will facilitate easier coalition formation. Since this weight is between two players, and the coalition examined contains the same two players, it is in and of itself an optimized coalition preference weight. Coalitions themselves are already in wide use; for example, any network containing a WindowsNT system divides users into coalitions, which are usually referred to as groups in a Windows environment. It restricts certain users in a coalition from having access to resources on the network, while other users belonging to a different coalition are granted such access. The primary advantage of using coalitions to grant permissions is its speed: it is faster than other approaches. The first approach commonly used, a zeroknowledge based system, grants permissions to individuals if they can prove secret knowledge; but by doing so they do not reveal the secret itself. A graph isomorphism is a means of implementing a zeroknowledge based system, whereby a graph representation of knowledge is shown to be identical to another graph with different vertex names. The problem with this approach is its inefficiency: proving the two graphs are an isomorphism of one another involves examining all possible combinations. The other approach commonly used for granting permissions involves secretkey encryption, but it is expensive to implement. Other work besides [4], [11] studies Pareto optimal potential games: the work by Bauso [13] examines this in a network resource sharing game. Bauso builds primarily upon Rosenthal [14] for potential games. But, like [11], he does not build upon Shapley [2], [6] despite the later publication date; this in turn causes Bauso’s results to be suboptimal. Specifically, Bauso examines purestrategy noncooperative nonrepeated (oneshot) and repeated games. Bauso correctly uses argmax to refine his answer and select the best equilibrium, but again like [4], [11] also uses it incorrectly to do an empirical 25 proof for Pareto optimality in oneshot games. This is not all: by overlooking Shapley [2], [6], Bauso’s work fails to find a Pareto optimal solution for coalitions and repeated games. Furthermore, Bauso’s coalition formation algorithm does not work. While Bauso’s game is partially correct in that it uses the Finite Improvement Property, according to Shapley [2] the Finite Improvement Property does not guarantee that a game possess a potential function. Rather, as stated above, the game must also have a finite end with unique moves and finite utility. What Bauso did with a repeated game possessing a potential function is violate its requirements according to Shapley [2]: the game is repeated and so each time it is restarted and played again, there exists at least one state that is not unique as it was played identically the last time around. Like Komali [4], Johari [1] develops interesting solutions using noncooperative games represented by a graph, but avoids potential functions altogether. Johari’s work addresses energy conservation for message passing in networks, and uses both noncooperative and cooperative games. In these games, all strategies are pure, and all nodes homogeneous, but unlike Komali uses the idea of bids between nodes to establish connections between nodes. Bidding takes place using a type of currency and occurs in sequence from one player to the next. Johari found several types of simple topologies that result when game theory is applied to graphs for the purpose of reaching some type of equilibrium. If the cost is applied only to the initiator of a connection, as characterized by noncooperative games, the star topology has the least cost to all nodes and will form. Otherwise, if cost is applied to both parties, as in the case of a cooperative game, a simple cycle or wheel forms. The simple cycle was also found by Johari to be a degenerative 26 topology: soon after the network formed by the noncooperative game degenerated from a star to a simple cycle, the network disconnected. While the above work is significant with respect to the game theoretic aspect to our security optimization solution, it does not address security. All previous game theoretic work with security deals with individual elements or components in the network. Only a few authors have examined using game theory to help solve security problems, and none of these authors have examined optimizing overall security, let alone overall security in a network. In addition, we are not aware of any previous game theoretic security optimization that validates its work using security metrics. For the little work that has been done in the area of game theory and security, the primary work has been done by Agah [26]  [27] to model a scenario where an attacker drops packets to cause communication disruption in a network. Here, game players represent nodes in the network, and players receive utility based on the number of successfully transferred packets. As a method of defense and attacker detection, each player individually examines the percentage of its own message packets not forwarded by other players. If another player fails to forward a percentage of messages beyond a threshold, then that other player is removed from its network. All other work in the area [28]  [29] follows a similar pattern. The work by Demirbas [29] is similar in that it also examines network games that optimize security for each component. However, their work focuses more on reconfiguring individual nodes to stabilize the network so that it may address the problem of defending against a direct attack against each individual player. The third significant 27 work with game theory and security is done by Sun [28], who uses game theory with security and economics at the component level. Each individual part of a network is examined, and cost/benefit analysis is done with respect to additional investment. Results showed that the cost inflicted by an attacker on each component is directly reduced by the security investment. While interesting in a broad sense, the results are generic and do not list any particular types of investment, but includes every possibility in one category. Recent work in the area of security metrics has examined the shortfall caused by generic security definitions. Security metrics are based on the idea of going beyond traditional qualitative security definitions into the area of quantitative measurement and analysis. Past definitions of security include such phrases as “works as expected” [31]. Such qualitative definitions, while traditional in security, depend upon perceptions of environment; they do not preclude the possibility of hidden vulnerabilities or sleeper agents that fail to affect the expected workings of a system until they are activated and cause destruction, illustrating that the system was never secure even though, up until that point, it did indeed work “as expected” [31]. Preventing such types of attacks is one of the purposes of quantitative security metrics. The earliest work on building a foundation for quantitative security analysis based on security metrics that received attention is by Almerhag and Woodward in 2005 [10]. The paper describes security levels related to the types of operations or rules of composition used to define them; these three levels from least important to most important are neighbor authentication, cryptography, and access control. Authentication is measured by whether or not a neighboring node computer’s identity is able to be 28 verified by a trusted third party in a network. Cryptography is expensive to implement, but prevents a transmission from being altered or decoded by an unwanted third party. Access control is cheaper to implement than cryptography, and works to directly stop individuals from gaining access to unauthorized information, such as user IDs and passwords. Payne [23] of the SANS Institute has a somewhat different definition of security metrics, stating that its core foundation lies in analysis of security data. Here, the essence of effective security analysis is risk analysis, with three core areas: asset value, threat, and vulnerability. Another technique that can be used to quantitatively analyze security is attack trees, which are sometimes called attack graphs. Attack trees are a data structure with nodes representing states of the environment; transitions exist between states. These transitions represent the conditions for moving from one state to another, much like a finite state automaton. Authors Sheyner [9] and Wang [25] have called for the need to quantitatively analyze security using attack trees, but their work lacks a means of quantitatively measuring security for the purpose of attack tree analysis; still, their work is one more step toward finding a means of tying this quantitative analysis to a practical security implementation. Existing approaches using attack trees, such as the work by [40], are representative of the implementation problems attack trees pose, as these works’ analyses degenerate into an NPcomplete problem of analyzing all connections between all nodes in a tree. In fact, much of the work in the area of attack trees, exemplified by [39], are on finding new ways to improve speedup for analyzing this NPcomplete problem. This work by [39] uses a backtracking and sorting of the relationships between nodes in the attack tree prior to any actual analysis taking place. 29 As stated earlier in Chapter I, our thesis will use constraint satisfaction problems as a means to better describe our problem and tie metrics to our game theoretic solution. The idea of constraints in games themselves goes back to the coalitions of games possessing information, capacity, participation, and incentive compatibility constraints. Information constraints are limitations imposed by a game designer on the players, whereby they have limited information about some aspect of the game, be it observing or predicting other players’ moves. As a result, information asymmetry between players results in these games and players must make decisions accordingly. A classic example of information constraints is the Prisoners’ dilemma. The second constraint type, capacity, is generally tied to games involving money or currency, possibly in a generic sense, and the limited capacity players have to spend or produce to maximize their own utility while minimizing cost. The third constraint type, participation constraints, is imposed on players to take part in the game. Last, incentive and compatibility constraints are related to one another. They are used in repeated games describing participation incentives; one example is in a game involving players that can produce products of varying quality to sell, but because other players know that lowquality products are more likely to be defective but cheaper and highquality products are less likely to be defective but more expensive, players know that they must produce highquality products to have a chance to generate a profit. As a result, discounts become the focus of the game to maximize utility. A constraint satisfaction problem is an AI technique that traditionally has nothing to do with game theory. Constraint satisfaction problems models variables’ constraints and variables in a problem, and can be generalized and solved by several different 30 methods. These methods are backtracking or other treepruning techniques. The work by Vickrey [16] was the first to examine the relationship between constraint satisfaction problems and games with complete information. Players in the game were represented by variables in the constraint satisfaction problem, and constraints were used as means of socially forcing players in the game to follow the strategy of other players in their local neighborhood. Constraints in this work were restricted to unary constraints, and it was thus limited by the inability to apply the constraints to any binary mathematical operations. The work by Soni, Singh, and Wellman [7], however, does apply to binary constraints. It builds upon the work by Vickrey, examining repeated cooperative games with complete information for messagepassing optimization, and reformulating the constraint satisfaction problem to allow binary and unary constraints. To do so, the problem in [7] was changed to take place within a graph so that constraints existed between each variable; constraints were related to equilibrium. In this, a constraint was satisfied if the player chose the best strategy to maximize its utility given the other players in the game also choose the best move. Each player, or variable, had its own unary constraint. While their work is significant because it is, as far as we are aware, the first to examine the relationship between constraint satisfaction problems and game theory, the solution is restricted to traditional constraint satisfaction problem solving techniques and can only apply to homogeneous players with pure strategies. The solution uses the authors’ own variation of a backtracking and treepruning algorithm from [16], the foundation of which is a classic AI technique. The work does incorporate game 31 theoretic means of determining tree pruning, but this is secondary to the authors’ own backtracking algorithm; potential functions and optimization are not considered. As mentioned in the introduction, we will compare our algorithm’s security optimization with a known algorithm; the one used will be Kerberos. Again, we refer the reader to [35] for a complete description. In the body of research with comparing new network security algorithms to Kerberos, there have been varying approaches to simulating Kerberos as exemplified by the more recent works of [36] – [38]. Older research in the field tends to focus on using offtheshelf software packages to simulate Kerberos as well as the authors' own algorithms, while newer researchers develop their own model to study specific aspects of Kerberos compared to their own work. In the following more widelyreferenced recent articles, each explores simulating and modifying a Kerberos system. The work by [36], which was published in 2007, apparently marks the beginning of the end of offtheshelf software use for Kerberos simulations. Here, the authors used the popular GSSAPI software package to simulate Kerberos and their own algorithm, only to discover that the accuracy and credibility of anyone’s results from the GSSAPI software had come into question by the international community while the authors (and others) were conducting experiments [36]. The authors of [36] discontinued and abandoned their experiments with GSSAPI, publishing only their formal model and algorithm with a note about the fate of GSSAPI and its discontinued use by the international community. In [37], which was published in the following year, the authors compare computation time of their cryptography model with their own representation of standard Kerberos cryptography by using a different offtheshelf software package called Crypto++. One of the most recent works is by [38], a 2009 32 journal article in which the authors abandon the offtheshelf software approach and instead focus on building a mathematical model and prototype. These authors model the Kerberos network through an equation derived from fluid mechanics to study bandwidth usage in networks; this equation follows similar methodology as the equation used to represent their own network optimization technique. 33 CHAPTER III SECURITY METRICS In this chapter we begin to propose our game theoretic approach to optimize overall security for a heterogeneous network. As far as we are aware, our thesis is the first in the area of optimizing overall network security using game theory. Security, as mentioned earlier in Chapter II, suffers from what we believe to be an insufficiently descriptive definition. While many authors have had difficulty defining what security is, we believe it is relatively easy to define what security is not. Security is not vulnerability, whereby an outsider may destroy, alter, or steal one’s possessions. Possessions are, in the case of our network, the data stored in the computers, the computers themselves, and the connections between computers in the network. We assume that maintaining control of possessions relates to access control, which is itself controlled by user IDs and passwords. Such data is sensitive and should be guarded carefully. Insensitive data is less important, but is still vulnerable to theft. There still exists the possibility in any network that an outsider may intercept or alter data transferred between computers in the network. These instances involving alteration, destruction, or theft of possessions characterize a vulnerable network. Since a vulnerable network is clearly not a secure one, we will define security in terms of what it is not, namely vulnerability. Vulnerability will thus be used as a foundation for our security definition, and network security will 34 be optimized by minimizing vulnerability. To solve the problem of optimizing security, we must first quantitatively measure security so that one can determine whether or not the security has improved. Measurement of security in the system, and not just an individual component, is essential if our proposed approach to security optimization is to be validated. To do so, we build upon existing work in the area of security metrics to come up with our own metrics for quantitative security measurement. Metrics will enable us to more fully describe the problem of security maximization and enable us to quantitatively measure security itself in a meaningful way. Using an approach that allows entities in the network to evaluate their environment without having to resort to qualitative, nebulous definitions could significantly improve evaluation of security and security itself. We propose the use of security metrics as a basis for quantifying security and validating our results. We will develop our metrics, which can enable us to take definitions of security that are typically qualitative and quantify them mathematically. Attack trees are a means of analyzing security. Attack tree analysis is not game theoretic, but is a way of describing the means by which relationships and vulnerabilities in an environment are analyzed for decisionmaking. In our problem, attack trees enable analysis to take the action that maximizes security. Since actions involve changing the value of a variable, and the context of our problem is security, we will see that actions involve changing the values of the security levels between nodes. We develop a methodology for applying metrics for measuring security. Since the metrics quantitatively measure security, these can be used as parameters to the analysis. In an attack tree, the tree root represents the computer whose vulnerability is being assessed. 35 In the tree, if another node or relationship is closer to root it has more access, which can result in greater vulnerability. It is clearly preferred to address a problem further away from the root rather than allowing it to reach levels closer to the root before addressing it. In an ideal world, each computer in the network would be able to implement the maximum possible security. However, we are attempting to optimize security for a heterogeneous network in the world of the practical; there are limitations which prevent the ideal from taking place. The heterogeneity of the computers forming the network prevents them from reaching the same maximum security and places limitations, or constraints, with regard to maximum security of the overall network. Since all devices in the network under consideration are different from one another, there are constraints with respect to available hardware and software, as well as corresponding constraints of the hardware and software itself that limit maximum achievable security. We believe that optimizing security for this type of environment fits the definition of, and at the very least lends itself to, a constraint satisfaction problem. Constraint satisfaction problems have variables, corresponding constraints on the variables, and problem state. A state of the problem represents the current values of some or all variables. Some constraint satisfaction problems have an objective function maximized by all variables; doing so leads to its solution. Thus we will describe the network as a constraint satisfaction problem so that we may better specify the problem of optimizing security within the security limitations. Since we propose the application of game theory to optimize security, we will solve our constraint satisfaction problem using a game. We propose players will use environment data, represented by variables quantified by security metrics, as input to players’ attack 36 tree analyses to determine vulnerability and thereby measure security. In doing so, players may choose the move that maximizes security. As connections change in the network during game play, metrics can be used to measure the changes in the network for attack tree analysis, choice of optimal move, and overall network security. But not all constraint satisfaction problems possess an objective function and can be directly correlated with, and thus be solved by, games. Conversely, not all games can be directly correlated with, and thus solve, the corresponding subset of constraint satisfaction problems. We must identify which constraint satisfaction problem subset can solve a subset of games that fits our problem. Hence we propose to identify the subset of constraint satisfaction problems that can be directly used with a subset of games that fit our security problem. To implement more effective security we will use coalitions. Coalition formation involves separation of nodes according to preferences, which are represented by current assignment of values to security levels of all connections. To give an example, complete preferences for coalition formation takes into account a node i and its links to neighboring nodes. Partial preferences, which are also known as incomplete preferences, take into account the links not made by node i but have been made by other coalition nodes j and k. Partial preferences also include the state of links prior to final optimization. Coalitions are usually formed only once all variables, or preferences, have had their final values assigned to them. To integrate the coalition formation process directly into our security optimization algorithm, we propose using coalition formation with partial preferences. Approaches to coalition formation relying on complete preferences would not be able to be directly integrated into the optimization process 37 itself, as they are instead formed after the optimization is complete, which can place a system in a suboptimal state. Through the above solutions, we propose our work presents a novel optimization technique that improves overall security for a heterogeneous network. 3.1 Problem definition Before examining how to quantitatively measure and optimize security, let us first define the problem, beginning with the network model and its notation. Assume the network whose security is to be optimized is represented by an a priori connected directed graph G = (V, E) (3.1) with set of vertices V and set of directed edges E. Vertex vi, an element of the set vertices, is denoted vi V = {v1, v2, … , vi , vj , vk , … , vn} (3.2) G is minimally connected with at least one edge between each of the n vertices such that there are at minimum 1 (3.3) edges, and thus the set of edges is at minimum denoted E , ,…, !" # (3.4) 38 Furthermore, let vertices represent computer nodes in the network. Let the vertex vi be represented by its index i i = vi V (3.5) and let vertex vj be represented by its index j, where $ % & (3.6) and likewise for all the other vertices in V. A directed edge forming a connection from i to j is written eij E (3.7) We define a directed edge to be synonymous with the terms edge, link, and connection. Likewise, an edge representing a connection from j to i is written eji E (3.8) Let the sequence of all k possible security levels of eij be represented by S, an ntuple containing a nondecreasing sequence of nonnegative real numbers, denoted ' , ,…, ( , 0 (3.9) Let all eij have numerical values associated with them. These are commonly called edge weights; this definition of a weight from graph theory is not to be confused with the type of game described in Chapter II called a weighted potential game. Therefore, we will define the edge weight as the security level of the connection between two nodes, and henceforth refer to it as such to avoid confusion. Thus, let 39 ) ' (3.10) denote security level of connection eij between nodes i and j. Changing a security level sij will be a valid move, or action, in our security optimization game. Hence, the moves in our game are changing the security levels of each sij. If we denote all nodes other than i as & (3.11) And, likewise, all nodes other than j as $ (3.12) where $ % & (3.13) We define the security levels of all direct connections node i makes to its neighbors forming the local network of node i as the union of the security of its connection to node j and its connections to nodes other than j, $ , denoted ) * ") (3.14) And if we assume for all direct connections i makes to its neighbors, we can define si, the security level of node i, as the weakest of all the direct connections from node i. The 40 security level of node i is defined as the minimum of the union of the security levels of all direct connections node i makes to its neighbors, written & + ) * "), (3.15) 3.2 Security metrics We shall define our metrics to measure security. These metrics will consider cryptography, data sensitivity, and access control, but exclude authentication. Authentication is excluded because, in our model, all aspects of the network are visible to all nodes. We therefore assume that any node in the network has authenticated. However, we reserve exploration of the issue of authentication and false impersonation for future work. The following metrics have binary representations. We define the binary representation of each metric as corresponding to security strength; thus if the vulnerability is high, the metric is assigned the binary number 0. 3.3 Cryptography Cryptography allows computers to send data to one another along eij in a way that any outsider or thirdparty who intercepts the data cannot read it. Encryption enables computers to implement cryptography. With weak encryption, there is a greater chance for vulnerability since it is relatively easy for a thirdparty intercepting messages sent 41 along eij to use the message to gain access to a node. An example of weak encryption, which we define as low encryption, would be a connection secured using a 32bit key. An example of strong encryption, which we define as high encryption, would be a connection secured using a 256bit key. Let all connections eij have encryption. Current encryption strength of connection eij is represented by  ) . 0, /01 2 3 &0 1, 4&54 2 3 &0 6 (3.16) Since connection eij has been defined as a directed or oneway connection from node i to node j, according to the definition of eij, yij ≠ yji. 3.4 Data sensitivity The data stored at each node can be either sensitive or insensitive. With sensitive data there is a greater possibility for vulnerability, such as if an intruder gained access to passwords, than with insensitive data. Sensitive data includes, for example, passwords and usernames. Insensitive data excludes sensitive data by definition. Insensitive data includes, for example, time of day, schedules, or other data that does not increase vulnerability if it is stolen. Let all nodes have data; all data of node j, is written 7 $ 80, & & 1, & & & 6 (3.17) 42 3.5 Access control Permissions to read and write a node’s data also affect security. Access to read and write data increases the vulnerability as it increases the possibility of an attacker stealing or modifying the data. Let write access from i to j be represented by 1 ) 7 $ (3.18) Again, the binary number relates to security strength. Consequently, if a node i has write access to data of node j, then it indicates that decreased vulnerability is false, or 0. Thus, 1 ) 7 $ . 0, 07 & 49 1 & 922 0 7 $ 1, 07 & 70 0 49 1 & 922 0 7 $ 6 (3.19) Let read access from i to j be represented by ) 7 $ (3.20) The binary number relates to security strength. Consequently, if a node i has read access to data of node j, then it indicates that decreased vulnerability is false, or 0. ) 7 $ . 0, 07 & 49 97 922 0 7 $ 1, 07 & 70 0 49 97 922 0 7 $ 6 (3.21) With our metrics we can define sij using security metrics )  ) : )+7 $ , : 1 )+7 $ , ' (3.22) 43 We will use algebra for translating a Cartesian product to a real number by applying an algebraic weighted sum to achieve a clearer security level conceptualization, translating a binary Cartesian product to a security value ranging from 0 to 10. In this context, the term “weight” will always be used with the word “sum” since it refers to the algebraic weighted sum and not the game theoretic definition of weight. For node i having connection to j we translate the security definition of sij, which is a Cartesian product, to a real number according to the formula ) ;< ·  ) > ;? · )+7 $ , > ;@ · 1 )+7 $ , (3.23) 3.6 Security metrics example To give an example of translating encryption, read, and write metrics to a real number according to equation (3.23), let us assign nonnegative real numbers to the coefficients of each of the metrics in the weighted sum to give a range of integer security values from 0 through 10, such that ' 0, 1, 2,…, 10 (3.24) Also, to aid in clarifying our example, we will separate the metric of data sensitivity from the read and write metrics. Thus we redefine sij as ) ;< ·  > ;? · > ;@ · 1 > ;B · 7 $ (3.25) We denote the set of all security levels of all h direct links from node i to all other nodes –i, forming the local neighborhood of i, as 44 C ) D) E) (3.26) Thus, for example, if node i has direct connections to nodes $, F, 9, G, 2, then H ) D )E) ), (, I, J, K# Next we determine the values of each weight so security ranges from 0…10, chosen for convenience, according to equation (3.24). We assume that data sensitivity is foremost in determining vulnerability. Since theft of data is of little consequence when it is insensitive and of great consequence when it is sensitive, we weigh data sensitivity the most heavily. Hence we shall assign the numerical value of 5 (out of 10) to ;B. Next, we consider data tampering to be the second greatest vulnerability. Data tampering can cause lost passwords or system failure if data is sensitive, and is accomplished by writing. Access control can be used to prevent an outsider from tampering with data. Encryption can also be used to prevent an outsider from tampering with data. We shall thus assign the same numerical value to the encryption and write metrics, 2 to ;< and ;@. Restricting read access can prevent an outsider from viewing data, which we consider to be less of a possible vulnerability than any of the other metrics, and we shall thus assign the numerical value of 1 to ;?. While encryption can also prevent an outsider from reading data, we consider its ability to prevent data tampering to be more important, and so it outweighs any security consideration for an outsider reading data. Thus, the weights add up to 10, the maximum security level that we assumed: 45 ;< > ;? > ;@ > ;B 2 > 1 > 2 > 5 10 (3.27) And in combination with the binary representation of our metrics, security levels will range from 0 to 10. We can now draw up a table, Table 3.1, which contains the Cartesian product of security metrics converted to real values using our algebraic weighted sum in equation (3.27), to represent the weighted sum and metrics to derive the security values of sij. Note in Table 3.1, if encryption is high and read and write access is restricted, the data sensitivity is irrelevant; hence the same security value for cases 14 and 15. The same can be said of the data for cases 6 and 7, as again, read and write access is denied. We denote these “don’t care” statuses using an X in the respective table cell. 46 Encryption (high) Read (restricted) Write (restricted) Data (insensitive) Security s Weights Case 2 1 2 5 15. 1 1 1 X 10 14. 1 1 1 X 10 13. 1 1 0 1 8 12. 1 1 0 0 3 11. 1 0 1 1 9 10. 1 0 1 0 4 9. 1 0 0 1 7 8. 1 0 0 0 2 7. 0 1 1 X 8 6. 0 1 1 X 8 5. 0 1 0 1 6 4. 0 1 0 0 1 3. 0 0 1 1 7 2. 0 0 1 0 2 1. 0 0 0 1 5 0. 0 0 0 0 0 Table 3.1: Cartesian product of security metrics converted to real values 47 CHAPTER IV CONSTRAINT SATISFACTION To describe our model in further detail, we will specify its constraints and explain how we can use it to improve representation of the requirements of our optimization problem. We will show how our problem can be modeled as a constraint satisfaction problem, which will act as an intermediate step in designing our game. 4.1 Constraint satisfaction problems Constraints represent the limitations of security for each computer in our network, and consequently, constraints are related to the overall network security limitations. A constraint is a function that maps the domain of possible security values S to the range of allowed security values for a computer. It thus restricts the domain of security values S to a subset of S that is achievable by the node given its hardware and software. There may be a great deal of difference in the processing power and other physical computational limits of the computers forming our heterogeneous network we are optimizing in our problem. These hardware and software limitations lead to actual security limits that each computer in the network can achieve. A constraint function is 48 thus itself a function of the hardware and software of a computer. Each kind of software provides a range of security levels, and each kind of hardware provides another range of security levels. The actual range of security values achievable by a computer is somewhat complicated, as it is related to whether the hardware and software independently provide security, or are dependent upon one another. If we consider the domain of security values as the Cartesian product of the set of all computer hardware and software, trying to enumerate all the possibilities would be difficult. The security function depends upon the relationship between hardware and software. In some situations where hardware and software are dependent upon one another for security, if one element is defeated, the other may be worthless. For example, if a security feature of the hardware is defeated, the software could be worthless for providing security. For an example of a problem (outside the scope of this work) such as laptop theft, in this case if a laptop is stolen and hard drive erased, then any software encryption of data on the hard drive is worthless. In other cases, the hardware and software may make each other stronger, such as a physical lock on an office door combined with a password on the computer in the office. Here, an attacker would have to spend time getting past the lock before spending time getting past the password on the computer. Because of the difficulty in deriving a function for all possible combinations of hardware and software, we will characterize the properties the function will have to develop a heuristic that is a reasonable model for our problem. For our problem, we can consider our definition of security as described above using metrics as first being softwarerelated, since encryption and access control to data are related to software. However, we may safely reason that a handheld device such as a 49 cell phone is capable of a lower and smaller range of security than a server due to the hardware and the software differences. Hence, we believe that for most cases related to our problem of optimizing a heterogeneous network, the hardware and software are dependent upon one another. Granted, it is possible that in certain cases our model fails to make sense; we are assuming that computers in our network will have security constraints whereby hardware and software are dependent upon one another, and that all computers being optimized can be characterized by our definitions of security and constraints. If we first characterize unary constraints, which form an essential part of a constraint satisfaction problem, we consider that this relates to the security of one computer’s hardware and software. Unary constraints pertain to the limitations on maximum achievable security of one computer, or rather one node in the network. If we say that a function f1 takes as input the hardware of a node i, 49 719 , and produces a range of security values that is a subset of S, and a second function f2 takes the software of a node i, 0M 19 , and produces another range of security values that is a subset of S, and we assume that these two subsets of f1 and f2 overlap with values in common between them; and if we have software that worsens overall security if the software is weaker, and hardware that worsens overall security if the hardware is weaker, then we can say that the unary constraint function N!IOP 49 719 , 0M 19 is at least as good as the weakest of the hardware and software for node i, N!IOP 49 719 , 0M 19 & M 49 719 , M 0M 19 50 What the security is less than or equal to is another matter. If the quality of the software and hardware are good, giving high security, then we will say that this is a bestcase scenario and consequently represents the maximum security. Here, we assume that we can characterize the maximum security all the possible nodes in our network with this equation, whereby the security is less than or equal to N!IOP 49 719 , 0M 19 Q 9R M 49 719 , M 0M 19 Putting these together to characterize unary constraints, we have the inequality & +M 49 719 , M 0M 19 , Q N!IOP 49 719 , 0M 19 Q 9R M 49 719 , M 0M 19 (4.1) There are exceptions to this model, however, because it is possible that combined hardware and software can work together to give a maximum security value that is greater than the maximum of either the hardware or software. For example, if we have a computer that uses protected memory on a CPU to prevent processes from accessing unauthorized data in combination with encryption on the data, this computer would achieve a security level beyond the maximum of encryption and protected memory, since even if a process was able to view data it was not supposed to, it would then have to get past the encryption on the data. This type of system would represent a significantly reduced vulnerability. However, we are assuming that the computers optimized stay within our model of unary constraints on security in equation (4.1). 51 For ease of notation and to more clearly see the node to which the unary constraint function is being applied, let us denote an abbreviation for constraints in equation (4.1) for each node i as N!IOP M 49 719 , M 0M 19 (4.2) Binary constraints are the other type of constraints in a constraint satisfaction problem, and pertain to the security value of an edge between two nodes. Here, we are dealing with constraints on a network, albeit a small network that is between two nodes. Interactions are complicated, and thus the safest assumption is to base the range of values on the weakest node forming the link. Here, the binary constraints range from the minimum of the weakest node to the maximum of the weakest node. For a connection eij from node i to node j at security sij, & S & +M 49 719 , M 0M 19 , , & TM +49 719 ),, M + 0M 19 ),U V Q J !IOP+49 719 , 0M 19 , 49 719 ), 0M 19 ), Q 9R S & +M 49 719 , M 0M 19 , , & TM +49 719 ),, M + 0M 19 ),U V (4.3) We shall denote an abbreviation for binary constraints of connection eij in equation (4.3) as )+ ), J !IOP+49 719 , 0M 19 , 49 719 ), 0M 19 ), (4.4) 52 Note that if the set of constraints of node i and the set of constraints of node j have something in common between them, a link can be formed between the two nodes. Mathematically, this is written as the intersection of the set of constraints of node i and the set of constraints of node j, denoted W )+ ), % X (4.5) then a link eij at sij can be formed between nodes i and j. Because security levels have to be determined within their constraints, we denote security given its constraints as an ordered pair + , , (4.6) and T ), )+ ),U (4.7) 4.2 Costs We define cost as a way of measuring lost security. We define pay, or payment, as compensation measured in utility to or from another node. Both payment and cost are denominated in units of security. To give an example, payment from one node i to another node j for creating link eij would come in the form of security gained by j through i allocating some of its CPU time to j. Because granting CPU time to node j restricts the available resources of node i, it decreases available resources for i to implement security, but increases the available resources of j to implement security. The cost to i for making 53 the payment would be lost security. For the connection, node i receives utility for the link since it is connected to the rest of the network, but node j will incur cost in the future from retransmitting messages sent by node i. Therefore, future cost to j is offset by payment from i for establishing the link. In doing so, our game fits the definition of a noncooperative game. Cost c of payment from i to j for forming eij shall be denoted as cost of eij, written 2+ ) , (4.8) The cost c of payment from node i to node j to form eij is determined by a varying price scheme, which is accomplished by bidding. The bidding process is tied to strength of need to establish a link measured by the effect it has on security. If a node benefits more by establishing the link, it would be willing to pay more than if little benefit was received. Bidding schemes include iterative or linear movement from the minimum to maximum amount a node is willing to pay. This scheme allows the player to move only some fixed amount each time it raises or lowers a bid; in other words, if a bid starts at 1, its next bid is at 2, then 3, etc… Another type of bidding scheme implements an exponential movement from minimum to maximum amount a node is willing to pay. This bidding scheme follows the pattern of an exponential function, whereby bidding increments are slow initially and increase exponentially as each bid is made. Finally, there exists the possibility of nodes implementing a scheme whereby bids follow a logarithmic movement from minimum to maximum amount willing to pay. 54 4.3 Side payments The calculation to decide the move that gives the most utility may indicate that it is not beneficial for that node to raise its security beyond some level. In addition to payment from node i to node j to form a link eij, we define a second type of payment called a side payment. Side payments are used to induce a node to move beyond its selfish motivations to benefit another node. A side payment is defined as an action that consists of payment made from node i to node j to induce j to change the security, sjk, of its link ejk to node k. If analysis shows that a node i gains the most utility by another node j altering a link to node k, where i is not connected to k, node i can take action to maximize its utility by paying node j to alter its link to node k. Adding side payments to the set of possible moves has the possibility of raising the security level of i as well as other nodes connected to j beyond what would be possible without a system of side payments, swaying the utility calculation of an individual node in favor of distributed security over local security, therefore benefiting the network as a whole. We denote a side payment action from node i to another node j to induce action T )(, )(+ )(,U that changes security of j’s connection to node k as 2 ) T )(, )(+ )(,U (4.9) Since a side payment is an action node i takes that changes a link, which in this case is altering link sjk, it is considered to be a move for node i. As such, it must take place within the constraints of i, . Since cost for the action is applied to i since i 55 must pay j to take action altering link sjk, cost c is additionally notated for clarity to indicate that cost is applied to i as it must pay j to take the action. We assume that j cannot refuse an action once it agrees to take the action. By having nodes pay other nodes to make changes in security that do not affect the other nodes directly but can cause them to become more vulnerable, a type of cooperation takes place. Side payments act as a facilitator of a form of cooperation, regardless of coalition membership, to increase overall security. The end result of this payment is that overall security of the nodes along the attack tree from payee to payer is increased. Without side payments between nodes, there may be areas in the graph or particular nodes for which this solution is suboptimal. This suboptimality can be brought on by individual nodes’ strategies or security limits due to the computers’ constraints. However, we believe side payments help in avoiding these suboptimal scenarios in a network. Besides helping form links, payments between players denominated in the same unit of measure as utility aid in applying attack tree analysis to improve security via side payment. For the above scenario for nodes i, j, and k, if a node i wishes to implement a change between nodes j and k, it corresponds to making a change further down the attack tree. This is cheaper than implementing changes higher up in the tree; changes further down (node k) correspond to earlier changes versus later changes when the problem is imminent (node j) and vulnerability is greater. As a result, not only would it be cheaper to make earlier changes or fixes in the tree, more nodes (such as other nodes connected to node j) can benefit from these changes. Such a payment should only make sense in the context of utility: node i that received benefit should ensure the node j that made the 56 change also benefit, especially when one considers that the node j making the change may not directly benefit from the change. Carrying out attack tree analyzed security changes through side payments enables the cooperation among the nodes. Algorithm 5.2 addresses how nodes perform attack tree analysis. 4.4 Objective function The objective function is a function maximized in a constraint satisfaction problem. Since we have not yet specified all aspects of our approach, describing the objective function beyond any general notation would be premature at this point. We thus say that the objective function, u, is used by all nodes to maximize security given its constraints. 4.5 Constraint satisfaction problems and game subset solvability The use of constraint satisfaction has aided in specifying our solution in more detail, but we must identify a subset of games that work with a constraint satisfaction problem subset for mathematical proof of optimization. This is achieved, explained in detail below, through a noncooperative potential game and constraint satisfaction problem possessing an objective function. Our reasoning is explained in Proof 4.1 below. 57 Theorem 4.1: A potential game that maximizes security can be used to solve a constraint satisfaction problem to maximize security ifandonly if the constraint satisfaction problem has an objective function that maximizes security. Proof 4.1 Proof of Theorem 4.1 Proving this Theorem 4.1 by contradiction is inappropriate as it creates a logical inequivalence that is difficult to resolve due to the use of negation with ifandonlyif. Thus, we will use a direct proof. We will represent the statement in Theorem 4.1 symbolically. p: game with potential function q: constraint satisfaction problem with an objective function Since a constraint satisfaction problem with an objective function by definition maximizes the function per its input, let us define input as security value according to equation (3.9) as ' And also define the objective function of the constraint satisfaction problem as maximization of s given constraint 9R+ , , 58 Statement q is thus written symbolically : 9R , Each player has its own variable that it maximizes, which we shall also call s because we are examining optimizing the same security domain as the constraint satisfaction problem. The domains of p and q are the same. Since a potential function by definition represents a function to be maximized by all parties, it is written 9R But if we consider that there is a corresponding function that restricts s to an allowed set of values that map the domain to a range of allowed values Then we are using the maximization function 9R , which is the potential function. Since 9R+ , , 9R+ , , the objective and potential functions are equivalent and we can write statement p as 3: 9R , Next we need to prove Z3 , Z 3 59 Since we are not trying to prove that all potential games solve all constraint satisfaction problems with objective functions, but that a constraint satisfaction problem with an objective function is solvable by a game with a potential function addressing the same problem, we thus have Z3 , Z 3 Where p: game with a potential function q: constraint satisfaction problem with an objective function With the above, we have 3: 9R , which, as before, is a potential function. We also have a constraint satisfaction problem with objective function, which as stated above is written : 9R , For the case of an exact potential function, the potential function is equivalent to the utility function u, , 9R , Then we do not need to break p into substatements describing , and 9R , since they are equivalent. We can now write symbolically what we are trying to prove as 60 Z3 , Z 3 [ 9R , 9R , which gives, using a truth table to examine logical equivalence for the exact potential function written above p q p ↔q 3. T T T 2. T F F 1. F T F 0. F F T All but case 3 above are vacuous to some degree or are false. We must now prove true for an ordinal potential function and objective function. We have p: game with a potential function q: constraint satisfaction problem with an objective function where 3: 9R , and constraint satisfaction problem with objective function 61 : 9R , Unlike exact potential, an ordinal potential function by definition does not have equality with utility. Instead, the potential function is greater than or equal to zero ifandonlyif the utility function is greater than or equal to zero, meaning p is actually written as 3: 9R , 0 , 0 Unlike the proof for exact potential, where , 9R , , we must break statement p into substatements. Since the substatements are not equal but are the same sign (positive or negative) ifandonlyif the other is the same sign, we must first construct a truth table to prove this before moving on to the larger proof for an ordinal potential function and objective function. Let us represent statement p as the substatements : , 0 : 9R , 0 Then p can be written as Z , Z From the definition of p, q, r, and s, we can write what we are trying to prove as Z , Z , Z which gives, using a truth table to examine logical equivalence 62 q r t (r ↔t) (r ↔t) ↔q 7. T T T T T 6. T T F F F 5. T F T F F 4. T F F T T 3. F T T T F 2. F T F F T 1. F F T F T 0. F F F T F We thus have four cases in the truth table where the result is true. Since cases 1, 2, and 4 are vacuous, but case 7 is valid when all exist, we drop the vacuous cases since they are not applicable. Case 7, however, is true and also valid for our problem definition. Thus because we proved true for the ordinal and exact potential functions, we can conclude that only potential games can be used to solve a constraint satisfaction problem ifandonly if the constraint satisfaction problem has an objective function. Q.E.D. 63 4.6 Utility Because utility is measured in security, choice of the action that gives maximum utility is the choice that maximizes security. To maximize security, node i must analyze the security of existing connections to itself as well as those to its neighbors to which it is directly connected, in order to determine whether connections should be modified. In addition, a node also estimates whether making a new connection or making a side payment to alter a connection would be the best decision to maximize security. We have already denoted the security levels of all existing connections. With their constraints this is denoted T ), )+ ),U * T "), ")+ "),U (4.10) The security levels of nonexisting connections from i, with their constraints, shall be denoted + " ), " )+ " ), , (4.11) The utility function is a mathematical function used by all players to make an optimal decision at each point in a game. The utility function allows a player to choose the best values that can be assigned to the game variables and maximize its reward, or utility, at each turn in the game. Utility in our game is measured in security. Since the purpose of our work is optimizing security, and any game theoretic solution optimizes utility, utility is measured in terms of security. As game variables are represented by all sij, then the utility function allows a player to choose the action that gives maximum security. Since 64 actions involve changing security levels of connections, for connection eij the utility function u is defined as T ), )+ ),U T ), )+ ),U 2+ ) , (4.12) 4.7 Equilibrium in a game The optimal action for node i given its constraints is to choose the security level that maximizes equations (4.10) – (4.12), denoted , 9R \T ), )+ ),U * T "), ")+ "),U * + " ), " )+ " ), ,] (4.13) The rationale for decisionmaking to maximize security is made according to Algorithm 5.2, which uses attack tree analysis. The utility received for this optimal action is denoted , (4.14) An action profile is a sequence containing each player’s move at that particular turn in the game. In some gametheoretic literature an action profile is referred to as a tuple or vector; this type of vector is not one with magnitude or direction, but instead refers to a row or column in a matrix. Hence we refer to this sequence of actions as simply an action profile in order to avoid confusion. This is not to be confused with a strategy, which is an action plan. An action profile is in equilibrium if it contains the 65 best, or optimal, move for each player versus all other best actions of the other players. An action profile in equilibrium, denoted s*, is written + , , , ,…, ! , ! ! , (4.15) In this equation, for example, , refers to the equilibrium action of player 1 given its constraints, and , refers to the equilibrium action of player 2 given that player’s constraints. Recall that actions involve changing security levels of links to other nodes. For example, if we assume best action for player i is forming a connection to player j at security level sij, then in this case , refers to T ), )+ ),U which involves bidding to establish or change the security sij of eij. To give another example, it is also possible that since a side payment is an action which does not involve bidding but alters a connection, it can be an optimal action si* for node i. In this case, if node i is directly connected to node j but not directly connected to node k, if the side payment to j to have j change sjk is calculated to be the optimal action , , then in this case , refers to 2 ) T )(, )(+ )(,U The definition of equilibrium for player i means that its utility, or security, is maximized. No player has any incentive to change its action given no other player 66 changes its action. An action that is not in equilibrium is a suboptimal action. A suboptimal action is defined, given its constraints, for player i as , (4.16) where the suboptimal action is never the equilibrium action, denoted , % , (4.17) The following equation describes the best action, or equilibrium, of player i; security of i is maximized if it takes the best action when all other players take their best action, thereby maximizing the utility function u, denoted + , , " , " " , + , , " , " " , (4.18) 67 CHAPTER V GAME THEORETIC ANALYSIS The best action a node can take is determined by attack tree analysis. However, before examining attack tree analysis to determine the best action, we need to address the reasoning behind the decisionmaking for granting other nodes access to data, which forms an essential component of attack tree analysis. Read and write access form two of the three security metrics. We have not specified whether or not access is granted on a casebycase basis, and if it is, we need to address the reasons behind granting access. Addressing this raises the need for a refined security definition and analysis algorithm, which will be made possible through coalitions. 5.1 Coalition formation for a weighted potential game Coalitions have the advantage of allowing aggregated or broad security levels and access control, which will be made possible in combination with security metrics and attack tree analysis. Without coalitions there is a less efficient method of analysis than is available with them. Without coalitions, the reasoning for nodes granting access to its own data is made on a casebycase basis. To form coalitions, the network is divided into nonoverlapping subsets according to a pairwise disjoint function known as a partition. 68 Coalition formation involves using the partition to combine preferences from individual nodes into a common coalition with one set of common constraints and preferences. First, we must define what we mean by preferences. Preferences are defined as the current best values for the variables in the game, which in other words is the current optimal security levels sij of the connections in the graph. They correspond to the environment and its current state. In our model these are the current values assigned to each variable within its constraints. Coalition formation can take place during the game, when preferences are being formed prior to stabilization. Otherwise, waiting for stabilization of preferences, which corresponds to final value assignment to all variables in the game once optimization is complete, could have the effect of placing the game into a nonequilibrium or nonPareto optimal state. Integrating the coalition formation process into our optimization algorithm without disturbing the optimization requires that coalitions be formed despite partial or incomplete preferences. Partial preferences in our algorithm are handled by the evaluation criteria for coalition formation, as well as the definition security si for each node i. Instead of treating a node as just a sum of its links to other nodes, security si of each node i is evaluated to determine coalition membership. Although nodes of different coalitions can communicate, each node can belong to only one coalition. Our definition of security si and its constraints includes criteria that indirectly takes into account security levels and constraints of other nodes connected to i, in which the nodes have shared preferences and privileges. Since si is defined as the minimum of all direct connections from node i to its neighbors, and each connection sij takes place within its constraints 69 which include constraints of both i and j, our definition of si is related to the constraints of the other node j. In combination with the definition of link formation, whereby both nodes in a link receive benefit, the definition of si will cause our game to be a weighted potential game. Because si takes into account the preferences of node i and all other nodes –i to which it is connected, the utility of node i is directly related to the utility of these other nodes. In addition, the partition that evaluates si for coalition membership must consider the preferences, in our case partial preferences, of both i and the other nodes to which i is connected in the coalition. Despite the partitioning of nodes into nonoverlapping subsets, the graph G of our network is connected because graphs of weighted potential games are, by definition, connected. Although each node can belong to only one coalition, in which the nodes have more access privileges to each other, nodes of different coalitions can still communicate. Coalitions can be used with constraints and metrics to form a type of access control list, which makes coalitions an essential part of security metrics. Once coalitions are formed, there is a common set of constraints for members of the coalition. For example, members of the coalition might have read access to all other members, or write access. Coalition membership can be revoked if a node i changes si to violate coalition constraints σA which are a range of security levels for each member to belong to the coalition. The node is then removed from the coalition and all rights as a coalition member are revoked. The node can choose to change si or try to join another coalition. 70 Algorithm 5.1: Coalition formation Algorithm 5.1 divides nodes into coalitions according to security. To form coalitions, the network is divided into nonoverlapping subsets according to a pairwise disjoint function known as a partition. Each subset has a minimum security level which is a function of the partition. To do so, it applies the partition A to each node’s security level si and sij to place each node into a subset, or coalition, and thus determine coalition membership. The partition A is a threshold function, which we assume has to be calculated, that gives the maximum security difference between nodes in G that can be members of the same coalition. The partition gives coalition constraints σA which are a range of security levels for each member to belong to the coalition. The partition ensures that any messages sent through the coalition are at that coalition’s minimum level of security. Note that according to the definitions of security, link formation, utility, and potential, membership in a coalition according to the partition does not prevent a node from connecting to another node outside its coalition, as the determination as to whether to connect to another node is done according to these equations. Define A as a pairwise disjoint function, or partition, dividing G into nonoverlapping subsets; these subsets are coalitions on A = {{a1}, {a2}, …, {aκ},… , {aη}}. Note that according to the definition of a partition that *A = G, and each coalition {aκ} may contain more than one node, e.g. {aκ} ≥ 1. The number of coalitions formed is dependent on the partition chosen for A. 71 Algorithm 5.1: Coalition formation: Input: G = (V, E), partition A, difference_threshold, security tolerance for coalition membership Output: set of coalitions AQ for each node i V Coalition_formation(G, A, difference_threshold) 1. for each node i V 2. { 3. for each node j = i V 4. { 5. if ( eij ) 6. { 7. Q = A(sij ) 8. if ( Q ≤ difference_threshold ) 9. { 10. Add i to same coalition as j: 11. AQ = {{i, j}} 12. } 13. else 14. { 15. Add i to different coalition from j: 16. AQ = {{i}, {j}} 17. } 18. } 19. if ( ! eij  si < sij ) 20. { 21. Q = A(si ) 22. if ( Q ≤ difference_threshold ) 23. Add i to same coalition as j: AQ ={{i, j}} 24. else 25. Add i to different coalition from j: AQ = {{i}, {j}} 26. } 27. } 28. } 29. return (AQ) 72 The advantage of our coalition formation algorithm is, by introducing coalitions, security of connections can be better described. We use a table, shown below in Table 5.1, as an example to show the effect of coalitions on security. Contrast this table with Tables 5.2 and 5.3, which reflects changes made to the security when coalitions are removed; note the less descriptive security characterized by the data in the Table 5.3. Level Security for connection Read self data Write self data Low 1 Minimum All All 2 Maximum All All 3 Minimum All None 4 Maximum All None 5 Minimum Coalition Coalition 6 Maximum Coalition Coalition 7 Minimum Coalition None 8 Maximum Coalition None 9 Minimum None None High 10 Maximum None None Table 5.1: Security levels with coalitions In the absence of coalitions, security levels are less precise: coalitions are an essential part of fulfilling the requirements for a secure network per the security metrics. Changes to security when coalitions are removed are shown in Table 5.2. 73 Level Security for connection Read self data Write self data Low 1 Minimum All All 2 Maximum All All 3 Minimum All None 4 Maximum All None 5 Minimum Coalition Coalition 6 Maximum Coalition Coalition 7 Minimum Coalition None 8 Maximum Coalition None 9 Minimum None None High 10 Maximum None None Table 5.2: Security levels and changes brought about by removing coalitions Comparing Tables 5.1, 5.2, and 5.3, we see the changes that occur to the security definition if coalitions are removed. The example presented by Table 5.3 below reflects this, as quantization of security is less precise, and shows the final result of changes from Table 5.1 to Table 5.2. Level Security for connection Read self data Write self data Low 1 Minimum All All 2 Maximum All All 3 Minimum All None 4 Maximum All None 5 (was 9) Minimum None None High 6 (was 10) Maximum None None
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  Using Noncooperative Potential Games to Improve Network Security 
Date  20100701 
Author  Harrington, Patrick D. 
Keywords  game theory, network security, potential games, security metrics 
Department  Computer Science 
Document Type  
Full Text Type  Open Access 
Abstract  Our work puts forth a game theoretic global security mechanism to optimize security in a large heterogeneous network consisting of autonomous devices. Our work is applicable to a network that includes various computing devices such as PCs, cell phones, sensors, and control systems. Constraint satisfaction is used to fulfill the requirements of the differing computers in the network. Security metrics are used to quantify network security in a meaningful way. Attack tree analysis of the quantified security measurements is performed for decisionmaking to maximize security by altering links that form the network. Coalitions of the computers forming the network are used to improve efficiency, as well as give a broader and greater overall security than would be possible in their absence. Side payments are used to induce a computer to move beyond its selfish motivations to benefit another computer. In keeping with noncooperative game rules, costs to form links are imposed only on the initiator of the link. Our solution is presented as a noncooperative weighted potential game using pure or mixed strategies. Findings showed that our game theory model of optimization improved overall security for heterogeneous networks, and demonstrated the viability of quantitative security analysis using metrics. Our game theory model of side payments and coalitions increased security by 10% in our experiments. Side payments more than doubled convergence time to optimal network security; however, side payments that were twice as effective in terms of security improvement reduced convergence time by 50%. Our game theory model of mixed strategies showed longer convergence time but overall improved security versus our pure strategy model. Findings also demonstrated that our game theory model of optimization improved security for networks of varying size. Through these solutions, our work presents a novel optimization technique that improves overall security for a heterogeneous network. 
Note  Dissertation 
Rights  © Oklahoma Agricultural and Mechanical Board of Regents 
Transcript  USING NONCOOPERATIVE POTENTIAL GAMES TO IMPROVE NETWORK SECURITY By PATRICK D. HARRINGTON Bachelor of Arts, English Oklahoma Baptist University Shawnee, OK 1996 Bachelor of Science, Computer Science Northeastern State University Tahlequah, OK 1999 Masters of Science, Computer Science University of Tulsa Tulsa, OK 2002 Submitted to the Faculty of the Graduate College of the Oklahoma State University in partial fulfillment of the requirements for the Degree of DOCTOR OF PHILOSOPHY July, 2010 ii USING NONCOOPERATIVE POTENTIAL GAMES TO IMPROVE NETWORK SECURITY Dissertation Approved: Dr. Johnson Thomas Dissertation Adviser Dr. George Hedrick Dr. Nohpill Park Dr. Marilyn Kletke Dr. Mark E. Payton Dean of the Graduate College iv ACKNOWLEDGMENTS I would like to first and foremost thank my wife, Rayna, for her unfailing support during my graduate career. I would also like to thank my advisor, Dr. Johnson Thomas, for his guidance, wisdom, and perspective for my work, as well as Drs. Hedrick, Kletke, Park, and Chandler for their help. I would also like to express thanks to the Department of Mathematics & Computer Science at Northeastern State University in Tahlequah, and in particular my department chair, Dr. Darryl Linde, for arranging my work schedule to facilitate making progress toward a PhD. This would also not have been possible without the support of the faculty, in particular Dr. Rick Matzen, Bill King, Gordon Shamblin, and Dr. Rad Alrifai. I would also like to especially acknowledge Bill, Gordon, and Rick for their lending of books and advice on mathematics. I would also like to thank my parents, Drs. Doug Harrington and Elisabeth WentzHarrington, for encouraging me to pursue a career in computer science and in teaching; and my late mother, Martha Harrington, who inspired me to live life fully. v TABLE OF CONTENTS Chapter Page I. INTRODUCTION ......................................................................................................1 II. REVIEW OF LITERATURE..................................................................................10 III. SECURITY METRICS ..........................................................................................33 3.1: Problem definition ..........................................................................................37 3.2: Security metrics ..............................................................................................40 3.3: Cryptography ..................................................................................................40 3.4: Data sensitivity ...............................................................................................41 3.5: Access control .................................................................................................42 3.6: Security metrics example ................................................................................43 IV. CONSTRAINT SATISFACTION.........................................................................47 4.1: Constraint satisfaction problems .....................................................................47 4.2: Costs................................................................................................................52 4.3: Side payments .................................................................................................54 4.4: Objective function...........................................................................................56 4.5: Constraint satisfaction problems and game subset solvability .......................56 4.6: Utility ..............................................................................................................63 4.7: Equilibrium in a game.....................................................................................64 V. GAME THEORETIC ANALYSIS .........................................................................67 5.1: Coalition formation for a weighted potential game ........................................67 5.2: Attack tree analysis to improve security .........................................................74 5.3: Pareto optimization .........................................................................................84 5.4: Game to optimize network security ................................................................90 5.5: Pure strategy game ..........................................................................................90 5.6: Mixed strategy game .......................................................................................92 5.7: Gamebased architecture .................................................................................94 VI. VALIDATION ....................................................................................................101 6.1: Comparing our algorithm to an established algorithm .................................101 6.2: O(n) analysis .................................................................................................112 vi Chapter Page VII. FINDINGS .........................................................................................................117 7.1: Prototype One ...............................................................................................121 7.2: Prototype Two...............................................................................................145 7.3: Prototype Three.............................................................................................156 7.3.1: Prototype Three Version Two..............................................................169 7.4: Prototype Four ..............................................................................................185 7.4.1: Prototype Four Version Two ...............................................................195 7.5: Kerberos comparison ....................................................................................197 7.6: Varying network size: a comparison ............................................................210 7.7: Detailed summary of results .........................................................................225 VIII. CONCLUSION .................................................................................................231 8.1: Future work ...................................................................................................235 REFERENCES ..........................................................................................................237 vii LIST OF TABLES Table Page 1.1: Prisoners’ dilemma ..............................................................................................8 3.1: Cartesian product of security metrics converted to real values .........................46 5.1: Security levels with coalitions ...........................................................................72 5.2: Security levels and changes brought about by removing coalitions ..................73 5.3: Noncoalition security levels .............................................................................73 7.1: Overview of all prototypes’ similarities and differences .................................119 7.2: Average security comparison, Prototype one ..................................................142 7.3: Average utility improvement comparison, Prototype one ...............................145 7.4: Table of Prototypes and General Results .........................................................224 viii LIST OF FIGURES Figure Page 2.1: Komali [4] simulation: Utility improvement ...................................................21 5.1: Attack tree analysis and vulnerability reduction example diagram .................76 5.2: Game layer diagram .......................................................................................100 7.1: Utility improvement, candidate nodes, prototype one ...................................123 7.2: Average utility improvement of network with homogeneous minimum security, prototype one ...................................................................................125 7.3: Comparison of candidate nodes' security, prototype one ..............................126 7.4: Average network security, same minimum, prototype one ...........................128 7.5: Average network security, different minima, prototype one .........................128 7.6: Average security, prototype one ....................................................................129 7.7: Average network utility improvement, prototype one ...................................130 7.8: Candidate nodes' security, different vs. same minimum security, prototype one .................................................................................................131 7.9: Average utility improvement of three networks, prototype one ....................134 7.10: Average security of three networks, prototype one .......................................136 7.11: Percent of achieved maximum security for three networks, prototype one ................................................................................................138 7.12: Average security, selected networks, prototype one......................................140 7.13: Average utility improvement, selected networks, prototype one ..................143 7.14: Average security, prototype two ....................................................................148 7.15: Average local neighborhood count, prototype two ........................................151 7.16: Average utility improvement, prototype two .................................................152 7.17: Average number of nodes forming a coalition, prototype two ......................153 7.18: Percentage of coalition members with sensitive data access, no side payments .................................................................................................154 7.19: Average security, prototype three ..................................................................158 7.20: Average local neighborhood count, prototype three ......................................161 7.21: Average utility improvement, prototype three ...............................................162 7.22: Average number of nodes forming a coalition, prototype three ....................163 7.23: Percentage of local neighborhood that is in coalition, prototype three .........164 7.24: Percentage of coalition members with sensitive data access, prototype three................................................................................................................165 7.25: Percent of nodes making side payments, prototype three ..............................167 7.26: Average security, prototype three v.2 ............................................................170 7.27: Average security, prototype three v.1 and v.2, max security = hetero min+5 .................................................................................172 ix Figure Page 7.28: Average security, prototype three v.1 and v.2, max security = hetero min+6 ................................................................................173 7.29: Percent of nodes making side payments, prototype three v.2 .......................175 7.30: Average local neighborhood count, prototype three v.2 ...............................176 7.31: Average local neighborhood count, prototype three v.1 and v.2 ..................178 7.32: Average maximum security, prototype three v.1 and v.2 .............................179 7.33: Average utility improvement, prototype three v.1 and v.2 ...........................180 7.34: Average number of nodes forming coalition, prototype three v.1 and v.2 ...........................................................................................................181 7.35: Average percentage of coalition members granted sensitive data access, prototype three v.1 and v.2 ...............................................................182 7.36: Best performing networks per respective prototype .....................................184 7.37: Average security, pure and mixed strategies ................................................187 7.38: Average security, prototype four ..................................................................189 7.39: Average utility improvement, prototype four ...............................................191 7.40: Percent of nodes making side payments, prototype four ..............................193 7.41: Average local neighborhood count, prototype four ......................................194 7.42: Average security, prototype four v.2 ............................................................196 7.43: Average security, Kerberos...........................................................................198 7.44: Percent of all nodes able to participate in Kerberos .....................................199 7.45: Average security for all prototypes, n=43 ....................................................202 7.46: Security comparison, max = hetero min plus 3 network ..............................204 7.47: Security comparison, max = hetero min plus 4 network ..............................205 7.48: Security comparison, max = hetero min plus 5 network ..............................206 7.49: Security comparison, max = hetero min plus 6 network ..............................207 7.50: Security comparison, max = hetero min plus 7 network ..............................208 7.51: Security comparison, max = hetero min plus 8 network ..............................209 7.52: Prototype 1 security, varying n .....................................................................212 7.53: Prototype 2 security, varying n .....................................................................213 7.54: Prototype 3 v.1 security, varying n ...............................................................214 7.55: Prototype 3 v.2 security, varying n ...............................................................215 7.56: Prototype 4 v.1 security, varying n ...............................................................217 7.57: Prototype 4 v.2 security, varying n ...............................................................218 7.58: Kerberos security, varying network size n....................................................219 7.59: Average security for all prototypes, n=20 ....................................................221 7.60: Average security for all prototypes, n=60 ....................................................222 7.61: Average security for all prototypes, n=80 ....................................................223 x SYMBOLS A partition on graph G that divides it into coalitions c cost c (si ) cost of security value si for vertex vi c ((sij), σij (sij )) cost of security value sij for edge eij given constraints σij d (j) data of node j E set of edges eij edge from vertex i to vertex j eij all other edges besides vertex i to vertex j G graph composed of the set of vertices and set of edges Γ game of G i node (player) i, represented in the graph by vertex vi j node (player) j, represented in the graph by vertex vj Π potential function rij (d(j)) read access from i to j set of positive real numbers S nondecreasing sequence of nonnegative security levels si security level of player i si security levels of all other players besides i sij security level of eij sij security level of eij s*i optimal action for player i s*i optimal action for all other players besides i xi s* action profile in equilibrium (sij , σij (sij )) security of sij given constraint σij ; also known as move sij for player i , suboptimal move for player i , optimal (equilibrium) move for player i cij(sjk , σjk (sjk )) side payment move for player i to j to induce change in sjk σi constraint of player i σi constraints of all other players besides i σi (si ) constraint of security value si for player i σi (si ) constraint of security value si for all other players besides i σij (sij ) constraint σij of sij u utility function V set of vertices vi vertex i, also referred to as node i or player i vj vertex j, also referred to as node j or player j wij (d(j)) write access from i to j yij current encryption strength of connection eij xii DEFINITIONS • Action: assigning a value to a variable. • Action profile: a sequence of actions for each player in the game; there is one action corresponding to each player in the sequence. • Coalition: a group of players who share a common security level and preferences. • Constraint: a function which maps the domain of possible values a variable may take to the codomain or range of values that do not violate the constraints. • Constraint satisfaction problem: abbreviated CSP, it is a problem defined by a set of variables and corresponding constraints on the variables. • Cooperative game: a game in which players make binding commitments that require the consent of all parties to break the commitment. • Cost: a measure of lost utility. Cost is denominated in units of security. • Edge: see Link • Equilibrium: the best possible move a player can make based on the assumption that all other players also make their best possible moves. Equilibrium maximizes utility, and is a partial order on the actions: they are reflexive, antisymmetric, and transitive with respect to one another. xiii • Finite Improvement Property: all potential games possess this property whereby there is a best possible move for each state of the game. Neither the game nor the improvement can go on forever, and there can be no repeated states, as the game must have a finite end with unique moves and finite utility. • Game: a game consists of the Players, Information, Actions, and Utilities. • Game theory: the study of actions by decisionmakers who are aware that their actions have an impact on others. • Information: a player’s knowledge about the set of variables describing the game, which includes constraints on what actions can and cannot be taken. • Incomplete Preferences: see Partial Preferences • Link: a oneway directed connection between nodes. • Metric: see Security metric • Mixed Strategy: a plan that maps a player’s information to a probability distribution (ranging from 0 to 1) over the set of pure strategies. • Nash equilibrium: see Equilibrium • Node: nodes in graph G represent computers in the network. Nodes are the players in the game. • Noncooperative game: a game in which any commitments made can be unilaterally broken. • Objective function: describes a function to be maximized by all variables in the constraint satisfaction problem. Not all constraint satisfaction problems have an objective function. xiv • Pareto optimized: a state in which a player can take no action deviating from this state without decreasing utility for itself or some other player. • Partial Preferences: equations in which a set of variables may have intermediate or unassigned values. • Partition: to form coalitions, the network is divided into nonoverlapping subsets according to a pairwise disjoint function known as a partition. • Pay: compensation measured in utility to or from another node. • Player: an individual making decisions and taking actions in the game. See also Node, as players are represented by nodes or computers in the network. • Potential function: the potential function takes the same input as the utility function, and returns a calculation that is either the same sign (for an ordinal potential function) or equal to (for an exact potential function) the value calculated by the utility function of each player. The exact potential function is defined as applicable when players move according to mixed strategies, while the ordinal potential is defined to be applicable when players move according to pure strategies. • Potential game: a game possessing a potential function. • Preferences: the current best values for the variables in the game. Since the variables in the game represent security levels, the preferences are the current optimal security levels. They correspond to the environment and its current state. • Problem state: some, but not necessarily all, variables have values assigned to them. • Pure strategy: a plan that maps a player’s information to a single action. • Security: the opposite of vulnerability. In our game, security is optimized by minimizing vulnerability. xv • Security metric: quantitative measurement of some aspect of security. Our metrics are cryptography, data sensitivity, and access control. • Side payment: an action that consists of a payment made from node i to node j to induce j to change the security of its link sjk to another node k. • Solution: a complete assignment of values to variables in a constraint satisfaction problem that do not violate the respective constraints. • Strategy: a plan to take a specific action in a game. Each player has a set of strategies that govern the player’s actions in every conceivable situation. • Utility: the quantity of positive feedback (which in our game is security) which a player receives for taking an action. Utility is denominated in units of security. • Utility function: the utility function takes as input the set of possible actions available to a player and determines a player’s preference over the given set of possible actions. These preferences enable a player to choose the best values that can be assigned to the game variables and maximize its utility at each turn in the game. • Vulnerability: a weakness whereby an outsider may destroy, alter, or steal one’s possessions, which is the data possessed by the nodes as well as the nodes themselves. Vulnerability is the opposite of security. • Weighted potential game: a type of potential game that possesses a utility function which is directly related to other players’ utility functions. A weighted potential game possesses a potential function for either mixed or pure strategies. We use a weighted potential game to optimize network security. 1 CHAPTER I INTRODUCTION Computer networks have changed significantly since their first invention. In the early days of the Internet, the network was composed of nearly identical computers connected to one another by wire, whereas today’s wireless network consists of increasingly heterogeneous devices ranging from PCs to iPhones to servers. Not only are today’s networks more complex to secure, but the attacks on the network are far more sophisticated. The advent of cloud computing and of cyberphysical systems composed of sensor networks, actuators, and control systems has only increased the heterogeneity and complexity of securing such a network. While a great deal of work has been reported on security for individual computers or devices, very little work has been done to optimize security for the overall network when all devices forming the network are not only heterogeneous but also autonomous. The security of the entire network itself is critical and cannot be done piecemeal. The problem considered in our work is how to maximize an entire network’s security when it is made up of computers or devices that may be very different from one another. The computers act independently and autonomously, with no broad or central coordinator. There has been previous research with focus on individual components 2 forming the network, such as Agah [26,27] and Demirbas [29], but these approaches are limited as they fail to optimize security for the entire network. In these approaches, network security is only as good as the security of the weakest component. Our work proposes to allow individual computers to work together to achieve the optimum security for the entire network using game theory. The problem considered in our work centers on a general representation of heterogeneous computers, each with different hardware and software. We consider hardware to include all physical, nonsoftware related computer components such as CPU, RAM, and available power or battery life. Software thus includes both system software, which refers to the operating system, and application software, which includes all other software. The hardware and software of a computer will subsequently restrict its ability to sustain maximum security, which is only possible in an ideal world. The network under consideration is a wireless network, where connections between nodes are assumed to exist a priori. The nodes themselves are not physically mobile, but we assume connections change. These connections change during the network security optimization process. Game theory is one solution to address the problem of maximizing security within a system’s limitations. Game theory, as defined by Rasmusen [8], is the study of actions by decisionmakers who are aware that their actions have an impact on others. A game consists of the players, information, actions, and utilities. The players are defined as the individuals making decisions and taking actions in the game. We define the computers in the network as nodes, and these nodes are the players in our game theoretic security solution proposed in our thesis. In this situation, the players are the computers, or nodes, 3 in the network. The information is defined as the players’ knowledge about the set of variables describing the game, which includes constraints on what actions can and cannot be taken. These variables are input to a player’s utility function, which determines a player’s preference over a given set of possible actions. The utility function takes as input the set of possible actions available to a player and determines a player's preference over the given set of possible actions. These preferences enable a player to choose the best values that can be assigned to the game variables and maximize its utility at each turn in the game. This plan of action is its strategy. The player then takes the best action by assigning these best values to its variables, resulting in a new state of the game. At each turn in the game the player applies new information to its utility function, determines its preference over a given set of possible actions, chooses the best values that can be assigned to the game variables, and maximizes its security. Game theory as an optimization technique offers several advantages over other rulebased, linear programming, treepruning or backtracking algorithms, as well as artificial intelligence (AI) techniques. Game theory allows the game designer to arrive at a solution by developing the model and evaluation criteria for players so they can determine the optimal next move to make in the game to maximize their utility; as the game plays out, the solution evolves, giving the optimal configuration for the network. The designer of the game need only model the moves of the game and their context, allow the players to act autonomously according to these rules, and an optimization results. Furthermore, game theory has the advantage of finding solutions to problems that would otherwise be difficult to solve using other approaches. Game theory can be used 4 to model complex interactions and environments, which in our problem is a heterogeneous network. The use of mixed strategies is unique to game theory and allows for modeling more complex decisionmaking processes than could be done by other techniques. Through the use of mixed strategies, the game designer is able to model the possibility of mistakes made by game players. With pure strategies, players always choose the optimal strategy. With mixed strategies, however, a player chooses a move according to a probability distribution over the set of pure strategies, thus taking the optimal action some percentage of the time and less than optimal otherwise. In our thesis, we will examine the methodology behind how certain game subsets have been proven to have mathematical advantages over others and how such game subsets make it easier to prove a solution is optimal. Furthermore, our thesis will take advantage of the modeling techniques exclusive to a game theoretic problemsolving approach through mixed strategies. It will also allow coalitions, which are otherwise known as groups, to be formed among the game players as part of the game optimization process. Coalitions can be used to improve efficiency as well as give a broader and greater overall security than would be possible in the absence of coalitions. We will develop a heterogeneous game theoretic distributed security model in which game players choose the move that optimizes security; once a player acts on its choice of moves, the state of the game changes, and game play leads to security optimization of the network. An important aspect of our work is that the security optimization found can be validated as opposed to existing or traditional solutions, whose effectiveness is subjective. Traditional security definitions such as “works as expected” [31] are no 5 longer sufficient. An April 2009 report by the Homeland Security Newswire [34] revealed that because they are now connected to the Internet, a significant number of US power plants have, over the past few years, had their systems compromised by intruder programs, and that these potential sleeper agents are still in place in the systems across the entire US electrical grid. Furthermore, these programs have become embedded in other parts of the US infrastructure, which includes water treatment plants. To date, no one is certain how to remove them, or what these programs' function truly serves beyond gathering intelligence, but the sophistication with which they are embedded suggests a wellfinanced organization with skilled members, and is thus most likely related to a foreign government. If so, it is likely that these programs indeed will become active if the US goes to war with the foreign government that put the sleeper software there, and can potentially devastate the US infrastructure. Still, the systems are continuing to work "as expected," and "officials...do not see an immediate danger" [34]. We believe that statements such as these are representative of the traditional security paradigm and do not preclude the possibility that these programs will prevent our power plants to continue to work "as expected" in the future. Clearly, there is a significant need for paradigm shift in the definition of security from a qualitative definition to one that can be measured quantitatively. Security metrics can be used as means to accomplish this paradigm shift. Security metrics is a new field of computer security and its viability as a field of study was first recognized as serious work only a few years ago, but it is beginning to become more widely used. The goal of security metrics is to be able to better analyze security by evaluating a system and quantitatively representing its inner workings and relationships between entities that form the system 6 itself. Security metrics can thus be used as a basis to give quantitative meaning to the qualitative definition. To use metrics in our security solution, we must devise a method of introducing security metrics themselves to a game. To date, no one has done so. However, we believe defining the problem itself as a game possessing a system of variables and constraints on security and energy can allow for the introduction of security metrics. This type of problem, with constraints and variables, is referred to as a constraint satisfaction problem. We define constraints as functions that restrict the domain of values a variable may take to a subset that forms a codomain or range. Constraint satisfaction problems are a traditional AI approach and can represent a multivariable problem with varying domain and ranges. Constraint satisfaction problems are traditionally solved using backtracking, tree pruning, or linear programming. In our work, however, game theory will be used to solve the constraint satisfaction problem, allowing us to model optimal and suboptimal decisions along with problem constraints, and validate our work using security metrics. To further validate the security optimization by our algorithm, we will compare its results with that of the established Kerberos algorithm, which is similar to our own algorithm in that it is designed to provide security for an entire network and uses methods of encryption and access control. For a more complete description of Kerberos, we refer you to [35]. Our work can be generalized to optimize security for almost any network or system because it can be applied to a network made up of computers that possess any 7 degree of heterogeneity. With regard to the sleeper software in the article mentioned earlier, since the parties responsible for securing the power plant have not divulged the manner in which the sleeper agent programs were detected, our only conclusion can be that their method is not one they wish to divulge to protect classified security methods or the programs were discovered by accident. We believe that since the past definition of security is based on the "works as expected" definition in [31], those individuals responsible for power plant security were simply following this definition. Since even today there have been no deviations in power plant expected performance, by this old definition the power plant is secure, and authorities even attest this when they say that there is "no immediate danger" [34]. We believe this event exemplifies the need to improve and redefine security; a first step in doing so would be to ensure that definitions of security are no longer quite as qualitative, as in the "works as expected" definition, but can be measured quantitatively. Our work is the first of which we are aware that uses a weighted potential game for a network security optimization solution. We will use a noncooperative instead of a cooperative game because it better fits our problem definition: noncooperative games focus on strategy and utility maximization, whereas cooperative games do not. Noncooperative games model relationships that may be unilaterally changed by players; there are thus no binding contracts. At each turn of a game, a player chooses its best move to maximize its utility. The best possible move a player can make versus all best possible moves of all other players is defined as an equilibrium, which is also known as Nash equilibrium. This equilibrium is not necessarily the best outcome, because there could still be multiple equilibrium or even a solution that goes beyond what is achievable 8 by equilibrium using traditional noncooperative game analysis. Such improved outcomes and “best” equilibrium are defined as Pareto optimal equilibrium. Potential games are a subset of the class of noncooperative games that indeed do find these Pareto optimal solutions to game theoretic problems. Pareto optimization goes beyond the definition of equilibrium. It is, informally, the best of the equilibrium or more optimal solution than equilibrium. Pareto optimized is defined as a state in which a player can take no action deviating from this state without decreasing utility for itself or some other player. That said, the best way to illustrate the difference between Pareto optimal and equilibrium is by the example of the game known as the Prisoners’ dilemma. In the Prisoners’ dilemma, two players are accused of committing a crime. The players are separated and cannot communicate with one another. The following Table 1.1 illustrates the respective utilities for each action, with units measured in years of imprisonment: Player 1 Player 2 Stay silent Blame Stay silent 1,1 10,0 Blame 0,10 8,8 Table 1.1: Prisoners’ dilemma Clearly, the solution in equilibrium is for each player to Blame the other and accept 8 years imprisonment because of the real possibility of being blamed while staying silent, 9 thus receiving 10 years in prison. However, the Pareto optimal solution is for both to Stay silent because it gives the most utility for all players. If prisoners could cooperate and had incentive to do so, they could get better than equilibrium. Shapley is recognized as being the first to develop a technique that can lead to a Pareto optimal solution for all players and games [2], which will be discussed in greater detail in Chapter II below. Chapter II contains the literature related to our security solution. In Chapters III  VI, we present the methodology of our solution and illustrate its improvements over previous work. Chapter VII contains our prototype simulation and its results, and Chapter VIII contains our conclusions. 10 CHAPTER II REVIEW OF LITERATURE Game theory is the analysis of games. Games can range from simple games, such as chess or checkers, to more complex games used in economic or strategic planning. While some roots of game theoretic strategy can be found in the philosophical writings of Plato and Kant [33], the first real work studying games themselves did not begin until the 19th century. This initial exploration into game theory was very simple and straightforward. Working separately, Cournot and Bertrand analyzed simple games where players chose the optimal move to maximize their utility [32]. While both made only initial contributions to game theory, Cournot is more widely recognized today due to his work on games that have an economic application. Regardless, nothing went beyond initial examination due to the lack of formal mathematical specification. True game theory began in the 20th century with the work by four men: Von Neumann and Morgenstern, Nash, and Shapley. In 1944, Von Neumann and Morgenstern wrote the groundbreaking “The Theory of Games and Economic Behavior” [17], which contained the analysis techniques, general formula for calculating utility to a player, and game terminology still in use today. VonNeumann and Morganstern’s work created the tools necessary to successfully analyze games, which led to a number of future discoveries. In addition, their work ensured that future explorations of game theory to solve problems were 11 restricted to situations and problems that could be fully described by mathematics. For example, using games to model computer problems has been largely successful for the reason that the factors affecting a problem with computers can be modeled with a great degree of certainty. As we know, although computers can malfunction, they are not capable of panic. Modeling a computer problem using game theory thus has greater likelihood of reaching an optimal result. Building upon VonNeumann and Morganstern’s work, John Nash developed the noncooperative game and defined game equilibrium in the 1950s. At the same time, Shapley [21]  [22] took VonNeumann and Morganstern’s work and used it to define the field of cooperative games. Cooperative games tend to spend little effort focusing on the strategy of each player in the game; noncooperative games do the exact opposite. While noncooperative games are now more widely studied than cooperative games, with [8] devoting an entire textbook to them, Shapley is the only living member of the four founders of game theory, and he continues to publish to this day. His efforts have turned toward noncooperative games, but they contain new ideas of how to create noncooperative games that go beyond their traditional definition, giving these games cooperative characteristics. His most recent work [6] developed a game that allows coalitions to form even though variables possess intermediate values. Furthermore, Shapley has made significant improvements on the class of noncooperative games known as potential games [2]; this work is one of the foundations of our thesis. A potential game is a game possessing a function, called a potential function, which is similar to a players' utility function. The potential function takes the same input as the utility function and outputs a value; in the case of an exact potential function, the 12 output is equivalent to that of the result given by the utility function; in the case of an ordinal potential function, the output has only the same sign (positive or negative) as the result output by the utility function. When players move according to mixed strategies, games possessing a potential function can have only an exact potential function; when players move according to pure strategies, the game possesses an ordinal potential function. Let us give the definition of a potential function in its relationship with a utility function as given by Shapley [2]. Given utility function u and potential function v, move m in the game is an element in the set of moves M, denoted (2.1) where M is a member of the set of positive real numbers, denoted (2.2) When move m is input to the ordinal potential function and also to the utility function, the value calculated by the ordinal potential function is positive or zero ifandonlyif the value calculated by the utility function is positive or zero, denoted 0 0 (2.3) For the same utility function u, let us give the definition for the exact potential function according to [2]. For the exact potential function, which is also denoted v, the value calculated by the utility function u is equivalent to the value calculated by the exact potential function v for input m, denoted (2.4) 13 Before delving further into Shapley’s work with potential games, we must examine the history of the potential game and its definition. In 1973 Rosenthal [14] did the earliest work with a type of potential games called congestion games. These games built upon Cournot’s initial work on analyzing oligopolies, whereby all players are selling the same item at different prices, and no new players are introduced once the game begins. The game players were all identical, and contained a finite set of actions. The utility was dependent upon the actions of other players. A linear inverse demand function, with respect to the item being sold in the game, was used to calculate utility. All moves in Rosenthals’ work were considered to be “pure” and were not subject to a probability distribution. Prior to Shapley’s proof in 1996 [2], showing that congestion games were an isomorphism of noncooperative games, a considerable amount of work on potential games was still done using Rosenthal’s work as a foundation. Even today, much of the research still focuses on Rosenthal’s work [11], [13] to the point that it contains the flaws that Shapley has pointed out in 1996. In this respect, it is somewhat myopic; it still follows the pattern of excluding mixed strategies and does not reference Shapley’s recent work in 1996 [2], with the exception of the recent work by Komali [4]. Shapley’s work with potential games [2] is significant. It improves on Rosenthal’s work by adding proofs that give enhanced definitions of potential games and their requirements, making it easier to design a game that has equilibrium and is also Pareto optimal. Shapley’s research deals with mixed and pure strategies and heterogeneous players, which was something that Rosenthal was unable to solve. 14 Shapley was also able to develop an improved type of potential game, the weighted potential game. Defined by Shapley [2], a game that possesses a utility function which is directly related to each of the players’ utility functions is a weighted potential game. A weighted potential game possesses a potential function for either mixed or pure strategies, and has efficiency and convergence improvements over other potential games or myopic, greedy strategy games. Weighted potential games possess at least one equilibrium, and are easier to prove Pareto optimal. Furthermore, the weighted potential game is valid for both mixed or pure strategies and players with any degree of heterogeneity. Shapley’s work with potential games extends to graph theory as well, containing a proof that any game containing a network using weighted potential for utility evaluation is connected, at minimum, by a simple cycle. Shapley explains why the weighted potential game gives a result that is more likely to be optimal than other types of potential games. Because the utility function that determines the weight of benefit between two players is piecewise continuously differentiable, results can be mathematically analyzed prior to any empirical simulations by using the equation of the potential. Nonweighted potential games do not possess this property, as was also proven by Shapley in [2]. Furthermore, the weighted potential game will lead to an optimal solution regardless of the weight used. Besides these improvements, Shapley also recognized and established rules for what leads to optimal solutions for a potential game, which is something not studied by Rosenthal. Foremost is what Shapley defined as the Finite Improvement Property: all 15 potential games possess this in that there is a best possible move for each state of the game, but this alone is not enough to guarantee an optimal solution. In addition, neither the game nor the improvement can go on forever, and there can be no repeated states; the game must have a finite end with unique moves and finite utility. This particular property contradicts Rosenthal and Shapley has a mathematical proof to back it up. In addition, Shapley defined the requirements for nonweighted mixed and pure strategy potential games. As a result of his work Shapley discovered that a potential game admits a cooperative solution to noncooperative game; in theory this would allow the players in the Prisoners’ dilemma to collaborate indirectly by maximizing the potential function. To explain this further, the incorporation of a potential function gives the noncooperative players, which have no binding contract to one another by the nature of the noncooperative game, a type of motivation and nonverbal collusion which creates a unique hybrid of noncooperative and cooperative games; if all players try to jointly maximize the potential function it effectively acts as a binding contract between the players. Hence in the case of the Prisoners’ dilemma, instead of each accusing the other, both players play the move to remain silent by jointly maximizing the potential function between them. The Pareto optimal solution would thus be reached concurrently by both players because the potential function changed the conditions of the game, allowing for a more beneficial solution for both players to be reached. Our understanding of Shapley’s work in [2] is that Paretooptimality supersedes equilibrium by its definition. While it is not spelled out in English words, but in equations, much of his most groundbreaking work takes this form. We have not found 16 any other works that reference this point about Pareto optimality, although the work by [4] implies that he understands it. However, despite the lack of other sources found, based upon the fact that much of Shapley’s work is purely in the form of an equation with little written Englishlanguage explanation, and that no authors found thus far are aware of Shapley’s contributions until referenced secondhand by another author who does understand Shapley’s equations, we believe that we are correctly reading his work. Shapley goes on to say in [2] that the existence of a potential function guarantees the existence of equilibrium. However, there may be several local equilibrium in addition to the best equilibrium overall. Rosenthal had previously postulated that the way to find the best equilibrium, which yields the Pareto optimal solution, is to solve for the maximum of the function, known as the argmax. While it seems obvious, it is not game theoretic, and defeats the purpose of the game. Still, other authors [4], [11], follow Rosenthal’s bad example despite this, and even go so far to use it as a method of proof as suggested by Rosenthal. Shapley’s work in [2] sheds light on Rosenthal’s shortcomings: experimental results showed that solving for the argmax could be used to determine which equilibrium is the optimum, but formal proofs demonstrate why solving for argmax is an invalid proof or predictor of the game itself. If one considers it logically, Shapley’s reasoning becomes obvious: solving for the maximum value of an equation is insufficient to describe the complexities of a game. Instead, Shapley said, argmax should be used as a refinement tool to identify and eliminate any possible false equilibrium. As stated earlier, authors such as [4], [11] have ignored much of Shapley’s work in this area, correctly using argmax as a refinement tool but incorrectly using it as a proof of equilibrium. 17 Komali’s proof for Pareto optimality of the equilibrium is similar to [11]. The optimal point is examined; once reached, change in utility would result in a player disconnecting from the network and subsequently cause the player to no longer be optimal or in equilibrium, which is correct. Ironically, parts of the Pareto optimality proofs by [4] and [11] are both logically unsound. Our understanding of logical equivalence leads us to believe that the proofs on Paretooptimality in [4], [11] are overworked via proof by contradiction to the point that they do not prove their original goal; these Pareto optimal proofs instead prove a logical inequivalence of their original statement. We refer the reader to [4] and [11] for the proofs themselves. We select the proof in [4]. To help clarify our own argument, we reproduce their statements; a game that meets these criteria is considered Pareto optimal: If the potential function will converge to equilibrium in the game, then no player can deviate from an action in equilibrium without violating its constraints and thus decrease utility and make the action not in Pareto optimal equilibrium. Let us examine the logical statements used in their proofbycontradiction of a Pareto optimal game to explain our reasoning. Let the statement p represent the first logical statement of the proof in [4] p: the potential function will converge to equilibrium in the game. Let the statement q represent the first part of the second logical statement of the proof in [4] 18 q: no player can deviate from its equilibrium action without violating its constraints. Let the statement r represent the second part of the second logical statement of the proof in [4] r: no player can deviate from Pareto optimal equilibrium action without decreasing its utility. Let the statement s represent the third logical statement of the proof in [4]. We understand the action causing deviation from equilibrium to mean “deviates from equilibrium action,” giving s: if a player deviates from its Pareto optimal equilibrium action, then the action is not in equilibrium. Note that statements q, r, and s are negations of statements. The first part of statements q, r and s address deviating from an equilibrium action, which is the opposite of playing an equilibrium action. The second part of the statements addresses violating constraints and decreasing utility, which is the opposite of preserving constraints and maximizing utility, respectively. Let us now break up q, r, s even smaller using the following statements: t: player plays action in Pareto optimal equilibrium u: player preserves constraints of its action v: player maximizes utility 19 We can now write q, r, and s symbolically: , , The latter statement is what [4], [11] focus their proofbycontradiction upon. However, proofbycontradiction works when the hypothesis and conclusion are different, which is not what we have here in statement s. Proofbycontradiction works by assuming the hypothesis true and conclusion false, and using this to arrive at a contradiction of the negated conclusion. We understand statement s above to be vacuous as it literally reads, “if a player plays an action in equilibrium, then a player does not play an action in equilibrium.” The authors in [4], [11] did not break down statement s into its substatements. Writing the statements symbolically has exposed the overcomplexity of this proofbycontradiction approach. This work by Komali in [4] focuses optimizing communications energy consumption in a network with game theory. In combination with ordinal potential functions, Komali constructs a game with graphs and greedy strategies where all players are identical and use pure strategies only. This work builds upon a proof by Shapley stating that said graphs are connected, at minimum, by a simple cycle. Specifically, Shapley states [2] that a graph representing a game is connected if the function used to calculate utility and thereby determine the best strategies is a potential function. Komali’s resulting game is noncooperative, and achieves an equilibrium that is Pareto optimal. However, its game 20 only addresses homogeneous players and ordinal utility with pure strategies, and does not examine heterogeneous players or mixed strategies. Its equation to calculate utility using linear inverse demand is a variation on Shapley’s [2] and Rosenthal’s [14] work: each player receives diminishing utility for every other player to whom it is connected, but also receives additional constant utility for maintaining network connectivity. Our understanding of the utility equation in Komali [4] is that it differs from the work in [2] because Komali has tailored his solution to fit his greedy strategies that determine player moves in the game; the utility calculations are only part of the players’ strategy. The proof that Komali’s algorithm in [4] is in equilibrium is in his earlier work [30]: however his proof ignores Shapley’s instructions [2] and instead uses argmax as a method of proof, which is invalid according to [2]. Thus Komali’s work leaves open the possibility of a subset of solutions not in equilibrium. In our own simulations of Komali’s algorithm in [4], its utility improvement fluctuates back and forth in a sinewavelike pattern around a threshold, never completely reaching the Pareto optimal equilibrium; see Figure 2.1 below. These results indicate Komali is indeed taking argmax of the final set of utilities fluctuating around a threshold to distinguish between optimal and suboptimal equilibrium. We believe this should have been incorporated into his algorithm; as it stands, this inability to distinguish between Pareto and suboptimal equilibrium is a flaw. We conclude the flaw is most likely caused by Komali’s greedy strategy used by players, which Shapley [2] says can tend to a suboptimal solution for potential games. However, Komali’s earlier work in [30] acknowledges that the optimal utility indeed does transition around a threshold and that this is sufficient for him for convergence. Regardless, we do not agree as mentioned 21 earlier, and believe improvements could be made in his work. Our own simulation of the energy optimization algorithm in Komali [4] is shown in Figure 2.1 below. Figure 2.1: Our own simulation of the energy optimization algorithm in [4] Besides the work by Komali, other work has been done in the area of tying noncooperative games to Pareto optimality. Heikkinen [11] examines a qualityofservice bandwidth allocation scheme in a distributed homogeneous network within the framework of a purestrategy noncooperative game, and uses Pareto optimality to prove that the equilibrium reached is best overall. It also shares a common approach to [4] in that the algorithm used by the players to maximize utility is a greedy one, and was successful at achieving results for equilibrium that is also Pareto optimal for the examined cases. However, the work is applicable to homogeneous players and pure 6.00% 4.00% 2.00% 0.00% 2.00% 4.00% 6.00% 0 2 4 6 8 10 12 14 Utility Improvement Iterations Komali [4] simulation: Utility improvement 22 strategies only, as it does not build upon Shapley’s work in [2] despite its publication at a later date. In addition to his work with potential games, Shapley also determined how to combine players in a game into coalitions by using a function that became known as the Shapley value [8], [21]. The Shapley value ensures that an individual player receives, as utility, an average of the utilities that other players receive for the player's actions; it acts as a sort of "golden rule" for players, and it was discovered by Shapley [2] that it is required for a game to have a potential function. In doing so, Shapley discovered additional requirements for all games using potential functions that were not listed before Shapley’s 1996 work. The game must also have a finite end with unique moves and finite utility. These requirements were not even hinted at in Rosenthal’s work. Shapley's 2008 work on multiplayer utility [6] continues this, examining forming coalitions without negotiation when only partial player preferences are known. This work assumes that that preference can be quantified. Preferences are the current best values for the variables in the game. Since the variables in the game represent security levels, the preferences are the current optimal security levels of the connections in the graph. Partial preferences, which are sometimes called incomplete preferences, are equations in which a set of variables may have intermediate or unassigned values. In the case of a game, the variables correspond to the players or variables maximized by the players, and the partial preferences themselves refer to the intermediate states of the game prior to equilibrium. Coalition formation in [6] is done by quantitatively comparing partial and complete preferences of players and coalitions. 23 Individual preferences are used to facilitate coalition formation. These preferences are combined using the mathematical fact that equilibrium is a partial order, and any remaining unknowns are combined using a weighted sum. This technique is able to aggregate individual preferences to coalition preferences without needing to arbitrate between the players. While Shapley does not explain it in words, we understand his equations to indicate that the reason the coalition formation algorithm works so well with partial preferences is that it takes advantage of the mathematical foundations of game theory to form coalitions. Specifically, Shapley’s coalition formation algorithm uses the property that an equilibrium is a partial order on the strategies as established in the mathematics of VonNeumann and Morganstern [17]. In addition, Shapley proves in [6] that because the design of a weighted potential game means the players are already receiving utility based upon the weight used, it leads more easily to coalition formation because of the collaboration already inherent in the weighted potential game. Coalition formation involves forming what are known as coalition preferences. We understand that these coalition preferences are quantified from a Cartesian product, which defines the actions of the game as described earlier, to a real number by using a weighted sum of the individual preferences that already exist prior to coalition formation. This is not the game theoretic weight as defined earlier in the context of a potential game, but refers to the algebraic definition, whereby a number is multiplied by each of the elements in the Cartesian product, and then the elements are added together. Shapley points out that there is no formula given in past work indicating how to best determine these weights for coalition preferences, but if there is an already existing 24 schema then it will facilitate easier coalition formation. Since this weight is between two players, and the coalition examined contains the same two players, it is in and of itself an optimized coalition preference weight. Coalitions themselves are already in wide use; for example, any network containing a WindowsNT system divides users into coalitions, which are usually referred to as groups in a Windows environment. It restricts certain users in a coalition from having access to resources on the network, while other users belonging to a different coalition are granted such access. The primary advantage of using coalitions to grant permissions is its speed: it is faster than other approaches. The first approach commonly used, a zeroknowledge based system, grants permissions to individuals if they can prove secret knowledge; but by doing so they do not reveal the secret itself. A graph isomorphism is a means of implementing a zeroknowledge based system, whereby a graph representation of knowledge is shown to be identical to another graph with different vertex names. The problem with this approach is its inefficiency: proving the two graphs are an isomorphism of one another involves examining all possible combinations. The other approach commonly used for granting permissions involves secretkey encryption, but it is expensive to implement. Other work besides [4], [11] studies Pareto optimal potential games: the work by Bauso [13] examines this in a network resource sharing game. Bauso builds primarily upon Rosenthal [14] for potential games. But, like [11], he does not build upon Shapley [2], [6] despite the later publication date; this in turn causes Bauso’s results to be suboptimal. Specifically, Bauso examines purestrategy noncooperative nonrepeated (oneshot) and repeated games. Bauso correctly uses argmax to refine his answer and select the best equilibrium, but again like [4], [11] also uses it incorrectly to do an empirical 25 proof for Pareto optimality in oneshot games. This is not all: by overlooking Shapley [2], [6], Bauso’s work fails to find a Pareto optimal solution for coalitions and repeated games. Furthermore, Bauso’s coalition formation algorithm does not work. While Bauso’s game is partially correct in that it uses the Finite Improvement Property, according to Shapley [2] the Finite Improvement Property does not guarantee that a game possess a potential function. Rather, as stated above, the game must also have a finite end with unique moves and finite utility. What Bauso did with a repeated game possessing a potential function is violate its requirements according to Shapley [2]: the game is repeated and so each time it is restarted and played again, there exists at least one state that is not unique as it was played identically the last time around. Like Komali [4], Johari [1] develops interesting solutions using noncooperative games represented by a graph, but avoids potential functions altogether. Johari’s work addresses energy conservation for message passing in networks, and uses both noncooperative and cooperative games. In these games, all strategies are pure, and all nodes homogeneous, but unlike Komali uses the idea of bids between nodes to establish connections between nodes. Bidding takes place using a type of currency and occurs in sequence from one player to the next. Johari found several types of simple topologies that result when game theory is applied to graphs for the purpose of reaching some type of equilibrium. If the cost is applied only to the initiator of a connection, as characterized by noncooperative games, the star topology has the least cost to all nodes and will form. Otherwise, if cost is applied to both parties, as in the case of a cooperative game, a simple cycle or wheel forms. The simple cycle was also found by Johari to be a degenerative 26 topology: soon after the network formed by the noncooperative game degenerated from a star to a simple cycle, the network disconnected. While the above work is significant with respect to the game theoretic aspect to our security optimization solution, it does not address security. All previous game theoretic work with security deals with individual elements or components in the network. Only a few authors have examined using game theory to help solve security problems, and none of these authors have examined optimizing overall security, let alone overall security in a network. In addition, we are not aware of any previous game theoretic security optimization that validates its work using security metrics. For the little work that has been done in the area of game theory and security, the primary work has been done by Agah [26]  [27] to model a scenario where an attacker drops packets to cause communication disruption in a network. Here, game players represent nodes in the network, and players receive utility based on the number of successfully transferred packets. As a method of defense and attacker detection, each player individually examines the percentage of its own message packets not forwarded by other players. If another player fails to forward a percentage of messages beyond a threshold, then that other player is removed from its network. All other work in the area [28]  [29] follows a similar pattern. The work by Demirbas [29] is similar in that it also examines network games that optimize security for each component. However, their work focuses more on reconfiguring individual nodes to stabilize the network so that it may address the problem of defending against a direct attack against each individual player. The third significant 27 work with game theory and security is done by Sun [28], who uses game theory with security and economics at the component level. Each individual part of a network is examined, and cost/benefit analysis is done with respect to additional investment. Results showed that the cost inflicted by an attacker on each component is directly reduced by the security investment. While interesting in a broad sense, the results are generic and do not list any particular types of investment, but includes every possibility in one category. Recent work in the area of security metrics has examined the shortfall caused by generic security definitions. Security metrics are based on the idea of going beyond traditional qualitative security definitions into the area of quantitative measurement and analysis. Past definitions of security include such phrases as “works as expected” [31]. Such qualitative definitions, while traditional in security, depend upon perceptions of environment; they do not preclude the possibility of hidden vulnerabilities or sleeper agents that fail to affect the expected workings of a system until they are activated and cause destruction, illustrating that the system was never secure even though, up until that point, it did indeed work “as expected” [31]. Preventing such types of attacks is one of the purposes of quantitative security metrics. The earliest work on building a foundation for quantitative security analysis based on security metrics that received attention is by Almerhag and Woodward in 2005 [10]. The paper describes security levels related to the types of operations or rules of composition used to define them; these three levels from least important to most important are neighbor authentication, cryptography, and access control. Authentication is measured by whether or not a neighboring node computer’s identity is able to be 28 verified by a trusted third party in a network. Cryptography is expensive to implement, but prevents a transmission from being altered or decoded by an unwanted third party. Access control is cheaper to implement than cryptography, and works to directly stop individuals from gaining access to unauthorized information, such as user IDs and passwords. Payne [23] of the SANS Institute has a somewhat different definition of security metrics, stating that its core foundation lies in analysis of security data. Here, the essence of effective security analysis is risk analysis, with three core areas: asset value, threat, and vulnerability. Another technique that can be used to quantitatively analyze security is attack trees, which are sometimes called attack graphs. Attack trees are a data structure with nodes representing states of the environment; transitions exist between states. These transitions represent the conditions for moving from one state to another, much like a finite state automaton. Authors Sheyner [9] and Wang [25] have called for the need to quantitatively analyze security using attack trees, but their work lacks a means of quantitatively measuring security for the purpose of attack tree analysis; still, their work is one more step toward finding a means of tying this quantitative analysis to a practical security implementation. Existing approaches using attack trees, such as the work by [40], are representative of the implementation problems attack trees pose, as these works’ analyses degenerate into an NPcomplete problem of analyzing all connections between all nodes in a tree. In fact, much of the work in the area of attack trees, exemplified by [39], are on finding new ways to improve speedup for analyzing this NPcomplete problem. This work by [39] uses a backtracking and sorting of the relationships between nodes in the attack tree prior to any actual analysis taking place. 29 As stated earlier in Chapter I, our thesis will use constraint satisfaction problems as a means to better describe our problem and tie metrics to our game theoretic solution. The idea of constraints in games themselves goes back to the coalitions of games possessing information, capacity, participation, and incentive compatibility constraints. Information constraints are limitations imposed by a game designer on the players, whereby they have limited information about some aspect of the game, be it observing or predicting other players’ moves. As a result, information asymmetry between players results in these games and players must make decisions accordingly. A classic example of information constraints is the Prisoners’ dilemma. The second constraint type, capacity, is generally tied to games involving money or currency, possibly in a generic sense, and the limited capacity players have to spend or produce to maximize their own utility while minimizing cost. The third constraint type, participation constraints, is imposed on players to take part in the game. Last, incentive and compatibility constraints are related to one another. They are used in repeated games describing participation incentives; one example is in a game involving players that can produce products of varying quality to sell, but because other players know that lowquality products are more likely to be defective but cheaper and highquality products are less likely to be defective but more expensive, players know that they must produce highquality products to have a chance to generate a profit. As a result, discounts become the focus of the game to maximize utility. A constraint satisfaction problem is an AI technique that traditionally has nothing to do with game theory. Constraint satisfaction problems models variables’ constraints and variables in a problem, and can be generalized and solved by several different 30 methods. These methods are backtracking or other treepruning techniques. The work by Vickrey [16] was the first to examine the relationship between constraint satisfaction problems and games with complete information. Players in the game were represented by variables in the constraint satisfaction problem, and constraints were used as means of socially forcing players in the game to follow the strategy of other players in their local neighborhood. Constraints in this work were restricted to unary constraints, and it was thus limited by the inability to apply the constraints to any binary mathematical operations. The work by Soni, Singh, and Wellman [7], however, does apply to binary constraints. It builds upon the work by Vickrey, examining repeated cooperative games with complete information for messagepassing optimization, and reformulating the constraint satisfaction problem to allow binary and unary constraints. To do so, the problem in [7] was changed to take place within a graph so that constraints existed between each variable; constraints were related to equilibrium. In this, a constraint was satisfied if the player chose the best strategy to maximize its utility given the other players in the game also choose the best move. Each player, or variable, had its own unary constraint. While their work is significant because it is, as far as we are aware, the first to examine the relationship between constraint satisfaction problems and game theory, the solution is restricted to traditional constraint satisfaction problem solving techniques and can only apply to homogeneous players with pure strategies. The solution uses the authors’ own variation of a backtracking and treepruning algorithm from [16], the foundation of which is a classic AI technique. The work does incorporate game 31 theoretic means of determining tree pruning, but this is secondary to the authors’ own backtracking algorithm; potential functions and optimization are not considered. As mentioned in the introduction, we will compare our algorithm’s security optimization with a known algorithm; the one used will be Kerberos. Again, we refer the reader to [35] for a complete description. In the body of research with comparing new network security algorithms to Kerberos, there have been varying approaches to simulating Kerberos as exemplified by the more recent works of [36] – [38]. Older research in the field tends to focus on using offtheshelf software packages to simulate Kerberos as well as the authors' own algorithms, while newer researchers develop their own model to study specific aspects of Kerberos compared to their own work. In the following more widelyreferenced recent articles, each explores simulating and modifying a Kerberos system. The work by [36], which was published in 2007, apparently marks the beginning of the end of offtheshelf software use for Kerberos simulations. Here, the authors used the popular GSSAPI software package to simulate Kerberos and their own algorithm, only to discover that the accuracy and credibility of anyone’s results from the GSSAPI software had come into question by the international community while the authors (and others) were conducting experiments [36]. The authors of [36] discontinued and abandoned their experiments with GSSAPI, publishing only their formal model and algorithm with a note about the fate of GSSAPI and its discontinued use by the international community. In [37], which was published in the following year, the authors compare computation time of their cryptography model with their own representation of standard Kerberos cryptography by using a different offtheshelf software package called Crypto++. One of the most recent works is by [38], a 2009 32 journal article in which the authors abandon the offtheshelf software approach and instead focus on building a mathematical model and prototype. These authors model the Kerberos network through an equation derived from fluid mechanics to study bandwidth usage in networks; this equation follows similar methodology as the equation used to represent their own network optimization technique. 33 CHAPTER III SECURITY METRICS In this chapter we begin to propose our game theoretic approach to optimize overall security for a heterogeneous network. As far as we are aware, our thesis is the first in the area of optimizing overall network security using game theory. Security, as mentioned earlier in Chapter II, suffers from what we believe to be an insufficiently descriptive definition. While many authors have had difficulty defining what security is, we believe it is relatively easy to define what security is not. Security is not vulnerability, whereby an outsider may destroy, alter, or steal one’s possessions. Possessions are, in the case of our network, the data stored in the computers, the computers themselves, and the connections between computers in the network. We assume that maintaining control of possessions relates to access control, which is itself controlled by user IDs and passwords. Such data is sensitive and should be guarded carefully. Insensitive data is less important, but is still vulnerable to theft. There still exists the possibility in any network that an outsider may intercept or alter data transferred between computers in the network. These instances involving alteration, destruction, or theft of possessions characterize a vulnerable network. Since a vulnerable network is clearly not a secure one, we will define security in terms of what it is not, namely vulnerability. Vulnerability will thus be used as a foundation for our security definition, and network security will 34 be optimized by minimizing vulnerability. To solve the problem of optimizing security, we must first quantitatively measure security so that one can determine whether or not the security has improved. Measurement of security in the system, and not just an individual component, is essential if our proposed approach to security optimization is to be validated. To do so, we build upon existing work in the area of security metrics to come up with our own metrics for quantitative security measurement. Metrics will enable us to more fully describe the problem of security maximization and enable us to quantitatively measure security itself in a meaningful way. Using an approach that allows entities in the network to evaluate their environment without having to resort to qualitative, nebulous definitions could significantly improve evaluation of security and security itself. We propose the use of security metrics as a basis for quantifying security and validating our results. We will develop our metrics, which can enable us to take definitions of security that are typically qualitative and quantify them mathematically. Attack trees are a means of analyzing security. Attack tree analysis is not game theoretic, but is a way of describing the means by which relationships and vulnerabilities in an environment are analyzed for decisionmaking. In our problem, attack trees enable analysis to take the action that maximizes security. Since actions involve changing the value of a variable, and the context of our problem is security, we will see that actions involve changing the values of the security levels between nodes. We develop a methodology for applying metrics for measuring security. Since the metrics quantitatively measure security, these can be used as parameters to the analysis. In an attack tree, the tree root represents the computer whose vulnerability is being assessed. 35 In the tree, if another node or relationship is closer to root it has more access, which can result in greater vulnerability. It is clearly preferred to address a problem further away from the root rather than allowing it to reach levels closer to the root before addressing it. In an ideal world, each computer in the network would be able to implement the maximum possible security. However, we are attempting to optimize security for a heterogeneous network in the world of the practical; there are limitations which prevent the ideal from taking place. The heterogeneity of the computers forming the network prevents them from reaching the same maximum security and places limitations, or constraints, with regard to maximum security of the overall network. Since all devices in the network under consideration are different from one another, there are constraints with respect to available hardware and software, as well as corresponding constraints of the hardware and software itself that limit maximum achievable security. We believe that optimizing security for this type of environment fits the definition of, and at the very least lends itself to, a constraint satisfaction problem. Constraint satisfaction problems have variables, corresponding constraints on the variables, and problem state. A state of the problem represents the current values of some or all variables. Some constraint satisfaction problems have an objective function maximized by all variables; doing so leads to its solution. Thus we will describe the network as a constraint satisfaction problem so that we may better specify the problem of optimizing security within the security limitations. Since we propose the application of game theory to optimize security, we will solve our constraint satisfaction problem using a game. We propose players will use environment data, represented by variables quantified by security metrics, as input to players’ attack 36 tree analyses to determine vulnerability and thereby measure security. In doing so, players may choose the move that maximizes security. As connections change in the network during game play, metrics can be used to measure the changes in the network for attack tree analysis, choice of optimal move, and overall network security. But not all constraint satisfaction problems possess an objective function and can be directly correlated with, and thus be solved by, games. Conversely, not all games can be directly correlated with, and thus solve, the corresponding subset of constraint satisfaction problems. We must identify which constraint satisfaction problem subset can solve a subset of games that fits our problem. Hence we propose to identify the subset of constraint satisfaction problems that can be directly used with a subset of games that fit our security problem. To implement more effective security we will use coalitions. Coalition formation involves separation of nodes according to preferences, which are represented by current assignment of values to security levels of all connections. To give an example, complete preferences for coalition formation takes into account a node i and its links to neighboring nodes. Partial preferences, which are also known as incomplete preferences, take into account the links not made by node i but have been made by other coalition nodes j and k. Partial preferences also include the state of links prior to final optimization. Coalitions are usually formed only once all variables, or preferences, have had their final values assigned to them. To integrate the coalition formation process directly into our security optimization algorithm, we propose using coalition formation with partial preferences. Approaches to coalition formation relying on complete preferences would not be able to be directly integrated into the optimization process 37 itself, as they are instead formed after the optimization is complete, which can place a system in a suboptimal state. Through the above solutions, we propose our work presents a novel optimization technique that improves overall security for a heterogeneous network. 3.1 Problem definition Before examining how to quantitatively measure and optimize security, let us first define the problem, beginning with the network model and its notation. Assume the network whose security is to be optimized is represented by an a priori connected directed graph G = (V, E) (3.1) with set of vertices V and set of directed edges E. Vertex vi, an element of the set vertices, is denoted vi V = {v1, v2, … , vi , vj , vk , … , vn} (3.2) G is minimally connected with at least one edge between each of the n vertices such that there are at minimum 1 (3.3) edges, and thus the set of edges is at minimum denoted E , ,…, !" # (3.4) 38 Furthermore, let vertices represent computer nodes in the network. Let the vertex vi be represented by its index i i = vi V (3.5) and let vertex vj be represented by its index j, where $ % & (3.6) and likewise for all the other vertices in V. A directed edge forming a connection from i to j is written eij E (3.7) We define a directed edge to be synonymous with the terms edge, link, and connection. Likewise, an edge representing a connection from j to i is written eji E (3.8) Let the sequence of all k possible security levels of eij be represented by S, an ntuple containing a nondecreasing sequence of nonnegative real numbers, denoted ' , ,…, ( , 0 (3.9) Let all eij have numerical values associated with them. These are commonly called edge weights; this definition of a weight from graph theory is not to be confused with the type of game described in Chapter II called a weighted potential game. Therefore, we will define the edge weight as the security level of the connection between two nodes, and henceforth refer to it as such to avoid confusion. Thus, let 39 ) ' (3.10) denote security level of connection eij between nodes i and j. Changing a security level sij will be a valid move, or action, in our security optimization game. Hence, the moves in our game are changing the security levels of each sij. If we denote all nodes other than i as & (3.11) And, likewise, all nodes other than j as $ (3.12) where $ % & (3.13) We define the security levels of all direct connections node i makes to its neighbors forming the local network of node i as the union of the security of its connection to node j and its connections to nodes other than j, $ , denoted ) * ") (3.14) And if we assume for all direct connections i makes to its neighbors, we can define si, the security level of node i, as the weakest of all the direct connections from node i. The 40 security level of node i is defined as the minimum of the union of the security levels of all direct connections node i makes to its neighbors, written & + ) * "), (3.15) 3.2 Security metrics We shall define our metrics to measure security. These metrics will consider cryptography, data sensitivity, and access control, but exclude authentication. Authentication is excluded because, in our model, all aspects of the network are visible to all nodes. We therefore assume that any node in the network has authenticated. However, we reserve exploration of the issue of authentication and false impersonation for future work. The following metrics have binary representations. We define the binary representation of each metric as corresponding to security strength; thus if the vulnerability is high, the metric is assigned the binary number 0. 3.3 Cryptography Cryptography allows computers to send data to one another along eij in a way that any outsider or thirdparty who intercepts the data cannot read it. Encryption enables computers to implement cryptography. With weak encryption, there is a greater chance for vulnerability since it is relatively easy for a thirdparty intercepting messages sent 41 along eij to use the message to gain access to a node. An example of weak encryption, which we define as low encryption, would be a connection secured using a 32bit key. An example of strong encryption, which we define as high encryption, would be a connection secured using a 256bit key. Let all connections eij have encryption. Current encryption strength of connection eij is represented by  ) . 0, /01 2 3 &0 1, 4&54 2 3 &0 6 (3.16) Since connection eij has been defined as a directed or oneway connection from node i to node j, according to the definition of eij, yij ≠ yji. 3.4 Data sensitivity The data stored at each node can be either sensitive or insensitive. With sensitive data there is a greater possibility for vulnerability, such as if an intruder gained access to passwords, than with insensitive data. Sensitive data includes, for example, passwords and usernames. Insensitive data excludes sensitive data by definition. Insensitive data includes, for example, time of day, schedules, or other data that does not increase vulnerability if it is stolen. Let all nodes have data; all data of node j, is written 7 $ 80, & & 1, & & & 6 (3.17) 42 3.5 Access control Permissions to read and write a node’s data also affect security. Access to read and write data increases the vulnerability as it increases the possibility of an attacker stealing or modifying the data. Let write access from i to j be represented by 1 ) 7 $ (3.18) Again, the binary number relates to security strength. Consequently, if a node i has write access to data of node j, then it indicates that decreased vulnerability is false, or 0. Thus, 1 ) 7 $ . 0, 07 & 49 1 & 922 0 7 $ 1, 07 & 70 0 49 1 & 922 0 7 $ 6 (3.19) Let read access from i to j be represented by ) 7 $ (3.20) The binary number relates to security strength. Consequently, if a node i has read access to data of node j, then it indicates that decreased vulnerability is false, or 0. ) 7 $ . 0, 07 & 49 97 922 0 7 $ 1, 07 & 70 0 49 97 922 0 7 $ 6 (3.21) With our metrics we can define sij using security metrics )  ) : )+7 $ , : 1 )+7 $ , ' (3.22) 43 We will use algebra for translating a Cartesian product to a real number by applying an algebraic weighted sum to achieve a clearer security level conceptualization, translating a binary Cartesian product to a security value ranging from 0 to 10. In this context, the term “weight” will always be used with the word “sum” since it refers to the algebraic weighted sum and not the game theoretic definition of weight. For node i having connection to j we translate the security definition of sij, which is a Cartesian product, to a real number according to the formula ) ;< ·  ) > ;? · )+7 $ , > ;@ · 1 )+7 $ , (3.23) 3.6 Security metrics example To give an example of translating encryption, read, and write metrics to a real number according to equation (3.23), let us assign nonnegative real numbers to the coefficients of each of the metrics in the weighted sum to give a range of integer security values from 0 through 10, such that ' 0, 1, 2,…, 10 (3.24) Also, to aid in clarifying our example, we will separate the metric of data sensitivity from the read and write metrics. Thus we redefine sij as ) ;< ·  > ;? · > ;@ · 1 > ;B · 7 $ (3.25) We denote the set of all security levels of all h direct links from node i to all other nodes –i, forming the local neighborhood of i, as 44 C ) D) E) (3.26) Thus, for example, if node i has direct connections to nodes $, F, 9, G, 2, then H ) D )E) ), (, I, J, K# Next we determine the values of each weight so security ranges from 0…10, chosen for convenience, according to equation (3.24). We assume that data sensitivity is foremost in determining vulnerability. Since theft of data is of little consequence when it is insensitive and of great consequence when it is sensitive, we weigh data sensitivity the most heavily. Hence we shall assign the numerical value of 5 (out of 10) to ;B. Next, we consider data tampering to be the second greatest vulnerability. Data tampering can cause lost passwords or system failure if data is sensitive, and is accomplished by writing. Access control can be used to prevent an outsider from tampering with data. Encryption can also be used to prevent an outsider from tampering with data. We shall thus assign the same numerical value to the encryption and write metrics, 2 to ;< and ;@. Restricting read access can prevent an outsider from viewing data, which we consider to be less of a possible vulnerability than any of the other metrics, and we shall thus assign the numerical value of 1 to ;?. While encryption can also prevent an outsider from reading data, we consider its ability to prevent data tampering to be more important, and so it outweighs any security consideration for an outsider reading data. Thus, the weights add up to 10, the maximum security level that we assumed: 45 ;< > ;? > ;@ > ;B 2 > 1 > 2 > 5 10 (3.27) And in combination with the binary representation of our metrics, security levels will range from 0 to 10. We can now draw up a table, Table 3.1, which contains the Cartesian product of security metrics converted to real values using our algebraic weighted sum in equation (3.27), to represent the weighted sum and metrics to derive the security values of sij. Note in Table 3.1, if encryption is high and read and write access is restricted, the data sensitivity is irrelevant; hence the same security value for cases 14 and 15. The same can be said of the data for cases 6 and 7, as again, read and write access is denied. We denote these “don’t care” statuses using an X in the respective table cell. 46 Encryption (high) Read (restricted) Write (restricted) Data (insensitive) Security s Weights Case 2 1 2 5 15. 1 1 1 X 10 14. 1 1 1 X 10 13. 1 1 0 1 8 12. 1 1 0 0 3 11. 1 0 1 1 9 10. 1 0 1 0 4 9. 1 0 0 1 7 8. 1 0 0 0 2 7. 0 1 1 X 8 6. 0 1 1 X 8 5. 0 1 0 1 6 4. 0 1 0 0 1 3. 0 0 1 1 7 2. 0 0 1 0 2 1. 0 0 0 1 5 0. 0 0 0 0 0 Table 3.1: Cartesian product of security metrics converted to real values 47 CHAPTER IV CONSTRAINT SATISFACTION To describe our model in further detail, we will specify its constraints and explain how we can use it to improve representation of the requirements of our optimization problem. We will show how our problem can be modeled as a constraint satisfaction problem, which will act as an intermediate step in designing our game. 4.1 Constraint satisfaction problems Constraints represent the limitations of security for each computer in our network, and consequently, constraints are related to the overall network security limitations. A constraint is a function that maps the domain of possible security values S to the range of allowed security values for a computer. It thus restricts the domain of security values S to a subset of S that is achievable by the node given its hardware and software. There may be a great deal of difference in the processing power and other physical computational limits of the computers forming our heterogeneous network we are optimizing in our problem. These hardware and software limitations lead to actual security limits that each computer in the network can achieve. A constraint function is 48 thus itself a function of the hardware and software of a computer. Each kind of software provides a range of security levels, and each kind of hardware provides another range of security levels. The actual range of security values achievable by a computer is somewhat complicated, as it is related to whether the hardware and software independently provide security, or are dependent upon one another. If we consider the domain of security values as the Cartesian product of the set of all computer hardware and software, trying to enumerate all the possibilities would be difficult. The security function depends upon the relationship between hardware and software. In some situations where hardware and software are dependent upon one another for security, if one element is defeated, the other may be worthless. For example, if a security feature of the hardware is defeated, the software could be worthless for providing security. For an example of a problem (outside the scope of this work) such as laptop theft, in this case if a laptop is stolen and hard drive erased, then any software encryption of data on the hard drive is worthless. In other cases, the hardware and software may make each other stronger, such as a physical lock on an office door combined with a password on the computer in the office. Here, an attacker would have to spend time getting past the lock before spending time getting past the password on the computer. Because of the difficulty in deriving a function for all possible combinations of hardware and software, we will characterize the properties the function will have to develop a heuristic that is a reasonable model for our problem. For our problem, we can consider our definition of security as described above using metrics as first being softwarerelated, since encryption and access control to data are related to software. However, we may safely reason that a handheld device such as a 49 cell phone is capable of a lower and smaller range of security than a server due to the hardware and the software differences. Hence, we believe that for most cases related to our problem of optimizing a heterogeneous network, the hardware and software are dependent upon one another. Granted, it is possible that in certain cases our model fails to make sense; we are assuming that computers in our network will have security constraints whereby hardware and software are dependent upon one another, and that all computers being optimized can be characterized by our definitions of security and constraints. If we first characterize unary constraints, which form an essential part of a constraint satisfaction problem, we consider that this relates to the security of one computer’s hardware and software. Unary constraints pertain to the limitations on maximum achievable security of one computer, or rather one node in the network. If we say that a function f1 takes as input the hardware of a node i, 49 719 , and produces a range of security values that is a subset of S, and a second function f2 takes the software of a node i, 0M 19 , and produces another range of security values that is a subset of S, and we assume that these two subsets of f1 and f2 overlap with values in common between them; and if we have software that worsens overall security if the software is weaker, and hardware that worsens overall security if the hardware is weaker, then we can say that the unary constraint function N!IOP 49 719 , 0M 19 is at least as good as the weakest of the hardware and software for node i, N!IOP 49 719 , 0M 19 & M 49 719 , M 0M 19 50 What the security is less than or equal to is another matter. If the quality of the software and hardware are good, giving high security, then we will say that this is a bestcase scenario and consequently represents the maximum security. Here, we assume that we can characterize the maximum security all the possible nodes in our network with this equation, whereby the security is less than or equal to N!IOP 49 719 , 0M 19 Q 9R M 49 719 , M 0M 19 Putting these together to characterize unary constraints, we have the inequality & +M 49 719 , M 0M 19 , Q N!IOP 49 719 , 0M 19 Q 9R M 49 719 , M 0M 19 (4.1) There are exceptions to this model, however, because it is possible that combined hardware and software can work together to give a maximum security value that is greater than the maximum of either the hardware or software. For example, if we have a computer that uses protected memory on a CPU to prevent processes from accessing unauthorized data in combination with encryption on the data, this computer would achieve a security level beyond the maximum of encryption and protected memory, since even if a process was able to view data it was not supposed to, it would then have to get past the encryption on the data. This type of system would represent a significantly reduced vulnerability. However, we are assuming that the computers optimized stay within our model of unary constraints on security in equation (4.1). 51 For ease of notation and to more clearly see the node to which the unary constraint function is being applied, let us denote an abbreviation for constraints in equation (4.1) for each node i as N!IOP M 49 719 , M 0M 19 (4.2) Binary constraints are the other type of constraints in a constraint satisfaction problem, and pertain to the security value of an edge between two nodes. Here, we are dealing with constraints on a network, albeit a small network that is between two nodes. Interactions are complicated, and thus the safest assumption is to base the range of values on the weakest node forming the link. Here, the binary constraints range from the minimum of the weakest node to the maximum of the weakest node. For a connection eij from node i to node j at security sij, & S & +M 49 719 , M 0M 19 , , & TM +49 719 ),, M + 0M 19 ),U V Q J !IOP+49 719 , 0M 19 , 49 719 ), 0M 19 ), Q 9R S & +M 49 719 , M 0M 19 , , & TM +49 719 ),, M + 0M 19 ),U V (4.3) We shall denote an abbreviation for binary constraints of connection eij in equation (4.3) as )+ ), J !IOP+49 719 , 0M 19 , 49 719 ), 0M 19 ), (4.4) 52 Note that if the set of constraints of node i and the set of constraints of node j have something in common between them, a link can be formed between the two nodes. Mathematically, this is written as the intersection of the set of constraints of node i and the set of constraints of node j, denoted W )+ ), % X (4.5) then a link eij at sij can be formed between nodes i and j. Because security levels have to be determined within their constraints, we denote security given its constraints as an ordered pair + , , (4.6) and T ), )+ ),U (4.7) 4.2 Costs We define cost as a way of measuring lost security. We define pay, or payment, as compensation measured in utility to or from another node. Both payment and cost are denominated in units of security. To give an example, payment from one node i to another node j for creating link eij would come in the form of security gained by j through i allocating some of its CPU time to j. Because granting CPU time to node j restricts the available resources of node i, it decreases available resources for i to implement security, but increases the available resources of j to implement security. The cost to i for making 53 the payment would be lost security. For the connection, node i receives utility for the link since it is connected to the rest of the network, but node j will incur cost in the future from retransmitting messages sent by node i. Therefore, future cost to j is offset by payment from i for establishing the link. In doing so, our game fits the definition of a noncooperative game. Cost c of payment from i to j for forming eij shall be denoted as cost of eij, written 2+ ) , (4.8) The cost c of payment from node i to node j to form eij is determined by a varying price scheme, which is accomplished by bidding. The bidding process is tied to strength of need to establish a link measured by the effect it has on security. If a node benefits more by establishing the link, it would be willing to pay more than if little benefit was received. Bidding schemes include iterative or linear movement from the minimum to maximum amount a node is willing to pay. This scheme allows the player to move only some fixed amount each time it raises or lowers a bid; in other words, if a bid starts at 1, its next bid is at 2, then 3, etc… Another type of bidding scheme implements an exponential movement from minimum to maximum amount a node is willing to pay. This bidding scheme follows the pattern of an exponential function, whereby bidding increments are slow initially and increase exponentially as each bid is made. Finally, there exists the possibility of nodes implementing a scheme whereby bids follow a logarithmic movement from minimum to maximum amount willing to pay. 54 4.3 Side payments The calculation to decide the move that gives the most utility may indicate that it is not beneficial for that node to raise its security beyond some level. In addition to payment from node i to node j to form a link eij, we define a second type of payment called a side payment. Side payments are used to induce a node to move beyond its selfish motivations to benefit another node. A side payment is defined as an action that consists of payment made from node i to node j to induce j to change the security, sjk, of its link ejk to node k. If analysis shows that a node i gains the most utility by another node j altering a link to node k, where i is not connected to k, node i can take action to maximize its utility by paying node j to alter its link to node k. Adding side payments to the set of possible moves has the possibility of raising the security level of i as well as other nodes connected to j beyond what would be possible without a system of side payments, swaying the utility calculation of an individual node in favor of distributed security over local security, therefore benefiting the network as a whole. We denote a side payment action from node i to another node j to induce action T )(, )(+ )(,U that changes security of j’s connection to node k as 2 ) T )(, )(+ )(,U (4.9) Since a side payment is an action node i takes that changes a link, which in this case is altering link sjk, it is considered to be a move for node i. As such, it must take place within the constraints of i, . Since cost for the action is applied to i since i 55 must pay j to take action altering link sjk, cost c is additionally notated for clarity to indicate that cost is applied to i as it must pay j to take the action. We assume that j cannot refuse an action once it agrees to take the action. By having nodes pay other nodes to make changes in security that do not affect the other nodes directly but can cause them to become more vulnerable, a type of cooperation takes place. Side payments act as a facilitator of a form of cooperation, regardless of coalition membership, to increase overall security. The end result of this payment is that overall security of the nodes along the attack tree from payee to payer is increased. Without side payments between nodes, there may be areas in the graph or particular nodes for which this solution is suboptimal. This suboptimality can be brought on by individual nodes’ strategies or security limits due to the computers’ constraints. However, we believe side payments help in avoiding these suboptimal scenarios in a network. Besides helping form links, payments between players denominated in the same unit of measure as utility aid in applying attack tree analysis to improve security via side payment. For the above scenario for nodes i, j, and k, if a node i wishes to implement a change between nodes j and k, it corresponds to making a change further down the attack tree. This is cheaper than implementing changes higher up in the tree; changes further down (node k) correspond to earlier changes versus later changes when the problem is imminent (node j) and vulnerability is greater. As a result, not only would it be cheaper to make earlier changes or fixes in the tree, more nodes (such as other nodes connected to node j) can benefit from these changes. Such a payment should only make sense in the context of utility: node i that received benefit should ensure the node j that made the 56 change also benefit, especially when one considers that the node j making the change may not directly benefit from the change. Carrying out attack tree analyzed security changes through side payments enables the cooperation among the nodes. Algorithm 5.2 addresses how nodes perform attack tree analysis. 4.4 Objective function The objective function is a function maximized in a constraint satisfaction problem. Since we have not yet specified all aspects of our approach, describing the objective function beyond any general notation would be premature at this point. We thus say that the objective function, u, is used by all nodes to maximize security given its constraints. 4.5 Constraint satisfaction problems and game subset solvability The use of constraint satisfaction has aided in specifying our solution in more detail, but we must identify a subset of games that work with a constraint satisfaction problem subset for mathematical proof of optimization. This is achieved, explained in detail below, through a noncooperative potential game and constraint satisfaction problem possessing an objective function. Our reasoning is explained in Proof 4.1 below. 57 Theorem 4.1: A potential game that maximizes security can be used to solve a constraint satisfaction problem to maximize security ifandonly if the constraint satisfaction problem has an objective function that maximizes security. Proof 4.1 Proof of Theorem 4.1 Proving this Theorem 4.1 by contradiction is inappropriate as it creates a logical inequivalence that is difficult to resolve due to the use of negation with ifandonlyif. Thus, we will use a direct proof. We will represent the statement in Theorem 4.1 symbolically. p: game with potential function q: constraint satisfaction problem with an objective function Since a constraint satisfaction problem with an objective function by definition maximizes the function per its input, let us define input as security value according to equation (3.9) as ' And also define the objective function of the constraint satisfaction problem as maximization of s given constraint 9R+ , , 58 Statement q is thus written symbolically : 9R , Each player has its own variable that it maximizes, which we shall also call s because we are examining optimizing the same security domain as the constraint satisfaction problem. The domains of p and q are the same. Since a potential function by definition represents a function to be maximized by all parties, it is written 9R But if we consider that there is a corresponding function that restricts s to an allowed set of values that map the domain to a range of allowed values Then we are using the maximization function 9R , which is the potential function. Since 9R+ , , 9R+ , , the objective and potential functions are equivalent and we can write statement p as 3: 9R , Next we need to prove Z3 , Z 3 59 Since we are not trying to prove that all potential games solve all constraint satisfaction problems with objective functions, but that a constraint satisfaction problem with an objective function is solvable by a game with a potential function addressing the same problem, we thus have Z3 , Z 3 Where p: game with a potential function q: constraint satisfaction problem with an objective function With the above, we have 3: 9R , which, as before, is a potential function. We also have a constraint satisfaction problem with objective function, which as stated above is written : 9R , For the case of an exact potential function, the potential function is equivalent to the utility function u, , 9R , Then we do not need to break p into substatements describing , and 9R , since they are equivalent. We can now write symbolically what we are trying to prove as 60 Z3 , Z 3 [ 9R , 9R , which gives, using a truth table to examine logical equivalence for the exact potential function written above p q p ↔q 3. T T T 2. T F F 1. F T F 0. F F T All but case 3 above are vacuous to some degree or are false. We must now prove true for an ordinal potential function and objective function. We have p: game with a potential function q: constraint satisfaction problem with an objective function where 3: 9R , and constraint satisfaction problem with objective function 61 : 9R , Unlike exact potential, an ordinal potential function by definition does not have equality with utility. Instead, the potential function is greater than or equal to zero ifandonlyif the utility function is greater than or equal to zero, meaning p is actually written as 3: 9R , 0 , 0 Unlike the proof for exact potential, where , 9R , , we must break statement p into substatements. Since the substatements are not equal but are the same sign (positive or negative) ifandonlyif the other is the same sign, we must first construct a truth table to prove this before moving on to the larger proof for an ordinal potential function and objective function. Let us represent statement p as the substatements : , 0 : 9R , 0 Then p can be written as Z , Z From the definition of p, q, r, and s, we can write what we are trying to prove as Z , Z , Z which gives, using a truth table to examine logical equivalence 62 q r t (r ↔t) (r ↔t) ↔q 7. T T T T T 6. T T F F F 5. T F T F F 4. T F F T T 3. F T T T F 2. F T F F T 1. F F T F T 0. F F F T F We thus have four cases in the truth table where the result is true. Since cases 1, 2, and 4 are vacuous, but case 7 is valid when all exist, we drop the vacuous cases since they are not applicable. Case 7, however, is true and also valid for our problem definition. Thus because we proved true for the ordinal and exact potential functions, we can conclude that only potential games can be used to solve a constraint satisfaction problem ifandonly if the constraint satisfaction problem has an objective function. Q.E.D. 63 4.6 Utility Because utility is measured in security, choice of the action that gives maximum utility is the choice that maximizes security. To maximize security, node i must analyze the security of existing connections to itself as well as those to its neighbors to which it is directly connected, in order to determine whether connections should be modified. In addition, a node also estimates whether making a new connection or making a side payment to alter a connection would be the best decision to maximize security. We have already denoted the security levels of all existing connections. With their constraints this is denoted T ), )+ ),U * T "), ")+ "),U (4.10) The security levels of nonexisting connections from i, with their constraints, shall be denoted + " ), " )+ " ), , (4.11) The utility function is a mathematical function used by all players to make an optimal decision at each point in a game. The utility function allows a player to choose the best values that can be assigned to the game variables and maximize its reward, or utility, at each turn in the game. Utility in our game is measured in security. Since the purpose of our work is optimizing security, and any game theoretic solution optimizes utility, utility is measured in terms of security. As game variables are represented by all sij, then the utility function allows a player to choose the action that gives maximum security. Since 64 actions involve changing security levels of connections, for connection eij the utility function u is defined as T ), )+ ),U T ), )+ ),U 2+ ) , (4.12) 4.7 Equilibrium in a game The optimal action for node i given its constraints is to choose the security level that maximizes equations (4.10) – (4.12), denoted , 9R \T ), )+ ),U * T "), ")+ "),U * + " ), " )+ " ), ,] (4.13) The rationale for decisionmaking to maximize security is made according to Algorithm 5.2, which uses attack tree analysis. The utility received for this optimal action is denoted , (4.14) An action profile is a sequence containing each player’s move at that particular turn in the game. In some gametheoretic literature an action profile is referred to as a tuple or vector; this type of vector is not one with magnitude or direction, but instead refers to a row or column in a matrix. Hence we refer to this sequence of actions as simply an action profile in order to avoid confusion. This is not to be confused with a strategy, which is an action plan. An action profile is in equilibrium if it contains the 65 best, or optimal, move for each player versus all other best actions of the other players. An action profile in equilibrium, denoted s*, is written + , , , ,…, ! , ! ! , (4.15) In this equation, for example, , refers to the equilibrium action of player 1 given its constraints, and , refers to the equilibrium action of player 2 given that player’s constraints. Recall that actions involve changing security levels of links to other nodes. For example, if we assume best action for player i is forming a connection to player j at security level sij, then in this case , refers to T ), )+ ),U which involves bidding to establish or change the security sij of eij. To give another example, it is also possible that since a side payment is an action which does not involve bidding but alters a connection, it can be an optimal action si* for node i. In this case, if node i is directly connected to node j but not directly connected to node k, if the side payment to j to have j change sjk is calculated to be the optimal action , , then in this case , refers to 2 ) T )(, )(+ )(,U The definition of equilibrium for player i means that its utility, or security, is maximized. No player has any incentive to change its action given no other player 66 changes its action. An action that is not in equilibrium is a suboptimal action. A suboptimal action is defined, given its constraints, for player i as , (4.16) where the suboptimal action is never the equilibrium action, denoted , % , (4.17) The following equation describes the best action, or equilibrium, of player i; security of i is maximized if it takes the best action when all other players take their best action, thereby maximizing the utility function u, denoted + , , " , " " , + , , " , " " , (4.18) 67 CHAPTER V GAME THEORETIC ANALYSIS The best action a node can take is determined by attack tree analysis. However, before examining attack tree analysis to determine the best action, we need to address the reasoning behind the decisionmaking for granting other nodes access to data, which forms an essential component of attack tree analysis. Read and write access form two of the three security metrics. We have not specified whether or not access is granted on a casebycase basis, and if it is, we need to address the reasons behind granting access. Addressing this raises the need for a refined security definition and analysis algorithm, which will be made possible through coalitions. 5.1 Coalition formation for a weighted potential game Coalitions have the advantage of allowing aggregated or broad security levels and access control, which will be made possible in combination with security metrics and attack tree analysis. Without coalitions there is a less efficient method of analysis than is available with them. Without coalitions, the reasoning for nodes granting access to its own data is made on a casebycase basis. To form coalitions, the network is divided into nonoverlapping subsets according to a pairwise disjoint function known as a partition. 68 Coalition formation involves using the partition to combine preferences from individual nodes into a common coalition with one set of common constraints and preferences. First, we must define what we mean by preferences. Preferences are defined as the current best values for the variables in the game, which in other words is the current optimal security levels sij of the connections in the graph. They correspond to the environment and its current state. In our model these are the current values assigned to each variable within its constraints. Coalition formation can take place during the game, when preferences are being formed prior to stabilization. Otherwise, waiting for stabilization of preferences, which corresponds to final value assignment to all variables in the game once optimization is complete, could have the effect of placing the game into a nonequilibrium or nonPareto optimal state. Integrating the coalition formation process into our optimization algorithm without disturbing the optimization requires that coalitions be formed despite partial or incomplete preferences. Partial preferences in our algorithm are handled by the evaluation criteria for coalition formation, as well as the definition security si for each node i. Instead of treating a node as just a sum of its links to other nodes, security si of each node i is evaluated to determine coalition membership. Although nodes of different coalitions can communicate, each node can belong to only one coalition. Our definition of security si and its constraints includes criteria that indirectly takes into account security levels and constraints of other nodes connected to i, in which the nodes have shared preferences and privileges. Since si is defined as the minimum of all direct connections from node i to its neighbors, and each connection sij takes place within its constraints 69 which include constraints of both i and j, our definition of si is related to the constraints of the other node j. In combination with the definition of link formation, whereby both nodes in a link receive benefit, the definition of si will cause our game to be a weighted potential game. Because si takes into account the preferences of node i and all other nodes –i to which it is connected, the utility of node i is directly related to the utility of these other nodes. In addition, the partition that evaluates si for coalition membership must consider the preferences, in our case partial preferences, of both i and the other nodes to which i is connected in the coalition. Despite the partitioning of nodes into nonoverlapping subsets, the graph G of our network is connected because graphs of weighted potential games are, by definition, connected. Although each node can belong to only one coalition, in which the nodes have more access privileges to each other, nodes of different coalitions can still communicate. Coalitions can be used with constraints and metrics to form a type of access control list, which makes coalitions an essential part of security metrics. Once coalitions are formed, there is a common set of constraints for members of the coalition. For example, members of the coalition might have read access to all other members, or write access. Coalition membership can be revoked if a node i changes si to violate coalition constraints σA which are a range of security levels for each member to belong to the coalition. The node is then removed from the coalition and all rights as a coalition member are revoked. The node can choose to change si or try to join another coalition. 70 Algorithm 5.1: Coalition formation Algorithm 5.1 divides nodes into coalitions according to security. To form coalitions, the network is divided into nonoverlapping subsets according to a pairwise disjoint function known as a partition. Each subset has a minimum security level which is a function of the partition. To do so, it applies the partition A to each node’s security level si and sij to place each node into a subset, or coalition, and thus determine coalition membership. The partition A is a threshold function, which we assume has to be calculated, that gives the maximum security difference between nodes in G that can be members of the same coalition. The partition gives coalition constraints σA which are a range of security levels for each member to belong to the coalition. The partition ensures that any messages sent through the coalition are at that coalition’s minimum level of security. Note that according to the definitions of security, link formation, utility, and potential, membership in a coalition according to the partition does not prevent a node from connecting to another node outside its coalition, as the determination as to whether to connect to another node is done according to these equations. Define A as a pairwise disjoint function, or partition, dividing G into nonoverlapping subsets; these subsets are coalitions on A = {{a1}, {a2}, …, {aκ},… , {aη}}. Note that according to the definition of a partition that *A = G, and each coalition {aκ} may contain more than one node, e.g. {aκ} ≥ 1. The number of coalitions formed is dependent on the partition chosen for A. 71 Algorithm 5.1: Coalition formation: Input: G = (V, E), partition A, difference_threshold, security tolerance for coalition membership Output: set of coalitions AQ for each node i V Coalition_formation(G, A, difference_threshold) 1. for each node i V 2. { 3. for each node j = i V 4. { 5. if ( eij ) 6. { 7. Q = A(sij ) 8. if ( Q ≤ difference_threshold ) 9. { 10. Add i to same coalition as j: 11. AQ = {{i, j}} 12. } 13. else 14. { 15. Add i to different coalition from j: 16. AQ = {{i}, {j}} 17. } 18. } 19. if ( ! eij  si < sij ) 20. { 21. Q = A(si ) 22. if ( Q ≤ difference_threshold ) 23. Add i to same coalition as j: AQ ={{i, j}} 24. else 25. Add i to different coalition from j: AQ = {{i}, {j}} 26. } 27. } 28. } 29. return (AQ) 72 The advantage of our coalition formation algorithm is, by introducing coalitions, security of connections can be better described. We use a table, shown below in Table 5.1, as an example to show the effect of coalitions on security. Contrast this table with Tables 5.2 and 5.3, which reflects changes made to the security when coalitions are removed; note the less descriptive security characterized by the data in the Table 5.3. Level Security for connection Read self data Write self data Low 1 Minimum All All 2 Maximum All All 3 Minimum All None 4 Maximum All None 5 Minimum Coalition Coalition 6 Maximum Coalition Coalition 7 Minimum Coalition None 8 Maximum Coalition None 9 Minimum None None High 10 Maximum None None Table 5.1: Security levels with coalitions In the absence of coalitions, security levels are less precise: coalitions are an essential part of fulfilling the requirements for a secure network per the security metrics. Changes to security when coalitions are removed are shown in Table 5.2. 73 Level Security for connection Read self data Write self data Low 1 Minimum All All 2 Maximum All All 3 Minimum All None 4 Maximum All None 5 Minimum Coalition Coalition 6 Maximum Coalition Coalition 7 Minimum Coalition None 8 Maximum Coalition None 9 Minimum None None High 10 Maximum None None Table 5.2: Security levels and changes brought about by removing coalitions Comparing Tables 5.1, 5.2, and 5.3, we see the changes that occur to the security definition if coalitions are removed. The example presented by Table 5.3 below reflects this, as quantization of security is less precise, and shows the final result of changes from Table 5.1 to Table 5.2. Level Security for connection Read self data Write self data Low 1 Minimum All All 2 Maximum All All 3 Minimum All None 4 Maximum All None 5 (was 9) Minimum None None High 6 (was 10) Maximum None None 



A 

B 

C 

D 

E 

F 

I 

J 

K 

L 

O 

P 

R 

S 

T 

U 

V 

W 


