Lattice-based security classification system and method6922696Abstract Despite advances in recent years in the area of mandatory access control in database systems, today's information repositories remain vulnerable to inference and data association attacks that can result in serious information leakage. Without support for coping against these attacks, sensitive information can be put at risk because of release of other (less sensitive) related information. The ability to protect information disclosure against such improper leakage would be of great benefit to governmental, public, and private institutions, which are, today more than ever, required to make portions of their data available for external release. In accordance with the invention, a solution to the problem of classifying information by enforcing explicit data classification as well as inference and association constraints is provided. We formulate the problem of determining a classification that ensures satisfaction of the constraints, while at the same time guaranteeing that information will not be unnecessarily overclassified. Claims 1. A method for assigning a partially ordered set of classification levels to a set of data attributes, comprising: Description BACKGROUND OF THE INVENTION
The constraints in all the four categories express restrictions on the visibility of information and are termed lower bound constraints, defined formally as follows. Definition 2.1 (Lower Bound Constraint) Let A be a set of attributes and L=(L,) be a security lattice. A lower bound constraint over A and L is an expression of the form lub{λ(A1), . . . , λ(An)} X, where n>0, AεA, i=1, . . . , n, and X is either a security level lεL or is of the form λ(A), with AεA. If n=1, the expression may be abbreviated as λ(Al) X. Note that all constraints allowed by this definition have the form (as opposed to), with security levels on the right hand side only. That is, they specify a lower bound on the classification assigned to attributes (which can be upgraded as required by other constraints). For instance, a constraint requiring illness to be classified at level Research will be stated as λ(illness) Research, implying that illness must be classified at least Research. This interpretation is a property of the problem under consideration, where data classification may need to be upgraded to combat inference channels and to solve association constraints. Note that assigning to an attribute a classification lower than that required by lower bound constraints would, directly or indirectly, leak information to subjects not cleared for it. Thus, the main function of lower bound constraints is to capture the requirements on classification assignments that will prevent improper downward information flow. Although lower bound constraints are sufficient for expressing the prevention of downward information flow, it can also be useful to establish maximum levels that should be assigned to attributes. Such maximum levels can be specified by upper bound constraints, defined as follows. Upper Bound Constraints Definition 2.2 (Upper Bound Constraint) Let A be a set of attributes and L=(L,) be a security lattice. An upper bound constraint over A and L is an expression of the form l λ(A), where 1εL is a security level and AεA is an attribute. Upper bound constraints have two main uses. One is the specification of visibility requirements, since their satisfaction ensures that the attribute will be visible to all subjects with level dominated by the specified upper bound. For example, if we wish to guarantee that names of patients in a hospital are always accessible to the administrative staff, we might impose the constraint Admin λ(patient) to prevent the classification of patient from being raised above Admin. In fact, this constraint together with the lower bound constraint λ(Patient) Admin effectively forces the classification of patient to be exactly Admin. The other main use of upper bound constraints is the modeling of subjects' existing or prior knowledge of certain information stored in the database. If such knowledge is not accounted for in the classification of the database, it is possible to produce classifications that provide a false sense of security. For example, suppose that providers know the illnesses of patients in a hospital. This knowledge could be captured by the constraint Provider λ(illness). Without this constraint, it might happen that inference or association constraints produce a higher (or incomparable) security classification, say HMO, for illness. Thus, although patient appears to be information classified at the HMO level, it really is not, since providers already know the illnesses of patients. Explicit upper bound constraints can prevent the assignment of such misleading classifications. The lower and upper bound constraints can be represented abstractly as pairs (lhs, rhs), where lhs is the security level or set of attributes appearing on the left-hand side of the constraint, and rhs is the attribute or security level appearing on the right-hand side of the constraint. Among lower bound constraints we refer to constraints whose left-hand side is a singleton as simple constraints, and to constraints with multiple elements in the left-hand side as complex constraints. Although the definitions do not permit lub expressions on the right-hand sides of constraints, this does not limit their expressiveness, since a constraint of the form X lub({λ(A1), . . . , (An)}) is equivalent to a set of constraints (X λ(A1), . . . ,X λ(A1)}. In the remainder of the paper we refer to arbitrary sets of lower and upper bounds constraints simply as classfication constraints and distinguish between lower and upper bound constraints when necessary. Any set of classification constraints can be viewed as a directed graph, which we call the constraint graph, not necessarily connected, containing a node for each attribute AεA and security level lεL. Each constraint (lhs, rhs), with lhs={Al, . . . , An}, is represented by a directed edge from node A1, if n=1, or hypernode containing A1, . . . , n, if n>1, to node rhs. Now, an example of a classification graph will be briefly described. FIG. 2 illustrates an example of a classification constraint graph 60, where security levels are taken from the security lattice 50 shown in FIG. 1c. In the graph, circle nodes 62 represent attributes, square nodes 64 represent security levels, and dashed ellipses 66 represent hypernodes. Note that the upper bound constraints 68 are edges from level nodes to attribute nodes. All other edges 70 represent lower bound constraints. The constraints in this example refer to patient information in a hospital database and reflect the following scenario. The two association constraints require protection of each of the patient's illness and bills information. In particular, the association between patients and their illnesses (e.g., the knowledge of which patient has which illness) can be known only to subjects at security level Clinical or above (as shown by the dashed ellipses with the arrow pointing towards the Clinical level), and the association between patients and their bills can be known only to subjects at level Admin or above (as shown by the shaded ellipses with the arrow towards the Admin level). Other lower bound constraints reflect (precise or imprecise) inferences that can be drawn from the data and that must therefore be reflected in the classification. For instance, by knowing the doctor who is caring for a patient, a subject can deduce the patient's illness within the specific set of illnesses falling in the doctor's specialty. Hence, the classification of attribute doctor must dominate the classification of attribute illness as shown by the arrow between the attributes. Analogously, the insurance plan together with the health care division allows inference on the doctor. Hence, subjects should have visibility on both the division and plan only if they have visibility on doctor. In terms of the classifications, the least upper bound of the classification of plan and division must dominate the classification of doctor. The motivation behind the other inference constraints appearing in the figure are analogous. There are also several basic constraints that require the classification of certain attributes to dominate specific levels. For instance, prescriptions can be released only to subjects at the level Clinical or above. In addition, there are several upper bound constraints reflecting the fact that specific information cannot be classified above certain levels because of required access or to account for information already known, as discussed. For instance, the classification of patient must be dominated by Admin and the classification of illness must be dominated by Provider. In the remainder of this description, we refer to the constraints and to their graphical representation interchangeably, and we often refer to a constraint (lhs, rhs) as the existence of an edge between lhs and rhs. Among lower bound constraints, we identify two subclasses of constraints. In particular, lower bound constraints whose graph representation is acyclic (i. e., is a DAG) are called acyclic constraints, while those involved in a cycle, including cycles through hypernodes, are called cyclic constraints. A cycle involving only simple constraints is called a simple cycle. For example, considering only the lower bound constraints in FIG. 2, constraints (illness, division), ({division, plan}, doctor), and (doctor, illness) are cyclic and constraints (exam, treatment), (treatment, visit), and (visit, exam) constitute a simple cycle while all other lower bound constraints are acyclic. Now, the concept of a minimal classification in accordance with the invention will be described. Minimal Classification Given a set of classification constraints, the objective of a minimal classification is to produce a classification λ: A L, which is an assignment of security levels in L to objects (attributes)in A, that satisfies the constraints. A classification λ satisfies a set C of constraints, denoted λ C, if for each constraint, the expression obtained by substituting every λ(A) with its corresponding level holds in the lattice ordering. In general, there may exist many classifications that satisfy a set of constraints. However, not all classifications are equally good. For instance, the mapping λ: A {T}classifying all data at the highest possible level satisfies any set of lower bound constraints. Such a strong classification is clearly undesirable unless required by the classification constraints, as it results in unnecessary information loss (by preventing release of information that could be safely released). Although the notion of information loss is difficult to make both sufficiently general and precise, it is clear that a first requirement in minimizing information loss is to prevent overclassification of data That is, the set of attributes should not be assigned security levels higher than necessary to satisfy the classification constraints. A classification mapping that meets this requirement is said to be minimal. To be more precise, we first extend the notion of dominance to classification assignments. For a given set A of attributes, security lattice (L,), and mappings λ1,: A L and λ2: A L, we say that λ1λ2 if AεA: λ1(A) λ2(A). The notion of minimal classification can now be defined as follows. Definition 2.3 (Minimal Classification) Given a set A of attributes, security lattice L=(L,) and a set C of classification constraints over A and L, a classification λ: A L is minimal with respect to C iff (1)λ C; and (2) for all λ′: A L such that λ′ C, λλ′λ=λ′. In other words, a minimal classification is one that both satisfies the constraints and is (pointwise) minimal in the lattice. Note that a minimal classification is not necessarily unique. The main problem now is to compute a minimal classification from a given set of classification constraints. Problem 1 (MIN-LATTICE ASSIGNMENT) Given a set A of attributes to be classified, a security lattice L=(L,), and a set C of classification constraints over A and L, determine a classification assignment λ: A L that is minimal with respect to C In general, a set of constraints may have more than one minimal solution. The following sections describe an approach for efficiently computing one such minimal solution and a (low-order) polynomial-time algorithm that implements the approach. Now, the security classification system in accordance with the invention will be described in more detail before describing the method and algorithms is more detail. FIG. 3 is a diagram illustrating a security classification system 80 in accordance with the invention. The security classification system may include one or more users 82 (User #1 . . . User #N) who are connecting to a central computer 84, such as a server, over a computer network 86, such as a local area network, a wide area network, the World Wide Web or the like. Each user may be using a typical personal computer or other type of computer in order to attempt to retrieve one or more pieces of data from a database 88 connected to the computer 84. The retrieval of the data from the database is controlled by a security system 90 in accordance with the invention that regulates what data can be accessed by what people. In a preferred embodiment, the security system is one or more software modules stored in a memory 92 of the computer 84 and executed by the central processing unit (CPU) 94 of the computer. The security system in accordance with the invention is executed by the CPU in order to determine classifications for the data in the database so that confidential data cannot be subjected to an association or an inference attack. To accomplish this, the security module 90 may include one or more sub-modules that implement some of the functionality of the security module. The one or more sub-modules may include a upper bound determiner module (UB) 96 that enforces any upper bound constraints to determine a firm maximum security level for each attribute and a lower bound determiner module (LB) and minimum classification module (Min) 98, 100 that determines the lower bound contestants and determines the minimal classification based on the lower bound contestants. The functions of each of these modules will be described in more detail. A basic requirement that must be satisfied to ensure the existence of a classification λ is that the set of classification constraints provided as input by complete and consistent. A set of classification constraints is complete if it defines a classification for each attribute in the database. It is consistent if there exists an assignment of levels to the attributes, that is, a definition of λ, that simultaneously satisfies all classification constraints. Completeness is easily guaranteed by providing a default classification constraint of the form λ(A) ⊥ for every attribute AεA. In addition, any set of lower bound constraints, which use only the dominance relationship and security levels (constants) only on the right-hand side, is by itself consistent, since mapping every attribute to trivially satisfies all such constraints. Analogously, any set of upper bound constraints is by itself trivially consistent. However, a set of constraints that includes both upper and lower bound constraints is not necessarily consistent, the simplest example of inconsistent constraints being {λ(A), ⊥ λA(A)} (assuming that and ⊥ are distinct). Given an arbitrary set of constraints, our method first enforces upper bound constraints to determine a firm maximum security level for each attribute. In the process, the consistence of the entire constraint set is checked. If the enforcement of upper bound constraints succeeds, a second phase evaluates the lower bound constraints to determine a minimal classification. In this method, we assume throughout that the left- and right-hand sides of each constraint are disjoint, since any constraint not satisfying this condition is trivially satisfied. Now, the method for determining the upper bound constraint in accordance with the invention will be described. FIG. 4 is a flowchart illustrating an upper bound constraint determination method 110 in accordance with the invention. Upper bound constraints require the level of an attribute to be dominated by a specific security level. Because of the transitivity of the dominance relationship and the presence of lower bound constraints, upper bound constraints can indirectly affect other attributes besides those on which they are specified. For instance, the combination of upper bound constraint Admin λ(patient) and lower bound constraint λ(patient). λ(employer) forces Admin as a maximum level for attribute employer as well. Intuitively, an upper bound constraint affects all the attributes on those paths in the constraint graph that have the upper bound constraint as the initial edge. Each upper bound constraint can thus be enforced by traversing paths from security levels and propagating the constraint forward, lowering the levels of attributes encountered along the way accordingly (to the highest levels that satisfy the constraints). More precisely, let l be a security level of the left-hand side of some upper bound constraint. For each edge leaving from node l to some attribute node A, we propagate l forward as follows in step 112. If l dominates the current level of A in step 114, the upper bound constraint under consideration is satisfied, and the process terminates. If not, the level λ(A) of attribute A is lowered to the greatest lower bound of its current value and l in step 116. A unique such level l′ is guaranteed to exist because we are working in a lattice. For each edge leaving from A, level l′ is propagated to the node reached by that edge. Also, for each edge leaving from a hypernode that contains A, the least upper bound l"; of all the attributes in the hypernode is propagated to the node reached by that edge. These steps are shown in the flowchart as a decision block to determine if more edges are present in step 118 and to determine if more nodes are present in step 120. Propagating a level 1′ to an attribute node A′ means lowering λ(A′) to the greatest lower bound of its current level and l′, and proceeding recursively on all edges leaving from A′ or from hypernodes containing it as just described. This process terminates for each path when a leaf node (security level) is reached. Then, if the level being propagated dominates the level of the leaf rode, the process terminates successfully for the upper bound constraint being considered. Otherwise, an inconsistency in the constraints has been detected. In this case the process terminates with failure. As a result of the upper bound determination method described herein, the maximum allowed security level for each attribute is determined. The maximum security level for each attribute may then be used by the minimal solution determination method described below to determine the minimal solution (e.g., sufficient security to protect the data without unnecessarily limiting access to the data). Now, an example of the upper bound determination in accordance with the invention will be described. FIGS. 5a-5c are diagrams illustrating an example of the upper and lower constraints, the constraint graph and the resulting upper bounds, respectively, for an exemplary data set in accordance with the invention. In particular, the example in FIGS. 5a-5c, with security levels taken from the lattice in FIG. 1(c), provides a simple illustration of the upper bound computation. Initially, the level of each attribute is set to HMO (T) which is the top security level of the lattice of FIG. 1c. There is one upper bound constraint, Provider λ(illness). Propagating level Provider forward causes λ(illness) to be lowered to HMO Provider=Provider. Likewise, Provider is propagated to division as a result of the constraint λ(illness) λ(division), lowering λ(division) to Provider. Next, the constraint λ(division) Public is checked and found to be satisfied, since Provider Public. Similarly, the constraint lub{λ(division), λ(plan)} doctor is found to be satisfied, since lub {Provider,HMO}=HMO λ(doctor)=HMO. Finally, the remaining constraint on illness, λ(illness) Research is checked and found to be satisfied, and the upper bound computation succeeds with the upper bounds as shown in FIG. 3(c). Note that if we were to replace the upper bound constraint with Financial λ(illness), for example, the process would fail upon checking λ(illness) Research, since-(Financial Research). Now, a method for determining a minimal solution from the lower bound constraints in accordance with the invention will be described. FIG. 6 is a flowchart illustrating a lower bound constraint and minimal solution determining method 130 in accordance with the invention. Examples of the application of this method are shown in FIGS. 7-9. Upon successful completion of the enforcement of upper bound constraints, the maximum allowed security level for each attribute is known, and the upper bound constraints require no further consideration. The second phase thus deals exclusively with lower bound constraints to determine a minimal classification. Among lower bound constraints, we consider separately the acyclic and cyclic constraints (as identified above). The reason for considering them separately is that acyclic constraints, which are expected to account for most constraints in practice, can be solved using a simpler and more efficient approach than that needed for cyclic constraints. In accordance with the invention, the method 130 first separates lower bound constraints into acyclic or cyclic constraints in step 132. Each of the steps of the method will be briefly described here and then described in more detail below. In step 134, the method determines if the acyclic constraint is simple or complex. If the acyclic constraint is complex (as defined above), then the attributes on the right hand side of the dominance equation are upgraded in step 136 so that the minimal solution may be determined in step 138. If the acyclic solution is simple (as defined above), then the method traverses the constraint graph from the leaves with the security levels to the nodes in step 140. During the backwards traversing of the constraint graph, the security levels of the leaves are propagated to the nodes according to the lower bound constraints in step 142 so that a minimal solution is determined in step 138. If a cyclic constraint exits, then the highest security level is assigned to each attribute (based on the upper bound constraints) in step 144. In step 146, a security level of an attribute is lowered and the method determines if the lower level violates a constraint in step 148. If a constraint is violated, then the right hand side (rhs) is tested in step 150 and the method loops back to step 146. If the lower level does not violate a constraint, then the method determines if there are more attributes to test in step 152 and loops back to step 146 to lower the levels of those attributes. If all of the attributes have been completed, then the minimal solution is determined in step 154. In this manner, a minimal solution that protects the data sufficiently while permitting as many people to access the data is achieved. The acyclic minimal solution will now be described along with an example of the process. Acyclic Constraints A straightforward approach to computing a minimal classification involves performing a backward propagation of security levels to the attributes. Consider an acyclic constraint graph with no hypernodes (simple constraints only). Starting from the leaves, we traverse the graph backward (opposite the direction of the edges) and propagate levels according to the constraints. Intuitively, propagating a level to an attribute node A according to a set of constraint edges {(A,X1), . . . ,(A,Xn)} means assigning to A the least upper bound of all levels represented by X1, . . . ,Xn. As long as each Xi is guaranteed to remain fixed, propagating in this way ensures that A is assigned the lowest level that satisfies all constraints on it. Thus, for acyclic simple constraints the unique, minimal solution can be computed simply by propagating levels back from the leaves, visiting all the nodes in (reverse) topological order. As an example, consider the seven simple constraints shown in FIG. 7(a) and the corresponding constraint graph 7(b), where the security levels are taken from the lattice in FIG. 1(c). Applying the process just outlined, we first propagate level Public to visit and level Research to illness. With the final levels for visit and illness now known, we next propagate the least upper bound of Public, λ(visit), and λ(illness), which is Research, to treatment. Finally, we propagate the least upper bound of λ(treatment) and Clinical, which is Clinical, to prescription, resulting in the minimal solution shown in FIG. 7(c). In the minimal solution, the illness attribute has at least a research security level, the prescription attribute has at least a clinical security level and the like which ensures adequate security from association and inference attacks but provides as much access to the data as possible. This process is clearly the most efficient one can apply, since each edge is traversed exactly once. In terms of the constraints, this corresponds to evaluating the constraints in a specific order, evaluating each constraint only once, when the level of its right-hand side becomes definitely known, and upgrading the left-hand side accordingly. In a set of acyclic constraints, the propagation method described for simple constraints alone requires only minor adaptation to handle complex constraints as well. The key observation is that, if a complex constraint is not already satisfied, it can be solved minimally by upgrading any one of the attributes on the left-hand side, provided that neither the level of the right-hand side nor the levels of any other attributes on the left-hand side are later altered. As long as the constraints are acyclic, there exists an order of constraint evaluation (security-level back-propagation) that ensures that the security levels of all attributes involved in a complex constraint are known prior to the selection of one for upgrading, if necessary, to satisfy the constraint. For example, consider the constraints in FIG. 8(a) and the corresponding constraint graph in FIG. 8(b). The complex constraint lub{λ(patient), λ(bill)} Admin can be solved by assigning either Admin to bill or Research to patient. Note that either solution is minimal according to Definition 2.3, and thus, minimal solutions for sets that include complex constraints are generally not unique. The particular minimal solution generated depends on the order of constraint evaluation. For the example in FIG. 8, the first solution (as shown in FIG. 8(c)) is computed if the simple constraint on patient is evaluated first, whereas the second solution (shown in FIG. 8(d)) is computed if the simple constraint on bill is evaluated first. Now, the determination of a minimal solution for a cyclic constraint will be described. Cyclic Constraints For cyclic constraints, the simple back-propagation of security levels is not directly applicable, and it is not clear whether the method can be adapted easily to deal with arbitrary sets of cyclic constraints. Simple cycles are easily handled, since they imply that all attributes in the cycle must be assigned the same security level-we can simply "replace" the cycle by a single node whose ultimate level is then assigned to each of the original attributes in the cycle. For example, we might imagine replacing the simple cycle involving attributes exam, treatment, and visit in FIG. 2 by a single node labeled "exam, treatment, visit" and proceeding as before. However, when complex constraints are involved in a cycle, the problem becomes more challenging. Recall that a complex constraint can be solved minimally by selecting any left-hand-side attribute to be upgraded, provided that the level of no other attribute in the constraint subsequently changes. For cyclic complex constraints, it can be difficult to ensure that this requirement is satisfied. We might upgrade the level of one attribute A on the left-hand side of a complex constraint only to find that a higher level is propagated through a cycle to another attribute A′ in the same constraint. The constraint remains satisfied, but the resulting classification may not be minimal, since the original upgrading of A may have been unnecessary for satisfaction of the constraint. In many cases it may be possible to determine a priori an order of constraint evaluation and a unique candidate for upgrading in each complex constraint that guarantees a minimal classification using back-propagation of levels through cycles. However, as the cycles become more complicated, the criteria and analysis needed for determining the attributes to be upgraded and a suitable evaluation order become more complex. The problem becomes particularly acute for cyclic complex constraints whose left-hand sides are nondisjoint (for example, constraints ({illness, patient}, Clinical)and ({patient, bill},Admin) in FIG. 2), since the choice of the attribute to be up-graded in one constraint may invalidate the choice made for another. Moreover, it is not generally possible to choose a single attribute in the intersection of two or more left-hand sides to be upgraded for all intersecting constraints. As an example, consider three constraints whose left-band sides are {A, B}, {B, C}, and {A, C}, respectively. If all three constraints require an attribute to be upgraded, one of the constraints will necessarily have both attributes upgraded. The result in such a case can still be minimal. However, it can be far from clear whether any two attributes will do, and if not, which two should be chosen, when such intersecting constraints are entangled in a complex cycle. Since it is difficult, at best, to ensure that no upgrading operation performed during back-propagation of levels through cycles involving complex constraints will ever be invalidated, we appear to be left with essentially two alternatives: (1) augment the back-propagation approach with backtracking capabilities for reconsidering and altering upgrading decisions that result in nonminimal classifications, or (2) develop a different approach for computing minimal classifications from cyclic constraints. We would of course prefer a method that is as close as possible in computational efficiency to the simple level propagation for acyclic constraints. Thus, we reject alternative (1), since the worst-case complexity of a backtracking approach is proportional to the product of the sizes of the left-hand sides of all constraints in the cycle. Instead, we develop a new solution approach to be applied to sets of cyclic constraints. This new approach begins with all attributes involved in a cycle at high security levels, and then attempts to lower the level of each such attribute incrementally as long as all affected constraints remain satisfied. More specifically, assume that we are given a set of cyclic constraints and that every attribute in the cycle is initially assigned the highest classification allowed by the upper bound constraints. For each attribute A involved in the cycle, we attempt to lower the level of A, one step at a time along an arbitrary path down the lattice. At each step we check whether lowering the level of A would violate any constraints, as follows. For each constraint on A, we check whether the level of the left-hand side would still dominate that of the right-hand side if A were to be assigned the lower level. If the constraint would still be satisfied, we simply continue. Otherwise, we check whether the level of the right-hand side can also be lowered so that the constraint is again satisfied. If the right-hand side is a level constant, we compare that level to the current level of A, failing if it is not dominated. Otherwise, the right-hand side is another attribute A′, and we then attempt (recursively)to lower the level of A′. If, finally, the attempted lowering of A from a level l1 to a level 12 fails, the lowering is attempted again along a different path down the lattice from l1. The last level for which lowering A succeeds is A's final level. Repeating this procedure for each attribute, the result at the end of the entire process is a minimal classification for all attributes in the cycle. Unlike the back-propagation method, which is applicable only to acyclic constraints, the incremental, forward lowering approach is applicable to all constraints. However, it is not generally as efficient, although its complexity remains low-order polynomial. Thus, it is preferable to apply the simple back-propagation method wherever possible and reserve the forward-lowering approach for sets of cyclic constraints. The following section describes an algorithm that elegantly combines the two approaches for greatest efficiency on arbitrary sets of constraints. For a simple illustration of this procedure, consider the cyclic constraint set in FIG. 9(a) and the corresponding constraint graph in FIG. 9(b), where the security levels are taken from the lattice in FIG. 1(c). Assume that all four attributes (division, doctor, illness, and plan) are initially labeled at level HMO (T). We select an arbitrary attribute, say illness, from the cycle and attempt to lower its level. We may try either Admin or Provider, and we choose Admin arbitrarily. We can lower (illness) to Admin as long as all affected constraints remain satisfied. The first constraint on illness remains satisfied, since Admin Research. The second constraint on illness remains satisfied only if λ(division) can also be lowered to Admin. Attempting to lower λ(division) to Admin, we find the simple constraint on division remains satisfied, and the complex constraint as well, since λ(plan) is HMO. It is easy to see, then, that λ(illness) and, consequently, λ(division) can be lowered ultimately to Research. Suppose now that we attempt to lower λ(division). Since λ(division)=Research we may try Public and find that both the simple and complex constraint on division remain satisfied. Finally, we attempt to lower λ(doctor). We first try level Admin and find that the simple constraints on doctor remain satisfied, since Admin Public and Admin λ(illness)=Research. We now try to lower λ(doctor) to Financial. This attempt fails because the simple constraint λ(doctor) λ(illness) remains satisfied only if λ(illness)can be lowered to Public. This is not possible because of the constraint λ(illness) Research. We then try to lower λ(doctor) to Clinical and succeed. Subsequently, we try to lower λ(doctor) to Research. Again the simple constraints on doctor remain satisfied, and so in the last step of the process we try to lower λ(doctor) to Public. As before, this attempt fails because it would require λ(illness) to be lowered to Public as well, which cannot be done. Once the cyclic constraints have been solved, the backward propagation process is executed, and plan is assigned level Admin, which is the lowest level that it can assume without violating the dominance constraints imposed on it, namely lub{λ(division), λ(plan)} λ(doctor) and λ(plan) Financial. The computed minimal solution appears in FIG. 9(c). Now. an example of the pseudocode that implements that above methods will be described. FIG. 10 illustrates the pseudocode for implementing the security classification method in accordance with the invention. At a high level, the algorithm implementing our approach consists of four main parts. In the first part, we identify sets of cyclic constraints to be evaluated with the forward lowering approach and determine the order in which attributes (sets of attributes in the case of cyclic constraints) will be considered for both the upper and lower bound constraint solving phases. The second part enforces upper bound constraints and, in the process, checks the entire input constraint set for consistency. The third and fourth parts represent, respectively, the back-propagation method for acyclic constraints and the forward lowering method for cyclic constraints. These two components operate alternately according to whether or not the attribute under consideration is involved in a cycle. The procedures embodying the different parts of the approach are presented formally in FIG. 10. Here we describe them informally. We assume that the input constraint set C is partitioned into two sets: Cupper, the upper bound constraints, and Clower, the lower bound constraints. The upper bound constraints are considered only in the computation of upper bounds for the security levels of attributes (procedure compute_upper_bounds), while lower bound constraints are considered in all phases of the algorithm. The primary task of main is to determine an ordering of the attributes that both identifies cyclic relationships and captures the order in which attributes will be considered when evaluating the classification constraints on them. This ordering reflects possible dependencies between the security levels of the attributes, as specified by the lower bound constraints, and is a total order over sets of attributes. Two attributes whose levels may be mutually dependent are part of a constraint cycle and are considered equivalent in terms of the attribute ordering. Intuitively, the security level of one attribute depends on that of a second attribute if the second is reachable from the first in the constraint graph. For the purpose of determining reachability only, we interpret each edge from a hypernode to a node as a set of edges, one from each attribute in the hypernode to the node. For example, in the constraint lub{λ(division), λ(plan)} λ(doctor) in FIG. 9, we would consider doctor to be reachable from either division or plan. This interpretation reflects the fact that the security levels of either division or plan may depend on the level of doctor. Using this interpretation of reachability, then, attributes involved in cyclic constraints correspond to those in strongly connected components (SCCs)of the constraint graph. Constraint cycles can therefore be identified by applying known methods for identification of SCCs. If we think of each such SCC as a kind of node (or node group) itself, the attribute order we seek is essentially the topological order of the attribute nodes (in the case of acyclic constraints) and SCCs in the constraint graph. Once computed, this order is used to guide the evaluation of both upper and lower bound constraints. The computation of the attribute ordering is accomplished through an adaptation of known approaches to SCC computation involving two passes of the graph with a depth first search (DFS) traversal of the lower bound constraints. The first pass (dfs_visit) executes a DFS on the graph, recording each attribute in a stack (Stack) as its visit is concluded. The second pass (dfs_back_visit) considers attributes in the order in which they appear in Stack, assigning each to the SCC list scc[max_scc] (where max_see is incremented as each attributed is visited) and marking the attribute as visited. The SCCs are maintained as lists rather than sets so that the attributes within an SCC can be processed in a predictable order in other parts of the algorithm. For each new attribute A popped from Stack, the process walks the graph backward with a (reverse) DFS and adds to the SCC list containing A all attributes it finds still unvisited, since such attributes are necessarily part of the SCC containing A. Each SCC satisfies the following properties: (1) each attribute is a member of exactly one SCC, (2) any two attributes belong to the same SSC if and only if they appear together in a cycle (i.e., are mutually reachable), and (3) the index of the SCC to which any attribute belongs is no greater than that of any attribute reachable from it (i.e., on which it depends). As an example, consider the constraints in FIG. 2. The execution of main produces the following SCCs: scc[1]=prescription) scc[2]=(exam, treatment, visit) scc[3]=(insurance) scc[4]=(bill) scc[5]=(patient) scc[6]=(employer) scc[7]=(plan) scc[8]=(doctor, division, illness) In addition to finding SCCs, main initializes several variables that are used either during the DFS procedures or in the actual classification process, as follows. For each attribute A, Constr[A] is the set of (lower bound)constraints whose left-hand side includes attribute A, visit[A] is used in the graph traversal to denote if A has been visited, and done[A] is set to TRUE when A becomes definitively labeled. For each security level lεL, we set done[l]to TRUE, since security levels are constants, and visit[l]to 1, since security levels are leaves in any (lower bound) constraint graph and thus represent terminal points in any traversal of the graph With each constraint cεClower we associate a count, count[c], initialized to the number of attributes in the left-hand side of c, and used during the computation of a solution to keep track of the number of attributes remaining to be considered. After initialization and SCC computation, main initializes each attribute's classification to T and concludes by invoking the main constraint solving procedures_compute_upper_bounds, compute_partial-lubs; and compute_minimal_solution. Procedure compute_upper_bounds constitutes the process for enforcing upper bound constraints outlined above. The first step directly evaluates each upper bound constraint by assigning to the constrained attribute the greatest lower bound ( )of its current level and the level specified by the constraint. The remainder of the procedure then propagates the enforced upper bounds throughout the (lower bound)constaint graph. This propagation considers each attribute in increasing SCC index order, since the upper bound of some attribute can affect the upper bounds only of attributes of equal or higher XC index, and thus, the number of traversals is minimized. As each attribute is considered, its upper bound is propagated to other attributes, via procedure upper-bound. As upper-bound processes each constraint c on an attribute, it decrements count[c]. The level of the left-hand side is then propagated to the right-hand side only if the count has reached 0, or the attribute on the right-hand side is in the same SCC. Such delayed propagation optimizes the processing of acyclic constraints, since the SCC index of the right-hand side attribute of any acyclic constraint is higher than that of any attribute on the left-hand side. Only after the last attribute in the left-hand side has been processed is it necessary to propagate the level forward. By considering all attributes in increasing SCC index order, we ensure that all upper bounds are eventually propagated through the graph (or found to violate the consistency requirement). Within a cycle (SCC), each upper bound is propagated (procedure upper_bound) only as far as necessary-the process terminates along any path in which the upper bound is already satisfied. To ensure that all upper bounds are eventually propagated throughout the cycle, procedure compute_upper_bounds calls upper_bound on all unvisited attributes in the cycle. This process guarantees that, even if constraints propagate upper bounds (from attributes of lower SCC index) into a cycle at several points, every upper bound will be propagated as far as necessary. Note that the level assigned to any attribute can always be lowered as much as required by any upper bound propagated into the attribute. Propagation failure can occur only when security levels (leaf nodes)are reached and the incoming upper bound does not dominate the level of the leaf node. Such failure indicates that the upper bound constraint that originated the failed propagation is inconsistent with the lower bound constraints. If compute_upper_bounds completes successfully, we know that the constraints are consistent and that the computation of a minimal solution will be successful (Theorem 5.1). The upper bound constraints need no further consideration. The purpose of compute_partial_lubs is to precompute the least upper bounds (lubs)of the levels of certain subsets of attributes. These partial lubs are used in procedure minlevel (called by compute_minimal_solution) to compute quickly the lub of the levels of all but one attribute in the left-hand side of an arbitrary constraint. The computation of the partial lubs is designed to take advantage of the fact that attributes in the left-hand side of an acyclic constraint are processed in a predictable order (the SCC index order determined by the DFS procedures). For each lower bound constraint c of the form (lhs, rhs), |lhs|+2 partial lubs are computed. At the conclusion of compute_partial_lubs, each partial lub Plub[c][i]f or constraint c is the least upper bound of the levels of all attributes from SCC index 1 up to i. Their use is made clearer in the following discussion. Procedure compute_minimal_solution integrates the two approaches (back-propagation as set forth above and forward lowering as outlined above) for determining a minimal solution for lower bound constraints. Unlike compute_upper_bounds it considers attributes in decreasing order of SCC index. That is, compute_minimal_solution traverses the constraint graph from the leaves back, rather than from the roots forward. For each attribute A at the SCC index being considered, all constraints in Constr[A] are processed as follows. For each constraint c whose right-hand side is definitively labeled (done[rhs]=TRUE), the procedure determines how to enforce the constraint on A. If c is simple (|lhs|=1), the level of the right-hand side is accumulated via the least upper bound ( )operation into variable 1 (initialized to ⊥). Otherwise, c is complex, and minlevel is called to compute a minimal level that A must dominate (accounting for the current levels of the other attributes on the left-hand side of the constraint) and still satisfy the constraint. Procedure minlevel first computes the least upper bound of the levels of all other attributes (lubothers)by using the precomputed partial lubs. If A is the jth attribute on the left-hand side to be processed, the lub of the other levels is simply the lub of the partial lubs Plub[c][j-;1] and Plub[c][j+1]. Next, minlevel computes a minimal level for A that maintains satisfaction of c by descending the lattice along a path from A's current level, one level at a time, stopping at the lowest level found whose direct descendants would all violate the constraint if assigned to A.1 The returned level is then accumulated into 1. If all the constraints in Constr[A] have the right-hand side done (which is always the case for acyclic constraints), A is simply assigned the level 1 so computed. Intuitively, this corresponds to enforcing back-propagation of security levels. 1 In the generally assumed case of compartmented lattices (e. g., FIG. 1(a)) the minimum level to be assigned to A can be computed directly without the need of walking through the lattice. The entire else branch of the minlevel procedure can in fact be substituted with the simple computation, If (lubothersl If, on the other hand, there is at least one constraint on A whose right-hand side is not definitively labeled (done[rhs]=FALSE), then attribute A must be involved in a constraint cycle. In this case, compute_minimal_solution proceeds by performing the forward lowering computation starting from A. At the start of this computation, level 1 represents a lower bound on A's final level. Thus, A must eventually be assigned a level somewhere between its current level (which must be at least as high as l if the constraints are consistent)and 1. We know that the constraints are satisfied with A at its current level, so the incremental forward lowering process begins by computing the set of levels (DSet) immediately below λ(A) in the lattice. A member 1"; of this set is chosen arbitrarily, and try_to_lower checks whether A can be lowered to level 1";. Procedure try_to_lower takes an attribute A and a level 1 and returns a set of attribute/level pairs that represent a satisfactory (but possibly non-minimal)assignment of levels to attributes that allows A to be lowered to 1 while maintaining satisfaction of all constraints. If no such assignment exists, try_to_lower returns the empty set to indicate failure. In the event that try_to_lower succeeds, compute_minimal_solution proceeds to enforce all level assignments (in set Lower) returned by try_to_lower. It then continues to attempt lowering the level of A from the most recent point of success. In the event that try_to_lower fails, another level to try is chosen from DSet. If all levels in DSet are tried and fail (DSet=Ø), the current level assigned to A is a minimal level for A that maintains satisfaction of all constraints. Note that the condition DSet=Ø must eventually become true, either because all attempts at lowering fail, or because ⊥ is reached. Note also that when a lowering attempt succeeds for some level in 1";εDSet, it is not necessary to consider any other level in DSet. That is, a minimal level for A will always be found by considering only levels lower than the level that last succeeded. This point is discussed in more detail in the correctness proof for the algorithm. The keys to the operation of procedure try_to_lower are the sets Tocheck and Tolower. Tocheck is the set of attribute/level pairs that remain to be checked to determine success or failure of the lowering attempt. Tolower is the set of attribute/level assignment pairs that must ultimately be enforced if the lowering attempt succeeds. In effect, Tocheck represents a set of tentative level assignments that may become definite at some point. Now, for a given call try_to_lower(A, l), Tocheck is initialized to (A, 1)and Tolower to Ø, since it is the attempt to lower the level of A to 1 that must be checked, while no assignments are yet implied by the attempted lowering. The procedure continues as long as there are tentative assignments to check. The checking process amounts to propagating levels forward through the constraint graph, maintaining additional lowerings found to be necessary in set Tocheck, moving them then to set Tolower for their later enforcement, if they do not result in any constraint violation. In the event of a constraint violation try_to_lower fails immediately, returning the empty set. Otherwise, it returns the set Tolower containing the assignments found to be necessary to enable the level of attribute A to be lowered to 1. Note that in the forward-lowering process, the level propagated forward may change and become either higher or lower because of complex constraints. The level can increase when traversing a complex constraint, because in this case we require only that the right-hand side is dominated by (i.e, lowered to) the level of the lub of all the attributes in the left-hand side. The level can also decrease when, traversing a complex constraint, we would require rhs to be dominated by (lowered to) a level incomparable to its current level or the level recorded for it in either Tocheck or Tolower. In this case, the process can succeed only if the attribute is dominated by both levels, that is, if it can be lowered to their greatest lower bound. We therefore record this tentative lowering (in Tocheck and propagate the level forward. Once a minimal level has been computed for any attribute A, compute_minimal_solution updates the partial lubs in which λ(A)is involved to keep the partial lubs correct with respect to λ. FIGS. 11a-11c illustrate the execution of the approach on the constraints of FIG. 2. For the readers convenience, we reproduce the lattice and the set of constraints in FIG. 8(a) and 8b) respectively. Table 8(c) lists attributes in the order in which they are considered and shows how their level (and those of attributes in the same SCC) change as each attribute is processed. An F on the side of a try_to_lower call indicates a failure. Traversing down a lattice is assumed to be performed by considering direct descendants in left-to-right order. The bottom line reports the final (minimal) levels computed. Now, the correctness and complexity of the method in accordance with the invention will be described. Correctness and Complexity Analysis In this section, the correctness of the method in accordance with the invention is described and the complexity of the method is described. Proofs of the theorems that appear in this section appear in the Appendix. Theorem 5.1 (Correctness) Algorithm 3.1 (See FIG. 10) the problem (MIN-LATTICE-ASSIGNMENT). That is, given a set C of classification constraints over a set A of attributes and a security lattice L=(L,), Algorithm 3.1 generates a minimal classification mapping λ: A□L satisfying C. Complexity In the complexity analysis we adopt the following notational conventions with respect to a given instance(A, L, C)of MIN-LATTICE-ASSIGNMENT: NA(=|A|)denotes the number of attributes in A; NL(=|L|)denotes the total number of security levels in L; Nc (=|C|)denotes the number of constraints in C; S=Σ(lhs,rhs) Theorem 5.2 (Complexity) Algorithm 3.1 (See FIG. 10) solves any instance (A, L, C) of the problem MIN-LATTICE-ASSIGNMENT in O(NASHMc) time, and, if the set of constraints C is acyclic, in O(SMc)time. Therefore, MIN-LATTICE-ASSIGNMENT is solvable in polynomial time. Note, in particular, that the time taken by Algorithm 3.1 is linear in the size of the constraints for acyclic constraints, and no worse than quadratic for cyclic constraints. Whether the complexity for the cyclic case can be improved to linear in the size of the constraints remains an open question. However, the complexity for the cyclic case is truly worst case-it assumes that the entire constraint set forms a single SCC, which rarely occurs in practice. For any instance of the problem, the acyclic complexity analysis applies to all acyclic portions of the constraint set. In Algorithm 3.1 the higher price is paid only for cyclic constraints, which typically include only a small portion of the input constraint set. The cost of lattice operations An important practical consideration is the efficiency of lattice computations. Recent work has shown that constant-time testing of partial orders can be accomplished through a data structure requiring O(n*n1/2) space and O(n2) time to construct, where n is the number of elements in the poset. Encoding techniques are known that enable near constant-time computation of lubs/glbs, so that c in the above analysis can be taken as constant, at the expense of additional preprocessing time. In practice, one would expect to use the same security lattice over many different instances of MIN-LATTICE-ASSIGNMENT, so that the additional preprocessing cost for lattice encoding is less of a concern. Finally, we note that the generally considered security lattices with access classes represented by pairs classification and a set of categories can be efficiently encoded as bit vectors that enable fast testing of the dominance relation and lub and glb computations. The limited number of levels (16) and categories (64) required by the standard allows the encoding of any security level in a small number of machine words, effectively yielding constant-time lattice operations. Returning a Preferred Minimal Solution As noted above, minimal solutions are generally not unique, since complex lower bound constraints can be solved minimally by assigning, if necessary, any one attribute on the left-hand side a sufficiently high level. The approach presented returns one minimal solution, where the particular solution returned depends both on the (fixed) topological order of attribute nodes and cycles that guides the back-propagation of security levels and on the (arbitrary) order in which constraints are evaluated within cycles. Not all minimal solutions to a set of constraints may be considered equal. Some solutions may be preferred over others, for instance because they grant greater visibility (i. e., accessibility to more subjects) on certain selected attributes. Previous approaches addressing the problem of minimizing information loss while satisfying some upgrading constraints based the choice of the specific solution to be returned on the concept of "optimal" classification. Optimality is expressed as minimization of cost measures determined from the association of weights to attributes and costs to security levels, and where the cost of each solution is the weighted sum of the classifications assigned. Finding such an optimal solution is however an NP-hard problem, and existing approaches typically perform exhaustive examination of all possible solutions. Beside suffering from a general computational intractability, these cost-based approaches are very difficult to use in practice, as it is generally far from obvious how to manipulate costs to achieve the desired classification behavior. We describe here two ways of specifying preference criteria on the minimal solution to be returned which are intuitive and easy to use. We also illustrate how they can be included in our approach without increasing the computational cost of finding the solution. Soft upper bound constraints. Soft upper bound constraints are, as their name suggests, upper bound constraints (Definition 2.2), whose satisfaction is not mandatory, rather it is a desiderata on the solution. Intuitively, soft upper bound constraints express visibility requirements that should be satisfied in the solution, if possible. Since not all soft constraints may be simultaneously satisfiable, it is convenient to consider soft constraints ordered according to their importance. We assume a list of soft upper bound constraints is provided as input, where the order in which the constraints appear reflects their importance. Soft upper bound constraints are enforced just after the upper bound constraints provided as part of the problem specification. The process for enforcing soft upper bound constraints is essentially the same as that for enforcing other upper bound constraints. The only difference is in the fact that constraints are considered in a specific order, and that constraints that cannot be satisfied (since they conflict with other upper or lower bound constraints or soft upper bound constraints already enforced)can simply be ignored. Attribute priority. Another, complementary, approach to specify and compute a preferred solution is the consideration of explicit priorities between attributes, which establish their importance in terms of visibility. The algorithm should then return the minimal solution that avoids penalizing those attributes whose visibility is more important. To the purpose of considering priorities, we first assume that attributes are prioritized according to a total order o, where A o B implies that the visibility of A is more important than the visibility of B. We then extend this order to classifications as follows. λ Definition 6.1 (Lexicographic Order) Given a set A of attributes, security lattice L=(L,), and a total ordering o on the elements of A, a classification λ: A□L lexicographically dominates (with respect to o) another classification λ′, denoted λoλ′, iff ∀AεA: (∀A′εA, A′≠A,A′o A: λ′(A′)=λ(A′)λ(A) λ(A). In other words, λoλ′ iff, for the least attribute A (in the total order o) for which λ and λ differ, λ(A) oλ′(A). Based on the above definition, a classification is said to be priority-minimal if it classifies the attributes whose visibility is more important as low as possible. This concept is made precise by the following definition. Definition 6.2 (Priority-Minimal Classification) Given a set A of attributes, security lattice L=(L,), a set C of classification constraints over A and L, and a total ordering o on the elements of A, a classification λ: A□L is priority-minimal with respect to o and C iff (1)λ|=C; and (2) ∀λ′: A□L such that λ′|=C, λoλ′λ′=λ. It is easy to see that the definition of priority-minimal is stronger than the definition of minimal Definition 2.3) and that any classification that is priority-minimal is also minimal (the converse does not necessarily hold). The proof is trivial by contradiction. Suppose the implication does not hold and consider a classification λ that is priority-minimal (with respect to some total order #o on the attributes)but is not minimal. Then, there exists a classification λ′≠λ such that λ′|=C and λλ′, i.e., λ(A) λ′(A), ∀AεA. Hence λoλ′ and λ≠λ′, which contradicts the assumption that is priority-minimal. While the additional control offered by the concept of attribute priority is useful, the assumption of totally ordered attributes is likely too strong as a practical requirement. We can imagine instead that attribute priorities will form a partial order, reflecting the fact that, while some attributes are more important than others in terms of visibility, there may be no relative importance between other attributes. We can also imagine the priority order to be only partially specified (on attributes whose visibility is most important), while all attributes not explicitly mentioned are assumed to have the same priority (at the top of the attribute ordering). For instance, referring to the example in FIG. 2, a priority order specification might say simply that patient o illness, meaning that the solution should guarantee first the maximum visibility of patient, then the maximum visibility of illness, then the visibility of the other attributes (in no particular order). To account for this general situation, we extend the definition of priority-minimal to allow the given priority ordering on the attributes A to be partial. We say that a total ordering o respects a partial ordering p if for all A, A′εA: ApA′AoA′. Definition 6.3 (Partial-Priority-Minimal Classification) Given a set A of attributes, security lattice L=(L,), a set C of classification constraints over A and L and a partial ordering p on the elements of A, a classification λ: A□L is partial-priority-minimal with respect to p and C iff(1) λ|=C; and (2) ∀λ′: A□L such that λ′|=C, (∀ total orders o respecting p, λoλ′)λ′=λ. Definition 6.3 simply extends Definition 6.2 to the case where the ordering on attributes is a partial order. Again, the condition of partial-priority-minimal is stronger than simple minimality and any solution satisfying Definition 6.3 is also a minimal solution. More precisely, it is a minimal solution preferred according to the visibility constraints specified by the given partial order on attributes. With minor modifications Algorithm 3.1 can be used to compute partial-priority-minimal solutions. Here we sketch how such a modified algorithm would work. The enforcement of upper bound constraints is carried out as in Algorithm 3.1, since their enforcement is deterministic. For lower bound constraints, the algorithm is modified to use the incremental lowering process (forward propagation) on attributes in nondecreasing attribute priority order, as determined by the partial order p. More specifically, for some total order o on the attributes that respects o, the incremental lowering procedure (try_to_lower) is applied successively to each attribute from least to greatest according to o. The level of each attribute is lowered as far as possible before proceeding to the next attribute. In this way, each attribute is assigned the lowest level that satisfies the constraints, subject to the additional constraint that the levels of attributes (lower in attribute priority order) already assigned cannot be modified. We state without proof that the solution so computed is partial-priority-minimal (with respect to p). The time complexity of this computation is the same as that of computing a minimal solution for a set of cyclic constraints (analyzed in the appendix), O(NASHMc). When the priority ordering on attributes is only partially specified (i. e., some subset of the attributes is not prioritized), the performance of the algorithm for computing partial-priority-minimal solutions can be improved by first executing the incremental lowering process as described only on the prioritized attributes. Then, procedure compute_minimal_solution from Algorithm 3.1 can be run unmodified. Intuitively, running the forward propagation approach on the prioritized attributes will set their final levels as low as possible. Then, the algorithm will proceed by executing compute_minimal_solution to determine a classification as before. To illustrate, consider the constraints in FIG. 2 and assume the partial priority order patient p plan, plan p doctor (with no other attributes prioritized). We first enforce the upper bound constraints, setting the highest level of each attribute as indicated in the first line of the table in FIG. 12. We then execute the forward propagation process on the prioritized attributes in increasing priority order. Hence, we try to lower patient one step at a time in the lattice, from its initial level Admin, propagating the constraint forward. All the levels attempted will return success, and patient will be ultimately assigned level Public, causing the highest level that can be assumed by employer to be lowered to Public as well. Next we consider attribute plan, trying to lower it one step at a time from its current level HMO. Again, every attempted level will succeed and plan will ultimately be assigned level Financial, causing the highest level that can be assumed by doctor to be lowered to Admin. Finally, we consider attribute doctor and attempt to lower it, one step at a time in the lattice, from its level Admin, propagating the constraint forward. The process determines Clinical as a lowest level that doctor can assume (the attempt to lower the attribute at level Research fails because of the required lowering of illness, whose least upper bound with patient would not be satisfied anymore). Hence, the level of doctor is determined as Clinical, causing the highest level of illness to Clinical as well. After this process the highest level assigned to patient, plan, and doctor is the lowest level they can assume, assumed the specified priority order, without causing any violations. We can now execute compute_minimal_solution to determine a solution. The classification process and the resulting solution are illustrated in FIG. 12. Arbitrary Partial Orders The results presented thus far are based on the assumption of classification levels forming a lattice. We consider here the problem of determining a minimal classification if the security levels do not form a lattice but may instead be an arbitrary poset. It turns out that the problem becomes intractable under this new condition, as the following theorem states. We define the problem MIN-POSET similarly to MIN-LATTICE-ASSIGNMENT, except that the partial order is not restricted to be a lattice and it is stated as a decision problem. Given a partial order (P,)and a set of constraints C, each constraint taking one of three forms. A A′, A 1, lub{A1, . . . , k} A, where the As are attributes, and 1 is a constant drawn from P, is there an assignment from attributes to members of P that satisfies all the constraints C, and which is minimal? Theorem 7.1 Min-Poset is NP-hard. Proof: The proof is presented in the attached appendix. In summary, the problem of computing an assignment of security levels to database attributes from a set of classification constraints has been considered. The constraints we consider permit specification of relationships between the security levels of a set of one or more attributes and the level of another attribute or an explicit level. In contrast to previous proposals investigating the NP-hard problem of determining optimal solutions (with respect to some cost measure), we provide an efficient algorithm for computing one solution with (pointwise)minimal information loss. Our approach efficiently handles complex cyclic constraints and guarantees a minimal solution in all cases in quadratic time, but also provides linear time performance for the common case of acyclic constraints. APPENDIX A Proofs A.1 Correctness of Algorithm 3.1 We first establish several lemmas used in the proof of the main theorem. The proofs often refer to immediate constraints on an attribute, by which we mean either lower bound constraints in which the attribute appears on the left-hand side or upper bound constraints in which the attribute is on the right-hand side. Lemma A.1 establishes the correctness of compute_upper_bounds, showing that it succeeds in generating an initial classification mapping that satisfies the input constraints if and only if the constraints are consistent. Lemma A.1 Let C=ClowerU Cupper be a set of classification constraints over a set of attributes A and a security lattice L=(L,). i) If compute_upper_bounds terminates with failure, then C is inconsistent. ≠ ii) If compute_upper_bounds terminates with success, then the computed classification mapping λ: A□L satisfies C(λ|=C), and hence, C is consistent. iii) Procedure_compute_upper bounds always terminates. Proof: i) We first prove that the following property holds of the current classification mapping λ throughout the computation of compute_upper_bounds:
Suppose now that upper_bound (and hence, compute_upper_bounds) terminates with failure. This means that a constraint c=(lhs, rhs), such that rhs εL is a security level, was found not to be satisfied; that is, λ|≠c. Since rhs is fixed, the only way to satisfy the constraint would be to suitably modify λ for some attribute(s) in lhs. Let 1′: A L be any mapping from attributes in A to levels in L. If λλ′, then λ′|≠c, since λ|≠c. Otherwise, λλ′. By the property just proved (A.1.1), there exists a constraint c′εC such that λ′|≠c. Hence, for any mapping λ′, there exists a constraint that cannot be satisfied, and therefore C is inconsistent. We begin by noting that before the first iteration (i=1), λ|=Cupper, since for each constraint cεCupper of the form (l,A), λ(A)is assigned λ(A) 1, so that 1 λ(A). Now consider an arbitrary iteration i. The following properties are readily established:
Lemma A.1 shows that, if the algorithm continues beyond the end of compute_upper_bounds, then the remainder of the algorithm starts from a point at which λ satisfies the constraints (and otherwise the constraints are inconsistent). The remaining lemmas are used in the proof of the main theorem to show that key parts of the final phase of the algorithm (compute minimal solution) preserve the property that, after every modification, λ remains a solution. First, we prove Lemma A.2, which shows that arguments about the satisfaction of generated classification assignments can be made locally. That is, it establishes that, if any changes to a solution mapping that are limited to a subset of the attributes result in satisfaction of the immediate constraints on those attributes, then the modified mapping remains a solution for all constraints. Lemma A.2 Given (1) a set C of constraints on a set A of attributes and (2) a subset A′ of A, let λ be an assignment of levels to attributes such that λ|=C and λ′ be an assignment such that λ□λ′ and that differs from λ only on attributes in A′. Let C′denote the set of immediate constraints on attributes in A′, that is, C′={(lhs, rhs)εC|lhs□A′≠Ø). Then, λ′|=C if and only if λ′|=C′. Proof: (Only if): If λ′ satisfies C, λ′ satisfies any subset of C. The following lemma shows that any change to A solution A resulting from the output of procedure try-to-lower in Algorithm 3.1 preserves λ as A solution. Lemma A.3 Let AS be the set of pairs of the form (λ′, 1′) returned by Try(A, 1). If AS≠Ø the assignment obtained by replacing λ(A′) with λ(A′)=1′ for all (A′, 1′)ε AS satisfies all immediate lower bound constraints on attributes in scc[i], where scc[i]is the SCC containing A. Proof: The following properties are readily established.
| ||||||