Researcher profile

Suman Sourav

Suman Sourav contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

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.

Published work

4 published item(s)

preprint2022arXiv

Distort to Detect, not Affect: Detecting Stealthy Sensor Attacks with Micro-distortion

In this paper, we propose an effective and easily deployable approach to detect the presence of stealthy sensor attacks in industrial control systems, where (legacy) control devices critically rely on accurate (and usually non-encrypted) sensor readings. Specifically, we focus on stealthy attacks that crash a sensor and then immediately impersonate that sensor by sending out fake readings. We consider attackers who aim to stay hidden in the system for a prolonged period. To detect such attacks, our approach relies on continuous injection of "micro distortion" to the original sensor's readings. In particular, the injected distortion should be kept strictly within a small magnitude (e.g., $0.5\%$ of the possible operating value range), to ensure it does not affect the normal functioning of the ICS. Our approach uses a pre-shared secret sequence between a sensor and the defender to generate the micro-distortions. One key challenge is that the micro-distortions injected are often much lower than the sensor's actual readings, hence can be easily overwhelmed by the latter. To overcome this, we leverage the observation that sensor readings in many ICS (and power grid in particular) often change gradually in a significant fraction of time (i.e., with small difference between consecutive time slots). We devise a simple yet effective algorithm that can detect stealthy attackers in a highly accurate and fast (i.e., using less than 100 samples) manner. We demonstrate the effectiveness of our defense using real-world sensor reading traces from two different smart grid systems.

preprint2021arXiv

Distributed Graph Realizations

We study graph realization problems from a distributed perspective and we study it in the node capacitated clique (NCC) model of distributed computing, recently introduced for representing peer-to-peer networks. We focus on two central variants, degree-sequence realization and minimum threshold-connectivity realization both of which result in overlay network realizations. Overlay network realizations can be either explicit or implicit. Explicit realizations require both endpoints of any edge in the realized graph to be aware of the edge. In implicit realizations, on the other hand, at least one endpoint of each edge of the realized graph needs to be aware of the edge. The main realization algorithms we present are the following. 1. An $\tilde{O}(\min\{\sqrt{m},Δ\})$ time algorithm for implicit realization of a degree sequence. Here, $Δ= \max_v d(v)$ is the maximum degree and $m = (1/2) \sum_v d(v)$ is the number of edges in the final realization. An $\tilde{O}(Δ)$ time algorithm for an explicit realization of a degree sequence. We first compute an implicit realization and then transform it into an explicit one in $\tilde{O}(Δ)$ additional rounds. 2. An $\tilde{O}(Δ)$ time algorithm for the threshold connectivity problem that obtains an explicit solution and an improved $\tilde{O}(1)$ algorithm for implicit realization when all nodes know each other's IDs. These algorithms are 2-approximations w.r.t. the number of edges. We complement our upper bounds with lower bounds to show that the above algorithms are tight up to factors of $\log n$. Additionally, we provide algorithms for realizing trees and an $\tilde{O}(1)$ round algorithm for approximate degree sequence realization.

preprint2020arXiv

Guarding a Polygon Without Losing Touch

We study the classical Art Gallery Problem first proposed by Klee in 1973 from a mobile multi-agents perspective. Specifically, we require an optimally small number of agents (also called guards) to navigate and position themselves in the interior of an unknown simple polygon with $n$ vertices such that the collective view of all the agents covers the polygon. We consider the visibly connected setting wherein agents must remain connected through line of sight links -- a requirement particularly relevant to multi-agent systems. We first provide a centralized algorithm for the visibly connected setting that runs in time $O(n)$, which is of course optimal. We then provide algorithms for two different distributed settings. In the first setting, agents can only perceive relative proximity (i.e., can tell which of a pair of objects is closer) whereas they can perceive exact distances in the second setting. Our distributed algorithms work despite agents having no prior knowledge of the polygon. Furthermore, we provide lower bounds to show that our distributed algorithms are near-optimal. Our visibly connected guarding ensures that (i) the guards form a connected network and (ii) the polygon is fully guarded. Consequently, this guarding provides the distributed infrastructure to execute any geometric algorithm for this polygon.

preprint2020arXiv

Latency, Capacity, and Distributed MST

We study the cost of distributed MST construction in the setting where each edge has a latency and a capacity, along with the weight. Edge latencies capture the delay on the links of the communication network, while capacity captures their throughput (in this case, the rate at which messages can be sent). Depending on how the edge latencies relate to the edge weights, we provide several tight bounds on the time and messages required to construct an MST. When edge weights exactly correspond with the latencies, we show that, perhaps interestingly, the bottleneck parameter in determining the running time of an algorithm is the total weight $W$ of the MST (rather than the total number of nodes $n$, as in the standard CONGEST model). That is, we show a tight bound of $\tildeΘ(D + \sqrt{W/c})$ rounds, where $D$ refers to the latency diameter of the graph, $W$ refers to the total weight of the constructed MST and edges have capacity $c$. The proposed algorithm sends $\tilde{O}(m+W)$ messages, where $m$, the total number of edges in the network graph under consideration, is a known lower bound on message complexity for MST construction. We also show that $Ω(W)$ is a lower bound for fast MST constructions. When the edge latencies and the corresponding edge weights are unrelated, and either can take arbitrary values, we show that (unlike the sub-linear time algorithms in the standard CONGEST model, on small diameter graphs), the best time complexity that can be achieved is $\tildeΘ(D+n/c)$. However, if we restrict all edges to have equal latency $\ell$ and capacity $c$ while having possibly different weights (weights could deviate arbitrarily from $\ell$), we give an algorithm that constructs an MST in $\tilde{O}(D + \sqrt{n\ell/c})$ time. In each case, we provide nearly matching upper and lower bounds.