Policy engineering pertains to devising access control policies. This can be performed either in a top-down or a bottom-up manner. The bottom-up approach, also referred to as policy mining, is to (automatically) discover security policies from the existing authorizations. Several researchers have proposed approaches for RBAC and ABAC policy mining. In contrast, the top-down approach relies on a careful analysis of the business processes of an organization to devise the appropriate security policies. Each approach has its own advantages and disadvantages. For example, the bottom-up approach lends itself to automation, but may result in erroneous policies as it relies on existing authorizations, which may not always be correct to begin with. On the other hand, although the top-down approach may result in more accurate policies, it is often manual, tedious and time consuming since it requires that the semantics of the business processes be well understood. Sometimes it may be more pragmatic to employ a hybrid approach to reap the benefits of both.

Natural Language Access Control Policies (NLACPs) define who can access specific information within an organization and under what conditions. While these policies are typically written in semi-formal or informal natural language, making them easily interpretable by humans, they cannot be directly enforced by access control systems. Their unstructured nature introduces ambiguities and inconsistencies, making automated extraction and translation into structured, machine-enforceable security rules a significant challenge.

A policy comprised of a set of rules forms the backbone of Attribute-based Access Control (ABAC) systems. Every incoming request is checked against such a policy and if at least one rule grants the access, it is allowed. Else, access is denied. The initial ABAC policy could be hand crafted by the security administrator or mined from a given set of authorizations using a policy engineering technique. In dynamic ABAC systems, over a period of time, additional authorizations may have to be granted or some removed as per situational changes. These changes are maintained in an auxiliary list. For access resolution, both the policy as well as the auxiliary list are considered before taking a decision. Since such a list can grow indefinitely and checking it adversely affects access resolution efficiency, periodic policy rebuilding must be done by combining the existing policy and the auxiliary list. However, regenerating the ABAC policy requires re-running computationally expensive policy mining algorithms. Further, access mediation has to be put on hold while this step is being carried out, resulting in periods of unavailability of the system. In this paper, we study the intricate problem of balancing access request resolution, accommodating dynamic authorization updates, and ABAC policy rebuilding. We employ a queuing theoretic approach where the access mediation process is modeled as an M/G/1 queue with vacation or limited service. While the server is primarily involved in resolving access requests, it occasionally goes on vacation to rebuild the ABAC policy. We study the effect of queue discipline on several performance parameters like request arrival rate, access resolution time, vacation duration and interval between vacations. Results of an extensive set of experiments provide a direction towards efficient implementation of dynamic ABAC systems.

Attribute-Based Access Control (ABAC) is increasingly becoming popular due to its dynamic, flexible, portable, and scalable nature. Under ABAC, security policies (ABAC rules) are stated in terms of the attributes of the subject, the object and the environment. A subject is granted access to an object if their respective attribute values are satisfied against a set of ABAC rules. Typically hierarchical relationships exist among the subjects as well as the objects, where more specific subjects (objects) inherit the attributes from the general ones. As such, if a subject is allowed access to a general object, that subject is allowed to access all of its sub-types. This has been the general understanding and current ABAC enforcement and policy mining approaches follow this approach. However, in this article, we argue that the general understanding of the semantics of the ABAC is not always appropriate. Indeed, under certain semantics, the specific data may be more sensitive than that of its general counterpart. In that situation, if a subject is allowed access to a general type, it should not be allowed access to its sub-type, which is contrary to the current understanding and implementation. This paper is the first attempt in the literature to distinguish these two different ABAC semantics arising from the different semantics of object attributes themselves. We present concrete examples of these two semantics and demonstrate what can go wrong - both anecdotally as well as empirically - if one ignores the underlying semantics and inappropriately uses the existing enforcement and mining algorithms. We then present how existing algorithms can be modified so that no misconfigurations arise and security is ensured.

Linux is a widely used multi-user operating system with applications ranging from personal desktop to commercial heavy duty web servers. It has built-in security features based on discretionary access control enforced in the form of access control lists, which can be enhanced using the Linux Security Module (LSM) Framework. LSM allows inserting security verification hooks for supporting custom security policies. However, there is no support yet for Attribute-Based Access Control (ABAC) - an access control model gaining popularity due to its dynamic nature and flexibility. In ABAC, access is granted or denied based on attributes of the subject, object and environment. In this work, we propose a method for enhancing Linux's security features by integrating ABAC for file system objects using the LSM framework. We look at various kernel and user space components and how they can be made to work together to enforce ABAC policies. Different algorithms and data structures for efficient access request resolution are also investigated. Finally, we carry out extensive performance evaluation of the ABAC-enabled Linux system and discuss its results.

Our vision is to achieve societally responsible secure and trustworthy cyberspace that puts algorithmic and technological checks and balances on the indiscriminate sharing and analysis of data. We achieve this vision in a holistic manner by framing research directions with four major considerations: (i) Expanding knowledge and understanding of security and privacy perceptions and expectations in vulnerable groups, which significantly contribute to their unwillingness to share data, and use that knowledge to drive research in (a) mitigating missing/imbalanced data problems, (b) understanding and modeling security and privacy risks of data sharing, and (c) modeling utility of data sharing. (ii) Developing a risk-adaptive, policy model capable of capturing and articulating security and privacy expectations of users that are relevant in a particular context and develops associated technology to ensure provenance and accountability. (iii) Developing robust AI/ML algorithms that are transparent and explainable with respect to fairness and bias to reduce/eliminate discrimination, misuse, privacy violations, or other cyber-crimes. (iv) Developing models and techniques for a nuanced, contextually adaptive, and graded privacy paradigm that allows trade-offs between privacy and utility. Towards this, in this paper we present the SAFE-PASS framework to provide Stewardship, Advocacy, Fairness and Empowerment in Privacy, Accountability, Security, and Safety for Vulnerable Groups.

Linux has built-in security features based on discretionary access control that can be enhanced using the Linux Security Module (LSM) framework. However, so far there has been no reported work on strengthening Linux with Attribute-Based Access Control (ABAC), which is gaining in popularity in recent years due to its flexibility and dynamic nature. In this paper, a method for enabling ABAC for Linux file system objects using LSM is proposed. We report initial experimental results and also share our public repository links for integrating ABAC in any Linux installation.

Access control policies are dynamic in nature, and therefore require frequent updates to synchronize with the latest organizational security requirements. As these updates are handled, it is important that all user access requests be answered contemporaneously and correctly without any interruption or delay. In this paper, considering the context of Attribute Based Access Control (ABAC), we propose an approach that is capable of immediately materializing any update to the policy and ensuring that it is taken into account for any subsequent access requests. One possibility is to update the policy based on the incoming changes through ABAC policy mining techniques. However, it turns out that no existing mining approach can offer correct enforcement of policies when access requests are entertained during the updates. We provide a formal proof for this surprising result and then propose an approach called δwOP that does not suffer from this problem. Essentially, δwOP keeps track of the needed information from updates and uses this in conjunction with the existing ABAC policy rules to make access decisions. We present the complexity analysis as well as a comprehensive experimental evaluation to demonstrate the efficacy of the proposed approach for different types of changes.

Discovery of Attribute Based Access Control policies through mining has been studied extensively in the literature. However, current solutions assume that the rules are to be mined from a static data set of access permissions and that this process only needs to be done once. However, in real life, access policies are dynamic in nature and may change based on the situation. Simply utilizing the current approaches would necessitate that the mining algorithm be re-executed for every update in the permissions or user/object attributes, which would be significantly inefficient. In this paper, we propose to incrementally maintain ABAC policies by only updating the rules that may be affected due to any change in the underlying access permissions or attributes. A comprehensive experimental evaluation demonstrates that the proposed incremental approach is significantly more efficient than the conventional ABAC mining.

NoSQL databases are gaining popularity in recent times for their ability to manage high volumes of unstructured data efficiently. This necessitates such databases to have strict data security mechanisms. Attribute-Based Access Control (ABAC) has been widely appreciated for its high flexibility and dynamic nature. We present an approach for integrating ABAC into NoSQL databases, specifically MongoDB, that typically only support Role-Based Access Control (RBAC). We also discuss an implementation and performance results for ABAC in MongoDB, while emphasizing that it can be extended to other NoSQL databases as well.

In recent years, Attribute-Based Access Control (ABAC) has emerged as the desired access control model in scenarios involving sharing of resources across multiple domains. This necessitates organizations using traditional access control models to use ABAC. However, ab initio deployment of ABAC is both cost and time intensive. In this paper, we present ABACaaS - a cloud service that enables any organization to integrate ABAC into their own environment irrespective of the platform they operate in. We show both SaaS as well as PaaS instances of ABACaaS along with results on its performance.

In Attribute-Based Access Control (ABAC), a user is permitted or denied access to an object based on a set of rules (together called an ABAC Policy) specified in terms of the values of attributes of various types of entities, namely, user, object and environment. Efficient evaluation of these rules is therefore essential for ensuring decision making at on-line speed when an access request comes. Sequentially evaluating all the rules in a policy is inherently time consuming and does not scale with the size of the ABAC system or the frequency of access requests. This problem, which is quite pertinent for practical deployment of ABAC, surprisingly has not so far been addressed in the literature. In this paper, we introduce two variants of a tree data structure for representing ABAC policies, which we name as PolTree. In the binary version (B-PolTree), at each node, a decision is taken based on whether a particular attribute-value pair is satisfied or not. The n-ary version (N-PolTree), on the other hand, grows as many branches out of a given node as the total number of possible values for the attribute being checked at that node. An extensive experimental evaluation with diverse data sets shows the scalability and effectiveness of the proposed approach.

In the present‐day computing environment, where access control decisions are often dependent on contextual information like the location of the requesting user and the time of access request, attribute‐based access control (ABAC) has emerged as a suitable choice for expressing security policies. In an ABAC system, access decisions depend on the set of attribute values associated with the subjects, resources, and the environment in which an access request is made. In such systems, the task of managing the set of attributes associated with the entities as well as that of analysing and understanding the security implications of each attribute assignment is of paramount importance. Here, the authors first introduce a comprehensive attribute‐based administrative model, named as AMABAC ( A dministrative M odel for ABAC ), for ABAC systems and then suggest a methodology for analysing the security properties of ABAC in the presence of the administrative model. For performing analysis, the authors use μZ , a satisfiability modulo theories‐based model checking tool. The authors study the impact of the various components of ABAC and AMABAC on the time taken for security analysis.

The flexibility, portability and identity-less access control features of Attribute Based Access Control(ABAC) make it an attractive choice to be employed in many application domains. However, commercially viable methods for implementation of ABAC do not exist while a vast majority of organizations use Role Based Access Control (RBAC) or their temporal extensions, such as Temporal Role Based Access Control (TRBAC). In this paper, we present a solution for organizations having a RBAC/TRBAC that can deploy an ABAC policy. Essentially, we propose a method for the translation of an ABAC policy (including time constraints) into a form that can be adopted by an RBAC/TRBAC system. We experimentally demonstrate that time taken to evaluate an access request in RBAC and TRBAC systems is significantly less than that of the corresponding ABAC system. Since the cost of security management is more expensive under RBAC when compared to ABAC, we present an analysis of the different management costs and present mitigation approaches by considering various administrative operations.

In Attribute-Based Access Control (ABAC), access to resources is given based on the attributes of subjects, objects, and environment. There is an imminent need for the development of efficient algorithms that enable migration to ABAC. However, existing policy mining approaches do not consider possible adaptation to the policy of a similar organization. In this article, we address the problem of automatically determining an optimal assignment of attribute values to subjects for enabling the desired accesses to be granted while minimizing the number of ABAC rules used by each subject or other appropriate metrics. We show the problem to be NP-Complete and propose a heuristic solution.

In Attribute-based Access Control (ABAC) systems, utilizing environment attributes along with the subject and object attributes introduces a dynamic nature to the access decisions. The inclusion of environment attributes helps in achieving a more fine-grained access control. In this paper, we present an ABAC policy mining algorithm that considers the environment attributes and their associated values while forming the rules. Furthermore, we use gini impurity to form the rules. This helps to minimize the number of rules in the generated policy. The experimental evaluation shows that our approach is quite effective in practice.

In recent years, concerns are increasingly being expressed about the threats of side-channel attacks that exploit acoustic emanations from electronic as well as mechanical devices of daily use. With the increased level of sophistication in both hardware and applications that run on mobile phones, the number of possible ways in which their vulnerabilities can be exploited is also on the rise. In this article, we demonstrate a novel attack which uses the sound emanating from a tap made on the touchscreen of a smartphone to decipher the text being typed. The audio signal captured by the pair of microphones typically embedded in a smartphone is first processed to determine a candidate set of keys. Filters are employed to make this step robust against ambient noise. Natural language processing techniques are then used to estimate the most probable words and sentences that can be constructed from a sequence of taps. It is shown that using even off-the-shelf tools, the typed text including passwords can be guessed with reasonably high accuracy. Besides raising awareness about this potential side-channel attack, we identify the causes that allow it to succeed and suggest countermeasures.

CAPTCHAs are reverse Turing tests that aim to distinguish between human and non-human online participants. CAPTCHAs enable site administrators to determine if a particular user is a legitimate human or a bot, and grant or deny them access to resources accordingly, thus preventing abuse of resources. However, given the incentive to break or circumvent CAPTCHAs, they must also evolve alongside advances in machine learning tools and techniques to continue providing security for online services. In this paper, we present the essential design criteria for building robust CAPTCHAs and thus provide a general framework for evaluating a specific CAPTCHA design. We then develop several new CAPTCHA exemplars, and analyze them from this perspective to show how design decisions impact different evaluation parameters. We also provide an overview of a new security method that can be applied to any image CAPTCHA and present the results of the evaluation of one of the most promising image based CAPTCHAs with a comprehensive user study.

Constraints form an important aspect of any access control system and are often regarded as one of the principle motivations behind developing different access control models. The two primary concerns related to a constraint are its specification and enforcement. Among the various types of constraints, enforcement of the Separation of Duty (SoD) constraint is considered to be the most important in commercial applications. In this paper, we introduce the problem of SoD specification, verification, and enforcement in attribute-based access control (ABAC) systems. We then demonstrate the effect of modifications in the different components of ABAC on enforcement. We also analyze the complexity of the enforcement problem and provide a methodology for solving it. Experiments on a wide range of data sets show encouraging results.

In practical access control systems, it is important to enforce an upper bound on the time taken to respond to an access request. This response time is directly influenced by the size (often called the weight) of each of the underlying access control rules. We present a constrained policy mining algorithm which takes an access control matrix as input and generates a set of attribute based access control (ABAC) rules, such that the weight of each rule is not more than a specified value and the sum of weights of all the rules is minimized. Our initial experiments show encouraging results.

The last two decades have witnessed an emergence of role‐based access control (RBAC) as the de facto standard for access control. However, for organisations already having a deployed RBAC system, in many cases it may become necessary to associate a temporal dimension with the existing access control policies due to changing organisational requirements. In such cases, migration from RBAC to a temporal extension of RBAC becomes essential. Temporal RBAC (TRBAC) is one such RBAC extension. The process of creating a set of roles for implementing a TRBAC system is known as temporal role mining . Existing temporal role mining approaches typically assume that TRBAC is being deployed from scratch and do not consider it as a migration from an existing RBAC policy. In this study, the authors propose two temporal role mining approaches that enable migration from RBAC to TRBAC. These approaches make use of conventional (non‐temporal) role mining algorithms. Apart from aiding the migration process, deriving the roles in this manner allows the flexibility of minimising any desired role mining metric. They experimentally evaluate the performance of both of the proposed approaches and show that they are both efficient and effective.

With ever increasing volume of video data, ensuring effective access control to video content has become one of the most important and pressing problems in the domain of information security. The traditional access control mechanisms are inadequate due to the complex nature of video access control where the requirements are not only to restrict access to videos based on their IDs, but also ensuring security of content within the videos (e.g., people, objects and events). For example, even if two users have access to the same video, they might not have access to the same objects or sequence of frames.

As online automation, image processing and computer vision become increasingly powerful and sophisticated, methods to secure online assets from automated attacks (bots) are required. As traditional text based CAPTCHAs become more vulnerable to attacks, new methods for ensuring a user is human must be devised. To provide a solution to this problem, we aim to reduce some of the security shortcomings in an alternative style of CAPTCHA - more specifically, the image CAPTCHA. Introducing noise helps image CAPTCHAs thwart attacks from Reverse Image Search (RIS) engines and Computer Vision (CV) attacks while still retaining enough usability to allow humans to pass challenges. We present a secure image generation method based on noise addition that can be used for image CAPTCHAs, along with 4 different styles of image CAPTCHAs to demonstrate a fully functional image CAPTCHA challenge system.

Statistical database auditing is the process of checking aggregate queries that are submitted in a continuous manner, to prevent inference disclosure. Compared to other data protection mechanisms, auditing has the features of flexibility and maximum information. Auditing is typically accomplished by examining responses to past queries to determine whether a new query can be answered. It has been recognized that query denials release information and can cause data disclosure. This paper proposes an auditing mechanism that is free of query denial threat and applicable to mixed types of aggregate queries, including sum, max, min, deviation, etc. The core ideas are (i) deriving the complete information leakage from each query denial and (ii) carrying the complete leaked information derived from past answered and denied queries to audit each new query. The information leakage deriving problem can be formulated as a set of parametric optimization programs, and the whole auditing process can be modeled as a series of convex optimization problems.

Role mining, the process of deriving a set of roles from the available user-permission assignments, is considered to be an essential step in successful implementation of Role-Based Access Control (RBAC) systems. Traditional role mining techniques, however, are not equipped to handle temporal extensions of RBAC like the Temporal-RBAC (TRBAC) model. In this paper, we formally define the problem of finding a minimal set of roles from temporal user-permission assignments, such that in the resulting TRBAC system, users acquire either the same or a subset of the permissions originally assigned to them for the complete or partial durations of time as specified in the input. We show that the problem is NP-complete and propose a greedy algorithm for solving it. Our algorithm first derives a set of candidate roles from the temporal user-permission assignments and then selects the least possible number of roles from the candidate role set. The final output consists of a set of roles, a user-to-role assignment relation, a role-to-permission assignment relation and a role enabling base describing the time durations for which each role is enabled. Performance of the proposed approach has been evaluated on a number of synthetic as well as real-world datasets.

Role mining is a critical step for organizations that migrate from traditional access control mechanisms to role based access control (RBAC). Additional constraints may be imposed while generating roles from a given user-permission assignment relation. In this paper we consider two such constraints which are the dual of each other. A role-usage cardinality constraint limits the maximum number of roles any user can have. Its dual, the permission-distribution cardinality constraint, limits the maximum number of roles to which a permission can belong. These two constraints impose mutually contradictory requirements on user to role and role to permission assignments. An attempt to satisfy one of the constraints may result in a violation of the other. We show that the constrained role mining problem is NP-Complete and present heuristic solutions. Two distinct frameworks are presented in this paper. In the first approach, roles are initially mined without taking the constraints into account. The user-role and role-permission assignments are then checked for constraint violation in a post-processing step, and appropriately re-assigned, if necessary. In the second approach, constraints are enforced during the process of role mining. The methods are first applied on problems that consider the two constraints individually, and then with both considered together. Both methods are evaluated over a number of real-world data sets.

Role Based Access Control (RBAC) is accepted as the de facto access control model for organizations of all sizes. However, engineering the right set of roles is crucial to enable the correct deployment of RBAC within an organization. Indeed, discovering an optimal and correct set of roles from existing permission assignments, referred to as the role mining problem (RMP), has gained significant attention in recent years. Role Mining is itself an instantiation of Boolean matrix decomposition – wherein a Boolean matrix is decomposed into two Boolean matrices giving a set of basis vectors and their appropriate combination. In fact, such decompositions are useful in a number of application domains beyond role engineering, including text mining as well as knowledge discovery. While a Boolean matrix can be decomposed in many ways, however, certain decompositions better characterize the semantics associated with the original matrix in a succinct but comprehensive way. Indeed, one can find different decompositions that are optimal with respect to different criteria that may match various semantics. In this paper, we first present a number of variants of the optimal Boolean matrix decomposition problem, including usage RMP, basic RMP, δ-approximate RMP, and edge RMP, that have pragmatic implications in the context of role mining. We then present a unified framework for modeling the optimal Boolean matrix decomposition and its variants using integer linear programming (ILP). Such modeling allows us to directly adopt the huge body of heuristic solutions and tools developed for integer linear programming. We also develop efficient heuristics and solutions for each RMP variant, and validate them by a comprehensive experimental evaluation.

Providing restrictive and secure access to resources is a challenging and socially important problem. Among the many formal security models, Role Based Access Control (RBAC) has become the norm in many of today's organizations for enforcing security. For every model, it is necessary to analyze and prove that the corresponding system is secure. Such analysis helps understand the implications of security policies and helps organizations gain confidence on the control they have on resources while providing access, and devise and maintain policies. In this paper, we consider security analysis for the Temporal RBAC (TRBAC), one of the extensions of RBAC. The TRBAC considered in this paper allows temporal restrictions on roles themselves, user-permission assignments (UA), permission-role assignments (PA), as well as role hierarchies (RH). Towards this end, we first propose a suitable administrative model that governs changes to temporal policies. Then we propose our security analysis strategy, that essentially decomposes the temporal security analysis problem into smaller and more manageable RBAC security analysis sub-problems for which the existing RBAC security analysis tools can be employed. We then evaluate them from a practical perspective by evaluating their performance using simulated data sets.

This panel will address the following question. Does an increase in the granularity of access control systems produce a measurable reduction in risk and help meet the goals of the organization, or is the cost prohibitively high?

Role Based Access Control (RBAC) is the de facto standard in access control models, and is widely used in many applications and organizations of all sizes. However, the task of finding an appropriate set of roles, called role engineering, remains the most challenging roadblock to effective deployment. In recent years, this problem has attracted a lot of attention, with several bottom-up approaches being proposed, under the field of role mining. However, most of these theoretical approaches cannot be directly applied to large scale datasets, which is where they are most necessary. Therefore, in this paper, we look at how to make role mining practical and usable for actual deployment. We propose a six steps methodology that makes role mining scalable without sacrificing on utility and is agnostic to the actual role mining technique used. The experimental evaluation validates the viability of our approach.

Today, Role Based Access Control (RBAC) is the de facto model used for advanced access control, and is widely deployed in diverse enterprises of all sizes. Several extensions to the authorization as well as the administrative models for RBAC have been adopted in recent years. In this paper, we consider the temporal extension of RBAC (TRBAC), and develop safety analysis techniques for it. Safety analysis is essential for understanding the implications of security policies both at the stage of specification and modification. Towards this end, in this paper, we first define an administrative model for TRBAC. Our strategy for performing safety analysis is to appropriately decompose the TRBAC analysis problem into multiple subproblems similar to RBAC. Along with making the analysis simpler, this enables us to leverage and adapt existing analysis techniques developed for traditional RBAC. We have adapted and experimented with employing two state of the art analysis approaches developed for RBAC as well as tools developed for software testing. Our results show that our approach is both feasible and flexible.

The role mining problem has received considerable attention recently. Among the many solutions proposed, the Boolean matrix decomposition (BMD) formulation has stood out, which essentially discovers roles by decomposing the binary matrix representing user-to-permission assignment (UPA) into two matrices-user-to-role assignment (UA) and permission-to-role assignment (PA). However, supporting certain embedded constraints, such as separation of duty (SoD) and exceptions, is critical to the role mining process. Otherwise, the mined roles may not capture the inherent constraints of the access control policies of the organization. None of the previously proposed role mining solutions, including BMD, take into account these underlying constraints while mining. In this paper, we extend the BMD so that it reflects such embedded constraints by proposing to allow negative permissions in roles or negative role assignments for users. Specifically, by allowing negative permissions in roles, we are often able to use less roles to reconstruct the same given user-permission assignments. Moreover, from the resultant roles we can discover underlying constraints such as separation of duty constraints. This feature is not supported by any existing role mining approaches. Hence, we call the role mining problem with negative authorizations the constraint-aware role mining problem (CRM). We also explore other interesting variants of the CRM, which may occur in real situations. To enable CRM and its variants, we propose a novel approach, extended Boolean matrix decomposition (EBMD), which addresses the ineffectiveness of BMD in its ability of capturing underlying constraints. We analyze the computational complexity for each of CRM variants and present heuristics for problems that are proven to be NP-hard.

Graph structured data can be ubiquitously found in the real world. For example, social networks can easily be represented as graphs where the graph connotes the complex sets of relationships between members of social systems. While their analysis cou

Mining discrete patterns in binary data is important for many data analysis tasks, such as data sampling, compression, and clustering. An example is that replacing individual records with their patterns would greatly reduce data size and simplify subsequent data analysis tasks. As a straightforward approach, rank-one binary matrix approximation has been actively studied recently for mining discrete patterns from binary data. It factorizes a binary matrix into the multiplication of one binary pattern vector and one binary presence vector, while minimizing mismatching entries. However, this approach suffers from two serious problems. First, if all records are replaced with their respective patterns, the noise could make as much as 50% in the resulting approximate data. This is because the approach simply assumes that a pattern is present in a record as long as their matching entries are more than their mismatching entries. Second, two error types, 1-becoming-0 and 0-becoming-1, are treated evenly, while in many application domains they are discriminated. To address the two issues, we propose weighted rank-one binary matrix approximation. It enables the tradeoff between the accuracy and succinctness in approximate data and allows users to impose their personal preferences on the importance of different error types. The decision problem, however, as proved in the paper is NP-complete. To solve it, several different mathematical programming formulations are provided, from which 2-approximation algorithms are derived for some special cases. An adaptive tabu search heuristic is presented for solving the general problem, and our experimental study shows the effectiveness of the heuristic.

This issue of the Journal of Computer Security comprises of three papers presented at the 22nd IFIP 11.3 Working Group Conference on Data and Application Security, which was held in London, UK, in July 2008.The primary objective of this annual conference is to disseminate original research results and the development efforts in the area of data and application security and privacy, and to provide a platform for researchers and practitioners to share their knowledge and experience.The three papers in this special issue were invited submissions that were substantially extended for journal publication and were reviewed through a normal review process of the Journal of Computer Security.These three papers address different aspects of data protection: efficient search on encrypted data, access control for spatio-temporal data, and preventing the leakage of private information when performing a combined analysis of data from multiple sources.The first paper, "Shared and searchable encrypted data for untrusted servers", by Changyu Dong, Giovanni Russello and Naranker Dulay, proposes a novel technique for keyword searches over outsourced encrypted data.The proposed solution is based on the combined use of proxy-encryption and keyword search, that allows each user to keep one secret key only.This makes key revocation operations highly efficient since it does not require re-encryption.Unlike prior approaches, this proposed model supports both read and write operations of the outsourced data.The second paper, "On the formalization and analysis of a spatio-temporal rolebased access control model", by Manachai Toahchoodee and Indrakshi Ray, proposes a new spatiotemporal role-based access control model for use in mobile applications.It supports the notions of spatial temporal inheritance, Separation of Duties and delegation of roles, permissions and delegation chain.It employs color Petri nets to perform automated analysis in order to verify the consistency and correctness of the proposed model.The third paper, "Secure construction and publication of contingency tables from distributed data", by Xiaoyun He, Haibing Lu, Jaideep Vaidya and Nabil Adam, presents a set of techniques for privacy preserving construction of contingency tables over data collected from multiple sources.Contingency tables are often used to study the relationship between two or more related variables.When there are multiple sources of the original data, these contingency tables must be constructed in a privacy preserving manner to avoid any leakage of private information.The paper presents approaches for both horizontally and vertically partitioned data.

In a mobile environment, user’s physical location plays an important role in determining access to resources. However, because current moving object databases do not keep the exact location of the moving objects, but rather maintain their approximate location for reasons of minimizing the updates, the access request evaluation cannot always guarantee the intended access control policy requirements. This may be risky to the system’s security, especially for highly sensitive resources. In this paper, we introduce an authorization model that takes the uncertainty of location measures into consideration for specifying and evaluating access control policies. An access request is granted only if the confidence level of the location predicate exceeds the predefined uncertainty threshold level specified in the policy. However, this access request evaluation is computationally expensive as it requires to evaluate a location predicate condition and may also require evaluating the entire moving object database. For reducing the cost of evaluation, in this paper, we compute lower and upper bounds (Rmin and Rmax) on the region that minimize the region to be evaluated, thereby allowing unneeded moving objects to be discarded from evaluation. To further minimize the region of evaluation, we propose to compute Rmin′ and Rmax′ that have smaller filter size so that filtering more objects out for evaluation. In addition, we extend our approach such that it does not require assumptions on the probability distribution functions. We show how these filters Rmin, Rmax, Rmin′, and Rmax′ can be computed and maintained, and provide algorithms to process access requests.

Location-based services (LBS) aim at delivering point of need information. Personalization and customization of such services, based on the profiles of mobile users, would significantly increase the value of such services. Since profiles may include sensitive information of mobile users and moreover can help identify a person, such customization is allowable only when the security and privacy policies dictated by them are respected. While LBS providers are presumed to be untrusted entities, the location services that capture and maintain mobile users' location to enable communication are considered trusted, and therefore can capture and manage the profile information. The question then is, how to enable the use of location based services while protecting privacy? In this paper, we address the problem of privacy preservation via anonymization. Prior research in this area attempts to ensure k-anonymity by generalizing the location. However, a person may still be identified based on his/her profile if the profiles of all k people in the generalized region are not the same. We extend the notion of k-anonymity by proposing a profile based k-anonymization model that guarantees anonymity even when profiles of mobile users are revealed to untrusted entities. Specifically, our anonymization methods generalize both location and profiles to the extent specified by the user. We propose a novel unified index structure, called the P TPR -tree to enhance the performance during anonymization. P TPR -tree is an extension of the TPR-tree [in: SIGMOD'00: Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, New York, NY, USA, ACM, 2000, pp. 331–342] which organizes both the locations of mobile users as well as their profiles using a single index, and therefore can efficiently find candidate users for the proposed profile based anonymization models.

The concept of location k-anonymity has been proposed to address the privacy issue of location based services (LBS). Under this notion of anonymity, the adversary only has the knowledge that the LBS request originates from a region containing at least k people, and therefore cannot individually distinguish the requestor. However, new types of LBS services such as continuous nearest neighbor searches require the knowledge of the user's trajectory, which can lead to a privacy breach. The longer the adversary can track the user's trajectory, the stronger the possibility that the user's sensitive information is revealed. To alleviate this problem, we propose algorithms to optimally partition a continuous request into multiple LBS requests with shorter trajectories. This results in increased privacy due to the unlinking of different requests over time and has the added benefit of improving the overall quality of service since the anonymized regions are now smaller. Our experimental results show that significant privacy and QoS benefits can be achieved with nominal computational overhead.

Distributed and open environments require flexible, scalable and extendible trust verification mechanisms to access resources. To address this, the use of digital credentials as a means for making access decisions has been promoted. The resource owner needs to verify if the requester's credentials satisfy the security policy of the owner. However, such verification becomes a challenging problem when either the requester does not wish to disclose her credentials before the verification is complete, or the owner wishes to keep its security policy confidential from the requester, or both. In addition, the requester may associate a score to each of her credentials based on her perceived level of privacy. Earlier proposals to address this problem limit the owners policy to be a set of credentials. However, real world policies are more complex than a simple set. In this paper, we present three alternative privacy preserving trust verification solutions that protect both the owner's policy and requester's credentials, while at the same time allowing more expressive owner's policies that can be specified as a tree structure. We analyze their computational complexity, communication cost and the amount of disclosure.

Uncontrolled dissemination of geospatial data may have grave implications on national security and personal privacy. Geospatial data can be considered sensitive based on attributes such as the location, resolution and the time of capture, etc. As such, authorisations associated with this data also possess spatial and temporal attributes. The main contribution of this paper is to improve the response time of access requests, by proposing a unified index structure called *-tree that is capable of indexing both spatiotemporal objects and authorisations in a single index structure. *-tree is an extension of R-tree that indexes objects based on their resolutions as well as on their spatial and temporal attributes and overlays spatiotemporal authorisations on the nodes of the tree. We show how the *-tree can be constructed and maintained, provide algorithms to process access requests and present performance evaluation results that demonstrate a significant improvement in performance.

The semantic web has been envisioned as a machine interpretable web, where data instances are described through concepts defined and related in ontologies. Though ontologies are publicly available as a crucial component of the semantic web infrastructure, many data instances are sensitive and should be kept confidential. Sensitive information can be illegally inferred from other seemingly unclassified information in combination with the underlying data semantics and interrelationships revealed by ontologies. In other words, the visibility of ontologies can pose inference threats to the security of data instances, and this requires that security policies be specified in such a way that the semantic relationships among data instances are taken into account. To protect the semantic web data or other semantics-rich data, this paper presents semantics-aware security policy specification. We propose concept-level, association-level and property-level access control models for different security objects, and that authorisations be propagated based on different inference patterns. These propagation policies can be used to generate safe and consistent access control authorisations.

Today, role-based access control (RBAC) has become a well-accepted paradigm for implementing access control because of its convenience and ease of administration. However, in order to realize the full benefits of the RBAC paradigm, one must first define the roles accurately. This task of defining roles and associating permissions with them, also known as role engineering, is typically accomplished either in a top-down or in a bottom-up manner. Under the top-down approach, a careful analysis of the business processes is done to first define job functions and then to specify appropriate roles from them. While this approach can help in defining roles more accurately, it is tedious and time consuming since it requires that the semantics of the business processes be well understood. Moreover, it ignores existing permissions within an organization and does not utilize them. On the other hand, under the bottom-up approach, existing permissions are used to derive roles from them. As a result, it may help automate the process of role definition. In this paper, we present an unsupervised approach, called RoleMiner, for mining roles from existing user-permission assignments. Since a role, when semantics are unavailable, is nothing but a set of permissions, the task of role mining is essentially that of clustering users having the same (or similar) permissions. However, unlike the traditional applications of data mining that ideally require identification of nonoverlapping clusters, roles will have overlapping permissions and thus permission sets that define roles should be allowed to overlap. It is this distinction from traditional clustering that makes the problem of role mining nontrivial. Our experiments with real and simulated data sets indicate that our role mining process is quite accurate and efficient. Since our role mining approach is based on subset enumeration, it is fairly robust to reasonable levels of noise.

Devising a complete and correct set of roles has been recognized as one of the most important and challenging tasks in implementing role-based access control. A key problem related to this is the notion of goodness/interestingness—when is a role good/interesting? In this article, we define the Role Mining Problem (RMP) as the problem of discovering an optimal set of roles from existing user permissions. The main contribution of this article is to formally define RMP and analyze its theoretical bounds. In addition to the above basic RMP, we introduce two different variations of the RMP, called the δ-Approx RMP and the minimal-noise RMP that have pragmatic implications. We reduce the known “Set Basis Problem” to RMP to show that RMP is an NP-complete problem. An important contribution of this article is also to show the relation of the RMP to several problems already identified in the data mining and data analysis literature. By showing that the RMP is in essence reducible to these known problems, we can directly borrow the existing implementation solutions and guide further research in this direction. We also develop a heuristic solution based on the previously proposed FastMiner algorithm, which is very accurate and efficient.

User search query logs have proven to be very useful, but have vast potential for misuse. Several incidents have shown that simple removal of identifiers is insufficient to protect the identity of users. Publishing such inadequately anonymized data can cause severe breach of privacy. While significant effort has been expended on coming up with anonymity models and techniques for microdata, there is little corresponding work for query log data. Query logs are different in several important aspects, such as the diversity of queries and the causes of privacy breach. This necessitates the need to design privacy models and techniques specific to this environment. This paper takes a first cut at tackling this challenge. Our main contribution is to define effective anonymization models for query log data along with proposing techniques to achieve such anonymization. We analyze the inherent utility and privacy tradeoff, and experimentally validate the performance of our techniques.

In a database system, disclosure of confidential private data may occur if users can put together the answers of past queries. Traditional access control mechanisms cannot guard against such breaches to private data. Online auditing techniques have been advanced to limit such disclosure of private data. Essentially, before answering any query, these techniques inspect the answers of the past queries to determine whether answering this query would compromise the stated data disclosure policies. While the primary requirement for online auditing is high efficiency, existing auditing approaches are expensive with respect to both computational time and space. Specifically, this cost is excessive in the general case of auditing arbitrary aggregate queries over real-valued confidential attributes with respect to interval-based privacy disclosure.

With the vast increase in collection and storage of data, the problem of data summarization is most critical for effective data management. Since much of this data is categorical in nature, it can be viewed in terms of a Boolean matrix. Boolean matrix decomposition (BMD) has been used to provide concise and interpretable representations of Boolean data sets. A Boolean matrix can be expressed as a product of two Boolean matrices, where the first matrix represents a set of meaningful concepts, and the second describes how the observed data can be expressed as combinations of those concepts. Typically, the combination is only in terms of the set union. In other words, a successful Boolean matrix decomposition gives a set of concepts and shows how every column of the input data can be expressed as a union of some subset of those concepts. However, this way of modeling only incompletely represents real data semantics. Essentially, it ignores a critical component -- the set difference operation: a column can be expressed as the combination of union of certain concepts as well as the exclusion of other concepts. This has two significant benefits. First, the total number of concepts required to describe the data may itself be reduced. Second, a more succinct summarization may be found for every column. In this paper, we propose the extended Boolean matrix decomposition (EBMD) problem, which aims to factor Boolean matrices using both the set union and set difference operations. We study several variants of the problem, show that they are NP-hard, and propose efficient heuristics to solve them. Extensive experimental results demonstrate the power of EBMD.

An access control system is often viewed as a state transition system. Given a set of access control policies, a general safety requirement in such a system is to determine whether a desirable property is satisfied in all the reachable states. Such an analysis calls for formal verification. While formal analysis on traditional RBAC has been done to some extent, the extensions of RBAC lack such an analysis. In this paper, we propose a formal technique to perform security analysis on the Generalized Temporal RBAC (GTRBAC) model which can be used to express a wide range of temporal constraints on different RBAC components like role, user and permission. In the proposed approach, at first the GTRBAC system is mapped to a state transition system built using timed automata. Characteristics of each role, user and permission are captured with the help of timed automata. A single global clock is used to express the various temporal constraints supported in a GTRBAC model. Next, a set of safety and liveness properties is specified using computation tree logic (CTL). Model checking based formal verification is then done to verify the properties against the model to determine if the system is secure with respect to a given set of access control policies. Both time and space analysis has been done for studying the performance of the approach under different configurations.

Graph structured data can be ubiquitously found in the real world. For example, social networks can easily be represented as graphs where the graph connotes the complex sets of relationships between members of social systems. While their analysis could be beneficial in many aspects, publishing certain types of social networks raises significant privacy concerns. This brings the problem of graph anonymization into sharp focus. Unlike relational data, the true information in graph structured data is encoded within the structure and graph properties. Motivated by this, we propose a structure aware anonymization approach that maximally preserves the structure of the original network as well as its structural properties while anonymizing it. Instead of anonymizing each node one by one independently, our approach treats each partitioned substructural component of the network as one single unit to be anonymized. This maximizes utility while enabling anonymization. We apply our method to both synthetic and real datasets and demonstrate its effectiveness and practical usefulness.

Spatial outlier detection approaches identify outliers by first defining a spatial neighborhood. However, existing approaches suffer from two issues: (1) they primarily consider autocorrelation alone in forming the neighborhood, but ignore heterogene

Because of its ease of administration, role-based access control (RBAC) has become the norm to enforcing security in most of today's organizations. For implementing RBAC, it is important to devise a complete and correct set of roles. This task, known as role engineering, has been identified as one of the costliest components in deploying RBAC. A key problem with respect to role engineering is that there is no formal metric for measuring the goodness/interestingness of the devised set of roles. Recently, Vaidya et al. [26], formally define the role mining problem (RMP) as the problem of discovering an optimal set of roles from existing user permissions, and analyze its theoretical bounds. Essentially, given a user-permission assignment (UPA), the basic RMP is to discover the user-role assignment relation (UA) and role-permission assignment relation (PA) such that the number of roles required is minimum. In this paper, we present another interesting and useful problem, called the edge-RMP, with a different minimality objective. The edge-RMP, requires the discovery of a complete and correct set of roles such that the discovered |UA|+|PA| is the minimum possible. Minimal |UA|+|PA| is a useful metric as it would minimize the administrative burden since less number of assignments need to be managed. Although the basic-RMP and the edge-RMP appear to be related problems, we demonstrate with concrete examples that they are, in fact, independent of each other. We prove that the edge-RMP is an NP-hard problem by reducing the known “vertex cover problem” to the decision version of the edge-RMP. Another important contribution of this paper is to provide a binary integer programming solution to this problem by showing that the edge-RMP can be formulated in that form. As a result, one can directly borrow existing implementation solutions for binary integer programming and guide further research in this direction. We also propose a heuristic solution for large scale problems, and experimentally validate our algorithm.

Role hierarchies are fundamental to the role based access control (RBAC) model. The notion of role hierarchy is a well understood concept that allows senior roles to inherit the permissions of the corresponding junior roles. Role hierarchies further ease the burden of security administration, as there is no need to explicitly specify and maintain a large number of permissions. Given a set of roles or user permissions, one may construct a number of alternative hierarchies. However, there does not exist the notion of an optimal role hierarchy. Optimality helps in maximizing the benefit of employing the role hierarchy. In this paper, we propose such a formal metric. Our optimality notion is based on the smallest graph representation of the role hierarchy (minimal in the number of edges) having the same transitive closure as any alternate representation. We show why this makes sense as well as ways to achieve this. The main contributions of this paper are to formalize the notion of optimality for role hierarchy construction, along with proposing heuristic solutions to achieve this objective, thus making role hierarchies feasible and practical.

A decomposition of a binary matrix into two matrices gives a set of basis vectors and their appropriate combination to form the original matrix. Such decomposition solutions are useful in a number of application domains including text mining, role engineering as well as knowledge discovery. While a binary matrix can be decomposed in several ways, however, certain decompositions better characterize the semantics associated with the original matrix in a succinct but comprehensive way. Indeed, one can find different decompositions optimizing different criteria matching various semantics. In this paper, we first present a number of variants to the optimal Boolean matrix decomposition problem that have pragmatic implications. We then present a unified framework for modeling the optimal binary matrix decomposition and its variants using binary integer programming. Such modeling allows us to directly adopt the huge body of heuristic solutions and tools developed for binary integer programming. Although the proposed solutions are applicable to any domain of interest, for providing more meaningful discussions and results, in this paper, we present the binary matrix decomposition problem in a role engineering context, whose goal is to discover an optimal and correct set of roles from existing permissions, referred to as the role mining problem (RMP). This problem has gained significant interest in recent years as role based access control has become a popular means of enforcing security in databases. We consider several variants of the above basic RMP, including the min-noise RMP, delta-approximate RMP and edge-RMP. Solutions to each of them aid security administrators in specific scenarios. We then model these variants as Boolean matrix decomposition and present efficient heuristics to solve them.

Location based services (LBS) aim at delivering point of need information. Personalization and customization of such services, based on the profiles of mobile users, would significantly increase the value of these services. Since profiles may include sensitive information of mobile users and moreover can help identify a person, customization is allowed only when the security and privacy policies dictated by them are respected. While LBS are often presumed as untrusted entities, the location services that capture and maintain mobile users' location to enable communication are considered trusted, and therefore can capture and manage the profile information. In this paper, we address the problem of privacy preservation via anonymization. Prior research in this area attempts to ensure k-anonymity by generalizing the location. However, a person may still be identified based on his/her profile if the profiles of all k people are not the same. We extend the notion of k-anonymity by proposing a profile based k-anonymization model that guarantees anonymity even when profiles of mobile users are known to untrusted entities. Specifically, our proposed approaches generalize both location and profiles to the extent specified by the user. We support three types of queries - mobile users requesting stationary resources, stationary users requesting mobile resources, and mobile users requesting mobile resources. We propose a novel unified index structure, called the (PTPR- tree), which organizes both the locations of mobile users as well as their profiles using a single index, and as a result, offers significant performance gain during anonymization as well as query processing.

Due to its exibility, ease of administration and intuitiveness, role-based access control (RBAC) is now part of most operating systems and application software. As a result of its commercial success, it has become a standard to implementing access control in many of today's organizations. However, deploying RBAC requires one to first identify an accurate and complete set of roles, and assign users to roles and permissions to roles. This process, known as role engineering [3], has been identified as one of the costliest components in realizing RBAC [7]. Although the problem of role engineering has been studied since early nineties, a recent surge in interest can be seen equally from academic and industry communities. The primary focus of this panel is to have an in-depth discussion of this problem along several dimensions. The panelists, drawn from both academia and industry, include Gail Ahn (University of North Carolina, Charlotte), Vijay Atluri (Rutgers University), Edward Coyne (Science Applications International Corporation), William Horne (Hewlett-Packard), Axel Kern (Beta Systems), Sylvia Osborn (University of Western Ontario) and Andreas Schaad (SAP Labs), who are experts in role engineering.

Security policy enforcement is instrumental in preventing the unauthorized disclosure of sensitive data, protecting the integrity of vital data, mitigating the likelihood of fraud, and ultimately enabling the secure sharing of information. In accessing a given resource, policy may dictate, for example that a user has a need-to-know, is appropriately cleared, is competent, has not already performed a different operation on the same resource, the resource was previously accessed by a different user, is incapable of accessing other enterprise resources, or is capable of accessing an object or any copy of the object while performing a specific task. Currently, there exist a rich set of formal security models that can translate organizational policies. A small sample of well documented policies include, avors of Discretionary Access Control (DAC), Mandatory Access Control (MAC), Role-Based Access Control (RBAC), ORCON, Chinese wall, and History-Based Separation of Duty. Enterprise policies that are designed to protect resources are also ad-hoc in nature.

Devising a complete and correct set of roles has been recognized as one of the most important and challenging tasks in implementing role based access control. A key problem related to this is the notion of goodness - when is a set of roles good? Recently, the role mining problem (RMP) has been defined as the problem of discovering an optimal set of roles from existing user permissions. Several different objectives for optimality have been proposed. However, one problem with these definitions is that often organizations already have a deployed set of roles and wish to optimize this set. Even if an optimal set of roles is discovered, if this is widely different, it is impossible to simply throw out the deployed roles and start using the new ones as this may disrupt organizational processes and separation of duty constraints that are defined on roles. Essentially, what is missing is taking role migration cost into account when defining optimality, which would allow us to come up with the best suited set of roles.

In the last decade, mobile communication has enjoyed unprecedented growth all over the world. The recent advances in mobile communication technologies including Global Positioning System (GPS) and Radio Frequency Identification (RFID) have propelled

Often, it is required to identify anomalous windows over a spatial region that reflect unusual rate of occurrence of a specific event of interest. A spatial scan statistic-based approach essentially considers a scan window and computes the statistic of a parameter(s) of interest, and identifies anomalous windows by moving the scan window in the region. While this approach has been successfully employed in identifying anomalous windows, earlier proposals adopting spatial scan statistic suffer from two limitations: (1) In general, the scan window should be of a regular shape (e.g., circle, rectangle, cylinder). Thus, most approaches are capable of identifying anomalous windows of fixed shapes only. However, the region of anomaly, in general, is not necessarily of a regular shape. Recent proposals to identify windows of irregular shapes identify windows much larger than the true anomalies or penalize large-sized windows. (2) These techniques take into account autocorrelation among spatial data but not spatial heterogeneity. As a result, they often result in inaccurate anomalous windows. To address these limitations, in this paper, we propose a random-walk-based Free-Form Spatial Scan Statistic (FS3). We construct a weighted Delaunay nearest neighbor (WDNN) graph to capture both spatial autocorrelation and heterogeneity. We then use random walks to identify natural free-form scan windows that are not restricted to a predefined shape. We use spatial scan statistics to identify anomalous windows and prove that they are not random but indeed are formed as a result of an anomaly. Application of FS3on real data sets has shown that it can identify more refined anomalous windows with better likelihood ratio of it being an anomaly than those identified by earlier spatial scan statistic approaches.

Devising a complete and correct of roles has been recognized as one of the most important and challenging tasks in implementing role based access control. A key related to this is the notion of goodness/interestingness -- when is a role good/interesting? In this paper, we define the role mining (RMP) as the of discovering an optimal of roles from existing user permissions. The main contribution of this paper is to formally define RMP, and analyze its theoretical bounds. In addition to the above basic RMP, we introduce two different variations of the RMP, called the δ-approx RMP and the Minimal Noise RMP that have pragmatic implications. We reduce the known set basis problem to RMP to show that RMP is an NP-complete problem. An important contribution of this paper is also to show the relation of the role mining to several problems already identified in the data mining and data analysis literature. By showing that the RMP is in essence reducible to these known problems, we can directly borrow the existing implementation solutions and guide further research in this direction.

In a dynamic coalition environment, organizations should be able to exercise their own local fine-grained access control policies while sharing resources with external entities. In this paper, we propose an approach that exploits the semantics associated with subject and object attributes to facilitate automatic enforcement of organizational access control policies while resource sharing occurs among coalition members. Our approach relies on identifying the necessary attributes required by external users to gain access to a specific organizational object (or service). Specifically, it consists of extracting user attribute sets that semantically match with the attributes of the objects for which a role has permissions. This relies on a closer examination of why a user is assigned a specific role. These attribute sets are first pruned based on their significance in characterizing a role, which are then checked against those submitted by an external user to decide whether to allow or deny access to the specific object. While our goal in this paper is to support coalition based access control, the proposed approach can also aid in automating the process of role engineering.

Geospatial databases include any data with reference to geocoordinate information. The geospatial data can either be digital raster images that represent the data on the earth in the form of pixels or digital vector data that is primarily from satellites. Due to the fact that many of the high-resolution satellites are commercial in nature, uncontrolled dissemination of the high resolution imagery may cause severe threats to national security as well as personal privacy. The severity of the threats is even more significant when this information is combined with vector maps or other publicly available vector data. In this paper, we present a GeoSpatial Authorisation System (GSAS), which is based on a GeoSpatial Authorisation Model (GSAM), for specifying and enforcing access control policies that makes reference to the spatial regions and locational credentials. The specification of authorisations is based on the spatial and temporal attributes associated with the image data, resolution of the images, geospatial credentials associated with users and privilege modes including view, zoom-in, overlay, view-thumbnail, view-annotation, identify, animate and fly-by that are relevant for geospatial image data. We present the GSAS system and its functionalities.

Today, many applications require users from one organization to access data belonging to organizations. While traditional solutions offered for the federated and mediated databases facilitate this by sharing metadata, this may not be acceptable for certain organizations due to privacy concerns. In this paper, we propose a novel solution -- Privacy-preserving Access Control Toolkit (PACT) -- that enables privacy-preserving secure semantic access control and allows sharing of data among heterogeneous databases without having to share metadata. PACT uses encrypted ontologies, encrypted ontology-mapping tables and conversion functions, encrypted role hierarchies and encrypted queries. The encrypted results of queries are sent directly from the responding system to the requesting system, bypassing the mediator to further improve the security of the system. PACT provides semantic access control using ontologies and semantically expanded authorization tables at the mediator. One of the distinguishing features of the PACT is that it requires very little changes to underlying databases. Despite using encrypted queries and encrypted mediation, we demonstrate that PACT provides acceptable performance.

Role engineering, the task of defining roles and associating permissions to them, is essential to realize the full benefits of the role-based access control paradigm. Essentially, there are two basic approaches to accomplish this: the top-down and the bottom-up. The top-down approach relies on a careful analysis of the business processes to define job functions and then specify appropriate roles from them. While this approach can aid in defining roles more accurately, it is tedious and time consuming since it requires that the semantics of the business processes be well understood. Moreover, it ignores existing permissions within an organization and does not utilize them. On the other hand, the bottom-up approach starts with existing permissions and attempts to derive roles from them, thus helping to automate role definition. In this paper, we present an unsupervised approach called RoleMiner that mines roles from existing user-permission assignments. Since a role is nothing but a set of permissions, when no semantics are available, the task of role mining is essentially that of clustering users that have same (or similar) permissions. However, unlike the traditional applications of data mining that ideally require identification of non-overlapping clusters, roles will have overlapping permission needs and thus permission sets that define roles should be allowed to overlap. It is this distinction from traditional clustering that makes the problem of role mining non-trivial. Our experiments with real and simulated data sets indicate that our role mining process is quite accurate and efficient.

Work flows model and control the execution of business process in an organization. They are typically comprised of tasks or logical steps in the business process. To mitigate the ability of insiders to commit fraud, care should be taken that people authorized to perform critical tasks cannot collude. This is typically done through the specification of separation of duty (SOD)constraints. SOD constraints impose restrictions on which users or roles can be assigned to tasks and have been discussed widely in the research literature in the context of a single work flow instance. In this paper, we argue that SOD constraints that span multiple instances of a work flow also need to be considered to mitigate the security fraud. To this end, we extend the notion of SOD to include constraints that span multiple executing instances of a work flow and constraints that also take into consideration the history of completed work flow instances. We present a constraint specification language to specify the inter-instance constraints and propose methodologies to identify the cases in which certain SOD specifications would result in an anomaly. Specifically, we identify 3 types of anomalies, namely, inconsistency, depletion anomaly and overlapping anomaly The identification and rectification of anomalies are done at both the work flow specification time as well as at runtime,as appropriate,so that users can be assigned to tasks in a consistent manner.

Ontologies evolve over time at both structural and semantic levels. Detecting semantic changes to ontologies is essential to the functioning of data instances and dependent ontologies over the semantic Web. In this article, we propose a SemDiff approach to examining structural changes and deriving both explicit and implicit semantic changes between ontology versions. Our approach exploits the semantic dependency between properties and concepts: we introduce the notion of isosems, and conduct implication analysis to examine whether, when, and how semantic changes to an isosem imply semantic changes to other isosems. A prototype of our approach is implemented.

Often, it is required to identify anomalous windows over a spatial region that reflect unusual rate of occurrence of a specific event of interest. A spatial scan statistic essentially considers a scan window, and identifies anomalous windows by moving the scan window in the region. While spatial scan statistic has been successful, earlier proposals suffer from two limitations: (i) They restrict the scan window to be of a regular shape (e.g., circle, rectangle, cylinder). However, the region of anomaly, in general, is not necessarily of a regular shape. (ii) They take into account autocorrelation among spatial data, but not spatial heterogeneity. As a result, they often result in inaccurate anomalous windows. To address these limitations, we propose a random walk based free-form spatial scan statistic (FS/sup 3/). Application of FS/sup 3/ on real datasets has shown that it can identify more refined anomalous windows with better likelihood ratio of it being an anomaly, than those identified by earlier spatial scan statistic approaches.

Typically, high-resolution remote sensing (HRRS) images contain a high level noise as well as possess different texture scales. As a result, existing image segmentation approaches are not suitable to HRRS imagery. In this paper, we have presented an unsupervised texture-based segmentation algorithm suitable for HRRS images, by extending the local binary pattern texture features and the lossless wavelet transform. Our experimental results using USGS 1ft or thoimagery show a significant improvement over the previously proposed LBP approach.

A composite multimedia object (cmo) is comprised of different media components such as text, video, audio and image, with a variety of constraints that must be adhered to. The constraints are 1) rendering constraints that comprise the temporal and spatial constraints between different components, and 2) behavioral constraints that include the security and fidelity constraints on each component. Different users have different 3Cs, which are: capabilities (e.g., monitor size), characteristics (e.g., age) and credentials (e.g., subscription to service). The focus of this paper is on addressing the problems of (1) specifying a consistent cmo that "automatically" adapts its spatial constraints to different user's devices. (2) Identifying the conflicts that might occur between the temporal and spatial constraints when having different monitor resolution that displays the cmo by means of reachability analysis of colored time Petri net (3) Resolving the identified conflicts automatically to render a cmo that is error-free when rendered at different user devices.

A key challenge for Mobile services is to offer personalized contents while preserving the privacy of customers. In mobile applications, location information is modeled as moving objects. Providing proper protection to customer information can be achieved by an access control system. However, providing such system is a challenging task due to: 1) the spatio-temporal nature of the constraints as well as the location information, and the interaction among them; 2) the complexity of resolving spatio-temporal and granularity conflicts; and 3) the required scalability and efficiency. In this paper, we present a solution that includes an access control model for moving objects and customer profiles. We also present a mechanism that enforces the spatio-temporal policies. The mechanism consists of three components: a text encoder, a spatio-temporal module that computes interactions between moving objects and spatio-temporal constraints, and a new data structure referred to as the Adaptive Search Multi-way trie (ASM-trie). We present the insertion and search algorithms of the ASM-trie and an evaluation study that shows the positive impact of the ASM-trie on the search efficiency.

A composite multimedia object (cmo) is comprised of different media components such as text, video, audio and image, with a variety of constraints that must be adhered to. The constraints are 1) rendering relationships that comprise the temporal and spatial constraints between different components, 2) behavioral requirements that include the security and fidelity constraints on each component and, 3) user interactions on a set of related media components. Different users have different capabilities (e.g. age), characteristics (e.g. monitor size) and credentials (e.g. subscription to service). Our objective is to author an interactive adaptive cmo that renders itself correctly to different users. Therefore, it is important to guarantee the consistency of the cmo specifications in all possible scenarios. In this paper, we include the user interaction with temporal and spatio-temporal behavior in the specification of the adaptive cmo. We then check the consistency of user interaction specifications by transforming the specifications into a color time Petri net model. We perform a reachability analysis on the Petri net to identify inconsistencies. We then resolve the identified inconsistencies to have a consistent Petri net. A consistent Petri net presents an error-free interactive cmo that can adapt to different users, by guaranteeing that link user interactions are reachable for all eligible users.

Workflows model and control the execution of business processes in an organization. A workflow typically comprises of a set of coordinated activities, known as tasks. Typically, organizations establish a set of security policies, that regulate how the business process and resources should be managed. While a simple policy may specify which user (or role) can be assigned to execute a task, a complex policy may specify authorization constraints, such as separation of duties. Users may delegate the tasks assigned to them. Often such delegations are short-lived and come into play when certain conditions are satisfied. For example, a user may want to delegate his task of check approval only when going on vacation, when a check amount is less than a certain amount, or when his workload exceeds a certain limit.In this paper, we extend the notion of delegation to allow for such conditional delegation, where the delegation conditions can be based on time, workload and task attributes. When workflow systems entertain conditional delegation, different types of constraints come into play, which include authorization constraints, role activation constraints and workflow dependency requirements. We address the problem of assigning users to tasks in a consistent manner such that none of the constraints are violated.

No abstract available.

Typically, geospatial data include satellite imagery, digital orthophoto quads, maps, digital line graphs, census data, voter registration, land ownership data, and land use data. This data is considered sensitive based on its location (characterized by its longitude and latitude), resolution, and the time of capture, among others. Since both objects and authorizations are associated with spatial and temporal attributes, in order to process access requests efficiently, it is essential that they both be accessed using some sort of index structures. However, processing an access request under this approach requires searching two indexes - one the object index and the other the authorization index. In this paper, we propose a novel index called STAR-Tree, a Spatio Temporal Authorization-driven R -Tree, that can uniformly index both spatiotemporal objects and the authorizations that govern access to them. STAR-Tree is an extension of R-tree that allows objects of different resolutions be indexed based on their spatial and temporal attributes, as well as allows layering of spatiotemporal authorizations on the tree itself. Compared to the previously proposed RMX-Quadtree, STAR-Tree enjoys several advantages. First, the 3 dimensional nature of the STAR-Tree accommodates the temporal dimension. Second, the STAR-Tree imposes no restrictions on the region covered by the geospatial objects. Third, in the STAR-Tree images of the same resolution may overlap with one another. We demonstrate how such a tree can be constructed and maintained, and show how access requests can be processed in an efficient manner.

Workflow systems are gaining importance as an infrastructure for automating inter-organizational interactions, such as those in Electronic Commerce. In such an environment, a centralized Workflow Management System is not desirable because: (i) it can be a performance bottleneck, and (ii) the system s are inherently distributed, heterogeneous, and autonomous in nature. Decentralized execution of inter-organizational workflows may raise a number of security issues including those related to conflict-of-interest among competing organizations. In this paper, we first provide an approach to realize decentralized workflow execution, in which the workflow is divided into partitions, called self-describing workflows, and handled by a light weight workflow management component, called workflow stub, located at each organizational agent. Second, we identify the limitations of the traditional workflow model with respect to expressing the various types of join dependencies and extend the traditional workflow model suitably. Distinguishing the different types of dependencies among tasks is essential in the efficient execution of self-describing workflows. Finally, we recognize that placing the task execution agents that belong to the same conflict-of-interest class in one self-describing workflow may lead to unfair, and in some cases, undesirable results, akin to being on the wrong side of the Chinese wall. Therefore, to address the conflict-of-interest issues that arise in competitive business environments, we propose a decentralized workflow Chinese wall security model. We propose a restrictive partitioning solution to enforce the proposed model.

The advent of commercial observation satellites in the new millennium provides unprecedented access to timely information, as they produce images of the Earth with the sharpness and quality previously available only from US, Russian, and French military satellites. Due to the fact that they are commercial in nature, a broad range of government agencies (including international), the news media, businesses, and nongovernmental organizations can gain access to this information. This may have grave implications on national security and personal privacy. Formal policies for prohibiting the release of imagery beyond a certain resolution, and notifying when an image crosses an international boundary or when such a request is made, are beginning to emerge. Access permissions in this environment are determined by both the spatial and temporal attributes of the data, such as location, resolution level, and the time of image download, as well as those of the user credentials. Since existing authorization models are not adequate to provide access control based on spatial and temporal attributes, We propose a geospatial data authorization model (GSAM). Unlike the traditional access control models where authorizations are specified using subjects and objects, authorizations in GSAM are specified using credential expressions and object expressions. GSAM supports privilege modes including view, zoom-in, download, overlay, identify, animate, and fly by, among others. We present our access control prototype system that enables subject, object as well as authorization specification via a Web-based interface. When an access request is made, the access control system computes the overlapping region of the authorization and the access request. The zoom-in and zoom-out requests can simply be made through a click of the mouse, and the appropriate authorizations will be evaluated when these access requests are made.

We present a system, called the Temporal Data Authorization Model (TDAM), for managing authorizations for temporal data. TDAM is capable of expressing access control policies based on the temporal characteristics of data. TDAM extends existing authorization models to allow the specifications of temporal constraints on data, based on data validity, data capture time, and replication time, using either absolute or relative time references. The ability to specify access control based on such temporal aspects were not supported before. The formulae are evaluated with respect to various temporal assignments to ensure the correctness of access control.

The term information portals refers to Web sites that serve as main providers of focused information, gathered from distributed data sources. Gathering and disseminating information through information portals introduce new security challenges. In particular, the authorization specifications, as well as the granting process, are temporal by nature. Also, more often than not, the information provided by the portal is in fact derived from more than one backend data source. Therefore, any authorization model for information portals should support access control based on temporal characteristics of the data, and also should provide tools to prevent indirect unauthorized access through the use of derived data. In this article we focus our attention on devising such an authorization model. The distinguishing features of this model include: (1) the specification of authorizations based on temporal characteristics of data, and (2) a formal framework to derive authorizations in a consistent and safe manner, based on relationships among data.

Digital libraries (DLs) introduce several challenging requirements with respect to the formulation, specification and enforcement of adequate data protection policies. Unlike conventional database environments, a DL environment is typically characterized by a dynamic user population, often making accesses from remote locations, and by an extraordinarily large amount of multimedia information, stored in a variety of formats. Moreover, in a DL environment, access policies are often specified based on user qualifications and characteristics, rather than on user identity (e.g. a user can be given access to an R-rated video only if he/ she is more than 18 years old). Another crucial requirement is the support for content-dependent authorizations on digital library objects (e.g. all documents containing discussions on how to operate guns must be made available only to users who are 18 or older). Since traditional authorization models do not adequately meet the access control requirements typical of DLs, we propose a content-based authorization model that is suitable for a DL environment. Specifically, the most innovative features of our authorization model are: (1) flexible specification of authorizations based on the qualifications and (positive and negative) characteristics of users, (2) both content-dependent and content-independent access control to digital library objects, and (3) the varying granularity of authorization objects ranging from sets of library objects to specific portions of objects.

Workflow systems are gaining importance as an infrastructure for automating inter-organizational interactions, such as those in Electronic Commerce. Execution of inter-organiz-ational workflows may raise a number of security issues including those related to conflict-of-interest among competing organizations. Moreover, in such an environment, a centralized Workflow Management System is not desirable because: (i) it can be a performance bottleneck, and (ii) the systems are inherently distributed, heterogeneous and autonomous in nature. In this paper, we propose an approach to realize decentralized workflow execution, in which the workflow is divided into partitions called self-describing workflows, and handled by a light weight workflow management component, called workflow stub, located at each organizational agent. We argue that placing the task execution agents that belong to the same conflict-of-interest class in one self-describing workflow may lead to unfair, and in some cases, undesirable results, akin to being on the wrong side of the Chinese wall. We propose a Chinese wall security model for the decentralized workflow environment to resolve such problems, and a restrictive partitioning solution to enforce the proposed model.

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.

Digital libraries are concerned with the creation and management of information sources, the movement of information across global networks, and the effective use of this information by a wide range of users. A digital library is a vast collection of objects that are of multimedia nature, e.g. text, video, images, and audio. Users wishing to access the digital library objects may possess varying capabilities, preferences, domain expertise, and may use different information appliances. Facilitating access to complex multimedia digital library objects that suits the users' requirements is known as universal access. We present an object manifestation approach in which digital library objects automatically manifest themselves to cater to the users' capabilities and characteristics. We provide a formal framework, based on Petri nets, to represent the various components of the digital library objects, their modality and fidelity, and the playback synchronization relationships among them. We develop methodologies for object delivery without any deadtime under network delays.

Article Free Access Share on An authorization model for temporal data Authors: Avigdor Gal Department of MSIS, Rutgers University Department of MSIS, Rutgers UniversityView Profile , Vijayalakshmi Atluri Department of MSIS, Rutgers University Department of MSIS, Rutgers UniversityView Profile Authors Info & Claims CCS '00: Proceedings of the 7th ACM conference on Computer and Communications SecurityNovember 2000 Pages 144–153https://doi.org/10.1145/352600.352621Published:01 November 2000Publication History 24citation514DownloadsMetricsTotal Citations24Total Downloads514Last 12 Months9Last 6 weeks2 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 SiteeReaderPDF

Workflow management systems (WFMS) support the modeling and coordinated execution of processes within an organization. To coordinate the execution of the various activities (or tasks) in a workflow, task dependencies are specified among them. Often, the workflow application domains are such that the workflow is a long-running activity and the various tasks that constitute the workflow need to be executed by systems that are distributed and autonomous in nature, possibly owned by di#erent organizations. In such an environment, it is desirable to minimize the number of communications among the distributed sites and minimize the number of tasks that need to wait for the execution of tasks at other sites. In [3], Atluri et al. propose an approach that can automatically redesign a workflow in such a way that it minimizes the number of communications and interference between sites. This approach performs a semantic categorization of task dependencies, and proposes to use for each categoriza...

Workflow Management Systems (WFMS) are being widely used today by organizations to coordinate the execution of various applications representing their day-to-day tasks. To ensure that these tasks are executed by authorized users or processes (subject

Workflow management systems (WFMS) support the modeling and coordinated execution of processes within an organization. To coordinate the execution of the various activities (or tasks) in a workflow, task dependencies are specified among them. As adva

In recent years, workflow management systems (WFMSs) have gained popularity in both research and commercial sectors. WFMSs are used to coordinate and streamline business processes. Very large WFMSs are often used in organizations with users in the range of several thousands and process instances in the range of tens and thousands. To simplify the complexity of security administration, it is common practice in many businesses to allocate a role for each activity in the process and then assign one or more users to each role—granting an authorization to roles rather than to users. Typically, security policies are expressed as constraints (or rules) on users and roles; separation of duties is a well-known constraint. Unfortunately, current role-based access control models are not adequate to model such constraints. To address this issue we (1) present a language to express both static and dynamic authorization constraints as clauses in a logic program; (2) provide formal notions of constraint consistency; and (3) propose algorithms to check the consistency of constraints and assign users and roles to tasks that constitute the workflow in such a way that no constraints are violated.

Workflow management systems (WFMS) support the modeling and coordinated execution of processes within an organization. As advances in workflow management take place, they are also required to support security. This paper makes two major contributions to the area of workflow management. First, it sh ows how both mandatory and discretionary security can be incorporated into WFMS. Second, it provides a formal framework, based on Petri nets (PNs), for modeling workflows. Such a theoretical model is necessary for a standard conceptual representation as well as for analyzing the workflows. This paper first presents a Petri Net based model, called color timed Petri net (CTPN), which is capable of modeling the attributes of both multilevel and discretionary security. With respect to the issue of mandatory security, this paper proposes a multilevel secure workflow transaction model and identifies the task dependencies in a workflow that cannot be enforced in order to meet multilevel security constraints. It shows how CTPN can be used to represent various types of task dependencies and shows how the task dependencies violating security can be automatically detected and prevented by building a secure Petri net (SPN) from CTPN. With respect to the issue of discretionary access control, this paper proposes a workflow authorization model (WAM) that is capable of specifying authorizations in such a way that subjects gain access to required objects only during the execution of the task, thus synchronizing the authorization flow with the workflow. To achieve this synchronization, an authorization template (AT) is associated with each task that allows appropriate authorizations to be granted only when the task starts and to be revoked when the task finishes. This paper also presents how this synchronization can be implemented using CTPN. We argue that Petri net is a suitable tool for modeling workflows because of its rich set of analysis techniques. Properties such as safety of workflows (i.e., whether a workflow terminates in an acceptable state) and safety of WAM can be tested using the already available analysis techniques of PNs.

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.

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.

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

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

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.

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