Instrumentation is too slow

[stephenrkell]

Our xed-based decode is especially slow, but even with the libx86emulate one, it takes too long to trap a whole segment of a large library like glibc. With xed, the pause time can be a second or so on my (slow) machine.

Some possible techniques for improving this:

• cache trap sites, probably as an ELF file with .rel/.rela sections;
• use a really fast decoder (maybe fastBT?);
• trap in smaller chunks, lazily (this could also simplify away our mmap-time shdr-boundary hackery in bootstrap.c).

[stephenrkell]

This may tie in with #12, which is about selective instrumentation. For example, if we go the caching route, we could cache additional facts when performing an offline static analysis, such as "this site only ever does syscall number 42".

[stephenrkell]

I had some nifty (perhaps over-clever) ideas in the related liballocs issue.

Basically it's about "flipping" a single binary between two states, such that it always offers the same behaviour but is either: (1) startup- and memory-efficient in the instrumented runs, because it is pre-trapped but has some dynamic relocs that revert it to normal if not skipped by our clever loader; or (2) startup- and memory-efficient in uninstrumented runs, which is like the default case now.

A combination of techniques is probably going to be needed.

[stephenrkell]

The killer test of the flipping idea is whether it could be acceptable for a libc binary. Since a common case will be not to have instrumentation enabled by default, we still require some mitigation for the startup cost when the U-form binary is loaded and instrumented. Keeping the dynamic relocs 'on the side', as a cache that avoids scanning/decoding the text, may be enough. Creating the I-form binary then becomes linking in an 'inverted' form of those, i.e. ones that do reloc'ing back to uninstrumented.

So the first thing to do is generate these relocs as a separate file, and see if they reduce the startup overhead to acceptable levels.

[stephenrkell]

To make a U-form libc binary from a stock one, we need to enlarge the dynamic reloc section. That's tricky because it's in a mapped segment. On my Debian glibc 2.28 binary, the .rela.dyn and .rela.plt sections come right at the end of the read-only segment. There is then a bit of padding, but less than 4k and in some cases this will be negligible. There are 406 instances of 'syscall' in the binary. Since a rela is 24 bytes, we need to make something like 10kB of space.

It's times like this when I wish I could edit ELF files easily. Shifting ELF contents around in offset-space and vaddr-space might not be too hard...? In my elftin repository there is a 'shift-elf' utility that does a very simple case of this, albeit not actually moving any contents. How hard would it be to write a next-generation version that can do simple realloc-style moves and fix up the offsets/addresses accordingly?

I suspect that file offset changes are easy -- not many parts of the file do reference by offset -- but vaddr changes are hard, e.g. because already-applied reloc records have baked in vaddr assignments. Can we avoid vaddr changes? Not easily, because the next segment follows on contiguously in vaddr space.

Either intervene at libc link time (not ideal), or make a brand new segment for the stuff we want to move. So let's say we append a brand new LOAD for the enlarged .rela.dyn and .rela.plt sections.

Before making elaborate tools, it's a good idea to proof-of-concept this manually.

One nice way to do this would be to disassemble the ELF file s.t. it reassembles byte-for-byte identically. Then I could hack the assembly to experiment with changes. Perhaps I could write a dumper, also acting as a modest iteration of my liballocs-based mapped file tooling. It would basically work section by section (plus the ELF header, program headers and section headers)... most sections would get dumped as .byte directives, but code could perhaps be dumped as assembly instructions (use opdis?). Getting the labels right will be tricky. The assembly output format would be raw binary, not ELF.

[stephenrkell]

Actually, this is not necessary for a U-form binary (efficient when uninstrumented). It's necessary for I-form because we need the stock ld.so to flip the ud2s back into actual syscalls. For a U-form one, we are doing the instrumentation to ud2, and so we can put our reloc data anywhere as long as our loader knows how to find it. We still want it to be loadable though, so putting it in an enlarged .rela.dyn section, or adjacent to it, would make sense.

[stephenrkell]

I think the "quick fix" to all this is to use seccomp in the common case. It's a totally different mechanism and obviously less portable than instruction rewriting, but I think libsystrap should offer it. Can we make it so that trap_one_instruction_range adds an entry to the seccomp filter?

[stephenrkell]

Actually seccomp is not so good because it remains active even across an execve and requires the process to be in PR_SET_NO_NEW_PRIVS mode, which cannot be unset. This means that setuid/setgid semantics are disabled for the whole process tree.

Can this be salvaged? If we plan always to preload ourselves into anything we exec, it's arguably OK. Not all use cases of libsystrap have that property, though.

Additionally, the filter would needs to restrict system calls to a mapping of our library (somehow defined)... if it were instead to work by address ranges, restricting syscalls as they are mapped, it would prevent the same ranges from being used differently in a child process. Can it express this 'mapping of our library' property? What state does a seccomp filter have access to?

[stephenrkell]

We could make the filter self-disabling, i.e. only firing for a given PID. That could cause problems when PIDs are reused, in an absurdly deep process tree or a system with high PID churn... but it's probably OK to ignore that.

Since that doesn't unbreak the setuid/setgid semantics, it's possibly OK for testing purposes but is not a sound long-term proposition.