Search

Despite their frequency, denial-of-service (DoS\blfootnote{Denial of Service (DoS), Distributed Denial of Service (DDoS), Probabilistic Packet Marking (PPM), coupon collector's problem (CCP)}) and distributed-denial-of-service (DDoS) attacks are difficult to prevent and trace, thus posing a constant threat. One of the main defense techniques is to identify the source of attack by reconstructing the attack graph, and then filter the messages arriving from this source. One of the most common methods for reconstructing the attack graph is Probabilistic Packet Marking (PPM). We focus on edge-sampling, which is the most common method. Here, we study the time, in terms of the number of packets, the victim needs to reconstruct the attack graph when there is a single attacker. This random variable plays an important role in the reconstruction algorithm. Our main result is a determination of the asymptotic distribution and expected value of this time. The process of reconstructing the attack graph is analogous to a version of the well-known coupon collector's problem (with coupons having distinct probabilities). Thus, the results may be used in other applications of this problem., Comment: 31 pages, 5 figures, 1 table

DoS and DDoS attacks are widely used and pose a constant threat. Here we explore Probability Packet Marking (PPM), one of the important methods for reconstructing the attack-graph and detect the attackers. We present two algorithms. Differently from others, their stopping time is not fixed a priori. It rather depends on the actual distance of the attacker from the victim. Our first algorithm returns the graph at the earliest feasible time, and turns out to guarantee high success probability. The second algorithm enables attaining any predetermined success probability at the expense of a longer runtime. We study the performance of the two algorithms theoretically, and compare them to other algorithms by simulation. Finally, we consider the order in which the marks corresponding to the various edges of the attack graph are obtained by the victim. We show that, although edges closer to the victim tend to be discovered earlier in the process than farther edges, the differences are much smaller than previously thought., Comment: 30 pages, 4 figures, 4 tables

User engagement is crucial to the long-term success of a mobile app. Several metrics, such as dwell time, have been used for measuring user engagement. However, how to effectively predict user engagement in the context of mobile apps is still an open research question. For example, do the mobile usage contexts (e.g.,~time of day) in which users access mobile apps impact their dwell time? Answers to such questions could help mobile operating system and publishers to optimize advertising and service placement. In this paper, we first conduct an empirical study for assessing how user characteristics, temporal features, and the short/long-term contexts contribute to gains in predicting users' app dwell time on the population level. The comprehensive analysis is conducted on large app usage logs collected through a mobile advertising company. The dataset covers more than 12K anonymous users and 1.3 million log events. Based on the analysis, we further investigate a novel mobile app engagement prediction problem -- can we predict simultaneously what app the user will use next and how long he/she will stay on that app? We propose several strategies for this joint prediction problem and demonstrate that our model can improve the performance significantly when compared with the state-of-the-art baselines. Our work can help mobile system developers in designing a better and more engagement-aware mobile app user experience., Comment: 38 pages, to appear in ACM Transactions on Information Systems 2021

A natural problem in the context of the coupon collector's problem is the behavior of the maximum of independent geometrically distributed random variables (with distinct parameters). This question has been addressed by Brennan et al. (British J. of Math. & CS. 8 (2015), 330-336). Here we provide explicit asymptotic expressions for the moments of that maximum, as well as of the maximum of exponential random variables with corresponding parameters. We also deal with the probability of each of the variables being the maximal one. The calculations lead to expressions involving Hurwitz's zeta function at certain special points. We find here explicitly the values of the function at these points. Also, the distribution function of the maximum we deal with is closely related to the generating function of the partition function. Thus, our results (and proofs) rely on classical results pertaining to the partition function., Comment: 32 pages, 2 tables

One of the most studied models of SAT is random SAT. In this model, instances are composed from clauses chosen uniformly randomly and independently of each other. This model may be unsatisfactory in that it fails to describe various features of SAT instances, arising in real-world applications. Various modifications have been suggested to define models of industrial SAT. Here, we focus mainly on the aspect of community structure. Namely, here the set of variables consists of a number of disjoint communities, and clauses tend to consist of variables from the same community. Thus, we suggest a model of random industrial SAT, in which the central generalization with respect to random SAT is the additional community structure. There has been a lot of work on the satisfiability threshold of random $k$-SAT, starting with the calculation of the threshold of $2$-SAT, up to the recent result that the threshold exists for sufficiently large $k$. In this paper, we endeavor to study the satisfiability threshold for the proposed model of random industrial SAT. Our main result is that the threshold in this model tends to be smaller than its counterpart for random SAT. Moreover, under some conditions, this threshold even vanishes., Comment: 32 pages

We present a theoretical study of the impact of oxygen diffusion in oxide crystals on metal dopants ionic state and the conduction type under dynamic changes. The slow changes under thermal equilibrium are provided in a companion, Part I paper. Oxygen vacancy formation acting as a shallow, double-electronic donor, is assumed to result from the crystal exposure to a low ambient oxygen pressure. Critical transitions from n- to a p-type at an oxygen partial pressure Pi, and in ionization state of the metal dopant at an oxygen partial pressure PM, are usually not simultaneous, and depend on the different reaction constants. Invoking ambipolar diffusion for all participating species, it is shown that oxygen vacancy diffusion exhibits well defined characteristics in specific regions of the vacancy concentration related to the said critical pressures. Particularly, the oxygen chemical diffusivity is practically constant between Pi and PM, and increases sharply for pressures P << Pi,PM and P >> P,PM. Prominent reaction fronts occur under specific conditions in the two latter regions., Comment: 18 pages, 4 figures

We present a theoretical study of the impact of oxygen diffusion in oxide crystals on metal dopants ionic state and the conduction type under thermal equilibrium. Oxygen vacancy formation acting as a shallow, double-electronic donor is assumed to result from the crystal exposure to a low ambient oxygen pressure. It is shown, that critical transitions from n- to a p-type at an oxygen partial pressure Pi, and in ionization state of the metal dopant at an oxygen partial pressure PM, are usually not simultaneous, and depend on the different reaction constants. Experimental study of the different species concentrations at thermodynamic equilibrium as functions of pressure and temperature should allow assessment of various reversible reaction constants controlling the process. In the Part II companion paper, the kinetic (diffusion) characteristics are considered in detail., Comment: 11 pages, 2 figures