Online intrusion detection systems (IDSs), i.e., tools for detecting live cyberattacks in the form of unauthorized access gained to a (networking) system, play a role of paramount importance in the cybersecurity landscape. Among the plethora of existing IDSs, the ones based on temporal graph anomaly detection (TGAD) process a temporal graph representing entities of interest of the underlying system and time-varying relationships among them, and identify anomalous temporal edges in such a graph as potential intrusions. TGAD-based IDSs are superior to various other existing types of IDS for their peculiarities of high generality and powerfulness in data representation and types of cyberattack identifiable. However, existing TGAD-based IDSs are still far from being suitable for real-world settings, due to their severe limitations in efficiently and effectively handling the underlying temporal graphs, which are typically really big. In this paper, we devise CAPTOR (“Cyber Attack Protection via Temporal Online graph Representation learning”), a novel TGAD-based IDS which addresses the limitations of the state of the art. CAPTOR consists of a careful selection and clever combination of graph representation learning (GRL), TGAD, and temporal aggregation of GRL representations (embeddings). These design choices make CAPTOR achieve the best tradeoff between accuracy and scalability in TGAD-based intrusion detection, as testified by extensive experiments on real cybersecurity datasets. As such, with this work we take a significant step forward towards rendering the important TGAD-based IDS technology actually applicable in real-world cybersecurity scenarios.

Adversarial attacks pose significant challenges to deep neural networks (DNNs) such as Transformer models in natural language processing (NLP). This article introduces a novel defense strategy, called GenFighter , which enhances adversarial robustness by learning and reasoning on the training classification distribution. GenFighter identifies potentially malicious instances deviating from the distribution, transforms them into semantically equivalent instances aligned with the training data, and employs ensemble techniques for a unified and robust response. By conducting extensive experiments, we show that GenFighter outperforms state-of-the-art defenses in accuracy under attack and attack success rate metrics while maintaining the same or superior generalization capabilities. Additionally, it requires a high number of queries per attack, making the attack more challenging in real scenarios. Finally, The ablation study shows that our approach proficiently integrates transfer learning, a generative/evolutive procedure, and an ensemble method, providing an effective defense against NLP adversarial attacks.

Health care providers may wish to share limited information with researchers. Manufacturing companies may want to share some but not all data with regulators or partners. Since the emergence of generative adversarial networks (GANs), efforts have been made to generate synthetic data that preserves semantic properties on the one hand and distributions on the other hand. However, all past efforts focus on a single table at a time. We propose${\sf FakeDB}$, a general framework to generate synthetic data that preserves a a wide variety of semantic integrity constraints as well as a broad set of statistical properties, across an entire relational database. We compare${\sf FakeDB}$with natural extensions of prior work on 8 well known relational databases as well as on a synthetically generated dataset, and show that${\sf FakeDB}$outperforms them. We also show that${\sf FakeDB}$runs in reasonable amounts of time, making it a practical solution to the problem of generating synthetic data.

Months may pass before the victim of IP theft even knows they have been compromised. During this time, the attacker can exfiltrate large amounts of data. Recent work has proposed the idea of injecting a set of believable fake versions of a real document into a network so that the attacker has to expend time and effort to identify the real document from a sea of similar documents. In this paper, we consider the problem of an attacker who is smart and breaks a technical document down into small, bit-sized “units” and inspects them one by one so as to defeat the fake document defense. If a unit in a document is determined to be fake, the adversary does not need to look further at the same document. He can also immediately identify as fake, any other document that contains the same unit. In this paper, we consider the problem of a smart attacker using this strategy. Our proposed defensive algorithm, called${\sf GAIT}$, is shown to be successful in mitigating such attacks.${\sf GAIT}$can work in conjunction with any NLP-based generative method to create fake technical documents.

With the rise of smart working and recent global events, the risk of cyberattacks is increasing steadily. Sometimes adversaries focus on stealing valuable data, such as intellectual property (IP): they exfiltrate a large volume of IP documents from a target company. They then identify those of their interest by leveraging automated methods. This work proposes the DARD (Deceptive Approaches for Robust Defense against IP theft) system, a framework designed to deceive adversaries who rely on automatic approaches to classify exfiltrated documents. Starting from an original repository of documents, DARD automatically generates a new deceptive repository that misleads popular automatic approaches, resulting in clusters of documents that are significantly different from the actual ones. By utilizing this approach, DARD aims to hinder the accurate clustering and the identification of the topic of documents by adversaries relying on automated techniques. The paper presents four deceptive operations (Basic Shuffle, Shuffle increment, Shuffle reduction, and Change topic) that DARD leverages to create a deceptive repository. We evaluate the efficacy of our approach by considering three different types of adversaries, each possessing varying levels of knowledge and expertise. Through extensive experiments, we show that the DARD system can deceive both automatic topic modeling and document clustering techniques, including widely-used commercial tools such as Amazon Comprehend. Hence, our solution provides a robust defense mechanism against Intellectual Property (IP) theft.

The coronavirus pandemic has fostered an explosion of misinformation about the disease, including the risk and effectiveness of vaccination. AI tools for automatic Scientific Claim Verification (SCV) can be crucial to defeat misinformation campaigns spreading through social media channels. However, over the past years, many concerns have been raised about the robustness of AI to adversarial attacks, and the field of automatic SCV is not exempt. The risk is that such SCV tools may reinforce and legitimize the spread of fake scientific claims rather than refute them. This article investigates the problem of generating adversarial attacks for SCV tools and shows that it is far more difficult than the generic NLP adversarial attack problem. The current NLP adversarial attack generators, when applied to SCV, often generate modified claims with entirely different meaning from the original. Even when the meaning is preserved, the modification of the generated claim is too simplistic (only a single word is changed), leaving many weaknesses of the SCV tools undiscovered. We propose T5-ParEvo, an iterative evolutionary attack generator, that is able to generate more complex and creative attacks while better preserving the semantics of the original claim. Using detailed quantitative and qualitative analyses, we demonstrate the efficacy of T5-ParEvo in comparison with existing attack generators.

With the increasing popularity of open-source software, embedded vulnerabilities have been widely propagating to downstream software. Due to different maintenance policies, software vendors may silently release security patches without providing sufficient advisories (e.g., CVE). This leaves users unaware of security patches and provides attackers good chances to exploit unpatched vulnerabilities. Thus, detecting those silent security patches becomes imperative for secure software maintenance. In this paper, we propose a graph neural network based security patch detection system named GraphSPD, which represents patches as graphs with richer semantics and utilizes a patch-tailored graph model for detection. We first develop a novel graph structure called PatchCPG to represent software patches by merging two code property graphs (CPGs) for the pre-patch and post-patch source code as well as retaining the context, deleted, and added components for the patch. By applying a slicing technique, we retain the most relevant context and reduce the size of PatchCPG. Then, we develop the first end-to-end deep learning model called PatchGNN to determine if a patch is security-related directly from its graph-structured PatchCPG. PatchGNN includes a new embedding process to convert PatchCPG into a numeric format and a new multi-attributed graph convolution mechanism to adapt diverse relationships in PatchCPG. The experimental results show GraphSPD can significantly outperform the state-of-the-art approaches on security patch detection.

The availability of a multitude of data sources has naturally increased the need for subjects to collaborate for supporting distributed computations that combine different data collections for their elaboration and analysis. Due to the quick pace at which datasets grow, often the authorities collecting and owning such datasets resort to external third parties (e.g., cloud providers) for their storage and management. Data under the control of different authorities are autonomously encrypted (using different encryption schemes and keys) for their external storage. This makes distributed computations combining these sources difficult to support. In this paper, we propose an approach enabling collaborative computations over data encrypted in storage, selectively involving also subjects that might not be authorized for accessing the data in plaintext when their collaboration is considered economically convenient. We also consider the possible adoption of trusted hardware components, to enable the evaluation of operations over plaintext data at non-fully trusted computational providers. The experimental results confirm the economic benefits that can be enabled by our proposal.

Distributed computing supports large scale and data-intensive computations with the cooperation of a multitude of parties, each responsible for a portion of the workload. Such parties are often not fully reliable and may return incorrect results. In this article, we address the problem of assessing the integrity of the computation results. We provide a comprehensive characterization of two techniques,sentinelsandtwins, evaluating their effectiveness and synergy. Sentinels are pre-computed tasks whose result is known apriori, and enable checking returned results against a ground truth. Twins are replicated tasks assigned to different workers, and enable cross-checking returned results for a same task. The analysis considers many questions that arise in the design of a concrete integrity assessment strategy and identifies the parameters that have a critical impact on the overall protection. Our model enables to tune the integrity controls so to achieve best effectiveness. The model can be applied to a variety of scenarios and offers guidelines that can find extensive application.

A Cybersecurity Operations Center (CSOC) performs various tasks to protect an organization from cyber threats. Several types of personnel collaborate to function effectively as a team to analyze the threat signals, in the form of alerts, arriving from various sources. Teams are often formed ad hoc, resulting in an imbalance in their performances and thereby increasing the risk associated with the low-performing teams. The current approach taken by behavioral scientists in forming effective teams focuses on first qualitatively assessing individuals such as analysts, who are then grouped into teams based on their credentials and expertise. Our work takes a holistic view of the CSOC by first defining team requirements and then selecting individuals to form several collaborative teams that meet these requirements for every shift of operation. We present a novel team formation framework that integrates optimization, simulation, and scoring methods to form effective teams and introduce a new collaborative score metric that measures their effectiveness. Results from simulated experiments show the formation of effective teams whose collaborative scores are maximized and balanced. Our approach is also able to identify high and low performers within the first few months of implementing the framework.

Tabular data typically contains private and important information; thus, precautions must be taken before they are shared with others. Although several methods (e.g., differential privacy and k-anonymity) have been proposed to prevent information leakage, in recent years, tabular data synthesis models have become popular because they can well trade-off between data utility and privacy. However, recent research has shown that generative models for image data are susceptible to the membership inference attack, which can determine whether a given record was used to train a victim synthesis model. In this paper, we investigate the membership inference attack in the context of tabular data synthesis. We conduct experiments on 4 state-of-the-art tabular data synthesis models under two attack scenarios (i.e., one black-box and one white-box attack), and find that the membership inference attack can seriously jeopardize these models. We next conduct experiments to evaluate how well two popular differentially-private deep learning training algorithms, DP-SGD and DP-GAN, can protect the models against the attack. Our key finding is that both algorithms can largely alleviate this threat by sacrificing the generation quality.

Account recovery (usually through a password reset) on many websites has mainly relied on accessibility to a registered email, due to its favorable deployability and usability. However, it makes a user's online accounts vulnerable to a single point of failure when the registered email account is compromised. While previous research focuses on strengthening user passwords, the security risk imposed by email-based password recovery has not yet been well studied. In this article, we first conduct a measurement study to characterize the password recovery activities in the wild. Specifically, we examine the authentication and password recovery protocols from 239 traffic-heavy websites, confirming that most of them use emails for password recovery. We further scrutinize the security policy of leading email service providers and show that a significant portion of them takes no or marginal effort to protect user email accounts, leaving compromised email accounts readily available for mounting password recovery attacks. Then, we conduct case studies to assess potential losses caused by such attacks. Finally, we propose and implement a lightweight email security enhancement called Secure Email Account Recovery (SEAR) to defend against password recovery attacks by adding an extra layer of protection to password recovery emails.

According to Symantec, the average gap from the time a company is compromised by a zero-day attack to the time the vulnerability is discovered is 312 days. This leaves an adversary with a lot of time to exfiltrate corporate IP. Recent work has suggested automatically generating multiple fake versions of a document to impose costs on the attacker who needs to correctly identify the original document from a set of mostly fake documents. But in the real world, documents contain many diverse components. In this article, we focus on technical documents that often contain equations. We present${\sf FEE}$(Fake Equation Engine), a framework to generate fake equations in such documents.${\sf FEE}$tries to preserve multiple aspects of a given equation when generating a fake. Moreover,${\sf FEE}$is very general and applies to diverse equational forms including polynomial equations, differential equations, transcendental equations, and more.${\sf FEE}$iteratively solves a complex, changing optimization problem inside it. We also present${\sf FEE-FAST}$, a fast approximate algorithm to solve the optimization problem within${\sf FEE}$. Using a panel of human subjects, we show that${\sf FEE}$achieves a high rate in deceiving sophisticated subjects.

We propose PCAM , a Probabilistic Cyber-Alert Management framework, that enables chief information security officers to better manage cyber-alerts. Workers in Cyber Security Operation Centers usually work in 8- or 12-hour shifts. Before a shift, PCAM analyzes data about all past alerts and true alerts during the shift time-frame to schedule a given set of analysts in accordance with workplace constraints so that the expected number of “uncovered” true alerts (i.e., true alerts not shown to an analyst) is minimized. PCAM achieves this by formulating the problem as a bi-level non-linear optimization problem and then shows how to linearize and solve this complex problem. We have tested PCAM extensively. Using statistics derived from 44 days of real-world alert data, we are able to minimize the expected number of true alerts that are not manually examined by a team consisting of junior, senior, and principal analysts. We are also able to identify the optimal mix of junior, senior, and principal analysts needed during both day and night shifts given a budget, outperforming some reasonable baselines. We tested PCAM ’s proposed schedule (from statistics on 44 days) on a further 6 days of data, using an off-the-shelf false alarm classifier to predict which alerts are real and which ones are false. Moreover, we show experimentally that PCAM is robust to various kinds of errors in the statistics used.

Security patches, embedding both vulnerable code and the corresponding fixes, are of great significance to vulnerability detection and software maintenance. However, the existing patch datasets suffer from insufficient samples and low varieties. In this paper, we construct a large-scale patch dataset called PatchDB that consists of three components, namely, NVD-based dataset, wild-based dataset, and synthetic dataset. The NVD-based dataset is extracted from the patch hyperlinks indexed by the NVD. The wild-based dataset includes security patches that we collect from the commits on GitHub. To improve the efficiency of data collection and reduce the effort on manual verification, we develop a new nearest link search method to help find the most promising security patch candidates. Moreover, we provide a synthetic dataset that uses a new oversampling method to synthesize patches at the source code level by enriching the control flow variants of original patches. We conduct a set of studies to investigate the effectiveness of the proposed algorithms and evaluate the properties of the collected dataset. The experimental results show that PatchDB can help improve the performance of security patch identification.

We consider surveillance of a geographic region by a collaborative system of drones. The drones assist each other in identifying and managing activities of interest on the ground. We also consider an adversary who can create both genuine and fake activities on the ground. The objective of the adversary is to use fake activities, in order to maximize the response time to genuine activities. We present two collaboration algorithms and analyze their response times, as well as the adversary's efforts in terms of the number of fake activities required to achieve a certain response time.

Graph synthesis is a long-standing research problem.Many deep neural networks that learn about latent characteristics of graphs and generate fake graphs have been proposed.However, in many cases their scalability is too high to be used to synthesize large graphs.Recently, one work proposed an interesting scalable idea to learn and generate random walks that can be merged into a graph.Due to its difficulty, however, the random walk-based graph synthesis failed to show state-of-the-art performance in many cases.We present an improved random walk-based method by using negative random walks.In our experiments with 6 datasets and 8 baseline methods, our method shows the best performance in almost all cases.We achieve both high scalability and generation quality.

Today, major corporations and government organizations must face the reality that they will be hacked by malicious actors. In this paper, we consider the case of defending enterprises that have been successfully hacked by imposing additional a posteriori costs on the attacker. Our idea is simple: for every real document $d$ d , we develop methods to automatically generate a set $Fake(d)$ F a k e ( d ) of fake documents that are very similar to $d$ d . The attacker who steals documents must wade through a large number of documents in detail in order to separate the real one from the fakes. Our $\mathsf {FORGE}$ FORGE system focuses on technical documents (e.g., engineering/design documents) and involves three major innovations. First, we represent the semantic content of documents via multi-layer graphs (MLGs). Second, we propose a novel concept of “meta-centrality” for multi-layer graphs. A meta-centrality (MC) measure takes a classical centrality measure (for ordinary graphs, not MLGs) as input, and generalizes it to MLGs. The idea is to generate fake documents by replacing concepts on the basis of meta-centrality with related concepts according to an ontology. Our third innovation is to show that the problem of generating the set $Fake(d)$ F a k e ( d ) of fakes can be viewed as an optimization problem. We prove that this problem is NP-complete and then develop efficient heuristics to solve it in practice. We ran detailed experiments on two datasets: one a panel of 20 human subjects, another with a panel of 10. Our results show that $\mathsf {FORGE}$ FORGE generates highly believable fakes.

The concept of attack surface has seen many applications in various domains, e.g., software security, cloud security, mobile device security, Moving Target Defense (MTD), etc. However, in contrast to the original attack surface metric, which is formally and quantitatively defined for a software, most of the applications at higher abstraction levels, such as the network level, are limited to an intuitive and qualitative notion, losing the modeling power of the original concept. In this paper, we lift the attack surface concept to the network level as a formal security metric for evaluating the resilience of networks against zero day attacks. Specifically, we first develop novel models for aggregating the attack surface of different network resources. We then design heuristic algorithms to estimate the network attack surface while reducing the effort spent on calculating attack surface for individual resources. Finally, the proposed methods are evaluated through experiments.

Recommender systems have been increasingly used in a variety of web services, providing a list of recommended items in which a user may have an interest. While important, recommender systems are vulnerable to various malicious attacks. In this paper, we study a new security vulnerability in recommender systems caused byweb injection, through which malicious actors stealthily tamper any unprotected in-transit HTTP webpage content and force victims to visit specific items in some web services (even running HTTPS),e.g., YouTube. By doing so, malicious actors can promote their targeted items in those web services. To obtain a deeper understanding on the recommender systems of our interest (including YouTube, Yelp, Taobao, and 360 App market), we first conduct a measurement-based analysis on several real-world recommender systems by leveraging machine learning algorithms. Then, web injection is implemented in three different types of devices (i.e., computer, router, and proxy server) to investigate the scenarios where web injection could occur. Based on the implementation of web injection, we demonstrate that it is feasible and sometimes effective to manipulate the real-world recommender systems through web injection. We also present several countermeasures against such manipulations.

Cyber-security is an important societal concern. Cyber-attacks have increased in numbers as well as in the extent of damage caused in every attack. Large organizations operate a Cyber Security Operation Center (CSOC), which forms the first line of cyber-defense. The inspection of cyber-alerts is a critical part of CSOC operations (defender or blue team). Recent work proposed a reinforcement learning (RL) based approach for the defender’s decision-making to prevent the cyber-alert queue length from growing large and overwhelming the defender. In this article, we perform a red team (adversarial) evaluation of this approach. With the recent attacks on learning-based decision-making systems, it is even more important to test the limits of the defender’s RL approach. Toward that end, we learn several adversarial alert generation policies and the best response against them for various defender’s inspection policy. Surprisingly, we find the defender’s policies to be quite robust to the best response of the attacker. In order to explain this observation, we extend the earlier defender’s RL model to a game model with adversarial RL, and show that there exist defender policies that can be robust against any adversarial policy. We also derive a competitive baseline from the game theory model and compare it to the defender’s RL approach. However, when we go further to exploit the assumptions made in the Markov Decision Process (MDP) in the defender’s RL model, we discover an attacker policy that overwhelms the defender. We use a double oracle like approach to retrain the defender with episodes from this discovered attacker policy. This made the defender robust to the discovered attacker policy and no further harmful attacker policies were discovered. Overall, the adversarial RL and double oracle approach in RL are general techniques that are applicable to other RL usage in adversarial environments.

Large organizations typically have Cybersecurity Operations Centers (CSOCs) distributed at multiple locations that are independently managed, and they have their own cybersecurity analyst workforce. Under normal operating conditions, the CSOC locations are ideally staffed such that the alerts generated from the sensors in a work-shift are thoroughly investigated by the scheduled analysts in a timely manner. Unfortunately, when adverse events such as increase in alert arrival rates or alert investigation rates occur, alerts have to wait for a longer duration for analyst investigation, which poses a direct risk to organizations. Hence, our research objective is to mitigate the impact of the adverse events by dynamically and autonomously re-allocating alerts to other location(s) such that the performances of all the CSOC locations remain balanced. This is achieved through the development of a novel centralized adaptive decision support system whose task is to re-allocate alerts from the affected locations to other locations. This re-allocation decision is non-trivial because the following must be determined: (1) timing of a re-allocation decision, (2) number of alerts to be reallocated, and (3) selection of the locations to which the alerts must be distributed. The centralized decision-maker (henceforth referred to as agent) continuously monitors and controls the level of operational effectiveness-LOE (a quantified performance metric) of all the locations. The agent's decision-making framework is based on the principles of stochastic dynamic programming and is solved using reinforcement learning (RL). In the experiments, the RL approach is compared with both rule-based and load balancing strategies. By simulating real-world scenarios, learning the best decisions for the agent, and applying the decisions on sample realizations of the CSOC's daily operation, the results show that the RL agent outperforms both approaches by generating (near-) optimal decisions that maintain a balanced LOE among the CSOC locations. Furthermore, the scalability experiments highlight the practicality of adapting the method to a large number of CSOC locations.

A typical Cybersecurity Operations Center (CSOC) is a service organization. It hires and trains analysts, whose task is to perform analysis of alerts that were generated while monitoring the client’s networks. Due to ever-increasing financial and infrastructure burden on a CSOC driven by the rapidly growing demand for security services, it would become prohibitively expensive to continually expand the size of a CSOC to meet the demands in the future. An alternative solution is to outsource the alert analysis process to on-demand analysts, to provide scalable CSOC service to its clients with features, such as (1) higher throughput, (2) higher quality, and (3) more economical service than the current in-house service. The current outsourcing model is not cost effective and an exact optimization model is computationally inefficient. This article presents a novel two-step sequential mixed integer programming optimization method that is used in the development of a new decision-support business model for outsourcing the alert analysis process. It is demonstrated that through this model, a CSOC can effectively deliver its alert management services with the above-mentioned features. Results indicate that the model is scalable, computationally viable, real-time implementable, and can deliver CSOC services that meet the service-level agreement (SLA) between the CSOC and its client. In addition, the article provides valuable insights into the cost of operating the new business process outsourcing model for cybersecurity services.

Security patches in open source software (OSS) not only provide security fixes to identified vulnerabilities, but also make the vulnerable code public to the attackers. Therefore, armored attackers may misuse this information to launch N-day attacks on unpatched OSS versions. The best practice for preventing this type of N-day attacks is to keep upgrading the software to the latest version in no time. However, due to the concerns on reputation and easy software development management, software vendors may choose to secretly patch their vulnerabilities in a new version without reporting them to CVE or even providing any explicit description in their change logs. When those secretly patched vulnerabilities are being identified by armored attackers, they can be turned into powerful "0-day" attacks, which can be exploited to compromise not only unpatched version of the same software, but also similar types of OSS (e.g., SSL libraries) that may contain the same vulnerability due to code clone or similar design/implementation logic. Therefore, it is critical to identify secret security patches and downgrade the risk of those "0-day" attacks to at least "n-day" attacks. In this paper, we develop a defense system and implement a toolset to automatically identify secret security patches in open source software. To distinguish security patches from other patches, we first build a security patch database that contains more than 4700 security patches mapping to the records in CVE list. Next, we identify a set of features to help distinguish security patches from non-security ones using machine learning approaches. Finally, we use code clone identification mechanisms to discover similar patches or vulnerabilities in similar types of OSS. The experimental results show our approach can achieve good detection performance. A case study on OpenSSL, LibreSSL, and BoringSSL discovers 12 secret security patches.

In many cases, an organization wishes to release some data, but is restricted in the amount of data to be released due to legal, privacy and other concerns. For instance, the US Census Bureau releases only 1% of its table of records every year, along with statistics about the entire table. However, the machine learning (ML) models trained on the released sub-table are usually sub-optimal. In this paper, our goal is to find a way to augment the sub-table by generating a synthetic table from the released sub-table, under the constraints that the generated synthetic table (i) has similar statistics as the entire table, and (ii) preserves the functional dependencies of the released sub-table. We propose a novel generative adversarial network framework called ITS-GAN, where both the generator and the discriminator are specifically designed to satisfy these two constraints. By evaluating the augmentation performance of ITS-GAN on two representative datasets, the US Census Bureau data and US Bureau of Transportation Statistics (BTS) data, we show that ITS-GAN yields high quality classification results, and significantly outperforms various state-of-the-art data augmentation approaches.

Today’s cloud providers strive to attract customers with better services and less downtime in a highly competitive market. The need for minimizing the operational cost unavoidably leads cloud providers to rely on third party remote administrators for fulfilling regular maintenance tasks. In such a scenario, the lack of trust in those third party remote administrators paired with the extra privileges granted to them to complete the maintenance tasks usually implies undesirable security threats. A dishonest remote administrator, or an attacker armed with the stolen credential of a remote administrator, can pose severe insider threats to both the cloud provider and its tenants. In this paper, we take the first step towards understanding and mitigating such insider threats of remote administrators in clouds. Specifically, we first model the maintenance task assignments and their corresponding security impact due to privilege escalation. We then mitigate such impact through optimizing the task assignments with respect to given constraints. Finally, the simulation results demonstrate the effectiveness of our solution in various scenarios.

Intrusion detection systems (IDSs) analyze data that are collected by sensors, which monitor the network traffic. Any alert generated by the IDS is transmitted to a cybersecurity operations center (CSOC), which performs the important task of analyzing the alerts. In order to deliver a strong security against threats, an efficient CSOC requires the following characteristics: 1) all alerts must be analyzed in a timely manner; 2) there must be an ideal mix of analyst expertise levels in the organization because the quality of analysis performed depends on the mix; and 3) there must be adequate operating budget to hire the required number of analyst personnel. However, it is non-trivial for a CSOC manager to establish the parameter settings for the above characteristics for a desired CSOC efficiency, and current literature lacks a thorough analysis of the tradeoffs between them. This void is filled by this paper whose research objective is to develop an optimized tradeoff study model of the CSOC that studies and quantifies the interactions between the above characteristics, and to use the knowledge gained from the above study to provide the foundation principles to establish and operate an efficient CSOC. A constraint-optimization tradeoff study model is built to drive the decisions that optimize the above characteristics of the CSOC, which is then tested via several simulation runs of the alert arrival and service processes at the CSOC. The paper serves as the first step toward a unified tradeoff study model that integrates the throughput performance, the quality of analysis, and the cost metrics to design and establish an efficient CSOC. Results from the above optimization-simulation tests capture several valuable insights along with parameter settings of the metrics that explain how to operate an efficient CSOC, and quantifies the economic impact of scaling-up the CSOC operation.

A Cyber Security Operations Center (CSOC) is responsible for investigating all the alerts generated from the intrusion detection systems to identify suspicious activities in a timely manner. There exists a critical gap between the time needed (demand) and the time available (limited analyst resource) for alert investigation at a CSOC. Hence, alert prioritization is important, for which CSOCs employ ad-hoc filtering methods to prune and triage the alerts that are presented to the analysts for investigation. One of the major drawbacks of the ad-hoc methods is that they do not comprehensively take into consideration the organization-specific factors such as mission and asset criticality, CSOC resource availability, demand variations, and the desired CSOC performance metrics. Hence, an ad-hoc triaging (or prioritization) method is insufficient, and an intelligent method for optimal selection of alerts that considers the above-mentioned organization-specific factors must be developed, which is described as a two-step process in this paper. First, a composite risk score of each alert is determined using a quantitative value function hierarchy process, which takes into account several organization-specific factors. Second, an optimization model selects a list of alerts for investigation that optimizes the CSOC performance metrics for a given demand subject to its resource constraints. Experimental results show that the alerts that pertain to mission criticalities are handled in a timelier manner as compared to current practices at the CSOCs. The average persistence time of an alert in the CSOC system is also shown to significantly reduce with this new approach, which is a paradigm shift in providing a stronger cyber-defense system by protecting the critical constituents of an organization.

The administrators of a mission critical network usually have to worry about non-traditional threats, e.g., how to live with known, but unpatchable vulnerabilities, and how to improve the network’s resilience against potentially unknown vulnerabilities. To this end, network hardening is a well-known preventive security solution that aims to improve network security by taking proactive actions, namely, hardening options. However, most existing network hardening approaches rely on a single hardening option, such as disabling unnecessary services, which becomes less effective when it comes to dealing with unknown and unpatchable vulnerabilities. There lacks a heterogeneous approach that can combine different hardening options in an optimal way to deal with both unknown and unpatchable vulnerabilities. In this paper, we propose such an approach by unifying multiple hardening options, such as service diversification, firewall rule modification, adding, removing, and relocating network resources, and access control, all under the same model. We then apply security metrics designed for evaluating network resilience against unknown and unpatchable vulnerabilities, and consequently derive optimal solutions to maximize security under given cost constraints. Finally, we study the effectiveness of our solution against unpatchable vulnerabilities through simulations.

Most past work on honeypots has made two assumptions: (i) they assume that the only defensive measure used is a honeypot mechanism, and (ii) they do not consider both rational and subrational adversaries and do not reason with an adversary model when placing honeypots. However, real-world system security officers use a mix of instruments such as traditional defenses (e.g. firewalls, intrusion detection systems), and honeypots form only one portion of the strategy. Moreover, the placement of traditional defenses and honeypots cannot be done independently. In this paper, we consider a Stackelberg-style game situation where the defender models the attacker and uses that model to identify the best placement of traditional defenses and honeypots. We provide a formal definition of undamaged asset value (i.e. the value that is not compromised by the attacker) under a given defensive strategy and show that the problem of finding the best placement so as to maximize undamaged asset value is NP-hard. We propose a greedy algorithm and show via experiments, both on real enterprise networks and on ones generated by the well-known network simulation tool NS-2, that our algorithm quickly computes near optimal placements. As such, our method is both practical and effective.

Privacy is an important concern for our society where sharing data with partners or releasing data to the public is a frequent occurrence. Some of the techniques that are being used to achieve privacy are to remove identifiers, alter quasi-identifiers, and perturb values. Unfortunately, these approaches suffer from two limitations. First, it has been shown that private information can still be leaked if attackers possess some background knowledge or other information sources. Second, they do not take into account the adverse impact these methods will have on the utility of the released data. In this paper, we propose a method that meets both requirements. Our method, called table-GAN , uses generative adversarial networks (GANs) to synthesize fake tables that are statistically similar to the original table yet do not incur information leakage. We show that the machine learning models trained using our synthetic tables exhibit performance that is similar to that of models trained using the original table for unknown testing cases. We call this property model compatibility . We believe that anonymization/perturbation/synthesis methods without model compatibility are of little value. We used four real-world datasets from four different domains for our experiments and conducted indepth comparisons with state-of-the-art anonymization, perturbation, and generation techniques. Throughout our experiments, only our method consistently shows balance between privacy level and model compatibility.

With increasingly complex cyber attacks occurring every day, memory-based forensic techniques are becoming instrumental in digital investigations. Forensic examiners can unravel what happened on a system by acquiring and inspecting in-memory data. However, the foundation of this analysis can be invalidated if the memory acquisition has been altered. In this paper, we study the feasibility of malicious software misusing architectural features to sabotage memory forensics. The misuse of two architectural features, namely, physical address layout and secure containers, is presented. The first architectural feature explored in this paper is the physical address layout. It is used by the northbridge to route memory access to either physical memory or I/O devices on x86 platforms. Observing this design choice, we propose Hidden in I/O Space (HIveS), which manipulates CPU registers to alter the physical address layout to conceal memory. The system uses a novel I/O shadowing technique to lock a memory region named HIveS memory into I/O address space to prevent access. Two novel techniques, blackbox write and TLB camouflage, are developed to further protect the unlocked HIveS memory against memory forensics while allowing access for attackers. The second architectural feature explored in this paper is hardware-aided secure execution technology. More specifically, hardware-enforced memory encryption in Intel secure guard extension is used in malicious enclave software (Malclaveware) to prevent introspection and memory forensics. A prototype of HIveS is built and tested against a set of memory acquisition tools for both Windows and Linux running on the x86 platform. Malclaveware is also prototyped in Windows to demonstrate the risk. More importantly, we proposed countermeasures and mitigations for the newly discovered attacks. Through these discussions, we aim to raise the awareness of the potential risks of misusing hardware architectural features.

Vulnerability remediation is a critical task in operational software and network security management. In this article, an effective vulnerability management strategy, called VULCON (VULnerability CONtrol), is developed and evaluated. The strategy is based on two fundamental performance metrics: (1) time-to-vulnerability remediation (TVR) and (2) total vulnerability exposure (TVE). VULCON takes as input real vulnerability scan reports, metadata about the discovered vulnerabilities, asset criticality, and personnel resources. VULCON uses a mixed-integer multiobjective optimization algorithm to prioritize vulnerabilities for patching, such that the above performance metrics are optimized subject to the given resource constraints. VULCON has been tested on multiple months of real scan data from a cyber-security operations center (CSOC). Results indicate an overall TVE reduction of 8.97% when VULCON optimizes a realistic security analyst workforce’s effort. Additionally, VULCON demonstrates that it can determine monthly resources required to maintain a target TVE score. As such, VULCON provides valuable operational guidance for improving vulnerability response processes in CSOCs.

The analysts at a cybersecurity operations center (CSOC) analyze the alerts that are generated by intrusion detection systems (IDSs). Under normal operating conditions, sufficient numbers of analysts are available to analyze the alert workload. For the purpose of this article, this means that the cybersecurity analysts in each shift can fully investigate each and every alert that is generated by the IDSs in a reasonable amount of time and perform their normal tasks in a shift. Normal tasks include analysis time, time to attend training programs, report writing time, personal break time, and time to update the signatures on new patterns in alerts as detected by the IDS. There are several disruptive factors that occur randomly and can adversely impact the normal operating condition of a CSOC, such as (1) higher alert generation rates from a few IDSs, (2) new alert patterns that decrease the throughput of the alert analysis process, and (3) analyst absenteeism. The impact of the preceding factors is that the alerts wait for a long duration before being analyzed, which impacts the level of operational effectiveness (LOE) of the CSOC. To return the CSOC to normal operating conditions, the manager of a CSOC can take several actions, such as increasing the alert analysis time spent by analysts in a shift by canceling a training program, spending some of his own time to assist the analysts in alert investigation, and calling upon the on-call analyst workforce to boost the service rate of alerts. However, additional resources are limited in quantity over a 14-day work cycle, and the CSOC manager must determine when and how much action to take in the face of uncertainty, which arises from both the intensity and the random occurrences of the disruptive factors. The preceding decision by the CSOC manager is nontrivial and is often made in an ad hoc manner using prior experiences. This work develops a reinforcement learning (RL) model for optimizing the LOE throughout the entire 14-day work cycle of a CSOC in the face of uncertainties due to disruptive events. Results indicate that the RL model is able to assist the CSOC manager with a decision support tool to make better decisions than current practices in determining when and how much resource to allocate when the LOE of a CSOC deviates from the normal operating condition.

A “noisy-rich” (NR) cyber-attacker (Lippmann et al. 2012) is one who tries all available vulnerabilities until he or she successfully compromises the targeted network. We develop an adversarial foundation, based on Stackelberg games, for how NR-attackers will explore an enterprise network and how they will attack it, based on the concept of a system vulnerability dependency graph. We develop a mechanism by which the network can be modified by the defender to induce deception by placing honey nodes and apparent vulnerabilities into the network to minimize the expected impact of the NR-attacker’s attacks (according to multiple measures of impact). We also consider the case where the adversary learns from blocked attacks using reinforcement learning. We run detailed experiments with real network data (but with simulated attack data) and show that Stackelberg Honey-based Adversarial Reasoning Engine performs very well, even when the adversary deviates from the initial assumptions made about his or her behavior. We also develop a method for the attacker to use reinforcement learning when his or her activities are stopped by the defender. We propose two stopping policies for the defender: Stop Upon Detection allows the attacker to learn about the defender’s strategy and (according to our experiments) leads to significant damage in the long run, whereas Stop After Delay allows the defender to introduce greater uncertainty into the attacker, leading to better defendability in the long run.

We present a novel approach for the specification and enforcement of authorizations that enables controlled data sharing for collaborative queries in the cloud. Data authorities can establish authorizations regulating access to their data distinguishing three visibility levels (no visibility, encrypted visibility, and plaintext visibility). Authorizations are enforced in the query execution by possibly restricting operation assignments to other parties and by adjusting visibility of data on-the-fly. Our approach enables users and data authorities to fully enjoy the benefits and economic savings of the competitive open cloud market, while maintaining control over data.

Malicious attackers often scan nodes in a network in order to identify vulnerabilities that they may exploit as they traverse the network. In this paper, we propose that the system generates a mix of true and false answers in response to scan requests. If the attacker believes that all scan results are true, then he will be on a wrong path. If he believes some scan results are faked, he would have to expend time and effort in order to separate fact from fiction. We propose a probabilistic logic of deception and show that various computations are NP-hard. We model the attacker's state and show the effects of faked scan results. We then show how the defender can generate fake scan results in different states that minimize the damage the attacker can produce. We develop a Naive-PLD algorithm and a Fast-PLD heuristic algorithm for the defender to use and show experimentally that the latter performs well in a fraction of the run time of the former. We ran detailed experiments to assess the performance of these algorithms and further show that by running Fast-PLD off-line and storing the results, we can very efficiently answer run-time scan requests.

Cybersecurity threats are on the rise with evermore digitization of the information that many day-to-day systems depend upon. The demand for cybersecurity analysts outpaces supply, which calls for optimal management of the analyst resource. Therefore, a key component of the cybersecurity defense system is the optimal scheduling of its analysts. Sensor data is analyzed by automatic processing systems, and alerts are generated. A portion of these alerts is considered to be significant , which requires thorough examination by a cybersecurity analyst. Risk, in this article, is defined as the percentage of unanalyzed or not thoroughly analyzed alerts among the significant alerts by analysts. The article presents a generalized optimization model for scheduling cybersecurity analysts to minimize risk (a.k.a., maximize significant alert coverage by analysts) and maintain risk under a pre-determined upper bound. The article tests the optimization model and its scalability on a set of given sensors with varying analyst experiences, alert generation rates, system constraints, and system requirements. Results indicate that the optimization model is scalable and is capable of identifying both the right mix of analyst expertise in an organization and the sensor-to-analyst allocation in order to maintain risk below a given upper bound. Several meta-principles are presented, which are derived from the optimization model, and they further serve as guiding principles for hiring and scheduling cybersecurity analysts. The simulation studies (validation) of the optimization model outputs indicate that risk varies non-linearly with an analyst/sensor ratio, and for a given analyst/sensor ratio, the risk is independent of the number of sensors in the system.

A Trusted Cloud Database System manages client-side encrypted cloud DBs. Queries may include encryption keys. The DBS decrypts/encrypts the data on-the-fly at the cloud. Plaintext is only in protected run-time variables. Stored data are by default probabilistically encrypted through AES. Any SQL queries are feasible, with negligible processing overhead and practical storage overhead. This is a major advance over the current alternative research proposals. We detail capabilities of a trusted DBS. We adapt SQL to client-side key management. Queries may remain usually almost as nonprocedural as now. A prototype implementation appears easy.

Managed security services (MSS) are becoming increasingly popular today. In MSS, enterprises contract a security firm such as Symantec or IBM to manage security of their enterprise network. MSS vendors thus have a small pool of cybersecurity analysts who must monitor many different alerts. In this paper, we study the problem of allocating cybersecurity analysts to alerts generated by intrusion detection systems and other security software. In particular, given an enterprise network (or set of enterprise networks) and information about the value of assets stored at a node (e.g. computer, router) in the network, together with probabilities of compromising a neighbor of a compromised vertex, we show that annotated probabilistic temporal (APT) logic programs allow a defender to express knowledge about the network that captures the probabilities that different nodes will be attacked. In addition, certain APT logic computations, in conjunction with a Stackelberg game theoretic formalization, enable us to capture the attacker’s maximal probability of success as well as his ability to maximize damage. We show how the defender can come up with optimal allocations of tasks to cybersecurity analysts, taking both network information into account as well as a behavioral model of the attacker into account. We show correctness and complexity theorems for both the attacker and the defender. We develop a prototype implementation of three algorithms for the defender that optimize the defender’s objectives and show that these algorithms work well on realistic network sizes.

In this paper, we consider restricted data sharing between a set of parties that wish to provide some set of online services requiring such data sharing. Each party is assumed to store its data in private relational databases, and is given a set of mutually agreed set of authorization rules that specify access to attributes over individual relations or joins over relations owned by one or more parties. The access restrictions introduce significant additional complexity in rule enforcement and query planning as compared with a traditional distributed database environment. We examine the problem of minimum cost rule enforcement which simultaneously checks for the enforceability of each rule and generation of minimum cost plan of its execution. However, the paper is not focused on specific cost functions, but instead of efficient methods for enforcing rules in the face of access restrictions and inter-party data transfer needs. We propose an efficient heuristic algorithm for this minimal enforcement since the exact problem is NP-hard. In some cases, it is not possible to enforce the rules with the regular parties only. In such cases, we need help of trusted third parties (TPs). If all parties trust a single TP, such a party can enforce all unenforced rules, but it is desirable to use the TP minimally. We also consider the extended case where multiple TPs are required since not every regular party can trust a single TP.

Cloud computing is receiving massive interest from users and companies for its convenient support of scalable access to data and services. The variety and diversification of offers by cloud providers allow users to selectively adopt storage and computational services as they best suit their needs, including cost saving considerations. In such an open context, security remains a major concern, as confidentiality and integrity of data and queries over them can be at risk. In this paper, we present efficient techniques to verify the integrity of join queries computed by potentially untrusted cloud providers, while also protecting data and computation confidentiality. Our techniques support joins among multiple data sources and introduce a limited overhead in query computation, enabling also economical savings, as the ability to assess integrity increases the spectrum of offers that can be considered for performing the computation. Formal analysis and experimental evaluations confirm the effectiveness and efficiency of our solutions.

Discusses the current state of the journal, reports on current and future areas of exploration and research, and presents new editors.

Account compromization is a serious threat to users of online social networks (OSNs). While relentless spammers exploit the established trust relationships between account owners and their friends to efficiently spread malicious spam, timely detection of compromised accounts is quite challenging due to the well established trust relationship between the service providers, account owners, and their friends. In this paper, we study the social behaviors of OSN users, i.e., their usage of OSN services, and the application of which in detecting the compromised accounts. In particular, we propose a set of social behavioral features that can effectively characterize the user social activities on OSNs. We validate the efficacy of these behavioral features by collecting and analyzing real user clickstreams to an OSN website. Based on our measurement study, we devise individual user's social behavioral profile by combining its respective behavioral feature metrics. A social behavioral profile accurately reflects a user's OSN activity patterns. While an authentic owner conforms to its account's social behavioral profile involuntarily, it is hard and costly for impostors to feign. We evaluate the capability of the social behavioral profiles in distinguishing different OSN users, and our experimental results show the social behavioral profiles can accurately differentiate individual OSN users and detect compromised accounts.

Diversity has long been regarded as a security mechanism for improving the resilience of software and networks against various attacks. More recently, diversity has found new applications in cloud computing security, moving target defense, and improving the robustness of network routing. However, most existing efforts rely on intuitive and imprecise notions of diversity, and the few existing models of diversity are mostly designed for a single system running diverse software replicas or variants. At a higher abstraction level, as a global property of the entire network, diversity and its effect on security have received limited attention. In this paper, we take the first step toward formally modeling network diversity as a security metric by designing and evaluating a series of diversity metrics. In particular, we first devise a biodiversity-inspired metric based on the effective number of distinct resources. We then propose two complementary diversity metrics, based on the least and the average attacking efforts, respectively. We provide guidelines for instantiating the proposed metrics and present a case study on estimating software diversity. Finally, we evaluate the proposed metrics through simulation.

An important component of the cyber-defense mechanism is the adequate staffing levels of its cybersecurity analyst workforce and their optimal assignment to sensors for investigating the dynamic alert traffic. The ever-increasing cybersecurity threats faced by today’s digital systems require a strong cyber-defense mechanism that is both reactive in its response to mitigate the known risk and proactive in being prepared for handling the unknown risks. In order to be proactive for handling the unknown risks, the above workforce must be scheduled dynamically so the system is adaptive to meet the day-to-day stochastic demands on its workforce (both size and expertise mix). The stochastic demands on the workforce stem from the varying alert generation and their significance rate, which causes an uncertainty for the cybersecurity analyst scheduler that is attempting to schedule analysts for work and allocate sensors to analysts. Sensor data are analyzed by automatic processing systems, and alerts are generated. A portion of these alerts is categorized to be significant , which requires thorough examination by a cybersecurity analyst. Risk, in this article, is defined as the percentage of significant alerts that are not thoroughly analyzed by analysts. In order to minimize risk, it is imperative that the cyber-defense system accurately estimates the future significant alert generation rate and dynamically schedules its workforce to meet the stochastic workload demand to analyze them. The article presents a reinforcement learning-based stochastic dynamic programming optimization model that incorporates the above estimates of future alert rates and responds by dynamically scheduling cybersecurity analysts to minimize risk (i.e., maximize significant alert coverage by analysts) and maintain the risk under a pre-determined upper bound. The article tests the dynamic optimization model and compares the results to an integer programming model that optimizes the static staffing needs based on a daily-average alert generation rate with no estimation of future alert rates (static workforce model). Results indicate that over a finite planning horizon, the learning-based optimization model, through a dynamic (on-call) workforce in addition to the static workforce, (a) is capable of balancing risk between days and reducing overall risk better than the static model, (b) is scalable and capable of identifying the quantity and the right mix of analyst expertise in an organization, and (c) is able to determine their dynamic (on-call) schedule and their sensor-to-analyst allocation in order to maintain risk below a given upper bound. Several meta-principles are presented, which are derived from the optimization model, and they further serve as guiding principles for hiring and scheduling cybersecurity analysts. Days-off scheduling was performed to determine analyst weekly work schedules that met the cybersecurity system’s workforce constraints and requirements.

With the growing complexity of computing systems, memory based forensic techniques are becoming instrumental in digital investigations. Digital forensic examiners can unravel what happened on a system by acquiring and inspecting in-memory data. Meanwhile, attackers have developed numerous anti-forensic mechanisms to defeat existing memory forensic techniques by manipulation of system software such as OS kernel. To counter anti-forensic techniques, some recent researches suggest that memory acquisition process can be trusted if the acquisition module has not been tampered with and all the operations are performed without relying on any untrusted software including the operating system.

Data fragmentation has been proposed as a solution for protecting the confidentiality of sensitive associations when releasing data for publishing or external storage. To enrich the utility of data fragments, a recent approach has put forward the idea of complementing a pair of fragments with some (non-precise, hence loose) information on the association between them. Starting from the observation that in presence of multiple fragments the publication of several independent associations between pairs of fragments can cause improper leakage of sensitive information, in this paper we extend loose associations to operate over an arbitrary number of fragments. We first illustrate how the publication of multiple loose associations between different pairs of fragments can potentially expose sensitive associations, and describe an approach for defining loose associations among an arbitrary set of fragments. We investigate how tuples in fragments can be grouped for producing loose associations so to increase the utility of queries executed over fragments. We then provide a heuristics for performing such a grouping and producing loose associations satisfying a given level of protection for sensitive associations, while achieving utility for queries over different fragments. We also illustrate the result of an extensive experimental effort over both synthetic and real datasets, which shows the efficiency and the enhanced utility provided by our proposal.

The National Vulnerability Database (NVD) maintained by the US National Institute of Standards and Technology provides valuable information about vulnerabilities in popular software, as well as any patches available to address these vulnerabilities. Most enterprise security managers today simply patch the most dangerous vulnerabilities—an adversary can thus easily compromise an enterprise by using less important vulnerabilities to penetrate an enterprise. In this article, we capture the vulnerabilities in an enterprise as a Vulnerability Dependency Graph (VDG) and show that attacks graphs can be expressed in them. We first ask the question: What set of vulnerabilities should an attacker exploit in order to maximize his expected impact? We show that this problem can be solved as an integer linear program. The defender would obviously like to minimize the impact of the worst-case attack mounted by the attacker—but the defender also has an obligation to ensure a high productivity within his enterprise. We propose an algorithm that finds a Pareto-optimal solution for the defender that allows him to simultaneously maximize productivity and minimize the cost of patching products on the enterprise network. We have implemented this framework and show that runtimes of our computations are all within acceptable time bounds even for large VDGs containing 30K edges and that the balance between productivity and impact of attacks is also acceptable.

Moving Target Defense (MTD) is emerging as a game changing approach consisting in a number of mechanisms that automatically change one or more system attributes in order to make a system's attack surface unpredictable to adversaries. The main objective of the First ACM Workshop on Moving Target Defense (MTD 2014) is to address the challenges of developing new MTD techniques and evaluating the effectiveness of MTD techniques with theoretical analysis and experimental results. This workshop aims to bring together researchers from academia, government, and industry to report on the latest research efforts on moving target defense,and to have productive discussion and constructive debate on this topic.

It is well known that not all intrusions can be prevented and additional lines of defense are needed to deal with intruders. However, most current approaches use honeynets relying on the assumption that simply attracting intruders into honeypots would thwart the attack. In this paper, we propose a different and more realistic approach, which aims at delaying intrusions, so as to control the probability that an intruder will reach a certain goal within a specified amount of time. Our method relies on analyzing a graphical representation of the computer network’s logical layout and an associated probabilistic model of the adversary’s behavior. We then artificially modify this representation by adding “distraction clusters” – collections of interconnected virtual machines – at key points of the network in order to increase complexity for the intruders and delay the intrusion. We study this problem formally, showing it to be NP-hard and then provide an approximation algo- rithm that exhibits several useful properties. Finally, we present experimental results obtained on a prototypal implementation of the proposed framework.

This paper proposes a simple but very effective approach called Gemini to prevent victim users from exposing sensitive credentials to a phishing site. As an emergency line of defense, Gemini assumes that a victim user is already deceived into a phishing site and starts the user authentication procedure. Gemini springs into action once the username field is filled in, and tackles the phishing problem from a new perspective. In particular, by exploiting username input, Gemini is able to provide more accurate detection of a phishing site and much stronger protection for a password, the most confidential and crucial information for user authentication. To validate the efficacy of Gemini, we implement different prototypes of Gemini as a browser extension for IE, Firefox, and Chrome, respectively, and conduct extensive live experiments over various legitimate and phishing websites for more than one month. Our experimental results show that Gemini can achieve zero false negative rate and less than 1% false positive rate, and Gemini can effectively block the access to a phishing site before a victim user begins to enter in a password. Moreover, Gemini is complementary to existing anti-phishing tools. The performance overhead induced by Gemini is minor and has a negligible effect upon users' browsing activities.

Fragmentation has been recently proposed as a promising approach to protect the confidentiality of sensitive associations whenever data need to undergo external release or storage. By splitting attributes among different fragments, fragmentation guarantees confidentiality of the associations among these attributes under the assumption that such associations cannot be reconstructed by re-combining the fragments. We note that the requirement that fragments do not have attributes in common, imposed by previous proposals, is only a necessary, but not sufficient, condition to ensure that information in different fragments cannot be recombined as dependencies may exist among data enabling some form of linkability. In this paper, we identify the problem of improper information leakage due to data dependencies, provide a formulation of the problem based on a natural graphical modeling, and present an approach to tackle it in an efficient and scalable way.

By enabling a direct comparison of different security solutions with respect to their relative effectiveness, a network security metric may provide quantifiable evidences to assist security practitioners in securing computer networks. However, research on security metrics has been hindered by difficulties in handling zero-day attacks exploiting unknown vulnerabilities. In fact, the security risk of unknown vulnerabilities has been considered as something unmeasurable due to the less predictable nature of software flaws. This causes a major difficulty to security metrics, because a more secure configuration would be of little value if it were equally susceptible to zero-day attacks. In this paper, we propose a novel security metric, k-zero day safety, to address this issue. Instead of attempting to rank unknown vulnerabilities, our metric counts how many such vulnerabilities would be required for compromising network assets; a larger count implies more security because the likelihood of having more unknown vulnerabilities available, applicable, and exploitable all at the same time will be significantly lower. We formally define the metric, analyze the complexity of computing the metric, devise heuristic algorithms for intractable cases, and finally demonstrate through case studies that applying the metric to existing network security practices may generate actionable knowledge.

Wireless sensor networks (WSNs) are increasingly used in many applications, such as volcano and fire monitoring, urban sensing, and perimeter surveillance. In a large WSN, in-network data aggregation (i.e., combining partial results at intermediate nodes during message routing) significantly reduces the amount of communication overhead and energy consumption. The research community proposed a loss-resilient aggregation framework called synopsis diffusion, which uses duplicate-insensitive algorithms on top of multipath routing schemes to accurately compute aggregates (e.g., predicate count or sum). However, this aggregation framework does not address the problem of false subaggregate values contributed by compromised nodes. This attack may cause large errors in the aggregate computed at the base station, which is the root node in the aggregation hierarchy. In this paper, we make the synopsis diffusion approach secure against the above attack launched by compromised nodes. In particular, we present an algorithm to enable the base station to securely compute predicate count or sum even in the presence of such an attack. Our attack-resilient computation algorithm computes the true aggregate by filtering out the contributions of compromised nodes in the aggregation hierarchy. Extensive analysis and simulation study show that our algorithm outperforms other existing approaches.

Measuring the mean time-to-compromise provides important insights for understanding a network's weaknesses and for guiding corresponding defense approaches. Most existing network security metrics only deal with the threats of known vulnerabilities and cannot handle zero day attacks with consistent semantics. In this paper, we propose a unified framework for measuring a network's mean time-to-compromise by considering both known, and zero day attacks. Specifically, we first devise models of the mean time for discovering and exploiting individual vulnerabilities. Unlike existing approaches, we replace the generic state transition model with a more vulnerability-specific graphical model. We then employ Bayesian networks to derive the overall mean time-to-compromise by aggregating the results of individual vulnerabilities. Finally, we demonstrate the framework's practical application to network hardening through case studies.

We address the problem of providing users with the ability to assess the integrity of join results produced by external computational providers and computed over externally stored databases. Our approach relies on different mutually supporting techniques offering strong integrity protection guarantees at a limited cost. The application of the approach is completely transparent to the computational provider, against which data and query confidentiality are preserved. The paper introduces our techniques analytically, examining their protection guarantees and performance. It also illustrates experimental results, which confirm the effectiveness and efficiency of our solutions.

We present a novel hybrid communication protocol that guarantees mobile users’ anonymity against a wide-range of adversaries by exploiting the capability of handheld devices to connect to both WiFi and cellular networks. Unlike existing anonymity schemes, we consider all parties that can intercept communications between a mobile user and a server as potential privacy threats. We formally quantify the privacy exposure and the protection of our system in the presence of malicious neighboring peers, global WiFi eavesdroppers, and omniscient mobile network operators, which possibly collude to breach user’s anonymity or disrupt the communication. We also describe how a micropayment scheme that suits our mobile scenario can provide incentives for peers to collaborate in the protocol. Finally, we evaluate the network overhead and attack resiliency of our protocol using a prototype implementation deployed in Emulab and Orbit, and our probabilistic model.

In this paper we consider the situation where a set of enterprises need to collaborate to provide rich services to their clients. Such collaboration often requires controlled access to each other's data, which we assume is stored in standard relational form. The access control is provided by a set o

Attack graph analysis has been established as a powerful tool for analyzing network vulnerability. However, previous approaches to network hardening look for exact solutions and thus do not scale. Further, hardening elements have been treated independently, which is inappropriate for real environments. For example, the cost for patching many systems may be nearly the same as for patching a single one. Or patching a vulnerability may have the same effect as blocking traffic with a firewall, while blocking a port may deny legitimate service. By failing to account for such hardening interdependencies, the resulting recommendations can be unrealistic and far from optimal. Instead, we formalize the notion of hardening strategy in terms of allowable actions, and define a cost model that takes into account the impact of interdependent hardening actions. We also introduce a near-optimal approximation algorithm that scales linearly with the size of the graphs, which we validate experimentally.

Multi-tenancy of the cloud maximizes the utility of computation and storage resources by multiplexing the underlying hardware infrastructure amongst cloud customers; however, it also introduces significant security issues such as information leakage between two virtual machines (VMs) even if certain access control policy (e.g., Chinese Wall security policy) has been deployed in the cloud. Physical resource isolation between VMs is an effective mechanism to remove the covert channels in the cloud and prevent information leakage; however, due to economic concerns or negligence, some cheap-and-lazy cloud providers are not motivated to enforce the physical resource isolation as they promised. In this paper, we first develop a mechanism to check the co-residency of two files on local hard disk(s) by measuring the file access time, and then extend our mechanism to check data storage co-residency on Amazon S3 cloud storage.

Enterprise networks today host a wide variety of network services, which often depend on each other to provide and support network-based services and applications. Understanding such dependencies is essential for maintaining the well-being of an enterprise network and its applications, particularly in the presence of network attacks and failures. In a typical enterprise network, which is complex and dynamic in configuration, it is non-trivial to identify all these services and their dependencies. Several techniques have been developed to learn such dependencies automatically. However, they are either too complex to fine tune or cluttered with false positives and/or false negatives. In this paper, we propose a suite of novel techniques and develop a new tool named NSDMiner (which stands for Mining for Network Service Dependencies) to automatically discover the dependencies between network services from passively collected network traffic. NSDMiner is non-intrusive; it does not require any modification of existing software, or injection of network packets. More importantly, NSDMiner achieves higher accuracy than previous network-based approaches. Our experimental evaluation, which uses network traffic collected from our campus network, shows that NSDMiner outperforms the two best existing solutions significantly.

A network security metric is desirable in evaluating the effectiveness of security solutions in distributed systems. Aggregating CVSS scores of individual vulnerabilities provides a practical approach to network security metric. However, existing approaches to aggregating CVSS scores usually cause useful semantics of individual scores to be lost in the aggregated result. In this paper, we address this issue through two novel approaches. First, instead of taking each base score as an input, our approach drills down to the underlying base metric level where dependency relationships have well-defined semantics. Second, our approach interprets and aggregates the base metrics from three different aspects in order to preserve corresponding semantics of the individual scores. Finally, we confirm the advantages of our approaches through simulation.

Twitter is a new web application playing dual roles of online social networking and microblogging. Users communicate with each other by publishing text-based posts. The popularity and open structure of Twitter have attracted a large number of automated programs, known as bots, which appear to be a double-edged sword to Twitter. Legitimate bots generate a large amount of benign tweets delivering news and updating feeds, while malicious bots spread spam or malicious contents. More interestingly, in the middle between human and bot, there has emerged cyborg referred to either bot-assisted human or human-assisted bot. To assist human users in identifying who they are interacting with, this paper focuses on the classification of human, bot, and cyborg accounts on Twitter. We first conduct a set of large-scale measurements with a collection of over 500,000 accounts. We observe the difference among human, bot, and cyborg in terms of tweeting behavior, tweet content, and account properties. Based on the measurement results, we propose a classification system that includes the following four parts: 1) an entropy-based component, 2) a spam detection component, 3) an account properties component, and 4) a decision maker. It uses the combination of features extracted from an unknown user to determine the likelihood of being a human, bot, or cyborg. Our experimental evaluation demonstrates the efficacy of the proposed classification system.

In a large sensor network, in-network data aggregation significantly reduces the amount of communication and energy consumption. Recently, the research community has proposed a robust aggregation framework called synopsis diffusion which combines multipath routing schemes with duplicate-insensitive algorithms to accurately compute aggregates (e.g., predicate Count, Sum) in spite of message losses resulting from node and transmission failures. However, this aggregation framework does not address the problem of false subaggregate values contributed by compromised nodes resulting in large errors in the aggregate computed at the base station, which is the root node in the aggregation hierarchy. This is an important problem since sensor networks are highly vulnerable to node compromises due to the unattended nature of sensor nodes and the lack of tamper-resistant hardware.

The widespread diffusion of Web-based services provided by public and private organizations emphasizes the need for a flexible solution for protecting the information accessible through Web applications. A promising approach is represented by credential-based access control and trust management. However, although much research has been done and several proposals exist, a clear obstacle to the realization of their benefits in data-intensive Web applications is represented by the lack of adequate support in the DBMSs. As a matter of fact, DBMSs are often responsible for the management of most of the information that is accessed using a Web browser or a Web service invocation. In this article, we aim at eliminating this gap, and present an approach integrating trust management with the access control of the DBMS. We propose a trust model with a SQL syntax and illustrate an algorithm for the efficient verification of a delegation path for certificates. Our solution nicely complements current trust management proposals allowing the efficient realization of the services of an advanced trust management model within current relational DBMSs. An important benefit of our approach lies in its potential for a robust end-to-end design of security for personal data in Web scenario, where vulnerabilities of Web applications cannot be used to violate the protection of the data residing on the database server. We also illustrate the implementation of our approach within an open-source DBMS discussing design choices and performance impact.

Existing approaches for protecting sensitive information outsourced at external “honest-but-curious” servers are typically based on an overlying layer of encryption applied to the whole database, or on the combined use of fragmentation and encryption. In this paper, we put forward a novel paradigm for preserving privacy in data outsourcing, which departs from encryption. The basic idea is to involve the owner in storing a limited portion of the data, while storing the remaining information in the clear at the external server. We analyze the problem of computing a fragmentation that minimizes the owner's workload, which is represented using different metrics and corresponding weight functions, and prove that this minimization problem is NP-hard. We then introduce the definition of locally minimal fragmentation that is used to efficiently compute a fragmentation via a heuristic algorithm. The algorithm translates the problem of finding a locally minimal fragmentation in terms of a hypergraph 2-coloring problem. Finally, we illustrate the execution of queries on fragments and provide experimental results comparing the fragmentations returned by our heuristics with respect to optimal fragmentations. The experiments show that the heuristics guarantees a low computation cost and is able to compute a fragmentation close to optimum.

We present a simple, yet powerful, approach for the specification and enforcement of authorizations regulating data release among data holders collaborating in a distributed computation, to ensure that query processing discloses only data whose release has been explicitly authorized. Data disclosure is captured by means of profiles, associated with each data computation, that describe the information carried by a base or a derived (i.e., computed by a query) relation. We present an algorithm that, given a query plan, determines whether it can be safely executed and produces a safe execution strategy for it. For each operation in a safe query plan, the algorithm determines the server(s) responsible for the execution, based on the entailed information flows, considering different strategies for the execution of joins. Finally, we discuss the architecture of a distributed database system based on the proposed model, illustrating possible design choices and their impact.

We analyze the security vulnerabilities of PEAS, ASCENT, and CCP, three well-known topology maintenance protocols (TMPs) for sensor networks. These protocols aim to increase the lifetime of the sensor network by only maintaining a subset of nodes in an active or awake state. The design of these protocols assumes that the sensor nodes will be deployed in a trusted, nonadversarial environment, and does not take into account the impact of attacks launched by malicious insider or outsider nodes. We propose a metaprotocol (Meta-TMP) to represent the class of topology maintenance protocols. The Meta-TMP provides us with a better understanding of the characteristics and of how a specific TMP works, and it can be used to study the vulnerabilities of a specific TMP. We describe various types of malicious behavior and actions that can be carried out by an adversary to attack a wireless sensor network by exploiting the TMP being used in the network. We describe three attacks against these protocols that may be used to reduce the lifetime of the sensor network, or to degrade the functionality of the sensor application by reducing the network connectivity and the sensing coverage that can be achieved. Further, we describe countermeasures that can be taken to increase the robustness of the protocols and make them resilient to such attacks.

LH*RE is a new Scalable Distributed Data Structure (SDDS) for hash files stored in a cloud. The client-side symmetric encryption protects the data against the server-side disclosure. The encryption key(s) at the client are backed up in the file. The client may recover/ revoke any keys lost or stolen from its node. A trusted official can also do it on behalf of the client or of an authority, e.g., to imperatively access the data of a client missing or disabled. In contrast, with high assurance, e.g., 99%, the attacker of the cloud should not usually disclose any data, even if the intrusion succeeds over dozens or possibly thousands of servers for a larger file. Storage and primary key-based access performance of LH*RE should be about those of the well-known LH* SDDS. Two messages should typically suffice for a key-based search and four in the worst case, with the application data load factor of 70%, regardless of the file scale up. These features are among most efficient for a hash SDDS. LH*RE should be attractive with respect to the competition.

Twitter is a new web application playing dual roles of online social networking and micro-blogging. Users communicate with each other by publishing text-based posts. The popularity and open structure of Twitter have attracted a large number of automated programs, known as bots, which appear to be a double-edged sword to Twitter. Legitimate bots generate a large amount of benign tweets delivering news and updating feeds, while malicious bots spread spam or malicious contents. More interestingly, in the middle between human and bot, there has emerged cyborg referred to either bot-assisted human or human-assisted bot. To assist human users in identifying who they are interacting with, this paper focuses on the classification of human, bot and cyborg accounts on Twitter. We first conduct a set of large-scale measurements with a collection of over 500,000 accounts. We observe the difference among human, bot and cyborg in terms of tweeting behavior, tweet content, and account properties. Based on the measurement results, we propose a classification system that includes the following four parts: (1) an entropy-based component, (2) a machine-learning-based component, (3) an account properties component, and (4) a decision maker. It uses the combination of features extracted from an unknown user to determine the likelihood of being a human, bot or cyborg. Our experimental evaluation demonstrates the efficacy of the proposed classification system.

Studied in this paper is the problem of restoring compromised privacy for micro-data disclosure with multiple disclosed views. The property of γ-privacy is proposed, which requires that the probability of an individual to be associated with a sensitive value must be bounded by γ in a possible table which is randomly selected from a set of tables that would lead the same disclosed answers. For the restricted case of a single disclosed view, the γ-privacy is shown to be equivalent to recursive ([EQUATION], 2)-Diversity, which is not defined for multiple disclosed views. The problem of deciding on γ-privacy for a set of disclosed views is proven to be #P-complete. To mitigate the high computational complexity, the property of γ-privacy is relaxed to be satisfied with (ε, θ) confidence, i.e., that the probability of disclosing a sensitive value of an individual must be bounded by γ + ε with statistical confidence θ. A Monte Carlo-based algorithm is proposed to check the relaxed property in O((λλ')4) time for constant ε and θ, where λ is the number of tuples in the original table and λ' is the number different sensitive values in the original table. Restoring compromised privacy using additional disclosed views is studied. Heuristic polynomial time algorithms are proposed based on enumerating and checking additional disclosed views. A preliminary experimental study is conducted on real-life medical data, which demonstrates that the proposed polynomial algorithms restore privacy in up to 60% of compromised disclosures.

Peer-to-peer (P2P) VoIP calls such as those provided by Skype have been becoming popular due to their quality-of-service, free of cost, security and convenience. Skype is a distributed P2P network with no centralized call servers. Calls traverse through a myriad of possible paths before reaching to the destination and each packet is encrypted with 256 bit AES encryption. In this paper, we are particularly interested in tracing out from this entangled web of peer nodes, who has called a target subscriber or to whom the target subscriber is calling. To this end, we present a transparent packet marking scheme that not only determines the origination and destination of a call but also the path taken through various hosts in P2P networks.

We propose a modeling of the problem of privacy-compliant data publishing that captures confidentiality constraints on one side and visibility requirements on the other side. Confidentiality constraints express the fact that some attributes, or associations among them, are sensitive and cannot be released. Visibility requirements express requests for views over data that should be provided. We propose a solution based on data fragmentation to split sensitive associations while ensuring visibility. In addition, we show how sensitive associations broken by fragmentation can be released in a sanitized form as loose associations formed in a way to guarantee a specified degree of privacy.

With abundant aggregate network bandwidth, continuous data streams are commonly used in scientific and commercial applications. Correspondingly, there is an increasing demand of authenticating these data streams. Existing strategies explore data stream authentication by using message authentication codes (MACs) on a certain number of data packets (a data block) to generate a message digest, then either embedding the digest into the original data, or sending the digest out-of-band to the receiver. Embedding approaches inevitably change the original data, which is not acceptable under some circumstances (e.g., when sensitive information is included in the data). Sending the digest out-of-band incurs additional communication overhead, which consumes more critical resources (e.g., power in wireless devices for receiving information) besides network bandwidth. In this paper, we propose a novel strategy, DaTA, which effectively authenticates data streams by selectively adjusting some interpacket delay. This authentication scheme requires no change to the original data and no additional communication overhead. Modeling-based analysis and experiments conducted on an implemented prototype system in an LAN and over the Internet show that our proposed scheme is efficient and practical.

In this paper, we introduce the concept ofwitness anonymityfor peer-to-peer systems, as well as other systems with the peer-to-peer nature. Witness anonymity combines the seemingly conflicting requirements of anonymity (for honest peers who report on the misbehavior of other peers) and accountability (for malicious peers that attempt to misuse the anonymity feature to slander honest peers). We propose theSecure Deep Throat(SDT) protocol to provide anonymity for the witnesses of malicious or selfish behavior to enable such peers to report on this behavior without fear of retaliation. On the other hand, in SDT, the misuse of anonymity is restrained in such a way that any malicious peer attempting to send multiple claims against the same innocent peer for the same reason (i.e., the same misbehavior type) can be identified. We also describe how SDT can be used in two modes. The active mode can be used in scenarios with real-time requirements, e.g., detecting and preventing the propagation of peer-to-peer worms, whereas the passive mode is suitable for scenarios without strict real-time requirements, e.g., query-based reputation systems. We analyze the security and overhead of SDT, and present countermeasures that can be used to mitigate various attacks on the protocol. Moreover, we show how SDT can be easily integrated with existing protocols/mechanisms with a few examples. Our analysis shows that the communication, storage, and computation overheads of SDT are acceptable in peer-to-peer systems.

The impact of privacy requirements in the development of modern applications is increasing very quickly. Many commercial and legal regulations are driving the need to develop reliable solutions for protecting sensitive information whenever it is stored, processed, or communicated to external parties. To this purpose, encryption techniques are currently used in many scenarios where data protection is required since they provide a layer of protection against the disclosure of personal information, which safeguards companies from the costs that may arise from exposing their data to privacy breaches. However, dealing with encrypted data may make query processing more expensive. In this article, we address these issues by proposing a solution to enforce the privacy of data collections that combines data fragmentation with encryption. We model privacy requirements as confidentiality constraints expressing the sensitivity of attributes and their associations. We then use encryption as an underlying (conveniently available) measure for making data unintelligible while exploiting fragmentation as a way to break sensitive associations among attributes. We formalize the problem of minimizing the impact of fragmentation in terms of number of fragments and their affinity and present two heuristic algorithms for solving such problems. We also discuss experimental results, comparing the solutions returned by our heuristics with respect to optimal solutions, which show that the heuristics, while guaranteeing a polynomial-time computation cost are able to retrieve solutions close to optimum.

Due to the poor physical protection of sensor nodes, it is generally assumed that an adversary can capture and compromise a small number of sensors in the network. In a node replication attack, an adversary can take advantage of the credentials of a compromised node to surreptitiously introduce replicas of that node into the network. Without an effective and efficient detection mechanism, these replicas can be used to launch a variety of attacks that undermine many sensor applications and protocols. In this paper, we present a novel distributed approach called Localized Multicast for detecting node replication attacks. The efficiency and security of our approach are evaluated both theoretically and via simulation. Our results show that, compared to previous distributed approaches proposed by Parno et al., Localized Multicast is more efficient in terms of communication and memory costs in large-scale sensor networks, and at the same time achieves a higher probability of detecting node replicas.

Current access control models typically assume that resources are under the strict custody of a trusted party which monitors each access request to verify if it is compliant with the specified access control policy. There are many scenarios where this approach is becoming no longer adequate. Many clear trends in Web technology are creating a need for owners of sensitive information to manage access to it by legitimate users using the services of honest but curious third parties, that is, parties trusted with providing the required service but not authorized to read the actual data content. In this scenario, the data owner encrypts the data before outsourcing and stores them at the server. Only the data owner and users with knowledge of the key will be able to decrypt the data. Possible access authorizations are to be enforced by the owner. In this article, we address the problem of enforcing selective access on outsourced data without need of involving the owner in the access control process. The solution puts forward a novel approach that combines cryptography with authorizations, thus enforcing access control via selective encryption . The article presents a formal model for access control management and illustrates how an authorization policy can be translated into an equivalent encryption policy while minimizing the amount of keys and cryptographic tokens to be managed. The article also introduces a two-layer encryption approach that allows the data owner to outsource, besides the data, the complete management of the authorization policy itself, thus providing efficiency and scalability in dealing with policy updates. We also discuss experimental results showing that our approach is able to efficiently manage complex scenarios.

The balance between privacy and utility is a classical problem with an increasing impact on the design of modern information systems. On the one side it is crucial to ensure that sensitive information is properly protected; on the other side, the impact of protection on the workload must be limited as query efficiency and system performance remain a primary requirement. We address this privacy/efficiency balance proposing an approach that, starting from a flexible definition of confidentiality constraints on a relational schema, applies encryption on information in a parsimonious way and mostly relies on fragmentation to protect sensitive associations among attributes. Fragmentation is guided by workload considerations so to minimize the cost of executing queries over fragments. We discuss the minimization problem when fragmenting data and provide a heuristic approach to its solution.

While network-wide anomaly analysis has been well studied, the on-line detection of network traffic anomalies at a vantage point inside the Internet still poses quite a challenge to network administrators. In this paper, we develop a behavioral distance based anomaly detection mechanism with the capability of performing on-line traffic analysis. To construct accurate online traffic profiles, we introduce horizontal and vertical distance metrics between various traffic features (i.e., packet header fields) in the traffic data streams. The significant advantages of the proposed approach lie in four aspects: (1) it is efficient and simple enough to process on-line traffic data; (2) it facilitates protocol behavioral analysis without maintaining per-flow state; (3) it is scalable to high speed traffic links because of the aggregation, and (4) using various combinations of packet features and measuring distances between them, it is capable for accurate on-line anomaly detection. We validate the efficacy of our proposed detection system by using network traffic traces collected at Abilene and MAWI high-speed links.

Proximity based services are location based services (LBS) in which the service adaptation depends on the comparison between a given threshold value and the distance between a user and other (possibly moving) entities. While privacy preservation in LBS has lately received much attention, very limited work has been done on privacy-aware proximity based services. This paper describes the main privacy threats that the usage of these services can lead to, and proposes original privacy preservation techniques offering different trade-offs between quality of service and privacy preservation. The properties of the proposed algorithms are formally proved, and an extensive experimental work illustrates the practicality of the approach.

One of the privacy threats recognized in the use of LBS is represented by an adversary having information about the presence of individuals in certain locations, and using this information together with an (anonymous) LBS request to re-identify the issuer of the request associating her to the requested service. Several papers have proposed techniques to prevent this, assuming that the use of the service is considered sensitive. In this paper we investigate the more general case in which the adversary is also able to recognize traces of LBS requests by the same anonymous user, so that the identification of the issuer of one request can lead to the disclosure of the same user being in other possibly sensitive locations at different times or using sensitive services.Using the notion of "historical k-anonymity", this paper provides the first formalization of this class of privacy threats. Through extensive experiments based on realistic simulations, and runs of an optimal algorithm, we show some negative results for the defenses based on spatial generalization against these attacks under very conservative assumptions. Under more realistic location knowledge assumptions, we propose two defense algorithms, based on a strategy of changing and reusing of pseudo-identifiers, whose correctness is formally proved. Our experiments show that, among all the proposed algorithms, the ProvidentHider algorithm is particularly effective in protecting privacy for reasonably long sequences of requests.

The anonymization of location based queries through the generalization of spatio-temporal information has been proposed as a privacy preserving technique. We show that the presence of multiple concurrent requests, the repetition of similar requests by the same issuers, and the distribution of different service parameters in the requests can significantly affect the level of privacy obtained by current anonymity-based techniques. We provide a formal model of the privacy threat, and we propose an incremental defense technique based on a combination of anonymity and obfuscation. We show the effectiveness of this technique by means of an extensive experimental evaluation.

A privacy violation occurs when the association between an individual identity and data considered private by that individual is obtained by an unauthorized party. Uncertainty and indistinguishability are two independent aspects that characterize the

Abstract In‐network data aggregationin wireless sensor networks (WSNs) is a technique aimed at reducing the communication overhead—sensed data are combined into partial results at intermediate nodes during message routing. However, in the above technique, some sensor nodes need to send their individual sensed values to an aggregator node, empowered with the capability to decrypt the received data to perform a partial aggregation. This scenario raises privacy concerns in applications like personal health care and the military surveillance. A few other solutions exist where the data are not disclosed to the aggregator (e.g., using privacy homomorphism (PH)), but these solutions are not robust to node or communication failure. The contributions of this paper are two‐fold: first, we design a private data aggregation protocol that does not leak individual sensed values during the data aggregation process. In particular, neither the base station (BS) nor the other nodes are able to compromise the privacy of an individual node's sensed value. Second, the proposed protocol is robust to data‐loss; if there is a node‐failure or communication failure, the protocol is still able to compute the aggregate and to report to the base station the number of nodes that participated in the aggregation. To the best of our knowledge, our scheme is the first one that efficiently addresses the above issues all at once. Copyright © 2009 John Wiley & Sons, Ltd.

We propose an approach for the selective enforcement of access control restrictions in, possibly distributed, large data collections based on two basic concepts: i) flexible authorizations identify, in a declarative way, the data that can be released, and ii) queries are checked for execution not with respect to individual authorizations but rather evaluating whether the information release they (directly or indirectly) entail is allowed by the authorizations. Our solution is based on the definition of query profiles capturing the information content of a query and builds on a graph-based modeling of database schema, authorizations, and queries. Access control is then effectively modeled and efficiently executed in terms of graph coloring and composition and on traversal of graph paths. We then provide a polynomial composition algorithm for determining if a query is authorized.

We present a simple, yet powerful, approach for the specification and enforcement of authorizations regulating data release among data holders collaborating in a distributed computation, to ensure that query processing discloses only data whose release has been explicitly authorized. Data disclosure is captured by means of profiles, associated with each data computation, that describe the information carried by the result. We also present an algorithm that, given a query plan, determines whether it can be safely executed and produces a safe execution strategy. The main advantage of our approach is its simplicity that, without impacting expressiveness, makes it nicely interoperable with current solutions for collaborative computations in distributed database systems.

Wireless Sensor Networks (WSNs) have proven to be useful in many applications, such as military surveillance and environment monitoring. To meet the severe energy constraints in WSNs, some researchers have proposed to use the in-network data aggregation technique (i.e., combining partial results at intermediate nodes during message routing), which significantly reduces the communication overhead. Given the lack of hardware support for tamper resistance and the unattended nature of sensor nodes, sensor network protocols need to be designed with security in mind. Recently, researchers proposed algorithms for securely computing a few aggregates, such as Sum (the sum of the sensed values), Count (number of nodes) and Average. However, to the best of our knowledge, there is no prior work which securely computes the Median, although the Median is considered to be an important aggregate. The contribution of this paper is twofold. We first propose a protocol to compute an approximate Median and verify if it has been falsified by an adversary. Then, we design an attack-resilient algorithm to compute the Median even in the presence of a few compromised nodes. We evaluate the performance and cost of our approach via both analysis and simulation. Our results show that our approach is scalable and efficient.

An attack graph models the causal relationships between vulnerabilities. Attack graphs have important applications in protecting critical resources in networks against sophisticated multi-step intrusions. Currently, analyses of attack graphs largely depend on proprietary implementations of speciali zed algorithms. However, developing and implementing algorithms causes a delay to the availability of new analyses. The delay is usually unacceptable due to rapidly-changing needs in defending against network intrusions. An administrator may want to revise an analysis as soon as its outcome is observed. Such an interactive analysis, similar to that in decision support systems, is desirable but difficult with current approaches based on proprietary implementations of algorithms. This paper addresses the above issue through a relational approach. Specifically, we devise a relational model for representing necessary inputs, such as network configurations and domain knowledge, and we generate attack graphs from these inputs as relational views. We show that typical analyses can be supported through different type of searches in an attack graph, and these searches can be realized as relational queries. Our approach eliminates the needs for implementing algorithms, because an analysis is now simply a relational query. The interactive analysis of attack graphs becomes possible, since relational queries can be dynamically constructed and revised at run time. As a side effect, experimental results show that the mature optimization techniques in relational databases can transparently improve the performance of the analysis.

Massive Internet media distribution demands prolonged continuous consumption of networking and disk bandwidths in large capacity. Many proxy-based Internet media distribution algorithms and systems have been proposed, implemented, and evaluated to address the scalability and performance issue. However, few of them have been used in practice, since two important issues are not satisfactorily addressed. First, existing proxy-based media distribution architectures lack an efficient media distribution control mechanism. Without copyright protection, content providers are hesitant to use proxy-based fast distribution techniques. Second, little has been done to protect client privacy during content accesses on the Internet. Straightforward solutions to address these two issues independently lead to conflicts. For example, to enforce distribution control, only legitimate users should be granted access rights. However, this normally discloses more information (such as which object the client is accessing) other than the client identity, which conflicts with the client's desire for privacy protection. In this article, we propose a unified proxy-based media distribution protocol to effectively address these two problems simultaneously. We further design a set of new algorithms in a cooperative proxy environment where our proposed scheme works efficiently and practically. Simulation-based experiments are conducted to extensively evaluate the proposed system. Preliminary results demonstrate the effectiveness of our proposed strategy.

Voice over IP (VoIP), also known as Internet telephony, is gaining market share rapidly and now competes favorably as one of the visible applications of the Internet. Nevertheless, being an application running over the TCP/IP suite, it is susceptible to flooding attacks. If flooded, as a time-sensitive service, VoIP may show noticeable service degradation and even encounter sudden service disruptions. Because multiple protocols are involved in a VoIP service and most of them are susceptible to flooding, an effective solution must be able to detect and overcome hybrid floods. As a solution, we offer the VoIP flooding detection system (vFDS)-an online statistical anomaly detection framework that generates alerts based on abnormal variations in a selected hybrid collection of traffic flows. It does so by viewing collections of related packet streams as evolving probability distributions and measuring abnormal variations in their relationships based on the Hellinger distance-a measure of variability between two probability distributions. Experimental results show that vFDS is fast and accurate in detecting flooding attacks, without noticeably increasing call setup times or introducing jitter into the voice streams.

Wireless sensor nodes lack hardware support for tamper- resistance and are often deployed in unattended environments, thus leaving them vulnerable to capture and compromise by an adversary. In a node replication attack, an adversary uses the credentials of a compromised node to surreptitiously introduce replicas of that node into the network. These replicas are then used to launch a variety of attacks that subvert the goal of the sensor application, and the operation of the underlying protocols. We present a novel distributed approach called Localized Multicast for detecting node replication attacks. We evaluate the performance and security of our approach both theoretically and via simulation. Our results show that Localized Multicast is more efficient than previous distributed approaches in terms of communication and memory costs. Further, in our approach, the probability of detecting node replicas is much higher than that achieved in previous distributed protocols.

This talk will discuss issues and methods for survivability of systems under malicious attacks. To protect from such attacks, it is necessary to take steps to prevent attacks from succeeding. At the same time, it is important to recognize that not all attacks can be averted at the outset; attacks that are successful to some degree must be recognized as unavoidable and comprehensive support for identifying and responding to attacks is required.In my talk, I will describe the recent research on attack graphs that represent known attack sequences attackers can use to penetrate computer networks. I will show how attack graphs can be used to compute actual sets of hardening measures that guarantee the safety of given critical resources. Attack graphs can also be used to correlate received alerts, hypothesize missing alerts, and predict future alerts, all at the same time. Thus, they offer a promising solution for administrators to monitor and predict the progress of an intrusion, and take appropriate countermeasures in a timely manner.

Trust management represents today a promising approach for supporting access control in open environments. While several approaches have been proposed for trust management and significant steps have been made in this direction, a major obstacle that still exists in the realization of the benefits of this paradigm is represented by the lack of adequate support in the DBMS.In this paper, we present a design that can be used to implement trust management within current relational DBMSs. We propose a trust model with a SQL syntax and illustrate the main issues arising in the implementation of the model in a relational DBMS. Specific attention is paid to the efficient verification of a delegation path for certificates. This effort permits a relatively inexpensive realization of the services of an advanced trust management model within current relational DBMSs.

The problem of information disclosure has attracted much interest from the research community in recent years. When disclosing information, the challenge is to provide as much information as possible (optimality) while guaranteeing a desired safety property for privacy (such as l-diversity). A typical disclosure algorithm uses a sequence of disclosure schemas to output generalizations in the nonincreasing order of data utility; the algorithm releases the first generalization that satisfies the safety property. In this paper, we assert that the desired safety property cannot always be guaranteed if an adversary has the knowledge of the underlying disclosure algorithm. We propose a model for the additional information disclosed by an algorithm based on the definition of deterministic disclosure function (DDF), and provide definitions of p-safe and p-optimal DDFs. We give an analysis for the complexity to compute a p-optimal DDF. We show that deciding whether a DDF is p-optimal is an NP-hard problem, and only under specific conditions, we can solve the problem in polynomial time with respect to the size of the set of all possible database instances and the length of the disclosure generalization sequence. We then consider the problem of microdata disclosure and the safety condition of l-diversity. We relax the notion of p-optimality to weak p-optimality, and develop a weak p-optimal algorithm which is polynomial in the size of the original table and the length of the generalization sequence.

A general consensus is that the proliferation of location- aware devices will result in a diffusion of location-based services. Privacy preservation is a challenging research issue for this kind of service. A possible solution consists of ensuring users' anonymity, i.e., ensuring that the user issuing a request is indistinguishable, among a group of users, by any attacker who has access to the service requests. In this paper we propose a formal framework to model the problem of guaranteeing anonymity when requiring location-based services. The proposed framework extends existing approaches by allowing to model different kinds of knowledge that may be available to the attacker. We show application examples of our framework, modeling both known scenarios and new ones. From a practical point of view, the framework makes it possible to define anonymity-preserving techniques that best suite the system assumptions as derived from the applicative context, and the level of privacy protection defined by the user.

Many proposed low-latency anonymous communication systems have used various flow transformations such as traffic padding, adding cover traffic (or bogus packets), packet dropping, flow mixing, flow splitting, and flow merging to achieve anonymity. It has long been believed that these flow transformations would effectively disguise net-workflows, thus achieve good anonymity. In this paper, we investigate the fundamental limitations of flow transformations in achieving anonymity, and we show that flow transformations do not necessarily provide the level of anonymity people have expected or believed. By injecting unique watermark into the inter-packet timing domain of a packet flow, we are able to make any sufficiently long flow uniquely identifiable even if I) it is disguised by substantial amount of cover traffic, 2) it is mixed or merged with a number of other flows, 3) it is split into a number subflows, 4) there is a substantial portion of packets dropped, and 5) it is perturbed in timing due to either natural network delay jitter or deliberate timing perturbation. In addition to demonstrating the theoretical limitations of low-latency anonymous communications systems, we develop the first practical attack on the leading commercial low-latency anonymous communication system. Our real-time experiments show that our flow watermarking attack only needs about 10 minutes active Web browsing traffic to "penetrate" the total net shield service provided by www.anonymizer.com. Our analytical and empirical results demonstrate that achieving anonymity in low-latency communication systems is much harder than we have realized, and current flow transformation based low-latency anonymous communication systems need to be revisited.

This paper studies the inference control of multi-dimensional range (MDR) sum queries. We show that existing inference control methods are usually inefficient for MDR queries. We then consider parity-based inference control that restricts users to queries involving an even number of sensitive values. Such a restriction renders inferences significantly more difficult, because an even number is closed under addition and subtraction, whereas inferences target at one value. However, more sophisticated inferences are still possible with only even MDR queries. We show that the collection of all even MDR queries causes inferences if and only if a special collection of sum-two queries (that is, the summation of exactly two values) does so. The result leads to an inference control method with an improved computational complexity [Formula: see text] (over the previous result of [Formula: see text]) for m MDR queries over n values. We show that no odd MDR queries can be answered without causing inferences. We show how to check non-MDR queries for inferences in linear time. We also show how to find large inference-free subsets of even MDR queries when they do cause inferences.

Can-follow concurrency control permits a transactionto read (write) an item write-locked (read-locked) by anothertransaction with almost no delays. By combining the merits of2PL and 2V2PL, this approach mitigates the lock contention notonly between update and read-only transactions, but also betweenupdate and update transactions.

Sensor networks are often deployed in unattended environments, thus leaving these networks vulnerable to false data injection attacks in which an adversary injects false data into the network with the goal of deceiving the base station or depleting the resources of the relaying nodes. Standard authentication mechanisms cannot prevent this attack if the adversary has compromised one or a small number of sensor nodes. We present three interleaved hop-by-hop authentication schemes that guarantee that the base station can detect injected false data immediately when no more than t nodes are compromised, where t is a system design parameter. Moreover, these schemes enable an intermediate forwarding node to detect and discard false data packets as early as possible. Our performance analysis shows that our scheme is efficient with respect to the security it provides, and it also allows a tradeoff between security and performance. A prototype implementation of our scheme indicates that our scheme is practical and can be deployed on the current generation of sensor nodes.

The efficiency of promptly releasing security alerts of established analysis centers has been greatly challenged by the continuous emergence of various large scale network attacks, such as worms. With a limited number of sensors deployed over the Internet and a long attack verification period, when the alert is released by analysis centers, the best time to stop the attack may have passed. On the other hand, (1) most of the past large scale attacks targeted known vulnerabilities, and (2) today numerous Internet systems have integrated detection tools, such as virus detection software and intrusion detection systems (IDS), the power of which could be harnessed to defend against large scale attacks. In this paper, we propose V-COPS - a vulnerability-based cooperative alert distribution system, by leveraging existing independent local attack detection systems. V-COPS is capable of promptly propagating genuine alerts with critical vulnerability information, based on which relevant stakeholders can take preventive actions in time. Extensive analysis and experiments have been performed to study the performance of V-COPS. The preliminary results show V-COPS is effective

In this paper, we introduce the concept of witness anonymity for peer-to-peer systems. Witness anonymity combines the seemingly conflicting requirements of anonymity (for honest peers who report on the misbehavior of other peers) and accountability (for malicious peers that attempt to misuse the anonymity feature to slander honest peers). We propose the Secure Deep Throat (SDT) protocol to provide anonymity for witnesses of malicious or selfish behavior to enable such peers to report on this behavior without fear of retaliation. On the other hand, in SDT the misuse of anonymity is restrained in such a way that any malicious peer that attempts to send multiple claims against the same innocent peer for the same reason (i.e., the same misbehavior type) can be identified. We also describe how SDT can be used in two modes. The active mode can be used in scenarios with real-time requirements, e.g., detecting and preventing the propagation of peer-to-peer worms, whereas the passive mode is suitable for scenarios without strict real-time requirements, e.g., query-based reputation systems. We analyze the security and overhead of SDT and present countermeasures that can be used to mitigate various attacks on the protocol. Our analysis shows that the communication, storage, and computation overheads of SDT are acceptable in peer-to-peer systems.

Being a fast-growing Internet application, Voice over Internet Protocol (VoIP) shares the network resources with the regular Internet traffic, and is susceptible to the existing security holes of the Internet. Moreover, given that voice communication is time sensitive and uses a suite of interacting protocols, VoIP exposes new forms of vulnerabilities to malicious attacks. In this paper, we propose a highlyneeded VoIP intrusion detection system. Our approach is novel in that, it utilizes not only the state machines of network protocols but also the interaction among them for intrusion detection. This detection approach is particularly suited for protecting VoIP applications, in which a melange of protocols are involved to provide IP telephony services. Based on tracking deviations from interacting protocol state machines, our solution shows promising detection characteristics and low runtime impact on the perceived quality of voice streams.

Massive Internet media distribution demands pro longed continuous consumption of networking and disk band widths in large capacity. Many proxy-based Internet media distribution algorithms and systems have been proposed, implemented, and evaluated to address the scalability issue. However, few of them have been used in practice, since two important issues are not satisfactorily addressed. First, existing proxy-based media distribution architectures lack an efficient media distribution control mechanism. Without protection on the Internet, content providers are hesitant to use existing fast distribution techniques. Second, little has been done to protect client privacy during client accesses. Straightforward solutions to address these two issues independently lead to conflicts. For example, to enforce distribution control, only legitimate users should be granted access rights. However, this normally discloses more information (such as which object the client is accessing) other than the client identity, which conflicts with the client's desire for privacy protection. In this paper, we propose a unified proxy-based media distribution protocol to effectively address these two problems simultaneously. We further design a set of new algorithms for cooperative proxies where our proposed scheme works practically. Simulation results show that our proposed strategy is efficient

Recently voice over IP (VoIP) is experiencing a phenomenal growth. Being a real-time service, VoIP is more susceptible to denial-of-service (DoS) attacks than regular Internet services. Moreover, VoIP uses multiple protocols for call control and data delivery, making it vulnerable to various DoS attacks at different protocol layers. An attacker can easily disrupt VoIP services by flooding TCP SYN packets, UDP-based RTP packets, or SIP-based INVITE messages, which pose a critical threat to IP telephony. In this paper, we present an online statistical detection mechanism, called vFDS, to detect DoS attacks in the context of VoIP. The core of vFDS is based on Hellinger distance method, which computes the variability between two probability measures. Using Hellinger distance, we characterize normal protocol behaviors and then detect the traffic anomalies caused by flooding attacks. Our experimental results show that vFDS achieves fast and accurate detection of DoS attacks

This talk will discuss issues and methods for survivability of systems under malicious attacks. To protect from such attacks, it is necessary to take steps to prevent attacks from succeeding. At the same time, it is important to recognize that not all attacks can be averted at the outset; attacks that are successful to some degree must be recognized as unavoidable and comprehensive support for identifying and responding to attacks is required.

When an access decision function denies a data access request by a mission participant in a mission-critical situation, the mission often suffers. In this paper, we propose a sharing control mechanism that computes and executes requests that are mission-related to denied requests. We extend the Flexible Authorization Framework (FAF)with predicates and hierarchies that permit us to specify authorization rules over denied requests and mission-specific relationships. We illustrate our techniques using a prototypical information sharing scenario, namely an emergency first-responder scenario.

In this paper, we first define the requirements on anonymity and security properties of the routing protocol in mobile ad hoc networks, and then propose a new anonymous routing protocol with the local-repair mechanism. Detailed analysis shows that our protocol achieves both anonymity and security properties defined. A major challenge in designing anonymous routing protocols is to reduce computation and communication costs. To overcome this challenge, our protocol is design to require neither asymmetric nor symmetric encryption/decryption while updating the flooding route requests; more importantly, once a route is broken, instead of re-launching a new costly flooding route discovery process like previous work, our protocol provides a local-repair mechanism to fix broken parts of a route without compromising anonymity

In this paper we extend the notion of k-anonymity in the context of databases with timestamped information in order to naturally define k-anonymous views of temporal data. We also investigate the problem of obtaining these views. We show that known generalization techniques, despite being applicable under certain conditions, have some limitations, and propose a new generalization algorithm based on the hierarchy of time granularities.

We present GKMPAN, an efficient and scalable group rekeying protocol for secure multicast in ad hoc networks. Our protocol exploits the property of ad hoc networks that each member of a group is both a host and a router, and distributes the group key to member nodes via a secure hop-by-hop propagation scheme. A probabilistic scheme based on pre-deployed symmetric keys is used for implementing secure channels between members for group key distribution. GKMPAN also includes a novel distributed scheme for efficiently updating the pre-deployed keys. GKMPAN has three attractive properties. First, it is significantly more efficient than group rekeying schemes that were adapted from those proposed for wired networks. Second, GKMPAN has the property of partial statelessness; that is, a node can decode the current group key even if it has missed a certain number of previous group rekeying operations. This makes it very attractive for ad hoc networks where nodes may lose packets due to transmission link errors or temporary network partitions. Third, in GKMPAN the key server does not need any information about the topology of the ad hoc network or the geographic location of the members of the group. We study the security and performance of GKMPAN through detailed analysis and simulation; we have also implemented GKMPAN in a sensor network testbed.

We describe LEAP+ (Localized Encryption and Authentication Protocol), a key management protocol for sensor networks that is designed to support in-network processing, while at the same time restricting the security impact of a node compromise to the immediate network neighborhood of the compromised node. The design of the protocol is motivated by the observation that different types of messages exchanged between sensor nodes have different security requirements, and that a single keying mechanism is not suitable for meeting these different security requirements. LEAP+ supports the establishment of four types of keys for each sensor node: an individual key shared with the base station, a pairwise key shared with another sensor node, a cluster key shared with multiple neighboring nodes, and a global key shared by all the nodes in the network. LEAP+ also supports (weak) local source authentication without precluding in-network processing. Our performance analysis shows that LEAP+ is very efficient in terms of computational, communication, and storage costs. We analyze the security of LEAP+ under various attack models and show that LEAP+ is very effective in defending against many sophisticated attacks, such as HELLO flood attacks, node cloning attacks, and wormhole attacks. A prototype implementation of LEAP+ on a sensor network testbed is also described.

We apply adjacency matrix clustering to network attack graphs for attack correlation, prediction, and hypothesizing. We self-multiply the clustered adjacency matrices to show attacker reachability across the network for a given number of attack steps, culminating in transitive closure for attack prediction over all possible number of steps. This reachability analysis provides a concise summary of the impact of network configuration changes on the attack graph. Using our framework, we also place intrusion alarms in the context of vulnerability-based attack graphs, so that false alarms become apparent and missed detections can be inferred. We introduce a graphical technique that shows multiple-step attacks by matching rows and columns of the clustered adjacency matrix. This allows attack impact/responses to be identified and prioritized according to the number of attack steps to victim machines, and allows attack origins to be determined. Our techniques have quadratic complexity in the size of the attack graph

Peer-to-peer VoIP calls are becoming increasingly popular due to their advantages in cost and convenience. When these calls are encrypted from end to end and anonymized by low latency anonymizing network, they are considered by many people to be both secure and anonymous.In this paper, we present a watermark technique that could be used for effectively identifying and correlating encrypted, peer-to-peer VoIP calls even if they are anonymized by low latency anonymizing networks. This result is in contrast to many people's perception. The key idea is to embed a unique watermark into the encrypted VoIP flow by slightly adjusting the timing of selected packets. Our analysis shows that it only takes several milliseconds time adjustment to make normal VoIP flows highly unique and the embedded watermark could be preserved across the low latency anonymizing network if appropriate redundancy is applied. Our analytical results are backed up by the real-time experiments performed on leading peer-to-peer VoIP client and on a commercially deployed anonymizing network. Our results demonstrate that (1) tracking anonymous peer-to-peer VoIP calls on the Internet is feasible and (2) low latency anonymizing networks are susceptible to timing attacks.

Broadcast authentication is a critical security service in sensor networks; it allows a sender to broadcast messages to multiple nodes in an authenticated way. /spl mu/TESLA and multi-level /spl mu/TESLA have been proposed to provide such services for sensor networks. However, none of these techniques are scalable in terms of the number of senders. Though multi-level /spl mu/TESLA schemes can scale up to large sensor networks (in terms of receivers), they either use substantial bandwidth and storage at sensor nodes, or require significant resources at senders to deal with DOS attacks. This paper presents efficient techniques to support a potentially large number of broadcast senders using /spl mu/TESLA instances as building blocks. The proposed techniques are immune to the DOS attacks. This paper also provides two approaches, a revocation tree based scheme and a proactive distribution based scheme, to revoke the broadcast authentication capability from compromised senders. The proposed techniques are implemented, and evaluated through simulation on TinyOS. The analysis and experiment show that these techniques are efficient and practical, and can achieve better performance than the previous approaches.

Abstract — Most of the multicast routing protocols proposed for ad hoc networks assume a trusted, non-adversarial environment and do not take security issues into account in their design. In this paper, we investigate the security of MAODV (Multicast Ad hoc On-Demand Distance Vector protocol), a well-known multicast routing protocol, and identify several attacks on it. We show, via simulation, that these attacks can have a significant impact on the performance of MAODV. We present an authentication framework for MAODV and propose countermeasures that can prevent or mitigate the impact of these attacks. I.

We analyze the security vulnerabilities of PEAS, ASCENT, and CCP, three well-known topology maintenance protocols for sensor networks. These protocols aim to increase the lifetime of the sensor network by maintaining only a subset of nodes in an active or awake state. The design of these protocols assumes that the sensor nodes will be deployed in a trusted non-adversarial environment, and does not take into account the impact of attacks launched by malicious insider and outsider nodes. We describe three attacks against these protocols that can be used to reduce the lifetime of the sensor network, or to degrade the functionality of the sensor application by reducing the network connectivity and sensing coverage that can be achieved. Further, we describe counter-measures that can be used to increase the robustness of the protocols and make them resilient to such attacks.

While efficient graph-based representations have been developed for modeling combinations of low-level network attacks, relatively little attention has been paid to effective techniques for visualizing such attack graphs. This paper describes a number of new attack graph visualization techniques, each having certain desirable properties and offering different perspectives for solving different kinds of problems. Moreover, the techniques we describe can be applied not only separately, but can also be combined into coordinated attack graph views. We apply improved visual clustering to previously described network protection domains (attack graph cliques), which reduces graph complexity and makes the overall attack flow easier to understand. We also visualize the attack graph adjacency matrix, which shows patterns of network attack while avoiding the clutter usually associated with drawing large graphs. We show how the attack graph adjacency matrix concisely conveys the impact of network configuration changes on attack graphs. We also describe a novel attack graph filtering technique based on the interactive navigation of a hierarchy of attack graph constraints. Overall, our techniques scale quadratically with the number of machines in the attack graph.

In this paper, we present a technique for fingerprinting relational data by extending Agrawal et al.'s watermarking scheme. The primary new capability provided by our scheme is that, under reasonable assumptions, it can embed and detect arbitrary bit-string marks in relations. This capability, which is not provided by prior techniques, permits our scheme to be used as a fingerprinting scheme. We then present quantitative models of the robustness properties of our scheme. These models demonstrate that fingerprints embedded by our scheme are detectable and robust against a wide variety of attacks including collusion attacks.

The scope and character of today's computing environments are progressively shifting from traditional, one-on-one client-server interaction to the new cooperative paradigm. It then becomes of primary importance to provide means of protecting the secrecy of the information, while guaranteeing its availability to legitimate clients. Operating online querying services securely on open networks is very difficult; therefore many enterprises outsource their data center operations to external application service providers. A promising direction toward prevention of unauthorized access to outsourced data is represented by encryption. However, data encryption is often supported for the sole purpose of protecting the data in storage while allowing access to plaintext values by the server, which decrypts data for query execution. In this paper, we present a simple yet robust single-server solution for remote querying of encrypted databases on external servers. Our approach is based on the use of indexing information attached to the encrypted database, which can be used by the server to select the data to be returned in response to a query without the need of accessing the plaintext database content. Our indexes balance the trade-off between efficiency requirements in query execution and protection requirements due to possible inference attacks exploiting indexing information. We investigate quantitative measures to model inference exposure and provide some related experimental results.

We map intrusion events to known exploits in the network attack graph, and correlate the events through the corresponding attack graph distances. From this, we construct attack scenarios, and provide scores for the degree of causal correlation between their constituent events, as well as an overall relevancy score for each scenario. While intrusion event correlation and attack scenario construction have been previously studied, this is the first treatment based on association with network attack graphs. We handle missed detections through the analysis of network vulnerability dependencies, unlike previous approaches that infer hypothetical attacks. In particular, we quantify lack of knowledge through attack graph distance. We show that low-pass signal filtering of event correlation sequences improves results in the face of erroneous detections. We also show how a correlation threshold can be applied for creating strongly correlated attack scenarios. Our model is highly efficient, with attack graphs and their exploit distances being computed offline. Online event processing requires only a database lookup and a small number of arithmetic operations, making the approach feasible for real-time applications.

Recently, several database watermarking techniques have been developed to fight against database piracy. In watermarking, a database owner’s identification information is embedded into a database such that proof of ownership can be established by detecting the information in pirated data. However, most watermarking systems are vulnerable to the severe threat of additive attacks and this threat has not been studied formally. In an additive attack, a pirate inserts an additional watermark such that the proof of ownership becomes ambiguous. In this paper, we present an effective approach to defending against additive attacks. Our strategy is to raise the errors introduced during watermark insertion to a predetermined threshold such that any additive attack would introduce more errors than the threshold. Exceeding the error threshold means that the pirated data is less useful or less competitive; thus, the owner does not need to claim ownership for such pirated data. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Today, database relations are widely used and distributed over the Internet. Since these data can be easily tampered with, it is critical to ensure the integrity of these data. In this paper, we propose to make use of fragile watermarks to detect and localize malicious alterations made to a database relation with categorical attributes. Unlike other watermarking schemes which inevitably introduce distortions to the cover data, the proposed scheme is distortion free. In our algorithm, all tuples in a database relation are first securely divided into groups according to some secure parameters. Watermarks are embedded and verified in each group independently. Thus, any modifications can be localized to some specific groups. Theoretical analysis shows that the probability of missing detection is very low.

We present GKMPAN, an efficient and scalable group rekeying protocol for secure multicast in ad hoc networks. Our protocol exploits the property of ad hoc networks that each member of a group is both a host and a router, and distributes the group key to member nodes via a secure hop-by-hop propagation scheme. A probabilistic scheme based on predeployed symmetric keys is used for implementing secure channels between members for group key distribution. GKMPAN also includes a novel distributed scheme for efficiently updating the predeployed keys. GKMPAN has three attractive properties. First, it is significantly more efficient than group rekeying schemes that were adapted from those proposed for wired networks. Second, GKMPAN has the property of partial statelessness; that is, a node can decode the current group key even if it has missed a certain number of previous group rekeying operations. This makes it very attractive for ad hoc networks where nodes may lose packets due to transmission link errors or temporary network partitions. Third, in GKMPAN the key server does not need any information about the topology of the ad hoc network or the geographic location of the members of the group. We study the security and performance of GKMPAN through detailed analysis and simulation.

An OLAP (On-line Analytic Processing) system with insufficient security countermeasures may disclose sensitive information and breach an individual's privacy. Both unauthorized accesses and malicious inferences may lead to such inappropriate disclosures. Existing access control models in relational databases are unsuitable for the multi-dimensional data cubes used by OLAP. Inference control methods in statistical databases are expensive and apply to limited situations only. We first devise a flexible framework for specifying authorization objects in data cubes. The framework can partition a data cube both vertically based on dimension hierarchies and horizontally based on slices of data. We then study how to control inferences in data cubes. The proposed method eliminates both unauthorized accesses and malicious inferences. Its effectiveness does not depend on specific types of aggregation functions, external knowledge, or sensitivity criteria. The technique is efficient and readily implementable. Its on-line performance overhead is comparable to that of the minimal security requirement. Its enforcement requires little modification to existing OLAP systems.

Sensor networks are often deployed in unattended environments, thus leaving these networks vulnerable to false data injection attacks in which an adversary injects false data into the network with the goal of deceiving the base station or depleting the resources of the relaying nodes. Standard authentication mechanisms cannot prevent this attack if the adversary has compromised one or a small number of sensor nodes. In this paper, we present an interleaved hop-by-hop authentication scheme that guarantees that the base station will detect any injected false data packets when no more than a certain number t nodes are compromised. Further, our scheme provides an upper bound B for the number of hops that a false data packet could be forwarded before it is detected and dropped, given that there are up to t colluding compromised nodes. We show that in the worst case B is O(t/sup 2/). Through performance analysis, we show that our scheme is efficient with respect to the security it provides, and it also allows a tradeoff between security and performance.

We describe a framework for managing network attack graph complexity through interactive visualization, which includes hierarchical aggregation of graph elements. Aggregation collapses non-overlapping subgraphs of the attack graph to single graph vertices, providing compression of attack graph complexity. Our aggregation is recursive (nested), according to a predefined aggregation hierarchy. This hierarchy establishes rules at each level of aggregation, with the rules being based on either common attribute values of attack graph elements or attack graph connectedness. The higher levels of the aggregation hierarchy correspond to higher levels of abstraction, providing progressively summarized visual overviews of the attack graph. We describe rich visual representations that capture relationships among our semantically-relevant attack graph abstractions, and our views

This paper addresses the inference problem in on-line analytical processing (OLAP) systems. The inference problem occurs when the exact values of sensitive attributes can be determined through answers to OLAP queries. Most existing inference control methods are computationally expensive for OLAP systems, because they ignore the special structures of OLAP queries. By exploiting such structures, we derive cardinality-based sufficient conditions for safe OLAP data cubes. Specifically, data cubes are safe from inferences if their core cuboids are dense enough, in the sense that the number of known values is under a tight bound. We then apply the sufficient conditions on the basis of a three-tier inference control model. The model introduces an aggregation tier between data and queries. The aggregation tier represents a collection of safe data cubes that are pre-computed over a partition of the data using the proposed sufficient conditions. The aggregation tier is then used to provide users with inference-free queries. Our approach mitigates the performance penalty of inference control, because partitioning the data yields smaller input to inference control algorithms, pre-computing the aggregation tier reduces on-line delay, and using cardinality-based conditions guarantees linear-time complexity.

In-depth analysis of network security vulnerability must consider attacker exploits not just in isolation, but also in combination. The general approach to this problem is to compute attack paths (combinations of exploits), from which one can decide whether a given set of network hardening measures guarantees the safety of given critical resources. We go beyond attack paths to compute actual sets of hardening measures (assignments of initial network conditions) that guarantee the safety of given critical resources. Moreover, for given costs associated with individual hardening measures, we compute assignments that minimize overall cost. By doing our minimization at the level of initial conditions rather than exploits, we resolve hardening irrelevancies and redundancies in a way that cannot be done through previously proposed exploit-level approaches. Also, we use an efficient exploit-dependency representation based on monotonic logic that has polynomial complexity, as opposed to many previous attack graph representations having exponential complexity.

The scope and character of today's computing environments are progressively shifting from traditional, one-on-one client-server interaction to the new cooperative paradigm. It then becomes of primary importance to provide means of protecting the secrecy of the information, while guaranteeing its availability to legitimate clients. Operating on-line querying services securely on open networks is very difficult; therefore many enterprises outsource their data center operations to external application service providers. A promising direction towards prevention of unauthorized access to outsourced data is represented by encryption. However, data encryption is often supported for the sole purpose of protecting the data in storage and assumes trust in the server, that decrypts data for query execution.In this paper, we present a simple yet robust single-server solution for remote querying of encrypted databases on untrusted servers. Our approach is based on the use of indexing information attached to the encrypted database which can be used by the server to select the data to be returned in response to a query without the need of disclosing the database content. Our indexes balance the trade off between efficiency requirements in query execution and protection requirements due to possible inference attacks exploiting indexing information. We also investigate quantitative measures to model inference exposure and provide some related experimental results.

In this paper, we describe LEAP (Localized Encryption and Authentication Protocol), a key management protocol for sensor networks that is designed to support in-network processing, while at the same time restricting the security impact of a node compromise to the immediate network neighborhood of the compromised node. The design of the protocol is motivated by the observation that different types of messages exchanged between sensor nodes have different security requirements, and that a single keying mechanism is not suitable for meeting these different security requirements. LEAP supports the establishment of four types of keys for each sensor node -- an individual key shared with the base station, a pairwise key shared with another sensor node, a cluster key shared with multiple neighboring nodes, and a group key that is shared by all the nodes in the network. The protocol used for establishing and updating these keys is communication- and energy-efficient, and minimizes the involvement of the base station. LEAP also includes an efficient protocol for inter-node traffic authentication based on the use of one-way key chains. A salient feature of the authentication protocol is that it supports source authentication without precluding in-network processing and passive participation. We analyze the performance and the security of our scheme under various attack models and show our schemes are very efficient in defending against many attacks.

Shared scientific data, such as neuroimagery, offers great benefits to science. However, data owners must exercise custodial responsibilities which can conflict with the unhindered sharing of their data. Given simple choices of sharing widely or not at all, the result will frequently be no sharing. We hypothesize that neuroimagery sharing will be enhanced if data owners are provided with well-defined intermediate levels of data visibility. In this paper, we describe a broadly applicable data sharing model, Structured Sharing Communities (SSC), in which data becomes incrementally visible to communities structured as a complete partial-order; the associated properties of Privacy and Fairness regulate access to shared data. Within SSC, a customized policy space is defined capturing the sharing relationships among specific collaborators.

Agrawal and Kiernan's watermarking technique for database relations [1] and Li et al's fingerprinting extension [6] both depend critically on primary key attributes. Hence, those techniques cannot embed marks in database relations without primary key attributes. Further, the techniques are vulnerable to simple attacks that alter or delete the primary key attribute.This paper proposes a new fingerprinting scheme that does not depend on a primary key attribute. The scheme constructs virtual primary keys from the most significant bits of some of each tuple's attributes. The actual attributes that are used to construct then virtual primary key differ from tuple to tuple. Attribute selection is based on a secret key that is known to the merchant only. Further, the selection does not depend on an apriori ordering over the attributes, or on knowledge of the original relation or fingerprint codeword.The virtual primary keys are then used in fingerprinting as in previous work [6]. Rigorous analysis shows that, with high probability, only embedded fingerprints can be detected and embedded fingerprints cannot be modified or erased by a variety of attacks. Attacks include adding, deleting, shuffling, or modifying tuples or attributes (including a primary key attribute if one exists), guessing secret keys, and colluding with other recipients of a relation.

Recently, many group key management approaches based on the use of logical key trees have been proposed to address the issue of scalable group rekeying that is needed to support secure communications for large and dynamic groups. In this paper, we present two optimizations for logical key tree organizations that utilize information about the characteristics of group members to further reduce the overhead of group rekeying. First, we propose a partitioned key tree organization that exploits the temporal patterns of group member joins and departures to reduce the overhead of rekeying. Using an analytic model, we show that our optimization can achieve up to 31.4% reduction in key server bandwidth overhead over the unoptimized scheme. Second, we propose an approach under which the key tree is organized based on the loss probabilities of group members. Our analysis shows this optimization can reduce the rekeying overhead by up to 12.1%.

A prerequisite for a secure communication between two nodes in an ad hoc network is that the nodes share a key to bootstrap their trust relationship. In this paper, we present a scalable and distributed protocol that enables two nodes to establish a pairwise shared key on the fly, without requiring the use of any on-line key distribution center. The design of our protocol is based on a novel combination of two techniques - probabilistic key sharing and threshold secret sharing. Our protocol is scalable since every node only needs to possess a small number of keys, independent of the network size, and it is computationally efficient because it only relies on symmetric key cryptography based operations. We show that a pairwise key established between two nodes using our protocol is secure against a collusion attack by up to a certain number of compromised nodes. We also show through a set of simulations that our protocol can be parameterized to meet the desired levels of performance, security and storage for the application under consideration.

In this paper, we describe LEAP (Localized Encryption and Authentication Protocol), a key management protocol for sensor networks that is designed to support in-network processing techniques such as passive participation. LEAP includes support for multiple symmetric keying mechanisms including individual keys, pairwise shared keys, cluster keys, and a group key. This design is based on the observation that different types of messages exchanged between sensor nodes have different security requirements, and a single keying mechanism is not suitable for meeting these different security requirements.

We consider the problem of malicious attacks that lead to corruption of files in a file system. A typical method to detect such corruption is to compute signatures of all the files and store these signatures in a secure place. A malicious modification of a file can be detected by verifying the sign ature. This method, however, leaves the system vulnerable to an attacker who has access to some of the files and the signatures (but not the signing transformation) and who replaces some of the files by their old versions and the corresponding signatures by the signatures of the old versions. In this paper, we present a technique called Check2 that also relies on signatures for detecting corruption of files. The novel feature of our approach is that we compute additional levels of signatures to guarantee that any change of a file and the corresponding signature will require an attacker to perform a very lengthy chain of precise changes to successfully complete the corruption in an undetected manner. If an attacker fails to complete all the required changes, Check2 can be used to pinpoint which files have been corrupted. Two alternative ways of implementing Check2 are offered, the first using a deterministic way of combining signatures and the second using a randomized scheme. Our results show that the overhead added to the system is minimal.

Security-sensitive environments protect their information resources against unauthorized use by enforcing access control mechanisms driven by access control policies. Due to the need to compare, contrast, and compose such protected information resources, access control policies regulating their manipulation need to be compared, contrasted, and composed. An algebra for manipulating such access control policies at a higher (propositional) level, where the operations of the algebra are abstracted from their specification details, is the subject of this paper. This algebra is applicable to policies that have controlled nondeterminism and all or nothing assignments of access privileges in their specification. These requirements reflect current practices in discretionary and role-based access control models. Therefore, the proposed algebra can be used to reason about role-based access control policies combined with other forms of discretionary policies. We show how to use algebraic identities to reason about consistency, completeness, and determinacy of composed policies using similar properties of their constituents.

The Flexible Authorization Framework (FAF) defined by Jajodia et al. [2001] provides a policy-neutral framework for specifying access control policies that is expressive enough to specify many known access control policies. Although the original formulation of FAF indicated how rules could be added to or deleted from a FAF specification, it did not address the removal of access permissions from users. We present two options for removing permissions in FAF and provide details on the option which is representation independent.

We present a distributed algorithm for file allocation that guarantees high assurance, availability, and scalability in a large distributed file system. The algorithm can use replication and fragmentation schemes to allocate the files over multiple servers. The file confidentiality and integrity are preserved, even in the presence of a successful attack that compromises a subset of the file servers. The algorithm is adaptive in the sense that it changes the file allocation as the read-write patterns and the location of the clients in the network change. We formally prove that, assuming read-write patterns are stable, the algorithm converges toward an optimal file allocation, where optimality is defined as maximizing the file assurance.

This paper deals with the algebra used to compose access control policies of collaborating organizations. To maintain a conceptual coherence and to have a common basis for comparison, we seek a framework that can be viewed at different levels of abstraction. In [21, 22], we presented a propositional version of the algebra that can support algebraic manipulations of uninterpreted policies. This paper extends the algebra to many sorted first order predicate case. The predicate version can be used to reason about first order properties of security policies from their components. We show how to compose and reason about security properties such as those used in role based access control models usually specified using second order (set) quantifiers in languages (see RCL2000 [1]). We also show how different application specific notions of consistency and completeness can be formulated as sentences in our many sorted first order logic and propose a Hoare calculus to reason about them.

Recently, association rules have been used to generate profiles of “normal” behavior for anomaly detection. However, the time factor (especially in terms of multiple time granularities) has not been utilized extensively in generation of these profiles. In reality, user behavior during different tim e intervals may be very different. For example, the “normal” number and duration of FTP connections may vary from working hours to midnight, from business day to weekend or holiday. Furthermore, these variations may depend on the day of the month or the week. This paper proposes to build profiles using temporal association rules in terms of multiple time granularities, and describes algorithms to discover these profiles. Because multiple time granularities are used for the profile generation, the proposed method is more flexible and precise than previous methods that use fixed partition of time intervals. Finally, the paper describes an experiment and its preliminary result on TCP-dump data.

Preventive measures sometimes fail to deflect malicious attacks. We adopt an information warfare perspective, which assumes success by the attacker in achieving partial, but not complete, damage. In particular, we work in the database context and consider recovery from malicious but committed transactions. Traditional recovery mechanisms do not address this problem, except for complete rollbacks, which undo the work of benign transactions as well as malicious ones, and compensating transactions, whose utility depends on application semantics. Recovery is complicated by the presence of benign transactions that depend, directly or indirectly, on the malicious transactions. We present algorithms to restore only the damaged part of the database. We identify the information that needs to be maintained for such algorithms. The initial algorithms repair damage to quiescent databases; subsequent algorithms increase availability by allowing new transactions to execute concurrently with the repair process. Also, via a study of benchmarks, we show practical examples of how offline analysis can efficiently provide the necessary data to repair the damage of malicious transactions.

Although different organizations operate under different requirements for protection of their data, increasingly there is a need for organizations to connect their computing resources together to achieve common goals. The fundamental problem addressed in this paper is to capture the algebra used in composing access control policies of collaborating organizations. In doing so, we seek a framework that can be viewed at many levels of abstraction (such as abstract vs. explicit or propositional vs. predicate), independent of implementation mechanisms and environments, and is expressive enough to model existing practices of policy compositions.Propositional version consists of a syntax where policies are viewed as abstract symbols, and semantics consists of authorization state transformers, where an authorization state is a collection of (subject, object, access set) triples and a set of propositions satisfied by them. Syntactic rules are provided to simplify policy expressions without knowing their semantics, thereby supporting algebraic manipulations of uninterpreted policies. Because our algebra is at an abstract level, it can model any policy independent of the language that is used to implement it. We show how to reason about completeness, consistency, unambiguity and of abstractly specified policies and their semantic equivalence.

In an ownership-based framework for access control, with the possibility of granting access and administrative rights, chains of granted accesses will form. This is a comprehensive study of the problem of revoking such rights, and on the impact different revocation schemes may have on the chains. Three main revocation characteristics are identified: the extent of the revocation to other grantees (propagation), the effect on other grants to the same grantee (dominance), and the permanence of the negation of rights (resilience). A classification is devised using these three dimensions. The different schemes thus obtained are described, and compared to other models from the literature.

Preventive measures sometimes fail to defect malicious attacks. With cyber attacks on data-intensive applications becoming an ever more serious threat, intrusion tolerant database systems are a significant concern. Intrusion detectors are a key component of an intrusion tolerant database system. However, a relatively long detection latency is usually unavoidable for detection accuracy, especially in anomaly detection, and it can cause ineffective- to some degree at least- damage confinement. In a busy database ineffective confinement can make the database too damaged to be useful. In this paper, we present an innovative multi-phase damage confinement approach to solve this problem. In contract to a traditional one-phase confinement approach our approach has one confining phase to quickly confine the damage, and one or more later on unconfining phases to unconfine the objects that are mistakenly confined during the first phase. Our approach can ensure no damage spreading after the detection time, although some availability can be temporarily lost. Our approach can be easily extended to support flexible control of damage spreading and multiple confinement policies. Our approach is practical, effective, efficient, and to a large extent assessment independent.

1 Introduction From the first appearance of network attacks, the internet worm, to the most recent one in which the servers of several famous e-business companies were paralyzed for several hours, causing huge financial losses, network-based attacks have been increasing in frequency and severity. As a powerful weapon to protect networks, intrusion detection has been gaining a lot of attention.

A temporal association rule is an association rule that holds during specific time intervals. An example is that eggs and coffee are frequently sold together in morning hours. The paper studies temporal association rules during the time intervals specified by user-given calendar schemas. Generally, the use of calendar schemas makes the discovered temporal association rules easier to understand. An example of calendar schema is (year, month, day), which yields a set of calendar-based patterns of the form (d/sub 3/, d/sub 2/, d/sub 1/), where each d/sub i/ is either an integer or the symbol *. For example, (2000, *, 16) is such a pattern, which corresponds to the time intervals, each consisting of the 16th day of a month in year 2000. This paper defines two types of temporal association rules: precise-match association rules require that the association rule holds during every interval, and fuzzy-match ones require that the association rule holds during most of these intervals. The paper extends the well-known a priori algorithm, and also develops two optimization techniques to take advantage of the special properties of the calendar-based patterns. The experiments show that the algorithms and optimization techniques are effective.

Since 1990, transaction processing in multilevel secure database management systems (DBMSs) has been receiving a great deal of attention from the security community. Transaction processing in these systems requires modification of conventional scheduling algorithms and commit protocols. These modifications are necessary because preserving the usual transaction properties when transactions are executing at different security levels often conflicts with the enforcement of the security policy. Considerable effort has been devoted to the development of efficient, secure algorithms for the major types of secure DBMS architectures: kernelized, replicated, and distributed. An additional problem that arises uniquely in multilevel secure DBMSs is that of secure, correct execution when data at multiple security levels must be written within one transaction. Significant progress has been made in a number of these areas, and a few of the techniques have been incorporated into commercial trusted DBMS products. However, there are many open problems remain to be explored. This paper reviews the achievements to date in transaction processing for multilevel secure DBMSs. The paper provides an overview of transaction processing needs and solutions in conventional DBMSs as background, explains the constraints introduced by multilevel security, and then describes the results of research in multilevel secure transaction processing. Research results and limitations in concurrency control, multilevel transaction management, and secure commit protocols are summarized. Finally, important new areas are identified for secure transaction processing research.

Abstraction is an important issue in intrusion detection, since it not only hides the difference between heterogeneous systems, but also allows generic intrusion-detection models. However, abstraction is an error-prone process and is not well supported in current intrusion-detection systems (IDSs). This article presents a hierarchical model to support attack specification and event abstraction in distributed intrusion detection. The model involves three concepts: system view , signature , and view definition . A system view provides an abstract interface of a particular type of information; defined on the instances of system views, a signature specifies certain distributed attacks or events to be monitored; a view definition is then used to derive information from the matches of a signature and presents it through a system view. With the three elements, the model provides a hierarchical framework for maintaining signatures, system views, as well as event abstraction. As a benefit, the model allows generic signatures that can accommodate unknown variants of known attacks. Moreover, abstraction represented by a system view can be updated without changing either its specification or the signatures specified on its basis. This article then presents a decentralized method for autonomous but cooperative component systems to detect distributed attacks specified by signatures. Specifically, a signature is decomposed into finer units, called detection tasks , each of which represents the activity to be monitored on a component system. The component systems (involved in a signature) then perform the detection tasks cooperatively according to the "dependency" relationships among these tasks. An experimental system called CARDS has been implemented to test the feasibility of the proposed approach.

Public key management has received considerable attention from both the research and commercial communities as a useful primitive for secure electronic commerce and secure communication. While the mechanics of certifying and revoking public keys and escrowing and recovering private keys have been widely explored, less attention has been paid to access control frameworks for regulating access to stored keys by different parties. In this article we propose such a framework for a key management service that supports public key registration, lookup, and revocation, and private key escrow, protected use (e.g., to decrypt selected messages), and recovery. We propose an access control model using a policy based on principal, ownership, and authority relationships on keys. The model allows owners to grant to others (and revoke) privileges to execute various actions on their keys. The simple authorization language is very expressive, enabling the specification of authorizations for composite subjects that can be fully specified (ground) or partially specified, thus making the authorizations applicable to all subjects satisfying some conditions. We illustrate how the access control policy and the authorizations can easily be expressed through a simple and restricted, hence efficiently computable, form of logic language.

Although several access control policies can be devised for controlling access to information, all existing authorization models, and the corresponding enforcement mechanisms, are based on a specific policy (usually the closed policy). As a consequence, although different policy choices are possible in theory, in practice only a specific policy can actually be applied within a given system. In this paper, we present a unified framework that can enforce multiple access control policies within a single system. The framework is based on a language through which users can specify security policies to be enforced on specific accesses. The language allows the specification of both positive and negative authorizations and incorporates notions of authorization derivation, conflict resolution, and decision strategies. Different strategies may be applied to different users, groups, objects, or roles, based on the needs of the security policy. The overall result is a flexible and powerful, yet simple, framework that can easily capture many of the traditional access control policies as well as protection requirements that exist in real-world applications, but are seldom supported by existing systems. The major advantage of our approach is that it can be used to specify different access control policies that can all coexist in the same system and be enforced by the same security server.

Many electronic commerce applications, including those developed for business-to-consumer (B2C) and business-to-business (B2B) uses, require operations in computing environments that are truly distributed. That is, users can request data access from multiple locations within a distributed computing system. To complicate this type of operation, however, data can be distributed and represented in multiple forms. As a result, system administrators are encountering increasing difficulty in developing and managing application-specific policies for users and data. A multi-tier (N-tier) architecture can provide a powerful solution for meeting the diverse needs of the electronic commerce applications. However, a drawback to multi-tier architectures is that they require that a user's credentials and the policy-to-data mapping context must be available in the middle tier of the system architecture. This paper addresses the management of users and data by presenting a framework for combining attribute certificates with a mobile policy for effective application-specific control specification and administration in a distributed computing environment. Attribute certificates provide mobility to credentials and also provide fine-grained information about security principles. A mobile policy allows application-specific policies to move along with the data to other elements of the distributed computing system. We propose a high-level definition language to specify policies that are application-specific and mobile, and present an algorithm for enforcing attribute-based mobile policies.

Fair exchange between two or more potentially mutually distrusted parties has been identified as an important issue in electronic commerce. However, the correctness (fairness) of the existing fair exchange protocols that use a trusted third party (TTP) is based on the assumption that, during an exchange, there are no failures at any of the local systems involved in the exchange, which is too strong in many situations. This paper points out that (1) system failures could cause loss of fairness, and (2) existing fair exchange protocols that use TTPs cannot ensure fairness in presence of system failures. We present a systematic way to develop such data exchange systems that can recover from system failures without losing fairness. We identify a set of fairness loss risks caused by local system failures. We identify a fault-tolerance correctness criterion for fair data exchange, denoted "fairness-lossless recoverability". A fairness-lossless recoverable fair exchange system is immune from the set of fairness loss risks. Standard message logging approaches are then studied and extended to achieve fairness-lossless recoverability with good performance.

The authors describe a novel approach to scalable group re-keying for secure multicast. Our approach, which we call Kronos, is based upon the idea of periodic group re-keying. We first motivate our approach by showing that if a group is re-keyed on each membership change, as the size of the group increases and/or the rate at which members leave and join the group increases, the frequency of rekeying becomes the primary bottle neck for scalable group re-keying. In contrast, Kronos can scale to handle large and dynamic groups because the frequency of re-keying is independent of the size and membership dynamics of the group. Next, we describe how Kronos can be used in conjunction with distributed key management frameworks such as IGKMP (T. Hardjono et al., 1998) that use a single group-wide session key for encrypting communications between members of the group. Using a detailed simulation, we compare the performance tradeoffs between Kronos and other key management protocols.

System protection mechanisms such as access controls can be fooled by authorized but malicious users, masqueraders, and misfeasors. Intrusion detection techniques are therefore used to supplement them. However, damage could have occurred before an in

Investigates the problem of inference channels that occur when database constraints are combined with non-sensitive data to obtain sensitive information. We present an integrated security mechanism, called the Disclosure Monitor, which guarantees data confidentiality by extending the standard mandatory access control mechanism with a Disclosure Inference Engine. This generates all the information that can be disclosed to a user based on the user's past and present queries and the database and metadata constraints. The Disclosure Inference Engine operates in two modes: a data-dependent mode, when disclosure is established based on the actual data items, and a data-independent mode, when only queries are utilized to generate the disclosed information. The disclosure inference algorithms for both modes are characterized by the properties of soundness (i.e. everything that is generated by the algorithm is disclosed) and completeness (i.e. everything that can be disclosed is produced by the algorithm). The technical core of this paper concentrates on the development of sound and complete algorithms for both data-dependent and data-independent disclosures.

The classical Early Prepare (EP) commit protocol, used in many commercial systems, is not suitable for use in multi-level secure (MLS) distributed database systems that employ a locking protocol for concurrency control. This is because EP requires that read locks are not released by a participant during their window of uncertainty; however, it is not possible for a locking protocol to provide this guarantee in a MLS system (since the read lock of a higher-level transaction on a lower-level data object must be released whenever a lower-level transaction wants to write the same data). The only available work in the literature, namely the Secure Early Prepare (SEP) protocol, overcomes this difficulty by aborting those distributed transactions that release their low-level read locks prematurely. We see this approach as being too restrictive. One of the major benefits of distributed processing is its robustness to failures, and SEP fails to take advantage of this. In this paper, we propose the Advanced Secure Early Prepare (ASEP) commit protocol to solve the above problem, together with a number of language primitives that can be used as system calls in distributed transactions. These primitives permit features like partial rollback and forward recovery to be incorporated within the transaction model, and allow a distributed transaction to proceed even when a participant has released its low-level read locks prematurely. This not only offers flexibility, but can also be used, if desired, by a sophisticated programmer to trade off consistency for atomicity of the distributed transaction.

Recently, application-level isolation was introduced as an effective means of containing the damage that a suspicious user could inflict on data. In most cases, only a subset of the data items needs to be protected from damage due to the criticality level or integrity requirements of the data items. In such a case, complete isolation of a suspicious user can consume more resources than necessary. The paper proposes partitioning the data items into categories based on their criticality levels and integrity requirements; these categories determine the allowable data flows between trustworthy and suspicious users. An algorithm that achieves good performance when the number of data items is small, is also provided to detect inconsistencies between suspicious versions of the data and the main version.

Update anywhere-anytime-anyway transactional replication has unstable behavior as the workload scales up. To reduce this problem, a two-tier replication algorithm is proposed in (Gray et al., 1996) that allows mobile applications to propose tentative transactions that are later applied to a master copy. However it can suffer from heavy reprocessing overhead in many circumstances. We present the method of merging histories instead of reprocessing to reduce the overhead of two-tier replication. The basic idea is when a mobile node connects to the base nodes merging the tentative history into the base history so that substantial work of tentative transactions could be saved. As a result, a set of undesirable transactions (denoted B) have to be backed out to resolve the conflicts between the two histories. Desirable transactions that are affected directly or indirectly, by the transactions in B complicate the process of backing out B. We present a family of novel rewriting algorithms for the purpose of backing out B. By incorporating transaction semantics, our rewriting methods are strictly better at saving desirable tentative transactions than the traditional reads-from transitive-closure based approach. In most cases our rewriting methods are better at saving desirable tentative transactions than an approach which is based only on commutativity.

In this article, we present an authorization model that can be used to express a number of discretionary access control policies for relational data management systems. The model permits both positive and negative authorizations and supports exceptions at the same time. The model is flexible in that the users can specify, for each authorization they grant, whether the authorization can allow for exceptions or whether it must be strongly obeyed. It provides authorization management for groups with exceptions at any level of the group hierarchy, and temporary suspension of authorizations. The model supports ownership together with decentralized administration of authorizations. Administrative privileges can also be restricted so that owners retain control over their tables.

System protection mechanisms such as access controls can be fooled by authorized but malicious users, masqueraders, and misfeasors. Intrusion detection techniques are therefore used to supplement them. The capacity of these techniques, however is limited: innocent users may be mistaken for malicious ones while malicious users stay at large. Isolation is a method that has been applied to protect systems from damage while investigating further. This paper proposes the use of isolation at an application level to gain its benefits while minimizing loss of resources and productive work in the case of incidents later deemed innocent. We describe our scheme in the database context. It isolates the database transparently from further damage by users suspected to be malicious, while still maintaining continued availability for their transactions. Isolation is complicated by the inconsistencies that may develop between isolated database versions. We present both static and dynamic approaches to identify and resolve conflicts. Finally, we give several examples of applications in which the isolation scheme should be worthwhile and be able to achieve good performance.

Most concurrency control algorithms for multilevel secure databases based on kernelized architecture prevent covert channels between transactions at different security levels by preempting the high security transaction in the event of a data conflict with a lower security transaction. In environments with moderate to high levels of contention between low and high security transactions, this can lead to poor performance and even starvation of high security transactions. We examine this problem of unfairness in concurrency control mechanisms for secure databases. Based on an analysis of the performance of a secure version of two phase locking, we propose three different modifications to the protocol that address the problem of starvation of high security transactions. Through a detailed simulation study, we examine the fairness and performance of these approaches for a variety of workloads.

A typical misuse detection system contains: (1) a language for describing known techniques (called misuse signatures) used by attackers to penetrate the target system, and (2) monitoring programs for detecting the presence of an attack based on the given misuse signatures. In most of the systems appearing in the literature, however, the description of misuses is often in terms of a low level language (i.e. in terms of audit records of the target system), that either has limited expressiveness or is difficult to use. Moreover the monitoring algorithms are often fixed and do not adapt to a changing operating environment or to objectives of the site security officer. To overcome these limitations, the paper defines a high level language for abstract misuse signatures (MuSigs). Due to the use of high level concepts, a MuSig can represent misuses in a simple form and yet with high expressiveness. The paper also introduces a set of system directives provided by the system designer in support of high level concepts. The paper then discusses ways to translate MuSigs into monitoring program with the help of the system directives. The adaptability of the system is obtained by the ability for the site security officer to add or delete system directives to change the behavior of the monitoring program.

Multilevel transactions have been proposed for multilevel secure databases; in contrast to most proposals, such transactions allow users to read and write across multiple security levels. The security requirement that no high level operation influence a low level operation often conflicts with the atomicity requirement of the standard transaction processing model. In particular, others have shown that no concurrency control algorithm based on the standard transaction processing model can guarantee both atomicity and security. This conflict motivates us to propose an alternative semantic-based transaction processing model for multilevel transactions. Our model uses the semantics of the application to analyze an application and reason about its behavior. Our notion of correctness is based on semantic correctness instead of serializability as in the standard transaction processing model. Semantic correctness ensures that database consistency is maintained, transactions output consistent data, and all partially executed transactions complete. We show how an example application can be analyzed to assure semantic correctness and how this analysis can be automated. We also propose a simple timestamp-based multiversion concurrency control algorithm for transaction processing on a kernelized architecture. The advantages of our model over the standard transaction processing model are that atomicity can be assessed, and for some applications ensured via off line analysis, more concurrency is achieved, lesser synchronization between security levels is required, and a larger class of multilevel transactions can be processed.

The concurrency control requirements for transaction processing in a multilevel secure file system are different from those in conventional transaction processing systems. In particular, there is the need to coordinate transactions at different security levels avoiding both potential timing covert channels and the starvation of transactions at higher security levels. Suppose a transaction at a lower security level attempts to write a data item that is being read by a transaction at a higher security level. On the one hand, a timing covert channel arises if the transaction at the lower security level is either delayed or aborted by the scheduler. On the other hand, the transaction at the high security level may be subjected to an indefinite delay if it is forced to abort repeatedly. This paper extends the classical two-phase locking mechanism to multilevel secure file systems. The scheme presented here prevents potential timing covert channels and avoids the abort of higher level transactions nonetheless guaranteeing serializability. The programmer is provided with a powerful set of linguistic constructs that supports exception handling, partial rollback, and forward recovery. The proper use of these constructs can prevent the indefinite delay in completion of a higher level transaction, and allows the programmer to trade off starvation with transaction isolation.

Data explicitly stored in a temporal database are often associated with certain semantic assumptions. Each assumption can be viewed as a way of deriving implicit information from explicitly stored data. Rather than leaving the task of deriving (possibly infinite) implicit data to application programs, as is the case currently, it is desirable that this be handled by the database management system. To achieve this, the paper formalizes and studies two types of semantic assumptions: point based and interval based. The point based assumptions include those assumptions that use interpolation methods over values at different time instants, while the interval based assumptions include those that involve the conversion of values across different time granularities. The paper presents techniques on: (1) how assumptions on specific sets of attributes can be automatically derived from the specification of interpolation and conversion functions; and (2) given the representation of assumptions, how a user query can be converted into a system query such that the answer of this system query over the explicit data is the same as that of the user query over the explicit and the implicit data. To precisely illustrate concepts and algorithms, the paper uses a logic based abstract query language. The paper also shows how the same concepts can be applied to concrete temporal query languages.

An important usage of time sequences is to discover temporal patterns. The discovery process usually starts with a user specified skeleton, called an event structure, which consists of a number of variables representing events and temporal constraints among these variables; the goal of the discovery is to find temporal patterns, i.e., instantiations of the variables in the structure that appear frequently in the time sequence. The paper introduces event structures that have temporal constraints with multiple granularities, defines the pattern discovery problem with these structures, and studies effective algorithms to solve it. The basic components of the algorithms include timed automata with granularities (TAGs) and a number of heuristics. The TAGs are for testing whether a specific temporal pattern, called a candidate complex event type, appears frequently in a time sequence. Since there are often a huge number of candidate event types for a usual event structure, heuristics are presented aiming at reducing the number of candidate event types and reducing the time spent by the TAGs testing whether a candidate type does appear frequently in the sequence. These heuristics exploit the information provided by explicit and implicit temporal constraints with granularity in the given event structure. The paper also gives the results of an experiment to show the effectiveness of the heuristics on a real data set.

Although several access control policies can be devised for controlling access to information, all existing authorization models, and the corresponding enforcement mechanisms, are based on a specific policy (usually the closed policy). As a consequence, although different policy choices are possible in theory, in practice only a specific policy can be actually applied within a given system. However, protection requirements within a system can vary dramatically, and no single policy may simultaneously satisfy them all.

We consider the problem of surviving information warfare attacks on databases. We adopt a fault tolerance approach to the different phases of an attack. To maintain precise information about the attack, we mark data to reflect the severity of detected damage as well as the degree to which the damaged data has been repaired. In the case of partially repaired data, integrity constraints might be violated, but data is nonetheless available to support mission objectives. We define a notion of consistency suitable for databases in which some information is known to be damaged, and other information is known to be only partially repaired. We present a protocol for normal transactions with respect to the damage markings and show that consistency preserving normal transactions maintain database consistency in the presence of damage. We present an algorithm for taking consistent snapshots of databases under attack. The snapshot algorithm has the virtue of not interfering with countermeasure transactions.

This paper presents an approach to control information flow in object-oriented systems that takes into account, besides authorizations on objects, also how the information has been obtained and/or transmitted. These aspects are considered by allowing exceptions to the restrictions stated by the authorizations. Exceptions are specified by means of waivers associated with methods. Two kinds of waivers are supported: invoke-waivers, specifying exceptions applicable during a method's execution, and reply-waivers, specifying exceptions applicable to the information returned by a method. Information flowing from one object into another object is subject to the different waivers of the methods enforcing the transmission. We formally characterize information transmission and flow in a transaction taking into consideration different interaction modes among objects. We then define security specifications, meaning authorizations and waivers, and characterize safe information flows. We formally define conditions whose satisfaction ensures absence of unsafe flows and present an algorithm enforcing these conditions.

A major drawback of existing access control systems is that they have all been developed with a specific access control policy in mind. This means that all protection requirements (i.e. accesses to be allowed or denied) must be specified in terms of the policy enforced by the system. While this may be trivial for some requirements, specification of other requirements may become quite complex or even impossible. The reason for this is that a single policy simply cannot capture the different protection requirements that users may need to enforce on different data. In this paper, we take a first step towards a model that is able to support different access control policies. We propose a logical language for the specification of authorizations on which such a model can be based. The Authorization Specification Language (ASL) allows users to specify, together with the authorizations, the policy according to which access control decisions are to be made. Policies are expressed by means of rules which enforce the derivation of authorizations, conflict resolution, access control and integrity constraint checking. We illustrate the power of our language by showing how different constraints that are sometimes required, but very seldom supported by existing access control systems, can be represented in our language.

Multilevel security poses many challenging problems for transaction processing. The challenges are due to the conflicting requirements imposed by confidentiality, integrity, and availability-the three components of security. We identify these requirements on transaction processing in Multilevel Secure (MLS) database management systems (DBMSs) and survey the efforts of a number of researchers to meet these requirements. While our emphasis is primarily on centralized systems based on kernelized architecture, we briefly overview the research in the distributed MLS DBMSs as well.

We propose two extensions to the authorization model for relational databases defined originally by P.G. Griffiths and B. Wade (1976). The first extension concerns a new type of revoke operation, called noncascading revoke operation. The original model contains a single, cascading revoke operation, meaning that when a privilege is revoked from a user, a recursive revocation takes place that deletes all authorizations granted by this user that do not have other supporting authorizations. The new type of revocation avoids the recursive revocation of authorizations. The second extension concerns negative authorization which permits specification of explicit denial for a user to access an object under a particular mode. We also address the management of views and groups with respect to the proposed extensions.

We describe a high assurance discretionary access control model for object oriented systems. The model not only ensures protection against Trojan horses leaking information, but provides the flexibility of discretionary access control at the same time. The basic idea of our approach is to check all information flows among objects in the system in order to block possible illegal flows. An illegal flow arises when information is transmitted from one object to another object in violation of the security policy. The interaction modes among objects are taken into account in determining illegal flows. We consider three different interaction modes that are standard interaction modes found in the open distributed processing models. The paper presents formal definitions and proof of correctness of our flow control algorithm.

In some database applications the traditional approach of seerializability, in which transactions appear to execute atomically and in isolation on a consistent database state, fails to satisfy performance requirements. Although many researchers have investigated the process of decomposing transactions into steps to increase concurrency, such research typically focuses on providing algorithms necessary to implement a decomposition supplied by the database application developer and pays relatively little attention to what constitutess a desirable decomposition or how the developer should obtain one. We focus onthe decomposition itself. A decomposition generates proof obligations whose descharge ensures desirable properties with respect to the original collection of transactions. We introduce the notion of semantic histories to formulate and prove the necessary properties, and the notion of successor sets to describe efficiently the correct interleavings of steps. The successor set constraints use information about conflicts between steps so as to take full advantage of conflict serializability at the level of steps. We propose a mechanism based on two-phase locking to generate correct stepwise serializable histories.

The purpose of good database logical design is to eliminate data redundancy and isertion and deletion anomalies. In order to achieve this objective for temporal databases, the notions of temporal types , which formalize time granularities, and temporal functional dependencies (TFDs) are intrduced. A temporal type is a monotonic mapping from ticks of time (represented by positive integers) to time sets (represented by subsets of reals) and is used to capture various standard and user-defined calendars. A TFD is a proper extension of the traditional functional dependency and takes the form X → μ Y, meaning that there is a unique value for Y during one tick of the temporal type μ for one particular X value. An axiomatization for TFDs is given. Because a finite set TFDs usually implies an infinite number of TFDs, we introduce the notion of and give an axiomatization for a finite closure to effectively capture a finite set of implied TFDs that are essential of the logical design. Temporal normalization procedures with respect to TFDs are given. Specifically, temporal Boyce-Codd normal form (TBCNF) that avoids all data redundancies due to TFDs, and temporal third normal form (T3NF) that allows dependency preservation, are defined. Both normal forms are proper extensions of their traditional counterparts, BCNF and 3NF. Decompositition algorithms are presented that give lossless TBCNF decompositions and lossless, dependency-preserving, T3NF decompositions.

This article addresses the performance of distributed database systems. Specifically, we present an algorithm for dynamic replication of an object in distributed systems. The algorithm is adaptive in the sence that it changes the replication scheme of the object i.e., the set of processors at which the object inreplicated) as changes occur in the read-write patern of the object (i.e., the number of reads and writes issued by each processor). The algorithm continuously moves the replication scheme towards an optimal one. We show that the algorithm can be combined with the concurrency control and recovery mechanisms of ta distributed database management system. The performance of the algorithm is analyzed theoretically and experimentally. On the way we provide a lower bound on the performance of any dynamic replication algorith.

Article A non-timestamped authorization model for data management systems Share on Authors: Elisa Bertino Dipartimento di Scienze dell'Informazione, Università di Milano, Via Comelico, 39/41, 20135 Milano, Italy Dipartimento di Scienze dell'Informazione, Università di Milano, Via Comelico, 39/41, 20135 Milano, ItalyView Profile , Sushil Jajodia Center for Secure Information Systems, Department of Information and Software Systems Engineering, George Mason University, Fairfax, VA Center for Secure Information Systems, Department of Information and Software Systems Engineering, George Mason University, Fairfax, VAView Profile , Pierangela Samarati Dipartimento di Scienze dell'Informazione, Università di Milano, Via Comelico, 39/41, 20135 Milano, Italy Dipartimento di Scienze dell'Informazione, Università di Milano, Via Comelico, 39/41, 20135 Milano, ItalyView Profile Authors Info & Claims CCS '96: Proceedings of the 3rd ACM conference on Computer and communications securityJanuary 1996 Pages 169–178https://doi.org/10.1145/238168.238211Published:01 January 1996 8citation461DownloadsMetricsTotal Citations8Total Downloads461Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The classical Early Prepare commit protocol (EP), used in many commercial systems, is not suitable for use in multilevel secure distributed database systems that employ a locking protocol for concurrency control. This is because EP requires that read locks be not released by a subtransaction during its window of uncertainty; however, it is not possible for a locking protocol to provide this guarantee in a multilevel secure system (since read lock of a higher level transaction on a lower level data object must be released whenever a lower level transaction wants to write it). The Secure Early Prepare protocol (SEP) overcomes this difficulty by aborting those distributed transactions that release their low level read locks prematurely. We see this approach as being too restrictive. One of the major benefits of distributed processing is its robustness to failures, and SEP fails to take advantage of this. In this work, we propose the Advanced Secure Early Prepare commit protocol (ASEP) to...

With the evolution of the information superhighway, there is now an immense amount of information available in a wide variety of databases. Furthermore, users often have the ability to access legacy software packages developed by external sources. However, sometimes both the information provided by a data source, as well as one or more of the functions available through a software package may be sensitive-in such cases, organizations require that access by users be controlled. HERMES (HEterogeneous Reasoning and MEdiator System) is a platform that has been developed at the University of Maryland within which mediators may be designed and implemented. HERMES has already been used for a number of applications. In this paper, we provide a formal model of security in mediated systems. We then develop techniques that are sound and complete and respect security constraints of packages/databases participating in the mediated system. The security constraints described an this paper have been implemented, and we describe the existing implementation.

) Claudio Bettini Dept. of Computer Science (DSI) University of Milan via Comelico 39, 20135 Milan, Italy [email protected] X. Sean Wang, Sushil Jajodia Dept. of Info.& Software Systems Eng. George Mason University Fairfax, VA 22030, USA fxywang, [email protected] Abstract An important usage of time sequences is for discovering temporal patterns of events (a special type of data mining). This process usually starts with the specification by the user of an event structure which consists of a number of variables representing events and temporal constraints among these variables. The goal of the data mining is to find temporal patterns, i.e., instantiations of the variables in the structure, which frequently appear in the time sequence. This paper introduces event structures that have temporal constraints with multiple granularities (TCGs). Testing the consistency of such structures is shown to be NP-hard. An approximate algorithm is then presented. The paper also introduces ...

Ensuring atomicity is a major outstanding problem with present methods of handling multilevel transactions. The chief difficulty is that a high section of a transaction may be unable to complete due to violations of the integrity constraints, and a rollback of sections can be exploited to implement a covert channel. We define a notion of semantic atomicity which guarantees that either all or none of the sections of a transaction are present in any history. The notion of correct executions in our model is based on semantic correctness-that is, maintenance of integrity constraints-rather than serializability. We give a method whereby the application developer can statically analyze the set of transactions in the application and determine if the set ensures semantic atomicity and other desirable properties.

Although there are several choices of policies for protection of information, access control models have been developed for a fixed set pre-defined access control policies that are then built into the corresponding access control mechanisms. This becomes a problem, however, if the access control requirements of an application are different from the policies built into a mechanism. In most cases, the only solution is to enforce the requirements as part of the application code, but this makes verification, modification, and adequate enforcement of these policies impossible. In this paper, we propose a flexible authorization mechanism that can support different security policies. The mechanism enforces a general authorization model onto which multiple access control policies can be mapped. The model permits negative and positive authorizations, authorizations that must be strongly obeyed and authorizations that allow for exceptions, and enforces ownership together with delegation of administrative privileges.

Investigates issues related to transaction concurrency control in multilevel secure databases. This paper demonstrates how the conflicts between the correctness requirements and the secrecy requirements can be reconciled by proposing two different solutions. It first explores the correctness criteria that are weaker than one-copy serializability. Each of these weaker criteria, though not as strict as one-copy serializability, is required to preserve database consistency in some meaningful way, and moreover, its implementation does not require the scheduler to be trusted. It proposes three different, increasingly stricter notions of serializability (level-wise serializability, one-item read serializability and pair-wise serializability) that can serve as substitutes for one-copy serializability. The paper then investigates secure concurrency control protocols that generate one-copy serializable histories and presents a multiversion timestamping protocol that has several very desirable properties: it is secure, produces multiversion histories that are equivalent to serial one-copy histories in which transactions are placed in a timestamp order, eliminates starvation and can be implemented using single-level untrusted schedulers.

Digital libraries support quick and efficient access to a large number of information sources that are distributed but interlinked. As the amount of information to be shared grows, the need to restrict access only to specific users or for specific usage will surely arise. The protection of information in digital libraries, however, is difficult because of the peculiarity of the hypertext paradigm which is generally used to represent information in digital libraries, together with the fact that related data in a hypertext are often distributed at different sites. We present an authorization model for distributed hypertext systems. Our model supports authorizations at different granularity levels, takes into consideration different types of data and the relationships among them, and allows administrative privileges to be delegated.

The benefits of distributed systems and shared database resources are widely recognized, but they often cannot be exploited by users who must protect their data by using label-based access controls. In particular, users of label-based data need to read and write data at different security levels within a single database transaction, which is not currently possible without violating multilevel security constraints. The paper presents a formal model of multilevel transactions which provide this capability. We define four ACIS (atomicity, consistency, isolation, and security) correctness properties of multilevel transactions. While atomicity, consistency and isolation are mutually achievable in standard single-site and distributed transactions, we show that the security requirements of multilevel transactions conflict with some of these goals. This forces trade-offs to be made among the ACIS correctness properties, and we define appropriate partial correctness properties. Due to such trade-offs, an important problem is to design multilevel transaction execution protocols which achieve the greatest possible degree of correctness. These protocols must provide a variety of approaches to making trade-offs according to the differing priorities of various users. We present three transaction execution protocols which achieve a high degree of correctness. These protocols exemplify the correctness trade-offs proven in the paper, and offer realistic implementation options.

We consider communication structures for event ordering algorithms in distributed environments where information flows only in one direction. Example applications are multilevel security and hierarchically decomposed databases. Although the most general one directional communication structure is a partial order, partial orders do not enjoy the property of being consistently ordered, a formalization of the notion that local ordering decisions are ensured to be globally consistent. Our main result is that the crown free property is necessary and sufficient for a communication structure to be consistently ordered. We discuss the computational complexity of detecting crowns and sketch typical applications.

When querying a temporal database, a user often makes certain semantic assumptions on stored temporal data. This paper formalizes and studies two types of semantic assumptions: point-based and interval-baaed, The point-based assumptions include those assumptions that use interpolation methods, while the interval-based assumptions include those that involve different temporal types (time granularities). Each assumption is viewed as a way to derive certain implicit data from the explicit data stored in the database. The database system must use all explicit as well as (possibly infinite) implicit data to answer user queries. This paper introduces a new method to facilitate such query evaluations. A user query is translated into a system query such that the answer of this system query over the explicit data is the same as that of the user query over the explicit and the implicit data. The paper gives such a translation procedure and studies the properties (safety in particular) of user queries and system queries. 1

We offer a concurrency conirol algorithm for replicated, secure, multilevel databases. We compare the algorithm with a multiversion approach and with the typical full-replication approach. In the full-replication approach, each security level maintains a container that holds a complete copy of data at lower security levels. In the approach described here, access to data at lower security levels is through shared, read-only snapshots, where a constant number of snapshots at each level – two, as it turns out – is sufficient. We derive necessary properties for snapshots, give a switching algorithm to assign read-downs to snapshots, specify a snapshot creation algorithm, demonstrate that the approach is free of indirect channels and starvation, and prove one-copy serializability on execution histories. In contrast to some comparable algorithms, our algorithm is correct for any security structure that is a partial order.

The partitioned synchronization rule is a technique for proving the correctness of concurrency control algorithms. Prior work has shown the applicability of the partitioned synchronization rule to hierarchically decomposed databases whose structure is restricted to semitrees. The principal contribution of the paper is a demonstration that the partitioned synchronization rule also applies to more general structures than semitrees, specifically, to any planar extendible partial order, a partial order which when extended with a least and a greatest element still remains planar. To demonstrate utility, the paper presents two applications of the partitioned synchronization rule. The first application shows correctness of a component based timestamp generation algorithm suitable for implementing a timestamp ordering concurrency control algorithm. The second application shows correctness of a snapshot algorithm for concurrency control in a replicated multilevel secure database; we choose this application to highlight that hierarchically decomposed databases and multilevel secure databases are structurally similar. In both cases, the correctness proofs via the partitioned synchronization rule are substantially simpler than corresponding direct proofs.>

A common database need is to obtain a global-read, which is a consistent read of an entire database. To avoid terminating normal system activity, and thus improve availability, we propose an on-the-fly algorithm that reads database entities incrementally and allows normal transactions to proceed concurrently. The algorithm assigns each entity a color based on whether the entity has been globally read, and a shade based on how normal transactions have accessed the entity. Serializability of execution histories is ensured by requiring normal transactions to pass both a color test and a shade test before being allowed to commit. Our algorithm improves on a color-only-based scheme from the literature; the color-only scheme does not guarantee serializability.>

Multilevel secure (MLS) DBMSs are subject to a number of security-related architectural and functional factors that affect performance. These factors include, among others, the distribution of data among security levels, the session levels at which queries are run, and how the database is physically partitioned into files. In this paper, we present a benchmark methodology, a test database design, and a query suite designed to quantify this impact upon query processing. We introduce three metrics (uniformity, scale-up and speed-up) that characterize DBMS performance with varying data distributions. Finally, we provide comparisons and analysis of the results of a number of actual benchmarking experiments using DBMSs representative of the two major MLS DBMS architectures (trusted-subject and TCB-subset).>

We propose an efficient multiversion algorithm for servicing read requests in secure multilevel databases. Rather than keep an arbitrary number of versions of a datum, as standard multiversion algorithms do, the algorithm presented here maintains only a small fixed number of versions—up to three—for a modified datum. Each version corresponds to the state of the datum at the end of an externally defined version period. The algorithm avoids both covert channels and starvation of high transactions, and applies to security structures that are arbitrary partial orders. The algorithm also offers long-read transactions at any security level conflict-free access to a consistent, though slightly dated, view of any authorized portion of the database. We derive constraints sufficient to guarantee one-copy serializability of executions histories, and then exhibit an algorithm that satisfies these constraints.

We consider the propagation of authorizations in distributed database systems. If no constraints are imposed on the propagation of authorization changes, then the authorization states at different sites may evolve inconsistently. A standard solution is to suppress the distributed aspect and make all changes appear as if they had occurred in some serial order at a single site, perhaps via an atomic commit protocol. However, rigid insistence on consistency may result in authorization changes being needlessly delayed, a problem exacerbated in the context of site or communication failures. We propose an optimistic authorization propagation algorithm. We specify an authorization table and a set of operations for altering the authorization table. Each site maintains a log of authorization operations. We exploit the semantics of authorization operations to avoid relying on an undo-redo mechanism for processing out of order operations. Instead we give efficient, direct algorithms to scan the log and update the authorization table. Any inconsistencies in replicas of the authorization table are transient and are eliminated by further communication between sites. We discuss pruning the authorization log.

This paper addresses the problem of garbage collection in persistent object stores that are multilevel. The proposed approach is able to preserve referential integrity, while ensuring that security is not violated. we first discuss some general principles that should underlie any approach to garbage collection in secure environments. Then, we present a secure garbage collection algorithm, based on the copying approach.>

This paper proposes two major extensions to the authorization model for System R relational database management system. The first extension concerns the revoke operation. The revised model provides for a new type of revoke operation, called noncascading revoke, in addition to the System R cascading revoke operation. Unlike cascading revoke, noncascading revoke operation does not recursively remove privileges from users. The second extension concerns negative authorization. The details related to its application are specified in the paper.

Discretionary access control, based on checking access requests against users' authorizations, does not provide any way of restricting the usage of information once it has been “legally” accessed. This makes discretionary systems vulnerable to Trojan Horses maliciously leaking information. Therefore the need arises for providing additional controls limiting the indiscriminate flow of information in the system. This paper proposes a message filter complementing discretionary authorization control in object-oriented systems to limit the vulnerability of authorization systems to Trojan Horses. The encapsulation property of the object-oriented data model, which requires that access to objects be possible only through defined methods, makes information flow in such systems have a very concrete and natural embodiment in the form of messages and their replies. As a result, information information flow can be controlled by mediating the transmission of messages exchanged between objects. The message filter intercepts every message exchanged between objects to ensure that information is not leaked to objects accessible by users not allowed for it.

In a federated database environment, different constituents of the federation may use different temporal models or physical representations for temporal information. This paper introduces a new concept, called a temporal module, to resolve these differences, or mismatches, among the constituents. Intuitively, a temporal module hides the implementation details of a temporal relation by exposing its information only through two windowing functions: The first function associates each time point with a set of tuples and the second function links each tuple to a set of time points. A calculus-style language is given to form queries on temporal modules.

The concurrency control protocol that has been implemented in the commercially available Trusted Oracle multilevel secure database management system (DBMS) generates histories that are level-wise serializable. Level-wise serializability suffers from the inconsistent retrieval problems which may seriously harm database integrity. The authors show that it is possible to meet stricter correctness criteria using Trusted Oracle, provided knowledge of the update transactions that will be executed in the system is available. They perform a static analysis of the read- and write-sets of these transactions and, based on this analysis, control the order of submission of the transactions to the scheduler in such a way that the resultant history ensures higher correctness level. The exact order chosen depends on the level of consistency desired. The goal is achieved without modifying the Trusted Oracle concurrency control algorithm in any way.>

Data management applications that use multilevel database management system (DBMS) capabilities have the requirement to read and write objects at multiple levels within the bounds of a multilevel transaction. The authors define a new notion of atomicity that is meaningful within the constraints of the multilevel environment. They offer a model of multilevel atomicity that defines varying degrees of atomicity and recognizes that lower security level operations within a transaction must be able to commit or abort independently of higher security level operations. Execution graphs are provided as a tool for analyzing atomicity requirements in conjunction with internal semantic interdependencies among the operations of a transaction and rules for determining the greatest degree of atomicity are proved that can be attained for a given multilevel transaction. Several alternative transaction management algorithms that can be used to preserve multilevel atomicity are presented.>

Although high assurance multilevel secure database management systems (DBMSs) are slowly becoming commercially available, these systems have yet to offer a concurrency control protocol that is free of signaling channels and produces serializable (one-copy serializable when multiple versions of data are maintained) histories. In this paper, we consider the multiversion con currency control algorithm that has been implemented in the Trusted Oracle DBMS. It guarantees levelwise serializability, which is a weaker notion of correctness than one-copy serializability. While level wise serializability has many desirable properties, it suffers from the inconsistent retrieval problems that may seriously harm database integrity. In this paper, we demonstrate how pair wise serializability and one-copy serializability, stricter correctness criteria than levelwise serializability, can be achieved, using the Trusted Oracle scheduler. It is important to note that rather than taking the usual approach of modifying the underlying con currency control protocol such that it meets the stricter correctness requirements, we achieve our goal without modifying the Trusted Oracle con currency control algorithm in any way. In other words, in this paper, we do not propose a new scheduler for con currency control, but propose algorithms, if used with the Trusted Oracle scheduler, to generate pair wise or one-copy serializable histories. Our approach is based on the assumption that all transactions that are running during a certain interval are known in advance. We perform a static analysis of the read- and write-sets of these transactions to recognize conflicts among transactions. The results of the analysis are used to control the order of submission of the transactions in such a way that stricter correctness requirements are met. All the algorithms proposed in this paper are implementable with untrusted code.

Timestamps are considered for distributed environments in which information flow is restricted to one direction through a planar lattice imposed on a network. For applications in such networks, existing timestamping algorithms require extension and modification. For example, in secure environments, typical timestamps provide a potential signaling channel between incomparable levels. In hierarchical databases, typical timestamps cause peripheral sites to unnecessarily affect the behavior at main sites. Algorithms are presented by which a network node may generate and compare timestamps using timestamp components maintained at dominated nodes in the network. The comparison relation is shown to be acyclic for timestamps produced by the generation algorithm. We discuss ways to safely relax the requirement that the network be a lattice. By example, we show how to modify a simple nonplanar lattice so that the generation algorithm can be applied. Uses of the timestamp generation algorithm in the motivating applications are outlined.

We present two distributed algorithms for dynamic replication of a data-item in communication networks. The algorithms are adaptive in the sense that they change the replication scheme of the item (i.e. the set of processors at which the data-item is replicated), as the read-write pattern of the processors in the network changes. Each algorithm continuously moves the replication scheme towards an optimal one, where optimality is defined with respect to different objective functions. One algorithm optimizes the communication cost objective function, and the other optimizes the communication time. We also provide a lower bound on the performance of any dynamic replication algorithm.

A concurrency control algorithm for replicated, secure, multilevel databases is presented. Multiversion and replicated databases can avoid starvation problems without introducing indirect channels by maintaining stable copies of old low-level data values for use by high-level transactions. The algorithm presented improves on two comparable techniques, a direct multiversion approach of T. F. Keefe and W. T. Tsai and the full replication scheme of S. Jajodia and B. Kogan (both in Proc. 1990 IEEE Symp. on Res. In Security & Privacy, May 1990). In the latter, each security level has a container that holds a copy of all lower-level data. It is shown that only a constant number of old copies (two, as it turns out) must be maintained. The correctness of the algorithm is argued, and it is demonstrated that the algorithm is free of indirect channels and starvation.>

Two different areas related to the concurrency control in multilevel secure, multiversion databases are considered. First, the issue of correctness criteria that are weaker than one-copy serializability are explored. The requirements for a weaker correctness criterion are that it should preserve database consistency in some meaningful way, and moreover, it should be implementable in a way that does not require the scheduler to be trusted. Three different, increasingly stricter notions of serializability that can serve as substitutes for one-copy serializability are proposed. Second, a multiversion timestamping protocol is presented that has several very desirable properties: it is secure, produces multiversion histories that are equivalent to one-serial histories in which transactions are placed in a timestamp order, avoids livelocks, and can be implemented using single-level untrusted schedulers.>

Auditing capability is one of the requirements for secure databases. A secure database management system, among other things, has to provide not only facilities for recording the history of all updates and queries against the database but high-level support for querying this history as well. The authors present an audit model for object-oriented databases that satisfies both requirements. The model offers several additional advantages: (1) it imposes a uniform logical structure upon both the current and the audit data: (2) it results in zero-information loss, i.e. there is never any loss of historical or current information in this model; and (3) since it captures the entire database activity, a complete reconstruction of every action taken on the database is possible. They show how this third aspect can be exploited to provide high-level support for expressing audit and other database queries and therefore, they make a complete audit trail methodology available.>

The replicated architecture for multilevel secure database systems provides security by replicating data into separate untrusted single-level database systems. To be successful, a system using the replicated architecture must have a concurrency and replica control algorithm that does not introduce any covert channels. Jajodia and Kogan (1990) have developed one such algorithm that uses update projections and a write-all replica control algorithm. The authors describe an alternative algorithm. The new algorithm uses replicated transactions and a set of queues organized according to security class. A new definition of correctness is required for this approach, so they present one and use it to show that the algorithm is correct. The existence of this new algorithm increases the viability of the replicated architecture as an alternative to kernelized approaches.>

The authors present a secure kernelized architecture for multilevel object-oriented database management systems. The architecture is based on the notion of a message filter. It builds upon the typical architecture of current object-oriented database management systems. Since the operations mediated by the message filter are arbitrarily complex operations (as opposed to primitive reads and writes), a secure message filter requires careful attention to potential timing covert channels. Although the overall computation is logically a sequential one, to be secure one must actually execute pieces of the computation concurrently. This raises a synchronization problem for which they give a secure multiversion protocol. The fundamental problem solved is how to securely and correctly 'write up' in terms of abstract operations.>

Although there are several efforts underway to build multilevel secure relational database management systems, there is no clear consensus regarding what a multilevel secure relational data model exactly is. In part this lack of consensus on fundamental issues reflects the subtleties involved in extending the classical (single-level) relational model to a multilevel environment. Our aim in this paper is to discuss the most fundamental aspects of the multilevel secure relational model. Specifically, we consider two requirements: entity integrity and update semantics. Our overall goal is to preserve as much as possible the simplicity and flexibility of the relational model without sacrificing security in the process. 1 INTRODUCTION A large number of databases in the Department of Defense, the intelligence community and civilian government agencies contain data that are classified to have different security levels. All database users are also assigned security clearances. It is the respo...

Presents a novel decomposition algorithm that breaks a multilevel relation into single-level relations and a novel recovery algorithm which reconstructs the original multilevel relation from the decomposed single-level relations. There are several novel aspects to these decomposition and recovery algorithms which provide substantial advantages over previous proposals. The algorithms are formulated in the context of an operational semantics for multilevel relations, defined here by generalizing the usual update operations of structured query language (SQL) to multilevel relations. The algorithms, with minor modifications, can easily accommodate alternative update semantics which have been proposed in the literature. The algorithms are efficient because recovery is based solely on union-like operations without any use of joins. The decomposition is intuitively and theoretically simple, giving a sound basis for correctness.>

The paper by Ahad et al. [1] derives an analytical expression to estimate the cardinality of the projection of a database relation. In this note, we propose to show that this expression is in error even when all the parameters are assumed to be constant. We derive the correct formula for this expression.

A formal operational semantics is given for update operations on multilevel relations, i.e., relations in which individual data elements are classified at different levels. For this purpose, the familiar INSERT, UPDATE and DELETE operations of SQL are suitably generalized to cope with polyinstantiation. The authors conjecture that these operations are consistent (or sound) in that all relations which can be constructed will satisfy the basic integrity properties required of multilevel relations. They also conjecture that the operations are complete in that every multilevel relation can be constructed by some sequence of these operations.>

Multilevel relations in which security classifications are assigned at the granularity of individual data elements are considered. Usually these multilevel relations exist only at the logical level. In reality, a multilevel relation is decomposed into a collection of single level base relations which are then physically stored in a database, and a recovery algorithm is used to reconstruct the original multilevel relation. The authors formalize the relationship that exists between the decomposition-independent filtered relations and the multilevel relations obtained from decomposed single level relations using the recovery algorithm. Three requirements that must be met by any decomposition and recovery algorithms are stated. It is pointed out that previous algorithms given by the authors (1990) meet these requirements.>

A new polyinstantiation integrity constraint for multilevel relations based on the intuitive idea that every entity in a relation can have at most one tuple for every access class is proposed. The consequences of this property and some of its variations are discussed. A core set of properties which should apply to all relations is identified. These are entity integrity, interinstance integrity, subsumption integrity, and polyinstantiation integrity in the sense of PI-FD. Specific models impose additional polyinstantiation constraints. Oakland requires PI-null, Sea View requires PI-MVD, and the new Franconia model requires PI-Tuple-class. Each of these properties appears likely to arise often enough in practice to justify DBMS (database management system) support for its enforcement on a relation-by-relation basis.>

In a multilevel secure database management system based on the replicated architecture, there is a separate database management system to manage data at or below each security level, and lower level data are replicated in all databases containing higher level data. In this paper, we address the open issue of concurrency control in such a system. We give a secure protocol that guarantees one-copy serializability of concurrent transaction executions and can be implemented in such a way that the size of the trusted code (including the code required for concurrency and recovery) is small.

A security model is presented for object-oriented database systems. This model is a departure from the traditional security models based on the passive-object active-subject paradigm. The model is a flow model whose main elements are objects and messages. An object combines the properties of a passive information repository with those of an active agent. Messages are the main instrument of information flow. The chief advantages of the proposed model are its compatibility with the object-oriented data model and the simplicity with which security policies can be stated and enforced.>

In a multilevel secure database management system based on the replicated architecture, there is a separate database management system to manage data at or below each security level, and lower-level data are replicated in all databases containing higher-level data. The issue of transaction processing in such a system is addressed. A synchronization protocol is given that guarantees one-copy serializability of concurrent transaction executions. It is secure since the information always flows in one direction-from databases at lower security classes to databases with higher security classes-and it can be implemented in such a way that the size of the trusted code (including the code required for concurrency and recovery) is small.>

Polyinstantiation integrity (PI) as defined in the Sea View multilevel relational data model consists of a functional dependency component and a multivalued dependency component. It is shown that the latter component rules out many practically useful relations and is therefore unduly restrictive. This leads the authors to propose that PI be defined to consist only of the functional dependency component. For this revised definition of PI, they formulate and prove correct a lossless decomposition of multilevel relations into single-level ones with recovery based on the natural join operation.>

There are several replica control algorithms for managing replicated files in the face of network partitioning due to site or communication link failures. Pessimistic algorithms ensure consistency at the price of reduced availability; they permit at most one (distinguished) partition to process updates at any given time. The best known pessimistic algorithm, voting , is a “static” algorithm, meaning that all potential distinguished partitions can be listed in advance. We present a dynamic extension of voting called dynamic voting . This algorithm permits updates in a partition provided it contains more than half of the up-to-date copies of the replicated file. We also present an extension of dynamic voting called dynamic voting with linearly ordered copies (abbreviated as dynamic-linear ). These algorithms are dynamic because the order in which past distinguished partitions were created plays a role in the selection of the next distinguished partition. Our algorithms have all the virtues of ordinary voting, including its simplicity, and provide improved availability as well. We provide two stochastic models to support the latter claim. In the first (site) model, sites may fail but communication links are infallible; in the second (link) model the reverse is true. We prove that under the site model, dynamic-linear has greater availability than any static algorithm, including weighted voting, if there are four or more sites in the network. In the link model, we consider all biconnected five-site networks and a wide variety of failure and repair rates. In all cases considered, dynamic-linear had greater availability than any static algorithm.

A hybrid scheme that integrates the static voting protocol and dynamic voting with linearly ordered copies is proposed. A stochastic model is used to compare the file availability afforded by the proposed hybrid scheme with the availabilities of voting, dynamic voting, and dynamic voting with linearly ordered copies. The hybrid scheme has the most availability of these four algorithms for all reasonable repair/failure ratios tested.>

A consistency control algorithm is described for managing replicated files in the face of network partitioning due to node or communication link failures. It adopts a pessimistic approach in that mutual consistency among copies of a file is maintained by permitting files to be accessed only in a single partition at any given time. The algorithm simplifies the Davcev-Burkhard dynamic voting algorithm (1985) and also improves its availability by adding the notion of linearly ordered copies. A proof that any pessimistic algorithm with fresh reads is one-copy serializable is given.>

A hybrid scheme is proposed that integrates the static voting protocol and dynamic voting with linearly ordered copies. A stochastic model is used to compare the file availability afforded by the proposed hybrid scheme against the availabilities of voting, dynamic voting, and dynamic voting with linearly ordered copies. The analysis provides evidence for the conjecture that the hybrid scheme is the optimal algorithm in the context of the stochastic model.>

In this paper, we describe a consistency control algorithm for managing replicated files in the face of network partitioning due to node or communication link failures. It adopts a conservative approach in that mutual consistency among copies of a file is maintained by permitting files to be accessed only in a single partition. Our algorithm has the property that it permits dynamic switching between the “dynamic voting” algorithm and the “linearly ordered copies” algorithm. This aspect is not only appealing but results in greater file availability than in all previously published conservative algorithms.

In this paper we set forth a simple and efficient algorithm for managing replicated data in a decentralized distributed system, which allows for inserts, deletes, updates, and synonyms and which achieves a high degree of availability in the face of node or communication failures. We focus on the approach developed recently by Fischer and Michael and exploit the knowledge of the semantics of the database operations.

In a voting-based algorithm, a replicated file can be updated in a partition if it contains a majority of copies. In this paper, we propose an extension of this scheme which permits a file to be updated in a partition provided it contains a majority of up-to-date copies. Our scheme not only preserves mutual consistency of the replicated file, but provides improvement in its availability as well. We develop a stochastic model which gives insight into the improvements afforded by our scheme over the voting scheme.

Let R be a γ-acyclic relational scheme, and let F be the set of functional dependencies (FD's) embodied in R. Given an existence constrained database r over R, it was shown in [1] that it is possible to connect tuples from different relations in r and construct a universal instance L, possibly containing null values δ, such that the total projection of L onto R yields exactly the set r. Moreover, conditions were given which guarantee that this L would satisfy the functional dependency with nulls (NFD) counterparts of FD's, in F. The purpose of this note is to generalize the latter result and show that under the same conditions, L actually satisfies NFD counterparts of FD's in the closure F+ of F.

In this paper, we give a polynomial-time method to construct effectively the unique universal instance, using as few nulls as possible, from any loop-free network database, via a "minimal information" extension of natural join. Our results can be seen as concretely and quickly implementing the universal relation view for databases which are not pairwise consistent.

In this paper, we present a review of the issues that affect the software requirements for a local area network. We introduce protocols for the local area networks and characterize their software needs. Two approaches to operating systems are outlined and examples of each approach are presented. Various applications which use local area networks and performance issues are also discussed.

In the relation model of data, dependencies are used to decompose the initial relation schemas into smaller components. Whereas it is relatively easy to obtain an accurate set of functional dependencies (FDs), it is difficult to determine a correct set of multivalued dependencies (MVDs). MVDs depend on the context in which they are defined and thus are very hard to visualize. The purpose of this note is to give some results which may provide some insight regarding the existence of possible MVDs in the relation schemas provided all their FDs are known in advance.

In this paper, we study under what conditions will a pairwise inconsistent relational database ≪R,r≫ have a universal/representative instance L. If R is γ-acyclic and r satisfies all existence constraints, then it is possible to construct a universal instance L, using unmarked nulls, whose total projections onto R yield exactly the relations in r. We show that L would actually be a representative instance under a set of functional dependencies if R satisfies the additional mild condition: for any functional dependency X → A where A is a single attribute, whenever XA is contained in two relation schemes R and R' of R, it follows that R ∩R' is a relation scheme of R, having X as one of its keys.

This paper presents a recognition procedure for parallel tasks in the user program written in a conventional programming language. To establish our program model, it describes the parallelism of the program in tenns of a process flow graph in which the relationships among processes are of predecessors and successors. And finally it presents a parallel processing scheme which realizes automatically the recognition of parallel tasks and schedules these tasks for parallel execution.

We investigate the question of when two entity-relationship diagrams (ERD's) should be considered equivalent, in the sense of representing the same information. This question is very important for a database design process which uses the ERD model, and can be interpreted in various ways. We give three natural and increasingly stricter criteria for developing concepts of equivalence for ERD's. We first give a notion of "domain data compatibility" which ensures that the ERD's in question represent the same universe of data in an aggregate sense. Then we define the set of functional dependencies which are naturally embedded in each ERD, and use it to develop a concept of "data dependency equivalence" which ensures that the ERD's satisfy the same constraints (functional dependencies) among the represented data. Finally, we give our strongest criterion, instance data equivalence, which requires the ERD's to have the same power to represent instances of data. We develop several alternate forms of this third notion, including some giving efficient tableaux tests for its occurrence. Indeed, for each type of equivalence, we give a polynomial-time algorithm to test for it.