Bounded Flexible Arrays in C
How to modernize C arrays for greater memory safety: a case-study in refactoring the Linux kernel and a look to the future
Kees Cook
C is not just a fancy assembler any more
Large projects written in C, especially those written close to the hardware layer like Linux, have long treated the language as a high-level assembler. Using C allowed for abstracting away much of the difficulty of writing directly in machine code while still providing easy low-level access to memory, registers, and CPU features. However, C has matured over the last half century, and many language features that improve robustness go unused in older codebases. This is especially true for arrays, where the historical lack of bounds checking has been a consistent source of security flaws.
Converting such codebases to use “modern” language features, like those in C99 (still from the prior millennium), can be a major challenge, but it is an entirely tractable problem. This post is a deep dive into an effort underway in the Linux kernel to make array index overflows (and more generally, buffer overflows) a thing of the past, where they belong. Our success hinges on replacing anachronistic array definitions with well-defined C99 flexible arrays. This approach can be used by developers to refactor C code, making it possible to leverage 21st century mitigations (like -fsanitize=bounds and FORTIFY_SOURCE), since such things can finally be cleanly applied to the modernized codebase.
The fraught history of arrays in C
For the compiler to successfully apply array index bounds checking, array sizes must be defined unambiguously, which is not always easy in C. Depending on the array definition, bounds checking falls roughly into three categories: fixed-sized arrays, dynamically-sized arrays, and pointer offsets. Each category of array definitions must be made unambiguous before the next, as they mostly build on top of each other. For example, if the compiler cannot protect a fixed-sized array, it certainly cannot protect a dynamically-sized array, and array indexing is just a specialized case of calculating a memory pointer offset.
Properly defined dynamically-sized arrays were introduced in C99 (int foo[]), and called “flexible arrays”. Before that, many C projects used the GNU extension of zero-length arrays (int foo[0]), which is not recognized by the C standard. This was done because, before the GNU extension, C projects would use single-element arrays (int foo[1]) which had several frustrating characteristics. (Using sizeof() on such a structure would include a single element as well, which would require additional handling to get allocation sizes to be accurate. This is not a problem for zero-element or true flexible arrays.)
However, due to yet more historical situations (e.g. struct sockaddr, which has a fixed-size trailing array that is not supposed to actually be treated as fixed-size), GCC and Clang actually treat all trailing arrays as flexible arrays. This behavior makes things even more problematic, since it becomes impossible to limit a flexible array heuristic to only 1-element or 0-element (i.e. zero-length) arrays. For example, a compiler can't tell the intent of variable's use here:
struct obj {
...
unsigned char bytes;
int variable[4];
};
Is it actually a 4 element array, or is it sized by the bytes member? As such, compilers have had to assume that trailing arrays must be intended to be dynamically sized (even though most are intended to be fixed-size).
To clear the way for sensible protection of fixed-size arrays, and to have a common framework for handling dynamically-sized arrays, Linux must have all the “fake” flexible array members replaced with actual C99 flexible array members so that the programmer's intent can actually be represented in an unambiguous way. With this done, -Warray-bounds (and similar things like __builtin_object_size()) will catch compile-time problems, and -fsanitize=bounds (and similar things like __builtin_dynamic_object_size()) can catch run-time problems.
Once fixed-sized arrays are protected, dynamically sized arrays can be protected as well, though this requires introducing a way to annotate structures that contain flexible arrays. Nearly all such structs also contain the count of allocated elements present in the flexible array:
struct obj {
...
unsigned short count;
struct foo items[]; /* Has "count" many "struct foo"s */
} *ptr;
Such structs therefore fully describe their contents at runtime (and are called “flexible array structures” from here on). In other words, their size can be determined at run-time as:
sizeof(*ptr) + sizeof(*ptr->items) * ptr->count
Teaching the compiler which struct member is associated with the count of a given flexible array member will allow -fsanitize=bounds and __builtin_dynamic_object_size() to reason about flexible array structure usage as well, covering all arrays in Linux with “known bounds”.
(Not covered here is the closely related work to tighten the FORTIFY_SOURCE implementation for the memcpy()-family of functions which also depends on making flexible array sizes unambiguous.)
Replacing “fake” flexible arrays
Compile-time diagnostics about the size of arrays use either internal value range checking or things similar to the FORTIFY_SOURCE macros (which use __builtin_object_size() for their implementations). This works well for arrays not at the end of the structure, but gets disabled for trailing arrays since the compiler must treat trailing arrays as flexible arrays (see struct sockaddr above). And for everything treated as a flexible array (i.e. dynamically sized), the compiler cannot know the array length at compile time, since it will be only known at runtime. To make such array declarations unambiguous (and therefore able to gain sane runtime bounds checking), compilers must gain an option to disable all “fake” flexible array heuristics, and treat only true flexible arrays as flexible arrays.
The creation of -fstrict-flex-arrays is now available in recent GCC and Clang builds, but any project using it will need to replace all fake flexible arrays with true flexible arrays first (to separate them from any fixed-size trailing arrays). This comes with several challenges.
Replace 0-length arrays
Most replacement of 0-length arrays with flexible arrays requires no special handling. Simply removing the “0” in the array declaration is sufficient. For example,
struct obj {
...
int flex[0];
};
becomes:
struct obj {
...
int flex[];
};
However, there are a few things of note that can go wrong with these conversions:
Changes to sizeof()
While sizeof(instance->flex) for a 0-length array returns 0, it becomes a compile-time failure once it becomes a true flexible array. This usually manifests within other complex macros that are examining the details of a given struct, and are usually hidden bugs that switching to a flexible array helps expose.
Pass by value
Converting to a true flexible array will expose any strange cases of trying to pass a flexible array struct by value. These are almost always a bug, so it's another case where a problem is exposed by cleaning up fake flexible arrays. For example:
net/core/flow_dissector.c: In function 'is_pppoe_ses_hdr_valid':
net/core/flow_dissector.c:898:13: note: the ABI of passing struct with a flexible array member has changed in GCC 4.4
898 | static bool is_pppoe_ses_hdr_valid(struct pppoe_hdr hdr)
| ^~~~~~~~~~~~~~~~~~~~~~
Flexible arrays in unions
C99 6.7.2.1 “Structure and union specifiers” #16 declares true flexible arrays may not be in unions nor otherwise empty structures: “As a special case, the last element of a structure with more than one named member may have an incomplete array type; this is called a flexible array member.”
However, this situation is allowed by the GNU “trailing array” extension, where such arrays are treated as flexible arrays. More importantly, flexible arrays (via the GNU extension) are used in unions in many places throughout Linux code. The C99 treatment of true flexible arrays appears to be only a definitional limitation (and likely just an oversight) since the restriction can be worked around with creative use of anonymous structs. For example, this will build:
struct obj {
...
union {
struct foo name1[0];
struct bar name2[0];
};
};
but this will not:
struct obj {
...
union {
struct foo name1[];
struct bar name2[];
};
};
<source>:5:22: error: flexible array member in union
5 | struct foo name1[];
| ^~~~~
But in both cases, the compiler treats name1 and name2 as flexible arrays. What will happily compile, though, is wrapping true flexible arrays in a struct that has at least 1 other non-true-flexible array, including an empty anonymous struct (i.e. taking up no size):
struct obj {
...
union {
struct {
struct { } __unused_member1;
struct foo name1[];
};
struct {
struct { } __unused_member2;
struct bar name2[];
};
};
};
Thankfully, this was wrapped in Linux with the DECLARE_FLEX_ARRAY() macro:
struct obj {
...
union {
DECLARE_FLEX_ARRAY(struct foo, name1);
DECLARE_FLEX_ARRAY(struct bar, name2);
};
};
which makes this much more readable. I hope to see future C standards eliminate this restriction.
Overlapping composite structure members
This is another case of a real bug being exposed by true flexible array usage, as it is possible to create an implicit union of a flexible array and something else by including a flexible array structure in another struct. For example:
struct inner {
...
int flex[0];
};
struct outer {
...
struct inner header;
int overlap;
...
} *instance;
Here, instance->overlap and instance->header.flex[0] share the same memory location. Whether or not this is intentional cannot be understood by the compiler. If it is a bug, then using a true flexible array will trigger a warning. If it's not a bug, rearranging the structures to use an actual union is needed (see above).
struct definition parsed by something other than a C compiler
If the converted struct is part of a source file that is parsed by something that is not a C compiler, it may not be prepared to handle empty square braces on arrays. For example, SWIG broke when the Linux Userspace API headers got converted. This is a known issue in SWIG, and can be worked around in various ways.
Replace 1-element arrays
Most 1-element array conversions are similar to 0-length array conversions, but with the effect that the surrounding structure's sizeof() changes. This leads to a few additional significant issues:
Size calculations
If a struct is used entirely internally to Linux, it is generally sufficient to make changes to both the struct and all size calculations, which will result in identical binary output. For example:
struct object {
...
int flex[1];
} *p;
p = kmalloc(sizeof(*p) + sizeof(p->flex[0]) * (count - 1)),
GFP_KERNEL);
the above count - 1 becomes just count now:
struct object {
...
int flex[];
} *p;
p = kmalloc(sizeof(*p) + sizeof(p->flex[0]) * count),
GFP_KERNEL);
If all size calculations are correctly adjusted, there should be no differences in the resulting allocation size, etc. If a discrepancy is found, it is going to be either a bug introduced by the conversion, or the discovery of an existing bug in the original size calculations.
Note that depending on the sizes of the structure, its flexible array element, and count, there is also the risk associated with arithmetic overflow. Linux uses the struct_size() macro to perform these calculations so that the result saturates to at most SIZE_MAX, which will cause an allocation failure rather than wrapping around. So the best way to perform this allocation would be:
p = kmalloc(struct_size(p, flex, count), GFP_KERNEL);
Padding and interface sizes
When a structure definition is also used by a codebase we don't control (e.g. firmware, userspace, virtualization), changing its layout or sizeof() may break such code. Specifically, it may break its ability to communicate correctly with the kernel across the shared interface. Such structures cannot suddenly lose the single element of its trailing array. In these cases, a new member needs to be used for kernel code, explicitly keeping the original member for backward compatibility. For example:
struct object {
...
int flex[1];
};
becomes:
struct object {
...
union {
int flex[1];
DECLARE_FLEX_ARRAY(int, data);
};
};
Now the kernel will only use the newly named data member (and gain any potential bounds checking protections from the compiler), and external code that shares this structure definition can continue to use the flex member, all without changing the size of the structure.
This has the downside of needing to change the member name throughout Linux. However, if the other side of the interface doesn't actually use the original member, we can avoid this. We can convert the member to a flexible array and add explicit padding instead. This would mean no collateral changes with the member name in Linux are needed:
struct object {
...
union {
int __padding;
DECLARE_FLEX_ARRAY(int, flex);
};
};
Replace multi-element arrays
In the cases of trailing arrays with larger element counts, the usage needs to be even more carefully studied. Most problems end up looking very similar to 1-element interface conversions above. For example, if there is some hardware interface that returns at least 4 bytes for an otherwise dynamically sized array, the conversion would start from here:
struct object {
...
unsigned char data[4];
};
which becomes:
struct object {
...
union {
unsigned char __padding[4];
DECLARE_FLEX_ARRAY(unsigned char, data);
};
};
Enable -Warray-bounds
With all fixed-size array bounds able to be determined at build time, -Warray-bounds can actually perform the checking, keeping provably bad code out of Linux. (This option is already part of -Wall, which Linux isn't quite able to use itself yet, but is strongly recommended for other C projects.) As a reminder, optimization level will impact this option. The kernel is built with -O2, which is likely the right choice for most C projects.
Enable -Wzero-length-array
If all zero length arrays have been removed from the code, future uses can be kept out of the code by using -Wzero-length-array. This option is currently only available in Clang, and will warn when finding the definition of such structure members, rather than warning when they are accessed in code. Because of this, it is unlikely to ever be enabled in Linux since some array sizes are constructed from build configurations, and may drop to 0 when they are unused (i.e. they were never used as flexible arrays). As such, it is sufficient to use -fstrict-flex-arrays (see below) and -Warray-bounds.
Enable -fstrict-flex-arrays
Once all the fake flexible arrays have been converted to true flexible arrays, the remaining fixed-sized trailing arrays can start being treated as actually fixed-size by enabling -fstrict-flex-arrays. Future attempts to add fake flexible arrays to the code will then elicit warnings as part of the existing diagnostics from -Warray-bounds, since all fake flexible arrays are now treated as fixed-size arrays. (Note that this option sees the subset of 0-length arrays caught by -Wzero-length-array when they are actually used in the code, so -Wzero-length-array may be redundant.)
Coming soon: annotate bounds of flexible arrays
With flexible arrays now a first-class citizen in Linux and the compilers, it becomes possible to extend their available diagnostics. What the compiler is missing is knowledge of how the length of a given flexible array is tracked. For well-described flexible array structs, this means associating the member holding the element count with the flexible array member. This idea is not new, though prior implementation proposals have wanted to make changes to the C language syntax. A simpler approach is the addition of struct member attributes, and is under discussion and early development by both the GCC and Clang developer communities.
Add __attribute__((__counted_by__(member)))
In order to annotate flexible arrays, a new attribute could be used to describe the relationship between struct members. For example:
struct object {
...
signed char items;
...
int flex[];
} *p;
becomes:
struct object {
...
signed char items;
...
int flex[] __attribute__((__counted_by__(items)));
} *p;
This would allow -fsanitize=bounds to check for out-of-bounds accesses. For example, given the above annotation, each of the marked access into p->flex should trap:
sum += p->flex[-1]; // trap all negative indexes
sum += p->flex[128]; // trap when index larger than bounds type
sum += p->flex[0]; // trap when p->items <= 0
sum += p->flex[5]; // trap when p->items <= 5
sum += p->flex[idx]; // trap when p->items <= idx || idx < 0
The type associated with the bounds check (signed char in the example above) should perhaps be required to be an unsigned type, but Linux has so many counters implemented as int that it becomes an additional refactoring burden to change these to unsigned, especially since sometimes they are sneakily being used with negative values in some other part of the code. Better to leave them as-is (though perhaps emit a warning), and just add a negativity check at access time. Switching the counter to unsigned then potentially becomes a small performance improvement.
Similar to -fsanitize=bounds above, __builtin_dynamic_object_size() will perform the expected calculations with the items member as the basis for the resulting size (and where values less than 0 are considered to be 0 to avoid pathological calculations):
p->items = 5;
assert(__builtin_dynamic_object_size(p, 1) ==
sizeof(*p) + 5 * sizeof(*p->flex));
assert(__builtin_dynamic_object_size(p->flex, 1) ==
5 * sizeof(*p->flex));
assert(__builtin_dynamic_object_size(&p->flex[0], 1) ==
sizeof(*p->flex));
assert(__builtin_dynamic_object_size(&p->flex[2], 0) ==
3 * sizeof(*p->flex));
p->items = -10;
assert(__builtin_dynamic_object_size(p, 0) == sizeof(*p));
assert(__builtin_dynamic_object_size(p, 1) == sizeof(*p));
assert(__builtin_dynamic_object_size(p->flex, 1) == 0);
assert(__builtin_dynamic_object_size(&p->flex[2], 1) == 0);
Additional attributes may be needed if structures explicitly use byte counts rather than element counts.
Scope considerations
Composite structures need to be able to define __counted_by__ across struct boundaries:
struct object {
...
char items;
...
struct inner {
...
int flex[] __attribute__((__counted_by__(.items)));
};
} *ptr;
This may mean passing &ptr->inner to a function will lose the bounds knowledge, but it may be possible to automatically include a bounds argument as an invisible function argument, as any function able to understand the layout of struct inner must by definition have visibility into the definition of struct object. For example, with this:
struct object instance;
...
func(&instance.inner);
...
void func(struct inner *ptr) {
...
ptr->flex[foo]; /* "items" is not scope */
...
}
The prototype could either be rejected due to lack of available scope, or could be automatically converted into passing the outer object pointer with an injected scope:
void func(struct object *__ptr) {
struct inner *ptr = &__ptr->inner;
...
ptr->flex[foo]; /* __ptr->items is in scope */
...
}
Annotate kernel flexible array structs
With the compiler attribute available, all of Linux's flexible arrays can be updated to include the annotation, and CONFIG_FORTIFY_SOURCE can be expanded to use __builtin_dynamic_object_size().
Replace DECLARE_FLEX_ARRAY with DECLARE_BOUNDED_ARRAY
Most uses of DECLARE_FLEX_ARRAY() can be replaced with DECLARE_BOUNDED_ARRAY(), explicitly naming the expected flex array bounds member. For example, if we had:
struct obj {
...
int items;
...
union {
DECLARE_FLEX_ARRAY(struct foo, name1);
DECLARE_FLEX_ARRAY(struct bar, name2);
};
};
it would become:
struct obj {
...
int items;
...
union {
DECLARE_BOUNDED_ARRAY(struct foo, name1, items);
DECLARE_BOUNDED_ARRAY(struct bar, name2, items);
};
};
Add manual annotations
Any flexible array structures not already using DECLARE_BOUNDED_ARRAY() can be annotated manually with the new attribute. For example, assuming the proposed __attribute__((__counted_by__(member))) is wrapped in a macro named __counted_by():
struct obj {
...
int items;
...
int flex[];
};
becomes:
struct obj {
...
int items;
...
int flex[] __counted_by(items);
};
Future work: expand attribute beyond arrays
It will also be possible to use the new attribute on pointers and function arguments as well as flexible arrays. All the same details are available, though there would be the obvious differences for enclosing structure sizes, as the pointers are aimed (usually) outside the struct itself. Regardless, having it be possible to check offsets and inform __builtin_dynamic_object_size() would allow for several more places where runtime checking could be possible. For example, given this:
struct object {
...
unsigned char items;
...
int *data __attribute__((__counted_by__(items)));
...
} *p;
It should be possible to detect sizing information:
p->items = 5;
assert(__builtin_dynamic_object_size(p->data, 1) ==
5 * sizeof(*p->data));
assert(__builtin_dynamic_object_size(*p->data, 1) ==
sizeof(*p->data));
assert(__builtin_dynamic_object_size(*p->data, 0) ==
5 * sizeof(*p->data));
And it should be possible to trap on the following bad accesses:
int *ptr = p->data;
sum += ptr[-1]; // trap all negative indexes
sum += ptr[500]; // trap when index larger than bounds type
sum += ptr[0]; // trap when p->items <= 0
sum += ptr[5]; // trap when p->items <= 5
ptr += 5; // don't trap yet: allow ptr++ in a for loop
sum += *ptr; // trap when p->items <= 5
A safer code base
A C codebase that has refactored all of its arrays into proper flexible arrays can now finally build by using:
-Warray-bounds
-fstrict-flex-arrays
-fsanitize=bounds
-fsanitize-undefined-trap-on-error
-D_FORTIFY_SOURCE=3
With this, the burdens of C array index bounds checking will have been shifted to the toolchain, and array index overflow flaw exploitation can be a thing of the past, reducing severity to a simple denial of service (assuming the traps aren't handled gracefully). For the next trick, new code can be written in a language that is memory safe to start with (e.g. Rust).
Acknowledgements
Thanks to many people who gave me feedback on this post: Nick Desaulniers, Gustavo A. R. Silva, Bill Wendling, Qing Zhao, Kara Olive, Chris Palmer, Steven Rostedt, Allen Webb, Julien Voisin, Guenter Roeck, Evan Benn, Seth Jenkins, Alexander Potapenko, Ricardo Ribalda, and Kevin Chowski.
Discussion
Please join this thread with your thoughts, comments, and corrections. :)