Abstract

Natural Language Interface to Database (NLIDB) systems allow the users to query databases in a natural language. A NLIDB system takes a natural language (NL) query as input from the user and converts it to a database query language like SQL (structured query language). In this work, we present a novel approach to design a generic, portable and contextual NLIDB system. We have designed a novel computational paninian grammar (CPG) framework based semantic frames (i.e. domain knowledge) to identify the domain terms in the NL query. We propose a novel graph based method to identify join conditions of the SQL query. By using our approach, the domain of a NLIDB system can be easily changed without disturbing the implementation details of the system. Our approach greatly reduces both the size of the domain knowledge required to develop a NLIDB system and the time to create the domain knowledge. We propose a novel approach to identify contextual information in NLIDB systems. We present a novel classification of the interactions between user and system: Strongly Coherent interaction, Coherent interaction and Weakly Coherent interaction. We proposed three models depending on the way in which the contextual information can be utilized in the interactions: Linear Disjoint Model, Linear Coincident Model and Non-Linear Model. We propose a relationship schema among the responses (user and system responses). Further, we also present a novel method to identify contextual information in Linear Disjoint interactions. We evaluated our approach on university related queries and the results confirm the viability of the proposed approach.

Abstract

The Internet and its applications have increased to an enormous extent in the past decade. This has exposed its users to various threats. In-premise appliances such as firewalls, IDS and anti-virus usually just prevent the attack and do not trace the attacker. Network forensic techniques can be used to traceback the source and the path of an attack that can be used as a legal evidence in a court of law. Packet attribution is a network forensics method that can be used to perform traceback of the packet to its source. It does not rely upon header of IP packet alone because headers can be spoofed and manipulated. Hence for accurate traceback, there is a need to include packet‘s payload to perform attribution. Storing each and every packet traversing though network is not practical and would raise privacy concerns. Packet Attribution System technique which stores the network data in compressed formats is more suitable for such applications. Given a payload (or its significant portion/signature called excerpt) and time interval, attribution system would enable identifying receivers and senders of the packet. During traceback, the excerpt needs to be matched with the stored packet payload at every network device and identify the path taken by the packets. Various compression techniques based on Bloom Filters were proposed to solve both storage and privacy issues. Packet Attribution Systems like Source Path Isolation Engine, Block Bloom Filters, and Hierarchical Bloom Filters are based upon bloom filters to traceback the attack path. Existing techniques have defined a way to store and query the bloom filters, but have not provided a standard mechanism to submit the excerpt query to the routers. Because there is no common way for submitting the query, it would lead to implementation difficulties. In this thesis, we propose query approach, leveraging existing standards and techniques based on SNMP; it is easy to implement and deploy at each router using standard SNMP extensions. All the features inherently supported by SNMP can be used including security features of SNMPv3 while performing excerpt query. In this approach, a new Management Information Base (MIB) is defined to capture all the query attributes. Router’s SNMP agent is extended by loading the new MIB implementation. NMS or a MIB Browser can be used (without any modifications) by simply loading extended MIB structure and send SNMP request to router for the excerpt. This approach can be used not only by Packet Attribution Systems, but also by any approach which involves submitting excerpt query to the network appliances. In case of incident, NMS sends the excerpt query to all the routers in Autonomous System (AS). Each router upon receiving the request, search their bloom filters for existence of excerpt and send the result to NMS. NMS receives the response from different routers and determines the traceback path from victim to source of attack. Here all the routers are engaged in searching the bloom filters while causing possible latency in performing actual routing tasks; this degrades network performance and in-turn may lead to self Denial of Service (DoS) on the network. To avoid the performance issue, in this thesis, we propose the optimization of routers to be searched, by prioritizing them. In this method, as a first step we sequentially search only the preferred routers in the path and traceback the attacker. Routers to be searched will be determined by modified packet attribution methods and communicated to NMS while performing excerpt query. There would be no need to calculate the attack path and only required routers will be loaded to determine attack path.

Abstract

Syntactic parsing is the process of analyzing a given natural language sentence to identify various syntactic roles played by the words in the sentence. Such roles can be very useful for downstream natural language processing applications. Parsing morphologically rich languages is a challenging task due to their non-configurational properties like long distance dependencies, free word order, non-projective structures and complex agreement rules. Dependency parsing using computational panianian grammar was succesfully tried for Hindi, which is a morphologically rich, relatively free-word-order language compared to English. Both rule based and data-driven dependency parsers for Hindi exist and are being used in some downstream applications (like Machine Translation). Rulebased techniques operate on expert rules and constraints manually loaded into the algorithm that detect the relationships between the words. Data-driven techniques, on the other hand, exploit the available manually annotated parse trees using various machine learning techniques, to learn a mapping between the sentences and the parse trees. While rule-based systems work as expected on the sentence types they can handle, they often suffer from lesser coverage than data-driven systems. This leads to data-driven systems achieving better accuracies than rule-based systems across different types of data. However, the existing rule-based technique (constraint-based parsing) for Hindi dependency parsing exploits the notion of a clause in sentences while doing parsing thereby distributing the parsing complexity into two stages instead of a one stage parsing strategy that is employed in the data-driven techniques. In this work, we use insights from the constraint based parsing framework to develop a two-stage data-driven clausal dependency parsing approach for Hindi. We first propose a data-driven method to do clausal parsing (parsing different clauses in a sentence separately). To use the partial parses thus obtained in a full sentence dependency parser, we propose two data-driven methods that can start with a partial parse (instead of starting from a raw sentence) and completes the full dependency parse. We compare each of these methods in their ability to deal with different issues in statistical parsing of morphologically rich languages. These methods lead to a statistically significant improvement over the state-of-the-art Hindi dependency parsing accuracy for sentences with more than one clause (complex sentence). Detailed error analysis was carried out to sort out the constructions for which the best dependency parsers (for Hindi) till now perform well and the constructions for which, the parsers have to be improved significantly.

Abstract

Since FCC had authorized UWB frequency range from 3.1 GHz to 10.6 GHz for wireless communication, several technologies developed for communication applications. And, demand of low cost, high data rate wireless communication systems rapidly increased. Although, current wireless design circuits built for cellular or non-cellular applications, trade-off with matching, signal detection, linearity, gain and noise parameters. In wireless receiver systems, effect of noise of all the subsequent stages is reduced by the gain of low noise amplifier (LNA) and its noise injects directly into the receiver. Thus, it is necessary to boost the desired signal power while adding as little noise and distortion as possible so that the retrieval of this signal is possible in the later stages in the system. As LNA is first block in receiver chain, it must provide high gain for the next blocks. Moreover, noise of LNA is critical, since the received input signal is extremely weak and can be easily corrupted by even small amount of thermal noise. Additionally, it is desirable to integrate the circuit with CMOS technology to achieve low cost and chip area. This block has the job of matching the antenna input with the rest of the circuitry and simultaneously amplifying it for further processing. Recent demonstrations show that LNAs ranging from few MHz to 10 GHz are included in wireless receivers which uses single LNA for contiguous broadband signal processing. And, there are various techniques to design narrow band and wide band LNAs such as design using basic common source and common gate configurations with few improvement methods such as using noise cancellation techniques. In contrast to existing LNA topologies implementing noise cancellation techniques which usually do not consider much about gain improvement, this work proposes a design of common gate LNA employing a noise cancelling technique which not only reduces the noise but also improves the gain and is novel to best of our knowledge. In order to cancel the dominant thermal noise, we have analyzed the noise contributions from both, active and passive components in an existing CG LNA. The input matching device viz. first CG transistor was identified as the most dominant noise source which contributes 42% of overall LNA noise and remains flat i.e. (2.8 ± 0.3) dB over the entire range. However, second stage common source transistor contributes 22% in whole range and is more near the corner frequencies which is due to the narrow band characteristics of common source amplifiers. Hence, this work’s target is to cancel the most dominant thermal noise through proposed noise cancelling technique. The proposed technique is based on combining two paths one with reversed phase noise-signal and the other with non-reversed phase noise-signal, simultaneously the RF-signals in the two paths should be in-phase. The two parallel paths were designed by symmetrical cascade combination of CG-CS and CS-CG stages. Moreover, theoretical model of noise cancellation is presented along with the derived equations of overall noise figure. Finally, implementation is done using TSMC 0.18 μm CMOSRF technology on Cadence Spectre RF tool. Significantly, proposed LNA achieve a reduction of 22.49% in base noise figure and 31.48% improvement in peak power gain when compared to LNA without noise cancelling technique. Ultimately, peak power gain of 28.4 dB and base NF of 3.17 dB with good stability and linearity are achieved over the spectrum from 2.5 GHz to 4.5 GHz. Additionally, this work implement a design of UWB LNA which include interstage matching network to carry forward desired signal with the stoppage of undesired signal. Also includes a Chebyshev band pass filter for input matching and a shunt-series inductive peaking network to compensate the gain roll-off at higher frequencies. This design provides a peak power gain of 17.12 dB and base noise figure 3.4 dB within the frequency range from 3.1 GHz to 10.6 GHz. Also demonstrate a good input matching i.e. well below -10 dB in the desired frequency range. The entire circuit consumes 11.2 mW with 1.8 V supply and occupies 1 mm x 0.9 mm of layout area. Moreover, a detailed survey of various existing methodologies (basic and advanced) for narrow band, wide band and noise cancelling LNAs are discussed with their pros and cons.

Abstract

Barter was the original means of exchange and commerce in the olden days and was replaced by currency in the modern world. However, with the growth of ecommerce and the advent of the internet, online trade exchanges have sprouted. This has resulted in a spurt of online trading activity in the form of auctions, B2B and C2C barter. Hand-to-hand barter has given way to multifarious online trade exchanges such as BizXchange, BarterCard and Swap.com. Currently, one of the largest networks of online trade is BarterCard with over 50 million dollars of annual worldwide trade. In our work, we have explored a new and unstudied trade market which is a trust-based local, deadline-driven community. This trade market is explained below. Herein, the participants are members of a close-knit community such as a university hostel or a gated community. In a small social environment such as the ones mentioned, ordinary people are expected to have a variety of needs arising from time to time. Often, objects are required for short periods of time (a book to read), one-time use (redcolored shoes for a theme party) and the person is unwilling to buy new items for one-time use from the market. In such cases, the most common solution people opt for, is to borrow things from friends. We have explored and extended this trend to a larger community wherein close friends expand their barter circle to local acquaintances. Participants behave as ‘givers’ and ‘takers’ who exchange goods with each other over a period of time. The concept of ‘utility’ has been defined for both givers and takers in the following manner.

Abstract

Separation of images into its constituent components based on source of data, frequency distribution, or nature of data has been a widely used technique in the field of image processing and computer vision. Many problems are solved by partitioning images into components and working on each component separately. Common examples include breaking down of image into Red, Green and Blue channels/components for ease of representation or into Luminance and Chrominance for better compression. In this thesis, we explore the separation of natural images into appropriate components for the purpose of representation as well as recognition. We first introduce a framework where separation of images into direct and global components helps in modeling of 3D textures. These 3D textures are often described by parametric functions for each pixel, that models the variation in its appearance with respect to varying lighting direction. However, parametric models such as Polynomial Texture Maps(PTMs) tend to smoothen the changes in appearance. Therefore we propose a technique to effectively model natural material surfaces and their interactions with changing light conditions. We show that the direct and global components of an image have different characteristics, and when modeled separately, leads to a more accurate and compact model of the 3D surface texture. Direct component is mainly affected by structural properties of the surface and is therefore deals with phenomena like shadows and specularity, which are sharply varying functions. The global component is used to model overall luminance and color values, a smoothly varying function. For a given lighting position, both components are computed separately and combined to render a new image. This method models sharp shadows and specularities, while preserving the structural relief and surface color. Thus rendered image have enhanced photorealism as compared to images rendered by existing single pixel models such as PTMs. We then look at separating an image based on its sources of illumination or albedo variations for the purpose of scene text segmentation. Extracting text from scene images is a challenging task due to the variations in color, size, and font of the text and the results are often affected by complex backgrounds, different lighting conditions, shadows and reflections. A robust solution to this problem can significantly enhance the accuracy of scene text recognition algorithms leading to a variety of applications such as scene understanding, automatic localization and navigation, and image retrieval. We propose a method to extract and binarize text from images that contains complex background. We use Independent Component Analysis (ICA) to map out the text region, which is inherently uniform in nature, while removing shadows, specularity and reflections, which are included in the background. The technique identifies the text regions from the components extracted by ICA using a simple global thresholding method to isolate the foreground text. We show the results of our algorithm on some of the most complex word images from the ICDAR 2003 Robust Word Recognition Dataset and compare with previously reported methods.

Abstract

Biometrics have been established to be extremely reliable at the task of identifying individuals and thus are at the core of several real-world systems ranging from employee attendance to access control systems in the military. With growing computing resources available to individuals, biometric authentication systems are being deployed in even wider range of commercial applications. The permanent nature of biometrics raises serious security concerns with these deployments. Also, losing one's biometric trait can compromise that individual's identity in all the systems he is enrolled in. Biometrics are of non-rigid nature, requiring a fuzzy matching process, thus making it difficult to directly borrow popular security techniques used elsewhere with passwords and key-cards. Thus, the research interest received by this field attempts to develop efficient and reliable biometric authentication systems while addressing the issues of security and privacy. Binary biometric representations have been shown to provide significant improvement in efficiency without compromising the system performance for various modalities including fingerprints, palmprints and iris. Hence, this thesis is focused on developing secure and privacy preserving protocols for fixed-length binary biometric templates which use hamming distance as the dissimilarity measure. We propose a novel authentication protocol using a extit{somewhat} homomorphic encryption scheme that provides template protection and ability to use masks while computing the hamming distance. The protocol operates on encrypted data, providing complete biometric privacy to individuals trying to authenticate, only revealing the final matching score to the server. It allows real-time authentication and retains matching accuracy of the underlying representation as demonstrated by our experiments on iris and palmprints. We also propose a one-time biometric token based authentication protocol for widely used banking transactions. In the current scenario, the user is forced to trust the service provider with his sole banking credentials or credit card details for availing desired services. Often used one-time password based systems do provide additional transaction security, however the organizations using such systems are still incapable of differentiating between a genuine user trying to authenticate or an adversary with stolen credentials. Involving biometric security would certainly strengthen the authentication process. The proposed protocol upholds the requirements of secure authentication, template protection and revocability while providing user anonymity from the service provider. We demonstrate our system's security and performance using iris biometrics to authenticate individuals.

Abstract

An e-contract is an electronic version of the conventional contract and provides automated support for e-contracting. More formally, an e-contract is a contract specified, modeled and executed by a software system. Government (large organizations) contracts evolve due to changing context. Workflow management systems proposed for individual process simulations are restricted in their applicability to e-contracts because of their rigid pre-defined process definition and process execution frameworks. Current e-contract enactment systems lack context-awareness and face difficulties in supporting context based changes in workflow specification and execution procedures. Workflow management system needs necessary infrastructure to support contextual enactment of e-contract and exceptions handling that arise during enactment. Meta model based systems proposed provide a guided approach to conceptual modeling and facilitate the design of models for specific domains, such as e-governance, banking, and healthcare. However, most of the proposed meta models are not context based and only parametric driven template based meta-models. These models lack flexibility to adapt to changes to mini-world or run-time changes as well as the capabilities of modeling the exceptions. This necessitates context based meta-model driven approaches that should allow flexibility to suit the needs of modeling specific e-contracts. In this thesis work, we developed a context-aware e-contract enactment system for monitoring and enactment of government contracts. It consists of Context model for easier management of context information. Context model processes context data and provides context information during workflow specification and workflow execution. We develop context driven meta-models, which generates context-based meta execution workflows to drive the execution of e-contracts according to the current context information. Other major components of our system such as contract enactor, contract workflow, and workflow views also help in providing smooth enactment of e-contract by coordinating among themselves. As part of our case study, we have used the e-Government contract for modeling our context-aware e-contract system. We have implemented a prototype based on the architecture and consequently provided the implementation details of the system.

Abstract

Advancement in FPGA technology has enabled deployment of large complex FPGAs in the heart of modern high performance systems as compared to few years back when they were just used for glue lo gic, bridging applications. While custom IPs (Intellectual Property) both soft and hard are commonly used on FPGA to develop system designs, processor based systems are not commonly used or explored enough due to concerns about meeting a right trade -off between area usage, achievable performance, and the required design time. FPGA based designs are challenging as discussed in this thesis especially when the design sizes are big and performance expectations are high. Processor based systems on FPGAs can overcome these challenges if at all they can address the issue of low performance. This work showcases how to develop a multiprocessing system on FPGA using multiple light weight soft processors (LWP). These processors take very less resources, consume less power and are high in performance. They make use of abundantly available hard ened DSP48 blocks on the FPGAs to extract performance and also provide 2 nd level programmability to the designer. The processors can also work in conjunction with a custom hardware to achieve much higher system performance. As an example a TDEA (Triple Data Encryption Algorithm) cryptographic algorithm has been implemented on a multiprocessing system that uses 2.5 x lesser area, is 40% higher in performance, and requires 20% less er power as compared to equivalent solution implemented using a commercial soft processor.

Abstract

Problem of spectrum scarcity has not only affected cellular communication bands but is continuously pushing freely available ISM bands to its limits. Devices which work in ISM band were developed without the consideration of co-existence and interoperability. Proliferation of cheap wireless devices and systems utilizing the ISM band is creating spectrum scarcity in the band which is nonetheless severe compared to cellular communication spectrum scarcity. WSN is one of the systems whose performance is being severely affected by other ISM band systems such as Wi-Fi, Bluetooth etc. Concept of cognitive radio has been applied to WSN in order to opportunistically utilize the freely available licensed bands. This gave origin to cognitive radio based wireless sensor networks (CRWSN). But, existing cognitive radio algorithms such as spectrum sensing, spectrum prediction and spectrum monitoring etc. cannot be applied to CRWSN in their existing forms because of the inherent limitations of CRWSN such as limited battery life, less computational power and implementation issues. In this thesis, we address three problems (i) Efficient Spectrum Sensing Technique for CRWSN (ii) Real Time Spectrum Monitoring technique for CRWSN & (iii) Testbed Development for CRWSN In first part of the thesis, we present an energy and time efficient method of spectrum sensing technique for CRWSN using doubly cognitive architecture (DCA). DCA is based prediction followed by sensing. It predicts not only with respect to time but space also. Hence for CRWSN, which can be highly mobile in nature, DCA is well suited for the task of spectrum sensing. Apart from predicting the primary user spectrum usage pattern, DCA assigns the order of spectrum sensing in case multiple channels are required to be sensed for their vacancy and channel characteristics. We, further enhanced the DCA by adaptive FFT resizing to make it faster and more energy efficient. Adaptive FFT resizing assigns proportionate FFT points to the channels in accordance with their probability of vacancy, while performing the spectrum sensing operation. Our experiments on the CRWSN testbed show that DCA is more efficient with 42% and 19% of average normal spectrum discovery time. In the second part of the thesis, we present a novel method to detect the reappearance of primary user in real time. This method senses a part of the bandwidth of interest in order to capture the primary user reappearance immediately without any significant lag compared to contemporary state of the art methods. Contemporary spectrum monitoring methods suffer from real time detection requirement, unreliable prediction and inefficient bandwidth utilization. Our proposed method of partial sensing based spectrum monitoring successfully addresses all these issues. Additionally, our method is computationally simpler and does not require any additional hardware or software add-on in the existing system in order to deploy it in real time. Our experiments on the CRWSN testbed show that partial sensing-based spectrum monitoring outperforms periodic spectrum monitoring with average PU detection time (3sec.) and variance (1.85), which are significantly reduced to 0.27 and 0.12 times the average of 11 seconds and variance of 15.42 of periodic spectrum monitoring. Time-bandwidth-product of partial spectrum monitoring is found to be 50% more than periodic spectrum monitoring leading to higher bandwidth efficiency.