Fluent Essays

Article attached below. Article Review should include: - a summary of the article's core contents, arguments, conclusions ( 3 pages) - critical assessment & comment based on your own research on the topic (1 Page) For example, new developments (technologies, theories) on the topic Integrity Mechanisms in Database Management Syst ems 617 Essay 27 Integrity Mechanisms in Database Management Systems Ravi S. Sandhu and Sushil Jajodia Information integrity means different things to different people, and will probably continue to do so for some time. The 1989 NIST workshop, which set out to establish a consensus definition, instead arrived at th e following conclusion [NIST89, page 2.6]: The most important conclusion to be drawn from this compila- tion of papers and working group reports: don’t draw too many conclusions about the appropriate definition for data integrity just yet.... In the mean time, papers addressing integrity issues should present or reference a definition of integrity applicable to that paper. So the first order of business is to define integrity. Our approach to this question is pragmatic and utilitarian. The objective is to settle on a definition within which we can achieve practically useful results, rather than search for some absolute and airtight formulation. We define integrity1as being concerned with the improper modification of information (much as confidentiality is concerned with improper dis- closure). We understand modification to include insertion of new infor- mation and deletion of existing information, as well as changes to existing information. 1Our definition of integrity is considerably broader than the traditional use of this term in the database literature. For instance, Date [DATE86] says, “Security refers to the protection of data against unauthorized disclosure, alteration, or destruction; integrity refers to the accuracy or validity of data.” The consensus view among security researchers is that integrity is one component of security and accuracy/validity is one component of integrity [FERN81, NIST89]. 618 Information Security The reader has probably seen similar definitions using “unauthorized” instead of “improper.” Our use of the latter term is quite deliberate and significant. First, it acknowledges that security breaches can and do oc- cur without authorization violations — that is, authorization is only on e piece of the solution. Second, it adheres to the well-established and useful notion that information security has three components: integrity, confidentiality, and availability. We see no need to discard this standard viewpoint in the absence of some compelling demonstration of a supe- rior one. Finally, our definition brings to the front the very important question: What do we mean by improper? It is obvious that this ques- tion intrinsically cannot have a universal answer. So it is futile to try to answer it outside of a given context. We are specifically interested in information systems used to control and account for an organization’s assets. In such systems, the primary goal is prevention of fraud and errors. The meaning of improper modifi- cation in this context has been given by Clark and Wilson [CLAR87] as follows: No user of the system, even if authorized, may be permitted to modify data items in such a way that assets or accounting re- cords of the company are lost or corrupted. Note their express qualification: “even if authorized.” The word “com- pany” in this quotation reveals the authors’ commercial bias but, as they have clarified [CLAR89a], these concepts apply equally well to any information system that controls assets — be it in the military, govern- ment, or commercial sectors. Our goal in this essay is to answer the following question: What mechanisms are required in a general-purpose multiuser DBMS to help achieve the integrity objectives of information systems? There are many compelling reasons to focus on DBMSs for this purpose. The most im- portant has been succinctly stated by Burns [BURN89] as follows: A database management system (DBMS) provides the appropriate level of abstraction for the implementation of integrity controls as presented in the Clark and Wilson paper [CLAR87].... It is clear that the domain of applicability of the Clark and Wilson model is not an operating system or a network or even an application sys- tem, it is fundamentally a DBMS. This is particularly true when we focus on mechanisms. Moreover, DBMSs have the wonderful ability to express and manipulate complex relationships. This comes in very handy when dealing with sophisti- cated integrity policies. Integrity Mechanisms in Database Management Syst ems 619 The operating system must clearly provide some core integrity and se- curity mechanisms. In terms of the Orange Book [DOD85], one would need at least a B1 system to enforce encapsulation of the DBMS — that is, to ensure that all manipulation of the database can only be through the DBMS. The question of what minimal features are required in th e operating system is important, but outside the scope of this essay. For now, let us assume that operating systems with the requisite features are available. The bulk of integrity mechanisms belong in the DBMS. Integrity poli- cies are intrinsically application specific, and the operating system sim- ply cannot provide the means to state application-specific concerns. On e might then argue: Why not put all the mechanism in the applica- tion code? There are several persuasive reasons not to do this. First, it is not very conducive to reuse of common mechanisms. Second, any as- surance that integrity mechanisms interspersed within application code will be correct or even comprehensible is rather dubious. Third, th e whole point of a database is to support multiple applications. A particu- lar application may well be in a position to handle all its integrity re- quirements. Yet it is only the DBMS which can prevent other applications from corrupting the database. The rest of the essay is organized as follows. First we discuss princi- ples for achieving integrity in information systems. Then we describe the mechanisms required in a DBMS to support these high-level principles. In some of the more detailed considerations, we will limit ourselves spe- cifically to relational DBMSs. As we will see, traditional DBMS mecha- nisms provide the foundations for this purpose, but by themselves do not go far enough. Integrity principles We begin by describing basic principles for achieving information integ- rity. These can be viewed as high-level objectives that are made more concrete when specific mechanisms are proposed to support them. In other words, these principles lay down broad goals without specifying how to achieve them. We will subsequently map these principles to DBMS mechanisms. We emphasize that the principles themselves are independent of the DBMS context. They apply equally well to any in- formation system, be it a manual paper-based system, a centralized batch system, an interactive and highly distributed system, and so on. The nine integrity principles enumerated below are abstracted from the Clark and Wilson papers [CLAR87, CLAR89a, CLAR89b], the NIS T workshops [NIST87, NIST89], and the broader security and database lit- 620 Information Security erature.2These principles express what needs to be done rather than how it is going to be accomplished (the latter question is addressed in the next section): 1. Well-formed transactions. Clark and Wilson [CLAR87] have defined this principle as follows: “The concept of the well-formed transac- tion is that a user should not manipulate data arbitrarily, but only in constrained ways that preserve or ensure the integrity of th e data.” This principle has also been called constrained change [CLAR89b] — that is, data can be modified only by well-formed transactions rather than by arbitrary procedures. Moreover, th e well-formed transactions are known (“certified”) to be individually correct with some (mostly qualitative) degree of assurance. 2. Authenticated users. This principle stipulates that modifications should be carried out only by users whose identities have been authenticated to be appropriate for the task. 3. Least privilege. The notion of least privilege was one of the earli- est to emerge in security research. It has classically been stated in terms of processes (executing programs) [SALT75]: A process should have exactly those privileges needed to accomplish its as- signed task, and none extra. The principle applies equally well to users, except that it is more difficult to precisely delimit the scope of a user’s “task.” A process is typically created to accomplish some very specific task and terminates on completion. A user, on th e other hand, is a relatively long-lived entity and will be involved in varied activities during his life span. His authorized privileges will therefore exceed those strictly required at any given instant. In the realm of confidentiality, least privilege is often called need-to- know. In the integrity context, it is appropriately called need-to-do. Another appropriate term for this principle is least temptation — that is, do not tempt people to commit fraud by giving them greater power than they need. 4. Separation of duties. Separation of duties is a time-honored prin- ciple for prevention of fraud and errors, going back to the very be- ginning of commerce. Simply stated, no single individual should be in a position to misappropriate assets on his own. Operationally, this means that a chain of events that affects the balance of as- sets must require different individuals to be involved at key points, so that without their collusion the overall chain cannot take effect. 2The literature is too numerous to cite works individually. For those unfamil- iar with the “older” literature, there are some useful starting points [DENN79, FERN81, GRAY78, LIND76, SALT75]. Integrity Mechanisms in Database Management Syst ems 621 5. Reconstruction of events. This principle seeks to deter improper behavior by threatening its discovery. It is a necessary adjunct to least privilege for two reasons. First, least privilege, even taken to its theoretical limit, will leave some scope for fraud. Second, a zealous application of least privilege is not a terribly efficient way to run an organization. It conveys an impression of an enterprise enmeshed in red tape.3 So practically, users must be granted more privileges than are strictly required. We therefore should be able to accurately reconstruct essential elements of a system’s history, so as to detect misuse of privileges. 6. Delegation of authority. This principle fills in a piece missing from the Clark and Wilson papers and much of the discussion they have generated.4It concerns the critical question of how privileges are acquired and distributed in an organization. Clearly, the pro- cedures to do so must reflect the structure of the organization and allow for effective devolution of authority. Individual manag- ers should have maximum flexibility regarding information re- sources within their domains, tempered by constraints imposed by their superiors. Without this flexibility at the end-user level, th e authorization will most likely be inappropriate to the actual needs. This can only result in security being perceived as a drag on productivity and something to be bypassed whenever possible. 7. Reality checks. This principle has been well motivated by Clark and Wilson [CLAR89b] as follows: “A cross-check with the external reality is a central part of integrity control. ...integrity is meaning- ful only in terms of the relation of the data to the external world.” Or in more concrete terms: “If an internal inventory record does not correctly reflect the number of items in stock, it makes little difference if the value of the recorded inventory has been re- flected correctly in the company balance sheet.” 8. Continuity of operation. This principle states that system opera- tions should be maintained to some appropriate degree in th e face of potentially devastating events beyond the organization’s 3This comment is made in the context of users rather than processes (trans- actions). Least privilege with respect to processes is more of an internal issue within the computer system, and its zealous application is most desirable (modulo the performance and cost penalties it imposes). 4The closest concept that Clark and Wilson have to this principle is their Rule E4, which they summarize as follows [CLAR87, Figure 1]: “Authorization lists changed only by the security officer.” This notion of a central security offi- cer as an authorization czar is inappropriate and unworkable. Rational security policies can be put in place only if appropriate authority is vested in end users. 622 Information Security control. This catchall description is intended to include natural disasters, power outages, disk crashes, and the like.5 9. Ease of safe use.6 In a nutshell, this principle requires that th e easiest way to operate a system should also be the safest. Ther e is ample evidence that security measures are all too often incor- rectly applied or simply bypassed by the system managers. This happens due to one or a combination of the following: (1) poorly designed defaults (such as indefinite retention of vendor-supplied passwords for privileged accounts), (2) awkward and cumbersome interfaces (such as requiring many keystrokes to effect simple changes in authorization), (3) lack of tools for authorization re- view, and (4) mismatched policy and mechanism (“...to the extent that the user’s mental image of his protection goals matches th e mechanism he must use, mistakes will be minimized” [SALT75]). It is inevitable that these principles are fuzzy, abstract, and high level. In developing an organization’s security policy, one would elaborate on each of these principles and make precise the meaning of terms such as “appropriate” and “proper.” How to do so systematically is perhaps th e most important question in successful application of these principles. In other words, how does one articulate a comprehensive policy based on these high-level objectives? This question is beyond the scope of this essay. Our present focus is on this question: How do these principles translate into concrete mechanisms in a DBMS? The goals encompassed by these principles may appear overwhelming. After all, in the extreme these principles amount to solving the total system correctness problem, which we know is well beyond the state of the art. Fortunately, in our context, the degree to which one would seek to enforce these objectives and the assurance of this enforcement are matters of risk management and cost-benefit analysis. Laying out these principles explicitly does give us the following major benefits: • The overall problem is partitioned into smaller components for which solutions can be developed independently of each other (that is, divide and conquer). • The principles suggest common mechanisms that belong in th e DBMS and can be reused across multiple applications. • The principles provide a set against which the mechanisms of specific DBMSs can be evaluated (in an informal sense). • The principles similarly provide a set on the basis of which the re- quirements of specific information systems can be articulated. 5One might argue that we are stepping into the scope of availability here. If so, so be it. 6Thanks to Stanley Kurzban and William Murray for coining this term. Integrity Mechanisms in Database Management Syst ems 623 • Last, but not least, the principles invite criticism from the security community, particularly regarding what may have been left out. Integrity mechanisms In this section, we consider DBMS mechanisms to facilitate applica- tion of the principles defined in the previous section. The principles have been applied in practice [MURR87a, WIMB71], but with most of th e mechanisms built into application code. Providing these mechanisms in the DBMS is a prerequisite for their widespread use. Our mapping of principles to mechanisms is summarized in Table 1. Some of these mechanisms are available in commercial products. Oth- ers are well established in the database literature. There are also some newer, recently proposed mechanisms, for example, transaction controls for separation of duties [SAND88b], the temporal model for audit data [JAJO90g], and propagation constraints for dynamic authorization [SAND88a, SAND89]. Finally, there are places where existing mecha- nisms and proposals need to be extended in novel ways. Overall, th e required mechanisms are quite practical and well within the reach of today’s technology. Table 1. Summary. Integrity Principle DB M S Mechanisms Well-formed transactions Encapsulated updates Atomic transactions Consistency constraints Continuity of operation Redundancy Recovery Authenticated users Authentication Least privilege Fine-grained access control Separation of duties Transaction controls Layered updates Reconstruction of events Audit trail Delegation of authority Dynamic authorization Propagation constraints Reality checks Consistent snapshots Ease of safe use Fail-safe defaults 624 Information Security Integrity Principle DB M S Mechanisms Human factors W ell- f ormed transactions. The concept of a well-formed transaction corresponds very well to the standard DBMS concept of a transaction [GRAY78, GRAY86]. A transaction is defined as a sequence of primitive actions that satisfies the following properties: 1. Failure atomicity. Either all or none of the updates of a transaction take effect. We understand update to mean modification; that is, it includes insertion of new data, deletion of existing data, and changes to existing data. 2. Serializability. The net effect of executing a set of transactions is equivalent to executing them in some sequential order, even though they may actually be executed concurrently (that is, their actions are interleaved or simultaneous). 3. Progress. Every transaction will eventually complete; that is, there is no indefinite blocking due to deadlock and no indefinite re- starts due to livelock. 4. Correct state transform. Each transaction if run by itself in isola- tion and given a consistent state to begin with will leave the da- tabase in a consistent state. We will elaborate on these properties in a moment. First let us note the basic requirement that the DBMS must ensure that updates are restricted to transactions. Clearly, if users are allowed to bypass transac- tions and directly manipulate relations in a database, we have no foun- dation to build upon. We represent this requirement with the diagram in Figure 1 — updates are encapsulated within transactions. At this point it is worth recalling that the database itself must be encapsulated within the DBMS by the operating system. Users Transactions Database Figure 1. Encapsulated updates. Integrity Mechanisms in Database Management Syst ems 625 It is clear that the set of database transactions is itself going to change during the system life cycle. Now the same nine principles of the previ- ous section apply with respect to maintaining the integrity of the trans- actions. In particular, transactions should be installed, modified, and supplanted only by the use of well-formed “transaction-maintenance transactions.” One can apply this argument once again to say that th e transaction-maintenance transactions themselves need to be main- tained by another set of transactions, and so on indefinitely. We believe there is little to be gained by having more than two steps in this poten- tially unbounded sequence of transaction-maintenance transactions. The rate of change in the transaction set will be significantly slower than the rate of change in the database proper. Going one step further, the rate of change in the transaction-maintenance transactions will be yet slower to the point where, for all practical purposes, these can be viewed as static over the life span of typical systems. With this perspec- tive, the database administrator is responsible for installing and main- taining transaction-maintenance transactions, which in turn maintain actual database transactions. We now return to considering the four properties of DBMS transac- tions enumerated earlier. The first three properties — failure atomicity, serializability, and progress — can be achieved in a purely “syntactic” manner — that is, completely independent of the application. These three requirements for a transaction are recognized in the database lit- erature as appropriate for the DBMS to implement. Mechanisms to achieve these objectives have been extensively researched in the last 15 years or so, and our understanding of this area can certainly be de- scribed as mature. The basic mechanisms — two-phase locking, time stamps, multiversion databases, two-phase commit, undo-redo logs, shadow pages, deadlock detection and prevention — have been known for a long time and have made their way into numerous products. In de- veloping integrity guidelines and/or evaluation criteria, one might con- sider some progressive measure of the extent to which a particular DBMS meets these objectives. For instance, with failure atomicity, is there a guarantee that we will know which of the two possibilities oc- curred? Similarly, with serializability, does the DBMS enforce th e concurrency control protocol or does it rely on transactions to execut e explicit commands for this purpose? And, with the issue of progress, do we have a probabilistic or absolute guarantee? Such questions must be systematically addressed. The fourth property, correct state transforms, is the ultimate bottle- neck in realizing well-formed transactions. It is also an objective that cannot be achieved without considering the semantics of the applica- tion. The correctness issue is, of course, undecidable in general. In practice, we can assure correctness only to some limited degree of confi- dence by a mix of software engineering techniques such as formal verifi- 626 Information Security cation, testing, quality assurance, and so on. Responsibility for imple- menting transactions as correct state transforms has traditionally been assigned to the application programmer. Even in theory, DBMS mecha- nisms can never fully take over this responsibility. DBMS mechanisms can help in assuring the correctness of a state by enforcing consistency constraints on the data. Consistency constraints are also often called integrity constraints or integrity rules in the data- base literature. Since we are using integrity in a wider sense, we prefer the term consistency constraint. The relational data model in particular imposes two consistency con- straints [CODD79, DATE86]: • Entity integrity stipulates that attributes in the primary key of a base relation cannot have null values. This amounts to requiring that each entity represented in the database must be uniquely identifiable. • Referential integrity is concerned with references from one entity to another. A foreign key is a set of attributes in one relation whose values are required to match those of the primary key of some specific relation. Referential integrity requires that either a foreign key be all null7or a matching tuple exist in the latter rela- tion. This amounts to ruling out dangling references to nonexist- ent entities. Entity integrity is easily enforced. Referential integrity, on the other hand, requires more effort and has seen limited support in commercial products. The precise manner in which to achieve it is also very de- pendent on the semantics of the application. This is particularly so when the referenced tuple is deleted. There are several choices: 1. prohibit this delete operation, 2. delete the referencing tuple (with a possibility of further cascading deletes), or 3. set the foreign key attributes in the referencing tuple to null. There are proposals for extending SQL so that these choices can be specified for each foreign key. The relational model in addition encourages the use of domain con- straints, whereby the values in a particular attribute (column) are con- strained to come from some given set. These constraints are particularly easy to state and enforce, at least so long as the domains are defined in terms of primitive types such as integers, decimal numbers, and charac- 7Often the notion of a null foreign key is semantically incorrect. In such cases, an additional consistency constraint can disallow null values. Integrity Mechanisms in Database Management Syst ems 627 ter strings. A variety of dependency constraints [DATE86] that constrain the tuples in a given relation have been extensively studied in the da- tabase literature. In the limit, a consistency constraint can be viewed as an arbitrary predicate that all correct states of the database must satisfy. The predi- cate may involve any number of relations. Although this concept is theoretically appealing and flexible in its expressive power, in practice the overhead in checking the predicates for every transaction has been prohibitive. As a result, relational DBMSs typically confine their en- forcement of consistency constraints to domain constraints and entity integrity. Continuity of operation. The problem of maintaining continuity of operation in the face of natural disasters, hardware failures, and other disruptive events has received considerable attention in both theory and practice [GRAY78]. The basic technique to deal with such situa- tions is redundancy in various forms. Recovery mechanisms in DBMSs must also ensure that we arrive at a consistent state. In many respects, these mechanisms are “syntactic” in the sense of being application in- dependent, much as mechanisms for the first three properties pre- sented in the section “Well-formed transactions” were. Authenticated users. Authentication is primarily the responsibility of the operating system. If the operating system is lacking in its authenti- cation mechanism, it would be very difficult to ensure the integrity of the DBMS itself. The integrity of the database would thereby be that much more suspect. It therefore makes sense not to duplicate authenti- cation mechanisms in the DBMS. Authentication underlies some of the other principles, particularly least privilege, separation of duties, reconstruction of events, and dele- gation of authority. In all of these, the end objective can be achieved to the fullest extent only if authentication is possible at the level of indi- vidual users. Least privilege. The principle of least privilege translates into a re- quirement for fine-grained access control. Earlier we noted that least privilege must be tempered with practicality in avoiding excessive red tape. Nevertheless, a high-end DBMS should provide for access control at very fine granularity, leaving it to the database designers to apply these controls as they see fit. It is clear from the Clark and Wilson papers, if not evident from earlier work, that modification of data must be controlled in terms of transac- tions rather than blanket permission to write. We have already put forth the concept of encapsulated updates for this purpose. In terms of th e 628 Information Security relational model, it is not immediately obvious at what granularity of data this should be enforced. To control read access, DBMSs have used mechanisms based on views (as in System R) or query modification (as in INGRES). These mecha- nisms are extremely flexible and can be as fine grained as desired. How- ever, neither one provides the same potential for flexible control of updates. The fundamental reason for this is our theoretical inability to translate updates on views unambiguously into updates of base rela- tions. As a result, authorization to control updates is often less sophis- ticated than authorization for read access. In relational systems, it is natural for obvious reasons to represent th e access matrix by one or more relations [SELI80]. At a coarse level, w e might control access by tuples of the following form: user, transaction, relation This means that the specified user can execute the specified transac- tion on the specified relation. Tuples of the form shown below would give greater selectivity: user, transaction, relation, attribute This would allow us to control the execution of transactions such as “give everyone a 5 percent raise,” without giving the same transaction permission to change employee addresses. The following authorization tuple accomplishes this: Joe, Give-5 % -raise, Employees, Salary A transaction that gives a raise to a specific employee needs a further dimension of authorization to specify which employee it pertains to. Thus, if Joe is authorized to give a 5 percent raise to John, the authori- zation tuple would look as follows: Joe, Give-5 % …