The Decentralized Label Model

23rd May 2008

While programming languages provide support for encapsulation and basic access control there are rarely methods in place to mediate how data flows around an application. This is essential to ensuring that a system does not suffer from information leaks. The Decentralized Label Model and Java Information Flow framework approach this problem by providing a means of statically checking the flow of information around an application, based on policies associated with variables.

In this, the first in a two part series on controlling information flow, we look at the problem of information flow control and how the Decentralized Label Model can be used to minimise leaks.


This article was adapted from one originally written as an assignment in advances in programming languages and serves as an introduction to the topics discussed.

Download the original project report. Please note that to open this file you will need to have a PDF reader installed


Overview



Introduction

Nowadays, almost all organisations rely on computer systems to store and retrieve personal information about their customers. Whether it be an address, account or even just a name this information must be kept secure under the terms of the Data Protection Act (1998). Under the Act, organisations storing personal information must ensure that “Appropriate technical and organisational measures shall be taken against unauthorised or unlawful processing of personal data and against accidental loss or destruction of, or damage to, personal data.” [artdpa] Consequently, organisations must provide a means to mediate access to any sensitive information contained in their systems. Conversely, the systems themselves must be protected from users. Just as customer information should never be exposed to unauthorised users, nor should information about the system itself. Information leaked about how the system works can provide clues allowing a malicious user to compromise it.

The way that information moves through a program or system is often referred to as information flow and is defined by the variables and methods in the program. Each time a program produces an output there is the possibility that the information it contains includes data that was never supposed to be disclosed. To solve this problem it has been suggested that programs should implement a permission based model to impose ownership on the variables in a program. This ensures that only the principals authorised to read and write variables can do so.



Controlling Information Flow

Security covers a wide range of topics and programmers have long considered security implications while developing systems. Information security discusses how principals actions on objects are controlled by policies. A principal is a user, group or role that can affect an object in the system. For example a principal could read/write a value from/to and object. A policy is a set of rules which define what principals can perform what actions on a particular object. For the duration of this report consider Alice and Bob as principals. An example policy may state that Alice can read some value x but Bob cannot. The Java programming language provides an extensive set of security libraries covering domains such as encryption and authentication as well as security policies to limit the access a program has to the system. Using best practices [artjavasec] combined with these tools can improve the security of an application, however, it provides no guarantee the information will not be leaked from the system.

A leak of information occurs when a program sends output to an unintended recipient. For example, a user could be presented with another user's bank account details. Alternatively the information could be about the system, such as the location of a file reported during an exception. To guarantee that information cannot be leaked during the execution of a program requires that all variable assignments, operations and methods be checked to ensure that the information flow is permitted. This also requires that the system calculate the implicit permissions of any new object to ensure that restricted data is not copied to less-restrictive variables. Mandatory Access Control (MAC) is a mechanism whereby all operations on an object are checked against a central policy before they are executed. Unlike Discretionary Access Control, the access control model used in most UNIX filesystems, there is no way for the owner of an object to override the security policy. The system maintains a security object for each variable to keep track of each variable's permissions and uses them to compute new security objects for new variables when appropriate [myers99jflow]. While the MAC model has seen some success in access controls for filesystems, coarse permissions granularity and runtime checking, and therefore significant overheads, have made it unsuitable for use in a programming language.

The DLM stores the security policy of each variable as a label and allows principals to control the flow of information through the application [363526]. By storing policies using labels the compiler can statically check the information flow of the program removing the need to perform all checks at runtime. To ensure that the system remains flexible, it is still possible to declare runtime principals.


Decentralized Label Model (DLM)


Principals

Principals are users, groups or roles that can affect some portion of the system, usually by reading or writing values in the program. Since principals are not limited to users, the provide a flexible means by which to manage access to variables. Jif implements the notion of a principal hierarchy through acts-for relationships. Any principal can authorise another to act on its behalf. This allows it to carry out any of the actions the original principal would be authorised to make in a program. Since principals can be roles, it is possible to implement a complex structure whereby an abstract manager can act for several employees, and a person can act for a manager, fulfilling their role.

To make the language more usable there are also limit principals ⏉ (*), which can act for any principal and ⏊ (_) which can be acted for by any principal.



Policies

The DLM allows the programmer to specify policies using labels for each variable. This is done after the variable type declaration and is parenthesised by braces. The label is can contain a set of policies and where more than one policy is required, more can be defined by using semicolons to separate them. If there are no policies assigned to a variable it will infer one from its position in the program, though it is also possible to specify a public policy using the empty label {}. There are two main types of policy, one to specify who can read a variable and one to specify who can write to it.

Confidentiality policies describe which principals can read a variable and are described using the {o → r} notation where r is the reader and o is the owner of the policy. The owner of a policy can, implicitly, also read that variable. More readers can be added to the policy using a comma-seperated list, for example {o → r1,r2}. This notation has changed with the development of Jif and is also referred to as {o:r} and {->}. The listings in part two of this series use the {->} notation as this is considered the most natural notation for programming.

Integrity policies describe which principals can write to a variable and are described using the {o ← w} notation where w is the reader and o is the owner of the policy. Again, the owner of a policy can, implicitly, write to the variable it represents.

This is all very well, except that it requires the application trust all information it contains. Where the application allows data input this is not always appropriate. To solve this the DLM requires that for the policy to be upheld, the owner of the policy must act for the current principal. This models the relationship of trust between the current principal and the data. In the case that the owner does not act for the current principal, the current principal ignores the policy.

The limit principals can also be used to define highly or minimally restrictive policies. For example, the label {o → ⏉} allows only the top principal to read the variable, and is effectively the same as having no readers at all.

Since labels contain sets of policies, the model allows for basic set operations. These can be used to calculate the intersections and unions of policies and therefore calculate the actual policy based on several distinct ones. This allows the programmer to think more abstractly about how policies affect one another and which is the most or least restrictive policy for a particular value.

To reduce the possibility of an information leak, data can only be transferred to variables or methods with at least as restrictive a policy as the original. For instance, new variables can only add owners or remove readers from policies. Since the transfer of information can only ever become more restrictive it is difficult or impossible for an information leak to occur.



By Niall Napier

Bibliography

[myers99jflow] Andrew C. Myers. 1999. Symposium on Principles of Programming Languages. . {JFlow}: Practical Mostly-Static Information Flow Control”. Symposium on Principles of Programming Languages. 228-241. citeseer.ist.psu.edu/myers99jflow.html.

[1255332] Scott F. Smith and Mark Thober. 2007. PLAS '07: Proceedings of the 2007 workshop on Programming languages and analysis for security. . Improving usability of information flow security in java”. PLAS '07: Proceedings of the 2007 workshop on Programming languages and analysis for security. 978-1-59593-711-7. 11-20. http://doi.acm.org/10.1145/1255329.1255332. ACM. New York, NY, USA.

[1255331] Boniface Hicks, Dave King, and Patrick McDaniel. 2007. PLAS '07: Proceedings of the 2007 workshop on Programming languages and analysis for security. . Jifclipse: development tools for security-typed languages”. PLAS '07: Proceedings of the 2007 workshop on Programming languages and analysis for security. 978-1-59593-711-7. 1-10. http://doi.acm.org/10.1145/1255329.1255331. ACM. New York, NY, USA.

[363526] Andrew C. Myers and Barbara Liskov. Protecting privacy using the decentralized label model”. 410-442. ACM Trans. Softw. Eng. Methodol.. 9. 4. 1049-331X. 410-442. http://doi.acm.org/10.1145/363516.363526. ACM. New York, NY, USA.

[1134757] Boniface Hicks, Dave King, Patrick McDaniel, and Michael Hicks. 2006. PLAS '06: Proceedings of the 2006 workshop on Programming languages and analysis for security. . Trusted declassification:: high-level policy for a security-typed language”. PLAS '06: Proceedings of the 2006 workshop on Programming languages and analysis for security. 1-59593-374-3. 65-74. http://doi.acm.org/10.1145/1134744.1134757. ACM. New York, NY, USA.

[manjif] Stephen Chong, Andrew C. Myers, K. Vikram, and Lantian Zheng. Jif Reference Manual”. . Cornell University, Ithaca, NY, USA. http://www.cs.cornell.edu/jif/doc/jif-3.1.1/manual.html [last checked 10th March 2008].

[artmanaccess] Wikipedia Contributions. Mandatory Access Control”. . Wikimedia Foundation, Inc. http://en.wikipedia.org/wiki/Mandatory_access_control [last checked 13th March 2008].

[artjavasec] Sun Microsystems. Secure Coding Guidelines for the Java Programming Language”. . Sun Microsystems, Inc. http://java.sun.com/security/seccodeguide.html [last checked 8th March 2008].

[artdpa] . UK Data Protection Act 1998”. . Office of Public Sector Information.


Back to the blog

comments powered by Disqus

This Article's Tags

View the whole tag cloud