Abstract

More than a decade ago, startups, companies, research groups or individuals had to purchase hardware and set it up for each task. This approach made sense when the utility and the requirement of the hardware were fixed. However, this does not make sense in today’s growing market, since there is a continuous increase or decrease in hardware’s demands. Often, people require large amounts of resources for short duration of time (like in the case of scientific computation). In other cases, people require the ability to scale up and down the number of systems based on the demand rendering dedicated systems unprofitable. Resources can be of different types such as computation(CPU), storage(distributed file system storage), network, databases, etc. Cloud computing opens up a whole new paradigm where individuals or companies can rent all the resources they need and dispose them off later after the work is done. In this process, they are charged for exactly what they use and not a penny more. This is therefore a highly flexible model, since one can add or reduce the resources on the fly according to the requirements and be charged accordingly. With data centers spread across the globe and the use of cloud computing, we can now localize resources closer to the end user to improve performance and experience. Cloud Computing is thus highly profitable as it is based on utilization of commodity hardware. The systems are heterogeneous in nature as they have different memory performance, different storage capabilities, different network capabilities etc. In today’s world, we cannot have homogeneous systems as they will not be able to provide the flexibility that we require. For example, if some nodes in the cluster are over-utilized and some disks in the storage cluster are under-utilized, there can be a lot of scenarios where homogeneous systems won’t work due to the dynamic nature of our workloads or tasks. We therefore need to develop systems that are cognizant of this inherent heterogeneity and can adapt to the constantly changing environment. In our work, we are focused on allocating resources for workloads which are short lived and mainly used for batch processing. During a computing process, workload is the amount of processing that the computer has been given to do at a given time. So our main focus is to allocate resources from a specific cloud provider for handling these dynamic workloads. These assignments could be on the basis of price, utilization, individual cloud characteristics, efficiency/performance etc. We try to use all these factors to design various techniques for the assignment of different types of heterogeneous scenarios. Below are the three scenarios of heterogeneous cloud systems for which we have designed frameworks/algorithms to assign workloads: • In the first scenario, we propose MultiStack, which is a big data orchestration platform for deploying big data jobs across the hybrid cloud environment. The specific architecture elaborated in this paper uses Amazon Web Services as the public cloud provider and Openstack as the private cloud framework. The proposed framework aims at reducing the job completion time of workloads along with decreasing the cost using Spot Instance provisioning instead of on-demand provisioning. In this case, we try to assign an optimal number of instances (cluster of computing resources) to the given workload along with cost minimization. • In the second scenario, we propose a solution for optimal IO Workload assignment with respect to backend storage (Software Defined Storage) using statistical modelling to estimate measures of performance such as Throughput, IOPS, et al in that storage system. The proposed system uses support vector regression to estimate the performance of individual IO Workloads on each available Software Defined Storage(SDS) system for optimal assignment. We demonstrate our solution in a heterogeneous environment comprising of HDFS, GlusterFS, and Ceph. Therefore, in this case, we try to increase the efficiency by choosing/assigning an optimal storage environment for any given type of workload. • In the third scenario, we try to provide optimal assignment of IO workload with respect to compute and storage for a multi-cloud heterogeneous systems. We try to achieve and represent “optimality” by designing a pipeline model which selects a compute and a storage class for a given workload to maximize efficiency and then apply discount schemes provided by the public cloud providers for cost minimization. We also use some input parameters provided by the user to fine tune the cost minimization procedure. We have designed these methods and algorithms using the following three public cloud providers: Amazon Web Services, Microsoft Azure and Google Cloud Platform. We expand on these different scenarios and try to build different methods to solve each of them. Through this work, we hope to help individuals, startups, researc

Abstract

Code-Mixing (CM), a progeny of multilingualism, is defined as a phenomenon where linguistic units such as phrases, words and morphemes of one language are embedded within an utterance of another language. This phenomenon is often observed in conversations within the bilingual and multilingual user group. Also, Code-Mixed language is extensively used on social media sites like Facebook and Twitter. Though code-mixing is the most natural form of conversation both in speech and text (online chats), the current dialog systems and search engines are not capable of handling this kind of social interaction. Many Popular virtual personal assistants used by a significant amount of smart phone users are unable to handle the mixing and switching between any two languages, which occurs very naturally to any bilingual or multilingual person. So, as mentioned above, it becomes extremely important to understand CM for both information extraction and for the purpose of building dialog systems that are capable of social interaction. In this thesis we take the first step towards understanding CM between two languages - Telugu and English, belonging to two different language families, sharing no ancestry at all. We start by building basic preprocessing tools like Language Identification (LID) models, POS taggers for CM data. We collected Telugu-English code-mixed social-media blog based data. The collected data was annotated by two individual annotators and a Kappa score of 88.91 is reported, which is a sign of reliable data. We experimented with various machine learning algorithms and finally we present a Multiple Layer Perceptron (Neural networks) LID model that uses character n-gram vectors augmented with other handcrafted features. Our system gives an F1-score of 97 for English and 96 for Telugu. The LID module has been used for the task of POS tagging of Telugu-English CM data, which produced an accuracy of 52.37%. In the second part of the thesis we made an attempt towards understanding code-mixing in dialog (richest and most natural form of language) through automatic recognition of dialog act (speaker’s intention) of an utterance. We have experimented with learning algorithms like Support Vector Machines, Naive Bayes, Kth Nearest Neighbor and Hidden Markov Models. Our best system that gives an F1-score of 72.30 is HMM based. Non-availability of annotated conversational code-mixed data poses problems and hinders us from adopting data-driven methods like Neural networks. Manual procurement and annotation of code-mixed data is not only time-consuming but also is labor intensive. Therefore, we also investigate on how knowledge extracted from resource rich languages could be useful in dialog act recognition of code-mixed conversations. We show that a decent accuracy of 66% can be obtained by transforming the code-mixed utterances into a sequence of English words by the use of modules like LID, transliteration and translation. We propose that in the future, a variant of transfer learning can be used to incorporate this knowledge along with the knowledge obtained from manually annotated code-mixed conversations.

Abstract

In-band full-duplex (FD) communication that enables concurrent transmission and reception in a single frequency-time channel holds the promise of nearly doubling the spectral efficiency compared to the current half-duplex and out-of-band FD communication systems. The main hurdle in the practical implementation of such a full-duplex system is the loopback self-interference (LSI), which arises due to the FD operation of the communicating nodes. In such an FD transceiver, the transmit signal generally overpowers the intended receive signal making its detection extremely difficult. However, with the recent advancements in the LSI cancellation techniques, FD systems have finally become viable. Hence, it is no wonder that FD has been envisaged as one of the promising technologies for the next generation wireless networks, viz., 5G and beyond. In practice, the LSI cancellation process cannot eliminate the LSI completely due to various reasons, chief among them the difficulty in obtaining the perfect channel state information of the loopback channel. As a result, we are still left with a residual LSI, which would degrade the performance of an FD system. In this work, we consider the design of optimal transceiver and relay processing algorithms for FD multiple-input multiple-output (MIMO) cooperative networks. Specifically, we propose the algorithms for FD communication in three different scenarios: (i) a cognitive radio network, (ii) secure communication using physical layer security techniques, and (iii) a cellular network. In the cognitive radio setup, we consider the FD transceivers and the FD relay to be a part of the secondary network. The transceiver and the relay precoders are designed so as to ensure that the interference caused to the primary user is always below a specified threshold. We have considered the maximization of the receive signal-to-noise ratio (SNR) as the criterion for the design of the transceiver precoders. We have further extended this problem to the case where multiple relays are available for selection. A central control unit selects the relay that provides the highest receive SNR. In the next scenario, a passive eavesdropper tries to decode the data of the two legitimate FD transceivers. In this case, we consider secure communication between the legitimate transceivers using physical layer security techniques. The precoder and receive filter matrices are designed to ensure secure communication between the legitimate users. The secrecy performance of this system in the presence of a passive eavesdropper is analyzed by considering the relay signal as artificial noise for the eavesdropper. The effectiveness of the proposed design is evaluated in terms of the sum-secrecy-rate of the system. Finally, we consider a futuristic FD cellular network scenario where an FD base station communicates with two FD transceiver nodes, where one of the transceivers is assisted by an FD amplify-and-forward relay. In each of the scenarios, our prime focus is on mitigating the residual LSI and its detrimental effect on the performance of the system. The precoders at the transceiver nodes are designed to mitigate the LSI based on the requirements of their operating environment. The LSI at the relay is mitigated by incorporating it into the sum of meansquareerror (SMSE) minimization problem. The relay precoder and the transceiver receive filters are designed based on the minimization of the SMSE of the end-to-end communication. The resulting optimization problem is non-convex and hence a globally optimal solution is not guaranteed. We apply the coordinate descent method and the Karush-Kuhn-Tucker (KKT) conditions to obtain sub-optimal solutions. The complexities of the proposed algorithms are lower than that of the state-of-the-art algorithms, in terms of both number of computations and memory requirements. The various simulation results demonstrate the efficacy of our proposed designs in terms of LSI mitigation, power efficiency, number of iterations, and sum-rate performance.

Abstract

Wireless communication has expanded its horizon in almost every aspect of human lives and its consequence is rapid surge in the demand of spectral resource. Electromagnetic spectrum is a gift of nature and such spectrum bands cannot be increased beyond certain limit. Presently, spectrum is licensed by government agencies to the interested parties by accepting a license fee. At the time of allocation, it is assumed that the licensed party will be utilizing the spectrum up-to its full potential i.e. 100% of the time. Hence the frequency bands to be utilized by the primary user are decided a-priori irrespective of its dynamic utilization status. On the other side with the advent of technologies like IoT, wearable consumer electronics and smartphones etc. applications are becoming bandwidth hungry and the number of connected devices are increasing drastically. Gardner technology research, a premier IoT research company claims that in the year 2015, 4.9 billion devices were connected to the internet and by 2020 this figure will reach to 20.8 billion. Hence with such an exponential increase in the number of connected devices, we will soon be facing scarcity of the electromagnetic spectrum in near future. Cognitive Radio is an innovative technology with unprecedented level of intelligence and capability to enhance the system capacity as well as spectrum agility of wireless communication systems. It mitigates the problem of spectrum scarcity with the aid of opportunistic access of spectrum. This work is dedicated towards developing hardware efficient and reconfigurable spectrum sensing architectures as well as techniques from VLSI design and implementation perspectives. We propose enhancements to the widely used energy detector design which helps in reducing the overall hardware resources (like adders and multipliers) consumed by 46% and alleviates the memory footprint by more than 95%. Further the conventional energy detector design is extended for wide band sensing applications without compromising on detector performance. We also present reconfigurable VLSI architectures for cyclostationary spectrum sensor which aids in sensing OFDM signals constructed with a variety of sub-carrier lengths. We suggested a novel selective sampling based reconfigurable cyclostationaryspectrum sensor which reduces the memory requirement by 99% and other resources by 33%. To evaluate the performance of these architectures, extensive computer simulations are carried out and detector architectures are implemented on an FPGA platform to verify the timing and functionality. Such verification has been carried out by feeding real-world RF signals captured from standard-RF SDR front-ends. Finally, ASIC syntheses and post-layout simulations of these architectures in 90 and 65 nm-CMOS technologies are carried out and its implementation results are compared with the stateof-the-art.

Abstract

An important component of software reliability is the assurance of certain security guarantees, such as absence of low-level bugs that may result in code exploitation, for example. A program crash is an early indicator of possible errors in the program like memory corruption, access violation or division by zero. In particular, a crash may indicate the presence of safety or security critical errors. A safety-error crash does not result in any exploitable condition, whereas a security-error crash allows an attacker to exploit a vulnerability. However, distinguishing one from the other is a non-trivial task. This exacerbates the problem in cases where we get hundreds of crashes and programmers have to make choices which crash to patch first! In this work, we present a technique to identify security critical crashes by applying machine learning on a set of features derived from core-dump files and runtime information obtained from hardware assisted monitoring such as the last branch record (LBR) register. We implement the proposed technique in a prototype called Exniffer. Our empirical results, obtained by experimenting Exniffer on several crashes on real-world applications show that proposed technique is able to classify a given crash as exploitable or not-exploitable with high accuracy.

Abstract

World Wide Web was brought to the fore in 1989 as the first version of HTML (HyperText Markup Language), accompanied with the capability of hypertext - a base format for publishing web pages. As the user types in a website’s address in the address bar of the browser, an HTTP request is initiated by the browser. The browser receives the response from the web server and builds a DOM (Document Object Model), a data structure for storing information in a tree format. It then renders the content from the DOM into its window. Further, Image tag was proposed in 1993, which enabled web pages to cascade requests thereby escalating security threats. The basic browser model, however, allows content inclusion from any server, and this prevails as a basic design flaw which has led to several malicious attacks. Existing browser security policies like Same Origin Policy (SOP), Content Security Policy (CSP) do not mitigate these attacks by design. On March 27, 2015, Github witnessed a massive DDoS attack, the largest in Github’s history till date which prevailed for over three days. In this incident, browsers and users were used as vectors to launch the attack. This class of attack has affected many other websites on a large scale, such as Incapsula and CloudFlare. Upon detailed analysis, we found the primary cause of these attacks to be cross-origin request attacks (CORA). Given the fact that current browser security model does not prevent content inclusion cross-origin attacks, it is rather easy to launch such attacks. CORA is one of the top attacks in web security with CSRF (cross-site request forgery) attack ranking in the top 10 attacks (2017), by OWASP. Against this compelling backdrop, this work undertakes a detailed analysis of CORP, a browser security policy which can be used to mitigate cross-origin request attacks. CORP enables a server to control cross-origin interactions initiated by a browser. The browser intercepts the cross-origin requests and blocks the unwanted requests by the server. Further, we explain the outcome of this work in three folds: Firstly, it demonstrates a compelling application of CORP in mitigating the browser-based DDoS attack, which has severely affected several websites in the past. Secondly, to gain a better understanding of CORP, we built a formal model of cross-origin request attacks and mitigated it using CORP. CORP has a client side dependency where users will have to use a CORP compliant browser to mitigate cross-origin attacks. Considering this, the concluding task was - implementation of CORP in Chromium source code. To evaluate the effectiveness of CORP, we conducted several experiments on various cross-origin attacks. We simulated a browser-based DDoS attack in a lab environment and did a detailed analysis on mitigation of the attack using CORP. After that, we modelled a complex case of a cross-origin transaction, FIM (Federated Identity Management), and incorporated a malicious cross-origin attack in it. We, then, validated CORP by mitigating the attack successfully using CORP. Modelling helped us in identifying the different parts involved in a CORP transaction. Thereon, to gain deeper insight into the functioning of CORP, we implemented CORP in Chromium browser and demonstrated the mitigation of various cross-origin attacks (CSRF, Clickjacking, cross-site timing attacks), present in websites hosted by top enterprises (such as facebook, google, twitter, dropbox, etc.), using CORP.

Abstract

In a large distributed network of interconnected nodes, the goal of any 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 the literature, different variants of SMT problem have been studied depending on the type of network model and/or the types of node corruptions. Undirected graph model and directed graph model are two of the most well-studied network models. Different types of node corruptions studied are passive, fail-stop, omission and Byzantine. In passive corruption, the adversary is only allowed to read/eavesdrop the corrupted node. In fail-stop corruption, the adversary can crash the corrupted node at its will. In omission corruption, the adversary can eavesdrop and/or crash the corrupted node. In Byzantine corruption, the adversary fully controls the actions of the corrupted nodes. In an undirected graph setting, for most variants of SMT problem whether the corresponding SMT protocols exist or not is known in the literature. Moreover, whenever a protocol exists, communication efficient protocols have been designed too. Whereas, in directed graph setting very little is known about the existence of protocols (for dif- ferent variants of SMT problem) as well as the design of efficient protocols. This thesis primarily focuses on bridging this gap between undirected and directed graph settings. It is usually difficult to design efficient protocols in arbitrary directed graphs due to the plethora of different cases/possibilities that usually need to be dealt with. However, in the literature due to the simplicity and ease of protocol design, wires model is considered which is a special case of directed graph setting. In wires model, paths (known as wires) from the sender to the receiver and vice-versa are considered whereas the weak paths are discarded. On the other hand, if the intermediate nodes can generate random-coins and/or perform computations, it is known that the directed wires-based abstraction is inadequate to capture arbitrary directed graphs. In this thesis, we design efficient protocols for different variants of SMT problem in both wires model as well as arbitrary directed graph model. Moreover, we introduce a new model namely routing model to answer the following fundamental question. If each intermediate node is a mere router (can not do computations but can route message to its neighbours) then under what condition(s) is given variant of SMT (im)possible? Furthermore, in arbitrary directed graph setting, we design a protocol which is both communication as well as round/hop optimum when the adversary is passive.

Abstract

Indian classical music is monophonic in nature. Melody is key to any performance. The entire performance is based on a single raga (melodic mode). Some performances are based on a coalescence of two or more ragas. Only a small duration in any musical performance in Indian art music is the precomposed portion. The rest involves a gradual systematic exploration of the raga using various forms ¯ of improvisation. The performer has great freedom in exploring his own improvisational patterns in order to delve into the intricacies of the given raga. However the performer is bound by the frame- ¯ work of the raga, t ¯ ala and other factors such as ghar ¯ an¯ a (the musical school which he belongs to), laya ¯ (tempo). There is a great variation in quality and nature of improvisation among different practitioners based on their cognitive and imaginative abilities. There are two important tools used in improvisation: alankar/alank ¯ aran (musical ornamentation) and t ¯ anas. In this thesis we restrict our study to the present ¯ day usage of alankaran ¯ 1 . Ornamentation is an indispensable part of improvisation. The performer tries to evoke the mood of the raga (melodic-mode) with the delicate exploration of flourishes and ornamentation. Indian classical ¯ music is cognitively associated with these decorations instead of the actual underlying notes. We are interested in discovering the hidden musical patterns and structures in Indian music which are fundamental in unfolding of a raga. Recognizing these patterns can further help in music search, retrieval, recommendation and pedagogy. This thesis makes an attempt to study these ornaments computationally. We begin the study with the objective to computationally detect these ornaments in Dhrupad performances on rudra veen ¯ . a. Dhrupad is the oldest surviving form of Hindustani classical music, is monophonic ¯ in nature and has a wealth of ornamentation. We have crowd-sourced multimedia annotations of primary alankara-s, namely, meen ¯ . da (glides between notes), andolana (vacillations in the note region) and ¯ gamaka (two notes alternation). These were used as the ground truth. Two signals in the time domain, a query signal, which consists of fundamental ornament templates, and a reference signal were compared. Using a variant of dynamic time warping, we then detect the matching subsequences in the reference signal with high accuracy. This method of iterative template matching is naive and has drawbacks, some of which are: 1.) Restrictiveness of the experiment to a set of non-exhaustive list of ornament templates, 2.) Computational overheads of comparing huge pitch vectors using dynamic time warping. While DTW matching was an effective method of detecting these ornaments, we didnt use any domain specific knowledge to detect/identify these ornaments computationally. Cognitively ragas are ¯ 1Most of these definitions are either explained in the introduction section or in the glossary at the end vi vii associated with ornamentation.These along with the ways in which notes are approached,sustained and quitted constitute flows. We call them flows due to the constant change in the frequency and amplitude domains. The rate of change in frequency and amplitude domains together constitute the fundamental nature of ornamentation. We thus model ornamentation as first and second derivative of frequency and amplitude information to see whether the property of rate of change is fundamental to the idea of flows. We were able to achieve very high clustering accuracy by using this representation and our custom defined distance measure. We achieved an accuracy of 81% in distinguishing between Murki vs Kan and 84.5% in Andolana vs Ghaseet. This again shows that transition is at the heart of the definition ¯ of flows and ornaments. However this doesnt account for hidden musical patterns which might not be captured by the manually engineered representation and custom distance. It is important to note that ornaments and flows are intricate Indian music decorations which only experienced musicians can recognize and comprehend. In all of our previous experiments we have used small annotated datasets which do not exhaustively capture patterns underlying ornaments. The biggest challenge in learning and making sense of flows or ornaments is the unavailability of annotated music data. Thus, to have a big data driven exhaustive exploration of these melodic structures implies having either 1.) a multi performer crowdsourced effort to create a large exhaustive dataset, or 2.) an unsupervised/semi-supervised method of learning. To avoid the shortcomings of non-exhaustive small datasets and hand engineered representations, we also develop a robust unsupervised method to learn fixed length representations of ornaments. In the domain of speech processing, neural networks have recently successfully been used for encoding acoustic inf

Abstract

Although tremendous progress has been achieved towards understanding the biochemical versatility and biological functions of RNA, there is a need to deepen our understanding of the principles governing the structural and functional diversity of these fascinating biomacromolecules. One possible factor that contributes to the structural diversity of RNA is the presence of a variety of post-transcriptional modifications of the canonical nucleobases. Detailed analysis of the role of noncovalent interactions involving modified nucleobases in RNA is thus, expected to contribute to our understanding of the factors governing the structure and dynamics of RNA. In an attempt to contribute towards this theme, the present work employs a combination of sequence and structural bioinformatics techniques, along with quantum chemical calculations to understand the structure and strength of hydrogen bonded pairs and higher order structures involving post-transcriptionally modified nucleobases that are present in RNA macromolecular crystal structures. In addition to highlighting the important structural roles some of these hydrogen bonded entities in RNA molecules, our studies highlight the need for, and providing a comprehensive approach towards further investigations on such interactions in the context of many biological processes involving RNA. In addition to understanding the role of posttranscriptional modifications in RNA, we explored the structural and functional diversity exhibited by riboswitches, non-coding RNA, a class of RNA molecules that are a part of RNA regulatory networks, which specifically binds to small cognate ligands and regulate their turnover. Using QM and MD simulations, we explored the molecular features responsible for ligand recognition, and the associated role of noncovalent interactions in gene regulation by riboswitches. Overall, the thesis contributes towards understanding the structure-functional relationships in RNA macromolecules.

Abstract

This thesis discusses a mixed-initiative, domain independent dialog system based on a hierarchically structured knowledge base. The system is rule-based and uses dependency relations and part-of-speech tags obtained from the Stanford Parser coupled with the hierarchical structure of the knowledge base to identify the user’s goal. Primarily, the system is able to accept multi-sentence inputs, that is, multiple sentences forming a query in a single user turn. The system was tested for its accuracy over answering questions, and also subjective testing was done to evaluate the dialog flow; mainly over the books domain. We show examples of the system developed over the domains of books, movies and restaurants to demonstrate the domain independence. We also discuss in detail the simple, rule-based system of extracting relevant information from a user’s query that contributes to the domain independent dialog system. Relevant information is extracted from a user query by using only dependency relations and POS tags, obtained from the Stanford Dependency Parser. Using the universal dependency tags provided by the parser, we tried to understand the semantic structure of a query. This is done by looking for semantically important dependents of the verb, such as the subject, direct object, prepositions and their objects, and so on. Using information obtained from a combination of the dependency relations and the inherent semantic implications of words (such as ‘who’ or ‘where’), we tried to extract the main objective or keyword of the query, and the constraints pertaining to it. This implementation itself is domain independent, however, a mapping to a knowledge base would require some domain knowledge; this issue is resolved using the hierarchically structured knowledge base. This keyword and constraint identification system is tested on the course management domain and the library domain. In order to further improve the domain independent keyword identification for natural language queries, we used statistical methods. We took queries supplemented by only their dependency tags (Stanford Parser) and part-of-speech tags (Stanford POS tagger) and labeled the keywords. We then delexicalised the training data, and used the Conditional Random Fields algorithm to learn these labels. We used the queries created by [45] in the course management domain for training, and tested our model on the queries of three domains: course management, library and the G EO Q UERIES 250 dataset and report fairly high accuracies of 90.65%, 83.19% and 97.13% respectively, making our model a truly domain independent and highly accurate keyword identifier. There is no agreed upon standard for the evaluation of conversational dialog systems, which are well-known to be hard to evaluate. The difficulty lies in pinning down metrics that will correspond to human judgments and the subjective nature of human judgment itself. We explored the possibility of using Grice’s Maxims to evaluate effective communication in conversation. We collected a few system generated dialogs from popular conversational chatbots across the spectrum and conducted a survey to see how the human judgements based on Gricean maxims correlate, and if such human judgments can be used as an effective evaluation metric for dialogs.