Search

Cybersecurity is increasingly threatened by advanced and persistent attacks. As these attacks are often designed to disable a system (or a critical resource, e.g., a user account) repeatedly, it is crucial for the defender to keep updating its security measures to strike a balance between the risk of being compromised and the cost of security updates. Moreover, these decisions often need to be made with limited and delayed feedback due to the stealthy nature of advanced attacks. In addition to targeted attacks, such an optimal timing policy under incomplete information has broad applications in cybersecurity. Examples include key rotation, password change, application of patches, and virtual machine refreshing. However, rigorous studies of optimal timing are rare. Further, existing solutions typically rely on a pre-defined attack model that is known to the defender, which is often not the case in practice. In this work, we make an initial effort towards achieving optimal timing of security updates in the face of unknown stealthy attacks. We consider a variant of the influential FlipIt game model with asymmetric feedback and unknown attack time distribution, which provides a general model to consecutive security updates. The defender's problem is then modeled as a time associative bandit problem with dependent arms. We derive upper confidence bound based learning policies that achieve low regret compared with optimal periodic defense strategies that can only be derived when attack time distributions are known., Comment: 9 pages, 2 figures; accepted by the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), San Francisco, CA, USA, Feb. 2017

In this work, we aim to obtain the optimal tradeoff between the average delay and the average power consumption in a communication system. In our system, the arrivals occur at each timeslot according to a Bernoulli arrival process and are buffered at the transmitter. The transmitter determines the scheduling policy of how many packets to transmit under an average power constraint. The power is assumed to be an increasing and convex function of the number of packets transmitted in each timeslot to capture the realism in communication systems. We also consider a finite buffer and allow the scheduling decision to depend on the buffer occupancy. This problem is modelled as a Constrained Markov Decision Process (CMDP). We first prove that the optimal policy of the (Lagrangian) relaxation of the CMDP is deterministic and threshold-based. We then show that the optimal delay-power tradeoff curve is convex and piecewise linear, where each of the vertices are obtained by the optimal solution to the relaxed problem. This allows us to show the optimal policies of the CMDP are threshold-based, and hence can be implemented by a proposed efficient algorithm. The theoretical results and the algorithm are validated by Linear Programming and simulations., Comment: 30 pages, 8 figures

In modern computer systems, jobs are divided into short tasks and executed in parallel. Empirical observations in practical systems suggest that the task service times are highly random and the job service time is bottlenecked by the slowest straggling task. One common solution for straggler mitigation is to replicate a task on multiple servers and wait for one replica of the task to finish early. The delay performance of replications depends heavily on the scheduling decisions of when to replicate, which servers to replicate on, and which job to serve first. So far, little is understood on how to optimize these scheduling decisions for minimizing the delay to complete the jobs. In this paper, we present a comprehensive study on delay-optimal scheduling of replications in both centralized and distributed multi-server systems. Low-complexity scheduling policies are designed and are proven to be delay-optimal or near delay-optimal in stochastic ordering among all causal and non-preemptive policies. These theoretical results are established for general system settings and delay metrics that allow for arbitrary arrival processes, arbitrary job sizes, arbitrary due times, and heterogeneous servers with data locality constraints. Novel sample-path tools are developed to prove these results.

In this work, we investigate the design of information-update systems, where incoming update packets are forwarded to a remote destination through multiple servers (each server can be viewed as a wireless channel). One important performance metric of these systems is the age-of-information or simply age, which is defined as the time elapsed since the freshest packet at the destination was generated. Recent studies on information-update systems have shown that the age-of-information can be reduced by intelligently dropping stale packets. However, packet dropping may not be appropriate in many applications, such as news and social updates, where users are interested in not just the latest updates, but also past news. Therefore, all packets may need to be successfully delivered. In this paper, we study how to optimize age-of-information without throughput loss. We consider a general scenario where incoming update packets do not necessarily arrive in the order of their generation times. We prove that a preemptive Last Generated First Served (LGFS) policy simultaneous optimizes the age, throughput, and delay performance in infinite buffer queueing systems. We also show age-optimality for the LGFS policy for any finite queue size. These results hold for arbitrary, including non-stationary, arrival processes. To the best of our knowledge, this paper presents the first optimal result on minimizing the age-of-information in communication networks with an external arrival process of information update packets., Comment: 8 pages, 4 figures

There have been recent attempts to develop scheduling schemes for downlink transmission in a single cell of a multi-channel (e.g., OFDM-based) cellular network. These works have been quite promising in that they have developed low-complexity index scheduling policies that are delay-optimal (in a large deviation rate-function sense). However, these policies require that the channel is ON or OFF in each time-slot with a fixed probability (i.e., there is no memory in the system), while the reality is that due to channel fading and doppler shift, channels are often time-correlated in these cellular systems. Thus, an important open question is whether one can find simple index scheduling policies that are delay-optimal even when the channels are time-correlated. In this paper, we attempt to answer this question for time-correlated ON/OFF channels. In particular, we show that the class of oldest packets first (OPF) policies that give a higher priority to packets with a large delay is delay rate-function optimal under two conditions: 1) The channel is non-negatively correlated, and 2) The distribution of the OFF period is geometric. We use simulations to further elucidate the theoretical results., Comment: 15 pages, 5 figures

In this work, we study how to optimally manage the freshness of information updates sent from a source node to a destination via a channel. A proper metric for data freshness at the destination is the age-of-information, or simply age, which is defined as how old the freshest received update is since the moment that this update was generated at the source node (e.g., a sensor). A reasonable update policy is the zero-wait policy, i.e., the source node submits a fresh update once the previous update is delivered and the channel becomes free, which achieves the maximum throughput and the minimum delay. Surprisingly, this zero-wait policy does not always minimize the age. This counter-intuitive phenomenon motivates us to study how to optimally control information updates to keep the data fresh and to understand when the zero-wait policy is optimal. We introduce a general age penalty function to characterize the level of dissatisfaction on data staleness and formulate the average age penalty minimization problem as a constrained semi-Markov decision problem (SMDP) with an uncountable state space. We develop efficient algorithms to find the optimal update policy among all causal policies, and establish sufficient and necessary conditions for the optimality of the zero-wait policy. Our investigation shows that the zero-wait policy is far from the optimum if (i) the age penalty function grows quickly with respect to the age, (ii) the packet transmission times over the channel are positively correlated over time, or (iii) the packet transmission times are highly random (e.g., following a heavy-tail distribution).