Scudo ("Shield" in Italian) is a memory allocator designed at mitigating heap-based vulnerabilties. It gained popularity when Google adopted it as the default allocator as of Android 11, in Fuchsia and Trusty. Scudo is part of LLVM, and is documented there.[scudo]. A detailed analysis can also be found in blogposts by Trenchant[sctr], Vectorize.re[vrs], un1fuzz[scu1], and by Synacktiv.[scsa]
Nomenclature
Scudo divides the heap into regions, which are backed by a number of mmap(2)ed pages. Each region is assigned a class, wherein a number of equal size chunks may be allocated, by a random order. Thus, different regions are used for different allocation sizes. Each allocation chunk is preceded by a header.
As with other allocators, chunks may be regularly allocated or freed. Scudo, however, differs by additionally defining a state of quarantine, wherein a chunk is temporarily marked as unallocated, yet unavailable to be used. This is with the explicit purpose of preventing Use-After-Free exploits (discussed later in this chapter). Quarantine requires a compile time option, which Android's configuration does not use.
Scudo defines two allocators:
The Primary Allocator: Used for most allocations of under 64KB (technically, under 64K + 16) in size.
The Secondary Allocator: normally used for allocations larger than 64K.
Scudo uses prctl(…, PR_SET_NAME, …) (in its mmapWrapper(…)) to name its allocator mappings, so they are clearly visible in /proc/pidmaps. Scudo's internal allocator metadata, however, is stored separately, in libscudo (or, in Android, Bionic libc.so) writable data segments.
Regions
Each Scudo region is associated with a ClassId. The number of ClassIds is configured using MinSizeLog and MidSizeLog parameters, and their size by SizeDelta. The configuration from Android's /platform/external/scudo branch is shown in the following listing:
Listing memP-scudocls: The Scudo ClassIds (from config/custom_scudo_config.h)
Note, that the allocation size includes the block header (16, 0x10 bytes), such that the first class (32 bytes, for Region 1) can accommodate up to 16 bytes of user allocation, the second class (48, for Region 2) up to 32, and so on. Region 0 is used internally, as discussed later.
---- Page Break ----
Region Allocation
Listing memP-scint (next page) annotates the relevant portions of primary region allocation. It can be summarized as follows:
NumClasses (in Android, 33) regions are to be allocated. Metadata is maintained in a RegionInfoArray (of NumClasses entries) as part of the Allocator instance.
getRegionInfo(I) is used to get an entry by index. Each region entry has its own 32-bit RandState. Entropy is seeded by the system's monotonic clock.
In Android, Config::getEnableContiguousRegions() returns true, so Scudo initially mmap(2)s all primary region memory as no-access (---), labeled [anon:scudo:primary_reserve].
The primary regions are each carved out of the reserve, with a size of up to 2RegionSizeLog (a build-time parameter from Config::Primary::, commonly 28, i.e. 0x10000000).
Config::getEnableRandomOffset() is true, so a random number of guard pages is kept between region mappings to offset the RegionBeg(inning, as set in initRegion(…), not shown). These guard pages both offset the region start, and ensure that a potential overflow in one region cannot spill over to another region without hitting a guard page, which would crash the process.
The regions are "shuffled", so that they do not appear in an expected order (which would enable guessing the region size by address).
The region mappings remain unused until each region's first allocation, which changes a 256KB portion of that region's allocation to read/write, and its label to [anon:scudo:primary]. Regions may then grow up to the maximum size in MapSizeIncrement (also 218, or 256K). The mappings can easily be seen through /proc/pid/maps. memento(j)'s heap option can autodetect Scudo heaps and resolve the mappings to their Scudo region classes:
Figure memP-scgp: Viewing Scudo's region layout using /proc/pid/maps and memento(j)
-
The region metadata is stored in an UnpaddedRegionInfo object, which is then wrapped by a RegionInfo, padding it for SCUDO_CACHE_LINE_SIZE optimization, at 192 bytes. All the RegionInfos are then held in a RegionInfoArray, which is shuffled during creation so as to add randomness to the allocator layout.
Figure memP-regionInfo: The Scudo RegionInfo object
The layout of the in-region blocks is given by the FreeListInfo, but the figure intentionally leaves this out for the moment (until 2.2.4 and Figure memP-bg), as we first need to describe what a "chunk" in Scudo parlance actually means.
---- Page Break ----
... Displaying the Allocator and RegionInfoArray using memento(j)
Chunks
The element returned by the malloc(3) family to the caller is a chunk. Scudo allocates equal sized chunks within each region, using two important features for security - layout randomization, and a header checksum.
Randomization
Not only are the regions randomized (as shown in Figure memP-scgp), but so are the chunks within each region. This can be seen easily by inspecting the memory of a simple program to allocate memory in a loop, and initialize each allocation with the allocation size, with a sample program such as this:
Listing memP-scregProg: Sample program to display allocations in Scudo regions
Running this program will demonstrate the randomization, which performed differently in each region, based on the RandState of that RegionInfo.
Output memP-screg: Example allocations in Scudo regions
Every Scudo chunk in the primary allocator is preceded by 16-bytes, of which 8 bytes are the chunk header, and the other 8 left as padding for 16-byte alignment. The header is illustrated in the following figure (note 32-bit, little endian representation):
Figure memP-sch: The Scudo HeaderFigure memP-scchunk: Example Scudo chunks (from Output xx-screg(2)) in memory
Before performing any chunk operation, Scudo will verify the chunk header checksum. The header checksum is performed by a CRC32 computation taking three arguments - the header itself, the chunk address (header address + 0x10), and a random value - a cookie. This is illustrated (alongside the code) below:
Figure memP-schcrc: The Scudo Header checksum calculation
As the above shows, the choice of CRC-32 allows for hardware optimizations, such as those of Intel's SSE4 or ARM v8.1's FEAT_CRC32. The header checksum verification is imperative to both detecting accidental heap corruptions, and preventing deliberate ones. In the deliberate case, even if the adversary knows the chunk address, the cookie still provides some randomness (though significantly less, due to CRC-32 collisions).
---- Page Break ----
Chunks in the Secondary Allocator
Secondary allocator regions are allocated as the need arises, with varying sizes and random locations, and a single guard page on each end.
Chunks in the secondary allocator are preceded by a LargeBlock::Header, which is defined in /standalone/secondary.h. This contains the doubly linked list of blocks, and metadata about the underlying mapping in which they are located - both the committed base address and size, as well as a "MemMap" object, which whose base and capacity fields include the surrounding guard pages. The MemMap (same as the one embedded in the RegionInfo object) may also contain MapPlatformData for platform specific metadata, which is used in Fuchsia, but not Linux or Android. The standard chunk header follows, as is shown in this figure (note 64-bit width):
Figure memP-sch2nd-a: The Scudo Secondary Allocator Header
Overlaying Figure memP-sch2nd-a over a memory dump, we arrive at Figure xx-sch2nd-b:
Figure memP-sch2nd-a: The Scudo Secondary Allocator Header, overlaid on memory
---- Page Break ----
Transfer Batches
Each region maintains its free list as a SinglyLinkedList of Transfer Batch Groups. These are linked list of "compact pointers". Compaction of a pointer involved taking its relative offset within the region block, and then further shifting it right by CompactPtrScale bits. In Android's configuration, this is SCUDO_MIN_ALIGNMENT_LOG, or 4 for 64-bit platforms.
Each TransferBatchT (from standalone/allocator_common.h) contains up to MaxNumCachedHint (= 13, per Listing memP-scudocls) compact pointers. This is shown in Figure memP-bg, which connects to the pointer left dangling in Figure memp@@:
Figure memPb-bg: Scudo BatchGroupTs and TransferBatchTs
memento(j)'s heap analysis will walk the Scudo heap and display region's FreeListInfo's, iterating through the TransferGroupT and the TransferBatchT:
Output memP-memheap: Demonstrating memento(j)'s Scudo heap walk
Unlike secondary allocator chunks, which form a linked list, Scudo's primary chunk headers provide no idea about the overall structure of the heap. That metadata is deliberately stored outside the allocator regions.
Further, Scudo is thread aware, and uses a TSD (Thread Specific Data, see @@) structure to hold its state. The TSD cache is accessible from Scudo's TLS Slot, which (as returned by Bionic's getPlatformAllocatorTlsSlot()) is the TLS_SLOT_SANITIZER (#6, see Listing memP-andtls). It is the CacheT's allocate(classId) method that is responsible for locating, allocating and returning the chunk to the caller.
The PerClass data
The TSD cache object holds a PerClassArray, with NumClasses entries of CompactPtrTs, up to twice the SizeClassMap::MaxNumCachedHint (i.e. usually, 26) . The PerClass structures of the array are cache aligned (and thus padded to 128 bytes).
Listing memP-slc: The Scudo SizeClassAllocatorLocalCache object (from standalone/local_cache.h)
The next pointer for allocation can be easily found by decompacting the class' PerClass[…].Chunks entry, and decrementing the count. When the count drops to 0, it indicates the CompactPtrTs have run out, and the cache needs to be populated by popping a TransferBatch. Conversely, if the count increases by free() operations, the TransferBatchs can be repopulated and pushed.
Local Stats
The TSDCache's Stats member is a LocalStats structure. This is defined in stats.h as consisting of a HybridMutex, which guards a DoublyLinkedList of StatsArray. The Array tracks three entries - StatAllocated, StatFree and StatMapped. The DoubleLinkedList contains one entry per region in order of ClassId, and can be walked in order to get to other regions.
Listing memP-sls: The Scudo LocalStats object (from standalone/stats.h)
---- Page Break ----
Experiment: Tracing Scudo's allocations using memento(j)
Looking back at Listing memP-scregProg, you'll notice a sleep(3) statement was deliberately inserted. This enables the capturing of a "before" and "after" core dump of the process, using memento pid core. Comparing the two core dumps can then be helpful to walk through the internals of the allocations involved.
For this experiment, we compile the program using the Android NDK (you can also download a precompiled version here), push the binary to the device and run it. Right as it sleep(3)s, we can suspend it and capture a core dump. Renaming the core dump to "…before", we can wait for the sleep duration, and then capture a second dump, renamed to "…after". The command would be something like this:
Output memP-scexp: The commands required for the experiment
tokay:/ $ /data/local/tmp/b 3
32#1@0xb40000741020f2b0
64#1@0xb4000074f020b8d0
131072#1@0xb4000075e043d000
32#2@0xb40000741020f070
64#2@0xb4000074f020bc90
131072#2@0xb4000073d010a000
# Pressing CTRL-Z to suspend the process
^Z[1] + Stopped /data/local/tmp/b 3
tokay:/ $ /data/local/tmp/memento $! core 2> /dev/null
Dumping core for Pid 19660
...
Dumped 0x78c000, total: 0x78f000 (7925760) to /data/local/tmp/core.19660
tokay:/ $ mv /data/local/tmp/core.19660 /data/local/tmp/core.19660.before#
# memento has a side effect on CONTinuing the process, so we wait a bit
# to get the last allocation before the deeper sleep:
#
32#3@0xb40000741020f6a0
64#3@0xb4000074f020b6f0
tokay:/ $ /data/local/tmp/memento 19660 core 2> /dev/null
Dumping core for Pid 19660
...
Dumped 0x78c000, total: 0x78f000 (7925760) to /data/local/tmp/core.19660
tokay:/ $ mv /data/local/tmp/core.19660 /data/local/tmp/core.19660.after
The two cores (which you can also download here) provide exact snapshots of the entire process - including the Scudo internal state. Although memento(j) does not (at the time of writing) have a core dump comparison feature, a simple workaround is to hexdump -C both of the dumps, and perform a standard diff(1) operation:
Output memP-scexp2: Retrieving the cores, and comparing them
Experiment: Tracing Scudo's allocations using memento(j) (cont.)
Using memento(j)map offset arguments, we can translate the differing offsets to where they fall in the address space. Ignoring the first two (which fall in the ELF NT_FILE note generated by memento(j) we look at the next batch:
Output memP-scexp3:diff(1)ing cores
morpheus@eM1nent (~) % memento /tmp/core.$PID.after map offset 0x17a690
Offset 0x17a690 maps to address 0x741020f690 mapped to [anon:scudo:primary]
morpheus@eM1nent (~) % memento /tmp/core.$PID.after map offset 0x23a6e0
Offset 0x23a6e0 maps to address 0x74f020b6e0 mapped to [anon:scudo:primary]
It should come as no surprise the second and third offset (above, 0x17a690 and 0x23a6e0) are exactly 0x10 bytes before the two 32- and 64- byte allocations, since Scudo places the chunk header there. This leaves us with the last three, which fall in the [anon:.bss]. Using memento(j)'s heap analysis, we see:
Output memP-scexp4:memento(j) heap analysis, focusing on Region allocations
morpheus@eM1nent (~) % memento /tmp/core.19660.after heap | grep Region
TSDCache: 0x75e03aa480 Allocator@0x75e03a53c0 Region Info@0x75e03a53f0
Region 0 (special) mapped@0x746020f000-0x746024f000 (3MB/256GB @0x7460202000)
Region 1 (32 byte chunks) mapped@0x749020e000-0x749024e000 (1MB/256GB @0x7490202000)
Region 2 (48 byte chunks) mapped@0x741020f000-0x741024f000 (2MB/256GB @0x7410202000)
Region 3 (64 byte chunks) mapped@0x754020c000-0x754024c000 (3MB/256GB @0x7540202000)
Region 4 (80 byte chunks) mapped@0x74f020b000-0x74f024b000 (4MB/256GB @0x74f0202000)
Region 16 (1104 byte chunks) mapped@0x73e020c000-0x73e024c000 (30MB/256GB @0x73e0202000)
We can quickly verify that offsets 0x17a690 and 0x23a6e0 fall in region 2 and 4 - as one would expect, for 32 and 64 byte allocations (remembering the Scudo header adds 16). To figure out the [anon:.bss] changes, we look through the TSDCache:
Output memP-scexp5:memento(j) heap analysis, focusing on Region allocations
And we see the differences fall exactly in PerClass[2] and PerClass[4] (dropping the count from 0x0b to 0x0a for both, due to the extra allocation in both), and in the LocalStats (increasing StatAllocated from 0x05f0 to 0x670) and StatCount (from 0xacd0 to 0xad50) - upping both statistics by 128 bytes.
---- Page Break ----
Errors
Scudo performs several sanity checks when manipulating pointers. Any failure in these checks leads to a program abort(3). Scudo's standalone/report.cpp's ScopedReport class is responsible for the generated error message. On Android, this becomes the "Abort message:" of the generated tombstone (see @@), followed by one of the strings in Table memP-scerr:
Table memP-scerr: Scudo ERROR messages
Abort message
Reason
invalid chunk state when...
Double free or relloc of freed pointer
misaligned pointer when deallocating address
Pointer arithmetic error
invalid allocation alignment:
An allocation not aligned on a power of 2
invalid alignment requested in posix_memalign
invalid sized delete when deallocating address ..
delete() size mismatch
corrupted chunk header at address ..
Pointer arithmetic error, double free or heap overflow
allocation type mismatch when ...
Incorrect alloc/free function pairing (e.g. malloc() vs. delete())
Output memP-scudots: A typical tombstone generated by SCUDO detection chunk header corruption
Build fingerprint: 'google/tokay/tokay:15/AP3A.241005.015/12366759:user/release-keys'
Revision: 'MP1.0'
ABI: 'arm64'
...
signal 6 (SIGABRT), code -1 (SI_QUEUE), fault addr --------
Abort message: 'Scudo ERROR: corrupted chunk header at address 0x200007b832892e0'
...
9 total frames
backtrace:
#00 pc 000005da84 …libc.so (abort+164) (BuildId: …)
#01 pc 0000049058 …libc.so (scudo::die()+8) (BuildId: …)
#02 pc 0000049d1c …libc.so (scudo::reportRawError(char const*)+28) (BuildId: …)
#03 pc 0000049c8c …libc.so (scudo::ScopedErrorReport::~ScopedErrorReport()+12) (BuildId: …)
#04 pc 0000049df0 …libc.so (scudo::reportHeaderCorruption(void*)+96) (BuildId: …)
#05 pc 000004b798 …libc.so (scudo::Allocator::deallocate(void*,
scudo::Chunk::Origin, unsigned long, unsigned long)+280) (BuildId: …)
#06 pc 0000001880 /data/local/tmp/b (allocAndPrint+88)
#07 pc 0000001938 /data/local/tmp/b (main+164)
#08 pc 0000057214 …libc.so (__libc_init+116) (BuildId: …)
...
Configurable Options
Scudo's options are normally set at compile-time through the SCUDO_DEFAULT_OPTIONS macro. The options can be overridden at runtime, using a variety of methods:
Defining a char *__scudo_default_options(void) returning an options string.
Setting the SCUDO_OPTIONS environment variable: separating options by colons, similar to the PATH environment variable.
Using mallopt(3): Scudo implements mallopt(3) (in standalone/wrappers_c.inc) in a manner similar to glibc (2.1.3), recognizing options defined in Bionic's libc/include/malloc.h and summarized here:
Table memP-scmallopt: Bionic mallopt(3) options recognized by Scudo
-
Experiment: Tracing Scudo's allocations using