abstract: The field of cyber-defenses has played catch-up in the cat-and-mouse game of finding vulnerabilities followed by the invention of patches to defend against them. With the complexity and scale of modern-day software, it is difficult to ensure that all known vulnerabilities are patched; moreover, the attacker, with reconnaissance on their side, will eventually discover and leverage them. To take away the attacker's inherent advantage of reconnaissance, researchers have proposed the notion of proactive defenses such as Moving Target Defense (MTD) in cyber-security. In this thesis, I make three key contributions that help to improve the effectiveness of MTD. First, I argue that naive movement strategies for MTD systems, designed based on intuition, are detrimental to both security and performance. To answer the question of how to move, I (1) model MTD as a leader-follower game and formally characterize the notion of optimal movement strategies, (2) leverage expert-curated public data and formal representation methods used in cyber-security to obtain parameters of the game, and (3) propose optimization methods to infer strategies at Strong Stackelberg Equilibrium, addressing issues pertaining to scalability and switching costs. Second, when one cannot readily obtain the parameters of the game-theoretic model but can interact with a system, I propose a novel multi-agent reinforcement learning approach that finds the optimal movement strategy. Third, I investigate the novel use of MTD in three domains-- cyber-deception, machine learning, and critical infrastructure networks. I show that the question of what to move poses non-trivial challenges in these domains. To address them, I propose methods for patch-set selection in the deployment of honey-patches, characterize the notion of differential immunity in deep neural networks, and develop optimization problems that guarantee differential immunity for dynamic sensor placement in power-networks. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2020

L’actuariat non-vie étudie les différents aspects quantitatifs de l’activité d’assurance. Cette thèse vise à expliquer sous différentes perspectives les interactions entre les différents agents économiques, l’assuré, l’assureur et le marché, sur un marché d’assurance. Le chapitre 1 souligne à quel point la prise en compte de la prime marché est importante dans la décision de l’assuré de renouveler ou non son contrat d’assurance avec son assureur actuel. La nécessitéd’un modèle de marché est établie. Le chapitre 2 répond à cette problématique en utilisant la théorie des jeux non-coopératifs pour modéliser la compétition. Dans la littérature actuelle, les modèles de compétition seréduisent toujours à une optimisation simpliste du volume de prime basée sur une vision d’un assureur contre le marché. Partant d’un modèle de marché à une période, un jeu d’assureurs est formulé, où l’existence et l’unicité de l’équilibre de Nash sont vérifiées. Les propriétés des primes d’équilibre sont étudiées pour mieux comprendre les facteurs clés d’une position dominante d’un assureur par rapport aux autres. Ensuite, l’intégration du jeu sur une période dans un cadre dynamique se fait par la répétition du jeu sur plusieurs périodes. Une approche par Monte-Carlo est utilisée pour évaluer la probabilité pour un assureur d’être ruiné, de rester leader, de disparaître du jeu par manque d’assurés en portefeuille. Ce chapitre vise à mieux comprendre la présence de cycles en assurance non-vie. Le chapitre 3 présente en profondeur le calcul effectif d’équilibre de Nash pour n joueurs sous contraintes, appelé équilibre de Nash généralisé. Il propose un panorama des méthodes d’optimisation pour la résolution des n sous-problèmes d’optimisation. Cette résolution sefait à l’aide d’une équation semi-lisse basée sur la reformulation de Karush-Kuhn-Tucker duproblème d’équilibre de Nash généralisé. Ces équations nécessitent l’utilisation du Jacobiengénéralisé pour les fonctions localement lipschitziennes intervenant dans le problème d’optimisation.Une étude de convergence et une comparaison des méthodes d’optimisation sont réalisées.Enfin, le chapitre 4 aborde le calcul de la probabilité de ruine, un autre thème fondamentalde l’assurance non-vie. Dans ce chapitre, un modèle de risque avec dépendance entre lesmontants ou les temps d’attente de sinistre est étudié. De nouvelles formules asymptotiquesde la probabilité de ruine en temps infini sont obtenues dans un cadre large de modèle de risquesavec dépendance entre sinistres. De plus, on obtient des formules explicites de la probabilité deruine en temps discret. Dans ce modèle discret, l’analyse structure de dépendance permet dequantifier l’écart maximal sur les fonctions de répartition jointe des montants entre la versioncontinue et la version discrète. / In non-life actuarial mathematics, different quantitative aspects of insurance activity are studied.This thesis aims at explaining interactions among economic agents, namely the insured,the insurer and the market, under different perspectives. Chapter 1 emphasizes how essentialthe market premium is in the customer decision to lapse or to renew with the same insurer.The relevance of a market model is established.In chapter 2, we address this issue by using noncooperative game theory to model competition.In the current literature, most competition models are reduced to an optimisationof premium volume based on the simplistic picture of an insurer against the market. Startingwith a one-period model, a game of insurers is formulated, where the existence and uniquenessof a Nash equilibrium are verified. The properties of premium equilibria are examinedto better understand the key factors of leadership positions over other insurers. Then, thederivation of a dynamic framework from the one-period game is done by repeating of theone-shot game over several periods. A Monte-Carlo approach is used to assess the probabilityof being insolvent, staying a leader, or disappearing of the insurance game. This gives furtherinsights on the presence of non-life insurance market cycles.A survey of computational methods of a Nash equilibrium under constraints is conductedin Chapter 3. Such generalized Nash equilibrium of n players is carried out by solving asemismooth equation based on a Karush-Kuhn-Tucker reformulation of the generalized Nashequilibrium problem. Solving semismooth equations requires using the generalized Jacobianfor locally Lipschitzian function. Convergence study and method comparison are carried out.Finally, in Chapter 4, we focus on ruin probability computation, another fundemantalpoint of non-life insurance. In this chapter, a risk model with dependence among claimseverity or claim waiting times is studied. Asymptotics of infinite-time ruin probabilitiesare obtained in a wide class of risk models with dependence among claims. Furthermore,we obtain new explicit formulas for ruin probability in discrete-time. In this discrete-timeframework, dependence structure analysis allows us to quantify the maximal distance betweenjoint distribution functions of claim severity between the continuous-time and the discrete

This thesis is organized into two parts, one for my main area of research in the field of stochastic games, and the other for my contributions in the area of service systems. We first provide an abstract for my work in stochastic games. The field of stochastic games has been actively pursued over the last seven decades because of several of its important applications in oligopolistic economics. In the past, zero-sum stochastic games have been modelled and solved for Nash equilibria using the standard techniques of Markov decision processes. General-sum stochastic games on the contrary have posed difficulty as they cannot be reduced to Markov decision processes. Over the past few decades the quest for algorithms to compute Nash equilibria in general-sum stochastic games has intensified and several important algorithms such as stochastic tracing procedure [Herings and Peeters, 2004], NashQ [Hu and Wellman, 2003], FFQ [Littman, 2001], etc., and their generalised representations such as the optimization problem formulations for various reward structures [Filar and Vrieze, 1997] have been proposed. However, they suffer from either lack of generality or are intractable for even medium sized problems or both. In our venture towards algorithms for stochastic games, we start with a non-linear optimization problem and then design a simple gradient descent procedure for the same. Though this procedure gives the Nash equilibrium for a sample problem of terrain exploration, we observe that, in general, it need not be true. We characterize the necessary conditions and define KKT-N point. KKT-N points are those Karush-Kuhn-Tucker (KKT) points which corresponding to Nash equilibria. Thus, for a simple gradient based algorithm to guarantee convergence to Nash equilibrium, all KKT points of the optimization problem need to be KKT-N points, which restricts the applicability of such algorithms. We then take a step back and start looking at better characterization of those points of the optimization problem which correspond to Nash equilibria of the underlying game. As a result of this exploration, we derive two sets of necessary and sufficient conditions. The first set, KKT-SP conditions, is inspired from KKT conditions itself and is obtained by breaking down the main optimization problem into several sub-problems and then applying KKT conditions to each one of those sub-problems. The second set, SG-SP conditions, is a simplified set of conditions which characterize those Nash points more compactly. Using both KKT-SP and SG-SP conditions, we propose three algorithms, OFF-SGSP, ON-SGSP and DON-SGSP, respectively, which we show provide Nash equilibrium strategies for general-sum discounted stochastic games. Here OFF-SGSP is an off-line algorithm while ONSGSP and DON-SGSP are on-line algorithms. In particular, we believe that DON-SGSP is the first decentralized on-line algorithm for general-sum discounted stochastic games. We show that both our on-line algorithms are computationally efficient. In fact, we show that DON-SGSP is not only applicable for multi-agent scenarios but is also directly applicable for the single-agent case, i.e., MDPs (Markov Decision Processes). The second part of the thesis focuses on formulating and solving the problem of minimizing the labour-cost in service systems. We define the setting of service systems and then model the labour-cost problem as a constrained discrete parameter Markov-cost process. This Markov process is parametrized by the number of workers in various shifts and with various skill levels. With the number of workers as optimization variables, we provide a detailed formulation of a constrained optimization problem where the objective is the expected long-run averages of the single-stage labour-costs, and the main set of constraints are the expected long-run average of aggregate SLAs (Service Level Agreements). For this constrained optimization problem, we provide two stochastic optimization algorithms, SASOC-SF-N and SASOC-SF-C, which use smoothed functional approaches to estimate gradient and perform gradient descent in the aforementioned constrained optimization problem. SASOC-SF-N uses Gaussian distribution for smoothing while SASOC-SF-C uses Cauchy distribution for the same. SASOC-SF-C is the first Cauchy based smoothing algorithm which requires a fixed number (two) of simulations independent of the number of optimization variables. We show that these algorithms provide an order of magnitude better performance than existing industrial standard tool, OptQuest. We also show that SASOC-SF-C gives overall better performance.