Index: clang/docs/ControlFlowIntegrityDesign.rst =================================================================== --- clang/docs/ControlFlowIntegrityDesign.rst +++ clang/docs/ControlFlowIntegrityDesign.rst @@ -274,6 +274,74 @@ need to check that the address is in range and well aligned. This is more likely to occur if the virtual tables are padded. +Forward-Edge CFI for Virtual Calls by Interleaving Virtual Tables +================================================================= + +Alternatively, Dimitar et. al. in [1]_ proposed a novel approach that interleaves virtual tables. +This approach is more efficient in terms of space because padding and bit vectors are no longer needed. +At the same time, it is also more efficient in terms of performance because in the interleaved virtual +table address points are consecutive, thus the validity check of a virtual vtable pointer is simplified +to a range check. + +On the high level, the interleaving scheme consists of two steps: 1) order virtual tables by a pre-order +traversal of the class hierarchy and 2) interleave the virtual tables entry by entry. + +.. [1] `Protecting C++ Dynamic Dispatch Through VTable Interleaving `_. Dimitar Bounov, Rami Gökhan Kıcı, Sorin Lerner. + +Order virtual tables by a pre-order traversal of the class hierarchy +-------------------------------------------------------------------- + +This step is common to both the old scheme described above and the interleaving scheme. For each class +this step ensures that classes in sub-hierarchies of this class are laid out as close as possible. + +For example, consider the following four C++ classes: + +.. code-block:: c++ + + struct A { + virtual void f1(); + }; + + struct B : A { + virtual void f1(); + virtual void f2(); + }; + + struct C : A { + virtual void f1(); + virtual void f3(); + }; + + struct D : B { + virtual void f1(); + virtual void f2(); + virtual void f4(); + }; + +This step will arrange the virtual tables for A, B, C, and D in the order of *vtable-of-A, vtable-of-B, vtable-of-D, vtable-of-C*. +In this order, for any class all the compatible virtual tables will appear consecutively. + +Interleave the virtual tables entry by entry +-------------------------------------------- + +This step is where the interleaving scheme deviates from the old scheme. Instead of laying out +whole virtual tables in the previously computed order, the interleaving scheme lays out table +entries one by one from the virtual tables in that order. Dynamic dispatch still +works under this scheme because the interleaved virtual table has the property that for +each virtual funtion the distance between an entry of this function and the corresponding +address point is always the same. + +To follow the example used in the previous step, the interleaved virtual table will look like this: + +.. csv-table:: Interleaved Virtual Table Layout for A, B, C, D + :header: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 + + A::offset-to-top, B::offset-to-top, D::offset-to-top, C::offset-to-top, &A::rtti, &B::rtti, &D::rtti, &C::rtti, &A::f1, &B::f1, &D::f1, &C::f1, &B::f2, &D::f2, &C::f3, &D::f4 + +Let us take f2 as an example to see the aforementioned property. In the interleaved virtual table, +there are two entries for f2: B::f2 and D::f2. The distance between &B::f2 +and its address point &B::f1 is 3 entry-length, so is the distance between &D::f2 and &D::f1. + Forward-Edge CFI for Indirect Function Calls ============================================