Data collaborations allow users to draw upon diverse resources to solve complex problems. While collaborations enable a greater ability to manipulate data and services, they also create new security vulnerabilities. Collaboration participants need methods to detect suspicious behaviors (potentially

Many applications, including provenance and some analyses of social networks, require path-based queries over graphstructured data. When these graphs contain sensitive information, paths may be broken, resulting in uninformative query results. This paper presents innovative techniques that give users more informative graph query results; the techniques leverage a common industry practice of providing what we call surrogates: alternate, less sensitive versions of nodes and edges releasable to a broader community. We describe techniques for interposing surrogate nodes and edges to protect sensitive graph components, while maximizing graph connectivity and giving users as much information as possible. In this work, we formalize the problem of creating a protected account G' of a graph G. We provide a utility measure to compare the informativeness of alternate protected accounts and an opacity measure for protected accounts, which indicates the likelihood that an attacker can recreate the topology of the original graph from the protected account. We provide an algorithm to create a maximally useful protected account of a sensitive graph, and show through evaluation with the PLUS prototype that using surrogates and protected accounts adds value for the user, with no significant impact on the time required to generate results for graph queries.

Whereas strategies for discovering content on the surface web are commonplace, similar strategies for the private web are nonexistent. In this paper we first establish a formal framework for advertising the existence of private web resources that subsumes many existing summarization strategies based on succinct statistical summaries (which we call digests). We then investigate the tradeoff between the data owners' desires to minimize disclosure and the searchers' desires to minimize query error, demonstrating that our techniques are superior to k-anonymity. Finally, we show that our techniques for summarization do, in fact, make it possible to discover private web data resources.

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

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

One of the most important responsibilities of a database management system (DBMS) is maintaining the integrity of data. Traditional database integrity mechanisms have evolved in DBMSs to fulfill this need, including transaction management to maintain

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

C<,retoness conditicms arc given which describe some nf tile pt'tq~crlie~ c×hibiLed by Ilighly aw~itable distributed database systems sttch a:; the 511,'x.RI) (Systcnl I~n' l lighly Available Replicated Data) ,¢.ystem cuurcntlv be~hg developed at Comptller Corporation of /~l]lOi'iC;i.This svslcm allows a da~d~ase application to contilme OpClatlt:~l ill tile lace o1" communicatiun faih.llCS,incheding fietwork pa0"tidons.A penalty is paid tbr thir; c×tz'a availability: the usual corrc,:tncss conditi,n,~; serializability of tr:msactions and preservation of iritcgrily c,n.~traims, ,:re not guaranteed.I Iowevcr, it is still possihle to make intcrestin~g claims about the beh,vior e,f the system.The kinds of claims whicli can be 9roved include bom~ds on tile costs oF violatior, of integrity cofistraints, and Ihirness guma,tces.In comrast to serializ~bility:s all-or-m~thing character, this work has a "continuous" flavor:small changes in available inform~itiou lead a) small perturbations in corrcctuess conditk)ns."['l:.iswork is novel, because there has been very little previous success in'stating .inlcresti'ngproperties whk:h are guaranteed by nonscrializable systems.

An overview is presented of an approach to distributed database design which emphasizes high availability in the face of network partitions and other communication failures. This approach is appropriate for applications which require continued operation and can tolerate some loss of integrity of the data. Each site presents its users and application programs with the best possible view of the data which it can, based on those updates which it has received so far. Mutual consistency of replicated copies of data is ensured by using time stamps to establish a known total ordering on all updates issued, and by a mechanism which ensures the same final result regardless of the order in which a site actually receives these updates. A mechanism is proposed, based on alerters and triggers, by which applications can deal with exception conditions which may arise as a consequence of the high-availability architecture. A prototype system which demonstrates this approach is near completion.

Semantic integrity assertions are predicates that define consistent states. A database system enforces assertions by ensuring that consistency is maintained as the database is updated.Most research on the efficient enforcement of assertions has concentrated on assertion simplification algorithms --- algorithms that produce simplified assertions that can be evaluated before the update is executed. This paper describes a strategy for further improving the efficiency of assertion enforcement.We develop an efficient algorithm for evaluating an assertion produced by an assertion simplification algorithm. We characterize a class of assertions that can be evaluated using a simple two-step procedure. The first step defines and evaluates simple selection queries on each relation. The second step applies set emptiness tests to the results of these selections. We also show how these techniques may be used to improve the efficiency of evaluating assertions outside our class.