A precise characterization of those security policies enforceable by program rewriting is given. This also exposes and rectifies problems in prior work, yielding a better characterization of those security policies enforceable by execution monitors as well as a taxonomy of enforceable security policies. Some but not all classes can be identified with known classes from computational complexity theory. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 1515 Broadway, New York, NY 10036 USA, fax: +1 (212) 869-0481, or permissions@acm.org.  Extensible systems, such as web browsers, which download and run applet programs, or operating systems, which incorporate drivers for new devices, must ensure that their extensions behave in a manner consistent with the intentions of the system designer and its users. When unacceptable behavior goes unchecked, damage can result-not only to the system itself but also to connected systems. Security enforcement mechanisms are employed to prevent unacceptable behavior. Recently, attention has turned to formally characterizing types of enforcement mechanisms and identifying the classes of security policies they can enforce [Ligatti et al. 2003; Schneider 2000; Viswanathan 2000 ]. This work allows us to assess the power of different mechanisms, choose mechanisms well suited to particular security needs, identify kinds of attacks that might still succeed even after a given mechanism has been deployed, and derive meaningful completeness results for newly developed mechanisms. The abstract model for security policies developed by Schneider [2000] and refined by Viswanathan [2000] characterizes a class of policies meant to capture what could be effectively enforced through execution monitoring. Execution monitors are enforcement mechanisms that work by monitoring the computational steps of untrusted programs and intervening whenever execution is about to violate the security policy being enforced. Execution monitoring, however, can be viewed as an instance of the more general technique of program-rewriting, wherein the enforcement mechanism transforms untrusted programs before they are executed so as to render them incapable of violating the security policy to be enforced. To our knowledge, no characterization of the class of security policies enforceable by program-rewriting has been developed. Since numerous systems [Deutsch and Grant 1971; Small 1997; Wahbe et al. 1993; Schneider 2000a, 2000b; Evans and Twynman 1999] use program-rewriting in ways that go beyond what can be modeled as an execution monitor, a characterization of the class of policies enforceable by program-rewriters would be useful. So we here extend Schneider's and Viswanathan's model to characterize this new class of policies, the RWenforceable policies, corresponding to what can be effectively enforced through program-rewriting. Execution monitoring can be viewed as an instance of program-rewriting, so one would expect the class EM orig of policies characterized by Schneider and Viswanathan to be a subclass of the RW-enforceable policies. However, we show that surprisingly this is not the case; there are some policies in EM orig that are not enforceable by any program-rewriter. Our analysis of these policies shows that they cannot actually be enforced by an execution monitor either, revealing that EM orig actually constitutes an upper bound on the class of policies enforceable by execution monitors instead of an exact bound, as was previously thought. We then show that intersecting EM orig with the RW-enforceable policies yields exactly those policies that can actually be enforced by an execution monitor, the EM-enforceable policies. We proceed as follows. We establish a formal model of security enforcement in Section 2. Next, in Section 3 we use that model to characterize and relate
Hamlen et al. REF provided a taxonomy of the main security enforcement mechanisms classes.
Computability classes for enforcement mechanisms
TOPL
Computer Science