[cfe-dev] RFC: Syringe -- A Dynamic Behavior Injection Framework

[David Blaikie via cfe-dev]

On Mon, Sep 10, 2018 at 10:38 PM Paul Kirth via cfe-dev <
cfe-dev at lists.llvm.org> wrote:

> On Mon, Sep 10, 2018 at 5:46 PM Kostya Serebryany <kcc at google.com> wrote:
>
>> [I haven't given this much though, so forgive me if my questions are
>> naive]
>>
>>
> No. These are great questions. Thank you for the feedback.
>
>
>> * I think you should state the goals and major use cases more clearly.
>> E.g. if the goal to ever have this in production (looks like it's not)
>> then the design is scary given all the threats associated with indirect
>> calls.
>>
>>
> The goal of this work is to allow developers to dynamically enable new
> behaviors as their program runs, for some set of behaviors determined at
> compile time.  I think that any use case where the author may wish to
> transitively modify the program's normal behavior is a good candidate. The
> main use cases I've thought about revolve around things that usually fall
> under the umbrella of testing(fault injection, dependency injection,
> probabilistic sanitizers, etc.). As I mentioned in the RFC, Syringe takes a
> general approach, and can be used for a variety of tasks.
>
> As for whether to use Syringe in production, I'd be a bit hesitant to
> recommend it for deployment. That being said, unlike most indirect call
> sites, functions modified by Syringe have exactly two valid targets. This
> is far from the intractable problem facing Control Flow Integrity in the
> general case. I don't see a reason why the implementation should not insert
> forward edge CFI checks. Syringe also brings up some 'trusting trust' types
> of concerns, so I would say my recommendation would be to avoid using it in
> production, until these shortcomings have been addressed.
>
> In short, while Syringe isn't currently intended for use in production, I
> think with some thought and careful design the security weaknesses
> introduced by our instrumentation can be mitigated so that someday that
> limitation could be lifted.
>
>
>> * What are your performance requirements?
>> If this is not needed for production, then perhaps 5%-10% is tolerable.
>>
>>
> Estimating the overhead from instrumentation is highly dependent on what
> functions are instrumented. i.e. changing a call inside a tight loop will
> have a much greater impact  on changing the performance than if we
> instrument a function that is only called infrequently. Choosing an
> appropriate benchmark to accurately demonstrate the overhead of our
> approach would be challenging.
>
> I think the majority of use cases for this type of framework are less
> concerned with the overhead involved, and more interested in having the
> ability to dynamically change the program's behavior. Many of the most
> obvious use cases fall somewhere roughly under testing. I don't want to
> limit what Syringe is intended to do (its quite general), but I think many
> of the most beneficial uses will be out of production, for example fault
> injection.
>
> Should Syringe move into code review, I would expect a portion of the
> discussion to center on how best to benchmark the cost of this type of
> instrumentation.
>
>
>> * I'd like to understand more about what's missing for you in XRay.
>> IIRC, XRay injects ~11 bytes of NOPs into the function prologue, which
>> you can replace with any code you like, any time you want.
>> You may for example replace those NOPs with a jump to the payload, which
>> will achieve your goal. No? Why?
>>
>>
> Modifying  XRay was something we considered, but ultimately decided
> against.
>

Not sure it'd even involve modifying XRay - but potentially using XRay
as-is and building on top of it (but yeah, I don't really know where the
boundaries are between the generic functionality XRay provides, as Kostya
described it, and the features built on top of it - and don't mean to get
into a fussy discussion about the distinctions)


> One of the reasons being that for our initial use case (fault injection)
> we felt that the overhead of repeatedly writing to code pages may be too
> expensive if we needed to quickly enable and disable the new behavior. In
> my understanding, XRay works by making code pages writable, and then
> updating the NOP sleds of the target functions. The overhead introduced by
> changing permissions on the code pages may make quickly enabling and
> disabling new behaviors difficult, if we require fine grained toggling
> (i.e. only inject new behavior during a single call). I think in a tight
> loop, or in closely interleaved set of threaded calls the contention to
> change the code pages might cause our system to loose some of its
> precision. My understanding here could be incomplete, however, so if I am
> wrong, please correct me.
>

Seems to me if the overhead was too high, you could avoid it by updating
the NOP sled once to point to the "handler" & the handler could make a
determination if the original function was to be called & call/jump back
into it ("if (disabled) call original"). Admittedly, adding some overhead
to the disabled case.

A tool built on top of Detours I'd used before did something like this -
allowed filtering based on caller (walking the call stack to see if the
caller was a certain function - and only redirecting the functionality if
it was), thread id, etc, etc. And it did so by intercepting all calls to
the target function (within the scope of the redirector - a C++ RAII style
object) & then deciding whether it was an interesting one or not.


> The other reason was that our proposed approach was more straightforward,
> as indirect calls and stubs are easy to understand and allowed us to
> leverage parts of ORC.
>
> * You can have a simpler implementation that for every instrumented
>> function does
>>      if (DivertFuncToPayload) return PayloadForFunc(args); // tail call
>> and thus instead of an indirect call on main path you have a load/cmp on
>> the main path and a direct call on the slow path.
>>
>>
> This is another alternative that we considered, but again thought that our
> approach was more straightforward. However, it is worth noting that using
> direct as suggested above may also have the benefit of simplifying  some
> complexities with C++ templates as well. Should we move forward with
> upstreaming, this is one aspect of the design I would wish to compare
> against the alternative.
>
>
>> --kcc
>>
>>
>> On Wed, Sep 5, 2018 at 6:10 PM Paul Kirth via cfe-dev <
>> cfe-dev at lists.llvm.org> wrote:
>>
>>> TLDR; During my internship at Google I developed a proof of concept
>>> framework for supporting dynamic behavior injection. It allows users to
>>> specify alternate implementations of functions, and dynamically switch
>>> between the original and new behavior at runtime. It works by dispatching
>>> the original call through a function pointer that can either point to the
>>> original function body or the injected version. We would like feedback
>>> about our approach, and the communities’ interest in adding our framework
>>> to LLVM.
>>>
>>> -----
>>>
>>> Overview
>>>
>>> Syringe takes a different approach from other systems interested in
>>> modifying runtime behavior, such as Detours or XRay, and borrows
>>> inspiration from JIT compilers to inject new behaviors. JIT compilers often
>>> use stub functions to dispatch execution to specially optimized versions of
>>> function bodies. Our approach uses the idea of an indirect call through a
>>> stub function to instead dispatch control flow to either the original
>>> behavior or the newly injected behavior. Our runtime component exposes APIs
>>> to allow the user to modify this behavior during execution.
>>>
>>> We achieve this through the following steps:
>>>
>>>
>>>    1.
>>>
>>>    Target functions are cloned and renamed
>>>    2.
>>>
>>>    The original function body is replaced with a stub
>>>    3.
>>>
>>>    The new stub makes an indirect call through a pointer controlled by
>>>    the Syringe runtime
>>>    4.
>>>
>>>    This implementation pointer will either point to the original
>>>    implementation or the new payload
>>>    5.
>>>
>>>    The payload function is given an alias that can be used to resolve
>>>    its address at link-time
>>>    6.
>>>
>>>    Callbacks into the runtime are used toggle between the two
>>>    implementations of a target function
>>>
>>>
>>> Syringe introduces the notion of injection sites (the target function
>>> whose behavior should be changed), and payloads (the new behavior to inject
>>> into the target function). These functions must always come in pairs, and
>>> will cause an error if they do not. However, this is a link time error, as
>>> Syringe payloads are designed such that they can exist in different
>>> translation units from their target function. Because these bindings don't
>>> get resolved until linking, we must tie a payload to its injection site. We
>>> achieve this by creating an alias for the payload based on its target
>>> function. The runtime registration functions can then reference this alias,
>>> and the dynamic linker can patch in the correct address when the Syringe
>>> runtime is being initialized.
>>>
>>> The Syringe runtime is very thin. It currently consists of a
>>> registration function, and a few APIs for changing the active variant for a
>>> target function. When calling into the runtime, the target function is
>>> looked up in the runtime metadata, and the implementation pointer’s value
>>> is changed to the other variant.
>>>
>>> Our current approach involves the following:
>>>
>>> 1.
>>>
>>> *Clang + LLVM*: Add support for function attributes(
>>> `[[clang::syringe_injection_site]]`,
>>> `[[clang::syringe_payload(“target_function_name”)]]` ) to indicate if a
>>> function should be considered a syringe injection site or a syringe payload
>>> respectively. The payload attribute requires a parameter to bind the
>>> syringe site and payload for use in the runtime.
>>>
>>> 2.
>>>
>>> *Clang*: Add flags (`-fsyringe`,
>>> `-fsyringe-config-file=”/path/to/config.yml”`) to enable and control
>>> Syringe instrumentation.
>>>
>>> 3.
>>>
>>> *LLVM*: Add a Transformation pass that instruments syringe sites and
>>> payloads, and generates the necessary initialization functions. Function
>>> cloning, stub creation, and implementation pointer management are all
>>> implemented using existing code in LLVM’s ORC library.
>>>
>>> 4.
>>>
>>> *compiler-rt* : Implement a small library called “syringe” that exposes
>>> the required APIs for toggling between implementations:
>>>
>>> `__syringe__toggle_impl(&targetFunction)` uses the function address to
>>> toggle its implementation
>>>
>>> `__syringe__cxx_toggle_impl(&Class::targetMethod, &class_instance)`
>>> looks up the target address in the class vtable according to the Itanium
>>> ABI, and uses that to change the runtime value of the target function
>>> pointer
>>>
>>> `__syringe_registration(&orig_function, &orig_impl, &injected_func,
>>> &impl_ptr)` used to initialize the runtime data used by Syringe.
>>>
>>> Improvements
>>>
>>> Our prototype works well in many cases, but has a few shortcomings which
>>> we would like to address.
>>>
>>> First, our implementation is almost completely contained in the LLVM
>>> backend, and thus has no real understanding of C++. While we can currently
>>> use the mangled names of functions to achieve our desired result, this is
>>> cumbersome and error prone. There are additional limitations when
>>> considering C++ Templates and class hierarchies. Right now, class methods
>>> can be instrumented and replaced by payloads in the same class hierarchy.
>>> In this case, an injected method must inherit from the target method’s
>>> class and override the target function. This has additional challenges if
>>> the function is virtual, since our runtime uses function addresses to
>>> resolve which function should be modified. As a result, we do not support
>>> injection of virtual methods outside of the Itanium ABI, where we can
>>> reliably index into the vtable and thus perform the correct behavior in the
>>> runtime. We currently consider C++ templates completely out of scope for
>>> the current implementation, chiefly because they are too cumbersome to use
>>> without support from the frontend.
>>>
>>> In light of these shortcomings, we believe that our current
>>> implementation should be extended with more support from the clang frontend
>>> to:
>>>
>>> 1. Alleviate the need to mangle function names
>>>
>>> 2. Directly support C++ class hierarchy
>>>
>>> 3. Add support for C++ Templates
>>>
>>> 4. Add new intrinsics to directly handle runtime lookups (i.e. directly
>>> insert real addresses for class methods without (ab)using the Itanium ABI)
>>>
>>> I have been exploring how to achieve this in Clang, and believe that it
>>> is possible to achieve these properties. Clang can correctly resolve the
>>> unmangled name and  can add a new payload annotation with the mangled name
>>> if required. Since this is abstracted away from the user, there is little
>>> downside to directly tagging the functions in this way.
>>>
>>> Because Clang understands the class hierarchy, we can add a new
>>> annotation for class methods that will take the target base class as a
>>> parameter. Clang, in Sema, can look up the base class and add the correct
>>> payload annotation to the resulting LLVM function. Similarly for Templates,
>>> any instantiated template function, or dependent method, can have its
>>> payload forcibly instantiated, and have the new instantiation correctly
>>> tagged. This requires that for templates the target and payload definitions
>>> must appear in the same translation unit, so that their instantiations can
>>> be correctly resolved. While this forces a change to the actual source code
>>> (even if it is only an #include directive) it seems to be a reasonable way
>>> to offer support for a feature a core language feature.
>>>
>>> Lastly, calls into the Syringe runtime currently use function addresses
>>> as keys to manipulate the target function pointer. It should be possible to
>>> use some new intrinsic(s) that can correctly resolve the address of
>>> functions and methods without relying on ABI details. Because the compiler
>>> will be aware of how Syringe works, it should be possible to have the
>>> compiler directly insert the correct address while providing an intuitive
>>> API to the user.
>>>
>>>
>>> Other considerations and future work:
>>>
>>> Currently Syringe modifies the global definition of a function for the
>>> entire program. While in some cases this behavior makes sense there are
>>> several strong use cases for handling behavior injection on a per thread
>>> basis. One solution here is to use thread local storage to manage these
>>> pointers on a per-thread basis. It is also possible to manage a global set
>>> of metadata with per thread information. Suggestions on approaches here are
>>> most welcome.
>>>
>>> Syringe was designed to help automate behavior injection by
>>> understanding a small set of trigger conditions that could be responsible
>>> for enabling and disabling the injected behavior. In our initial designs
>>> these triggers were often based on profiling counters that could be used to
>>> toggle the behavior after some threshold was exceeded. Currently, this is
>>> left up to the programmer, but our YAML configuration already supports
>>> these sort of annotations. In principle there is no reason why these
>>> quality of life instrumentation should not be implemented as the use and
>>> design of Syringe solidifies.
>>>
>>> Our Syringe prototype currently uses dynamic storage to manage runtime
>>> metadata. Future versions should transition from this to storing the
>>> required metadata in RO memory. The indirect call stubs should also have
>>> additional CFI checks added, because we statically know that only two valid
>>> targets for any particular Syringe function pointer exist.
>>>
>>> Questions
>>>
>>>    1.
>>>
>>>    Is this something the LLVM community is interested in having?
>>>    2.
>>>
>>>    Do you have feedback on our proposed approach/improvements?
>>>
>>>
>>>
>>> --
>>> Paul Kirth
>>> _______________________________________________
>>> cfe-dev mailing list
>>> cfe-dev at lists.llvm.org
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>>>
>>
>
> --
> Paul Kirth
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20180911/49355eee/attachment.html>