Game Theoretic Security, 2014

	Game Theoretic Security, 2014

Game theory has historically been the provenance of social sciences such as economics, political science, and psychology. Game theory has developed into an umbrella term for the logical side of science that includes both human and non-human actors like computers. It has been used extensively in wireless networks research to develop understanding of stable operation points for networks made of autonomous/selfish nodes. The nodes are considered as the players. Utility functions are often chosen to correspond to achieved connection rate or similar technical metrics. In security, the computer game framework is used to anticipate and analyze intruder and administrator concurrent interactions within the network. Research cited here was presented in 2013 and 2014.

Jinghao Shi, Zhangyu Guan, Chunming Qiao, Tommaso Melodia, Dimitrios Koutsonikolas, Geoffrey Challen. “Crowdsourcing Access Network Spectrum Allocation Using Smartphones.” HotNets-XIII Proceedings of the 13th ACM Workshop on Hot Topics in Networks, October 2014, Pages 17. doi:10.1145/2670518.2673866
Abstract: The hundreds of millions of deployed smartphones provide an unprecedented opportunity to collect data to monitor, debug, and continuously adapt wireless networks to improve performance. In contrast with previous mobile devices, such as laptops, smartphones are always on but mostly idle, making them available to perform measurements that help other nearby active devices make better use of available network resources. We present the design of PocketSniffer, a system delivering wireless measurements from smartphones both to network administrators for monitoring and debugging purposes and to algorithms performing realtime network adaptation. By collecting data from smartphones, PocketSniffer supports novel adaptation algorithms designed around common deployment scenarios involving both cooperative and self-interested clients and networks. We present preliminary results from a prototype and discuss challenges to realizing this vision.
Keywords: Smartphones, crowdsourcing, monitoring (ID#: 15-5880)
URL:  http://doi.acm.org/10.1145/2670518.2673866

Gilles Barthe, Cédric Fournet, Benjamin Grégoire, Pierre-Yves Strub, Nikhil Swamy, Santiago Zanella-Béguelin. “Probabilistic Relational Verification for Cryptographic Implementations.” POPL '14 Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, January 2014, Pages 193-205. doi:10.1145/2535838.2535847
Abstract: Relational program logics have been used for mechanizing formal proofs of various cryptographic constructions. With an eye towards scaling these successes towards end-to-end security proofs for implementations of distributed systems, we present RF*, a relational extension of F*, a general-purpose higher-order stateful programming language with a verification system based on refinement types. The distinguishing feature of F* is a relational Hoare logic for a higher-order, stateful, probabilistic language. Through careful language design, we adapt the F* typechecker to generate both classic and relational verification conditions, and to automatically discharge their proofs using an SMT solver. Thus, we are able to benefit from the existing features of F*, including its abstraction facilities for modular reasoning about program fragments. We evaluate RF* experimentally by programming a series of cryptographic constructions and protocols, and by verifying their security properties, ranging from information flow to unlinkability, integrity, and privacy. Moreover, we validate the design of RF* by formalizing in Coq a core probabilistic λ calculus and a relational refinement type system and proving the soundness of the latter against a denotational semantics of the probabilistic lambda λ calculus.
Keywords: probabilistic programming, program logics (ID#: 15-5881)
URL: http://doi.acm.org/10.1145/2535838.2535847

Patrick McDaniel, Trent Jaeger, Thomas F. La Porta, Nicolas Papernot, Robert J. Walls, Alexander Kott, Lisa Marvel, Ananthram Swami, Prasant Mohapatra, Srikanth V. Krishnamurthy, Iulian Neamtiu. “Security and Science of Agility.” MTD '14 Proceedings of the First ACM Workshop on Moving Target Defense, November 2014, Pages 13-19. doi:10.1145/2663474.2663476
Abstract: Moving target defenses alter the environment in response to adversarial action and perceived threats. Such defenses are a specific example of a broader class of system management techniques called system agility. In its fullest generality, agility is any reasoned modification to a system or environment in response to a functional, performance, or security need. This paper details a recently launched 10-year Cyber-Security Collaborative Research Alliance effort focused in-part on the development of a new science of system agility, of which moving target defenses are a central theme. In this context, the consortium seeks to address the questions of when, what, and how to employ changes to improve the security of an environment, as well as consider how to measure and weigh the effectiveness of different approaches to agility. We discuss several fundamental challenges in developing and using MTD maneuvers, and outline several broad classes of mechanisms that can be used to implement them. We conclude by detailing specific MTD mechanisms used to adaptively quarantine vulnerable code in Android applications, and consider ways of comparing cost and payout of its use.
Keywords: agility, moving target defenses (ID#: 15-5882)
URL:  http://doi.acm.org/10.1145/2663474.2663476

Prabhu Natarajan, Trong Nghia Hoang, Yongkang Wong, Kian Hsiang Low, Mohan Kankanhalli. “Scalable Decision-Theoretic Coordination and Control for Real-time Active Multi-Camera Surveillance.” ICDSC '14 Proceedings of the International Conference on Distributed Smart Cameras, November 2014, Article No. 38. doi:10.1145/2659021.2659042
Abstract: This paper presents an overview of our novel decision-theoretic multi-agent approach for controlling and coordinating multiple active cameras in surveillance. In this approach, a surveillance task is modeled as a stochastic optimization problem, where the active cameras are controlled and coordinated to achieve the desired surveillance goal in presence of uncertainties. We enumerate the practical issues in active camera surveillance and discuss how these issues are addressed in our decision-theoretic approach. We focus on two novel surveillance tasks: maximize the number of targets observed in active cameras with guaranteed image resolution and to improve the fairness in observation of multiple targets. We discuss the overview of our novel decision-theoretic frameworks: Markov Decision Process and Partially Observable Markov Decision Process frameworks for coordinating active cameras in uncertain and partially occluded environments.
Keywords: Active camera networks, Multi-camera coordination and control, Smart camera networks, Surveillance and security (ID#: 15-5883)
URL: http://doi.acm.org/10.1145/2659021.2659042

Koen Claessen, Michał H. Pałka. “Splittable Pseudorandom Number Generators Using Cryptographic Hashing.” Haskell '13 Proceedings of the 2013 ACM SIGPLAN Symposium on Haskell, September 2013, Pages 47-58. doi:10.1145/2503778.2503784
Abstract: We propose a new splittable pseudorandom number generator (PRNG) based on a cryptographic hash function. Splittable PRNGs, in contrast to linear PRNGs, allow the creation of two (seemingly) independent generators from a given random number generator. Splittable PRNGs are very useful for structuring purely functional programs, as they avoid the need for threading around state. We show that the currently known and used splittable PRNGs are either not efficient enough, have inherent flaws, or lack formal arguments about their randomness. In contrast, our proposed generator can be implemented efficiently, and comes with a formal statement and proofs that quantify how 'random' the results are that are generated. The provided proofs give strong randomness guarantees under assumptions commonly made in cryptography.
Keywords: haskell, provable security, splittable pseudorandom number generators (ID#: 15-5884)
URL:  http://dl.acm.org/citation.cfm?doid=2503778.2503784

Fatemeh Vafaee. “Learning the Structure of Large-Scale Bayesian Networks Using Genetic Algorithm.” GECCO '14 Proceedings of the 2014 Conference on Genetic and Evolutionary Computation, July 2014, Pages 855-862. doi:10.1145/2576768.2598223
Abstract: Bayesian networks are probabilistic graphical models representing conditional dependencies among a set of random variables. Due to their concise representation of the joint probability distribution, Bayesian Networks are becoming incrementally popular models for knowledge representation and reasoning in various problem domains. However, learning the structure of the Bayesian networks is an NP-hard problem since the number of structures grows super-exponentially as the number of variables increases. This work therefore is aimed to propose a new hybrid structure learning algorithm that uses mutual dependencies to reduce the search space complexity and recruits the genetic algorithm to effectively search over the reduced space of possible structures. The proposed method is best suited for problems with medium to large number of variables and a limited dataset. It is shown that the proposed method achieves higher model's accuracy as compared to a series of popular structure learning algorithms particularly when the data size gets smaller.
Keywords: Bayesian networks, genetic algorithms, structure learning (ID#: 15-5885)
URL:  http://doi.acm.org/10.1145/2576768.2598223

Yitao Duan. “Distributed Key Generation for Encrypted Deduplication: Achieving the Strongest Privacy.” CCSW '14 Proceedings of the 6th edition of the ACM Workshop on Cloud Computing Security, November 2014, Pages 57-68. doi:10.1145/2664168.2664169
Abstract: Large-scale cloud storage systems often attempt to achieve two seemingly conflicting goals: (1) the systems need to reduce the copies of redundant data to save space, a process called deduplication; and (2) users demand encryption of their data to ensure privacy. Conventional encryption makes deduplication on ciphertexts ineffective, as it destroys data redundancy. A line of work, originated from Convergent Encryption [27], and evolved into Message Locked Encryption [13] and the latest DupLESS architecture [12], strives to solve this problem. DupLESS relies on a key server to help the clients generate encryption keys that result in convergent ciphertexts. In this paper, we first introduce a new security notion appropriate for the setting of deduplication and show that it is strictly stronger than all relevant notions. We then provide a rigorous proof of security against this notion, in the random oracle model, for the DupLESS architecture which is lacking in the original paper. Our proof shows that using additional secret, other than the data itself, for generating encryption keys achieves the best possible security under current deduplication paradigm. We also introduce a distributed protocol that eliminates the need for the key server. This not only provides better protection but also allows less managed systems such as P2P systems to enjoy the high security level. Implementation and evaluation show that the scheme is both robust and practical.
Keywords: cloud computing security, deduplication, deterministic encryption (ID#: 15-5886)
URL:  http://doi.acm.org/10.1145/2664168.2664169

Javier Cámara, Gabriel A. Moreno, David Garlan. “Stochastic Game Analysis and Latency Awareness for Proactive Self-Adaptation.” SEAMS 2014 Proceedings of the 9th International Symposium on Software Engineering for Adaptive and Self-Managing Systems, June 2014, Pages 155-164. doi:10.1145/2593929.2593933
Abstract: Although different approaches to decision-making in self-adaptive systems have shown their effectiveness in the past by factoring in predictions about the system and its environment (e.g., resource availability), no proposal considers the latency associated with the execution of tactics upon the target system. However, different adaptation tactics can take different amounts of time until their effects can be observed. In reactive adaptation, ignoring adaptation tactic latency can lead to suboptimal adaptation decisions (e.g., activating a server that takes more time to boot than the transient spike in traffic that triggered its activation). In proactive adaptation, taking adaptation latency into account is necessary to get the system into the desired state to deal with an upcoming situation. In this paper, we introduce a formal analysis technique based on model checking of stochastic multiplayer games (SMGs) that enables us to quantify the potential benefits of employing dierent types of algorithms for self-adaptation. In particular, we apply this technique to show the potential benefit of considering adaptation tactic latency in proactive adaptation algorithms. Our results show that factoring in tactic latency in decision making improves the outcome of adaptation. We also present an algorithm to do proactive adaptation that considers tactic latency, and show that it achieves higher utility than an algorithm that under the assumption of no latency is optimal.
Keywords: Latency, Proactive adaptation, Stochastic multiplayer games (ID#: 15-5887)
URL: http://doi.acm.org/10.1145/2593929.2593933

Chunyao Song, Tingjian Ge. “Aroma: A New Data Protection Method with Differential Privacy and Accurate Query Answering.” CIKM '14 Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, November 2014, Pages 1569-1578. doi:10.1145/2661829.2661886
Abstract: We propose a new local data perturbation method called Aroma. We first show that Aroma is sound in its privacy protection. For that, we devise a realistic privacy game, called the exposure test. We prove that the αβ algorithm, a previously proposed method that is most closely related to Aroma, performs poorly under the exposure test and fails to provide sufficient privacy in practice. Moreover, any data protection method that satisfies ε-differential privacy will succeed in the test. By proving that Aroma satisfies ε-differential privacy, we show that Aroma offers strong privacy protection. We then demonstrate the utility of Aroma by proving that its estimator has significantly smaller errors than the previous state-of-the-art algorithms such as αβ, AM, and FRAPP. We carry out a systematic empirical study using real-world data to evaluate Aroma, which shows its clear advantages over previous methods.
Keywords: data perturbation, differential privacy, query (ID#: 15-5888)
URL:  http://doi.acm.org/10.1145/2661829.2661886

Florian Hahn, Florian Kerschbaum. “Searchable Encryption with Secure and Efficient Updates.” CCS '14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 310-320.  doi:10.1145/2660267.2660297
Abstract: Searchable (symmetric) encryption allows encryption while still enabling search for keywords. Its immediate application is cloud storage where a client outsources its files while the (cloud) service provider should search and selectively retrieve those. Searchable encryption is an active area of research and a number of schemes with different efficiency and security characteristics have been proposed in the literature. Any scheme for practical adoption should be efficient -- i.e. have sub-linear search time --, dynamic -- i.e. allow updates -- and semantically secure to the most possible extent. Unfortunately, efficient, dynamic searchable encryption schemes suffer from various drawbacks. Either they deteriorate from semantic security to the security of deterministic encryption under updates, they require to store information on the client and for deleted files and keywords or they have very large index sizes. All of this is a problem, since we can expect the majority of data to be later added or changed. Since these schemes are also less efficient than deterministic encryption, they are currently an unfavorable choice for encryption in the cloud. In this paper we present the first searchable encryption scheme whose updates leak no more information than the access pattern, that still has asymptotically optimal search time, linear, very small and asymptotically optimal index size and can be implemented without storage on the client (except the key). Our construction is based on the novel idea of learning the index for efficient access from the access pattern itself. Furthermore, we implement our system and show that it is highly efficient for cloud storage.
Keywords: dynamic searchable encryption, searchable encryption, secure index, update (ID#: 15-5889)
URL: http://doi.acm.org/10.1145/2660267.2660297

Itay Berman, Iftach Haitner, Aris Tentes. “Coin Flipping of Any Constant Bias Implies One-Way Functions.” STOC '14 Proceedings of the 46th Annual ACM Symposium on Theory of Computing, May 2014, Pages 398-407. doi:10.1145/2591796.2591845
Abstract: We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., .499) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias [EQUATION] -- o(1) ≈ .207. Unlike the result of Haitner and Omri, our result also holds for weak coin-flipping protocols.
Keywords: coin-flipping protocols, minimal hardness assumptions, one-way functions (ID#: 15-5890)
URL: http://doi.acm.org/10.1145/2591796.2591845

Hossain Shahriar, Hisham M. Haddad. “Content Provider Leakage Vulnerability Detection in Android Applications.” SIN '14 Proceedings of the 7th International Conference on Security of Information and Networks, September 2014, Pages 359. doi:10.1145/2659651.2659716
Abstract: Although much research effort has focused on Android malware detection, very little attention has been given to implementation-level vulnerabilities. This paper focuses on Content Provider Leakage vulnerability that can be exploited by viewing or editing sensitive data through malware. We present a new technique for detecting content provider leakage vulnerability. We propose Kullback-Leibler Divergence (KLD) as a measure to detect the content provider leakage vulnerability. In particular, our contribution includes the development of a set of elements and mapping the elements to programming principles for secure implementation of content provider classes. These elements are captured from the implementation to form the initial population set. The population set is used to measure the divergence of a newly implemented application with content provider to identify potential vulnerabilities. We also apply a back-off smoothing technique to compute the KLD value. We implement a java prototype tool to evaluate a set of content provider implementations to show the effectiveness of the proposed approach. The initial results show that by choosing an appropriate threshold level, KLD is an effective method for detecting content provider leakage vulnerability.
Keywords: Android Application, Content Provider Vulnerability, Kullback-Leibler Divergence, SQL Injection, Secure Programming (ID#: 15-5891)
URL:  http://doi.acm.org/10.1145/2659651.2659716

Yunhua He, Limin Sun, Zhi Li, Hong Li, Xiuzhen Cheng. “An Optimal Privacy-Preserving Mechanism for Crowdsourced Traffic Monitoring.” FOMC '14 Proceedings of the 10th ACM International Workshop on Foundations of Mobile Computing, August 2014, Pages 11-18. doi:10.1145/2634274.2634275
Abstract: Crowdsourced traffic monitoring employs ubiquitous smartphone users to upload their GPS samples for traffic estimation and prediction. The accuracy of traffic estimation and prediction depends on the number of uploaded samples; but more samples from a user increases the probability of the user being tracked or identified, which raises a significant privacy concern. In this paper, we propose a privacy-preserving upload mechanism that can meet users\textquoteright~diverse privacy requirements while guaranteeing the traffic estimation quality. In this mechanism, the user upload decision process is formalized as a mutual objective optimization problem (user location privacy and traffic service quality) based on an incomplete information game model, in which each player can autonomously decide whether to upload or not to balance the live traffic service quality and its own location privacy for utility maximization. We theoretically prove the incentive compatibility of our proposed mechanism, which can motivate users to follow the game rules. The effectiveness of the proposed mechanism is verified by a simulation study based on real world traffic data.
Keywords: crowdsourcing, game theory, location privacy (ID#: 15-5892)
URL: http://doi.acm.org/10.1145/2634274.2634275

Kevin M. Carter, James F. Riordan, Hamed Okhravi. “A Game Theoretic Approach to Strategy Determination for Dynamic Platform Defenses.” MTD '14 Proceedings of the First ACM Workshop on Moving Target Defense, November 2014, Pages 21-30. doi:10.1145/2663474.2663478
Abstract: Moving target defenses based on dynamic platforms have been proposed as a way to make systems more resistant to attacks by changing the properties of the deployed platforms. Unfortunately, little work has been done on discerning effective strategies for the utilization of these systems, instead relying on two generally false premises: simple randomization leads to diversity and platforms are independent. In this paper, we study the strategic considerations of deploying a dynamic platform system by specifying a relevant threat model and applying game theory and statistical analysis to discover optimal usage strategies. We show that preferential selection of platforms based on optimizing platform diversity approaches the statistically optimal solution and significantly outperforms simple randomization strategies. Counter to popular belief, this deterministic strategy leverages fewer platforms than may be generally available, which increases system security.
Keywords: game theory, moving target, system diversity (ID#: 15-5893)
URL:  http://doi.acm.org/10.1145/2663474.2663478

Eli A. Meirom, Shie Mannor, Ariel Orda. “Network Formation Games with Heterogeneous Players and the Internet Structure.” EC '14 Proceedings of the Fifteenth ACM Conference on Economics and Computation, June 2014, Pages 735-752. doi:10.1145/2600057.2602862
Abstract: We study the structure and evolution of the Internet's Autonomous System (AS) interconnection topology as a game with heterogeneous players. In this network formation game, the utility of a player depends on the network structure, e.g., the distances between nodes and the cost of links. We analyze static properties of the game, such as the prices of anarchy and stability and provide explicit results concerning the generated topologies. Furthermore, we discuss dynamic aspects, demonstrating linear convergence rate and showing that only a restricted subset of equilibria is feasible under realistic dynamics. We also consider the case where utility (or monetary) transfers are allowed between the players.
Keywords: dynamic network formation games, game theory, inter-as topology; as heterogeneity, internet evolution (ID#: 15-5894)
URL: http://doi.acm.org/10.1145/2600057.2602862

Jianye Hao, Eunsuk Kang, Daniel Jackson, Jun Sun. “Adaptive Defending Strategy for Smart Grid Attacks.” SEGS '14 Proceedings of the 2nd Workshop on Smart Energy Grid Security, November 2014, Pages 23-30. doi:10.1145/2667190.2667195
Abstract: One active area of research in smart grid security focuses on applying game-theoretic frameworks to analyze interactions between a system and an attacker and formulate effective defense strategies. In previous work, a Nash equilibrium (NE) solution is chosen as the optimal defense strategy, which [7, 9] implies that the attacker has complete knowledge of the system and would also employ the corresponding NE strategy. In practice, however, the attacker may have limited knowledge and resources, and thus employ an attack which is less than optimal, allowing the defender to devise more efficient strategies. We propose a novel approach called an adaptive Markov Strategy (AMS) for defending a system against attackers with unknown, dynamic behaviors. The algorithm for computing an AMS is theoretically guaranteed to converge to a best response strategy against any stationary attacker, and also converge to a Nash equilibrium if the attacker is sufficiently intelligent to employ the AMS to launch the attack. To evaluate the effectiveness of an AMS in smart grid systems, we study a class of data integrity attacks that involve injecting false voltage information into a substation, with the goal of causing load shedding (and potentially a blackout). Our preliminary results show that the amount of load shedding costs can be significantly reduced by employing an AMS over a NE strategy.
Keywords: adaptive learning, data injection, markov games, smart grid security (ID#: 15-5895)
URL: http://doi.acm.org/10.1145/2667190.2667195

Euijin Choo, Jianchun Jiang, Ting Yu. “COMPARS: Toward an Empirical Approach for Comparing the Resilience of Reputation Systems.” CODASPY '14 Proceedings of the 4th ACM Conference on Data and Application Security and Privacy, March 2014, Pages 87-98. doi:10.1145/2557547.2557565
Abstract: Reputation is a primary mechanism for trust management in decentralized systems. Many reputation-based trust functions have been proposed in the literature. However, picking the right trust function for a given decentralized system is a non-trivial task. One has to consider and balance a variety of factors, including computation and communication costs, scalability and resilience to manipulations by attackers. Although the former two are relatively easy to evaluate, the evaluation of resilience of trust functions is challenging. Most existing work bases evaluation on static attack models, which is unrealistic as it fails to reflect the adaptive nature of adversaries (who are often real human users rather than simple computing agents). In this paper, we highlight the importance of the modeling of adaptive attackers when evaluating reputation-based trust functions, and propose an adaptive framework -- called COMPARS -- for the evaluation of resilience of reputation systems. Given the complexity of reputation systems, it is often difficult, if not impossible, to exactly derive the optimal strategy of an attacker. Therefore, COMPARS takes a practical approach that attempts to capture the reasoning process of an attacker as it decides its next action in a reputation system. Specifically, given a trust function and an attack goal, COMPARS generates an attack tree to estimate the possible outcomes of an attacker's action sequences up to certain points in the future. Through attack trees, COMPARS simulates the optimal attack strategy for a specific reputation function f, which will be used to evaluate the resilience of f. By doing so, COMPARS allows one to conduct a fair and consistent comparison of different reputation functions.
Keywords: evaluation framework, reputation system, resilience, trust functions (ID#: 15-5896)
URL:  http://doi.acm.org/10.1145/2557547.2557565

Ryan M. Rogers, Aaron Roth. “Asymptotically Truthful Equilibrium Selection in Large Congestion Games.” EC '14 Proceedings of the Fifteenth ACM Conference on Economics and Computation, June 2014, Pages 771-782. doi:10.1145/2600057.2602856
Abstract: Studying games in the complete information model makes them analytically tractable. However, large n player interactions are more realistically modeled as games of incomplete information, where players may know little to nothing about the types of other players. Unfortunately, games in incomplete information settings lose many of the nice properties of complete information games: the quality of equilibria can become worse, the equilibria lose their ex-post properties, and coordinating on an equilibrium becomes even more difficult. Because of these problems, we would like to study games of incomplete information, but still implement equilibria of the complete information game induced by the (unknown) realized player types. This problem was recently studied by Kearns et al. [Kearns et al. 2014], and solved in large games by means of introducing a weak mediator: their mediator took as input reported types of players, and output suggested actions which formed a correlated equilibrium of the underlying game. Players had the option to play independently of the mediator, or ignore its suggestions, but crucially, if they decided to opt-in to the mediator, they did not have the power to lie about their type. In this paper, we rectify this deficiency in the setting of large congestion games. We give, in a sense, the weakest possible mediator: it cannot enforce participation, verify types, or enforce its suggestions. Moreover, our mediator implements a Nash equilibrium of the complete information game. We show that it is an (asymptotic) ex-post equilibrium of the incomplete information game for all players to use the mediator honestly, and that when they do so, they end up playing an approximate Nash equilibrium of the induced complete information game. In particular, truthful use of the mediator is a Bayes-Nash equilibrium in any Bayesian game for any prior.
Keywords: algorithms, differential privacy, mechanism design (ID#: 15-5897)
URL: http://doi.acm.org/10.1145/2600057.2602856

Minzhe Guo, Prabir Bhattacharya. “Diverse Virtual Replicas for Improving Intrusion Tolerance in Cloud.” CISR '14 Proceedings of the 9th Annual Cyber and Information Security Research Conference, April 2014, Pages 41-44. doi:10.1145/2602087.2602116
Abstract: Intrusion tolerance is important for services in cloud to continue functioning while under attack. Byzantine fault-tolerant replication is considered a fundamental component of intrusion tolerant systems. However, the monoculture of replicas can render the theoretical properties of Byzantine fault-tolerant system ineffective, even when proactive recovery techniques are employed. This paper exploits the design diversity available from off-the-shelf operating system products and studies how to diversify the configurations of virtual replicas for improving the resilience of the service in the presence of attacks. A game-theoretic model is proposed for studying the optimal diversification strategy for the system defender and an efficient algorithm is designed to approximate the optimal defense strategies in large games.
Keywords: diversity, intrusion tolerance, virtual replica (ID#: 15-5898)
URL: http://doi.acm.org/10.1145/2602087.2602116

Gilles Barthe, François Dupressoir, Pierre-Alain Fouque, Benjamin Grégoire, Jean-Christophe Zapalowicz. “Synthesis of Fault Attacks on Cryptographic Implementations.” CCS '14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 1016-1027. doi:10.1145/2660267.2660304
Abstract: Fault attacks are attacks in which an adversary with physical access to a cryptographic device, say a smartcard, tampers with the execution of an algorithm to retrieve secret material. Since the seminal Bellcore attack on modular exponentiation, there has been extensive work to discover new fault attacks against cryptographic schemes and develop countermeasures against such attacks. Originally focused on high-level algorithmic descriptions, these efforts increasingly focus on concrete implementations. While lowering the abstraction level leads to new fault attacks, it also makes their discovery significantly more challenging. In order to face this trend, it is therefore desirable to develop principled, tool-supported approaches that allow a systematic analysis of the security of cryptographic implementations against fault attacks. We propose, implement, and evaluate a new approach for finding fault attacks against cryptographic implementations. Our approach is based on identifying implementation-independent mathematical properties, or fault conditions. We choose fault conditions so that it is possible to recover secret data purely by computing on sufficiently many data points that satisfy them. Fault conditions capture the essence of a large number of attacks from the literature, including lattice-based attacks on RSA. Moreover, they provide a basis for discovering automatically new attacks: using fault conditions, we specify the problem of finding faulted implementations as a program synthesis problem. Using a specialized form of program synthesis, we discover multiple faulted attacks on RSA and ECDSA. Several of the attacks found by our tool are new, and of independent interest.
Keywords: automated proofs, fault attacks, program synthesis, program verification (ID#: 15-5899)
URL: http://doi.acm.org/10.1145/2660267.2660304

Christian Kroer, Tuomas Sandholm. “Extensive-Form Game Abstraction With Bounds.” EC '14 Proceedings of the Fifteenth ACM Conference on Economics and Computation, June 2014, Pages 621-638. doi:10.1145/2600057.2602905
Abstract: Abstraction has emerged as a key component in solving extensive-form games of incomplete information. However, lossless abstractions are typically too large to solve, so lossy abstraction is needed. All prior lossy abstraction algorithms for extensive-form games either 1) had no bounds on solution quality or 2) depended on specific equilibrium computation approaches, limited forms of abstraction, and only decreased the number of information sets rather than nodes in the game tree. We introduce a theoretical framework that can be used to give bounds on solution quality for any perfect-recall extensive-form game. The framework uses a new notion for mapping abstract strategies to the original game, and it leverages a new equilibrium refinement for analysis. Using this framework, we develop the first general lossy extensive-form game abstraction method with bounds. Experiments show that it finds a lossless abstraction when one is available and lossy abstractions when smaller abstractions are desired. While our framework can be used for lossy abstraction, it is also a powerful tool for lossless abstraction if we set the bound to zero. Prior abstraction algorithms typically operate level by level in the game tree. We introduce the extensive-form game tree isomorphism and action subset selection problems, both important problems for computing abstractions on a level-by-level basis. We show that the former is graph isomorphism complete, and the latter NP-complete. We also prove that level-by-level abstraction can be too myopic and thus fail to find even obvious lossless abstractions.
Keywords: abstraction, equilibrium finding, extensive-form game (ID#: 15-5900)
URL: http://doi.acm.org/10.1145/2600057.2602905

Carlos Barreto, Alvaro A. Cárdenas, Nicanor Quijano, Eduardo Mojica-Nava. “CPS: Market Analysis of Attacks Against Demand Response in the Smart Grid.” ACSAC '14 Proceedings of the 30th Annual Computer Security Applications Conference, December 2014, Pages 136-145. doi:10.1145/2664243.2664284
Abstract: Demand response systems assume an electricity retail-market with strategic electricity consuming agents. The goal in these systems is to design load shaping mechanisms to achieve efficiency of resources and customer satisfaction. Recent research efforts have studied the impact of integrity attacks in simplified versions of the demand response problem, where neither the load consuming agents nor the adversary are strategic. In this paper, we study the impact of integrity attacks considering strategic players (a social planner or a consumer) and a strategic attacker. We identify two types of attackers: (1) a malicious attacker who wants to damage the equipment in the power grid by producing sudden overloads, and (2) a selfish attacker that wants to defraud the system by compromising and then manipulating control (load shaping) signals. We then explore the resiliency of two different demand response systems to these fraudsters and malicious attackers. Our results provide guidelines for system operators deciding which type of demand-response system they want to implement, how to secure them, and directions for detecting these attacks.
Keywords: (not provided) (ID#: 15-5901)
URL:  http://doi.acm.org/10.1145/2664243.2664284

Hongxin Hu, Gail-Joon Ahn, Ziming Zhao, Dejun Yang. “Game Theoretic Analysis of Multiparty Access Control in Online Social Networks.” SACMAT '14 Proceedings of the 19th ACM Symposium on Access Control Models and Technologies, June 2014, Pages 93-102.  doi:10.1145/2613087.2613097
Abstract: Existing online social networks (OSNs) only allow a single user to restrict access to her/his data but cannot provide any mechanism to enforce privacy concerns over data associated with multiple users. This situation leaves privacy conflicts largely unresolved and leads to the potential disclosure of users' sensitive information. To address such an issue, a MultiParty Access Control (MPAC) model was recently proposed, including a systematic approach to identify and resolve privacy conflicts for collaborative data sharing in OSNs. In this paper, we take another step to further study the problem of analyzing the strategic behavior of rational controllers in multiparty access control, where each controller aims to maximize her/his own benefit by adjusting her/his privacy setting in collaborative data sharing in OSNs. We first formulate this problem as a multiparty control game and show the existence of unique Nash Equilibrium (NE) which is critical because at an NE, no controller has any incentive to change her/his privacy setting. We then present algorithms to compute the NE and prove that the system can converge to the NE in only a few iterations. A numerical analysis is also provided for different scenarios that illustrate the interplay of controllers in the multiparty control game. In addition, we conduct user studies of the multiparty control game to explore the gap between game theoretic approaches and real human behaviors.
Keywords: game theory, multiparty access control, social networks (ID#: 15-5902)
URL: http://doi.acm.org/10.1145/2613087.2613097

Florian Kerschbaum, Axel Schroepfer. “Optimal Average-Complexity Ideal-Security Order-Preserving Encryption.” CCS '14 Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, November 2014, Pages 275-286. doi:10.1145/2660267.2660277
Abstract: Order-preserving encryption enables performing many classes of queries -- including range queries -- on encrypted databases. Popa et al. recently presented an ideal-secure order-preserving encryption (or encoding) scheme, but their cost of insertions (encryption) is very high. In this paper we present an also ideal-secure, but significantly more efficient order-preserving encryption scheme. Our scheme is inspired by Reed's referenced work on the average height of random binary search trees. We show that our scheme improves the average communication complexity from O(n log n) to O(n) under uniform distribution. Our scheme also integrates efficiently with adjustable encryption as used in CryptDB. In our experiments for database inserts we achieve a performance increase of up to 81% in LANs and 95% in WANs.
Keywords: adjustable encryption, efficiency, ideal security, in-memory column database, indistinguishability, order-preserving encryption (ID#: 15-5903)
URL:  http://doi.acm.org/10.1145/2660267.2660277

Rui Zhuang, Scott A. DeLoach, Xinming Ou. “Towards a Theory of Moving Target Defense.” MTD '14 Proceedings of the First ACM Workshop on Moving Target Defense, November 2014, Pages 31-40. doi:10.1145/2663474.2663479
Abstract: The static nature of cyber systems gives attackers the advantage of time. Fortunately, a new approach, called the Moving Target Defense (MTD) has emerged as a potential solution to this problem. While promising, there is currently little research to show that MTD systems can work effectively in real systems. In fact, there is no standard definition of what an MTD is, what is meant by attack surface, or metrics to define the effectiveness of such systems. In this paper, we propose an initial theory that will begin to answer some of those questions. The paper defines the key concepts required to formally talk about MTD systems and their basic properties. It also discusses three essential problems of MTD systems, which include the MTD Problem (or how to select the next system configuration), the Adaptation Selection Problem, and the Timing Problem. We then formalize the MTD Entropy Hypothesis, which states that the greater the entropy of the system's configuration, the more effective the MTD system.
Keywords: computer security, moving target defense, network security, science of security (ID#: 15-5904)
URL:  http://doi.acm.org/10.1145/2663474.2663479

Rattikorn Hewett, Sudeeptha Rudrapattana, Phongphun Kijsanayothin. “Cyber-Security Analysis of Smart Grid SCADA Systems with Game Models.” CISR '14 Proceedings of the 9th Annual Cyber and Information Security Research Conference, April 2014, Pages 109-112. doi:10.1145/2602087.2602089
Abstract: Smart grid SCADA (Supervisory Control and Data Acquisition) systems are key drivers to monitor, control and manage critical processes for the delivery and transmission of electricity in smart grids. Security attacks to such systems can have devastating effects on the functionality of the smart grids leading to electrical blackouts, economic losses or even fatalities. This paper presents an analytical game theoretic approach to analyzing security of SCADA smart grids by constructing a model of sequential, nonzero sum, two-player game between an attacker and a security administrator. The distinction of our work is the proposed development of game payoff formulae. A decision analysis can then be obtained by applying backward induction technique on the game tree derived from the proposed payoffs. The paper describes the development of the game payoffs and illustrates its analysis on a real-world scenario of Sybil and node compromised attacks at the sensor level of the smart grid SCADA systems.
Keywords: SCADA, SCADA security, game theory, payoffs, sequential games, utility function (ID#: 15-5905)
URL: http://doi.acm.org/10.1145/2602087.2602089  

Umesh Vazirani, Thomas Vidick. “Robust Device Independent Quantum Key Distribution.” ITCS '14 Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, January 2014, Pages 35-36. doi:10.1145/2554797.2554802
Abstract: Quantum cryptography is based on the discovery that the laws of quantum mechanics allow levels of security that are impossible to replicate in a classical world. Can such levels of security be guaranteed even when the quantum devices on which the protocol relies are untrusted? This fundamental question in quantum cryptography dates back to the early nineties when the challenge of achieving device independent quantum key distribution, or DIQKD, was first formulated [9]. We answer this challenge affirmatively by exhibiting a robust protocol for DIQKD and rigorously proving its security. The protocol achieves a linear key rate while tolerating a constant noise rate in the devices. The security proof assumes only that the devices can be modeled by the laws of quantum mechanics and are spatially isolated from each other and any adversary's laboratory. In particular, we emphasize that the devices may have quantum memory. All previous proofs of security relied either on the use of many independent pairs of devices, or on the absence of noise. To prove security for a DIQKD protocol it is necessary to establish at least that the generated key is truly random even in the presence of a quantum adversary. This is already a challenge, one that was recently resolved. DIQKD is substantially harder, since now the protocol must also guarantee that the key is completely secret from the quantum adversary's point of view, and the entire protocol is robust against noise; this in spite of the substantial amounts of classical information leaked to the adversary throughout the protocol, as part of the error estimation and information reconciliation procedures. Our proof of security builds upon a number of techniques, including randomness extractors that are secure against quantum storage as well as ideas originating in the coding strategy used in the proof of the Holevo-Schumacher-Westmoreland theorem which we apply to bound correlations across multiple rounds in a way not unrelated to information-theoretic proofs of the parallel repetition property for multiplayer games. Our main result can be understood as a new bound on monogamy of entanglement in the type of complex scenario that arises in a key distribution protocol. Precise statements of our results and detailed proofs can be found at arXiv:1210.1810.
Keywords: certified randomness, chsh game, device-independence, monogamy, quantum key distribution (ID#: 15-5906)
URL:  http://doi.acm.org/10.1145/2554797.2554802

George Theodorakopoulos, Reza Shokri, Carmela Troncoso, Jean-Pierre Hubaux, Jean-Yves Le Boudec. “Prolonging the Hide-and-Seek Game: Optimal Trajectory Privacy for Location-Based Services.” WPES '14 Proceedings of the 13th Workshop on Privacy in the Electronic Society, November 2014, Pages 73-82. doi:10.1145/2665943.2665946
Abstract: Human mobility is highly predictable. Individuals tend to only visit a few locations with high frequency, and to move among them in a certain sequence reflecting their habits and daily routine. This predictability has to be taken into account in the design of location privacy preserving mechanisms (LPPMs) in order to effectively protect users when they expose their whereabouts to location-based services (LBSs) continuously. In this paper, we describe a method for creating LPPMs tailored to a user's mobility profile taking into her account privacy and quality of service requirements. By construction, our LPPMs take into account the sequential correlation across the user's exposed locations, providing the maximum possible trajectory privacy, i.e., privacy for the user's past, present location, and expected future locations. Moreover, our LPPMs are optimal against a strategic adversary, i.e., an attacker that implements the strongest inference attack knowing both the LPPM operation and the user's mobility profile. The optimality of the LPPMs in the context of trajectory privacy is a novel contribution, and it is achieved by formulating the LPPM design problem as a Bayesian Stackelberg game between the user and the adversary. An additional benefit of our formal approach is that the design parameters of the LPPM are chosen by the optimization algorithm.
Keywords: bayesian stackelberg game, location privacy, location transition privacy, optimal location obfuscation, privacy-utility tradeoff, trajectory privacy (ID#: 15-5907)
URL: http://doi.acm.org/10.1145/2665943.2665946

Martin Chapman, Gareth Tyson, Peter McBurney, Michael Luck, Simon Parsons. “Playing Hide-and-Seek: An Abstract Game for Cyber Security.” ACySE '14 Proceedings of the 1st International Workshop on Agents and CyberSecurity, May 2014, Article No. 3. doi:10.1145/2602945.2602946
Abstract: In order to begin to solve many of the problems in the domain of cyber security, they must first be transformed into abstract representations, free of complexity and paralysing technical detail. We believe that for many classic security problems, a viable transformation is to consider them as an abstract game of hide-and-seek. The tools required in this game -- such as strategic search and an appreciation of an opponent's likely strategies -- are very similar to the tools required in a number of cyber security applications, and thus developments in strategies for this game can certainly benefit the domain. In this paper we consider hide-and-seek as a formal game, and consider in depth how it is allegorical to the cyber domain, particularly in the problems of attack attribution and attack pivoting. Using this as motivation, we consider the relative performance of several hide and seek strategies using an agent-based simulation model, and present our findings as an initial insight into how to proceed with the solution of real cyber issues.
Keywords: agent-based modelling, cyber security, hide-and-seek games, search games (ID#: 15-5908)
URL: http://doi.acm.org/10.1145/2602945.2602946

Note:

Articles listed on these pages have been found on publicly available internet pages and are cited with links to those pages. Some of the information included herein has been reprinted with permission from the authors or data repositories. Direct any requests via Email to news@scienceofsecurity.net for removal of the links or modifications to specific citations. Please include the ID# of the specific citation in your correspondence.