x86_64 RIP-relative addressing bug

[Jim Keniston]

A while ago, I took an AR to summarize our ideas for fixing the bug in
x86_64 kprobes's handling of RIP-relative addressing.  Here are my
thoughts, including a variety of suggested solutions.  This writeup
includes suggestions from Prasanna a few weeks ago.  I'm not sure where
Prasanna is on this bug fix.

Further suggestions are welcome.

Jim Keniston
IBM Linux Technology Center - RAS
-------------- next part --------------
1	Handling x86_64 RIP-Relative Addressing in Kprobes

1.1	The Problem

1.1.1	Background

Probepoints are implemented by replacing the first byte of the probed
instruction with an int3 instruction.  When a probepoint is hit, we do
the following:
1.  Call the probepoint's pre_handler function.
2.  Single-step the probed instruction.
3.  Call the probepoint's post_handler function, if any.
4.  Resume execution with the instruction following the probed instruction.

Step 2 can be accomplished in two ways:

a)  Replace the int3 instruction with the original opcode,
single-step the instruction, and then put back the int3.  (Call this
"opcode replacement.")	This introduces a small time window during which
another CPU (in an SMP system) can execute the probed instruction but
miss the probepoint.

b)  Single-step a copy of the probed instruction.  Afterward (as part
of step 4), we must do some fix-ups to account for the difference between
the addresses of the probed instruction and its copy.  For example,
if the probed instruction is a call, we must adjust the return address
that was pushed onto the stack.

Kprobes uses method (b).  For most architectures, this works fine.

1.1.2	The Bug

Unlike the i386, the x86_64 architecture supports RIP-relative addressing
for many instructions that access data in memory (RIP = instruction
pointer).  This addressing mode is used frequently in the x86_64 kernel,
especially for references to extern data.  Since the RIP value for the
probed instruction is different from that of the copy, single-stepping
the copy will yield erroneous memory references for instructions that
use the RIP-relative addressing mode.  The current implementation of
kprobes does not address this problem.

1.2	Basic Approaches toward a Solution

When asked to install a probepoint on an instruction that uses
RIP-relative addressing, we have at least the following alternatives:

1.  Refuse to install the probepoint, and return an appropriate error
code.

2.  Install the probepoint, but single-step via opcode replacement.

3.  On an SMP system, refuse to install the probepoint; otherwise use
opcode replacement.

4.  When creating the copy of the probed instruction, adjust it so that
it accesses the appropriate memory location.

5.  Install the probepoint on the next instruction that doesn't
use RIP-relative addressing.  (I know of no instruction that does a
RIP-relative read/write AND a call or branch, so this should be safe,
though counterintuitive.)

Note that approach 4 requires a very detailed understanding of the x86_64
instruction set and instruction layout - similar to what a disassembler
must know.  We may need to handle cases where the instruction's offset
field must expand from (say) 16 bits to 32 bits.

Approach 5 requires us to know at least length(s) of the instruction(s)
that we're skipping over.  One way to determine this is to disassemble
the instruction and analyze the result.

How can we tell whether an instruction uses RIP-relative addressing?

1.  We can remain ignorant, treating all instructions the same.

2.  We can rely on the user to tell us.

3.  Based on opcode alone, we can do a simplistic determination that
the instruction (a) is "safe" or (b) might use RIP-relative addressing.

4.  We can disassemble the instruction (using "objdump -D") and parse
the disassembler's output.

5.  We can parse the instruction, like a disassembler.

I don't consider option #3 very promising.  See the "Opcode-Level
Screening" solution.

1.3	The Ideal Solution

The ideal fix for this bug would have the following attributes:

- sensitivity: The fix should not allow RIP-relative data accesses to
be mishandled.

- specificity: The fix should not adversely affect probepoints that
don't involve RIP-relative addressing.  I.e., we should not reject a
probepoint or resort to opcode replacement if we don't have to.

- transparency: The x86_64 kprobes user should not have to know any more
about this subject than the i386 kprobes user.

- simplicity: The fix should be simple.

- simplicity wrt kernel: If the fix is not simple, the kernel component
of the fix should be as simple as possible.

- efficiency: The fix should not slow down probepoint handling
significantly.

The section "Summary of Suggested Solutions" rates each suggested solution
on each of these attributes.

1.4	Suggested Solutions

1.4.1	Low-Tech Solutions

1.4.1.1	Document the Bug

On the appropriate website(s), and perhaps in the Linux Documentation
directory, document the bug and advise users not to place probepoints
on instructions that use RIP-relative addressing.

1.4.1.2	Use Opcode Replacement

Occasionally missing a probepoint (and only on SMP systems) is presumably
better than spraying data into random spots in the kernel address space.
So we could use opcode replacement for single-stepping the instruction -
whether or not it uses RIP-relative addressing.

1.4.1.3	User Certifies Instruction

When the user calls register_kprobe() (or register_jprobe()), he must
explicitly specify whether the instruction uses RIP-relative addressing.
(This could be via an additional field in struct kprobe.  The "yes, RIP"
and "no, no RIP" values for this field should contain signature bits
that minimize the possibility that a non-answer will be interpreted as
a yes or no.)

If the user specifies "no," then we can single-step a copy of
the instruction as we currently do.  If he specifies "yes," then we
single-step the original instruction via opcode replacement.  If he fails
to specify a valid yes or no, then we reject the registration request.

1.4.2	Medium-Tech Solutions

1.4.2.1	Opcode-Level Screening

register_kprobe() examines only the first byte of the probed instruction.
If it is the opcode of an instruction that might use RIP-relative
addressing, then we either reject the registration request or single-step
the instruction via opcode replacement.

This check can be implemented using a simple table or bitmap, indexed
by opcode.  For certain troublesome "opcodes" - e.g., 0xff and instruction
prefixes - we can be more precise by adding more intelligence.

To assess the usefulness of this approach, I disassembled a kernel,
grepped for "(%rip)", and tallied those opcodes that showed up.
Unfortunately, it's a big number.  When I gave up about halfway through,
I had reached 120 opcodes.  (I counted 0f b6 (movzbl) as different from
0f b7 (movzwl), and 40 13 (adc) as different from 13 (adc).)  So this
approach would brand a large fraction of all opcodes as unsafe.

1.4.2.2	Disassemble and Register

This approach is similar to "User Certifies Instruction," except that we
provide a user-mode program that disassembles the probed instruction;
checks for the "(%rip)" string; and runs insmod, passing as a module
option the "yes, RIP" or "no, no RIP" value.

1.4.2.3	Disassemble, Fudge, and Register

This approach is similar to the previous one, except that if the probed
instruction uses RIP-relative addressing, the user-mode program finds
the next "safe" instruction, prints an appropriate warning, and passes
the safe instruction's address as an insmod option.

1.4.3	High-Tech Solutions

As far as I can determine, if we really want to insert a probepoint on
an instruction that uses RIP-relative addressing (and we want to avoid
the SMP bug inherent in opcode replacement), the smartest approach is
instruction adjustment.  That is, the copy of the instruction that we
single-step must be adjusted so that it accesses the same memory location
as the original instruction.  (kprobes must also handle the possibility
that the instruction copy will be longer than the original.)

As mentioned under "Basic Approaches toward a Solution," this requires a
very detailed understanding of the x86_64 instruction set and instruction
layout, and probably hundreds of lines of code to implement.  So let's
begin with some basic observations:

1.  I believe that any such solution would be overkill for the problem
we're trying to solve.

2.  Any such solution should make up in transparency what it lacks
in simplicity.  I.e., if the user needs to use some special command to
install his x86_64 probepoints, then the solution is hardly better than
the "Low-Tech Solutions" described previously.

3.  A bug fix that adds "hundreds of lines" to the kernel will probably
not be accepted.  Therefore, much of the work must somehow be done in
user space, as suggested by Prasanna.

Here are three solutions that implement instruction adjustment, but
add relatively little code to the kernel.  None are ideal, and only one
achieves transparency.  I'm sure we can all think of many variations on
these themes.

1.4.3.1	Instruction Adjustment via call_usermodehelper

The user invokes register_kprobe() as usual.  register_kprobe() invokes
a user-mode program via call_usermodehelper(), passing it the address of
the probed instruction and the address where the copy of the instruction
is to be stored.  This program analyzes the probed instruction and, if
necessary, creates an appropriately adjusted copy.  The program either
stuffs the copy into place by writing to /dev/[k]mem, or it stuffs it
somewhere in /proc where register_kprobe() can get at it.

The program returns the number of bytes in the adjusted instruction,
or zero if the instruction doesn't use RIP-relative addressing, or some
big or negative value if the adjustment somehow fails.

1.4.3.2	Instruction Adjustment before Registration

The user invokes a user-mode program to install the probepoint, passing
it the address of the probed instruction and the module to insert.
This program uses an ioctl (say) to reserve a slot in the kprobes's
page of instruction-copy slots.  This ioctl returns the address of
the instruction copy.  Using this address, the program creates an
appropriately adjusted instruction, and invokes insmod, passing the
adjusted instruction as an option.

register_kprobe() must be enhanced to accept a pre-adjusted instruction
copy.

1.4.3.3	Analysis before Registration; Adjustment After

In this variation, the probed instruction is analyzed in user mode,
but register_kprobe() does any necessary adjustment.

The user invokes a user-mode program to install the probepoint, passing
it the address of the probed instruction and the module to insert.
The program analyzes the instruction, identifying its parameters:
prefix(es), opcode, ModR/M, SIB, offset, etc.  The program invokes insmod,
passing the instruction's parameters as an option.

register_kprobe() must be enhanced to accept the instruction parameters
and adjust the copy of the instruction accordingly.

1.4.4	Summary of Suggested Solutions

Note: All proposed solutions rate high in probe-time efficiency.  H, M,
L = high, medium, low.  V = very.

Solution	Sensitive	Specific	Transparent	Simple	Simple
									wrt
									Kernel
Document bug	[1]		[1]		L		VH	VH
Use opcode replacement [2]
		H		L		M		H	H
User certifies instruction
		[1]		[1]		L		MH	MH
Opcode-level screening
		H		ML		M		M	M
Disassemble and register [2]
		H		H		ML		M	MH
Disassemble, fudge, and register [3]
		H		H		M		M	MH
Instruction adjustment using call_usermodehelper
		H		H		H		L	MH
Instruction adjustment before registration
		H		H		M		L	MH
Analysis before registration; adjustment afterward
		H		H		M		L	ML
[1] The user is responsible for identifying which instructions can be
probed and/or how they should be single-stepped.
[2] Single-stepping via opcode replacement substitutes a less serious
bug for a more serious one.
[3] The probepoint may not be installed at exactly the desired
instruction, but the user is warned accordingly.

1.5	Revision History

Rev	Date	Author		Notes
0.1	2/28/05	Jim Keniston	Initial draft