Processor micro-architecture internals (branch prediction, branch predictor and indirect branch）

Introduction

Recently, our security research on leverage a Performance Monitor Unit as a technique for monitoring a function call and control-flow integrity.

We leverage a following perf event , and we faced an interesting problem , 

Figure[1]


The one of the following event is almost always get counted by Performance Counter.
BR_MISP_EXEC.TAKEN_INDIRECT_NEAR_CALL
The interesting question is that why such instruction is always get mispredicted ?  There are couples of things we need to clarify and dive into....

Indirect Branch

jmp rax ; Indirect jmp
call  rax ; Indirect call

Branch Target Buffer

BTB is a table that in a processor internal, for optimising the processor performance during it's making a branch decision (yes/no), and it is indexed by current RIP (instruction pointer) and the value is branch target address ,  BTB's structure as following figure




Figure[2]

Branch Predictor

Branch predictor leverages BTB and perform as following prediction process, due to the indirect branch is always unconditionally executed, as a result, the branch predictor always taken that instruction and build the BTB entry when it's first executed.

However, there is a main point for the heavy misprediction, despite of the indirect branch is unconditional branch, the target address is still unexpected until the branch instruction actually decoded, such situation may cause BTB will easily get wrong if the register/memory content changed later. (such as, windows' SSDT dispatcher, almost always different across each execution)



Figure[3]


That's mean, an indirect instruction is being executed with a different target address frequently, (such as, C++ vtable function call / Window's SSDT dispatcher, etc), the branch prediction may easily be wrong,  it's not because the branch shouldn't be taken, instead, it is due to the BTB stored the wrong (old) value and use it compare to the new branch target address, and as a result, it gets wrong result (mis-prediction, see Figure[4]) ,

It finally flush the misprediction instruction, delete the BTB entry, and restart the instruction.  As a result, these kind of indirect branch suffering such infinite-misprediction-loop. :)


Figure[4]

Reference





Comments

Post a Comment

Popular posts from this blog

Android Kernel Development - Kernel compilation and Hello World

Image
Introduction Due to the lack of the material that clearly kick off the  android kernel development , hopefully it will gives the clearer  guide to develop your own android driver and debugging it. p.s. Due to the version differential, this article  is not ensure all of the Android Version , SDK version,  source  code , and   Emulator is compatible , however,  the door of   research is always opened,   just   feel   free   to contact me  and play together :P All the materials   are also  saved   in   the VM  ,   you can just directly leverage  the  existing VM Image for  development or  alternatively, as a research and studying, follow the following guide  to create your own workplace.  Android kernel didn't have dynamically insmod like the other linux, so this tutorial is trying to build a new Android Kernel and make test our kernel driver as well. Material Ubuntu 18.04.2 LTS  Android studio Android ndk-r10 Android SDK Goldfish v3.10 VMWare 15   
Read more

How does Nested-Virtualization works?

Image
What is Nested virtualization? ----------------------------------------------------------------------------------------------------- Nowadays, Software Security is becoming more important criteria in the industry, and in recent years, virtualization as a popular topic for protecting / attacking a software, however, most of the virtualization technology framework (bluepill-liked) is not provide an ability that let a guest virtualize one more layer, we called it "Nested Virtualization", level 2. Basic Virtual Machine Monitor Architecture ------------------------------------------------------------------------------------------------------ Figure[1] Host VMM trap any type of event which wants to monitor, such as, Interrupt, exception, privileged register access, one of this event is VMX instruction, after VMM loaded, VMM can always monitor a any one of the  VMX instructions, which provide a good chance for us. As following chart: Figure[2] VMM Life Cycle
Read more

Understanding ACPI and Device Tree

Image
This blog document and help to understand how ACPI works AML (ACPI Machine Language) AML is compiled binary that written in the ACPI Source Language (ASL) and it is interpreted binary that interpreted by AML interpreter during OS runtime. AML is provided by hardware manufacture and embedded in the firmware, it provides the entire device base hierarchy (all thing that equipped on your motherboard, and cannot be removed.) and function to OS that could interface the dedicated hardware, like PCI-ISA bridge or processor, controlling the power, turn on/off, etc. AML operated by different object type, and defined in definition block in firmware table (DSDT / SSDT) AML object type Scope String   Constant Package Control Method Device   ACPI Object  Naming Convention 1. All object names are 32 bits long. 2. The first byte of a name must be one of 'A' - 'Z', '_'. 3. Each of the remaining bytes of a name must be one of 'A' - 'Z', '0' - '
Read more