System call instrumentation on Linux/x86-64 using memory-indirect calls(dl.acm.org)

Diverting trains of thought, wasting precious time

In my last post I identified some
approaches to system call instrumentation on x86-64 Linux
that combine instruction punning
with the memory-indirect call and (most eccentrically)
lcall (“far call”) instructions.
I mentioned these have some interesting differences with
the direct relative jmp or register-indirect call
used by straightforward instruction punning or zpoline approaches.

These differences appear to be fractionally useful if you care about
saving a small amount of memory
(relative to E9Patch),
keeping the memory map simple for debugging purposes
(cf. an incidental downside of E9Patch that might bite when debugging low-level
code),
about minimising introduction of new instructions for security reasons
(an advantage of the memory-indirect approach over conventional trampolines), and/or
about keeping the standard hardware null-pointer trapping in place
even for function pointers,
while avoiding any need for special low memory-mapping privileges or not-so-ubiquitous CPU features
(advantages over zpoline).

In this post I'll cover more details about how to make this work,
especially around the segmentation features on which far calls rely.
I've implemented one variant of the idea (the
%rax-relative lcall one) on the use-lcall branch of my libsystrap
repository.
“Details” is the word; if you're not into details you probably
don't need this post, and I'm putting this here partly so that
anyone searching on related topics might benefit from what I've learned.

Let's recap from last time the picture we need for our %rax-relative
far calls.

How does this work?
For any system call that we patched to instead be a far call
indirecting %rax-relativewise via the low 2GB,
our lcall *0xnnnn(%rax) instruction we will read the six-byte far address
0x1f1f:0x1f1f1f1f.
The 16-bit selector 0x1f1f denotes an LDT entry, number 0x3e3 (discard the bottom three bits of 0x1f1f).
So if we put our handler code at 0x1f1f1f1f,
and install an LDT entry at slot number 0x3e3, with base address zero,
we can start to handle these calls.
(The base address doesn't have to be zero... I will come back to this.
And we don't have to pick 0x1f as our repeating byte—if our LDT is
otherwise empty, then any selector ending 7 or f will map to an LDT entry we can use,
so we have 32 byte values to play with.
0x1f is good because it's always an illegal instruction
in x86—just in case this memory gets executed by mistake somehow.)

Let's look at the modify_ldt system call.
It's a very confusing beast for a number of reasons.
Firstly, despite the name, it can be used to read the LDT as well as writing it.
Secondly, there are two flavours of write operation.
Thirdly, it uses different data formats for reading and writing.
The manual page gives it the following signature:

... while noting that
glibc provides no wrapper, so in reality we have to use syscall().
We get the read function if passing func equal to 0,
and two different write functions
if passing func equal to 1 or 17 (0x11).

Although the manual page is not clear on this,
the read function (func == 0) will read raw LDT entries in the hardware-defined format.
This is C-ified by Linux, inside the kernel, as follows
(from Linux 6.18).

One entry is eight bytes in size, and decoding its idiosyncratic narrow-width fields requires
reading
the Intel documentation.

By contrast, the write function updates a single entry, at the given index, where the entry is
described by the user_desc structure
as seen in the manual page.

This lacks some of the hardware's fields—but
offers friendlier names for those if does have, and does not fragment
long fields over many small pieces owing to Intel's piecemeal hardware evolution.
It does betray its age a little though, since it uses only a 32-bit unsigned integer
for the base and limit fields.

The two write operations, 0x1 and 0x11, differ only in that
the kernel's internal write_ldt()
is called with parameter oldmode equal to 1 for 0x1 (the older operation)
and 0 for 0x11 (the newer one).
The differences are only as follows.

Overall, old mode is less expressive; it is more clear-happy and less set-happy.
So there is no reason to use it; it exists for compatibility.

Finally, modify_ldt has a fourth operation, the
undocumented “read default” function (func == 2)
which currently
reads a collection of zero bytes
so is not especially useful.

The kernel's logic to populate the actual LDT entry looks like the following (from Linux 6.18,
fill_ldt() in arch/x86/include/asm/desc.h):

(The code further up the call chain that reaches here,
modify_ldt and write_ldt,
lies elsewhere.)

You can also see in the above code that Linux won't let us create a 64-bit code segment
either—not only because the base and limit fields of user_desc
are not wide enough,
but also because the long-mode l bit is hard-wired to 0.
This is documented in the manual page.

Why is this? The relevant bit of kernel code above
hints that user_64bit_mode() is part of the explanation; let's take a look at it.

In short, the kernel is assuming that our friendly 0x33 (__USER_CS)
is the only long-mode user-accessible segment selector.
It uses this fact to make it simple to test whether a process's userland is
running in 64-bit mode: is %cs set to that unique selector?

The “overridden by sysret”
is meanwhile referring to some behaviour of one of the “other” far-calling
primitives of 64-bit x86, namely sysret that is the converse of syscall.
Much like the instructions we've been thinking about,
sysret does a far indirect jump, to some target code segment
(in user space).
However, in 64-bit mode it works in a “special” (hacky) way.

... where the “fixed values” look like this:

In other words, the OS has configured a model-specific register (MSR)
with some code segment selector of its choosing.
In principle, this could point into either the GDT or LDT.
That configured value is used to restore %cs.
Then, the private architectural state that caches the GDT/LDT contents (currently in-use
segment descriptors)
is initialized with a “universal” “expected” values,
namely the fields that specify (deep breath) a ring-3 zero-base max-limit page-granularity non-system
readable executable code segment that is long-mode if and only if the default
current operand size at the site of the sysret itself is 64 bits.
It's up to the OS to ensure that the GDT/LDT contents match these fixed values,
i.e. that that is what the GDT/LDT contains at the MSR-selected entry.
In practice, on Linux achieves that in a particular way:
the configured selector always points into the GDT,
and Linux permits no long-mode segments in the LDT.
Therefore we can never be attempting to sysret into one of those.

All this seems a missed opportunity in some sense.
If Linux wanted to (it doesn't), it could expose more of the underlying
x86 architecture to its user programs.
There's another restriction of this form....

Our long call has a selector 0x1f1f and an offset 0x1f1f1f1f.
This offset seems a bit extraneous, because we're free to define the base address
of our segment descriptor.
We could make it point straight to our handler code... but
then we'd have to call it with offset zero, which we are not doing!
We are calling it with offset 0x1f1f1f1f.
For such a callable segment, could we declare it as
not needing or taking an offset?

In short, yes: the hardware lets us do this.
It allows for a special kind of pesudo-segment, a call gate.
Such an entry defines a call entry point rather than a segment of text per se.
But no; Linux won't let us create call gates in the LDT even though the hardware allows them.

The idea of call gates is not-so-uncannily similar to system calls:
a key purpose of call gates is as opportunities to change the current privilege level,
e.g. to transition from ring 3 (unprivileged user code)
to ring 0 (kernel mode),
because the descriptor records the privilege level with which the jumped-to
code will run.
Call gates don't have to be used for privilege transition though—a call gate
can retain the current privilege level too, making it
effectively an opaque procedure call entry point recorded in the LDT (or GDT)
and callable by a 16-bit segment selector (the offset is thrown away).

Indeed, a traditional way to implement system calls on Intel hardware
is exactly to define one or more call gates.
One classic way to make a system call in pre-Linux Unix systems running on x86
was lcall 7, i.e.  a call to the first entry in the LDT, which would be
set up as the unique system call gate.
According to the System V ABI supplement for the i386, which is
(to my knowledge) still deemed current on 32-bit platforms including Linux,
support for an exit() system call made by lcall 7 is the only mandated
system call interface (p50 of that PDF). It appears Linux no longer supports this,
if it ever did, as it does not create the necessary call gate in the LDT
(at least on my system; it may be possible to cajole it into doing so,
but personality(PER_SVR4) or similar do not suffice).

At the very start of this work I was hoping we might be able simply and cleanly to turn system calls
into via-call-gate far calls.
That is not possible, unfortunately.
Partly that's because there's no 2-byte form that calls the LDT entry whose index is in %rax:
we know that all far calls indirect through memory, not just registers, and that
an arbitrary (punned) 16-bit selector might nominate either GDT or LDT.
After that became clear, I was next hoping there might be a longer encoding of call
that takes the segment selector from a register (hand-waving away the GDT issue for now)
and the offset from an immediate.
If such an encoding existed, then we could pun with im-pun-ity:
the register would select a call gate and the offset, read punningly from the instruction stream,
would be thrown away.
Sadly, there's also no form of call like this.

And there's also a much more boring reason why this won't work.
Linux rather rudely does not let us define call gates.
Call gates are deemed to be a kind of “system” descriptor.
The s bit of the descriptor is for “system” but is inverted:
a system segment must have the s bit set to 0.
From the above code we can see that only a non-system descriptor can be created
by modify_ldt(): no field in the user_desc structure
gives us control of this bit, which is unconditionally set to 1.

If we're going to use lcall at all,
we've established that we need to call a 32-bit segment and that it must be an ordinary
text segment, not a call gate.
The resulting handler is a slightly odd beast.

It necessarily starts in 32-bit mode, but the handler code we
want to run is 64-bit (for emulating or wrapping a 64-bit system call).
So I coded it up as simply immediately switching back to 64-bit mode,
by jumping to its next instruction addressed via the __USER_CS code segment, i.e. the
unique 64-bit code segment that Linux creates for us.
Now I've got my head around all this I plan to rewrite my trampoline somewhat, but for now
it looks like this:

... after the jump, it also pushes %rax and then loads
the “real” handler address straight out of the eight bytes
immediately following the instruction.
(My rewrite will use %rcx for any scratch needs and skip the push, because
system calls are expected to clobber %rcx.
And I should probably not do the gross data-in-instruction-stream thing.)

Despite branching out of user code using a far call to a 32-bit code segment,
one quirk of all this is that
we will return to the caller purely in 64-bit code, without ever going back through 32-bit mode.
How to actually perform the return will turn out to be non-obvious....

Our far call operation is from a 64-bit code segment,
to a 32-bit code segment identified by a 16:32 far address,
and has the default operand width for such calls.
What is that width?
It's 32 bits. (We did not use the rex.W prefix which would
let us use a 16:64 memory operand indirectly; it would require an extra byte for the prefix, and
in our pun context we literally don't have space.)

What does that width mean?
Clearly it selects the width of the far address loaded (from our stepping-stone location),
It also selects the width of the return address saved on the stack:
that, too, will be a 16:32 value: a 32-bit offset followed by a 16-bit segment selector.

Therefore, the top 32 bits of our return address will be discarded.
That's a problem!
We need them if we're to get back to the system call site.

The simple fix is to keep a look-up table of system call sites, keyed on their lower 32 bits,
and only use the far-call instrumentation for some subset of system call sites
for which these keys are unique.
It's unlikely that wouldn't cover all syscalls, but if we do find a duplicate, we need to trap it some other way.

Such a look-up table is not without cost.
In my prototype I use a binary search over a sorted array... elegant
but somewhat slow.
A faster approach might be to “burn an LDT entry”.
This works for the %rip-relative lcall only.
The byte value that we surround our text with need not be
1f— it could be any two-hex-digit value ending 7 or f
whose corresponding LDT entry is free. (Recall: the low three bits of this
byte value must all be 1, as only these denote a user-privilege entry in the LDT.)
We do only have 32 of these byte-repeated LDT entries to play with, however.

So to quickly restore our return address, we issue a different
LDT entry for every loaded binary—or, more precisely,
for every aligned 4GB region that contains system calls trapped in this way.
Each LDT entry points to a different handler, although all are mutually similar:
restore the top 32 bits of the on-stack return address, then proceed.
Each handler knows the 32-bit value it must restore, because it is used only
from a given 4GB region.

It's unfortunate that this works only for the %rip-relative lcall,
since it'd be really useful to have a good solution also for the %rax-relative ones.
Although those only work in 50% of puns anyway,
our low-2GB stepping stone area is shared across
the whole address space so we cannot tailor it to a particular 4GB region.
Note, however, that our return address recovery is uncannily similar
to the return address validation done by existing approaches
based on zpoline-style handlers that must check for null pointer errors (zpoline, lazypoline, K23).
We expect it to have a similar overhead,while being needed in strictly fewer cases.

What if the guest program wants to use the LDT for its own purposes?
Wine and Dosemu are the canonical examples but perhaps there are others.
In principle this is fine, as long as they check for a free entry
(rather than expecting entries at specific indices to be free)
and do not end up racing with our code.
I don't yet know whether these hold or can be made to hold.
We have plenty of entries, since we are liable to use few or no entries
besides the 32 that have byte-repeating selector values.
(But see “LDT punning” for one exception to that.)

Since when we use the far call recipes,
the segment we call through is a 32-bit one, we temporarily
have at our disposal all the affordances of “proper” segmentation:
non-zero base addresses and (should we wish them) non-ignored segment limits.
Recall that in 64-bit mode,
unless selecting through %fs or %gs (e.g. for thread-local storage)
segment bases are hard-wired to zero and limits are mostly ignored.
(Limits can optionally be re-enabled, on sufficiently recent but not too recent
AMD hardware (search for “LMSLE”)
but not, I think, any Intel hardware.
I have a vague memory of discovering that Intel did eventually implement this,
using an incompatible MSR, but I think I dreamt it.)

While we are in 32-bit mode,
the brief return to “proper” segmentation lets us play some games.
In essence, the contents of an LDT entry are a secret maintained for us by the kernel.
I am pretty sure the only interface for accessing them is modify_ldt()
(which also provides a read interface, despite its name)
and we are between the user code and this system call.
So if we wanted to store our system call handler at a secret randomized address,
we could do that by randomising the segment base field in the LDT.
We simply arrange that when adding 0x1f1f1f1f to it modulo 232, we get the
actual handler address. It doesn't have to live literally at linear address 0x1f1f1f1f.
The reason I am hedging with the “pretty sure” thing is that
there is a “load segment limit”
instruction which will retrieve the limit field (“unscrambled” meaning
pieced together from its various fragmentary bit-fields) for an arbitrary segment selector.
I'm not aware of anything that will retrieve the base address,
and of course the LDT itself is not in user-addressable memory.

Is this useful, security-wise? Perhaps, but I don't have anything concrete.
At a very hand-wavy level,
exploits often want to perform system calls, so by making it harder to find the “true”
code path that performs a syscall, we may make exploits harder.
However, the “soft” system call paths that we are providing
using this lcall malarkey
are, necessarily, still effective at making system calls; perhaps if there were
some extra checking along these paths, which an attacker were trying to evade,
this secrecy could be useful, but for now I am just noting the trick in passing.

When we land in a 32-bit code segment,
the relevant stack pointer will be the %esp register,
i.e. the low 32 bits of the %rsp register.
So, we will have to provide a stack located in the low 4GB.

This is easy to achieve in my use case.
It's fortuitous that I want to use these techniques
in a library for trapping system calls,
where that library is in fact
linked into a chain loader
that (e.g.) implements a strace-like tool.
The use of the chain loader guarantees that we get control
from the beginning of execution,
and the strace-like nature means we already want to observe
all system calls—including, bootstrappingly, all memory-mapping operations that might
introduce new system call sites, and also
all those that might map a new stack.

It also means we have control of the stack at start-of-day—“start”
as seen not only by the
loaded executable but even by the “real” (chained-to) dynamic linker.
By default, the kernel will allocate a stack fairly high, but
we can simply switch to a low stack when we run the chained-to dynamic linker;
it does not seem to mind.

We do, however
need to split the possibly-large blocks of strings (I call them “asciz data”) from
the on-stack pointer structures that reference them (often called argv and envp).
Most code does not mind this split at all.
Caveat: I have written code that does mind, in liballocs, which
I'd have to update a little not to be wrongfooted by this physically split stack.

Stacks are not all alike; the initial stack, created by the kernel during execve(),
need not be created the same was as a user thread stack.
According to Rich Felker, who would know,
Linux
reserves 128kB for the initial stack but will attempt to grow it larger on demand.
By contrast, libpthread will map an entire stack and,
contrary to expectations, neither glibc's nor musl's pthread_create() implementations
(at least in the old-ish source trees that I have handy)
will map a thread stack with MAP_GROWSDOWN.
They just map the entire stack from the off.
Although they also include a guard area, it's used to catch small overflows,
but not to trigger growth.

We need a low stack for a subtly broader reason than for executing 32-bit code.
We need it very slightly sooner than we execute any such code:
simply for calling out of 64-bit code, to 32-bit code.
When I first tested my lcall approach,
my 32-bit test code did not use the stack at all, yet
still I found the lcall was mysteriously segfaulting,
with messages like the below (visible from dmesg).

This threw me for a minute. “error 6” refers to a user-mode
store to memory (see this great page by Chris Siebenmann)... but
I'm doing a call?
Of course, a call stores to the stack and the stack is the problem.
Here %rsp is 0x00007fffcbd695f0
and the CPU is trying to store a return address at 0xcbd695ec,
i.e. its 32-bit truncation (minus four).

We infer that if we long-call into a 32-bit code segment, even (morally) before it jumps,
the CPU wants to push the return address
through %esp not through %rsp.
I suppose that's reasonable, because it's assumed the call-to-32-bit will end with a
ret-from-32-bit.
Under this assumption,
the return address we push must be accessible through %esp, so it must be
stored to the lower 4GB.
(Of course, our particular code invalidates this assumption! As
mentioned above, my handler path immediately switches
back to 64-bit mode, so we return without ever doing a 32-bit ret.)

Some things I checked for completeness: if we do rex.W lcall to a 64-bit segment,
how wide is the return address pushed, and does %rsp truncation occur?
Answers: 16 bytes of which only 10 are used and no, of course not.

In x86, many instructions have an operand width.
I can movb to copy a byte, movw to copy a two-byte “word”,
movd to ocpy a 32-bit double-word and movq to copy a
64-bit quad-word.

Although I hadn't thought about it much before, calls also have an operand width.
But what does it refer to?
From our earlier rex.W lcall example, we know that
the widths a call is working with include
both the width of the offset jumped to (4 or 8 bytes)
and the width of the return address pushed onto the stack (likewise; of course
the 16-bit selector is pushed too, in a long call, and the whole package padded to a word boundary).

There's a related but different width we saw with the need for a low stack:
the width of the stack address read from the stack pointer
as accessed by the call instruction itself.
Our previous low-stack surprise call to a 32-bit segment, even though it was executing
starting in 64-bit mode,
somehow triggered only a 32-bit register read, from %esp,
not a 64-bit one from %rsp
If it had done the latter, the segfault in the previous section would not have happened.

Does a rex.W lcall to a 32-bit code segment also trigger such a segfault?
Yes. We can infer that the stack pointer read width, effective at a call instruction,
is determined by the target code segment
and not by the operand width of the call instruction itself.

There are narrower calls too, of course:
even in 64-bit mode we can try to do:

... or the obvious lcall variants.
What does the “w” refer to?
When I try, I get a general protection fault, for reasons
unclear.
Do these also affect the width of the stack pointer (%esp versus %rsp)
used to address the stack during the push?
I doubt it but I confess I haven't been able to check.

(However,
this article shows that LLVM and binutils are confused
about callw instructions: they think any immediate displacement is only 16 bits wide, but
actually the processor heeds the full 32 bits and the size-override prefix is ignored.
Christopher Domas's sandsifter tool,
documented here,
also found that Intel processors ignore the override
but AMD ones heed it.
This affects decode, i.e. the width of the immediate operand in the instruction stream,
but also operation: whether the jump target is truncated to 16 bits.
Do AMD processors perform this truncation? I suspect so but I don't know.)

Just as calls can have their operand size overridden, they can have their segment overridden.
What does this do?
I haven't tested, but
this article
suggests that segment override applies to
memory-indirect calls only, and overrides the usual use of %ds for
loading the memory operand.
It would make conceptual sense to override the stack segment of a call, but
I believe overriding the stack segment is not supported, for any instruction
(corroboration).

I've not implemented this, but since we're contemplating the %rax-relative
thing that works in only 50% of cases,
there's a second idea that is not crazy to consider: it should work in roughly 12.5% of cases.
I'll call it LDT punning.
If we can't use %rip-relative punning, it's probably because
the successor bytes pun to only a small displacement, landing somewhere in
already-allocated memory such as another part of the same library's text.
If they land in the bytes 00 84 c0 74 40 0f, say,
then these themselves pun as a stepping stone:
they denote offset 0x74c08400 in the segment selected by the 16-bit value 0x400f,
i.e. LDT entry 0x801.

(Recall that the LDT is indexed by a 13-bit value
and the lower 3 bits of the selector must all be 1.)
We could allocate a unique LDT entry to handle these,
assuming entry 0x801 is otherwise unused.
In the LDT entry, we set the 32-bit segment base address to the linear address of our handler minus 0x74c08400
(modulo 32).
These may use non-byte-repeating 16-bit selectors, so we are choosing from a much wider space
than our 32 byte-repeating values.

One of the reasons my low-2GB %rax-punning lcall hack was appealing
is that most executables nowadays
are position-independent (PIE) and so
the low 2GB of the address space often has little content.
However, if we do have a non-PIE executable
that is linked at a low address range, what can we do?
We not only start to collide with stuff in the low 2GB,
but negative-pun displacements are mostly intractable for both %rip-relative
and %rax-relative cases.
If facing a non-small negative displacement in a non-PIE code context,
do all our recipes fail?
We can still do %rbp-relative punning
for frames that save a frame pointer, modulo the obviously
increased contention for low-4GB addresses.
We can still try the LDT punning trick, at 12.5% likelihood of success.
But both of these are a bit desperate.
To jump somewhere else punny within the low 4GB, we can fall back to E9Patch's 5-byte techniques;
it also suffers from unusable negative-displacement puns
but its (palatable) “jump padding” and (nasty)
“neighbour eviction” recipes give it more wiggle room to find a viable target.
In my case I am tempted to say... do we care?
Perhaps a trap via SIGSYS is not so bad in those cases.
PIE executables are rare, and executables contain few system calls (compared to the C library).
Furthermore, thanks to my next observation,
we only need any of these tactics for a slim minority of system calls in the first place....

All the while during this post and last,
we have been ignoring an important fact about system call instructions.
In most cases, they are preceded by an immediate move into %rax.
If we control that immediate, we control the system call number.
It is safe to patch the immediate if that %rax value
does not leak out, i.e. is not used by any other instruction.
Patching the immediate to a high value
allows us to use a zpoline-style %rax-relative register-indirect call in place of the
ensuing system call,
without inheriting the disadvantages of the zpoline itself (mapping low,
defeating null pointer checking, etc).
After checking that it's safe,
we'd simply patch both the system call and the write to %rax, so that the end result
is calling our handler, at some address higher up in the first 4GB.

I have found that 90% of syscalls can be classified as following this pattern
by a very stupid conservative analysis, which I have coded up as an awk script over
objdump --visualize-jumps.
Therefore, all the punny techniques we've been talking about are
needed only in the remaining 10% of awkward cases.

We can think of the patch to the immediate field as a “relocation” to the syscall:
it lets us change the binding, i.e. the effective %rax value
that reaches the site of the call.
(This view makes sense to me, anyway, but I have linking on the brain.)

Phew! That's all the corners I've explored so far.
I started all this thinking there wasn't enough here to be worth writing up as a research paper,
but I'm now starting to doubt that.
I'd need to measure performance, which for lcall may not be great
(but will be better than double traps).
I suspect that combining all the above does yield a system call trapping solution for x86
that is a “better” compromise, in some sense,
at least in some practical scenarios, than what's in the literature already.
I mainly want system call trapping for liballocs,
where I do need to avoid the run-time baggage of
K23-esque ptrace helpers or zpoline-style disruptions to null pointer trapping.
I also value minimal intrusion on debuggability, hence my aversion to E9Patch-style
funky noise in the memory map or disrupted control flow within patched functions.
So I think these techniques are worth adopting, at least for me.
To avoid debug-time confusion I now also want to write that pun-aware disassembler, however!

[/research]
[all entries]
permalink
contact