A. James Clark School of Engineering
Permanent URI for this communityhttp://hdl.handle.net/1903/1654
The collections in this community comprise faculty research works, as well as graduate theses and dissertations.
Browse
17 results
Search Results
Item Advances in Concrete Cryptanalysis of Lattice Problems and Interactive Signature Schemes(2024) Kippen, Hunter Michael; Dachman-Soled, Dana; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Advanced cryptography that goes beyond what is currently deployed to service our basic internet infrastructure is continuing to see widespread adoption. The enhanced functionality achieved by these schemes frequently yields an increase in complexity. Solely considering the asymptotic security of the underlying computational assumptions is often insufficient to realize practical and secure instantiations.In these cases, determining the risk of any particular deployment involves analyzing the concrete security (the exact length of time it would take to break the encryption) as well as quantifying how concrete security can degrade over time due to any exploitable information leakage. In this dissertation, we examine two such cryptographic primitives where assessing concrete security is paramount. First, we consider the cryptanalysis of lattice problems (used as the basis for current standard quantum resistant cryptosystems). We develop a novel side-channel attack on the FrodoKEM key encapsulation mechanism as submitted to the NIST Post Quantum Cryptography (PQC) standardization process. Our attack involves poisoning the FrodoKEM Key Generation (KeyGen) process using a security exploit in DRAM known as “Rowhammer”. Additionally, we revisit the security of the lattice problem known as Learning with Errors (LWE) in the presence of information leakage. We further enhance the robustness of prior methodology by viewing side information from a geometric perspective. Our approach provides the rigorous promise that, as hints are integrated, the correct solution is a (unique) lattice point contained in an ellipsoidal search space. Second, we study the concrete security of interactive signature schemes (used as part of many Privacy Enhancing Technologies). To this end, we complete a new analysis of the performance of Wagner’s k-list algorithm [CRYPTO ‘02], which has found significant utility in computing forgeries on several interactive signature schemes that implicitly rely on the hardness of the ROS problem formulated by Schnorr [ICICS ‘01].Item LOW-POWER AND SECURE IMPLEMENTATION OF NEURAL NETWORKS BY APPROXIMATION(2022) Xu, Qian; Qu, Gang; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Neural networks (NN), one type of machine learning (ML) algorithms, have emerged as a powerful paradigm for sophisticated applications such as pattern recognition and natural language processing. In this dissertation, we study how to apply the principle of approximate computing to solve two challenging problems in neural networks, namely energy efficiency and security. More specifically, we investigate approximation across three stacks in the implementation of NN models: computation units, data storage, and the NN model itself. Computation units, such as adders and multipliers, have been one of the main targets for power-efficient implementation of neural networks. Many low-power approximate adders and multipliers have been proposed. NNs also require complex operations like logarithms, despite the heavy usage and high energy consumption on such operations, they are not optimized for energy efficiency. Our first contribution is a truncation-based approximation method that can balance the computation precision and energy consumption of the popular floating-point logarithmic operation. We derive a formula for the most energy-efficient implementation of the logarithm unit given an error variance range. Based on this theoretical result, we propose BWOLF (Bit-Width Optimization for Logarithmic Function) to determine the bit-width of operands in the logarithms computation in order to minimize the energy consumption in delivering the required computation precision. We evaluate the efficacy of BWOLF in terms of energy savings on two widely used applications: Kullback-Leibler Divergence and Bayesian Neural Network. The experimental results validate the correctness of our analysis and show significant energy savings, from 27.18% to 95.92%, over the full-precision computation and a baseline approximation method based on uniform truncation. Storage approximation by reducing the supply voltage for dynamic random access memory (DRAM) is effective in saving the power for neural networks. However, this will introduce physical errors in DRAM and could impact the performance of NN models. In the second part of this dissertation, we explore the potential of storage approximation in improving NN system’s security in training data privacy. More specifically, we consider the Model Inversion Attacks (MIAs) that extrapolate the training data from model parameters. Our proposed solution -- MIDAS: Model Inversion Defenses with an Approximate memory System -- intentionally introduces memory faults by overscaling voltage to thwart MIA without compromising the original ML model. We use detailed SPICE simulations to build the DRAM fault model and evaluate MIDAS against state-of-the-art MIAs. Experiments demonstrate that MIDAS can effectively protect training data from run-time MIAs. In terms of the Pearson Correlation Coefficient (PCC) similarity between the original training data and the recovered version, MIDAS reduces the PCC value by 55% and 40% for shallow and deep neural networks under 1.5% accuracy relaxation. Although MIDAS shows promising security benefits through storage approximation, such approximation modifies the neural network parameters and may reduce the NN model’s accuracy. In the third part of this dissertation, we propose model approximation which aims at generating an approximate NN model to correct the errors during training and consequently reduce the possible degradation of NN’s classification results. We demonstrate this concept on gradient inversion attacks which utilize transmitted gradients between the nodes in a federated learning system to reconstruct the training data. Therefore, we propose DAGIA, a Data Augmentation defense against Gradient Inversion Attacks, to deliberately extend the training dataset and report the corresponding gradient updates to protect the original data. For multiple data augmentation techniques, we empirically evaluate the trade-off between test accuracy and information leakage to select the best technique for DAGIA. According to the Structural Similarity (SSIM) between reconstructed training data and the original CIFAR-10 dataset, the experimental results show that DAGIA can reduce the SSIM by 54% with a slightly increased test accuracy for the ConvNet model. In summary, this dissertation focuses on the role of approximation in energy efficiency and security during the implementation of neural networks. We show that computation units for complex operators can be approximated to reduce energy, the storage for neural network weights can be approximated to improve both energy efficiency and security (against information leak), and the NN model itself could be approximated during training for security enhancement. This dissertation work demonstrates that approximation is a promising method to improve the performance of neural networks. It opens the door to applying the principle of approximate computing to the implementation and optimization of neural networks where there are abundant opportunities for approximation.Item Machine Learning of Facial Attributes Using Explainable, Secure and Generative Adversarial Networks(2018) Samangouei, Pouya; Chellappa, Rama; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)"Attributes" are referred to abstractions that humans use to group entities and phenomena that have a common characteristic. In machine learning (ML), attributes are fundamental because they bridge the semantic gap between humans and ML systems. Thus, researchers have been using this concept to transform complicated ML systems into interactive ones. However, training the attribute detectors which are central to attribute-based ML systems can still be challenging. It might be infeasible to gather attribute labels for rare combinations to cover all the corner cases, which can result in weak detectors. Also, it is not clear how to fill in the semantic gap with attribute detectors themselves. Finally, it is not obvious how to interpret the detectors' outputs in the presence of adversarial noise. First, we investigate the effectiveness of attributes for bridging the semantic gap in complicated ML systems. We turn a system that does continuous authentication of human faces on mobile phones into an interactive attribute-based one. We employ deep multi-task learning in conjunction with multi-view classification using facial parts to tackle this problem. We show how the proposed system decomposition enables efficient deployment of deep networks for authentication on mobile phones with limited resources. Next, we seek to improve the attribute detectors by using conditional image synthesis. We take a generative modeling approach for manipulating the semantics of a given image to provide novel examples. Previous works condition the generation process on binary attribute existence values. We take this type of approaches one step further by modeling each attribute as a distributed representation in a vector space. These representations allow us to not only toggle the presence of attributes but to transfer an attribute style from one image to the other. Furthermore, we show diverse image generation from the same set of conditions, which was not possible using existing methods with a single dimension per attribute. We then investigate filling in the semantic gap between humans and attribute classifiers by proposing a new way to explain the pre-trained attribute detectors. We use adversarial training in conjunction with an encoder-decoder model to learn the behavior of binary attribute classifiers. We show that after our proposed model is trained, one can see which areas of the image contribute to the presence/absence of the target attribute, and also how to change image pixels in those areas so that the attribute classifier decision changes in a consistent way with human perception. Finally, we focus on protecting the attribute models from un-interpretable behaviors provoked by adversarial perturbations. These behaviors create an inexplainable semantic gap since they are visually unnoticeable. We propose a method based on generative adversarial networks to alleviate this issue. We learn the training data distribution that is used to train the core classifier and use it to detect and denoise test samples. We show that the method is effective for defending facial attribute detectors.Item Security and Energy Efficiency in Resource-Constrained Wireless Multi-hop Networks(2016) Paraskevas, Evripidis; Baras, John S; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In recent decades, there has been a huge improvement and interest from the research community in wireless multi-hop networks. Such networks have widespread applications in civil, commercial and military applications. Paradigms of this type of networks that are critical for many aspects of human lives are mobile ad-hoc networks, sensor networks, which are used for monitoring buildings and large agricultural areas, and vehicular networks with applications in traffic monitoring and regulation. Internet of Things (IoT) is also envisioned as a multi-hop network consisting of small interconnected devices, called ``things", such as smart meters, smart traffic lights, thermostats etc. Wireless multi-hop networks suffer from resource constraints, because all the devices have limited battery, computational power and memory. Battery level of these devices should be preserved in order to ensure reliability and communication across the network. In addition, these devices are not a priori designed to defend against sophisticated adversaries, which may be deployed across the network in order to disrupt network operation. In addition, the distributed nature of this type of networks introduces another limitation to protocol performance in the presence of adversaries. Hence, the inherit nature of this type of networks poses severe limitations on designing and optimizing protocols and network operations. In this dissertation, we focus on proposing novel techniques for designing more resilient protocols to attackers and more energy efficient protocols. In the first part of the dissertation, we investigate the scenario of multiple adversaries deployed across the network, which reduce significantly the network performance. We adopt a component-based and a cross-layer view of network protocols to make protocols secure and resilient to attacks and to utilize our techniques across existing network protocols. We use the notion of trust between network entities to propose lightweight defense mechanisms, which also satisfy performance requirements. Using cryptographic primitives in our network scenario can introduce significant computational overhead. In addition, behavioral aspects of entities are not captured by cryptographic primitives. Hence, trust metrics provide an efficient security metric in these scenarios, which can be utilized to introduce lightweight defense mechanisms applicable to deployed network protocols. In the second part of the dissertation, we focus on energy efficiency considerations in this type of networks. Our motivation for this work is to extend network lifetime, but at the same time maintain critical performance requirements. We propose a distributed sleep management framework for heterogeneous machine-to-machine networks and two novel energy efficient metrics. This framework and the routing metrics are integrated into existing routing protocols for machine-to-machine networks. We demonstrate the efficiency of our approach in terms of increasing network lifetime and maintaining packet delivery ratio. Furthermore, we propose a novel multi-metric energy efficient routing protocol for dynamic networks (i.e. mobile ad-hoc networks) and illustrate its performance in terms of network lifetime. Finally, we investigate the energy-aware sensor coverage problem and we propose a novel game theoretic approach to capture the tradeoff between sensor coverage efficiency and energy consumption.Item Security and Trust in Mobile Ad-Hoc Networks(2015) Jain, Shalabh; Baras, John S; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Distributed ad-hoc networks have become ubiquitous in the current technological framework. Such networks have widespread applications in commercial, civil and military domains. Systems utilizing these networks are deployed in scenarios influencing critical aspects of human lives, e.g.: vehicular networks for road safety, infrastructure monitoring for smart grid or wildlife, and healthcare systems. The pervasive nature of such systems has made them a valuable target for adversarial action. The risk is compounded by the fact that typically the networks are composed of low power, unattended devices with limited protection and processing capabilities. Usage of cryptographic primitives can prove to be a significant overhead in these scenarios. Further, behavioral aspects of participants, that are critical for distributed system operation, are not effectively addressed by cryptography. In this dissertation, we explore the direction of using notions of trust and privacy to address security in these networks. In the first part of the dissertation, we consider the problems of generation, distribution and utilization of trust metrics. We adopt a cross-layer and component based view of the network protocols. We propose schemes operating at the physical layer of the communication stack, to generate trust metrics. We demonstrate that these schemes reliably detect relay adversaries in networks, and can be an effective measure of trust for the neighborhood discovery component. We propose techniques to combine trust from different detectors across multiple layers into a singular trust metric. Further, we illustrate via simulations, the advantages and disadvantages of existing techniques for propagation of local trust metrics throughout the network. We propose modifications to increase the robustness of the semiring based framework for trust propagation. Finally, we consider utilization of trust metrics to increase resilience of network protocols. We propose a distributed trust based framework, to secure routing protocols such as AODV, DSR. We highlight utility of our framework by using the proposed point-to-point link trust metrics. In the second part of the dissertation, we focus on the role of privacy in ad-hoc networks. We demonstrate that for three broad categories of systems; distributed state estimation, distributed consensus and distributed monitoring systems, privacy of context can reduce cryptographic requirements (such as the need for encryption). In fact, efficient methods to preserve privacy can significantly reduce the energy footprint of the overall security component. We define a privacy framework applicable to these scenarios, where the network can be partitioned into a hierarchical structure of critical and non-critical components. We utilize a physical layer watermarking scheme to ensure privacy guarantees in our framework. Further, for systems that lack a natural hierarchical structure, such as information fusion systems, we define an efficient framework to define a hierarchy (network partition), without leaking the structure to the adversary.Item Model Based Optimization and Design of Secure Systems(2013) Malik, Waseem Ansar; Martins, Nuno C; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)ABSTRACT Title of dissertation: MODEL BASED OPTIMIZATION AND DESIGN OF SECURE SYSTEMS Waseem Ansar Malik, Doctor of Philosophy, 2013 Dissertation directed by: Prof. Nuno C. Martins Department of Electrical and Computer Engineering University of Maryland, College Park Dr. Ananthram Swami Computational and Information Sciences Directorate Army Research Laboratory Control systems are widely used in modern industry and find wide applications in power systems, nuclear and chemical plants, the aerospace industry, robotics, communication devices, and embedded systems. All these systems typically rely on an underlying computing and networking infrastructure which has considerable security vulnerabilities. The biggest threat, in this age and time, to modern systems are cyber attacks from adversaries. Recent cyber attacks have practically shut down government websites affecting government operation, undermined financial institutions, and have even infringed on public privacy. Thus it is extremely important to conduct studies on the design and analysis of secure systems. This work is an effort in this research direction and is mainly focused on incorporating security in the design of modern control systems. In the first part of this dissertation, we present a linear quadratic optimal control problem subjected to security constraints. We consider an adversary which can make partial noisy measurements of the state. The task of the controller is to generate control sequences such that the adversary is unable to estimate the terminal state. This is done by minimizing a quadratic cost while satisfying security constraints. The resulting optimization problems are shown to be convex and the optimal solution is computed using Lagrangian based techniques. For the case when the terminal state has a discrete distribution the optimal solution is shown to be nonlinear in the terminal state. This is followed by considering the case when the terminal state has a continuous distribution. The resulting infinite dimensional optimization problems are shown to be convex and the optimal solution is proven to be affine in the terminal state. In the next part of this dissertation, we analyze several team decision problems subjected to security constraints. Specifically, we consider problem formulations where there are two decision makers each controlling a different dynamical system. Each decision maker receives information regarding the respective terminal states that it is required to reach and applies a control sequence accordingly. An adversary makes partial noisy measurements of the states and tries to estimate the respective terminal states. It is shown that the optimal solution is affine in the terminal state when it is identical for both systems. We also consider the general case where the terminal states are correlated. The resulting infinite dimensional optimization problems are shown to convex programs and we prove that the optimal solution is affine in the information available to the decision makers. Next, a stochastic receding horizon control problem is considered and analyzed. Specifically, we consider a system with bounded disturbances and hard bounds on the control inputs. Utilizing a suboptimal disturbance feedback scheme, the optimization problem is shown to be convex. The problem of minimizing the empirical mean of the cost function is analyzed. We provide bounds on the disturbance sample size to compute the empirical minimum of the problem. Further, we consider the problem where there are hard computational constraints and complex on-line optimization is not feasible. This is addressed by randomly generating both the control inputs and the additive disturbances. Bounds on sample sizes are provided which guarantee a notion of a probable near minimum. Model uncertainty is also incorporated into the framework and relevant bounds are provided which guarantee a probable near minimax value. This work finds many applications in miniature devices and miniature robotics. In the final part of this dissertation, we consider a centralized intrusion detection problem with jointly optimal sensor placement. A team of sensors make measurements regarding the presence of an intruder and report their observations to a decision maker. The decision maker solves a jointly optimal detection and sensor placement problem. For the case when the number of sensors is equal to the number of placement points, we prove that uniform placement of sensors is not strictly optimal. We introduce and utilize a majorization based partial order for the placement of sensors. For the case when the number of sensors is less than or equal to six, we show that for a fixed local probability of detection (probability of false alarm) increasing the probability of false alarm (probability of detection) results in optimal placements that are higher on a majorization based partial order.Item Common Randomness Principles of Secrecy(2013) Tyagi, Himanshu; Narayan, Prakash; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation concerns the secure processing of distributed data by multi- ple terminals, using interactive public communication among themselves, in order to accomplish a given computational task. In the setting of a probabilistic multitermi- nal source model in which several terminals observe correlated random signals, we analyze secure distributed data processing protocols that harness the correlation in the data. The specific tasks considered are: computing functions of the data under secrecy requirements; generating secretly shared bits with minimal rate of public communication; and securely sharing bits in presence of a querying eavesdropper. In studying these various secure distributed processing tasks, we adopt a unified approach that entails examining the form of underlying common randomness (CR) that is generated at the terminals during distributed processing. We make the case that the exact form of established CR is linked inherently to the data processing task at hand, and its characterization can lead to a structural understanding of the associated algorithms. An identification of the underlying CR and its decomposi- tion into independent components, each with a different operational significance, is a recurring fundamental theme at the heart of all the proofs in this dissertation. In addition to leading to new theoretical insights, it brings out equivalences between seemingly unrelated problems. Another distinguishing feature of this work is that it considers interactive communication protocols. In fact, understanding the structure of such interactive communication is a key step in proving our results. We make the following contributions. First, we propose a new information theoretic formulation to study secure distributed computing using public communi- cation. The parties observing distributed data are trusted but an eavesdropper has access to the public communication network. We examine distributed communica- tion protocols that allow the trusted parties to accomplish their required computa- tion tasks while giving away negligible information about a specified portion of the data to an eavesdropper with access to the communication. Our theoretical results provide necessary and sufficient conditions that characterize the feasibility of vari- ous secure computing tasks; in many cases of practical importance, these conditions take a simple form and can be verified easily. When secure computing is feasible, we propose new algorithms in special cases. Next, we revisit the problem of generating shared secret keys (SKs). We investigate minimum communication requirements for generating information theo- retically secure SKs of maximum rates from correlated observations using interactive public communication. In particular, our approach allows us to examine the role of interaction in such communication. On the one hand, we find that interaction is not needed when the observed correlated bits are symmetrically correlated and therefore, in this case, simple noninteractive protocols are the most efficient means of generating optimum rate SKs. On the other hand, we illustrate that interactive pro- tocols can require a strictly lower rate of overall communication than noninteractive protocols. Finally, we consider the task of ensuring security against an eavesdropper who makes queries about a portion of the distributed data that the terminals share by communicating over a public network. We introduce an alternative notion of secrecy which requires rendering the task of a querying eavesdropper as onerous as possible. Our main contribution in this part is the development of a new technique for proving converse results for secrecy problems involving CR with interactive communication, which is employed then to obtain an upper bound for the maximum number of queries that can be inflicted on the eavesdropper for any CR and corresponding communication. Surprisingly, there is an equivalence between this notion of secrecy and that of information theoretic security, which leads to new theoretical results for SK generation; for instance, we prove a strong converse for the SK capacity. We conclude by hypothesizing the basic principles of secrecy generation that emerge from the results developed in this dissertation.Item A compiler level intermediate representation based binary analysis system and its applications(2013) Anand, Kapil; Barua, Rajeev; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Analyzing and optimizing programs from their executables has received a lot of attention recently in the research community. There has been a tremendous amount of activity in executable-level research targeting varied applications such as security vulnerability analysis, untrusted code analysis, malware analysis, program testing, and binary optimizations. The vision of this dissertation is to advance the field of static analysis of executables and bridge the gap between source-level analysis and executable analysis. The main thesis of this work is scalable static binary rewriting and analysis using compiler-level intermediate representation without relying on the presence of metadata information such as debug or symbolic information. In spite of a significant overlap in the overall goals of several source-code methods and executables-level techniques, several sophisticated transformations that are well-understood and implemented in source-level infrastructures have yet to become available in executable frameworks. It is a well known fact that a standalone executable without any meta data is less amenable to analysis than the source code. Nonetheless, we believe that one of the prime reasons behind the limitations of existing executable frameworks is that current executable frameworks define their own intermediate representations (IR) which are significantly more constrained than an IR used in a compiler. Intermediate representations used in existing binary frameworks lack high level features like abstract stack, variables, and symbols and are even machine dependent in some cases. This severely limits the application of well-understood compiler transformations to executables and necessitates new research to make them applicable. In the first part of this dissertation, we present techniques to convert the binaries to the same high-level intermediate representation that compilers use. We propose methods to segment the flat address space in an executable containing undifferentiated blocks of memory. We demonstrate the inadequacy of existing variable identification methods for their promotion to symbols and present our methods for symbol promotion. We also present methods to convert the physically addressed stack in an executable to an abstract stack. The proposed methods are practical since they do not employ symbolic, relocation, or debug information which are usually absent in deployed executables. We have integrated our techniques with a prototype x86 binary framework called \emph{SecondWrite} that uses LLVM as the IR. The robustness of the framework is demonstrated by handling executables totaling more than a million lines of source-code, including several real world programs. In the next part of this work, we demonstrate that several well-known source-level analysis frameworks such as symbolic analysis have limited effectiveness in the executable domain since executables typically lack higher-level semantics such as program variables. The IR should have a precise memory abstraction for an analysis to effectively reason about memory operations. Our first work of recovering a compiler-level representation addresses this limitation by recovering several higher-level semantics information from executables. In the next part of this work, we propose methods to handle the scenarios when such semantics cannot be recovered. First, we propose a hybrid static-dynamic mechanism for recovering a precise and correct memory model in executables in presence of executable-specific artifacts such as indirect control transfers. Next, the enhanced memory model is employed to define a novel symbolic analysis framework for executables that can perform the same types of program analysis as source-level tools. Frameworks hitherto fail to simultaneously maintain the properties of correct representation and precise memory model and ignore memory-allocated variables while defining symbolic analysis mechanisms. We exemplify that our framework is robust, efficient and it significantly improves the performance of various traditional analyses like global value numbering, alias analysis and dependence analysis for executables. Finally, the underlying representation and analysis framework is employed for two separate applications. First, the framework is extended to define a novel static analysis framework, \emph{DemandFlow}, for identifying information flow security violations in program executables. Unlike existing static vulnerability detection methods for executables, DemandFlow analyzes memory locations in addition to symbols, thus improving the precision of the analysis. DemandFlow proposes a novel demand-driven mechanism to identify and precisely analyze only those program locations and memory accesses which are relevant to a vulnerability, thus enhancing scalability. DemandFlow uncovers six previously undiscovered format string and directory traversal vulnerabilities in popular ftp and internet relay chat clients. Next, the framework is extended to implement a platform-specific optimization for embedded processors. Several embedded systems provide the facility of locking one or more lines in the cache. We devise the first method in literature that employs instruction cache locking as a mechanism for improving the average-case run-time of general embedded applications. We demonstrate that the optimal solution for instruction cache locking can be obtained in polynomial time. Since our scheme is implemented inside a binary framework, it successfully addresses the portability concern by enabling the implementation of cache locking at the time of deployment when all the details of the memory hierarchy are available.Item TRUST-BASED DEFENSE AGAINST INSIDER PACKET DROP ATTACKS IN WIRELESS SENSOR NETWORKS(2013) Cho, Youngho; Qu, Gang; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In most wireless sensor networks (WSNs), sensor nodes generate data packets and send them to the base station (BS) by multi-hop routing paths because of their limited energy and transmission range. The insider packet drop attacks refer to a set of attacks where compromised nodes intentionally drop packets. It is challenging to accurately detect such attacks because packets may also be dropped due to collision, congestion, or other network problems. Trust mechanism is a promising approach to identify inside packet drop attackers. In such an approach, each node will monitor its neighbor's packet forwarding behavior and use this observation to measure the trustworthiness of its neighbors. Once a neighbor's trust value falls below a threshold, it will be considered as an attacker by the monitoring node and excluded from the routing paths so further damage to the network will not be made. In this dissertation, we analyze the limitation of the state-of-the-art trust mechanisms and propose several enhancement techniques to better defend against insider packet drop attacks in WSNs. First, we observe that inside attackers can easily defeat the current trust mechanisms and even if they are caught, normally a lot of damage has already been made to the network. We believe this is caused by current trust models' inefficiency in distinguishing attacking behaviors and normal network transmission failures. We demonstrate that the phenomenon of consecutive packet drops is one fundamental difference between attackers and good sensor nodes and build a hybrid trust model based on it to improve the detection speed and accuracy of current trust models. Second, trust mechanisms give false alarms when they mis-categorize good nodes as attackers. Aggressive mechanisms like our hybrid approach designed to catch attackers as early as possible normally have high false alarm rate. Removing these nodes from routing paths may significantly reduce the performance of the network. We propose a novel false alarm detection and recovery mechanism that can recover the falsely detected good nodes. Next, we show that more intelligent packet drop attackers can launch advanced attacks without being detected by introducing a selective forwarding-based denial-of-service attack that drops only packets from specific victim nodes. We develop effective detection and prevention methods against such attack. We have implemented all the methods we have proposed and conducted extensive simulations with the OPNET network simulator to validate their effectiveness.Item RANDOM GRAPH MODELING OF KEY DISTRIBUTION SCHEMES IN WIRELESS SENSOR NETWORKS(2011) Yagan, Osman; Makowski, Armand M; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Wireless sensor networks (WSNs) are distributed collections of sensors with limited capabilities for computations and wireless communications. It is envisioned that such networks will be deployed in hostile environments where communications are monitored, and nodes are subject to capture and surreptitious use by an adversary. Thus, cryptographic protection will be needed to ensure secure communications, as well as to support sensor-capture detection, key revocation and sensor disabling. Recently, random key predistribution schemes have been introduced to address these issues, and they are by now a widely accepted solution for establishing security in WSNs. The main goal of the dissertation is to investigate and compare two popular random key predistribution schemes, namely the Eschenauer-Gligor (EG) scheme and the pairwise key distribution scheme of Chan, Perrig and Song. We investigate both schemes through their induced random graph models and develop scaling laws that corresponds to desirable network properties, e.g., absence of secure nodes that are isolated, secure connectivity, resiliency against attacks, scalability, and low memory load - We obtain conditions on the scheme parameters so that these properties occur with high probability as the number of nodes becomes large. We then compare these two schemes explaining their relative advantages and disadvantages, as well as their feasibility for several WSN applications. In the process, we first focus on the "full visibility" case, where sensors are all within communication range of each other. This assumption naturally leads to studying the random graph models induced by the aforementioned key distribution schemes, namely the random key graph and the random pairwise graph, respectively. In a second step, we remove the assumption of full visibility by integrating a wireless communication model with the random graph models induced under full visibility. We study the connectivity of WSNs under this new model and obtain conditions (for both schemes) that lead to the secure connectivity of the