diff options
Diffstat (limited to 'docs/DataFlowSanitizerDesign.rst')
| -rw-r--r-- | docs/DataFlowSanitizerDesign.rst | 220 |
1 files changed, 220 insertions, 0 deletions
diff --git a/docs/DataFlowSanitizerDesign.rst b/docs/DataFlowSanitizerDesign.rst new file mode 100644 index 0000000..32db88b --- /dev/null +++ b/docs/DataFlowSanitizerDesign.rst @@ -0,0 +1,220 @@ +DataFlowSanitizer Design Document +================================= + +This document sets out the design for DataFlowSanitizer, a general +dynamic data flow analysis. Unlike other Sanitizer tools, this tool is +not designed to detect a specific class of bugs on its own. Instead, +it provides a generic dynamic data flow analysis framework to be used +by clients to help detect application-specific issues within their +own code. + +DataFlowSanitizer is a program instrumentation which can associate +a number of taint labels with any data stored in any memory region +accessible by the program. The analysis is dynamic, which means that +it operates on a running program, and tracks how the labels propagate +through that program. The tool shall support a large (>100) number +of labels, such that programs which operate on large numbers of data +items may be analysed with each data item being tracked separately. + +Use Cases +--------- + +This instrumentation can be used as a tool to help monitor how data +flows from a program's inputs (sources) to its outputs (sinks). +This has applications from a privacy/security perspective in that +one can audit how a sensitive data item is used within a program and +ensure it isn't exiting the program anywhere it shouldn't be. + +Interface +--------- + +A number of functions are provided which will create taint labels, +attach labels to memory regions and extract the set of labels +associated with a specific memory region. These functions are declared +in the header file ``sanitizer/dfsan_interface.h``. + +.. code-block:: c + + /// Creates and returns a base label with the given description and user data. + dfsan_label dfsan_create_label(const char *desc, void *userdata); + + /// Sets the label for each address in [addr,addr+size) to \c label. + void dfsan_set_label(dfsan_label label, void *addr, size_t size); + + /// Sets the label for each address in [addr,addr+size) to the union of the + /// current label for that address and \c label. + void dfsan_add_label(dfsan_label label, void *addr, size_t size); + + /// Retrieves the label associated with the given data. + /// + /// The type of 'data' is arbitrary. The function accepts a value of any type, + /// which can be truncated or extended (implicitly or explicitly) as necessary. + /// The truncation/extension operations will preserve the label of the original + /// value. + dfsan_label dfsan_get_label(long data); + + /// Retrieves a pointer to the dfsan_label_info struct for the given label. + const struct dfsan_label_info *dfsan_get_label_info(dfsan_label label); + + /// Returns whether the given label label contains the label elem. + int dfsan_has_label(dfsan_label label, dfsan_label elem); + + /// If the given label label contains a label with the description desc, returns + /// that label, else returns 0. + dfsan_label dfsan_has_label_with_desc(dfsan_label label, const char *desc); + +Taint label representation +-------------------------- + +As stated above, the tool must track a large number of taint +labels. This poses an implementation challenge, as most multiple-label +tainting systems assign one label per bit to shadow storage, and +union taint labels using a bitwise or operation. This will not scale +to clients which use hundreds or thousands of taint labels, as the +label union operation becomes O(n) in the number of supported labels, +and data associated with it will quickly dominate the live variable +set, causing register spills and hampering performance. + +Instead, a low overhead approach is proposed which is best-case O(log\ +:sub:`2` n) during execution. The underlying assumption is that +the required space of label unions is sparse, which is a reasonable +assumption to make given that we are optimizing for the case where +applications mostly copy data from one place to another, without often +invoking the need for an actual union operation. The representation +of a taint label is a 16-bit integer, and new labels are allocated +sequentially from a pool. The label identifier 0 is special, and means +that the data item is unlabelled. + +When a label union operation is requested at a join point (any +arithmetic or logical operation with two or more operands, such as +addition), the code checks whether a union is required, whether the +same union has been requested before, and whether one union label +subsumes the other. If so, it returns the previously allocated union +label. If not, it allocates a new union label from the same pool used +for new labels. + +Specifically, the instrumentation pass will insert code like this +to decide the union label ``lu`` for a pair of labels ``l1`` +and ``l2``: + +.. code-block:: c + + if (l1 == l2) + lu = l1; + else + lu = __dfsan_union(l1, l2); + +The equality comparison is outlined, to provide an early exit in +the common cases where the program is processing unlabelled data, or +where the two data items have the same label. ``__dfsan_union`` is +a runtime library function which performs all other union computation. + +Further optimizations are possible, for example if ``l1`` is known +at compile time to be zero (e.g. it is derived from a constant), +``l2`` can be used for ``lu``, and vice versa. + +Memory layout and label management +---------------------------------- + +The following is the current memory layout for Linux/x86\_64: + ++---------------+---------------+--------------------+ +| Start | End | Use | ++===============+===============+====================+ +| 0x700000008000|0x800000000000 | application memory | ++---------------+---------------+--------------------+ +| 0x200200000000|0x700000008000 | unused | ++---------------+---------------+--------------------+ +| 0x200000000000|0x200200000000 | union table | ++---------------+---------------+--------------------+ +| 0x000000010000|0x200000000000 | shadow memory | ++---------------+---------------+--------------------+ +| 0x000000000000|0x000000010000 | reserved by kernel | ++---------------+---------------+--------------------+ + +Each byte of application memory corresponds to two bytes of shadow +memory, which are used to store its taint label. As for LLVM SSA +registers, we have not found it necessary to associate a label with +each byte or bit of data, as some other tools do. Instead, labels are +associated directly with registers. Loads will result in a union of +all shadow labels corresponding to bytes loaded (which most of the +time will be short circuited by the initial comparison) and stores will +result in a copy of the label to the shadow of all bytes stored to. + +Propagating labels through arguments +------------------------------------ + +In order to propagate labels through function arguments and return values, +DataFlowSanitizer changes the ABI of each function in the translation unit. +There are currently two supported ABIs: + +* Args -- Argument and return value labels are passed through additional + arguments and by modifying the return type. + +* TLS -- Argument and return value labels are passed through TLS variables + ``__dfsan_arg_tls`` and ``__dfsan_retval_tls``. + +The main advantage of the TLS ABI is that it is more tolerant of ABI mismatches +(TLS storage is not shared with any other form of storage, whereas extra +arguments may be stored in registers which under the native ABI are not used +for parameter passing and thus could contain arbitrary values). On the other +hand the args ABI is more efficient and allows ABI mismatches to be more easily +identified by checking for nonzero labels in nominally unlabelled programs. + +Implementing the ABI list +------------------------- + +The `ABI list <DataFlowSanitizer.html#abi-list>`_ provides a list of functions +which conform to the native ABI, each of which is callable from an instrumented +program. This is implemented by replacing each reference to a native ABI +function with a reference to a function which uses the instrumented ABI. +Such functions are automatically-generated wrappers for the native functions. +For example, given the ABI list example provided in the user manual, the +following wrappers will be generated under the args ABI: + +.. code-block:: llvm + + define linkonce_odr { i8*, i16 } @"dfsw$malloc"(i64 %0, i16 %1) { + entry: + %2 = call i8* @malloc(i64 %0) + %3 = insertvalue { i8*, i16 } undef, i8* %2, 0 + %4 = insertvalue { i8*, i16 } %3, i16 0, 1 + ret { i8*, i16 } %4 + } + + define linkonce_odr { i32, i16 } @"dfsw$tolower"(i32 %0, i16 %1) { + entry: + %2 = call i32 @tolower(i32 %0) + %3 = insertvalue { i32, i16 } undef, i32 %2, 0 + %4 = insertvalue { i32, i16 } %3, i16 %1, 1 + ret { i32, i16 } %4 + } + + define linkonce_odr { i8*, i16 } @"dfsw$memcpy"(i8* %0, i8* %1, i64 %2, i16 %3, i16 %4, i16 %5) { + entry: + %labelreturn = alloca i16 + %6 = call i8* @__dfsw_memcpy(i8* %0, i8* %1, i64 %2, i16 %3, i16 %4, i16 %5, i16* %labelreturn) + %7 = load i16* %labelreturn + %8 = insertvalue { i8*, i16 } undef, i8* %6, 0 + %9 = insertvalue { i8*, i16 } %8, i16 %7, 1 + ret { i8*, i16 } %9 + } + +As an optimization, direct calls to native ABI functions will call the +native ABI function directly and the pass will compute the appropriate label +internally. This has the advantage of reducing the number of union operations +required when the return value label is known to be zero (i.e. ``discard`` +functions, or ``functional`` functions with known unlabelled arguments). + +Checking ABI Consistency +------------------------ + +DFSan changes the ABI of each function in the module. This makes it possible +for a function with the native ABI to be called with the instrumented ABI, +or vice versa, thus possibly invoking undefined behavior. A simple way +of statically detecting instances of this problem is to prepend the prefix +"dfs$" to the name of each instrumented-ABI function. + +This will not catch every such problem; in particular function pointers passed +across the instrumented-native barrier cannot be used on the other side. +These problems could potentially be caught dynamically. |
