Nội dung

Nonfunctional requirements validation using nash equilibria 49 3.1.2. Modelling scenarios using Security and Network properties This activity aims to assess the security NFR of the prospective network using a number of scenarios. A game theoretical model of the proposed network is presented and subsequently the necessary tools and notions that enable its security quantification are explained. We model both network and security specifications presented in section 3.1.1. using two graph-theoretic games introduced and investigated in [MPPS05c, MPPS05b, MMPPS06]. The game is played on a graph G representing the network N. The players of the game are of two kinds: the attackers players and the defender players, representing the attacks and the security software of the network. The attackers play on the vertices of the graph, representing the nodes of the network. We consider two scenarios for the defenders: a) The defender plays on the edges of the graph, representing the links of the network. This case models the single-edge–protection security specification and calls this model single-edge-protection game. b) The defender plays on sets of k edges of the graph, representing sets of links of the network. This case models the multiple-edge–protection security specification and calls this model k-edges-protection game. 3.1.2.1 Network Configurations A network configuration s models the location (nodes) of attackers and defense mechanism (link or a set of links) on the network. The positioning of attackers and defenders may follow a probability distribution. That is, each attacker can target more than one node according to some probability distribution and similarly, the defense mechanism may protect more than one link according to another probability distribution. In such a case, have a mixed configuration of s. Otherwise, the configuration is said to be pure; one attacker on one node and the sole defender on one link. This constitutes another property of the scenario specification. Example of the Single-edge-protection game. Figure 2 illustrates a mixed configuration for an example network, N consisting of 8 nodes (n=8). It can be seen that the network is a hit-all type. We assume that there exists 3 different attackers (=3). According to the threat analysis of the security specification, the attacks are uniform; and hence, the probability of an attacker assaulting any node of the network is equal to 1/n which is equal to 1/8. In the Figure, attacker i is indicated by Xi. Next, in the technology analysis of the security specification we designate that the security software mechanism is a single-edge–protection. Hence, modeled using the single-edgeprotection game. Moreover, according to the security specifications, the security mechanism uses a uniform-hit-all probability distribution on a set of links E. Recall that E is such that any node of the network is hit by (exactly) one link of that set. So, the defender chooses each links of this set with probability 1/|E'|= 1/4. In Figure 2, the links, as well as their corresponding visiting probabilities, are indicated by Y and thick lines. 50 Management and Services Fig. 2. An example of a network configuration for the Single-edge-protection game. We assume that there exists 3 different attackers (=3). Each attacker is indicated by X. Each attacker targets any node of the network with probability 1/8. The security software chooses among a subset of links E' to clean them from possible attacks, uniformly at random. The links consisting the set E', and their corresponding visiting probabilities, are indicated by Y in thick lines. So, each link in the set is visited by the security software with probability 1/4. The assessed security level of this scenario is equal to 25%. Example of the k-edges-protection game. Figure 3 illustrates a network configuration for the same sample network of Figure 2 and the same scenario assumptions for the attackers. The scenario specification for the security software mechanism is defined as a multiple-edge–protection. Hence, modeled in a k-edgeprotection game. Here, we assume that k=n/2. Moreover, according to the security specifications, the set of edges E’, that the defense mechanism can clean simultaneously, constitute a k-edges-hit-all set. That is, any node of the network is hit by (exactly) one link of the set E. In Figure 3, the links of the set E’ are indicated by thick lines. Fig. 3. An example of a network configuration for the k-edges-protection game. In this case the defense mechanism can clean k links at the same time; that is k=n/2. Also, the defense mechanism is placed on a set of links E’ such that the set is a k-edges-hit-all indicated with thick lines. The assessed security level of this scenario is equal to 100%. Nonfunctional requirements validation using nash equilibria 51 3.1.3. Validation of the Non-functional Security Requirement 3.1.3.1 A Game-Theoretic Security Measurement To evaluate network security it is necessary to assess the security level of an arbitrary profile (configuration) of the defined game of the prospective network similarly with [MPPS05c, MPPS05b, GMPPS06]. Therefore, consider a pure network configuration s. Let sd be the edges defended by the security software. For each attacker i[], let si be the node in which the attacker strikes. We say that the attacker i is killed by the security mechanism if the node si is one of the two endpoints of the link sd being defended by the security software. Then, the defense ratio [MMPPS06] of the configuration s, denoted by rs is defined to be as follows, when given as a percentage: number of attackers killed in s  100. a (1) expected number of attackers killed in s  100. a (2) rs  For a mixed network configuration, the defense ratio [MMPPS06] of the configuration, rs is defined as: rs  From the above, the optimal defense ratio of a network equals to 100 if the security software manages to kill all attackers. In such a case we specify that the network configuration obtains 100 security level. The larger the value of rs the greater the security level obtained. Through this approach, we assess the security level of perspective networks by only examining stable configurations and hence limited scenarios. Given that, whenever the network reaches a stable a configuration it tents to remain in that configuration, highlights the significance of evaluating scenarios that emerge from this to assess its security NFR. This is because in such configurations no single player has an incentive to unilaterally deviate from its current strategy. So, such configurations constitute the most probable states of the network and hence we use these to define the test scenarios based on which to assess security. Therefore, we escape from the NP-hard problem of having to assess each possible configuration or scenario. We identify such stable configurations evaluate the network security on them. Thus, this measurement constitutes a representative assessment of the security level of prospective networks. Considering that the network designer wishes to achieve a security level of 90%, the following procedure is used to assess the security level for different network configurations. The main constrain of the approach is that it limits its scope to hit-all type networks. Initially, we identify stable configurations resulting from the specifications by the Nash equilibria found in the game of [MMPPS06]. Thus, in order to evaluate network security we evaluate the Nash equilibria of the game of [MPPS05c, MPPS05b]. Indeed they showed a result which is interpreted in our terms as follows: Theorem 1. [MMPPS06] Consider a network N with n nodes such that the network and security and functional and non-functional specifications of Section 3.1.1 (case (a) of Technology analysis of Section 3.1.1) are satisfied. Then the network contains a stable configuration (i.e. a mixed Nash equilibrium) s where the expected number of attackers killed is 2/n. So, the defense ratio here is : 52 Management and Services rs  2  100 n (3) The result combined with equation (1) above implies that the network of Figure 1 has security level equal to 2/n100=2/8100=25, since n=8. This designates that the level of security is 25 given the functional requirements specified in configuration s. This assessment however indicates that the initial NFR specified by the designer is not satisfied using the prescribed functional requirements of the network as is. Hence, the network specification needs to be revised and the security NFR revalidated, prior to implementation. We also use the following result: Theorem 2. [GMPPS06] Consider a network N with n nodes such that the network and security and functional and non-functional requirements given in section 3.1 (b) are satisfied and k=n/2. Then the network contains a stable configuration (i.e. a Nash equilibrium) s where all attackers are killed. So, the defense ratio is rs  a  100  100 a (4) The result implies that the network of Figure 2 has security level equal to 100 (recall that k=n/2 here) given the functional requirements specified in configuration s. This assessment indicates that the NFR specified by the designer a priori is now satisfied using the prescribed functional requirements of the network. 4. Conclusion Security requirements validation is traditionally performed through security-specific testing. Ideally, validation should be performed on all possible network conditions expressed by test scenarios. However, examining all possible scenarios [AD93, AS02] to validate security requirement early in the design phase of a prospective network, constitutes a highly complex and sometimes infeasible task. In this work we manage to accomplish this process in only polynomial time. This is achieved by considering only stable configurations of the system, that we model using Nash equilibria. This yields in a limited set of test scenarios that guarantee the assessment of network’s security level. In this context, the method presented in this paper constitutes a novelty in validating security NFR through game theory. 5. References [AB04] T. Alpcan and T. Basar, ``A Game Theoretic Analysis of Intrusion Detection In Access Control Systems,'' in Proceedings of the 43rd IEEE Conference on Decision and Control , Vol. 2, pp. 1568-1573, 2004. [AD93] J. S. Anderson, B. Durley, ``Using Scenarios in Deficiency-Driven Requirements Engineering,'' in Proceedings of the Requirements Engineering (RE'99), pp. 134-141, 1993. [ADTW03] E. Anshelevich, A. Dasgupta, É. Tardos, and T. Wexler, ‘‘Near-Optimal Network Design with Selfish Agents,” in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pages 511–520, 2003. Nonfunctional requirements validation using nash equilibria 53 [ACY05] J. Aspnes, K. C hang, and A. Yampolskiy, `` Inoculation Strategies for Victims of Viruses and the Sum-of-squares Partition Problem,'' in Proceedings of the 16th Annual A CM-SIAM Symposium on Discrete Algorithms (SODA 2005) , pages 43--52. Society for Industrial and Applied Mathematics, 2005. [B99] D. Burke, A game theory model of Information Warfare, USAF Air Force Institute of Technology, Air University, Master's thesis, 1999. [Car00] J.M. Carroll, Making Use: Scenario-Based Design of Human-Computer Interaction, MIT Press, Cambridge, MIT, 2000. [CHK05] G. Christodoulou and E. Koutsoupias, ‘‘The Price of Anarchy of Finite Congestion Games,” in Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC 2005), pages 67–73, ACM Press, 2005. [CILN02] R. Crook, D. Ince, L. Lin and B. Nuseibeh, ``Security requirements Engineering: When Anti-Requirements Hit the Fan,'' in Proceedings of the 10th Anniversary IEEE Joint International Conference of Computing (STOC 2004) , pages 604—612, ACM Press, 2004. [FPT04] A. Fabrikant, C. H. Papadimitriou, and K. Talwar, ‘‘The Complexity of Pure Nash Equilibria,” in Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004), pages 604–612, ACM Press, 2004. [FAGY00] M. Franklin, Z. Galil, and M. Yung, `` Eavesdropping Games: a Graph- Theoretic Approach to Privacy in Distributed Systems,'' Journal of the ACM , 47(2):225--243, 2000. [GMPPS06] M. Gelastou, M. Mavronicolas, V. G. Papadopoulou, A. Philippou and P. G. Spirakis, "The Power of the Defender", CD-ROM Proceedings of the 2nd International Workshop on Incentive-Based Computing (IBC 2006), in conjunction with the 26th IEEE International Conference on Distributed Computing Systems Workshops (ICDCSW'06), pp. 37, July 2006. [AG05] A. Gregoriades and A. Sutcliffe, ``Scenario-Based Assessment of Non-Functional Requirements,'' Proceedings of the IEEE Transactions on Software Engineering, Vol. 31, no. 5, pp. 392-409, 2005. [KO04] M. Kearns and L. Ortiz, ‘‘Algorithms for Interdependent Security Games,” in Proceedings of the 16th Annual Conference on Neural Information Processing Systems (NIPS 2004), pages 288–297, MIT Press, 2004. [KP99] E. Koutsoupias and C. H. Papadimitriou. ``Worst-Case Equilibria,'' in Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science , pp. 404--413, Springer-Verlag, March 1999. [L01] A. van Lamsweerde, ``Goal-Oriented Requirements Engineering: A Guided Tour,'' Proc. Fifth IEEE Int’l Symp. Requirements Eng. (RE ’01), 2001. [L00] A. van Lamsweerde and E. Letier, ``Handling Obstacles in Goal-Oriented Requirements Engineering,'' IEEE Trans. Software Eng., vol. 26, pp. 978-1005, 2000. [L04] A. van Lamsweerde, ``Elaborating Security Requirements by Construction of Intentional Anti-Models'', in Proceedings of the 26th International Conference on Software Engineering, pp. 148--157, 2004, IEEE Press. [LP86] L. Lovasz and M. D. Plummer, Matching Theory, North-Holland Mathematics Studies, 121, 1986. [NR99] N. Nissan, A. Ronen, “Algorithmic Mechanism Design,” Proceedings of the 31st Annual ACM Symposium on Theory of computing (STOC ’99), pp. 129–140, 1999. [O94] M. J. Osborne and A. Rubinstein, A Course in Game Theory, MIT Press, 1994. 54 Management and Services [MPPS05c] M. Mavronicolas, V. G. Papadopoulou, A. Philippou, and P. G. Spirakis, A Graph- Theoretic Network Security Game, in Proceedings of the 1st International Workshop on Internet and Network Economics (WINE 2005) , volume 3828 of Lecture Notes in Computer Science , pages 969—978, Springer, 2005. [MPPS05b] M. Mavronicolas, V. G. Papadopoulou, A. Philippou, and P. G. Spirakis, ‘‘A Network Game with Attacker and Protector Entities”, in Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), volume 3827 of Lecture Notes in Computer Science, pages 288–297. Springer, 2005. [MMP08] M. Mavronicolas, B. Monien, and V. G. Papadopoulou, ‘‘How Many Attackers Can Selfish Defenders Catch?” in CD-ROM Proceedings of the 41st Hawaii International Conference on System Sciences, Software Technology Track, Algorithmic Challenges in Emerging Applications of Computing Minitrack, January 2008 [MMPPS06] M. Mavronicolas, L. Michael, V. G. Papadopoulou, A. Philippou and P. G. Spirakis, “The Price of Defense”, Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science, pp. 717–728, Vol. 4162, Lecture Notes in Computer Science, Springer-Verlag, August/September 2006. [Nash50] J. F. Nash. ``Equilibrium Points in n-Person Games,'' Proceedings of the National Academy of Sciences of the United States of America , Vol 36, pp 48-49, 1950. [Nash51] J. F. Nash, ``Non-cooperative Games'', Annals of Mathematics , 54(2):286--295, 1951. [C01] C. H. Papadimitriou: ``Algorithms, games, and the internet``, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 749-753, 2001. [P99] C. Potts, ``ScenIC: A Strategy for Inquiry-Driven Requirements Determination,'' Proc. Int'l Symp. Requirements Eng., 1999. [P98] C. Potts and A. Anton, ``A Representational Framework for Scenarios of System Use,'' Requirements Eng., vol. 3, pp. 219-241, 1998. [P94] C. Potts, K. Takahashi, and A. Anton, ``Inquiry-Based Requirements Analysis,'' IEEE Software, vol. 11, pp. 21-32, 1994. [RT02] T. Roughgarden and É. Tardos, ‘‘How Bad is Selfish Routing?” Journal of the ACM, 49(2): 236–259, 2002. [R05] T. Roughgarden, Selfish Routing and the Price of Anarchy. MIT Press, 2005. [S05] I. Summerville, “Software Engineering”, Seventh Edition, Addison Wesley, 2005. [AS02] A.G. Sutcliffe and A. Gregoriades, ``Validating Functional System Requirements with Scenarios'', Proceedings of the First IEEE Joint International Conference of Requirements Engineering (RE '02) , Sept. 2002. [T04] É. Tardos, “Network games, Proceedings of the thirty-sixth Annual ACM symposium on Theory of computing, pp. 341–342,2004 [T01] K.S. Trivedi, Probability and Statistics with Reliability, Queuing, and Computer Science Applications, John Wiley and Sons, New York, 2001, ISBN number 0-471-33341-7. [W08] M. Wing ''Scenario Graphs Applied to Network Security'', Information Assurance: Survivability and Security in Networked Systems , Chapter 9, Yi Qian, James Joshi, David Tipper, and Prashant Krishnamurthy, editors, Morgan Kaufmann Publishers, Elsevier, Inc., 2008, pp. 247-277. [ZJ00] H. Zhu, L., Jin, ``Scenario Analysis in an Automated Tool for Requirements Engineering'', Journal of Requirements Engineering, 5 (1), 2-22, 2000. Constructing geo-information sharing GRID architecture 55 X4 Constructing geo-information sharing GRID architecture 1Institute Qiang Liu1 and Boyan Cheng1,2 of Geo-Spatial Information Science and Technology University of Electronic Science and Technology of China China 2No.95007, Guangzhou, Guangdong China 1. Introduction Along with the development of Internet, Geo-information Sharing and Open GIS are of increasing importance for GIS application fields. Spatial Information Grid (SIG) is the fundamental application of Grid technology in spatial information application service domain. This chapter presents a pilot platform for Resource and Environment Geo-information Sharing for Southwestern China based on Web Services, .NET, OGC, Web GIS, SIG, and Mobile Agent is constructed. The architecture in the pilot platform consists of 3 tiers: application layer, service layer and resource layer. Via the pilot platform, distributed heterogeneous geo-information, software and hardware resource from four provinces and one municipality in Southwestern China is integrated. Geospatial data is the major type of data that human beings have collected. Geospatial data and information are significantly different from those in other disciplines. How to effectively, wisely, and easily use the geospatial data is the key information technology issue that we have to solve. Along with the development of Internet, Geo-information Sharing and Open GIS are of increasing importance. Grid technology is developed for general sharing of computational resources and not aware of the specialty of geospatial data. Spatial Information Grid (SIG) is the fundamental application of Grid technology in spatial information application service domain. This paper presents a pilot platform for Resource and Environment Geo-information Sharing Architecture for the Southwestern China based on Web Services, Open GIS, Spatial Information Grid and OGSI.Net. 1.1. Open Geographical Information Systems In (Panagiotis A. Vretanos. 2005), Open GIS Consortium (OGC) thinks that Interoperability is the “capability to communicate, execute programs, or transfer data among various functional units in a manner that requires the user to have little or no knowledge of the unique characteristics of those units.” There are many methods of information