Declarative, Temporal, and Practical Programming with Capabilities

William R. Harris, Somesh Jha, Thomas W. Reps, Jonathan Anderson, Robert N. M. Watson

TL;DR

This paper introduces capweave, a tool that automatically rewrites C programs to use Capsicum capabilities, a security mechanism for fine-grained privilege control. capweave takes a declarative policy of desired capabilities and transforms the program, making it easier to write secure software with less manual effort and comparable performance to expert-written code.

What Problem Does This Paper Address?

Developing secure software is notoriously difficult. Traditional operating systems offer limited tools for applications to manage their own privileges, often requiring developers to prove complex properties like memory safety. Newer systems like Capsicum offer "capabilities" – essentially fine-grained access rights to resources – which allow for more robust security by limiting what code can do. However, manually instrumenting programs to correctly use these capability primitives is a complex and error-prone task, even for experienced developers. The core challenge is translating high-level security policies into the low-level, temporal sequences of system calls required by capability systems, while also preserving the program's original functionality.

Methods

The paper introduces capweave, a tool that tackles the "Capsicum policy-weaving problem." It operates in two main stages:

  1. Declarative Policy: A programmer defines a security policy using a declarative, temporal language. This policy specifies the capabilities a program should have at different points during its execution. This is a significant improvement over manually reasoning about the intricate temporal effects of capability primitives.
  2. Automatic Instrumentation: capweave takes the original, unwoven program (written in LLVM IR) and the declarative policy. It then uses an automata-theoretic approach, specifically a two-player safety game between an "Attacker" and a "Defender," to find a winning strategy for the Defender. This strategy is then translated into code that instruments the original program, inserting Capsicum system calls (primitives) at the appropriate locations to enforce the policy. The system is designed to be adaptable to new Capsicum primitives by simply updating a formal description of Capsicum's semantics.

Datasets

Not discussed in the paper. The paper focuses on applying capweave to existing UNIX utilities.

Key Insights and Ideas

  • Declarative Policies Simplify Security: The core insight is that expressing security requirements as declarative, temporal policies (what capabilities should be held) is far more manageable for developers than manually orchestrating low-level capability primitives.
  • Automata Games for Security Synthesis: The paper demonstrates the practical application of automata-theoretic safety games for automatically synthesizing security instrumentation. This is a powerful technique for bridging the gap between abstract policies and concrete code.
  • Separation of Concerns: capweave effectively separates the "what" (the policy) from the "how" (the instrumentation). This allows security architects to define policies and application developers to use capweave without needing deep expertise in the intricacies of Capsicum primitives.
  • Practicality of Capabilities: The work shows that capability systems, when coupled with effective tooling like capweave, can be used to secure real-world applications with minimal developer effort and acceptable performance overhead.

Key Results

  • Reduced Effort: Developers needed only a few lines of code annotations and a policy of 35-114 lines to rewrite complex UNIX utilities like bzip2, gzip, php-cgi, tar, tcpdump, and wget.
  • Efficiency: capweave itself is efficient, weaving programs in minutes (except for php-cgi which took 46 minutes), making it suitable for integration into build systems.
  • Performance: Programs woven by capweave incurred a runtime overhead of at most 4% on realistic workloads, comparable to programs manually instrumented by experts.
  • Effectiveness: The woven programs successfully mitigated known vulnerabilities and enforced the defined security policies. For example, a woven tcpdump could not open files containing secret keys, as dictated by its policy.

Limitations and Future Work

  • Undecidability: The general policy-weaving problem is undecidable. capweave uses a sound but incomplete approach.
  • Failure Diagnostics: The current version of capweave does not provide detailed diagnostic information when it fails to find a solution, which is a planned area for future work.
  • Programmer Study: The authors suggest a comprehensive programmer study is needed to fully evaluate the utility of capweave and related tools.
  • Policy Inference: Future work could involve tools that infer likely policies from system call usage, further reducing the burden on the programmer.
  • Cost Metrics: Extending capweave to use cost metrics could help find more optimal strategies, especially when dealing with costly primitives like fork.

Summary updated

Abstract

New operating systems, such as the Capsicum capability system, allow a programmer to write an application that satisfies strong security properties by invoking security- specific system calls at a few key points in the program. However, rewriting an application to invoke such system calls correctly is an error-prone process: even the Capsicum developers have reported difficulties in rewriting programs to correctly invoke system calls. This paper describes capweave, a tool that takes as input (i) an LLVM program, and (ii) a declarative policy of the possibly-changing capabilities that a program must hold during its execution, and rewrites the program to use Capsicum system calls to enforce the policy. Our experiments demonstrate that capweave can be applied to rewrite security-critical UNIX utilities to satisfy practical security policies. capweave itself works quickly, and the runtime overhead incurred in the programs that capweave produces is generally low for practical workloads.
BibTeX
@inproceedings{harris2013declarative,
  author = {William R. Harris and Somesh Jha and Thomas W. Reps and Jonathan Anderson and Robert N. M. Watson},
  title = {{Declarative, Temporal, and Practical Programming with Capabilities}},
  booktitle = {IEEE Symposium on Security and Privacy},
  year = {2013},
  doi = {10.1109/sp.2013.11},
}
Figure