Abstract

Analyzing the dominance relationship amongst points has become an important task in various applications such as tourism industry, sports and movie ranking. The goal of comparing the points in a dataset is not just computing the best points but also to look at interesting sets of points. Skyline queries address the problem of computing the interesting points by suggesting points which are not dominated by any other point in the dataset. In this thesis, we address the problem of computing strong and weak dominant set and dominated set over subsets of dimensions.

Abstract

The Internet is driven by a common internetworking protocol suite called TCP/IP. Within the suite, a network layer protocol named Internet Protocol version 4 (IPv4) exists. IPv4, with 32-bit address fields, was designed without anticipating the forthcoming flood of global community. At the time, the 232 address space was sufficient to support the few users. As the Internet grew with diverse networking demands and technologies, IPv4’s ability to support the size and the demands thereof was surpassed. The latest IANA’s address exhaustion reports project that the end days of unallocated IPv4 address space is a matter of months. Furthermore, the original design assumed trusted users; security was thus hardly an issue. The design favored interoperability over security and did not contain features that protected the confidentiality, integrity or availability of communications. Such incidents as the outbreak of the Morris worm that marked the dawn of a new era of Internet security are prime witnesses. Therefore, addressing these plagues was necessitated. For these nuisances, both short-term and long-term solutions have been put forward. Short-term ’solutions’ such as Classless Inter-Domain Routing (CIDR) and Network Address Translation (NAT) have prolonged the lifetime of IPv4 to some extent. As expected, these are time-bounded and ’patch- and-prolong’ solutions. To address the security issues, a protocol suite named Internet Protocol Security (IPsec) was then introduced to be used optionally,and not as a mandatory feature. On the other hand, IETF’s quest for a long-term solution gave birth to a new and backward-incompatible network layer successor protocol, Internet Protocol version 6 (IPv6). Put simply, IPv6 is the next generation Internet protocol designed to handle the unprecedented growth of the Internet and cope up with the very current networking requirements such as end-to-end security, Quality of Service (QoS), scalability and ubiquity. IPv6 is already gaining global momentum, even in production and mission-critical environments. Nations that did not benefit from the disproportionate IPv4 address allocation (e.g. Asia, Europe) have shifted their gears and efforts towards embracing it to the fullest. Even in parts where IPv4 relatively has a higher life expectancy (e.g. US), the effort is towards catalyzing the transition. For instance, the US federal agencies are mandated to be IPv6-ready from 2008 onwards. The bottom line is that a global migration to the IPv6 Internet is inevitable. IPv6 being on the horizon, studying its security notions is critically important. With increased addi- tion of unimaginable morphs of nodes (e.g. smart home appliances, cars, sensors, body-worn miniature devices, etc) to the Internet and the attacks thereof, the worth of this study can not be emphasized further. In this thesis, we have taken the initial stride of studying the security ramifications of IPv6’s key features, in the hope of laying a foundation for security of the next generation Internet. Generally, the research is centered around the following key objectives: 1. To identify vulnerability points of the protocol as early as possible. 2. To assess some of the proposed solutions in view of the threats identified. 3. To show the road map towards a more secure IPv6 world from the perspective of network protec- tion devices (NPDs) and existing as well as IPv6-specific [projected] security practices. To meet the first two objectives, in part I of the thesis, we have done an extensive threat analysis on prominent features such as Neighbor Discovery, Autoconfiguration, Extension Headers, Mobile IPv6 (MIPv6) as well as on deployment-related aspects like transition mechanisms. For a so-obvious reason, the analysis could not be exhaustive. In addition, we have done a comparative analysis of well-known existing attacks in the light of IPv6. The viability as well as the resistance to potential attacks of some of the proposed solutions such as Secure Neighbor Discovery (SEND), authentication solutions of MIPv6 and automatic IPv6-in-IPv4 tunneling protocols have also been analyzed. In part II of the thesis, we show the road map towards the detection and prevention strategies, in view of the threats analyzed in the preceding part. In this part, the inter IPv6-NPD issues and chal- lenges are explored and assessed in a reasonable detail from the perspective of veteran security devices: packet filters and deep packet inspection devices. Moreover, we present potential futuristic security architectures of the IPv6 world. We also forward recommendations and Best Security Practices (BSPs) based on the threat analysis done. These practices would pretty much serve as a stepping stone for more comprehensive next generational security practices.

Abstract

In a distributed network, where some of the nodes may be corrupt, a sender node s intends to com- municate securely with a distant receiver node r. If the network has sufficient connectivity, a protocol can be designed which enables this communication irrespective of the behaviour of corrupt nodes. In this thesis we consider two very different kinds of networks: synchronous neighbour networks and asynchronous unicast networks. We consider the case where some of the nodes in these networks, whose identities are not known a priori, can behave arbitrarily (or, even maliciously). We investigate the minimum connectivity required to facilitate the design of a protocol which enables a node to com- municate reliably with another node in a network of the former type, and to communicate reliably and privately in a network of the latter type.

Abstract

Synthesis of complex consonant clusters is a challenge in TTS systems, as it is dicult to ensure proper coarticulation. This problem surfaces in the synthesis of missing units in unit concatenation systems. Back-o techniques are used to synthesize these missing units. The current back-o techniques, which use smaller sub-word units to synthesize the missing unit, are found unsuitable for frequent usage causing severe degradation in synthesis quality. However missing units are a frequent occurrence when synthesizing unrestricted text. Hence to build open domain TTS systems, ecient back-o techniques are necessary. This problem is further aggravated when working with under-resourced languages as they lack the manually annotated speech corpora which enable the development of these high quality synthesis techniques. In this thesis we propose a two pronged strategy to improve the quality of back-o techniques. The two pronged strategy consists of rening the boundaries of units in the acoustic inventory to reduce phone insertion errors during back-o and use of a novel back-o technique to ensure coarticulation consistency. A boundary renement algorithm which removes necessity for manually labelled data by relying on a knowledge base of cost functions derived from landmark specic acoustic cues was proposed, to increase the quality of unit boundaries. However increase in accuracy of unit boundaries was insucient when context-dependent units are not available in the database. Hence a back-o technique which synthesizes complex consonant clusters even when the required context-dependent units are not available, was proposed. This technique is motivated from a phenomenon observed during second language acquisition and emulates native speaker intuition in synthesis of these clusters. The technique was proven to be better than the conventional backo  techniques. Further it was proven to be robust to segmentation errors, reducing the reliance on high quality segmentation techniques which require manually labelled data.

Abstract

As the electronics activity is penetrating into various walks of life like electronic governance, banking, reservation systems, the need for higher and higher security in protecting the banking transactions, passwords, PNR numbers, etc. is increasing. The security lapses not only occur through software but also from the hardware circuits that are used for implementing them. One of the methods of breaking the security is through the observations of the pattern of power consumed by the gadget. These methods through which the secured information is obtained are known as Side Channel Attacks (SCA). There is considerable amount of effort that is put in to make the electronic circuits immune to SCA. In this process, bulk of the effort is put in making complementary metal oxide semiconductor (CMOS) circuits immune from these attacks. One of the normal approaches is by having a gate operated with the complementary gate in parallel, like an inverter working in parallel with a buffer, a NAND working in parallel with AND. This combination of circuits may be termed as dual-rail pre-charge (DRP) logic. Because of the additional circuits, the power consumed by the circuit in general gets doubled. So they may not be really suitable for low power applications where the battery life is also important. In view of this, the problem of reducing the power dissipation in DRP logic has been looked at. It has been realized that adiabatic approach is a reasonable method for reducing the power dissipation. In view of this, adiabatic dual-rail inverter-buffer circuit has been built with circuit topology as shown in Figure 4.3. It has been found that this circuit works properly as an inverter, as a buffer and also results in considerable reduction in power dissipation. The current drawn from the power supply has a pattern which is independent of the input signal (0 to 1 or 1 to 0 transitions). Further it has been observed that the input and output logic levels are the same which indicates that these circuits are cascadable. In view of this, it has been concluded that it is possible to realize low power secure circuits based on adiabatic dual-rail approach. To examine whether large scale secure systems can be built with this approach, the universal logic gates, NAND and NOR have been constructed on the lines similar to CMOS NAND, NOR with adiabatic approach. In these circuits there have been certain current patterns that emerged depending on the input signal. This difference in the pattern has been identified to be due to the number of transistors which are in the ON state are different for different input signals. This problem has been overcomed by carefully analyzing the transistors that are put ON for each of the input condition and by balancing the resistances for all the inputs. This called for incorporating additional transistors in some branches. With this balancing technique and adiabatic approach, it has been possible to realize low power secure NAND and NOR gates. Even these gates have the same input and output logic levels which make them suitable for cascadable circuits. Thus it is clearly established that using the dual-rail adiabatic approach, secure digital circuits can be built. Even though cascadability of the individual secure logic gates have been established, when the circuits are really cascaded, it is possible that the currents drawn may depend upon the logic functions that are executed (based on the gates that are used). To avoid this problem, the circuits have been modified to have a structure in which there is always a current drawn by each of the gates for each operation of the signal. This is done by incorporating pre-charge and evaluation steps in these circuits. Using this approach, all the gates (Inverter-Buffer, AND-NAND, OR-NOR, XOR-XNOR) are constructed and it is observed that the current patterns are input independent and a significant amount of power reduction is observed when compared to the existing secure logic styles. Hence, low power secure logic style has been established.

Abstract

A roof with an ability to reflect and emit the sun‘s heat back to the sky instead of transferring it to the buildings is said to be a cool roof. It has high solar reflectance and thermal emittance values. Cool roofs are one of the important energy conservation measures in buildings in countries like India. This thesis presents an assessment of the energy savings potential of cool roof through the analysis of experimental results, and through simulations. Further, a tool has been developed to calculate energy savings, payback and thermal comfort due to cool roof. The work also includes a survey of cool roof in historical and present day context of India, and a field study of performance of various cool roof materials. A survey of various cool roof technologies available across India was done. The study shows the importance of cool roof in historical architecture of India, the current trends, and its relevance in codes and rating systems. Further, several cool roof materials were installed on field, and were tested for performance over a year. From this, it has been observed that ceramic tiles though provide lesser savings compared to the white elastomeric coatings; they tend to have longer life providing a good payback over time. The work includes analysis of the raw data of a parallel experiment conducted in two typical buildings in Hyderabad by IIIT Hyderabad in collaboration with LBNL- USA. The collected data has been analysed based on the operating hours of the building, and the calculated average savings ranged between 0.066-0.072 kWh/m2/day. The work also includes the development of an online cool roof calculator. This cool roof calculator provides the energy savings, payback and thermal comfort achieved due to cool roof for the user specified building parameters and for the specified city. The calculator can be accessed at: http://coolroof.cbs.iiit.ac.in/index.html . This is the first of its kind tool, which performs online simulation using EnergyPlus for all available Indian weather files. Lastly, cool roof was analysed in combination with roof insulation. The impact of cool roof on requirement of roof insulation in office buildings was understood through simulations. Results showed that the savings achieved by increasing the thickness of insulation, has diminishing returns, and the insulation has negligible effect on cooling electrical energy consumption in case of roof with high solar reflectivity. Especially, roofs with very high solar reflectivity values of 0.7 and 0.8, adding roof insulation might increase the cooling energy consumption. This study also suggests that the recommendation by the Energy Conservation Building Code of India for the prescriptive method is to be revisited.

Abstract

There has been a continuous pressure on VLSI chip manufacturing industry to increase the manufacturing yield. Integrated circuit manufacturers are constantly trying to decrease the number of faulty parts they produce. The reliability of System on Chips must be ensured to a certain extent since a single fault is likely to make the whole chip useless. VLSI testing is the backbone of manufacturing reliable integrated circuits. Therefore, fault diagnosis and fault repairing techniques are gaining importance these days. A manufacturer may be able to improve the circuit design or the manufacturing process by analyzing the parts that fail production tests and determining the cause of failure for each part. During the design as well as manufacturing several faults may creep in. Therefore there is a need to test the VLSI chips at the design level as well as after manufacturing. Detection of fault and the type of fault present in a circuit is known as fault diagnosis. With increase in the complexity of the integrated circuits the effort to detect and diagnose the fault is becoming time consuming and demanding more and more resources. There has been continuous effort to develop methods of testing ICs, more efficiently and with less effort. This activity encompasses: 1) Development of methodologies for testing 2) Model the faults 3) Evaluate the effect of the fault on the performance and 4) Diagnosing the fault from the change in performance. With the growth of IC technology and with the advent of reconfigurable circuits like FPGAs, PLAs, PLDs etc. testing only for faulty chip is not adequate. Fault location may be required to identify and then replace or discard the faulty sub-circuit. It can also be used to analyze the defect causing the faulty behavior. Fault diagnosis is executed upon manufactured chips, which are found to be faulty in order to identify the position and types of the faults present in them. This thesis is devoted to new methods of identifying (locating) faults in a conventional IC as well as in programmable ICs like FPGAs. An exhaustive test pattern set for a modern VLSI circuit could result into a hundred million or more vectors. The amount of time that each circuit requires for testing is also an important factor in determining the overall test cost. In order to reduce the test application cost it is important to keep the number of test patterns to a minimum. In this thesis the trade-off between fault coverage and the number of test vectors is studied. A faster algorithm named POTG (Position Oriented Test Generation) algorithm has also been proposed to get the minimum number of test vectors which covers high fault coverage for testing of ASIC designs. There are two types of fault diagnosis which differ in the way they are pre-computed. i) Dictionary based approach which uses a pre-computed dictionary that contains information about the faults and the test vectors. ii) Dynamic or fault simulation based approach which generally does not use any pre-computed information. In this thesis we have used dictionary based approach for fault diagnosis. CONE partitioning technique is used for generation of test vectors in bigger circuits (whose input vector is greater than 22 bits). A modified fault dictionary is prepared that is used to minimize the effort in fault location. For location of a fault a new fault dictionary is proposed in which fault vs test vectors is stored and each test vector is assigned weightage (the number of faults it can detect). The proposed POTG algorithm has two parts: first, generation of optimized fault dictionary, and then usage of this fault dictionary. POTG algorithm essentially finds the intersection of the faults and finally arrives at the minimum number of vector that is needed for locating a particular fault. This modified dictionary also gives a heuristic approach to minimize the number of test vectors required for testing the chip with some trade-off with fault coverage. This proposed algorithm is faster in locating a fault in a chip compared to other classical fault location technique. The effectiveness of this POTG algorithm is checked by applying it to ISCAS’85 Benchmark circuits c432, c499, c880, c1355. There is an increase similar to logarithmic increase in the probability of fault location with the increase in test vectors used. Thus a small drop in fault coverage may results in huge reduction in number of test vectors. For example for circuit c432, 96% of the faults can be located with only 56 test vectors, otherwise for 100% fault coverage we have to apply 240 test vectors. This algorithm takes O (|F| * log2|T|) which is faster in locating a fault compared to those which uses classical fault dictionary which takes O (|F|*|T|*log2|F|) time. Thus the POTG algorithm which is developed enables location of the faults effectively with considerably less effort. Testing an FPGA chip poses a challenging problem for test engineers. A modified BIS

Abstract

Visual representations are ubiquitous in modern day science textbooks and have become an object of much research in recent years. Since textbooks are a primary source of content information in most science classrooms it is therefore particularly important to understand how students integrate words and figures in textbook style learning materials. The quality and utility of visual representations has been subject to much debate. In order to improve design of the instructional material visual representations which make up one third to one half of every page in a science textbook need to be studied in greater depth so that the these visual representations are productive to the learning of scientific ideas.
The research in this dissertation is centered on three parameters of visual representations. The text that is present within visual representation, and how color plays a vital role in information recall. The second parameter studied is the various categories of the visual representations and their effect on different types of learning outcomes. This study focuses on what type of visual representation should accompany the text so that it provides the best support for the learning of scientific ideas. The third study focuses on the placement of the visual representation with respect to the corresponding text. Studying the text –illustration proximity to find out if learning outcome is effected by the placement of the visual representation helps provide insight about learning behaviors and leads to an improved design of instructional material. The results from the three empirical studies help provide useful recommendations to instructional material designers. Modest modifications in the ways that visual representations are presented in textbooks could greatly improve students’ comprehension.

Abstract

Severe Acute Respiratory Syndrome is a respiratory illness that affected more than 8000 patients and caused around 774 deaths in 26 countries, within its first year of emergence. This disease has an average mortality rate of 10% and is caused by an enveloped, single-stranded positive sense RNA (Ribose Nucleic Acid) Corona-virus (Co-V) known as Severe Acute Respiratory Syndrome Corona-virus (SARS-CoV) that has the capacity for human-to-human transmission. In April 2003, the genome of this virus was completely sequenced. The 29.7 kb long genome reveals that the SARS-CoV bears no resemblance to any existing corona-virus, and contains 14 putative open reading frames (ORFs) out of which 6 major ORFs encode the two replicase poly-proteins and four structural proteins; the spike glycoprotein, envelope protein, membrane protein and helical nucleocapsid protein, and the remaining 8 ORFs for unknown proteins. Though the lifecycle of the SARS-CoV is believed to follow that of other corona-virus i.e., release of genetic material into the cytoplasm of the host cell where it directs the production of new virus genetic material and virus proteins, the exact steps and details of the proteins involved are largely unknown. Identification and characterization of new functional proteins from the ORFs will be helpful for understanding the pathogenesis of SARS-CoV. Up till now there are no effective drugs or vaccines against SARS-CoV. The identification of new viral proteins and the understanding of their functions will provide potential targets for design of drugs or vaccines against SARS. The detection of the 3a gene product in SARS-CoV infected cells and in the lungs of SARS patients confirms that the ORF 3a of the SARS-CoV encodes an accessory protein consisting of 274 a.a. that lacks any significant similarities to any known protein. Though the putative full length sequence of 3a protein lacks sequence homology to any other known proteins, topology prediction of 3a proteins based on amino acid (a.a.) sequences suggests that 3a is a type-III transmembrane protein with multi trans-membrane domains. The interaction of the 3a protein with the spike protein suggests that one of the intracellular roles of 3a is to mediate intracellular trafficking of the spike protein in SARS-CoV infected cells. Although the biological role of the 3a protein remains unclear, it is known that 3a also interacts with the membrane protein, envelope protein and genes that are involved in multiple cellular processes. This suggests that the 3a protein functions as both a viral regulatory protein and as a structural protein in infected cells and mature viral particles respectively. Though a contemporary work showed that 3a is a trans-membrane protein that is capable of forming an ion-channel, the exact structure or the process of homo-merization is unknown. The functions of ion-channels vary among one another and a deeper understanding of the ion-channel activity of 3a proteins will help in elucidating its role in viral lifespan and pathogenesis. Further studies on modulation of virus release mediated by 3a protein will provide new prospects to the understanding of the pathogenesis of the SARS-CoV (and other corona-viruses) as well as can serve as a potential target for therapeutic developments. Protein modelling studies have been carried out on the 3a protein. Three-dimensional structures were modelled from the primary sequence of the 3a protein and then evaluated based on non-bonded interactions, RMSD calculations and solvent accessible surface area computations. These studies help in understanding the possible structure of 3a and its ability to function as an ion-channel. The reliability of the structures was also evaluated using graph spectral analysis (Generally mutation studies are conducted on individual amino acids to identify the critical residues that significantly contribute to the structure and thus function of the protein). Centrality measures of a vertex (i.e. amino acid residue) helps in determining the relative importance of a vertex within the graph (protein structure). Degree centrality, betweenness, eigenvector centrality and graph density were calculated for the proposed models to understand their compactness and to identify the critical residues within a model and common to all models. These critical residues can serve as sites for drug targeting.

Abstract

Present day computing systems deal with calculations involving large range of numbers. One of the ways by which such a wide number range can be provided is through the use of floating point format for number representation. Among the floating point operations, floating point multiplication has been a very power hungry operation, having the maximum share in the power consumption in most of the applications. With the advent of mobile devices which have a fixed power budget, there is a need for investigation of low power designs for a floating point multiplier to trim down the power consumption of the whole system. The work presented in this thesis aims at exploring techniques which can be used to reduce the power consumed in a single precision floating point multiplier. We apply a combination of truncation and voltage scaling in the mantissa multiplier to achieve power savings and implement redundancy in the exponent calculation to attain error resilience. With the scaling of technology and the supply voltage of CMOS transistors, it has been predicted that noise will affect the correct functioning of circuits in the future technology nodes. This will lead to computations which may not be deterministic but probabilistic. In such a scenario, the technique of voltage scaling will lead to increased errors due to further reduction of the noise margin. One of the methods by which the effect of the reduced noise margin can be modeled is through introduction of random or Gaussian noise along with the signals. This noise introduction results in erroneous calculation which is referred to as probabilistic computation in this thesis. Each of the low power techniques used (truncation and voltage scaling) lead to power savings at the cost of errors in the computations. Hence, we apply these low power techniques in the mantissa calculation of the floating point multiplier because it is less significant as compared to the other calculations (exponent and sign) and is also the most power consuming calculation of the floating point multiplier. This is done to achieve maximum power savings at the cost of introducing some errors as far as the multiplication result is concerned. We also make the exponent calculations less error prone by implementing redundancy in the exponent block. This leads to substantial error reduction with very nominal increase in power, thereby keeping the overall error in the results low. By the low power techniques and redundancy we realize a multiplier design with error tolerance and considerable power savings. It is then demonstrated that sizeable amount of power savings can be achieved in a Ray Tracing application by replacing a subset of the deterministic multiplications by probabilistic multiplications. This was achieved at the cost of negligible degradation in the quality of the output image generated.