Ad hoc wireless networks are vulnerable to a wide range of security attacks, due to the ease of the nodes being compromised and the cooperative nature of these networks. A solution approach widely used for defending these networks is behavior-based detection. In this, nodes overhear communications in their neighborhood exploiting the open nature of the wireless medium, and determine if the behaviors of their neighbors are legitimate. An important issue with behavior-based detection that arises in multi-channel ad hoc wireless networks is on which channels monitoring nodes should overhear their neighbors’ communications. ^ In this dissertation, we develop a framework for behavior-based detection in multi-channel ad hoc wireless networks. We are interested in the issue of how to optimally place monitoring nodes and to select channels to tune their radios to. We show that the problem is NP-hard, then develop approximation algorithms. We show that one of our algorithms attains the best approximation ratio achievable among all polynomial-time algorithms. Also, we develop distributed channel assignment algorithms for large-scale and dynamic networks. The distributed nature of the algorithm allows it to scale to large networks. Further, we allow for imperfect detection, where monitoring nodes may probabilistically fail to detect malicious behaviors. For this scenario, we consider providing multiple covers to each node, thereby still maintaining the detection accuracy above a certain level. We evaluate our algorithms for random and scale-free networks and consider optimizations for practical deployment scenarios, such as when the network configuration is changing fast versus a relatively static network.^

Query-based web search is becoming an integral part of many people’s daily activities. Most do not realize that their search history can be used to identify them (and their interests). In July 2006, AOL released an anonymized search query log of some 600K randomly selected users. While valuable as a research tool, the anonymization was insufficient: individuals could be identified from the contents of the queries alone. We propose a client-centered approach based on deniable search: actual user queries are replaced with a set of k queries that hide the actual query. We formalize the definition of Deniable Search and develop two complementary schemes that achieve deniable privacy for web search. ^ In the first approach of Plausibly Deniable Search, cover queries have characteristics similar to the user query but on unrelated topics. The system ensures that any of these k queries will produce the same set of k queries, giving k possible topics the user could have been searching for. We also investigate a system for generating queries automatically by creating clusters of a query log in the semantic space. In the second approach, we ensure that sequences of queries (and cover queries) retain deniability. Real user queries share terms and topics in a sequence as the users refine queries. We extract features from user query logs and use them to generate cover query sequences that have similar properties. We evaluate the methods using a large query log and DMOZ categorized webpages. ^

This dissertation investigates the problem of developing models and mechanisms for user authorization based on uncertain evidence and dynamic trust. The research directions are modeling dynamic trust, modeling uncertain evidence, and integrating them with role assignment for user authorization. ^ A computational trust model rooted in findings from social science is developed. Trusting belief, disposition to trust, and context are represented. Trusting belief in competence is distinguished from that in integrity. Trusting beliefs can be built based on direct experience, reputation, most common belief, and a priori belief. The building process is affected by a truster’s disposition to trust. This research concentrates on developing (1) competence reputation aggregation methods that eliminate the impact of subjectivity and (2) the integrity belief formation method that captures the behavior trend. ^ An evidence statement is designed to enable issuers or parties relying on evidence to express uncertain belief about the evidence. An opinion structure is used to measure the uncertainty. An evidence rewriting rule is developed based on the discounting operator proposed by Shafer. It is used to translate an issuer’s uncertain belief to the belief of the evidence relying party. Three inference methods are devised to address the opinion inference problem raised in user authorization. ^ A role assignment policy definition language is developed. It allows a policy maker to express the evidence and dynamic trust requirements for assigning a role. An evaluation semantic is defined to make role-assignment decisions based on the provided evidence set and policies. A role assignment algorithm is developed based on it. An authorization framework called TERA is developed. It integrates uncertain evidence, dynamic trust, and role assignment, and cooperates with RBAC-enhanced application servers for authorization in open environments. A prototype has been implemented.

Access control is essential for safe and secure access to software and hardware resources. Operating systems, database systems, and other applications employ policies to constrain access to application functionality, file systems, and data. Often these policies are implemented in software that serves as a front end guard to the protected resources or is interwoven with the application. It is important that the access control software is correct in that it faithfully implements a policy it is intended to; hence testing of access control systems becomes critical. The challenge is in devising such testing techniques that are scalable and effective in detecting those faults that can occur in an access control system. ^ In this thesis, we address the problem of generating tests for access control systems. As a solution we first evaluated automata theoretic procedures for test generation using fault models specific to implementations of Role Based Access Control (RBAC) and temporal RBAC (TRBAC) systems. This evaluation led to improved and scalable methods for test generation. In particular the proposed procedures are associated with varying cost and effectiveness for conformance testing of RBAC and TRBAC systems. A probabilistic model for fault coverage is proposed and the fault detection effectiveness of proposed test generation techniques is formally analyzed for a variety of fault distributions. Cost and effectiveness of the proposed procedures in functional testing was evaluated using a case study based on an implementation of RBAC. The proposed test generation procedures provide cost efficient solutions with varying level of fault coverage for conformance testing and thus address the functional correctness requirements of RBAC and TRBAC systems.^

This dissertation seeks to address the sharp increase in public debate about privacy issues, particularly on the issues of Internet privacy, genetic information privacy and the value of personal information, in markets exhibiting adverse selection. The dissertation is divided into three essays. All essays deal with the value of personal information—browsing behavior or genetic information—to firms, and the inherent loss of privacy of the consumer, associated with the release of this information. The first essay looks at privacy in the context of the Internet. The collection of browsing behavior, and forming consumer profiles based on the collected information, is useful to firms, who want to target consumers with a personalized product or service. At the same time, there is an inherent disutility to the consumer because of the collection of browsing behavior and the consequent loss of privacy. We study mechanisms that compensate consumers for their loss of privacy, thus allowing for a better match between personalized products and consumers. In the second essay we study the efficiency implications of privacy laws, on markets that enable trade in personal information. We create an experimental market populated with human agents and artificial agents, who trade in personal information. The setting allows us to test the theoretical predictions obtained in the first essay experimentally. It also allows us to study the impact of stricter privacy regimes on sellers profits, consumer surplus and overall efficiency. The third essay looks at privacy in the context of genetic testing. We study the impact of genetic testing, on a health insurance market. We characterize the existence and nature of insurance contracts when the individual can consent to revealing information, but where the revelation of genetic information is associated with a loss of privacy. We then examine the welfare implications of different policy proposals regarding genetic testing, with the decision of the consumer to take a genetic test and to reveal genetic information, being endogenous. ^

To secure today’s computer systems, it is critical to have different intrusion detection sensors embedded in them. The complexity of distributed computer systems makes it difficult to determine the appropriate choice and placement of these detectors because there are many possible sensors that can be chosen, each sensor can be placed in several possible places in the distributed system, and overlaps exist between functionalities of the different detectors. For our work, we first describe a method to evaluate the effect a detector configuration has on the accuracy and precision of determining the systems security goals. The method is based on a Bayesian network model, obtained from an attack graph representation of the target distributed system that needs to be protected. We use Bayesian inference to solve the problem of determining the likelihood that an attack goal has been achieved, given a certain set of detector alerts. Based on the observations, we implement a dynamic programming algorithm for determining the optimal detector settings in a large-scale distributed system and compare it against a greedy algorithm, previously developed.

The ability to trap the execution of a binary program at desired instructions is essential in many security scenarios such as malware analysis and attack provenance. However, an increasing percent of both malicious and legitimate programs are equipped with anti-debugging and anti-instrumentation techniques, which render existing debuggers and instrumentation tools inadequate. In this paper, we present SPIDER, a stealthy program instrumentation framework which enables transparent, efficient and flexible instruction-level trapping based on hardware virtualization. SPIDER uses invisible breakpoint, a novel primitive we develop that inherits the efficiency and flexibility of software breakpoint, and utilizes hardware virtualization to hide its side-effects from the guest. We have implemented a prototype of SPIDER on KVM. Our evaluation shows that SPIDER succeeds in remaining transparent against state-of-the-art anti-debugging and anti-instrumentation techniques; the overhead of invisible breakpoint is comparable with traditional hardware breakpoint. We also demonstrate SPIDER’s usage in various security applications.

With fast evolving attacks, using software patches for fixing software bugs is not enough as there are often considerable delays in their application to vulnerable systems and the attackers may find other vulnerabilities to exploit. A secure architecture design that provides robust protection against malware must be guided by strong security design principles. In this work, we propose a system design based on the security principles that aim at achieving isolation and reducing attack surface. Our design leverages multi-core architecture to enforce physical isolation between application processes so that a malicious or infected application is unable to affect other parts of the system. Further, we significantly reduce the software attack surface by executing each application on its own customized operating system image that is minimized to only contain code required by the given application.

In software security and malware analysis, researchers often need to directly manipulate binary program—benign or malicious—without source code. A useful pair of binary manipulation primitives are binary functional component extraction and embedding, for extracting a functional component from a binary program and for embedding a functional component in a binary program, respectively. Such primitives are applicable to a wide range of security scenarios such as legacy program hardening, binary semantic patching, and malware function analysis. Unfortunately, existing binary rewriting techniques are inadequate to support binary function carving and embedding. In this paper, we present BISTRO, a system that supports these primitives without symbolic information, relocation information, or compiler support. BISTRO preserves functional correctness of both the extracted functional component and the stretched binary program (with the component embedded) by properly patching them using—interestingly—the same technique and algorithm. We have implemented an IDA Pro-based prototype of BISTRO and evaluated it using real-world Windows software. Our results show that BISTRO performs these primitives efficiently; Each stretched binary program only incurs small time and space overhead. Furthermore, we demonstrate BISTRO’s capabilities in various security applications.

Fine-grained access control for relational data defines user authorizations at the tuple level. Role Based Access Control (RBAC) has been proposed for relational data where roles are allowed access to tuples based on the authorized view defined by a selection predicate. During the last few years, extensive research has been conducted in the area of role engineering. The existing approaches for role engineering are top-down (using domain experts), bottom-up (role-mining), or a hybrid of both. However, no research has been conducted for role engineering in relational data. In this paper, we address this problem. The challenge is to extract an RBAC policy with authorized selection predicates for users given an existing tuple-level fine-grained access control policy. We formulate the problem for relational data, propose a role mining algorithm and conduct experimental evaluation. Experiments demonstrate that the proposed algorithm can achieve up to 400% improvement in performance for relational data as compared to existing role mining techniques.