Researcher profile

Majid Khabbazian

Majid Khabbazian contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Distributed, Parallel, and Cluster Computing Data Structures and Algorithms Cryptography and Security Networking and Internet Architecture Computational Geometry Information Theory math.CO math.IT

Trust snapshot

Quick read

Trust 21 - Emerging

8works

0followers

8topics

4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Barometers Can Hear, and Sense Finger Taps

Most modern smartphones are equipped with a barometer to sample air pressure. Accessing these samples is deemed harmless, hence does not require any permission. In this work, we show, however, that these samples can reveal sensitive information in smartphones with ingress protection. For the first time, it is shown that barometer samples, even at a low rate of 25 Hz, can leak information about the smartphone's speaker activity. Specifically, we use these samples to detect with high accuracy (>= 95%) whether the smartphone's speaker is silent or playing a sound such as a ringtone. In addition, we use the samples to detect the activity of an external speaker. Finally, we show that low-rate barometer samples can be used to 1) detect touchscreen finger taps with 100% accuracy, and 2) gain information about the positions of finger taps.

preprint2020arXiv

The DAO Induction Attack Against the RPL-based Internet of Things

RPL is the emerging routing standard for low power and lossy networks (LLNs). LLN is a key component of the Internet of Things (IoT), hence its security is imperative for the age of IoT. In this work, we present the DAO induction attack, a novel attack against RPL. In this attack, a malicious insider or a compromised node periodically increments its DTSN number. Each such increment can trigger/induce a large number of control message transmissions in the network. We show that this degrades the network performance in terms of end-to-end latency, packet loss ratio, and power consumption. To mitigate, we propose a lightweight solution to detect the DAO induction attack. Our solution imposes nearly no overhead on IoT devices, which is important as these devices are typically constrained in terms of power, memory and processing.

preprint2016arXiv

Optimal Locally Repairable Codes with Improved Update Complexity

For a systematic erasure code, update complexity (UC) is defined as the maximum number of parity blocks needed to be changed when some information blocks are updated. Locally repairable codes (LRCs) have been recently proposed and used in real-world distributed storage systems. In this paper, update complexity for optimal LRC is studied and both lower and upper bounds on UC are established in terms of length (n), dimension (k), minimum distance (d), and locality (r) of the code, when (r+1)|n. Furthermore, a class of optimal LRCs with small UC is proposed. Our proposed LRCs could be of interest as they improve UC without sacrificing optimality of the code.

preprint2015arXiv

Multi-Version Coding

We derive a simple lower bound for the multi-version coding problem formulated in [1]. We also propose simple algorithms that almost match the lower bound derived. Another lower bound is proven for an extended version of the multi-version coding problem introduced in [2].

preprint2014arXiv

Broadcast Throughput in Radio Networks: Routing vs. Network Coding

The broadcast throughput in a network is defined as the average number of messages that can be transmitted per unit time from a given source to all other nodes when time goes to infinity. Classical broadcast algorithms treat messages as atomic tokens and route them from the source to the receivers by making intermediate nodes store and forward messages. The more recent network coding approach, in contrast, prompts intermediate nodes to mix and code together messages. It has been shown that certain wired networks have an asymptotic network coding gap, that is, they have asymptotically higher broadcast throughput when using network coding compared to routing. Whether such a gap exists for wireless networks has been an open question of great interest. We approach this question by studying the broadcast throughput of the radio network model which has been a standard mathematical model to study wireless communication. We show that there is a family of radio networks with a tight $Θ(\log \log n)$ network coding gap, that is, networks in which the asymptotic throughput achievable via routing messages is a $Θ(\log \log n)$ factor smaller than that of the optimal network coding algorithm. We also provide new tight upper and lower bounds that show that the asymptotic worst-case broadcast throughput over all networks with $n$ nodes is $Θ(1 / \log n)$ messages-per-round for both routing and network coding.

preprint2014arXiv

Randomized Broadcast in Radio Networks with Collision Detection

We present a randomized distributed algorithm that in radio networks with collision detection broadcasts a single message in $O(D + \log^6 n)$ rounds, with high probability. This time complexity is most interesting because of its optimal additive dependence on the network diameter $D$. It improves over the currently best known $O(D\log\frac{n}{D}\,+\,\log^2 n)$ algorithms, due to Czumaj and Rytter [FOCS 2003], and Kowalski and Pelc [PODC 2003]. These algorithms where designed for the model without collision detection and are optimal in that model. However, as explicitly stated by Peleg in his 2007 survey on broadcast in radio networks, it had remained an open question whether the bound can be improved with collision detection. We also study distributed algorithms for broadcasting $k$ messages from a single source to all nodes. This problem is a natural and important generalization of the single-message broadcast problem, but is in fact considerably more challenging and less understood. We show the following results: If the network topology is known to all nodes, then a $k$-message broadcast can be performed in $O(D + k\log n + \log^2 n)$ rounds, with high probability. If the topology is not known, but collision detection is available, then a $k$-message broadcast can be performed in $O(D + k\log n + \log^6 n)$ rounds, with high probability. The first bound is optimal and the second is optimal modulo the additive $O(\log^6 n)$ term.

preprint2013arXiv

A Bound on the Throughput of Radio Networks

We consider the well-studied radio network model: a synchronous model with a graph G=(V,E) with |V|=n where in each round, each node either transmits a packet, with length B=Omega(log n) bits, or listens. Each node receives a packet iff it is listening and exactly one of its neighbors is transmitting. We consider the problem of k-message broadcast, where k messages, each with Theta(B) bits, are placed in an arbitrary nodes of the graph and the goal is to deliver all messages to all the nodes. We present a simple proof showing that there exist a radio network with radius 2 where for any k, broadcasting k messages requires at least Omega(k log n) rounds. That is, in this network, regardless of the algorithm, the maximum achievable broadcast throughput is O(1/log n).

preprint2011arXiv

Bounding Interference in Wireless Ad Hoc Networks with Nodes in Random Position

The interference at a wireless node s can be modelled by the number of wireless nodes whose transmission ranges cover s. Given a set of positions for wireless nodes, the interference minimization problem is to assign a transmission radius (equivalently, a power level) to each node such that the resulting communication graph is connected, while minimizing the maximum interference. We consider the model introduced by von Rickenback et al. (2005), in which each transmission range is represented by a ball and edges in the communication graph are symmetric. The problem is NP-complete in two dimensions (Buchin 2008) and no polynomial-time approximation algorithm is known. Furthermore, even in one dimension (the highway model), the problem's complexity is unknown and the maximum interference of a set of n wireless nodes can be as high as Theta(sqrt(n)) (von Rickenback et al. 2005). In this paper we show how to solve the problem efficiently in settings typical for wireless ad hoc networks. In particular, we show that if node positions are represented by a set P of n points selected uniformly and independently at random over a d-dimensional rectangular region, for any fixed d, then the topology given by the closure of the Euclidean minimum spanning tree of P has maximum interference O(log n) with high probability. We extend this bound to a general class of communication graphs over a broad set of probability distributions. Next we present a local algorithm that constructs a graph from this class; this is the first local algorithm to provide an upper bound on the expected maximum interference. Finally, we discuss an empirical evaluation of our algorithm with a suite of simulation results.