# Negar Kiyavash

## Contact Details

NameNegar Kiyavash |
||

Affiliation |
||

Location |
||

## Pubs By Year |
||

## Pub CategoriesComputer Science - Information Theory (16) Mathematics - Information Theory (16) Computer Science - Cryptography and Security (9) Computer Science - Learning (9) Statistics - Machine Learning (7) Computer Science - Artificial Intelligence (5) Computer Science - Discrete Mathematics (4) Mathematics - Combinatorics (2) Mathematics - Optimization and Control (1) Computer Science - Multimedia (1) Mathematics - Number Theory (1) Statistics - Methodology (1) Computer Science - Operating Systems (1) Computer Science - Networking and Internet Architecture (1) |

## Publications Authored By Negar Kiyavash

We study causal inference in a multi-environment setting, in which the functional relations for producing the variables from their direct causes remain the same across environments, while the distribution of exogenous noises may vary. We introduce the idea of using the invariance of the functional relations of the variables to their causes across a set of environments. We define a notion of completeness for a causal inference algorithm in this setting and prove the existence of such algorithm by proposing the baseline algorithm. Read More

In real-time embedded systems (RTS), failures due to security breaches can cause serious damage to the system, the environment and/or injury to humans. Therefore, it is very important to understand the potential threats and attacks against these systems. In this paper we present a novel reconnaissance attack that extracts the exact schedule of real-time systems designed using fixed priority scheduling algorithms. Read More

Measuring the dependencies among the variables of a network is of great interest to many disciplines. This paper studies the limitations of the existing dependencies measures such as their shortcomings in detecting direct influences or their lack of ability for group selection in order to have effective interventions and introduces a new statistical influence measure to overcome them. This measure is inspired by Dobrushin's coefficients and has been developed based on the paradigm that the conditional distribution of the variable of interest given all the direct causes will not change by intervening on other variables in the system. Read More

We study the problem of causal structure learning over a set of random variables when the experimenter is allowed to perform at most $M$ experiments in a non-adaptive manner. We consider the optimal learning strategy in terms of minimizing the portions of the structure that remains unknown given the limited number of experiments in both Bayesian and minimax setting. We characterize the theoretical optimal solution and propose an algorithm, which designs the experiments efficiently in terms of time complexity. Read More

We study the problem of learning the dependency graph between random processes in a vector auto regressive (VAR) model from samples when a subset of the variables are latent. We show that the dependencies among the observed processes can be identified successfully under some conditions on the VAR model. Moreover, we can recover the length of all directed paths between any two observed processes which pass through latent part. Read More

Interaction information is one of the multivariate generalizations of mutual information, which expresses the amount information shared among a set of variables, beyond the information, which is shared in any proper subset of those variables. Unlike (conditional) mutual information, which is always non-negative, interaction information can be negative. We utilize this property to find the direction of causal influences among variables in a triangle topology under some mild assumptions. Read More

We study a covert queueing channel between two users sharing a round robin scheduler. Such a covert channel can arise when users share a resource such as a computer processor or a router arbitrated by a round robin policy. We present an information-theoretic framework to model and derive the maximum reliable data transmission rate, i. Read More

We propose an approach for learning the causal structure in stochastic dynamical systems with a $1$-step functional dependency in the presence of latent variables. We propose an information-theoretic approach that allows us to recover the causal relations among the observed variables as long as the latent variables evolve without exogenous noise. We further propose an efficient learning method based on linear regression for the special sub-case when the dynamics are restricted to be linear. Read More

This paper proposes a novel, non-linear collusion attack on digital fingerprinting systems. The attack is proposed for fingerprinting systems with finite alphabet but can be extended to continuous alphabet. We analyze the error probability of the attack for some classes of proposed random and deterministic schemes and obtain a bound on the number of colluders necessary to correctly estimate the host signal. Read More

We consider the problem of performing community detection on a network, while maintaining privacy, assuming that the adversary has access to an auxiliary correlated network. We ask the question "Does there exist a regime where the network cannot be deanonymized perfectly, yet the community structure could be learned?." To answer this question, we derive information theoretic converses for the perfect deanonymization problem using the Stochastic Block Model and edge sub-sampling. Read More

Learning the influence structure of multiple time series data is of great interest to many disciplines. This paper studies the problem of recovering the causal structure in network of multivariate linear Hawkes processes. In such processes, the occurrence of an event in one process affects the probability of occurrence of new events in some other processes. Read More

We consider the problem of perfectly recovering the vertex correspondence between two correlated Erd\H{o}s-R\'enyi (ER) graphs. For a pair of correlated graphs on the same vertex set, the correspondence between the vertices can be obscured by randomly permuting the vertex labels of one of the graphs. In some cases, the structural information in the graphs allow this correspondence to be recovered. Read More

This paper addresses the problem of neighborhood selection for Gaussian graphical models. We present two heuristic algorithms: a forward-backward greedy algorithm for general Gaussian graphical models based on mutual information test, and a threshold-based algorithm for walk summable Gaussian graphical models. Both algorithms are shown to be structurally consistent, and efficient. Read More

We propose algorithms to approximate directed information graphs. Directed information graphs are probabilistic graphical models that depict causal dependencies between stochastic processes in a network. The proposed algorithms identify optimal and near-optimal approximations in terms of Kullback-Leibler divergence. Read More

Many of the classic problems of coding theory are highly symmetric, which makes it easy to derive sphere-packing upper bounds and sphere-covering lower bounds on the size of codes. We discuss the generalizations of sphere-packing and sphere-covering bounds to arbitrary error models. These generalizations become especially important when the sizes of the error spheres are nonuniform. Read More

When multiple job processes are served by a single scheduler, the queueing delays of one process are often affected by the others, resulting in a timing side channel that leaks the arrival pattern of one process to the others. In this work, we study such a timing side channel between a regular user and a malicious attacker. Utilizing Shannon's mutual information as a measure of information leakage between the user and attacker, we analyze privacy-preserving behaviors of common work-conserving schedulers. Read More

Timing side channels in two-user schedulers are studied. When two users share a scheduler, one user may learn the other user's behavior from patterns of service timings. We measure the information leakage of the resulting timing side channel in schedulers serving a legitimate user and a malicious attacker, using a privacy metric defined as the Shannon equivocation of the user's job density. Read More

We consider deletion correcting codes over a q-ary alphabet. It is well known that any code capable of correcting s deletions can also correct any combination of s total insertions and deletions. To obtain asymptotic upper bounds on code size, we apply a packing argument to channels that perform different mixtures of insertions and deletions. Read More

In this work, we study information leakage in timing side channels that arise in the context of shared event schedulers. Consider two processes, one of them an innocuous process (referred to as Alice) and the other a malicious one (referred to as Bob), using a common scheduler to process their jobs. Based on when his jobs get processed, Bob wishes to learn about the pattern (size and timing) of jobs of Alice. Read More

Flow watermarks efficiently link packet flows in a network in order to thwart various attacks such as stepping stones. We study the problem of designing good flow watermarks. Earlier flow watermarking schemes mostly considered substitution errors, neglecting the effects of packet insertions and deletions that commonly happen within a network. Read More

We consider the problem of constructing deletion correcting codes over a binary alphabet and take a graph theoretic view. An $n$-bit $s$-deletion correcting code is an independent set in a particular graph. We propose constructing such a code by taking the union of many constant Hamming weight codes. Read More

Explicit non-asymptotic upper bounds on the sizes of multiple-deletion correcting codes are presented. In particular, the largest single-deletion correcting code for $q$-ary alphabet and string length $n$ is shown to be of size at most $\frac{q^n-q}{(q-1)(n-1)}$. An improved bound on the asymptotic rate function is obtained as a corollary. Read More

We propose a graphical model for representing networks of stochastic processes, the minimal generative model graph. It is based on reduced factorizations of the joint distribution over time. We show that under appropriate conditions, it is unique and consistent with another type of graphical model, the directed information graph, which is based on a generalization of Granger causality. Read More

Linking network flows is an important problem in intrusion detection as well as anonymity. Passive traffic analysis can link flows but requires long periods of observation to reduce errors. Active traffic analysis, also known as flow watermarking, allows for better precision and is more scalable. Read More

In this paper, we analyze several recent schemes for watermarking network flows that are based on splitting the flow into timing intervals. We show that this approach creates time-dependent correlations that enable an attack that combines multiple watermarked flows. Such an attack can easily be mounted in nearly all applications of network flow watermarking, both in anonymous communication and stepping stone detection. Read More

Digital fingerprinting is a framework for marking media files, such as images, music, or movies, with user-specific signatures to deter illegal distribution. Multiple users can collude to produce a forgery that can potentially overcome a fingerprinting system. This paper proposes an equiangular tight frame fingerprint design which is robust to such collusion attacks. Read More

Recent work in traffic analysis has shown that traffic patterns leaked through side channels can be used to recover important semantic information. For instance, attackers can find out which website, or which page on a website, a user is accessing simply by monitoring the packet size distribution. We show that traffic analysis is even a greater threat to privacy than previously thought by introducing a new attack that can be carried out remotely. Read More

We investigate approximating joint distributions of random processes with causal dependence tree distributions. Such distributions are particularly useful in providing parsimonious representation when there exists causal dynamics among processes. By extending the results by Chow and Liu on dependence tree approximations, we show that the best causal dependence tree approximation is the one which maximizes the sum of directed informations on its edges, where best is defined in terms of minimizing the KL-divergence between the original and the approximate distribution. Read More

In order to understand the performance of a code under maximum-likelihood (ML) decoding, it is crucial to know the minimal codewords. In the context of linear programming (LP) decoding, it turns out to be necessary to know the minimal pseudo-codewords. This paper studies the minimal codewords and minimal pseudo-codewords of some families of codes derived from projective and Euclidean planes. Read More