musl 1.1.16 fixes allocation arithmetic in regular expression matching

An allocator cannot reject an oversized request if the caller has already reduced it to a small integer by overflow. The security fix in musl 1.1.16 concerns that earlier calculation. Rich Felker's release announcement identifies a serious under-allocation bug in regexec, tracked as CVE-2016-8859. The release reaches the public archive on January 3 and also adds an s390x port. The regex correction is the part that most directly concerns the boundary between valid allocation calls and invalid storage calculations.

The versioned regular expression implementation shows why a check on the allocator's result cannot provide the entire defence. Before requesting storage, the matcher calculates several regions for its internal state. Those regions share one allocated block. The size calculation must account for each region, repeated tag storage and alignment padding before the allocator sees a byte count.

I regard this as one of the recurring costs of C's explicit storage model. A program can use an allocator correctly at the call boundary and still supply a dangerously incorrect request. Reviewing whether the pointer is null is necessary, but the more demanding question is whether the size still describes the objects that the program intends to place behind that pointer.

A single allocation contains several internal arrays

The parallel matcher maintains state for the regex execution, including current and next reachable states. Its allocation block contains temporary tags, the two reachability arrays and position data. It then supplies tag storage for each state in both reachability arrays. These are distinct uses of storage with a shared lifetime, so combining them into one block makes the size expression compound.

The implementation calculates individual quantities named tbytes, rbytes, pbytes and xbytes. Temporary tag storage depends on the number of tags. Reachability storage depends on the state count, including an additional entry. Per-state tag storage depends on both tags and states. A product of dimensions therefore occurs inside a larger sum, and part of the result appears twice.

After allocating the block, the matcher advances a character pointer through those regions. It aligns intermediate positions before assigning typed pointers. Later iterations assign each reachable state's tag pointer and advance again. This layout process assumes that the preceding calculation reserved enough bytes for every advance. An arithmetic error in the total undermines that assumption throughout the block.

There are two relevant numerical questions here. Each multiplication must represent its intended product, and the sum must represent the combined sizes. Checking the components without considering their repetition and addition leaves a different route to an undersized total. The structure of the layout determines the structure of the required checks.

The checks reserve room for the complete expression

The 1.1.16 implementation checks the tag count against a limit involving SIZE_MAX, the size of a tag offset and the number of states. It separately checks the state-derived storage for the reachability arrays and the position array. The code comments explain that these checks prevent overflow in the component calculations and limit their contribution to the eventual sum.

The source constructs the combined size with this expression after the component checks. Here the variable names retain the meanings assigned in the implementation.

total_bytes =
  (sizeof(long) - 1) * 4
  + (rbytes + xbytes * tnfa->num_states) * 2
  + tbytes + pbytes;

The four padding allowances belong to the pointer alignment steps. The factor of two covers the two sets of reachable states and their tag storage. Reading the expression alongside the pointer advances makes it possible to check that the requested byte count covers the layout, including storage that does not correspond to a separately allocated array.

The factors in the checks matter. They account for the fact that storage occurs more than once and that the final allocation includes several terms. A bound that merely allowed one component to consume the largest representable byte count would provide no room for the others. Dividing the available range before multiplication allows the implementation to reject a request before computing an unrepresentable product.

The final allocation uses calloc(total_bytes, 1). Its two arguments cannot reveal the intended dimensions because the caller has already combined those dimensions into total_bytes. Even an allocator that checks multiplication of its own arguments cannot reconstruct the previous arithmetic. The missing information has to remain available at the point where the matcher checks its counts.

Allocation failure is still a separate path. The implementation returns REG_ESPACE if calloc cannot satisfy the request. That result concerns an allocation whose byte count has survived the preceding checks. Rejecting impossible arithmetic and handling unavailable memory solve different problems, and the source contains both operations.

Matching behaviour determines the storage path

The public regexec implementation dispatches between matchers according to whether the compiled expression contains backreferences. The source sends expressions with backreferences to a backtracking matcher and other expressions to the parallel matcher. It also handles match tags according to whether the caller requests submatch results. The storage requirements are consequently properties of the matching operation and the compiled expression, not just the input string's length.

That distinction matters when interpreting the vulnerability. Calling the issue a regex buffer problem does not identify which dimensions need bounds. The implementation provides a more useful explanation by showing the counts used in its allocation expressions. A size calculation can depend on internal representations whose scale is not obvious at the public function call.

The source also explains that temporary matching storage is allocated per operation for thread safety. This makes allocation arithmetic part of execution, even though the expression has already been compiled. A successful compilation step does not establish that every later matching allocation will be valid or available. Each operation still has to handle its own storage requirements.

The scope of the release

Felker's announcement includes changes beyond the security correction. It reports a static PIE startup fix involving initialized thread-local storage and an overhaul of overflow handling in printf. It also names a MIPS regression affecting tcsetattr, introduced in 1.1.15. These are separate defects, with different triggering conditions, so the regex vulnerability should not become an explanation for all of them.

I value the ability to inspect a library at the same level as the calling program. In this case, reading the matcher makes the security boundary concrete. The caller's expression eventually becomes counts, those counts become a layout, and the layout becomes a byte request. The checks must preserve that correspondence before any writes into the allocated block occur.

For the regex fix, the useful implementation detail is the treatment of the whole allocation expression. Individual arrays share one block, and their dimensions contribute to both products and sums. musl 1.1.16 checks those dimensions before constructing the total, so the allocator receives a request consistent with the layout the matcher will use.