Re: TCG Address Sanitizer Optimization.

["Alex Bennée" <alex.bennee@linaro.org>]

Jon Wilson <jonwilson030981@googlemail.com> writes:

(Adding Richard, the TCG maintainer to CC)

> I am attempting to optimize some TCG code which I have previously written for
> qemu-libafl-bridge (https://github.com/AFLplusplus/qemu-libafl-bridge), the 
> component used by the LibAFL project when fuzzing binaries using QEMU to 
> provide runtime instrumentation. The code is used to write additional TCG into 
> basic blocks whenever a load or store operation is performed in order to provide
> address sanitizer functionality.

I would like to figure out if we can push any of this instrumentation
into TCG plugins so you can avoid patching QEMU itself. I guess you need
something that allows you to hook a memory address into some sort of
gadget?

> Address sanitizer is quite simple and works by mapping each 8-byte region of
> address space to single byte within a region called the shadow map. The address
> (on a 64-bit platform) of the shadow map for a given address is:
>
>     Shadow = (Mem >> 3) + 0x7fff8000;
>
> The value in the shadow map encodes the accessibility of an address:
>
>     0  - The whole 8 byte region is accessible.
>     1 .. 7 - The first n bytes are accessible.
>     negative - The whole 8 byte region is inaccessible.
>
> The following pseudo code shows the algorithm:
>
> ////////////////////////////////////////////////////////////////////////////////
>
> https://github.com/google/sanitizers/wiki/addresssanitizeralgorithm
>
> byte *shadow_address = MemToShadow(address);
> byte shadow_value = *shadow_address;
> if (shadow_value) {
>   if (SlowPathCheck(shadow_value, address, kAccessSize)) {
>     ReportError(address, kAccessSize, kIsWrite);
>   }
> }
>
> // Check the cases where we access first k bytes of the qword
> // and these k bytes are unpoisoned.
> bool SlowPathCheck(shadow_value, address, kAccessSize) {
>   last_accessed_byte = (address & 7) + kAccessSize - 1;
>   return (last_accessed_byte >= shadow_value);
> }
>
> ////////////////////////////////////////////////////////////////////////////////
>
> My current implementation makes use of conditional move instructions to trigger
> a segfault by way of null dereference in the event that the shadow map indicates
> that a memory access is invalid.
>
> ////////////////////////////////////////////////////////////////////////////////
>
> #if TARGET_LONG_BITS == 32
> #define SHADOW_BASE (0x20000000)
> #elif TARGET_LONG_BITS == 64
> #define SHADOW_BASE (0x7fff8000)
> #else
> #error Unhandled TARGET_LONG_BITS value
> #endif
>
> void libafl_tcg_gen_asan(TCGTemp * addr, size_t size)
> {
>     if (size == 0)
>         return;
>
>     TCGv addr_val = temp_tcgv_tl(addr);
>     TCGv k = tcg_temp_new();
>     TCGv shadow_addr = tcg_temp_new();
>     TCGv_ptr shadow_ptr = tcg_temp_new_ptr();
>     TCGv shadow_val = tcg_temp_new();
>     TCGv test_addr = tcg_temp_new();
>     TCGv_ptr test_ptr = tcg_temp_new_ptr();
>
>     tcg_gen_andi_tl(k, addr_val, 7);
>     tcg_gen_addi_tl(k, k, size - 1);
>
>     tcg_gen_shri_tl(shadow_addr, addr_val, 3);
>     tcg_gen_addi_tl(shadow_addr, shadow_addr, SHADOW_BASE);
>     tcg_gen_tl_ptr(shadow_ptr, shadow_addr);
>     tcg_gen_ld8s_tl(shadow_val, shadow_ptr, 0);
>
>     /*
>      * Making conditional branches here appears to cause QEMU issues with dead
>      * temporaries so we will instead avoid branches.

This sounds like a TCG bug that may have been fixed.

>      We will cause the guest
>      * to perform a NULL dereference in the event of an ASAN fault. Note that
>      * we will do this by using a store rather than a load, since the TCG may
>      * otherwise determine that the result of the load is unused and simply
>      * discard the operation. In the event that the shadow memory doesn't
>      * detect a fault, we will simply write the value read from the shadow
>      * memory back to it's original location. If, however, the shadow memory
>      * detects an invalid access, we will instead attempt to write the value
>      * at 0x0.
>      */

Why not conditionally call a helper here? Forcing the guest to actually
fault seems a bit hammer like.

>     tcg_gen_movcond_tl(TCG_COND_EQ, test_addr,
>         shadow_val, tcg_constant_tl(0),
>         shadow_addr, tcg_constant_tl(0));
>
>     if (size < 8)
>     {
>         tcg_gen_movcond_tl(TCG_COND_GE, test_addr,
>             k, shadow_val,
>             test_addr, shadow_addr);
>     }
>
>     tcg_gen_tl_ptr(test_ptr, test_addr);
>     tcg_gen_st8_tl(shadow_val, test_ptr, 0);
> }
>
> ////////////////////////////////////////////////////////////////////////////////
>
> However, I would like test an implementation more like the following to see how
> the performance compares. Whilst this introduces branches, the fast path is much
> more likely to be executed than the slow path and hence bypassing the additional
> checks and unnecessary memory writes I am hopeful it will improve performance.
>
> ////////////////////////////////////////////////////////////////////////////////
>
> void libafl_tcg_gen_asan(TCGTemp* addr, size_t size)
> {
>     if (size == 0) {
>         return;
>     }
>
>     if (size > 8) {
>         size = 8;
>     }
>
>     TCGLabel *done = gen_new_label();
>
>     TCGv addr_val = temp_tcgv_tl(addr);
>     TCGv shadow_addr = tcg_temp_new();
>     TCGv_ptr shadow_ptr = tcg_temp_new_ptr();
>     TCGv shadow_val = tcg_temp_new();
>     TCGv k = tcg_temp_new();
>     TCGv zero = tcg_constant_tl(0);
>     TCGv_ptr null_ptr = tcg_temp_new_ptr();
>
>     tcg_gen_shri_tl(shadow_addr, addr_val, 3);
>     tcg_gen_addi_tl(shadow_addr, shadow_addr, SHADOW_BASE);
>     tcg_gen_tl_ptr(shadow_ptr, shadow_addr);
>     tcg_gen_ld8s_tl(shadow_val, shadow_ptr, 0);
>
>     tcg_gen_brcond_tl(TCG_COND_EQ, shadow_val, zero, done);
>
>     tcg_gen_andi_tl(k, addr_val, 7);
>     tcg_gen_addi_tl(k, k, size - 1);
>
>     tcg_gen_brcond_tl(TCG_COND_LT, shadow_val, k, done);
>
>     tcg_gen_tl_ptr(null_ptr, zero);
>     tcg_gen_st8_tl(zero, null_ptr, 0);
>
>     gen_set_label(done);
> }
>
> ////////////////////////////////////////////////////////////////////////////////
>
> However, when I change to using this implementation, I get the following error.
> I have tested it with a trivial hello world implementation for x86_64 running in
> qemu-user. It doesn't occur the first time the block is executed, therefore I
> think the issue is caused by the surrounding TCG in the block it is injected
> into?
>
> ////////////////////////////////////////////////////////////////////////////////
> runner-x86_64: ../tcg/tcg.c:4852: tcg_reg_alloc_mov: Assertion `ts->val_type == TEMP_VAL_REG' failed.
> Aborted (core dumped)
> ////////////////////////////////////////////////////////////////////////////////
>
> I would be very grateful for any advice of how to resolve this issue, or any
> alternative approaches I could use to optimize my original implementation. The
> code is obviously a very hot path and so even a tiny performance improvement
> could result in a large performance gain overall.

-- 
Alex Bennée
Virtualisation Tech Lead @ Linaro