1---
2layout: post
3title: "Security Advisory -- And how to catch integer overflows with template metaprogramming"
4author: kentonv
5---
6
7As the installation page has always stated, I do not yet recommend using Cap'n Proto's C++ library for handling possibly-malicious input, and will not recommend it until it undergoes a formal security review. That said, security is obviously a high priority for the project. The security of Cap'n Proto is in fact essential to the security of [Sandstorm.io](https://sandstorm.io), Cap'n Proto's parent project, in which sandboxed apps communicate with each other and the platform via Cap'n Proto RPC.
8
9A few days ago, the first major security bugs were found in Cap'n Proto C++ -- two by security guru [Ben Laurie](http://en.wikipedia.org/wiki/Ben_Laurie) and one by myself during subsequent review (see below). You can read details about each bug in our new [security advisories directory](https://github.com/sandstorm-io/capnproto/tree/master/security-advisories):
10
11* [Integer overflow in pointer validation.](https://github.com/sandstorm-io/capnproto/tree/master/security-advisories/2015-03-02-0-c++-integer-overflow.md)
12* [Integer underflow in pointer validation.](https://github.com/sandstorm-io/capnproto/tree/master/security-advisories/2015-03-02-1-c++-integer-underflow.md)
13* [CPU usage amplification attack.](https://github.com/sandstorm-io/capnproto/tree/master/security-advisories/2015-03-02-2-all-cpu-amplification.md)
14
15I have backported the fixes to the last two release branches -- 0.5 and 0.4:
16
17- Release 0.5.1.1: [source](https://capnproto.org/capnproto-c++-0.5.1.1.tar.gz), [win32](https://capnproto.org/capnproto-c++-win32-0.5.1.1.zip)
18- Release 0.4.1.1: [source](https://capnproto.org/capnproto-c++-0.4.1.1.tar.gz)
19
20Note that we added a "nano" component to the version number (rather than use 0.5.2/0.4.2) to indicate that this release is ABI-compatible with the previous release. If you are linking Cap'n Proto as a shared library, you only need to update the library, not re-compile your app.
21
22To be clear, the first two bugs affect only the C++ implementation of Cap'n Proto; implementations in other languages are likely safe. The third bug probably affects all languages, and as of this writing only the C++ implementation (and wrappers around it) is fixed. However, this third bug is not as serious as the other two.
23
24### Preventative Measures
25
26It is our policy that any time a security problem is found, we will not only fix the problem, but also implement new measures to prevent the class of problems from occurring again. To that end, here's what we're doing doing to avoid problems like these in the future:
27
281. A fuzz test of each pointer type has been added to the standard unit test
29   suite.
302. We will additionally add fuzz testing with American Fuzzy Lop to our
31   extended test suite.
323. In parallel, we will extend our use of template metaprogramming for
33   compile-time unit analysis (kj::Quantity in kj/units.h) to also cover
34   overflow detection (by tracking the maximum size of an integer value across
35   arithmetic expressions and raising an error when it overflows). More on this
36   below.
374. We will continue to require that all tests (including the new fuzz test) run
38   cleanly under Valgrind before each release.
395. We will commission a professional security review before any 1.0 release.
40   Until that time, we continue to recommend against using Cap'n Proto to
41   interpret data from potentially-malicious sources.
42
43I am pleased to report that measures 1, 2, and 3 all detected both integer overflow/underflow problems, and AFL additionally detected the CPU amplification problem.
44
45### Integer Overflow is Hard
46
47Integer overflow is a nasty problem.
48
49In the past, C and C++ code has been plagued by buffer overrun bugs, but these days, systems engineers have mostly learned to avoid them by simply never using static-sized buffers for dynamically-sized content. If we don't see proof that a buffer is the size of the content we're putting in it, our "spidey sense" kicks in.
50
51But developing a similar sense for integer overflow is hard. We do arithmetic in code all the time, and the vast majority of it isn't an issue. The few places where overflow can happen all too easily go unnoticed.
52
53And by the way, integer overflow affects many memory-safe languages too! Java and C# don't protect against overflow. Python does, using slow arbitrary-precision integers. JavaScript doesn't use integers, and is instead succeptible to loss-of-precision bugs, which can have similar (but more subtle) consequences.
54
55While writing Cap'n Proto, I made sure to think carefully about overflow and managed to correct for it most of the time. On learning that I missed a case, I immediately feared that I might have missed many more, and wondered how I might go about systematically finding them.
56
57Fuzz testing -- e.g. using [American Fuzzy Lop](http://lcamtuf.coredump.cx/afl/) -- is one approach, and is indeed how Ben found the two bugs he reported. As mentioned above, we will make AFL part of our release process in the future. However, AFL cannot really _prove_ anything -- it can only try lots of possibilities. I want my compiler to refuse to compile arithmetic which might overflow.
58
59### Proving Safety Through Template Metaprogramming
60
61C++ Template Metaprogramming is powerful -- many would say _too_ powerful. As it turns out, it's powerful enough to do what we want.
62
63I defined a new type:
64
65{% highlight C++ %}
66template <uint64_t maxN, typename T>
67class Guarded {
68  // Wraps T (a basic integer type) and statically guarantees
69  // that the value can be no more than `maxN` and no less than
70  // zero.
71
72  static_assert(maxN <= T(kj::maxValue), "possible overflow detected");
73  // If maxN is not representable in type T, we can no longer
74  // guarantee no overflows.
75
76public:
77  // ...
78
79  template <uint64_t otherMax, typename OtherT>
80  inline constexpr Guarded(const Guarded<otherMax, OtherT>& other)
81      : value(other.value) {
82    // You cannot construct a Guarded from another Guarded
83    // with a higher maximum.
84    static_assert(otherMax <= maxN, "possible overflow detected");
85  }
86
87  // ...
88
89  template <uint64_t otherMax, typename otherT>
90  inline constexpr Guarded<guardedAdd<maxN, otherMax>(),
91                           decltype(T() + otherT())>
92      operator+(const Guarded<otherMax, otherT>& other) const {
93    // Addition operator also computes the new maximum.
94    // (`guardedAdd` is a constexpr template that adds two
95    // constants while detecting overflow.)
96    return Guarded<guardedAdd<maxN, otherMax>(),
97                   decltype(T() + otherT())>(
98        value + other.value, unsafe);
99  }
100
101  // ...
102
103private:
104  T value;
105};
106{% endhighlight %}
107
108So, a `Guarded<10, int>` represents a `int` which is statically guaranteed to hold a non-negative value no greater than 10. If you add a `Guarded<10, int>` to `Guarded<15, int>`, the result is a `Guarded<25, int>`. If you try to initialize a `Guarded<10, int>` from a `Guarded<25, int>`, you'll trigger a `static_assert` -- the compiler will complain. You can, however, initialize a `Guarded<25, int>` from a `Guarded<10, int>` with no problem.
109
110Moreover, because all of `Guarded`'s operators are inline and `constexpr`, a good optimizing compiler will be able to optimize `Guarded` down to the underlying primitive integer type. So, in theory, using `Guarded` has no runtime overhead. (I have not yet verified that real compilers get this right, but I suspect they do.)
111
112Of course, the full implementation is considerably more complicated than this. The code has not been merged into the Cap'n Proto tree yet as we need to do more analysis to make sure it has no negative impact. For now, you can find it in the [overflow-safe](https://github.com/sandstorm-io/capnproto/tree/overflow-safe) branch, specifically in the second half of [kj/units.h](https://github.com/sandstorm-io/capnproto/blob/overflow-safe/c++/src/kj/units.h). (This header also contains metaprogramming for compile-time unit analysis, which Cap'n Proto has been using since its first release.)
113
114### Results
115
116I switched Cap'n Proto's core pointer validation code (`capnp/layout.c++`) over to `Guarded`. In the process, I found:
117
118* Several overflows that could be triggered by the application calling methods with invalid parameters, but not by a remote attacker providing invalid message data. We will change the code to check these in the future, but they are not critical security problems.
119* The overflow that Ben had already reported ([2015-03-02-0](https://github.com/sandstorm-io/capnproto/tree/master/security-advisories/2015-03-02-0-c++-integer-overflow.md)). I had intentionally left this unfixed during my analysis to verify that `Guarded` would catch it.
120* One otherwise-undiscovered integer underflow ([2015-03-02-1](https://github.com/sandstorm-io/capnproto/tree/master/security-advisories/2015-03-02-1-c++-integer-underflow.md)).
121
122Based on these results, I conclude that `Guarded` is in fact effective at finding overflow bugs, and that such bugs are thankfully _not_ endemic in Cap'n Proto's code.
123
124With that said, it does not seem practical to change every integer throughout the Cap'n Proto codebase to use `Guarded` -- using it in the API would create too much confusion and cognitive overhead for users, and would force application code to be more verbose. Therefore, this approach unfortunately will not be able to find all integer overflows throughout the entire library, but fortunately the most sensitive parts are covered in `layout.c++`.
125
126### Why don't programming languages do this?
127
128Anything that can be implemented in C++ templates can obviously be implemented by the compiler directly. So, why have so many languages settled for either modular arithmetic or slow arbitrary-precision integers?
129
130Languages could even do something which my templates cannot: allow me to declare relations between variables. For example, I would like to be able to declare an integer whose value is less than the size of some array. Then I know that the integer is a safe index for the array, without any run-time check.
131
132Obviously, I'm not the first to think of this. "Dependent types" have been researched for decades, but we have yet to see a practical language supporting them. Apparently, something about them is complicated, even though the rules look like they should be simple enough from where I'm standing.
133
134Some day, I would like to design a language that gets this right. But for the moment, I remain focused on [Sandstorm.io](https://sandstorm.io). Hopefully someone will beat me to it. Hint hint.
135