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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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 ...

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.

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

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.>

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.

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.

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...

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.

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.

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 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.