dataesr/scientific-paragraphs-categorization huggingface dataset:
g. link-time optimisation) or inline-assembly snippets. This omission prevents debugging with standard tools and, more annoyingly, implies that hacks and workarounds are required to use a wide range of useful program analysis instruments. It also implies that the programmer must manually encode the DWARF bytecode in the inline-assembly snippets. Slow Accessing a row of the table requires interpreting all the bytecode from the beginning of the enclosing function, and this must be repeated for each stack-frame on the call stack. Despite the aggressive caching performed by libraries as libunwind, DWARF-based unwinding can be a bottleneck for time-sensitive program analysis tools. For instance the perf profiler is forced to copy the whole stack on taking each sample and to build the backtraces offline: this solution has a memory and time overhead but also serious confidentiality and security flaws.
We are not the only ones to raise these concerns. We have been told that all critical code at Google is compiled with a frame pointer, to ensure fast and reliable backtraces [Engineer 2018]. Similarly, the Linux kernel by default relies on a frame pointer to provide reliable backtraces. This incurs in a space and time overhead; for instance it has been reported (https://lwn. net/Articles/727553/) that the kernel's. text size increases by about 3. 2%, resulting in a broad kernel-wide slowdown. Measurements have shown a slowdown of 5-10% for some workloads (https://lore. kernel. org/lkml/ 20170602104048. jkkzssljsompjdwy@suse. de/T/#u). Linus Torvalds uses colourful words to summarise why DWARF-based unwinding is unreliable: Sorry, but last time was too f***ing painful. The whole (and *only*) point of unwinders is to make debugging easy when a bug occurs.
eh_frame stack description tables do not depend on source code semantics, but capture instead an abstract symbolic execution of the binary machine instructions. Once we can cross-check binaries against their DWARF unwind tables, it is only a small extra step to synthesise DWARF unwind tables from binaries. Our second contribution is a technique to synthesise DWARF unwind information by automatic analysis of ELF binaries lacking unwind information. This is implemented and evaluated in a second tool. Finally, our third contribution is to investigate various strategies to precompile the. eh_frame table into assembly code, and to have extended libunwind to support the precompiled tables. We have observed 25x speedups on DWARF-unwind intensive applications, at the cost of a 2. 5x increase of the size of unwind tables on disk.
The first two contributions are presented in Section 2, after a precise description of the close relationship between assembly code and unwind tables. The third contribution is presented in Section 3. Related and future works, including ongoing discussion with developers of mainstream tools, conclude the paper. All along the paper we focus on the columns needed to walk the stack and build a backtrace: this is the most common operation that involves. eh_frame tables. This allows us to keep the presentation compact and accessible, by ignoring some of the callee-saved register columns. be extended to support all callee-saved registers. Overall, our contributions show that relatively simple techniques are effective in improving DWARF-based unwinding reliability and efficiency, hopefully paving the way for their adoption by mainstream tools.
VALIDATION AND SYNTHESIS OF DWARF-UNWIND TABLES To understand the close relation between assembly code and the associated unwind tables, we report in Figure  2  the assembly code for the unwind table of Figure  1 , and the table itself. Entries have been aligned so that the table describe the stack state before executing the corresponding instruction. To make the presentation compact we focus on the CFA, rbp and ra columns, and omit the other callee-saved register columns. Their treatment is analogous to that of the rbp column. Upon invoking the function foo, before its first instruction is executed, the semantics of the call instruction ensures that the address where the return address is stored is in rsp. The table reflects this by setting the CFA at rsp+8 and the return address at c-8. Next, the first push instruction updates the stack and decrements the value of rsp by 8: the table updates the CFA computation to rsp+16, reflecting the new value of the stack pointer.
Similarly for the other push or pop instructions and the sub $0x68, %rsp instruction at line 6, which allocates space on the stack: all these modify the stack pointer and the CFA computation is updated accordingly. Instructions that do not modify the stack pointer leave entries unchanged in the unwind table. In this example all the expressions to compute the CFA are defined in term of the stack pointer rsp, so tracking instructions that modify the stack pointer is enough. In general, DWARF expressions can involve arbitrary registers and can read arbitrary memory locations, so a complete host instruction set semantics might be needed. In Section 3. 2 we will investigate the real-world uses of DWARF instructions but for now, the key remark we make is that all the information stored in the unwind table can be recomputed from the semantics of the assembly code and the calling conventions.
We track the stack addresses where the return addresses have been saved by keeping a stack of all the return address addresses, called shadow stack. Whenever we observe a call instruction being executed, we push the current value of the stack pointer on the shadow stack. Similarly, upon execution of a ret instruction, one entry is popped (and discarded) from the shadow stack. Implementation. This strategy requires being able to execute an assembly program one step at a time, while accessing the machine state. There are several alternatives for this task, of varying robustness and efficiency. We have opted to build upon the gdb debugger: the debugger gives us access to the machine state, can execute a binary one assembly instruction at a time, and can be scripted using Python. Our tool thus is implemented as a Python script that implements literally the dynamic analysis described above, sketched in Algorithm 1.
For ELF and DWARF parsing we rely on the pyelftools library  [Bendersky 2019 ] to which we contributed a parser for the. eh_frame table, since only the rarely-used. debug_frame table was initially supported. This approach is simple and robust, and can validate arbitrarily complex control flow or DWARF unwind tables. Additionally it is easily portable to multiple architectures: in addition to supporting the x86_64 architecture and calling conventions, we have experimental support for the IBM Power architecture. The tool can process about 3000 assembly instructions per second, measured by dividing the overall running time by the number of assembly instructions executed, easily obtained via gdb. Validation speed is independent of the program being verified, the overhead coming mostly from gdb step-by-step execution and pyelftools decoding of.
eh_frame tables. Although the overhead is important, our implementation is fast enough for batch testing as done by C fuzzers or library test-suites. At work. We have put our validation tool at work to test both the binaries generated by C mainstream compilers and the binary of the glibc library. By leveraging the CSmith fuzzer  [Yang et al. 2011 ] and CReduce test-case reducer  [Regehr et al. 2012] , we have performed random testing of the. eh_frame table generation of the gcc and clang C compilers. The program we reported in Figure  3  was indeed found with fuzzing: the compiler forgot to insert a. cfi_ * directive to reflect the update to the stack pointer due to restoring register rbx. If an interrupt occurs between the pop and ret instructions, the unwind information might be wrong, despite using -fasynchronous-unwind-tables which is supposed to be exact at every instruction.
We have filed a report to clang developers (https://bugs. llvm. org/show_bug. cgi?id=13161#c2); the last version of the compiler does not miscompile the. eh_frame table anymore, suggesting that the issue has been resolved. Our previous example contradicts the common belief that the unwinder does not fail on C/C++ compiled code. Hand-written assembly code raises extra challenges. We focus on the glibc library, that often relies on inline assembly and comes with an extensive test suite. To illustrate the complexity of unwinding correctly hand-written assembly we report on the excerpt in Figure  4  of #define LLL_STUB_UNWIND_INFO_START \ ". section. eh_frame,\"a\",@progbits\n" \ "5:\t" ". long 7f-6f # Length of CIE\n" \ "6:\t" ". long 0x0  the lowlevellock. h file. This file is part of the implementation of futexes (fast user-space mutexes), and the low-level thread synchronisation is implemented in inline assembly.
The figure reports the intricate, hand-written, DWARF. eh_frame bytecode corresponding to the low-level lock functions. Despite great care by the authors, we identified an off-by-one error in one of the return-address offsets; this error causes, for instance, gdb to duplicate one _L_lock_19 call in the backtrace: Breakpoint 2, 0x0000000000406c2c in _L_lock_19 () (gdb) bt #0 0x0000000000406c2c in _L_lock_19 () #1 0x0000000000406c3f in _L_lock_19 () #2 0x00000000004069c6 in abort () #3 0x0000000000401017 in main () at foo1. c:4 Most other program analysis tools, rather than a relatively harmless duplicate frame, would crash upon following a bad pointer in an unwind table.
Synthesis of. eh_frame Tables In an ideal world, no programmer would have to hand-write DWARF unwind bytecode: this should be inferred by the compiler for the inline assembly snippets, as it is for the rest of the C code. This is the starting point for this section: we will design and implement a tool that synthesises DWARF unwind tables directly from the assembly program text. We have seen that there is a close relationship between assembly instructions and updates to the lines of the unwind table. We also observe that the unwind data itself is structured in a collection of Frame Description Entries (FDEs), each FDE providing the unwind information for a given function in the original source code: ABI calling conventions ensure that unwind tables are compositional. Therefore our synthesis algorithm only needs to analyse one function body at a time.
Let us initially consider a function for which the compiler can statically compute the stack size at any instruction. In this case, before each assembly instruction, the CFA can always be expressed as a static offset from the stack pointer register. Additionally, suppose that we can reliably build the control flow graph for the assembly code of the function. Let us consider the running example in Figure  5 , and focus on the entry basic block. Calling conventions ensure that before the first instruction the address of the return address is stored at rsp. Therefore we can synthesise the standard CFA = rsp+8; ra = c-8 entry. We can then analyse all the following instructions in the basic block, one at a time, checking if they modify the stack pointer. If Fig. 6. Dynamically stack-allocated data-structures they do, we update the CFA offset accordingly.
In turn, no conflict can arise when merging the propagated unwind lines, and in presence of loops computing a fixpoint is not necessary. The forward analysis iterates the process of computing the unwind information for a basic block, and propagating the last entry to the successor blocks, until unwind information is synthesised for all the basic blocks. Suppose now that semantics of the code implies that stack offsets cannot be statically computed. This happens in presence of variable-size data structures dynamically allocated on the stack, as in the example reported in Figure  6. In this case it turns out that compilers systematically fall back to using a base-pointer register even if the -fomit-frame-pointer option has been specified, as revealed by a quick glance to the unwind table (or to the assembly).
As a sanity check, if different rows are propagated to a merge point the tool aborts and reports an error. Once the table is synthesised, it is encoded using simple DWARF bytecode instructions, analogous to those used by gcc or clang. Heuristics. The first key choice when synthesising the unwind row for a given IP is guessing if the register rbp is being used as base pointer or as general purpose register. Rather than attempting to identify instruction patterns, we use a two-pass approach. Our algorithm first attempts to synthesise a table indexing the CFA exclusively with the register rsp. We call this state rsp-index mode. If synthesis in rsp-index mode fails, then the process is started again, allowing both rsp and rbp registers to be used index the CFA. In practice this method is successful because if the first pass succeeds, then a correct rsp-based CFA indexing was found; if not, then the source code must contain variable-size stack-allocated data structures, and as we have seen the compiler itself opted to use rbp as a base pointer.
In detail, when CFA is expressed as an offset of the rsp register (both in rsp-indexing and rbpindexing mode), then it must be updated whenever an instruction modifies the rsp register. Such instructions are represented in the BAP internal representation as rsp <-EXPR. We perform a simple syntactic analysis of EXPR: if EXPR is of the form rsp + offset, then the CFA is updated with the specified offset. Otherwise, the analysis is said to lose track and it is restarted in rbp-index mode if it was in rsp-index mode, and aborted otherwise. When the algorithm is in rbp-index mode and CFA is set as an offset of rbp, by definition the assembly code is relying on a stable frame pointer in rbp, then the offset should not affected by assembly instructions. However, in rbp-index mode, the synthesis must detect when the CFA indexing switches from register rsp to register rbp and vice-versa.
One binary compiled at -O0 has dead code inside a function. Our algorithm cannot synthesise unwind tables for dead code because the forward dataflow analysis cannot guess initial values. This is not an issue as unwinding will never be called from a location in dead code. In one case, compiled with -O1, clang generates code for which no correct. eh_frame entry exists while handling abort paths. This is arguably a bug in clang linearisation algorithm and we will report to clang developers. The two observed failures at -O2 and the other failure at -O1 are instead cases in which synthesis is performed correctly, but clang generates incorrect tables. These will be reported to the clang developers. Hand-written tests checked that our tool synthesises correct tables for C code including inline assembly that artificially move the stack pointer or the base pointer in a consistent way -that is, such that there exists a valid table -compiled with gcc.
In this section we explore a strategy to precompile the. eh_frame section of a binary to executable code directly responsible for unwinding one stack frame. Rather than generating directly assembly code, we actually translate DWARF bytecode to C code later compiled by gcc in -O2 mode, to benefit from gcc optimisations. We show one example in Listing 1 to 4. The generated code consists of a single function, called _eh_elf, taking as arguments the current instruction pointer and the current memory context describing the values stored in processor registers. The _eh_elf function then returns a new memory context containing the values the registers after unwinding the current frame. Unwind contexts are defined in Listing 4: the values of processor registers are stored with type uintptr_t, while flags is a 8-bits value, indicating for each register whether it is present or not in this context, plus an error bit useful to report errors due e.
g. to unsupported instructions. Only registers rip, rbp, rsp and rbx are tracked by the contexts: in Section 3. 2 we provide evidence that these are sufficient to perform stack-unwinding reliably (surprisingly rbx is used a few times in glibc and other less common libraries to hold the CFA address in common functions). Observe that the _eh_elf function is compositional and it can be called multiple times in a row to unwind the stack, as in the pseudocode below: while(!unwinding_done()) { current_context = _eh_elf(current_context[RA], current_context); do_something_with_context(current_context); } The C code for case 0x615. 0x618 in Listing 3 is compiled from the first two instructions of Listing 1. In Section 2 we assumed we had a reliable interpreter of DWARF bytecode and we were thus working directly with the rows and columns of the interpreted unwind table.
Our ahead-oftime DWARF unwind compiler works instead directly on DWARF instructions and expressions. The DWARF standard is written in English prose and it only defines an informal semantics for instructions DW_CFA_def_cfa: r7 (rsp)ofs 8 or DW_CFA_offset: r16 (rip)at cfa-8: the former sets the CFA of the current row at rsp+8, the latter sets the offset of the register rip (that is of the ra column) at CFA-8. The C code we generate is nothing more than a precise formalisation of the DWARF semantics. The full details are tedious, so we omit them here but we report the complete semantics and translation functions in Appendix A. Implementation details. We store the compiled unwinding code in separate shared object files, which we call eh_elfs: whenever the unwinder needs the _eh_elf function, it dynamically links its eh_elfs.
eh_frame. Several space optimisations, such as filtering out empty FDEs and merging together equivalent rows, were made in order to shrink the size of the eh_elfs. Replacing the switch/case construct with an explicit if/else tree implementing a binary search on the instruction pointer intervals was extremely effective in reducing the binary size. We also outline the code whenever possible: identical "switch cases" bodies are moved outside of the binary search tree, identified with a label and invoked using a goto. When applied to the eh_elfs code for libc, it turns out that of a total of 20827 rows, only 302 (1. 5 %) unique rows remain after the outlining. For flexibility of use, a setting of our compiler optionally enables another parameter to the _eh_elf function, deref, which is a function pointer.
Benchmarks and Evaluation To provide relevant benchmarks of the eh_elfs' performance, hundreds or thousands of stack unwindings must be sampled, because a single frame unwinding with regular DWARF takes the order of magnitude of 10 µs. At the same time, to mimic real-world unwind calls, unwind points should be distributed across the program; we should not unwind repeatedly from the same IP in the same function. The perf sampling-based profiler is an ideal candidate for providing such benchmarks; when invoked to reconstruct the call-graph, perf stops the traced program at regular intervals, unwinds the stack recording the current nested function calls, and integrates the sampled data in the end. As such it easily unwinds a running program thousands of times in a few seconds. We run perf-benchmarking on several standard Unix binaries, including gzip, find, sqlite3, and the python runtime executing a simple program.
Many of these spend most of the time in few functions, thus providing an ideal situation for comparing against libunwind caching. This allows us to evaluate a worst-case speedup for our ahead-of-time compilation strategy. Additionally, to stress-test the robustness of strategy, we run perf-benchmarking on hackbench  [Zhang 2008 ]. This small program is designed to stress-test and benchmark the Linux scheduler by spawning processes or threads that communicate with each other: it generates large stack activity, and is additionally linked against the pthread library. Interfacing eh_elfs with perf required adding eh_elfs support to libunwind, a widely used unwinder library. This required passing explicitly the memory map of the process to a library initialisation function; apart from this, the modified version of libunwind produced is entirely compatible with the vanilla version.
28 seconds. The unwinding errors are due to truncated stack records. Since perf dumps the last n bytes of the call stack (for a given n), and only keeps those for later unwinding, large stacks lead to lost information when analysing the results. Our implementation reports the same errors of the vanilla libunwind implementation. Space overhead. We measure the space taken by the eh_elfs and compare it against the size of. eh_frame tables for hackbench and the libraries on which it depends. Outlining proves effective. We note that hackbench has a significantly bigger growth than the other shared objects. This is because hackbench has a much smaller. eh_frame and the outlined data is reused only a few times, compared to e. g. glibc, in which the outlined data is heavily reused.
RELATED WORK We are not the first ones to have remarked the poor reliability of DWARF debug information, but most of the testing of DWARF tables is done with tools that lack a principled design. For instance, LLVM has a stack-unwinding stress-test suite, briefly described in https://reviews. llvm. org/D10454, that steps through the code line by line and then tests unwinding from each instruction. We have seen that testing unwinding is slow, in particular it is much slower than validating a DWARF entry as done by our validator tool. This test-suite is reported to to need minutes to run even over simple code, and is not part of the default testing of LLVM. Similar in principle but aimed at to provide quantitative values that indicate the quality of the debugging experience, the DExTer (Debugging Experience Tester) by Sony, available from https: //github.
Synthesis of DWARF frame information can be seen as reverse engineering of binary code, for which various other techniques have been demonstrated. Most similar are perhaps techniques for decompiling to high-level code  [Cifuentes 1994 ], which must analyse binary code to extract patterns of control flow. However it does not focus on techniques for recovering stack frame sizes. The work most closely related to ours is the ORC project, part of the Linux kernel. ORC is briefly described by  [Corbet 2017 ] and stems from a previous project, called objtool, that statically verifies that the frame pointer is correctly updated along all the execution paths of an x86_64 binary. Building backtraces with a frame pointer requires that all functions which call other functions must first create a stack frame and update the frame pointer; otherwise the caller of the first function will be skipped on a stack trace.
This is routinely done by the compiler when the -fno -omit-frame-pointer option is used, but for inline assembly the frame setup instructions have to be written by hand. Since the Linux kernel relies extensively on inline assembly, objtool attempts to verify that programmers do not accidentally break the frame pointer discipline. Building on objtool, Linux developers proposed a new, simple, binary format for unwind tables, called ORC, that can be edited using the internal objtool metadata. These include the size of the stack at each instruction or how to compute the base of the stack frame. At the time of writing ORC tables have the same expressiveness of the. eh_frame tables inferred by our synthesis tool. However they require an ad-hoc unwinder and, contrarily to our DWARF-based approach, they cannot be easily extended to support richer expressions.