In the first session of the second day of the conference, my graduate student Mahesh Tripunitara presented a paper titled "On Safety in Discretionary Access Control", coauthored by me (Ninghui Li) and Mahesh. In the paper, we assess the validity of the motivations and claims in a paper presented at the 2004 Oakland conference by Jon Solworth and Robert Sloan, titled "A Layered Design of Discretionary Access Controls with Decidable Safety Properties".
After the presentation, a graduate student of Prof. Jon Solworth stood up and announced that he has a statement from Prof. Jon Solworth and Prof. Robert Sloan to read. He read the statement and distributed a one-page written statement discussing this issue. In addition, Prof. Solworth set up a Webpage about this debate. Please see that webpage for the statements from Prof. Solworth. (The oral and the written statements have been removed from Prof. Solworth's webpage as of May 18.)
This page is our response to the oral statement, the written statement, and the webpage set up by Prof. Solworth.
What is the Solworth-Sloan paper about?
The paper by Profs. Solworth and Sloan begins by claiming that "all general access control models that were known to be sufficiently expressive to implement the full range of DAC models had an undecidable safety problem." They use this to motivate a new access control scheme, which we refer to as the Solworth-Sloan scheme. The scheme is presented without a precise and detailed specification. They then claim that the Solworth-Sloan scheme can implement the full range of DAC models, which refers to a family of DAC models discussed in a paper by Osborn, Sandhu, and Munawer in the context of comparing DAC with RBAC. There are then a few paragraphs discussing how these DAC schemes can be implemented in the Solworth-Sloan scheme.
What is in our paper?
We begin by observing that the assertion that safety is undecidable in DAC is a prevailing myth expressed by some security researchers and that this myth stems from equating DAC with the well-known Harrison-Ruzzo-Ullman (HRU) scheme, in which safety is known to be undecidable. We then do the following.
- We point out that DAC should not be equated with the HRU scheme, as one can have access control systems based on the HRU scheme with no DAC features. Furthermore, it is unclear how certain features in DAC schemes can be achieved in the HRU scheme.
- We provide an efficient (O(n3)) algorithm to decide safety in the Graham-Denning scheme, which is the "grandaddy" of DAC schemes. The DAC schemes discussed in Osborn et al. are either subsumed by or are simple extensions of the Graham-Denning scheme.
- We provide a precise and detailed description of the Solworth-Sloan scheme, based on their informal description.
- We assert that the Solworth-Sloan scheme cannot implement a simple sub-scheme of the Graham-Denning scheme known as Strict DAC with Change of Ownership (SDCO), which is one of the DAC schemes in Osborn et al. As no detailed construction is presented in the Solworth-Sloan paper, we use the hints presented in their paper and logical reasoning to give a detailed construction. We then observe the following:
- The construction does not preserve the invariance that there is only one owner for each object.
- The construction does not handle destruction of subjects/objects, as the Solworth-Sloan scheme does not have any primitives to handle destruction of subjects/objects. We point out in our paper that it is not obvious how to add such destruction actions to the Solworth-Sloan scheme.
- The construction is very expensive, i.e., it has considerable overhead.
What is the objection raised by Profs. Solworth and Sloan?
In their statements, Profs. Solworth and Sloan assert that our construction of SDCO in the Solworth-Sloan scheme is not what they intended in their paper. In particular, they argue that they handle change of ownership by relabling the object, rather than the subject. Based on this, they asked us to withdraw our conclusion that the claim in their paper (i.e., the claim that the Solworth-Sloan scheme can implement a range of DAC schemes) is incorrect.
What are our responses?
- Profs. Solworth and Sloan do not dispute the fact that the Solworth-Sloan scheme does not handle destruction of subjects/objects; however, they assert that this is a completeness issue but not a correctness issue. We, on the other hand, believe that completeness is part of correctness. It is incorrect to claim one can implement DAC schemes but do not deal with important features of DAC schemes.
- Using relabeling of an object to handle change of ownership leads to an obvious problem. Once an object's label is changed, the subjects who have read and write accesses to the object also change. This is inconsistent with SDCO, in which a change of ownership does not affect other rights. In other words, the construction that Profs. Solworth and Sloan claim that they intend in their paper has more obvious and more serious problems; thus we did not discuss that construction in our paper. While they do not dispute our challenge, they considered it to be out of scope of the discussion. If we submit a journal version of our paper, we will include the following discussion.
On the other hand, Profs. Solworth and Sloan can probably point to other things in our construction and claim that they do not match their intention. As details are not provided in their paper, their intended construction can always be a moving target.
- The key technical question here is whether the Solworth-Sloan scheme can implement SDCO. We stand by our conclusion that the Solworth-Sloan scheme cannot implement SDCO. The Solworth-Sloan paper claims that this can be done; however, the paper does not contain details. Prof. Solworth said in a telephone call that the reason was that it was only a conference paper and it did not have enough space for the details. We look forward to seeing a technical report or a journal submission with details of such a construction.
One main reason that we wrote our paper was to hope to raise the level of rigorousness in access control research. We cannot imagine that a paper that presents a new cryptographic construction without presenting details of the construction, definition of security, or a proof of security, would be accepted in a top cryptography conference. A reviewer would look for these things, and will reject a paper if it doesn't contain them. While such a level of rigorousness may not be appropriate for all topics within access control; we feel that it is definitely needed for papers dealing with safety or other analysis issues. We also feel that striving to raise the level of rigorousness is in general a good thing for the field.
If a paper presents a new access control scheme, especially in the context of discussing safety or other kinds of analyses, the scheme should be specified in a precise fashion using a meta-formalism. One suitable meta-formalism is a state-transition system (also known as a state machine). This enables one to precisely specify what information is maintained in a state and how state may change. Without such a precise specification, it is often impossible for a reviewer to judge the correctness of the content of a paper. The use of state-transition systems in access control can be traced back at least to the fundamental work of Bell and LaPadula. Personally, I consider one of the most important contributions Bell and LaPadula have made is to use state-transition systems to formally model computer systems and their protection states. This has been used in numerous later landmark works, such as, e.g., the Harrison-Ruzzo-Ullman model and the non-interference and the non-deducibility models.
Some related information that is not essential to the technical debate is included in the following page.
Thank you for reading this, and if you have comments you would like to share, please send email to email@example.com and/or firstname.lastname@example.org
First created on May 12, 2005.
Last updated on May 18, 2005.