What methodology can be used to change code flow atomically during program execution?

Question

I have been reading a lot about the different techniques for Windows API hooking (a technique I'm particularly fascinated by and fond of), and it seems a major problem in implementing a realiable hook function is ensuring that the hook is written in a way that is thread-safe. Of course, there are some techniques where this problem has been solved or can be solved trivially, such as hotpatching the Windows API, but hot patching is not guaranteed to work on all win32 or third party API functions and the techniques that do support hooking them are not normally thread-safe.

A very common technique that is has problems caused by multithreading is a inline hook that replaces the normal function prologue code with a jump instruction to the hook procedure, and then calls the original function as needed through a trampoline.

There are several inherent issues to the inline hook technique, which makes it a very complicated method to use and debug. A primary issue is as I mentioned, that it is not safe in a orthodox multithreaded environment in the real world. This is due to that when changing the bytes of the function, you can not guarantee that the instruction pointer will not be in the middle of your newly injected code, which may then cause the target application to crash from executing an invalid mix of the old opcodes mixed with the opcodes you inserted.

There are some solutions to this problem, with one being suspending all the threads in the process and then checking the instruction pointer in each thread to ensure that no thread is currently executing the target instructions you wish to replace. Then if there happens to be a thread or two executing that particular function, then you can respond accordingly by doing something such as performing a stack trace to place a breakpoint at the return address, resuming the thread, and then handling the exception when the thread has returned from the target function.

Of course, this method is still unsafe, because there is nothing stopping one sneaky thread from using CreateThread() before you can suspend all of the running threads in the process (some applications on my computer run with 40+ threads at once). There could even be a related process that uses CreateRemoteThread() in your target application and then calls the function you are hooking before it's safe.

A solution to that problem could be trying to debug the process and receive notifications of when a process creates a new thread, and then respond by suspending that thread. Of course, many event notification systems provided by the Windows API or a third party API will not be sent in real time, which may allow that thread to perform an unsafe operation before it is suspended.

Another solution could be to statically patch the executable with the hook function before the process is launched, presumably by hooking the EAT/IAT. This is not an option for me because I need to have an implementation that will work process wide, regardless of how a function is resolved or in the event of a new unhooked module calling the function.

There are many other issues to overcome with the inline hook technique that I did not mention. Which brings me back again to my question:

What methodology can be used to change code flow atomically during program execution ?

I was curious to see if there was a more robust solution out there that overcomes some of the shortcomings of the methods I covered in this post.

Please no third party library suggestions for hooking functions. I want to implement my own for the educational benefits.

I prefer hooking technique documentation and examples that use the C programming language.

My processor is an AMD Athlon II X2 250 that is x86-x64 compatible, and my operating system is Windows 7.

Answer 1

A sketch of how to implement your own patching system, where the length of the replacement instruction is less than or equal to the length of the instruction that you want to patch:

1. Make sure that none of your code depends on any of the code that you will want to patch. This is an issue of re-entrancy. If you patch code that your patching system will use, then you might deadlock / block / raise an infinite number of signals. A common solution is to do things like re-implement the subset of libc that you need, or statically link against some other implementation of libc. Symbol versioning can help ensure that no other libraries link against your version of libc (or libc-like functions) at runtime.
2. Have a dedicated patching "master" thread. If you're on linux, then this patching thread can be an external process that controls the program via ptrace. An alternative is to dynamically elect a master thread from one of the threads that gets signalled (mentioned in the next point).
3. Install a signal handler such that your patching thread can signal all other threads to stop and block on a condition variable. Obviously, make sure that your patcher thread does not signal itself. You might need to double check that in the time it took you to signal all threads (that you knew about), that no more new threads have been created.
4. Now you can patch code. Change the memory protection of the pages of code containing what you want to patch so that they are readable, writeable, but not executable. Make sure the code you're using doesn't appear on the same page(s)! Change the code. Change the memory protection of that code back to readable, executable, but not writeable.
5. Signal your condition variable / threads to wake up.
6. When your threads wake up from being blocked on the condition variable in their signal handlers, they need to execute a synchronizing instruction, e.g. CPUID, before executing the patched code. This is so that the old versions of the code do not remain in any instruction prefetch caches/buffers/whatever. Intel's software optimization manual goes into a few details here. By the way, watch out about patching the concurrency/signal mechanisms that you use to implement signal/wait/etc!
7. Then the threads will return from the signal handler to resume execution where they were signalled.

Now, what to do if you want to patch an N byte instruction with an M byte instruction such that M > N? We'll apply roughly the same technique, but we'll modify the return addresses of the signalled threads to point into a copy of the original instructions that include your patch P.

For example, lets say you have instructions I1; I2; I3; I4; ..., and your patch P, if placed, would end up as: P; I3_tail_garbage; I4; ....

Then you could create a patch entrypoint P; I1_copy; I2_copy; I3_copy; jmp &I4; at address patch. You will modify some of the the return addresses in the signal handlers as follows:

• If RA == &I1, then make it point to: P; I1_copy; I2_copy; I3_copy; jmp &I4;.
• If RA == &I2, then make it point to: I2_copy; I3_copy; jmp &I4;
• If RA == &I3, then make it point to: I3_copy; jmp &I4;

Patch I1; I2; I3; I4; ... to do the following: jmp patch; int3; ...; int3; I4; ....

Note: When copying code, you need to re-relativize it if your instructions somehow read from the instruction pointer. For example, if I1, I2, or I3 are branch instructions, or compute a RIP-relative address, then they will potentially need to be widened/modified/replaced with equivalent instructions.

Another approach is to patch each of I1, I2, and I3. If you do this, then you must start by patching only the first byte of each of these instructions, and only with an int3. This can be done safely, even while other threads are executing the code being patched. However, you cannot safely modify the other bytes of these instructions if other threads are concurrently executing those instructions. This is because those instructions might have been prefetched, and once that has happened, they are no longer a cohesive unit.

Figuring out the right protocol to handle the cases where threads concurrently execute the int3s is tricky, but I think it can be handled by following a similar methodology to above approach of duplicating the first few instructions so that you guarantee that those instructions aren't lost, but you also capture threads executing code that falls within your patch region.

I am not familiar with the Windows environment, so the CreateRemoteThread issue sounds tricky, but I think installing int3 instructions into the code as well as protecting the code from execution while you search for threads to signal might be sufficient. You might also consider having your master patching thread go to sleep for a short period of time.

Finally, some good references to look at are Kprobes and RCU stuff as well, as the problem faced by some "extra" thread seeing the old or the new version (or something in-between) is a major concern with RCU. As a concluding remark, watch out about the language of the Intel manual w.r.t. cache coherency and the icache. A lot of text can be interpreted as if atomic writes to the data caches will be represented in the icache, but in practice, this isn't guaranteed to be true (especially where prefetching is concerned), and there are some important CPU errata on the issue that make the problem harder than it first appears.

Answer 2

This is a good question, and I would argue there is no 100% safe method to patch a running windows process, unless you actively debug it, and even then there are probably edge cases. You could eliminate many potential problems, but I feel that potential threading problems couldn't be entirely eliminated for generic purposes.

This leaves a couple practical options in my opinion:

1.) Suspend the process, patch your code, and resume execution. Either all threads are suspended or they aren't, this is easily detectable if you have the rights to patch the process to begin with. This is my preferred method, though anti-debug measures based on timers as well as defensive hooks can detect this. Overall though I'd say it's quite dependable.

2.) Know your target well and don't depend upon "generic" one-size-fits-all patching techniques. You should know beforehand whether or not multi-threading is going to hamper a particular patch at a particular address for a specific target, and how feasible it will be to perform reliable realtime patching.

If you know or suspect that your target code is threaded, find the synchronization method used (locks, mutexes, interlocked operations, etc.) and begin your patch from thread-safe code, ideally after forcing temporary thread contention/deadlock to prevent execution while patching. Reliably doing this will likely be very target specific and therefore require at least a tiny bit of fairly intimate knowledge of your target.

Most important of all: Know which instructions on your current hardware are atomic. Without this knowledge to start with you can't possibly create an atomic patch.

You then have the problem of making a series of atomic writes (of atomic instructions) such that execution mid-patch doesn't crash/hang/alter execution in unintended ways. This is not a trivial problem to solve. Suspend the process and play it safe.

EDIT: I just realized that I took the bait and answered in a way that only considered hooking, i.e patching, even though your question specifically asks how to change code flow atomically during execution. Proper DLL injection should allow you to do this pretty reliably in most cases, though like always it's never a sure thing when you are modifying a running process.

Answer 3

Here's an older article on how hotpatching was implemented in Windows. If you want it done absolutely atomically, it has to be done from the kernel mode. There's no way around it. Here's the walkthrough:

• Set your thread's IRQL to CLOCK1_LEVEL (heck, you can even try HIGH_LEVEL), which is way above 2, that will pretty much stop all task switching in that system for the time your patching code is running. It is also high enough to preempt most interrupts. Or, you can try to disable them with a CLI instruction.

• Also schedule CPU-specific DPCs on all CPUs but your thread to keep those DPCs busy. (This is needed in case of a multi-core CPU.)

This basically turns your patching thread into a single threaded environment for a short while.

• To ensure that no other running thread was stopped on that short span of executable memory where you're applying your 5-byte JMP, walk through the context of each thread and check its RIP value. In an unlikely event that it overlaps, either cancel the patch and retry after a short while, or raise the thread's IRQL for a very short while and then lower it back. Then check again. Repeat N times until its RIP doesn't overlap with the patch.

• Finally apply the patch. Make sure to do it as quickly as possible. Try not to call any outside functions. Just do a quick REP MOVS on a prepared memory blob.

• You'll probably need to clear the processor's instruction cache. (In case the old code before the patch was in there.)

• Then undo all the steps above to restore the system back into the working state.

PS. Should work in theory. In practice, debugging this will be a living hell. Obviously do it in a VM and be ready to reboot (a lot.)

---

Edit: Here's an actual example, taken from the DebugView tool. If you know what it does, it tries to capture a program's debugger output. If you enable kernel debugger output on an older OS, that tool has no other option but to install a trampoline on a DbgPrint function on a live system when the DebugView starts up.

Here's how it does it (it uses somewhat old kernel functions, but it still delivers the idea):

1. Get number of CPU cores (it uses an older KeNumberProcessors global variable as such):

(For modern code I would probably use KeQueryActiveProcessors() with its bitmask, and KeQueryGroupAffinity() to account for number of CPUs greater than 32/64.)

2. Make sure that the current thread is running on the CPU core 0 by calling KeSetAffinityThread:

(Then check global variable bDontSet_FuncTrampoline in case we don't need to set this trampoline & restore thread affinity by jumping to step 6. But that case is not interesting.)

3. Then check if we just have one CPU core, and if so jump to step 5. (Not very interesting either.) Otherwise set global variable nCountCpuCores to the count of CPU cores, and reset global bAllowToContinue_CoreNon0_DeferredRoutine flag to 0:

4. Set each CPU core (other than 0, i.e. rsi pointer starts from index 1, or 0x8 offset in bytes) for high importance DPCs (deferred procedure calls) for our DeferredRoutine with the context set to CPU core number:

This will basically preempt whatever those other cores were doing and direct them to our DPC.

5. Then for our thread running in core 0, execute DPC routine DeferredRoutine:

6. After which restore this thread's affinity to what it used to be before:

---

Now the interesting thing is what happens in DeferredRoutine:

(Note that this routine will be executed on each CPU core.)

A. The first step, set IRQL for the thread to CLOCK_LEVEL (or 13 for x64 code.) This is done by using the cr8 CPU register. Doing this will block processing of the most interrupts:

B. Then decrement the counter in nCountCpuCores global variable, but do it using a lock CPU prefix to ensure synchronization among all CPU cores:

C. Check what CPU core this thread runs on and enter a spin-loop accordingly:

C.1. (Right side block in the code flow above.) For non-0 cores continue spinning in a loop while global variable bAllowToContinue_CoreNon0_DeferredRoutine is 0.

C.2. (Left side block in the code flow above.) For core 0, continue spinning in a loop while the count of processed cores in the nCountCpuCores global variable doesn't reach 0.

(I would personally add to each of those loops a pause instruction to ensure that CPU doesn't waste too much power while "spinning".)

C.3. Once the condition C.2. has been met, it means that we have our core 0 all to ourselves and all other cores are busy spinning in the loop in C.1. and we can proceed by calling our install_func_Trampoline function to install required trampoline.

C.4. When we're done with the trampoline, remember to release all cores from the spin-loop in C.1. by setting bAllowToContinue_CoreNon0_DeferredRoutine to 1.

D. Lastly, very important, restore IRQL back to what it used to be:

Return error nt_status code, if so. Otherwise, we're done!