article

Open access

Computability classes for enforcement mechanisms

Authors:

Kevin W. Hamlen,

Greg Morrisett,

Fred B. SchneiderAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 28, Issue 1

Pages 175 - 205

https://doi.org/10.1145/1111596.1111601

Published: 01 January 2006 Publication History

Abstract

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.

References

[1]

Anderson, J. 1972. Computer security technology planning study vols. I and III. Tech. Rep. ESD-TR-73-51, HQ Electronic Systems Division: Hanscom AFB, MA, Fort Washington, Pennsylvania. October.]]

[2]

Deutsch, P. and Grant, C. 1971. A flexible measurement tool for software systems. In Information Processing (Proceedings of the IFIP Congress). 320--326.]]

[3]

Erlingsson, Ú. and Schneider, F. B. 2000a. IRM enforcement of Java stack inspection. In IEEE Symposium on Security and Privacy. Oakland, California, 246--255.]]

[4]

Erlingsson, Ú. and Schneider, F. B. 2000b. SASI enforcement of security policies: A retrospective. In WNSP: New Security Paradigms Workshop. ACM Press.]]

[5]

Evans, D. and Twynman, A. 1999. Flexible policy-directed code safety. In IEEE Symposium on Security and Privacy. Oakland, California, 32--45.]]

[6]

Fong, P. W. L. 2004. Access control by tracking shallow execution history. In Proceedings of the 2004 IEEE Symposium on Security and Privacy. Berkeley, California, 43--55.]]

[7]

Gödel, K. 1931. Über formal unentscheidbare sätze der Principia Mathematica und verwandter Systeme. Monatshefte für Mathematik und Physik 38, 173--198.]]

[8]

Harrison, M. A., Ruzzo, W. L., and Ullman, J. D. 1976. Protection in operating systems. Comm. ACM 19, 8 (Aug.), 461--471.]]

[9]

Hopcroft, J. E. and Ullman, J. D. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.]]

[10]

Kiczales, G., Lamping, J., Medhdhekar, A., Maeda, C., Lopes, C., Loingtier, J.-M., and Irwin, J. 1997. Aspect-oriented programming. In European Conference on Object-Oriented Programming, M. Akşit and S. Matsuoka, Eds. Vol. 1241. Springer-Verlag, Berlin, Heidelberg, and New York, 220--242.]]

[11]

Kim, M., Kannon, S., Lee., I., and Sokolsky, O. 2001. Java-MaC: A run-time assurance tool for Java. In First International Workshop on Run-time Verification. Paris, France.]]

[12]

Lamport, L. 1977. Proving the correctness of multiprocess programs. IEEE Trans. Soft. Eng. SE-3 2, 125--143.]]

[13]

Lampson, B. 1971. Protection. In Proceedings of the 5th Symposium on Information Sciences and Systems. Princeton, New Jersey, 437--443.]]

[14]

Ligatti, J., Bauer, L., and Walker, D. 2003. Edit automata: Enforcement mechanisms for run-time security policies. Tech. Rep. TR-681-03, Princeton University, Princeton, New Jersey. May.]]

[15]

Ligatti, J., Bauer, L., and Walker, D. 2005. Enforcing non-safety security policies with program monitors. Tech. Rep. TR-720-05, Princeton University, Princeton, New Jersey. January.]]

[16]

Lindholm, T. and Yellin, F. 1999. The Java#8482; Virtual Machine Specification, second ed. Addison-Wesley.]]

[17]

Marcus, L. Fall 1989. The search for a unifying framework for computer security. IEEE Cipher, 55--63. Invited Panel Discussion Position Paper, Second Franconia Workshop on Foundations of Computer Security, June 11--14, 1989.]]

[18]

Morrisett, G., Crary, K., and Glew, N. 1999. From System F to Typed Assembly Language. ACM Trans. Prog. Lang. Syst. 21, 3 (May), 527--568.]]

[19]

Myers, A. C. 1999. Practical mostly-static information flow control. In Proceedings of the 26th ACM Symposium on Principles of Programming Languages. San Antonio, Texas, 228--241.]]

[20]

Nachenberg, C. 1997. Computer virus--antivirus coevolution. Comm. ACM 40, 1 (Jan.), 46--51.]]

[21]

Necula, G. 1997. Proof-Carrying Code. In 24th ACM Symposium on Principles of Programming Languages. Paris, France, 106--119.]]

[22]

Necula, G. C. and Lee, P. 1996. Safe kernel extensions without run-time checking. In Second Symposium on Operating Systems Design and Implementation (OSDI '96). USENIX, Berkeley, CA, USA, 229--243.]]

[23]

Necula, G. C. and Lee, P. 1998. The design and implementation of a certifying compiler. In Proceedings of the 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). 333--344.]]

[24]

Papadimitriou, C. H. 1995. Computational Complexity. Addison-Wesley.]]

[25]

Rees, J. and Clinger, W. 1991. Revised 4 report on the algorithmic language Scheme. Lisp Pointers 4, 3 (July--Sept.), 1--55.]]

[26]

Robben, W., Vanhaute, B., Joosen, W., and Verbaeten, P. 1999. Non-functional policies. Lecture Notes in Computer Science 1616, 74--92.]]

[27]

Schneider, F. B. 2000. Enforceable security policies. ACM Trans. Inform. Syst. Secur. 3, 1 (Feb.), 30--50.]]

[28]

Small, C. 1997. MiSFIT: A tool for constructing safe extensible C++ systems. In Proceedings of the Third USENIX Conference on Object-Oriented Technologies. Portland, Oregon.]]

[29]

Turing, A. M. 1936. On computable numbers with an application to the Entscheidungs-problem. In Proceedings of the London Mathematical Society. vol. 2. 42, 230--265.]]

[30]

Viswanathan, M. 2000. Foundations for the run-time analysis of software systems. Ph.D. thesis, University of Pennsylvania.]]

[31]

Wahbe, R., Lucco, S., Anderson, T. E., and Graham, S. L. 1993. Efficient software-based fault isolation. In Proceedings of the 14th ACM Symposium on Operating Systems Principles. 203--216.]]

[32]

Ware, W. 1979. Security controls for computer systems. Tech. Rep. R-609-1, Rand Corp. October.]]

Cited By

Basin DDebois SHildebrandt T(2024)Proactive enforcement of provisions and obligationsJournal of Computer Security10.3233/JCS-21007832:3(247-289)Online publication date: 17-Jun-2024
https://doi.org/10.3233/JCS-210078
Bauman EDuan JHamlen KLin Z(2023)Renewable Just-In-Time Control-Flow IntegrityProceedings of the 26th International Symposium on Research in Attacks, Intrusions and Defenses10.1145/3607199.3607239(580-594)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3607199.3607239
Taleb RHallé SKhoury R(2023)A modular pipeline for enforcement of security properties at runtimeAnnals of Telecommunications10.1007/s12243-023-00952-z78:7-8(429-457)Online publication date: 17-Apr-2023
https://doi.org/10.1007/s12243-023-00952-z
Show More Cited By

Recommendations

Run-Time Enforcement of Nonsafety Policies

A common mechanism for ensuring that software behaves securely is to monitor programs at run time and check that they dynamically adhere to constraints specified by a security policy. Whenever a program monitor detects that untrusted software is ...
Certified In-lined Reference Monitoring on .NET
PLAS '06: Proceedings of the 2006 workshop on Programming languages and analysis for security

MOBILE is an extension of the .NET Common Intermediate Language that supports certified In-Lined Reference Monitoring. Mobile programs have the useful property that if they are well-typed with respect to a declared security policy, then they are ...
Execution monitoring enforcement for limited-memory systems
PST '06: Proceedings of the 2006 International Conference on Privacy, Security and Trust: Bridge the Gap Between PST Technologies and Business Services

Recently, attention has been given to formally characterize security policies that are enforceable by different kinds of security mechanisms. Since execution monitoring (EM) is a ubiquitous technique for enforcing security policies, this class of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 28, Issue 1

January 2006

205 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/1111596

Issue’s Table of Contents

Copyright © 2006 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2006

Published in TOPLAS Volume 28, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

152
Total Citations
View Citations
1,000
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)10

Reflects downloads up to 04 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Basin DDebois SHildebrandt T(2024)Proactive enforcement of provisions and obligationsJournal of Computer Security10.3233/JCS-21007832:3(247-289)Online publication date: 17-Jun-2024
https://doi.org/10.3233/JCS-210078
Bauman EDuan JHamlen KLin Z(2023)Renewable Just-In-Time Control-Flow IntegrityProceedings of the 26th International Symposium on Research in Attacks, Intrusions and Defenses10.1145/3607199.3607239(580-594)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3607199.3607239
Taleb RHallé SKhoury R(2023)A modular pipeline for enforcement of security properties at runtimeAnnals of Telecommunications10.1007/s12243-023-00952-z78:7-8(429-457)Online publication date: 17-Apr-2023
https://doi.org/10.1007/s12243-023-00952-z
Araujo FAyoade GAl-Naami KGao YHamlen KKhan L(2021)Crook-sourced intrusion detection as a serviceJournal of Information Security and Applications10.1016/j.jisa.2021.10288061:COnline publication date: 1-Sep-2021
https://dl.acm.org/doi/10.1016/j.jisa.2021.102880
Yilmaz FSridhar MMohanty ATendulkar VHamlen K(2021)A fine-grained classification and security analysis of web-based virtual machine vulnerabilitiesComputers & Security10.1016/j.cose.2021.102246105(102246)Online publication date: Jun-2021
https://doi.org/10.1016/j.cose.2021.102246
Taleb RHallé SKhoury R(2021)A Modular Runtime Enforcement Model Using Multi-tracesFoundations and Practice of Security10.1007/978-3-031-08147-7_19(283-302)Online publication date: 7-Dec-2021
https://dl.acm.org/doi/10.1007/978-3-031-08147-7_19
Katz G(2021)Augmenting Deep Neural Networks with Scenario-Based Guard RulesModel-Driven Engineering and Software Development10.1007/978-3-030-67445-8_7(147-172)Online publication date: 2-Feb-2021
https://doi.org/10.1007/978-3-030-67445-8_7
Xu XGhaffarinia MWang WHamlen KLin ZHeninger NTraynor P(2019)CONFIRMProceedings of the 28th USENIX Conference on Security Symposium10.5555/3361338.3361463(1805-1821)Online publication date: 14-Aug-2019
https://dl.acm.org/doi/10.5555/3361338.3361463
Pfeffer TGlesner SSion RPapamanthou C(2019)Timing-Sensitive Synchronization for Efficient Secure Multi-ExecutionProceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop10.1145/3338466.3358914(153-164)Online publication date: 11-Nov-2019
https://dl.acm.org/doi/10.1145/3338466.3358914
Pfeffer TGöthel TGlesner SAhn GThuraisingham BKantarcioglu MKrishnan R(2019)Efficient and Precise Information Flow Control for Machine Code through Demand-Driven Secure Multi-ExecutionProceedings of the Ninth ACM Conference on Data and Application Security and Privacy10.1145/3292006.3300040(197-208)Online publication date: 13-Mar-2019
https://dl.acm.org/doi/10.1145/3292006.3300040
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents