• Overview

This tool makes it easy to capture the steps taken during the build process of a software project. This can be very useful for:

• Understanding build processes
• Debugging obscure build problems
• Applying static analysis and verification tools

In the first two cases, this tool gives a low-level view of exactly the set of files accessed by the build process (e.g., fully resolving all file includes and relative paths) in a way that is difficult to achieve by merely reading and understanding a build system. In a sense, it identifies the bill of materials for software.

In the third case, assurance tools generally require rebuilding programs in special modes or with alternative compilers (e.g., into LLVM bitcode for analysis or instrumentation). Doing so is typically labor intensive, as it requires extensive work to understand an existing build system, and more work still to modify it. This tool provides a way to apply analysis tools in a build system agnostic way.

This tool is primarily designed to help tame the myriad build systems of the C/C++ ecosystem, but it applies to any software project with a build step.

• Usage

This tool wraps your normal build command and builds LLVM bitcode when possible. It arranges things such that any binary artifacts produced by your build system (e.g., object files, archives, shared libraries, or binaries) have their LLVM bitcode attached to them and accessible. The workflow of this tool proceeds in two phases:

1. Building your software (using the ~generate-bitcode~ command wrapper)
2. Extracting your bitcode (using the ~extract-bitcode~ command)

There tool also supports some auxiliary commands for generating traces of builds for visualization and understanding.

An example use of the tool is shown below for a ~make~-based build:

+BEGIN_SRC

$ build-bom generate-bitcode -- make $ build-bom extract-bitcode /path/to/binary --output=/tmp/output.bc

+END_SRC

In the first step, the tool acts as a wrapper around the real build system. It runs the build system and, if it observes any compilation commands, it runs an extra build of the source file using clang to generate bitcode. It attaches bitcode to object files, and then resumes the build.

In the next step, the tool extracts all of the accumulated bitcode.

** Bitcode Generation Options

The ~generate-bitcode~ command has a number of options that may be useful in various contexts.

• ~--bc-out~: Directory to place LLVM bitcode (bc) output data
• ~--clang~: Specify the full name (or path if desired) of a clang binary to use
• ~--suppress-automatic-debug~: By default, ~build-bom~ automatically adds the ~-g~ flag when building bitcode to generate debug information; this flag inhibits this behavior
• ~--strict~: Generate strictly adhering bitcode: leaves in compilation arguments (e.g. optimization, arch-specific flags, etc.) that are normally removed because they might be problematic for ~clang~.
• ~--inject-argument=STRING~: Directs ~build-bom~ to inject an additional argument (~STRING~) into the command line for the command used to build bitcode (e.g., to configure the optimization level or level of debug information); can be specified multiple times
• ~--remove-argument=REGEX~: Directs ~build-bom~ to remove any argument matching the regular expression from the argument list when generating bitcode; can be specified multiple times

Note that ~--suppress-automatic-debug~ could be useful in cases where the generated bitcode is disruptively large due to the presence of unneeded debug information. Since it is useful in most cases, however, it is generated by default.

The ~--remove-argument~ can be used to remove arguments that inhibit analysis (e.g., ~-O3~ may apply optimizations that are annoying for a static analysis, so it could be removed). Note that ~build-bom~ does not add any anchors to the beginning (e.g., ~^~) or end (e.g., ~$~) of the regular expression it is given, so users will likely want to specify them manually as needed. The regular expressions are matched against each argument as seen by ~execve~, so conjoined single-argument flags like ~--foo=bar~ count as a single flag that could be matched against, while ~--foo bar~ appear as two separate entries in the argument list seen by ~execve~. Without explicit regex anchors, ~build-bom~ allows the specified regex to match /anywhere/ in each argument.

** Bitcode Extraction Options

The ~extract-bitcode~ command also provides options:

• ~--llvm-link-path~: Specify a path to the ~llvm-link~ binary; this is useful if LLVM commands are versioned on your system

• Design

The tool uses low-level operating system services to observe builds and record their actions. On Linux, it uses ~ptrace~ to observe every system call. When a source compilation command is observed, the tool generates the corresponding bitcode file using clang. It attaches the bitcode to the object file via a separate ELF section, allowing bitcode to be accumulated as a side effect of the build. At every stage, bitcode remains attached to build artifacts to ensure it is not lost.

There are four key observations enabling this approach to bitcode collection:

1. Whenever we see the original build system compile a C/C++ file, we know we need to make the corresponding bitcode file
2. We can attach arbitrary extra data (e.g., bitcode) to object files in extra ELF sections
3. ELF sections containing data without special meaning are concatenated by the linker
4. Standard tar files can be concatenated to produce a valid tar file that is the union of their contents

We wrap our generated bitcode in singleton tar files and allow the linker to accumulate them for us. When we want to collect aggregated bitcode for executable artifacts, we simply extract the tar file from their special LLVM bitcode ELF sections, extract the collected bitcode, and link it together with ~llvm-link~.

Observe as well that the ~build-bom~ process useful for selective rebuilds: rebuilding only a portion of the sources will still have access to llvm-bitcode ELF sections in object from previous builds. The use of ~build-bom~ also has graceful degradation properties: object files which do not have llvm bitcode sections in their ELF (i.e. built separately without using ~build-bom~) will simply not contributed to the ELF section/tarfile accumulation of bitcode; the final extraction ~llvm-link~ does not need to be total and is tolerant of unresolved symbols.

The bitcode extracted will be representative of the binary code contained in the specified file. It will not necessarily be identical to that code due to strictness flags, differences between clang and the native build compiler, and a different linking step.

• Executable: bitcode for the entirety of the executable, including any static libraries the executable was linked with, but not including any shared libraries (even if they themselves were built with ~build-bom~) or components built outside of a ~build-bom~ process.
• Shared library: bitcode for the entirety of the shared library will be extracted, excluding any components of the library built outside of a ~build-bom~ process.
• Static library: bitcode will only be available for the last element in the library. This is due to ~build-bom~'s use of ~objcopy~ to extract the ELF sections: all llvm bitcode sections from each member of the static library will be extracted, but they will successively overwrite each other, leaving only the bitcode from the last entry in the library. This is also noted in https://github.com/travitch/build-bom/issues/42.

This tool is also able to record all relevant system calls into a log. The tracing is designed to capture all of the information necessary to replay a build. It currently doesn't capture everything (especially file move and directory operations), but will be extended as-needed. Beyond system calls, it also captures the environment and working directory of each executed command.

The tool currently supports Linux, but is designed so that it will be modular enough to have separate tracing implementations for MacOS and Windows, while sharing the rest of the code.

** Related Tools

There are a number of tools in the space of build interposition for the purpose of instrumentation, build modification, or bitcode generation. Most are based on acting as wrappers around standard compilers either through explicit modification of the build system or by placing themselves earlier in the ~PATH~ as aliases to real build tools.

• Tools like [[https://github.com/travitch/whole-program-llvm][wllvm]] and [[https://github.com/SRI-CSL/gllvm][gllvm]] solve the problem of wrapping compiler commands to generate LLVM, but require manual modifications to the build system in order to invoke them.
• Tools like [[https://github.com/rizsotto/Bear][Bear]] and [[https://github.com/trailofbits/blight][blight]] provide general mechanisms for interposing on build commands by pretending to be a normal compiler earlier in your PATH. Bear additionally provides another mode based on using ~LD_PRELOAD~ to hook calls to ~execve~.
• Other tools record builds and replay them

These tools can be very effective, but have some issues with more complex build systems:

• Scripts that wrap compiler commands can have difficulty successfully getting through complex configure scripts that e.g., do aggressive version sniffing
• While configure script difficulties can be sometimes avoided by configuring with the real compiler and replacing or interposing the real build commands after the fact, it doesn't always work
  • Build systems that record absolute paths at configure time are difficult to modify completely
  • Some build systems run additional configure scripts as part of the build process, which are again difficult to pass using interposition
• Using ~LD_PRELOAD~ to hook ~execve~ can be very effective, but difficult, as some build systems rely on failed ~execve~ calls to perform ~PATH~ searches; it is difficult to know which commands succeed, as ~execve~ never returns in those contexts
• The ~LD_PRELOAD~ approach does not work for statically-linked compilers (so Bear has a fallback to wrapper scripts)
• Some types of multi-stage build require that all intermediate results actually be built and be executable (e.g., if a build creates a code generator and uses it for later build stages)
• Replaying builds based solely on compiler commands works for simple builds, but fails when build systems create and delete directories during the build (or make other interesting environmental changes) that make consistent replay very difficult

As a whole, these tools tend to require significant effort in build system understanding and modification to work on more complex codebases. The build-bom tool is designed to eliminate any need for build system modification to achieve its goals (primarily LLVM bitcode generation, but potentially arbitrary build modifications). In contrast to the other tools in this space, it monitors and interposes on the build system at the level of ~ptrace~.

• By working at the level of ~execve~, it can observe when real build tools are called, no matter what names the build system thinks they actually have (e.g., if the build system itself uses build tool wrappers)
• By working directly at the syscall level (rather than ~LD_PRELOAD~), it works on both static and dynamically-linked build tools
• By working at the level of ~execve~, build-bom never needs to implement any shell lexing logic, as the shell has already lexed all of the arguments
• By working at the ~ptrace~ level, build-bom is able to determine which calls to ~execve~ actually succeed
• Moreover, it can delay action until after build steps succeed (since it can observe when execed processes terminate, not just when they are about to start)
• The build-bom tool is able to maintain persistent state for an entire build without external storage, as a single process is able to view all build steps
• Configure scripts are never a problem (at any stage of the build) because the real build always runs
• Multi-stage builds always work because intermediate tools are build and are executable

** Caveats

• It is not possible to take advantage of parallel builds while using this tool, as all system calls in the entire build tree are serialized through a single tracing process

• Build steps that rely on input our output redirection through pipes are very difficult to replicate, since their targets are not observable without modeling the calling process file descriptor connection logic

• Full Example

Here is a full example on a real codebase:

+BEGIN_SRC sh

wget https://ftp.gnu.org/gnu/tar/tar-1.32.tar.gz tar xf tar-1.32.tar.gz cd tar-1.32 ./configure

Run the build under the bitcode generator

build-bom generate-bitcode -- make

Use a suffix of on LLVM tools because they are version-suffixed on Ubuntu

build-bom extract-bitcode src/tar --output=../tar.bc --llvm-tool-suffix=-9

+END_SRC

• Roadmap

• Serious polish required

• Build step dependency analysis for in-order replay

• Add more thorough support for Linux system calls

  • Add a 32 bit x86 syscall table
  • Add ARM syscall tables
  • Explore automated processing of system call argument lists

• Additional tools

  • Dependency graph analyzer and visualizer
  • A command to list all targets (or all library targets or all executable targets)
  • A command to rebuild a target binary with libfuzzer, Address Sanitizer, or Thread Sanitizer
  • Add a command to randomly test for potential missing dependencies in build systems

• Automated granular filename tracking (to precisely model renames)

• Fix parallel builds

• Full handling of environment variables

• Additional normalization policies

  • Ignore trivial dependencies like ld.so
  • Add ability to ignore dynamically loaded library dependencies

• Easier scripting

• MacOS backend based on Dtrace

• Windows backend

• License

Licensed under either of

• Apache License, Version 2.0 [[LICENSE-APACHE][LICENSE-APACHE]] or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license [[LICENSE-MIT][LICENSE-MIT]] or http://opensource.org/licenses/MIT)

at your option.

• Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.