Student Projects


DADS: Distributed Attestation for Device Swarms

Emerging trends in embedded systems, such as applications on Industrial control and IoTs, involve heterogeneous and mobile devices to communicate, process and exchange safety, privacy and mission critical information. These smart interconnected devices often operate in large number. These facts along with the nature of the devices make them susceptible to a wide range of attacks. Various approaches have been designed to check the authenticity of the software configuration. However, they either assume a single-prover device and thus do not scale to device swarms or allow cumulative attestation report to be sent out through a single node which could be resulted in a single point of failure. In this work, we present a distributed attestation scheme for device swarms which assures resilience of the system to node compromise/failure. First, devices are checked for their software integrity, and then take the responsibly to attest their neighbors. This way, attestation is distributed among devices and thus avoids a single point of failure. Besides this, network restructuring allows nodes to join and leave on the fly, which is in line with the dynamic nature swarms.

Research Area : Graphic and Vision
Project By : Samuel Wedaj
Supervised By : Kolin Paul , Vinay Joseph Ribeiro

Analysis of the Spread of Information on Twitter and its Application to Internet Content Distribution

With rapidly growing traffic volumes on the Internet, service providers are finding it increasingly hard to manage delivery of content to end users. We observe that a large portion of the traffic is contributed and accessed by Online Social Networking (OSN) websites, and we attempt to leverage this fact to build better content placement and caching strategies for Content Delivery Networks (CDNs). Through a large measurement study of OSN datasets, we show that highly popular topics cross regional geographic boundaries, and time-zone differences can be used to potentially improve content prefetching policies. Through an event-based analysis, we show that topic popularity peaks when multiple small components in the social graph coalesce together to form a single giant component. We also show that to track topic trends, it is sufficient to track a small percentile of the most popular users rather than track all users. Finally, we apply these insights to design OSN-aided caching policies in CDNs, but we discover that simple LRU caching does quite well unless cache sizes are very small. This is a significant negative result that can help guide other researchers interested in applying OSN signals to improve Internet performance. Our contributions also go beyond just scoping the potential of using OSN signals to aid content distribution our insights can find applications in the placement of advertisements on OSN websites, information recommendation, and other areas of work we hope to explore in the future.

Research Area : Computer Networks and Distributed Systems
Project By : Amit Ruhela
Supervised By : Aaditeshwar Seth ,

The rich and middle classes on Twitter: Are popular users indeed different from regular users?

Online social networking (OSN) websites such as Twitter and Facebook are known to have a wide heterogeneity in the popularity of their users, counted typically in terms of the number of followers or friends of the users. We add to the large body of work on information diffusion on online social networking websites, by studying how the behavior of the small minority of very popular users on Twitter differs from that of the bulk of the population of ordinary users, and how these differences may impact information diffusion. Our findings are somewhat counter intuitive. We find that on aggregate metrics such as the tweeting volume and degree of participation on different topics, popular users and ordinary users seem similar to each other. We also find that although popular users do seem to command an influential position in driving the popularity of topics on Twitter, in practice they do not affect growth rates of user participation and the causality of popular users driving event popularity is hard to establish. Our main contribution is to show that accurately capturing the similarity and differences between different segments of the user population can help OSN applications fine tune their design.

Research Area : Computer Networks and Distributed Systems
Project By : Amit Ruhela
Supervised By : Aaditeshwar Seth ,

Optimal Radius for Connectivity in Duty-Cycled Wireless Sensor Networks

We investigate the condition on transmission radius needed to achieve connectivity in duty-cycled wireless sensor networks (briefly, DC-WSN). First, we settle a conjecture of Das et. al. (2012) and prove that the connectivity condition on Random Geometric Graphs (RGG), given by Gupta and Kumar (1989), can be used to derive a weak sufficient condition to achieve connectivity in DCWSN. To find a stronger result, we define a new vertex-based random connection model which is of independent interest. Following a proof technique of Penrose (1991) we prove that when the density of the nodes approaches infinity then a finite component of size greater than 1 exists with probability 0 in this model. We use this result to obtain an optimal condition on node transmission radius which is both necessary and sufficient to achieve connectivity and is hence optimal. The optimality of such a radius is also tested via simulation for two specific duty-cycle schemes, called the contiguous and the random selection duty-cycle scheme. Finally, we design a minimum-radius duty-cycling scheme that achieves connectivity with a transmission radius arbitrarily close to the one required in Random Geometric Graphs. The overhead in this case is that we have to spend some time computing the schedule.

Research Area : Algorithms and Complexity Theory
Project By : Sainyam Galhotra Tarun Mangla
Supervised By : Amitabha Bagchi ,

Sec-X: A Framework for Collecting Runtime Statistics for SoCs with Multiple Accelerators

We are moving into an era where large SoCs will have a portfolio of different kinds of cores and accelerators. Many of these computational elements might be designed by third parties. In this setting, it is beneficial to collect accurate runtime information such that we can diagnose performance problems, verify and report correctness issues, and collect usage scenarios of third party hardware. This problem is non-trivial if we consider the possibility of defective or malicious elements in the chip. We design an architecture, Sec-X, which helps us collect various metrics of potential interest in a fair, reliable and secure fashion. These logs can subsequently be made available to users, IP vendors, and the system integrator through a trusted third party called the auditor. The performance (0.03%), power (1.04W) and area (0.32%) overheads of our scheme are minimal.

Research Area : Computer Networks and Distributed Systems
Project By : Rajshekar K
Supervised By : Smruti Ranjan Sarangi ,

Fast Dynamic Binary Translation for the Kernel

Dynamic binary translation (DBT) is a powerful technique with several important applications. System-level binary translators have been used for implementing a Virtual Machine Monitor [2] and for instrumentation in the OS kernel [10]. In current designs, the performance overhead of binary translation on kernel-intensive workloads is high. e.g., over 10x slowdowns were reported on the syscall nanobenchmark in [2], 2-5x slowdowns were reported on lmbench microbenchmarks in [10]. These overheads are primarily due to the extra work required to correctly handle kernel mechanisms like interrupts, exceptions, and physical CPU concurrency. We present a kernel-level binary translation mechanism which exhibits near-native performance even on applications with large kernel activity. Our translator relaxes transparency requirements and aggressively takes advantage of kernel invariants to eliminate sources of slowdown. We have implemented our translator as a loadable module in unmodified Linux, and present performance and scalability experiments on multiprocessor hardware. Although our implementation is Linux specific, our mechanisms are quite general; we only take advantage of typical kernel design patterns, not Linux-specific features. For example, our translator performs 3x faster than previous kernel-level DBT implementations while running the Apache web server.

Research Area : Computer Networks and Distributed Systems
Project By : Piyus Kedia
Supervised By : Sorav Bansal ,

MajSynth : An n-input Majority Algebra based Logic Synthesis Tool for Quantum-dot Cellular Automata

We need specialized logic synthesis methods to exploit the 3- input Majority gate, the primary logic element of the emerging Quantum-dot Cellular Automata paradigm. Existing methods take a narrow approach of manipulating functions into a network of 3-input Majority functions with no knowledge of larger Majority functions, and hence fall short while minimizing large Boolean functions. In this work, we extend the 3-input Majority operation to a generic n-input Majority operation, and develop the fundamental algebra for n-Majority functions. We use this new algebra to develop a logic synthesis method independent of the size of the target Majority gate. Additionally, we exploit the symmetry of the Majority gate to efficiently implement all classes of symmetric Boolean functions. We make the case for Boolean graph decomposition techniques needing to exploit the various levels of symmetry present in a graph in order to exploit the power of Majority gates. Our Majority Synthesis tool provides more compact 3-input Majority networks for large Boolean functions than existing tools. It is equipped to synthesize for the new 5-input Majority QCA gate if necessary.

Research Area : Computer Networks and Distributed Systems
Project By : Rajeswari D
Supervised By : M. Balakrishnan , Kolin Paul

Building citizen engagement into the implementation of welfare schemes in rural India

Citizen feedback on the implementation of social welfare schemes can help fine tune their design, understand problems, and assess the benefits and impact from these schemes. Such feedback loops however are singularly missing in most schemes in India, and are conveyed only indirectly via civil society and social audit organizations that try to serve as a bridge between citizens and the government. We leverage the deep penetration of mobile phones in India to design a suite of IVR (Interactive Voice Response) tools that can help capture community perceptions, improve awareness of the people, and verify official records directly by the beneficiaries themselves. In the context of a rural employment guarantee scheme, we evaluate these tools in a few villages in the state of Haryana and demonstrate that there is good scope for using IVR tools to serve as a citizen engagement channel for welfare schemes. Our contribution lies in outlining several use-cases for technology interventions, and uncovering nuances that should be addressed if such systems are integrated into the implementation of social welfare schemes.

Research Area : Computer Networks and Distributed Systems
Project By : Dipanjan Chakraborty
Supervised By : Aaditeshwar Seth ,

Result Clustering for Keyword Search on Graphs

Graph structured data on the web is now massive as well as diverse, ranging from social networks, web graphs to knowledge-bases. Effectively querying this graph structured data is non-trivial and has led to research in a variety of directions structured queries, keyword and natural language queries, automatic translation of these queries to structured queries, etc. In this project, we are concerned with a class of queries called relationship queries, which are usually expressed as a set of keywords (each keyword denoting a named entity). The results returned are a set of ranked trees, each of which denotes relationships among the various keywords. The result list could consist of hundreds of answers. The problem of keyword search on graphs has been explored for over a decade now, but an important aspect that is not as extensively studied is that of user experience. In this project, we focus on the problem of presenting results of a keyword search to users. Our approach is to present a clustering of results rather than single results. The novelty of our approach lies in the fact that we use language models to represent result trees and our clustering algorithm makes use of the JS-divergence as the distance measure. We compare our approach with the existing approaches based on isomorphism between trees and tree-edit distance. The LM based clusters formed are highly cohesive and clearly separated from each other.

Research Area : Computer Networks and Distributed Systems
Project By : Madhulika Mohanty
Supervised By : Maya Ramanath ,

Sampling and Reconstruction using Bloom Filters

In this paper, we address the problem of sampling from a set and reconstructing a set stored as a Bloom filter. To the best of our knowledge our work is the first to address this question. We introduce a novel hierarchical data structure called BloomSampleTree that helps us design efficient algorithms to extract an almost uniform sample from the set stored in a Bloom filter and also allows us to reconstruct the set efficiently. In the case where the hash functions used in the Bloom filter implementation are partially invertible, in the sense that it is easy to calculate the set of elements that map to a particular hash value, we propose a second, more space-efficient method called HashInvert for the reconstruction. We study the properties of these two methods both analytically as well as experimentally. We provide bounds on run times for both methods and sample quality for the BloomSampleTree based algorithm, and show through an extensive experimental evaluation that our methods are efficient and effective.

Research Area : Operating Systems, High Performance Computing and Systems
Project By : Neha Sengupta
Supervised By : Amitabha Bagchi , Maya Ramanath

Towards developing a Technical Knowledge-Base for Personalized Learning

A commonly faced challenge by enthusiastic learners is to build a complete and well-rounded understanding of a topic of interest. While understanding the big picture is equally important, it is also necessary that the learning material be presented to the user in the correct order. Understanding the content from a textbook would be too overwhelming for a reader who has very little background on a topic of interest. On the other hand, looking for documents on Web would not provide a point to start reading from since there are unlimited sources available on the Web. The background of a learner $A$ could be different from the background of another learner $B$ on a topic $t$. The requirement of well-rounded understanding of a topic of interest increases many fold in the technical domain where clarity of concepts is a pre-requisite for researchers to establish ground-breaking research. Computer Science is suitable field that is rich with technical concepts. There exists a need to build a system that would provide a personalized reading order along with appropriate background for a topic of interest for a user. This work will focus on building a Technical Knowledge Base that will aid in providing personalized lecture notes to enthusiastic learners.

Research Area : Computer Networks and Distributed Systems
Project By : Prajna Devi Upadhyay
Supervised By : Maya Ramanath ,

Copyright © 2024 Department of Computer Science and Engineering. All Rights Reserved.