This work presents an axiomatization for entropy based on an extension of concavity called core-concavity. We show that core-concavity characterizes the largest class of functions for which the data-processing inequality holds, under the assumption that conditional entropy is defined as a generalized average. Also, under the same assumption, we show that data-processing and “conditioning reduces entropy” properties are equivalent. We prove several properties of core-concave functions, including generalization of perfect secrecy and of Fano's inequality. We also show that definitions of conditional entropy based on worst-case can be retrieved as limit cases of generalized averages. A connection between statistical decision making and this axiomatic approach is also presented.

This work explores the problem of designing a channel that leaks the least amount of information while respecting a set of operational constraints. This paper focuses on deterministic channels and deterministic solutions. This setting is relevant because most programs and many channel design problems are naturally modelled by deterministic channels. Moreover, the setting is also relevant when considering an attacker who can observe many outputs of an arbitrary channel while the secret input stays the same: when the number of observations is arbitrarily large, the channel of minimal leakage is deterministic. The deterministic channel design problem has different solutions depending on which leakage measure is chosen. The problem is shown to be NP-hard in general. However, for a particular class of constraints, called k-complete hypergraph constraints, a greedy algorithm is shown to provide the optimal solution for a wide class of leakage measures.

This work introduces a new preorder over channels that is monotonic with Shannon's mutual information for all distributions over the input alphabet. Moreover, this monotonicity also holds when substituting mutual information for quantities relative to Arimoto-Rényi conditional entropies and guessing entropy. Several results connecting this new preorder with others from the literature are proven. This work also discusses an extension of Shannon ordering based on this new preorder, and establishes that channels ordered this way are also ordered with regards to both Shannon and min-capacity.

We introduce a novel generalization of entropy and conditional entropy from which most definitions from the literature can be derived as particular cases. Within this general framework, we investigate the problem of designing countermeasures for information leakage. In particular, we seek metric-invariant solutions, i.e., they are robust against the choice of entropy for quantifying the leakage. The problem can be modeled as an information channel from the system to an adversary, and the countermeasures can be seen as modifying this channel in order to minimize the amount of information that the outputs reveal about the inputs. Our main result is to fully solve the problem under the highly symmetrical design constraint that the number of inputs that can produce the same output is capped. Our proof is constructive and the optimal channels and the minimum leakage are derived in closed form.

In this paper we describe symbolic side-channel analysis techniques for detecting and quantifying information leakage, given in terms of Shannon and min-entropy. Measuring the precise leakage is challenging due to the randomness and noise often present in program executions and side-channel observations. We account for this noise by introducing additional (symbolic) program inputs which are interpreted probabilistically, using symbolic execution with parametrized model counting. We also explore a sampling approach for increased scalability. In contrast to typical Monte Carlo techniques, our approach works by sampling symbolic paths, representing multiple concrete paths, and uses pruning to accelerate computation and guarantee convergence to the optimal results. A key novelty of our approach is to provide bounds on the leakage that are provably under- and over-approximating the exact leakage. We implemented the techniques in the Symbolic PathFinder tool and demonstrate them on Java programs.

We consider a setting where a system has to interact, and hence create distinct outputs (observables), but subject to such operational constraints wants to minimize the leakage that such observables reveal about its secret input. It has been previously demonstrated that under some (highly symmetrical) constraints on the observables, it is possible to design systems that are universally optimal in the sense of leaking minimal information no matter how information is measured.,,In this work we make several contribution to this field. On universal (i.e., measure-invariant) optimality, we show its limitations through a counterexample where symmetry constraints are broken. Nevertheless, we also show two new universal optimality results: the first is in the presence of "graph like" constraints (that may lack symmetry). The second is universal optimality in the case of uncertainty about the prior. Furthermore, we prove that a generic class of leakage optimisation problems are convex problem, from which we derive that KKT conditions are necessary and sufficient for optimality. We demonstrate the practical value of the theory in the form of an application to timing attacks countermeasures.

Perfect secrecy describes cases where an adversary cannot learn anything about the secret beyond its prior distribution. A classical result by Shannon shows that a necessary condition for perfect secrecy is that the adversary should not be able to eliminate any of the possible secrets. In this paper we answer the following fundamental question: What is the lowest leakage of information that can be achieved when some of the secrets have to be eliminated? We address this question by deriving the minimum leakage in closed-form, and explicitly providing "universally optimal" randomized strategies, in the sense that they guarantee the minimum leakage irrespective of the measure of entropy used to quantify the leakage. We then introduce a generalization of Rényi family of asymmetric measures of leakage which generalizes the g-leakage and show that a slight modification of our strategies are optimal with respect to an important class of such measures. Subsequently, we show that our schemes constitute the Nash Equilibria of closely related two-person zero sum games. This game perspective provides implicit solutions for a wider set of structural constraints and asymmetric entropies. Finally we demonstrate how this work can also be seen as designing a universally optimal channel given a specified prior.

Studies on the propagation of malware in mobile networks have revealed that the spread of malware can be highly inhomogeneous. Platform diversity, contact list utilization by the malware, clustering in the network structure, etc., can also lead to differing spreading rates. In this paper, a general formal framework is proposed for leveraging such heterogeneity to derive optimal patching policies that attain the minimum aggregate cost due to the spread of malware and the surcharge of patching. Using Pontryagin's Maximum Principle for a stratified epidemic model, it is analytically proven that in the mean-field deterministic regime, optimal patch disseminations are simple single-threshold policies. These policies are amenable to implementation and can serve as benchmarks for policies that have less knowledge of the network. Through numerical simulations, the behavior of optimal patching policies is investigated in sample topologies, and their advantages are demonstrated.

Choosing a hard-to-guess secret is a prerequisite in many security applications. Whether it is a password for user authentication or a secret key for a cryptographic primitive, picking it requires the user to trade-off usability costs with resistance against an adversary: a simple password is easier to remember but is also easier to guess, likewise, a shorter cryptographic key may require fewer computational and storage resources but it is also easier to attack. A fundamental question is how one can optimally resolve this trade-off. A big challenge is the fact that an adversary can also utilize the knowledge of such usability vs. security trade-offs to strengthen its attack. In this paper, we propose a game-theoretic framework for analyzing the optimal trade-offs in the face of strategic adversaries. We consider two types of adversaries: those limited in their number of tries, and those that are ruled by the cost of making individual guesses. For each type, we derive the mutually-optimal decisions as Nash Equilibria, the strategically pessimistic decisions as maximin, and optimal commitments as Strong Stackelberg Equilibria of the game. We establish that when the adversaries are faced with a capped number of guesses, the user's optimal trade-off is a uniform randomization over a subset of the secret domain. On the other hand, when the attacker strategy is ruled by the cost of making individual guesses, Nash Equilibria may completely fail to provide the user with any level of security, signifying the crucial role of credible commitment for such cases. We illustrate our results using numerical examples based on real-world samples and discuss some policy implications of our work.

Regulating the ISPs to adopt more security measures has been proposed as an effective method in mitigating the threats of attacks in the Internet. However, economic incentives of the ISPs and the network effects of security measures can lead to an under-investment in their adoption. We study the potential gains in a network's social utility when a regulator implements a monitoring and penalizing mechanism on the outbound threat activities of autonomous systems (ASes). We then show how freeriding can render regulations futile if the subset of ASes under the regulator's authority is smaller than a threshold. Finally, we show how heterogeneity of the ASes affect the responses of the ISPs and discuss how the regulator can leverage such information to improve the overall effectiveness of different security policies.

The security of the Internet can be significantly improved if Internet Service Providers adopt firewalls to monitor traffic entering and leaving access networks. But this process suffers due to `free-riding', and hence, regulatory requirements and `seeding' strategies are required to influence the adoption process. In this paper, we analytically derive the equilibrium adoption levels and relate them to the initial seeding and mandating condition, and explore the issues of incentive alignment across users, firewall developers, and regulators. We define different notions of optimality and analytically develop optimum seeding and mandating policies.

In this work, we investigate the use of epidemic routing in energy constrained Delay Tolerant Networks (DTNs). In DTNs, connected paths between source and destination rarely materialize due to the mobility and sparse density of nodes. Epidemic routing is well-suited for these environments due to its simplicity and fully distributed implementation. In epidemic routing, messages are relayed by intermediate nodes at contact opportunities, i.e., when pairs of nodes come within transmission range. Each node needs to decide whether to forward its message upon contact with a new node based on its residual energy level and the age of that message.

Given the flexibility that software-based operation provides, it is unreasonable to expect that new malware will demonstrate a fixed behavior over time. Instead, malware can dynamically change the parameters of their infective hosts in response to the dynamics of the network, in order to maximize their overall damage. However, in return, the network can also dynamically change its counter-measure parameters in order to attain a robust defense against the spread of malware while minimally affecting the normal performance of the network. The infinite dimension of freedom introduced by variation over time and antagonistic and strategic optimization of malware and network against each other demand new attempts for modeling and analysis. We develop a zero-sum dynamic game model and investigate the structural properties of the saddle-point strategies. We specifically show that saddle-point strategies are simple threshold-based policies and hence, a robust dynamic defense is practicable.

The security threat posed by malware in mobile wireless networks can be countered through immunization using security patches. The distribution of patches, however, consumes bandwidth that is scarce in wireless networks, and must, there fore, be judiciously controlled in order to attain desired tradeoffs between security risks and bandwidth consumption. We consider both nonreplicative and replicative dissemination of patches: a predetermined set of dispatcher nodes distribute the patches in the former, whereas the dispatcher set continually grows in the latter as the nodes that receive the patch become dispatchers themselves. In each case, the desired tradeoffs can be attained by activating at any given time only fractions of dispatchers and selecting their packet transmission rates. We formulate the afore said tradeoffs as optimal control problems that seek to minimize the aggregate network costs that depend on security risks and the overall extra bandwidth used in the network for dissemination of the security patches. We prove that the dynamic control strategies have simple structures: when the cost function associated with the bandwidth consumed in patching is concave, the control strategies are bang-bang with at most one jump from the maximum to the minimum value. When the cost function is strictly convex, the aforesaid transition is strict but continuous. We compare the efficacy of different dispatch models and also those of the optimum dynamic and static controls using numerical computations.

Malware attacks constitute a serious security risk that threatens to slow down the large-scale proliferation of wireless applications. As a first step toward thwarting this security threat, we seek to quantify the maximum damage inflicted on the system due to such outbreaks and identify the most vicious attacks. We represent the propagation of malware in a battery-constrained mobile wireless network by an epidemic model in which the worm can dynamically control the rate at which it kills the infected node and also the transmission ranges and/or the media scanning rates. At each moment of time, the worm at each node faces the following tradeoffs: 1) using larger transmission ranges and media scanning rates to accelerate its spread at the cost of exhausting the battery and thereby reducing the overall infection propagation rate in the long run; or 2) killing the node to inflict a large cost on the network, however at the expense of losing the chance of infecting more susceptible nodes at later times. We mathematically formulate the decision problems and utilize Pontryagin Maximum Principle from optimal control theory to quantify the damage that the malware can inflict on the network by deploying optimum decision rules. Next, we establish structural properties of the optimal strategy of the attacker over time. Specifically, we prove that it is optimal for the attacker to defer killing of the infective nodes in the propagation phase until reaching a certain time and then start the slaughter with maximum effort. We also show that in the optimal attack policy, the battery resources are used according to a decreasing function of time, i.e., most aggressively during the initial phase of the outbreak. Finally, our numerical investigations reveal a framework for identifying intelligent defense strategies that can limit the damage by appropriately selecting network parameters.

Epidemic models based on nonlinear differential equations have been extensively applied in a variety of systems as diverse as infectious outbreaks, marketing, diffusion of beliefs, etc., to the dissemination of messages in MANET or p2p networks. Control of such systems is achieved at the cost of consuming the resources. We construct a unifying framework that models the interactions of the control and the elements in systems with epidemic behavior. Specifically, we consider non-replicative and replicative dissemination of messages in a network: a pre-determined set of disseminators distribute the messages in the former, whereas the disseminator set continually grows in the latter as the nodes that receive the patch become disseminators themselves. In both cases, the desired trade-offs can be attained by activating at any given time only fractions of disseminators and selecting their dissemination rates. We formulate the above trade-offs as optimal control problems that seek to minimize a general aggregate cost function which cogently depends on both the states and the overall resource consumption. We prove that the dynamic control strategies have simple structures: (1) it is never optimal to activate a partial fraction of the disseminators (all or none) (2) when the resource consumption cost is concave, the distribution rate of the activated nodes are bang-bang with at most one jump from the maximum to the minimum value. When the resource consumption cost is convex, the above transition is strict but continuous. We compare the efficacy and robustness of different dispatch models and also those of the optimum dynamic and static controls using numerical computations.

Given the flexibility that software-based operation provides, it is unreasonable to expect that new malware will demonstrate a fixed behavior over time. Instead, malware can dynamically change the parameters of their infective hosts in response to the dynamics of the network, in order to maximize their overall damage. However, in return, the network can also dynamically change its counter-measure parameters in order to attain a robust defense against the spread of malware while minimally affecting the normal performance of the network. The infinite dimension of freedom introduced by variation over time and antagonistic and strategic optimization of malware and network against each other demand new attempts for modeling and analysis. We develop a zero-sum dynamic game model and investigate the structural properties of the saddle-point strategies. We specifically show that saddle-point strategies are simple threshold-based policies and hence, a robust dynamic defense is practicable.

Malware attacks constitute a serious security risk that threatens to slow down the large scale proliferation of wireless applications. As a first step towards thwarting this security threat, we seek to quantify the maximum damage inflicted on the system owing to such outbreaks and identify the most vicious attacks. We represent the propagation of malware in a battery-constrained mobile wireless network by an epidemic model in which the worm can dynamically control the rate at which it kills the infected node and also the transmission range and/or the media scanning rate. At each moment of time, the worm at each node faces the following trade-offs: (i) using larger transmission range and media scanning rate to accelerate its spread at the cost of exhausting the battery and thereby reducing the overall infection propagation rate in the long run or (ii) killing the node to inflict a large cost on the network, however at the expense of loosing the chance of infecting more susceptible nodes at later times. We mathematically formulate the decision problems and utilize Pontryagin Maximum Principle from optimal control theory to quantify the damage that the malware can inflict on the network by deploying optimum decision rules. Next, we establish structural properties of the optimal strategy of the attacker over time. Specifically, we prove that it is optimal for the attacker to defer killing of the infective nodes in the propagation phase until reaching a certain time and then start the slaughter with maximum effort. We also show that in the optimal attack policy, the battery resources are used according to a decreasing function of time, i.e., mostly during the initial phase of the outbreak. Finally, our numerical investigations reveal a framework for identifying intelligent defense strategies that can limit the damage by appropriately selecting network parameters.

Reliable security measures against outbreaks of malware is imperative to enable large scale proliferation of wireless technologies. Immunization and healing of the nodes through dissemination of security patches can counter the spread of a malware upon an epidemic outbreak. The distribution of patches however burdens the bandwidth which is scarce in wireless networks. The trade-offs between security risks and resource consumption can be attained by activating at any given time only fractions of dispatchers and dynamically selecting their packet transmission rates. We formulate the above trade-offs as an optimal control problem that seek to minimize the aggregate network costs that depend on security risks and resource consumed by the countermeasures. Using Pontryagin's maximum principle, we prove that the dynamic control strategies have simple structures. When the resource consumption cost is concave, optimal strategy is to use maximum resources for distribution of patches until a threshold time, upon which, the patching should halt. When the resource consumption cost is convex, the above transition is strict but continuous.

We consider a wireless network consisting of two classes of potentially mobile users: primary users and secondary users. Primary users license frequency channels and transmit in their respective bands as required. Secondary users resort to unlicensed access of channels that are not used by their primary users. Primaries impose access fees on the secondaries which depend on access durations and may be different for different primary channels and different available communication rates in the channels. The available rates to the secondaries change with time depending on the usage status of the primaries and the random access quality of channels. Secondary users seek to minimize their total access cost subject to stabilizing their queues whenever possible. Our first contribution is to present a dynamic link scheduling policy that attains this objective. The computation time of this policy, however, increases exponentially with the size of the network. We next present an approximate scheduling scheme based on graph partitioning that is distributed and attains arbitrary trade-offs between aggregate access cost and computation times of the schedules, irrespective of the size of the network. Our performance guarantees hold for general arrival and primary usage statistics and multihop networks. Each secondary user is, however, primarily interested in minimizing the cost it incurs, rather than in minimizing the aggregate cost. Thus, it will schedule its transmissions so as to minimize the aggregate cost only if it perceives that the aggregate cost is shared among the users as per a fair cost sharing scheme. Using concepts from cooperative game theory, we develop a rational basis for sharing the aggregate cost among secondary sessions and present a cost sharing mechanism that conforms to the above basis.