pith. sign in

arxiv: 2606.08119 · v1 · pith:SI62LS6Snew · submitted 2026-06-06 · 💻 cs.CR · cs.OS

Policy Description Language for Authorization using Logic-Based Programming

Masaki Hashimoto , Mira Kim , Hidenori Tsuji , Hidehiko Tanaka This is my paper

Pith reviewed 2026-06-27 19:27 UTC · model grok-4.3

classification 💻 cs.CR cs.OS
keywords policy description languageaccess controlDatalogSELinuxauthorizationlogic programmingDefense-in-Depth
0
0 comments X

The pith

A Datalog-based policy language expresses fine-grained access control rules including dynamic process states and applies it to SELinux.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors claim that existing policy description languages cannot capture access control models at the needed level of detail for multi-layer defenses. They introduce a new language that treats diverse conditions, such as the runtime status of application processes, as inputs to authorization decisions and encodes the language in Datalog. The language is then used to write the SELinux policy, after which the authors assess whether the result is valid and sufficiently expressive. A reader would care if this approach yields policies that respond more precisely to changing system conditions than prior languages allow.

Core claim

We propose a policy description language which can designate many kinds of conditions for access control, such as the dynamic status of an application process, as an element of decision data, and implement it in Datalog. Using the proposed language, we compose the policy of SELinux, which is a major implementation achieving the multi-layer defense, and we confirm the advantages of the proposed language by evaluating its validity and expressiveness.

What carries the argument

The Datalog implementation of the policy description language, which encodes authorization rules and evaluates conditions including dynamic process states as decision data.

If this is right

  • SELinux policies can be written and checked using the new language.
  • Access decisions can incorporate dynamic application process status directly.
  • The language supports the fine-grained granularity required for Defense-in-Depth.
  • Validity and expressiveness can be confirmed through direct composition and testing of real policies.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The logic-programming base could support automated tools that search for policy conflicts or redundancies.
  • The same structure might be applied to other mandatory access control systems that track runtime state.
  • Policy updates could be performed by editing Datalog facts rather than rewriting imperative rules.
  • Runtime performance under high request loads would need separate measurement to confirm practicality.

Load-bearing premise

That earlier policy languages are unable to express access control models at proper granularity and that encoding the new language in Datalog will fix this without creating new limitations.

What would settle it

A concrete SELinux policy rule that cannot be written in the proposed language, or a measurable increase in evaluation time or memory use relative to the original SELinux policy engine.

read the original abstract

Recently, with the impossibility of eradicating the vulnerabilities of information systems, we must prepare for the occurrence of the security incident by the multi-layer defense called the Defense-in-Depth strategy. In the multi-layer defense, it is important to authorize accesses in fine-grained granularity to compose each layer effectively, and many access control models are proposed to follow them. However, policy description languages proposed so far cannot express the models appropriately in proper granularity. In this paper, we propose a policy description language which can designate many kinds of conditions for access control, such as the dynamic status of an application process, as an element of decision data, and implement it in Datalog. Using the proposed language, we compose the policy of SELinux, which is a major implementation achieving the multi-layer defense, and we confirm the advantages of the proposed language by evaluating its validity and expressiveness.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript proposes a policy description language implemented in Datalog that supports fine-grained authorization decisions, including dynamic conditions such as the status of application processes. It encodes SELinux allow/deny rules as predicates over subjects, objects, operations, and process-state facts, composes policies for this system, and evaluates validity and expressiveness through demonstration that selected policies can be expressed without semantic loss.

Significance. If the encoding preserves original SELinux semantics and the language successfully incorporates dynamic process status at the claimed granularity, the work supplies a constructive logic-programming approach to multi-layer access control. The full manuscript provides the syntax definition, encoding details, and demonstration absent from the abstract, so the initial unverifiability concern does not land. The explicit encoding of real policies is a clear strength of the proposal.

major comments (2)
  1. [§5] §5 (Evaluation): the validity and expressiveness evaluation is performed by composing selected SELinux policies and confirming they can be expressed, but contains no explicit example of a dynamic process-status condition that prior languages cannot capture at equivalent granularity; this is load-bearing for the claim that advantages are confirmed.
  2. [§3] §3 (Language Definition): the extension allowing dynamic process status as decision data is defined via additional predicates, yet the manuscript does not specify how fact updates or stratification are handled to preserve Datalog's termination properties, which directly affects the practicality of the dynamic-condition claim.
minor comments (3)
  1. [§2] §2 (Related Work): additional citations to recent Datalog-based authorization systems would help situate the contribution.
  2. Notation throughout: predicate names and variable conventions are introduced inline but would benefit from a consolidated table of symbols.
  3. [Conclusion] Conclusion: the discussion of limitations or scalability considerations for real-time policy evaluation is absent.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback and positive overall assessment. We address the two major comments below and will incorporate clarifications and additions in a revised manuscript.

read point-by-point responses

  1. Referee: [§5] §5 (Evaluation): the validity and expressiveness evaluation is performed by composing selected SELinux policies and confirming they can be expressed, but contains no explicit example of a dynamic process-status condition that prior languages cannot capture at equivalent granularity; this is load-bearing for the claim that advantages are confirmed.

    Authors: We agree that an explicit, concrete example of a dynamic process-status condition (e.g., conditioning an access decision on whether a process is currently executing in a verified/trusted runtime state that cannot be statically encoded) would better substantiate the claimed advantage over prior languages. The current evaluation focuses on faithful encoding of existing SELinux policies, which are largely static. In the revision we will add such an example to §5, drawn from the language's support for process-state predicates, to demonstrate a case where equivalent granularity is not achievable in standard SELinux or other non-dynamic policy languages. revision: yes

  2. Referee: [§3] §3 (Language Definition): the extension allowing dynamic process status as decision data is defined via additional predicates, yet the manuscript does not specify how fact updates or stratification are handled to preserve Datalog's termination properties, which directly affects the practicality of the dynamic-condition claim.

    Authors: The dynamic process-status facts are modeled as extensional (EDB) predicates supplied at runtime by an external monitor; the policy rules themselves are written as a stratified Datalog program (negation is confined to strata that do not depend on the dynamic predicates in a recursive manner). This preserves the standard termination guarantee of stratified Datalog. We acknowledge that the manuscript does not explicitly state the stratification invariant or the update mechanism. In the revision we will add a short subsection in §3 clarifying that dynamic facts remain EDB, that the rule set is stratified, and that updates occur outside the deductive fixpoint computation. revision: yes

Circularity Check

0 steps flagged

No significant circularity; proposal is constructive and self-contained

full rationale

The paper presents a constructive proposal for a Datalog-based policy description language to express fine-grained access control conditions (e.g., dynamic process status) for SELinux-style policies. The abstract and provided text describe defining an extended syntax, encoding rules as predicates, and evaluating validity/expressiveness via direct composition of existing policies. No equations, fitted parameters, predictions, or load-bearing self-citations appear that would reduce the central claim to its own inputs by construction. The work does not invoke uniqueness theorems, smuggle ansatzes, or rename known results; it is a direct encoding and demonstration rather than a comparative or derived result. This matches the default expectation of a non-circular proposal paper.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only abstract available; no free parameters, axioms, or invented entities can be identified from the provided text.

pith-pipeline@v0.9.1-grok · 5679 in / 1018 out tokens · 16373 ms · 2026-06-27T19:27:35.932094+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 11 canonical work pages

  1. [1]

    Bass and R

    T. Bass and R. Robichaux. Defense-in-depth revisited: qualitative risk analysis methodology for com- plex network-centric operations.Military Communications Conference, 2001. MILCOM 2001. Communi- cations for Network-Centric Operations: Creating the Information Force. IEEE, 1:64 – 70 vol.1, 2001. doi:10.1109/MILCOM.2001.985765

    work page doi:10.1109/milcom.2001.985765 2001

  2. [2]

    Integrating flexible support for security policies into the linux operating system

    Peter Loscocco and Stephen Smalley. Integrating flexible support for security policies into the linux operating system. InProceedings of the FREENIX Track: 2001 USENIX Annual Technical Conference, pages 29–42, Berkeley, CA, USA, 2001. USENIX Association. ISBN 1-880446-10-3

    2001

  3. [3]

    S. Ceri, G. Gottlob, and L. Tanca. What you always wanted to know about datalog (and never dared to ask).IEEE Transactions on Knowledge and Data Engineering, 1(1):146–166, Mar 1989. ISSN 1041-4347. doi:10.1109/69.43410. 10 Policy Description Language for Authorization using Logic-Based ProgrammingA PREPRINT

    work page doi:10.1109/69.43410 1989

  4. [4]

    Pereira, and Fernando Pereira

    David H D Warren, Luis M. Pereira, and Fernando Pereira. Prolog - the language and its implementation compared with lisp. InProceedings of the 1977 symposium on Artificial intelligence and programming languages, pages 109–115, New York, NY , USA, 1977. ACM. doi:http://doi.acm.org/10.1145/800228.806939

    work page doi:10.1145/800228.806939 1977

  5. [5]

    Role-based access control

    David F Ferraiolo and D Richard Kuhn. Role-based access control. In15th National Computer Security Conference, pages 13 – 16, Baltimore, MD, Jun 1992

    1992

  6. [6]

    An approach to dynamic domain and type enforcement.Lecture Notes in Computer Science, 1270:26–37, 1997

    J Tidswell and J Potter. An approach to dynamic domain and type enforcement.Lecture Notes in Computer Science, 1270:26–37, 1997

    1997

  7. [7]

    History-based access control and secure information flow.Lecture Notes in Computer Science, 3362:27–48, 2005

    A Banerjee and DA Naumann. History-based access control and secure information flow.Lecture Notes in Computer Science, 3362:27–48, 2005

    2005

  8. [8]

    The flask security architecture: System support for diverse security policies

    Ray Spencer, Secure Computing Corporation, Stephen Smalley, Peter Loscocco, National Security Agency, and Mike Hibler David Andersen. The flask security architecture: System support for diverse security policies. Inin Proceedings of The Eighth USENIX Security Symposium, pages 123–139, 1999

    1999

  9. [9]

    K. KaiGai. Security enhanced postgresql, 2006.http://code.google.com/p/sepgsql/

    2006

  10. [10]

    Design and implementation of the selinux policy management server

    Karl Macmillan, Joshua Brindle, Frank Mayer, Dave Caplan, Jason Tang, and Tresys Technology. Design and implementation of the selinux policy management server. InIn Proceedings of the Security Enhanced Linux Symposium, pages 1–6, 2006

    2006

  11. [11]

    On sdsi’s linked local name spaces.J

    Mart Abadi. On sdsi’s linked local name spaces.J. Comput. Secur., 6(1-2):3–21, 1998. ISSN 0926-227X

    1998

  12. [12]

    Ellison, B

    C. Ellison, B. Frantz, B. Lampson, R. Rivest, B. Thomas, and T. Ylonen.SPKI Certificate Theory, chapter 2693. RFC Editor, United States, 1999

    1999

  13. [13]

    Compliance checking in the policymaker trust management system

    Matt Blaze, Joan Feigenbaum, and Martin Strauss. Compliance checking in the policymaker trust management system. InFC ’98: Proceedings of the Second International Conference on Financial Cryptography, pages 254–274, London, UK, 1998. Springer-Verlag. ISBN 3-540-64951-4

    1998

  14. [14]

    Keromytis

    Matt Blaze, Joan Feigenbaum, and Angelos D. Keromytis. Keynote: Trust management for public-key infras- tructures (position paper). InProceedings of the 6th International Workshop on Security Protocols, pages 59–63, London, UK, 1999. Springer-Verlag. ISBN 3-540-65663-4

    1999

  15. [15]

    Design and semantics of a decentralized autho- rization language

    Moritz Becker, Cedric Fournet, and Andrew Gordon. Design and semantics of a decentralized autho- rization language. InCSF ’07: Proceedings of the 20th IEEE Computer Security Foundations Sym- posium, pages 3–15, Washington, DC, USA, 2007. IEEE Computer Society. ISBN 0-7695-2819-8. doi:http://dx.doi.org/10.1109/CSF.2007.18

    work page doi:10.1109/csf.2007.18 2007

  16. [16]

    Halpern and Vicky Weissman

    Joseph Y . Halpern and Vicky Weissman. Using first-order logic to reason about policies.ACM Trans. Inf. Syst. Secur., 11(4):1–41, 2008. ISSN 1094-9224. doi:http://doi.acm.org/10.1145/1380564.1380569

    work page doi:10.1145/1380564.1380569 2008

  17. [17]

    extensible access control markup language (xacml) version 2.0 core specification, 2005

    OASIS. extensible access control markup language (xacml) version 2.0 core specification, 2005. http://www. oasis-open.org/committees/xacml/

    2005

  18. [18]

    Sagonas, Terrance Swift, David Scott Warren, and Juliana Freire

    Prasad Rao, Konstantinos F. Sagonas, Terrance Swift, David Scott Warren, and Juliana Freire. Xsb: A system for effciently computing wfs. InLPNMR ’97: Proceedings of the 4th International Conference on Logic Programming and Nonmonotonic Reasoning, pages 431–441, London, UK, 1997. Springer-Verlag. ISBN 3-540-63255-7

    1997

  19. [19]

    Weidong Chen and David S. Warren. Tabled evaluation with delaying for general logic programs.J. ACM, 43(1): 20–74, 1996. ISSN 0004-5411. doi:http://doi.acm.org/10.1145/227595.227597

    work page doi:10.1145/227595.227597 1996

  20. [20]

    Weidong Chen, Michael Kifer, and David S. Warren. Hilog as a platform for database languages. InProceedings of the second international workshop on Database programming languages, pages 315–329, San Francisco, CA, USA, 1989. Morgan Kaufmann Publishers Inc. ISBN 1-55860-072-8

    1989

  21. [21]

    Dawson, C

    S. Dawson, C. R. Ramakrishnan, I. V . Ramakrishnan, K. Sagonas, S. Skiena, T. Swift, and D. S. Warren. Unification factoring for efficient execution of logic programs. InPOPL ’95: Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 247–258, New York, NY , USA,

  22. [22]

    ISBN 0-89791-692-1

    ACM. ISBN 0-89791-692-1. doi:http://doi.acm.org/10.1145/199448.199509

    work page doi:10.1145/199448.199509

  23. [23]

    Swi-prolog and the web.Theory Pract

    Jan Wielemaker, Zhisheng Huang, and Lourens Van der meij. Swi-prolog and the web.Theory Pract. Log. Program., 8(3):363–392, 2008. ISSN 1471-0684. doi:http://dx.doi.org/10.1017/S1471068407003237

    work page doi:10.1017/s1471068407003237 2008

  24. [24]

    Krzysztof R. Apt. Introduction to logic programming. Technical report, Austin, TX, USA, 1988

    1988

  25. [25]

    Brewer and M.J

    D.F.C. Brewer and M.J. Nash. The chinese wall security policy. InProceedings of IEEE Symposium on Security and Privacy, pages 206–214, May 1989. doi:10.1109/SECPRI.1989.36295. 11 Policy Description Language for Authorization using Logic-Based ProgrammingA PREPRINT

    work page doi:10.1109/secpri.1989.36295 1989

  26. [26]

    Tripathi

    Tanvir Ahmed and Anand R. Tripathi. Specification and verification of security requirements in a program- ming model for decentralized cscw systems.ACM Trans. Inf. Syst. Secur., 10(2):7, 2007. ISSN 1094-9224. doi:http://doi.acm.org/10.1145/1237500.1237503

    work page doi:10.1145/1237500.1237503 2007

  27. [27]

    R. S. Fabry. Capability-based addressing.Commun. ACM, 17(7):403–412, 1974. ISSN 0001-0782. doi:http://doi.acm.org/10.1145/361011.361070

    work page doi:10.1145/361011.361070 1974

  28. [28]

    Saltzer and M.D

    J.H. Saltzer and M.D. Schroeder. The protection of information in computer systems.Proceedings of the IEEE, 63(9):1278–1308, Sept. 1975. ISSN 0018-9219. 12

    1975