Abstract

In a distributed network, we consider two special nodes called the sender S and the receiver R that are connected by n node-disjoint (except for S and R) bi-directional wires. Out of these n wires, the adversary can control at most t wires (of its choice) in Byzantine fashion. In this setting, our goal is to design a message transmission protocol Π that assures the following two conditions hold: (1) by the end of the protocol Π, R gets the correct message m transmitted by S without any error (perfect reliability), and (2) the adversary learns no information aboutm, whatsoever, in information theoretic sense (perfect secrecy). Protocols that satisfy these two conditions are known as the Perfectly Secure Message Transmission (PSMT) protocols.

Abstract

In a synchronous distributed network of n nodes, the goal of a Secure Message Transmission (SMT) protocol is to securely deliver the sender’s message at the receiver’s end in the presence of a computationally unbounded adversary that can partially control the network by corrupting some of its nodes (except the sender and the receiver). In a network modelled as a directed graph, to achieve unconditional security tolerating tb Byzantine faults, it is known that: (1) if all the paths are one-way connected from the sender to the receiver – called as forward channels – then 2tb + 1 vertex-disjoint forward channels are necessary and sufficient (2) for 1 ≤ u ≤ tb, if there exist 2tb + 1 − u vertex-disjoint forward channels then u vertex-disjoint paths from the receiver to the sender – known as feedback channels – are necessary and sufficient. Moreover, similar characterization exists for tolerating mixed faults – up to t f fail-stop faults in addition to tp passive faults. We notice that these results characterized the networks by studying the required number of extra vertex-disjoint feedback channels, conditioned on the existence of a certain number of forward channels. In this work, we give a generic characterization without attaching any such if condition. Specifically, we answer the following questions. In a given directed graph, that is abstracted as a collection of strong paths from S to R and R to S, under what conditions is SMT (im)possible tolerating: (1) up to tp passive faults?, (2) mixed faults – up to t f fail-stop faults in addition to tp passive faults?, and (3) up to tb Byzantine faults? Also, for each of these three problems, we explicitly show that there are networks in which SMT protocols exist whereas the existing results do not characterize such networks.

Abstract

The architectural trend towards heterogeneity has pushed heterogeneous computing to the fore of parallel computing research. Heterogeneous algorithms, often carefully handcrafted, have been designed for several important problems from parallel computing such as sorting, graph algorithms, matrix computations, and the like. A majority of these algorithms follow a work partitioning approach where the input is divided into appropriate sized parts so that individual devices can process the “right-sized” parts of the input. However, arriving at a good work partitioning is usually non-trivial and may crucially depend also on the input instance apart from the heterogeneous algorithm used. An extensive empirical search is not helpful as such an empirical search can potentially offset any gains accrued out of heterogeneous algorithms. Other recently proposed approaches too are in general inadequate. In this paper, we propose a simple and effective technique for work partitioning in the context of heterogeneous algorithms. Our technique is based on randomized sampling and therefore can adapt to both the algorithm used and the input instance. Our technique is generic in its applicability as we will demonstrate in this paper. We validate our technique on three problems: multiplying two unstructured sparse matrices (spmm), multiplying two scale-free sparse matrices, and finding the connected components of a graph (CC). For these problems, we show that using our method, we can find the required threshold that is under 10% away from the best possible thresholds respectively.

Abstract

In a network of n nodes (modelled as a digraph), the goal of a perfectly secret message transmission (PSMT) protocol is to replicate sender’s message m at the receiver’s end without revealing any information about m to a computationally unbounded adversary that eavesdrops on any t nodes. The adversary may be mobile too – that is, it may eavesdrop on a different set of t nodes in different rounds. We prove a necessary and sufficient condition on the synchronous network for the existence of r-round PSMT protocols, for any given r > 0; further, we show that round-optimality is achieved without trading-off the communication complexity; specifically, our protocols have an overall communication complexity of O(n) elements of a finite field to perfectly transmit one field element. Apart from optimality/scalability, two interesting implications of our results are: (a) adversarial mobility does not affect its tolerability: PSMT tolerating a static tadversary is possible if and only if PSMT tolerating mobile t-adversary is possible; and (b) mobility does not affect the round optimality: the fastest PSMT protocol tolerating a static t-adversary is not faster than the one tolerating a mobile t-adversary.

Abstract

This paper extends recent work on vulnerability extrapolation. A surge in vulnerability exploits against old and new softwares, urges the importance of detection of vulnerabilities and possible attacks prior to the attacker. How sophisticated an exploit may be, an underlying prerequisite remains to be the presence of at least one memory corruption bug, serving as entry point for the exploit. Therefore several rigorous software testing techniques are borrowed to detect and eliminate software bugs as early as possible. Code similarity based bug detection is one of such techniques, which, in the parlance of software security, is also termed as vulnerability extrapolation. In this paper, we present a source code similarity based bug identification technique by considering code features that are relevant for security related bugs. Our technique works by enriching (augmenting) abstract syntax trees (ASTs) of functions by considering security relevant properties of the code. We show the effectiveness of the augmented AST based similarity approach over existing methods by evaluating proposed method on real-world applications.

Abstract

Consider a synchronous distributed network which is partly controlled by an adversary. In a Perfectly Secret Message Transmission(PSMT) protocol, the sender S wishes to transmit a message to the receiver R such that the adversary learns nothing about the message. We characterize the set of directed graphs that admit PSMT protocols tolerating a dual failure model where up to tp nodes are passively corrupted and further up to any tf nodes may fail.

Abstract

These days' discussion forums provide dependable solutions to the problems related to multiple domains and areas. However, due to the presence of huge amount of less-informative/inappropriate posts, the identification of the appropriate problem-solution pairs has become a challenging task. The emergence of a variety of topics, domains and areas has made the task of manual labelling of the problem solution-post pairs a very costly and time consuming task. To solve these issues, we concentrate on deep semantic and logical relation between terms. For this, we introduce a novel semantic correlation graph to represent the text. The proposed representation helps us in the identification of topical and semantic relation between terms at a fine grain level. Next, we apply the improved version of personalised pagerank using random walk with restarts. The main aim is to improve the rank score of terms having direct or indirect relation with terms in the given question. Finally, we introduce the use of the node overlapping version of GAAC to find the actual span of answer text. Our experimental results show that the devised system performs better than the existing unsupervised systems.

Abstract

In this paper, we present a novel N-gram (N> = 1) filtration technique for keyphrase extraction. To filter the sophisticated candidate keyphrases (N-grams), we introduce the combined use of: 1) statistical feature (obtained by using weighted betweenness centrality scores of words, which is generally used to identify the border nodes/edges in community detection techniques); 2) co-location strength (calculated by using nearest neighbour Dbpedia texts). We also introduce the use of N-gram (N> = 1) graph, which reduces the bias effect of lower length N-grams in the ranking process and preserves the semantics of words (phraseness), based upon local context. To capture the theme of the document and to reduce the effect of noisy terms in the ranking process, we apply an information theoretic framework for key-player detection on the proposed N-gram graph. Our experimental results show that the devised system performs better than the current state-of-the-art unsupervised systems and comparable/better than supervised systems.

Abstract

In extant quantum secret sharing protocols, once the secret is shared in a quantum network (qnet) it cannot be retrieved, even if the dealer wishes that his/her secret no longer be available in the network. For instance, if the dealer is part of two qnets, say Q1 and Q2 and he/she subsequently finds that Q2 is more reliable than Q1, he/she may wish to transfer all her secrets from Q1 to Q2. Known protocols are inadequate to address such a revocation. In this work we address this problem by designing a protocol that enables the source/dealer to bring back the information shared in the network, if desired. Unlike classical revocation, the no-cloning theorem automatically ensures that the secret is no longer shared in the network.

Abstract

Multiplying two sparse matrices, denoted spmm, is a fundamental operation in linear algebra with several applications. Hence, efficient and scalable implementation of spmm has been a topic of immense research. Recent efforts are aimed at implementations on GPUs, multicore architectures, FPGAs, and such emerging computational platforms. Owing to the highly irregular nature of spmm, it is observed that GPUs and CPUs can offer comparable performance. In this paper, we study CPU+GPU heterogeneous algorithms for spmm where the matrices exhibit a scale-free nature. Focusing on such matrices, we propose an algorithm that multiplies two sparse matrices exhibiting scale-free nature on a CPU+GPU heterogeneous platform. Our experiments on a wide variety of real-world matrices from standard datasets show an average of 25% improvement over the best possible algorithm on a CPU+GPU heterogeneous platform. We show that our approach is both architecture-aware, and workload-aware.