Sanitization is a process of detecting potential issues during the execution process. Sanitizers instrument (embedding checks into the generated code) and interact with the runtime linked into an executable, either statically or dynamically. In the past month, I've finished a functional support of MKSANITIZER with Address Sanitizer and Undefined Behavior Sanitizer. MKSANITIZER uses the default compiler runtime shipped with Clang and GCC and ported to NetBSD.
Over the past month, I've implemented from scratch a clean-room version of the UBSan runtime. The initial motivation was the need of developing one for the purposes of catching undefined behavior reports (unspecified code semantics in a compiled executable) in the NetBSD kernel. However, since we need to write a new runtime, I've decided to go two steps further and design code that will be usable inside libc and as a standalone library (linked .c source code) for the use of ATF regression tests.
The original Clang/LLVM runtime is written in C++ with features that are not available in libc and in the NetBSD kernel. The Linux kernel version of an UBSan runtime is written natively in C, and mostly without additional unportable dependencies, however, it's GPL, and the number of features is beyond the code generation support in the newest version of Clang/LLVM from trunk (7svn).
The implementation of µUBSan is located in
common/lib/libc/misc/ubsan.c.
The implementation is mostly Machine Independent, however, it assumes a typical 32bit or 64bit CPU with support for typical floating point types.
Unlike the other implementations that I know, µUBSan is implemented without Undefined Behavior.
I've decided to write the whole µUBSan runtime as a single self-contained .c soure-code file,
as it makes it easier for it to be reused by every interested party.
This runtime can be either inserted inline or linked into the program.
The runtime is written in C, because C is more portable, it's the native language of libc and the kernel, and additionally
it's easier to match the symbols generated by the compilers (Clang and GCC).
According to C++ ABI, C++ symbols are mangled,
and in order to match the requested naming from the compiler instrumentation
I would need to partially tag the code as C file anyway (extern "C").
Additionally, going the C++ way without C++ runtime features is not a typical way to use C++,
and unless someone is a C++ enthusiast it does not buy much.
Additionally, the programming language used for the runtime is almost orthogonal to the instrumentated programming language
(although it must have at minimum the C-level properties to work on pointers and elementary types).
µUBSan supports all report types except -fsanitize=vtpr.
For vptr there is a need for low-level C++ routines to introspect and validate the low-level parts of the C++ code
(like vtable, compatiblity of dynamic types etc).
While all other UBSan checks are done directly in the instrumented and inlined code, the vptr one is performed in runtime.
This means that most of the work done by a minimal UBSan runtime is about deserializing reports into verbose messages and printing them out.
Furthermore there is an option to configure a compiler to inject crashes once an UB issue will be detected and the runtine might not be needed at all,
however this mode would be difficult to deal with and the sanitized code had to be executed with aid of a debugger to extract any useful information.
Lack of a runtime would make UBSan almost unusable in the internals of base libraries such as libc or inside the kernel.
This Clang/LLVM arguments for UBSan are documented as follows in the official documentation:
-fsanitize=alignment: Use of a misaligned pointer or creation of a misaligned reference.
-fsanitize=bool: Load of a bool value which is neither true nor false.
-fsanitize=builtin: Passing invalid values to compiler builtins.
-fsanitize=bounds: Out of bounds array indexing, in cases where the array bound can be statically determined.
-fsanitize=enum: Load of a value of an enumerated type which is not in the range of representable values for that enumerated type.
-fsanitize=float-cast-overflow: Conversion to, from, or between floating-point types which would overflow the destination.
-fsanitize=float-divide-by-zero: Floating point division by zero.
-fsanitize=function: Indirect call of a function through a function pointer of the wrong type (Darwin/Linux[/NetBSD], C++ and x86/x86_64 only).
-fsanitize=implicit-integer-truncation: Implicit conversion from integer of larger bit width to smaller bit width, if that results in data loss. That is, if the demoted value, after casting back to the original width, is not equal to the original value before the downcast. Issues caught by this sanitizer are not undefined behavior, but are often unintentional.
-fsanitize=integer-divide-by-zero: Integer division by zero.
-fsanitize=nonnull-attribute: Passing null pointer as a function parameter which is declared to never be null.
-fsanitize=null: Use of a null pointer or creation of a null reference.
-fsanitize=nullability-arg: Passing null as a function parameter which is annotated with _Nonnull.
-fsanitize=nullability-assign: Assigning null to an lvalue which is annotated with _Nonnull.
-fsanitize=nullability-return: Returning null from a function with a return type annotated with _Nonnull.
-fsanitize=object-size: An attempt to potentially use bytes which the optimizer can determine are not part of the object being accessed. This will also detect some types of undefined behavior that may not directly access memory, but are provably incorrect given the size of the objects involved, such as invalid downcasts and calling methods on invalid pointers. These checks are made in terms of __builtin_object_size, and consequently may be able to detect more problems at higher optimization levels.
-fsanitize=pointer-overflow: Performing pointer arithmetic which overflows.
-fsanitize=return: In C++, reaching the end of a value-returning function without returning a value.
-fsanitize=returns-nonnull-attribute: Returning null pointer from a function which is declared to never return null.
-fsanitize=shift: Shift operators where the amount shifted is greater or equal to the promoted bit-width of the left hand side or less than zero, or where the left hand side is negative. For a signed left shift, also checks for signed overflow in C, and for unsigned overflow in C++. You can use -fsanitize=shift-base or -fsanitize=shift-exponent to check only the left-hand side or right-hand side of shift operation, respectively.
-fsanitize=signed-integer-overflow: Signed integer overflow, where the result of a signed integer computation cannot be represented in its type. This includes all the checks covered by -ftrapv, as well as checks for signed division overflow (INT_MIN/-1), but not checks for lossy implicit conversions performed before the computation (see -fsanitize=implicit-conversion). Both of these two issues are handled by -fsanitize=implicit-conversion group of checks.
-fsanitize=unreachable: If control flow reaches an unreachable program point.
-fsanitize=unsigned-integer-overflow: Unsigned integer overflow, where the result of an unsigned integer computation cannot be represented in its type. Unlike signed integer overflow, this is not undefined behavior, but it is often unintentional. This sanitizer does not check for lossy implicit conversions performed before such a computation (see -fsanitize=implicit-conversion).
-fsanitize=vla-bound: A variable-length array whose bound does not evaluate to a positive value.
-fsanitize=vptr: Use of an object whose vptr indicates that it is of the wrong dynamic type, or that its lifetime has not begun or has ended. Incompatible with -fno-rtti. Link must be performed by clang++, not clang, to make sure C++-specific parts of the runtime library and C++ standard libraries are present.
Additionally the following flags can be used:
-fsanitize=undefined: All of the checks listed above other than unsigned-integer-overflow, implicit-conversion and the nullability-* group of checks.
-fsanitize=undefined-trap: Deprecated alias of -fsanitize=undefined.
-fsanitize=integer: Checks for undefined or suspicious integer behavior (e.g. unsigned integer overflow). Enables signed-integer-overflow, unsigned-integer-overflow, shift, integer-divide-by-zero, and implicit-integer-truncation.
-fsanitize=implicit-conversion: Checks for suspicious behaviours of implicit conversions. Currently, only -fsanitize=implicit-integer-truncation is implemented.
-fsanitize=nullability: Enables nullability-arg, nullability-assign, and nullability-return. While violating nullability does not have undefined behavior, it is often unintentional, so UBSan offers to catch it.
The GCC runtime is a downstream copy of the Clang/LLVM runtime, and it has a reduced number of checks, since it's behind upstream. GCC developers sync the Clang/LLVM code from time to time. The first portion of merged NetBSD support for UBSan and ASan landed in GCC 8.x (NetBSD-8.0 uses GCC 5.x, NetBSD-current as of today uses GCC 6.x). This version of GCC also contains useful compiler attributes to mark certain parts of the code and disable sanitization of certain functions or files.
I've decided to design the policy for reporting issues differently to the Linux kernel one. UBSan in the Linux kernel prints out messages in a multiline format with stacktrace:
================================================================================ UBSAN: Undefined behaviour in ../include/linux/bitops.h:110:33 shift exponent 32 is to large for 32-bit type 'unsigned int' CPU: 0 PID: 0 Comm: swapper Not tainted 4.4.0-rc1+ #26 0000000000000000 ffffffff82403cc8 ffffffff815e6cd6 0000000000000001 ffffffff82403cf8 ffffffff82403ce0 ffffffff8163a5ed 0000000000000020 ffffffff82403d78 ffffffff8163ac2b ffffffff815f0001 0000000000000002 Call Trace: [] dump_stack+0x45/0x5f [ ] ubsan_epilogue+0xd/0x40 [ ] __ubsan_handle_shift_out_of_bounds+0xeb/0x130 [ ] ? radix_tree_gang_lookup_slot+0x51/0x150 [ ] _mix_pool_bytes+0x1e6/0x480 [ ] ? dmi_walk_early+0x48/0x5c [ ] add_device_randomness+0x61/0x130 [ ] ? dmi_save_one_device+0xaa/0xaa [ ] dmi_walk_early+0x48/0x5c [ ] dmi_scan_machine+0x278/0x4b4 [ ] ? vprintk_default+0x1a/0x20 [ ] ? early_idt_handler_array+0x120/0x120 [ ] setup_arch+0x405/0xc2c [ ] ? early_idt_handler_array+0x120/0x120 [ ] start_kernel+0x83/0x49a [ ] ? early_idt_handler_array+0x120/0x120 [ ] x86_64_start_reservations+0x2a/0x2c [ ] x86_64_start_kernel+0x16b/0x17a ================================================================================
Multiline print has an issue of requiring locking that prevents interwinding multiple reports, as there might be a process of printing them out by multiple threads in the same time. There is no way to perform locking in a portable way that is functional inside libc and the kernel, across all supported CPUs and what is more important within all contexts. Certain parts of the kernel must not block or delay execution and in certain parts of the booting process (either kernel or libc) locking or atomic primitives might be unavailable.
I've decided that it is enough to print a single-line message where occured a problem and what was it, assuming that printing routines are available and functional. A typical UBSan report looks this way:
Undefined Behavior in /public/netbsd-root/destdir.amd64/usr/include/ufs/lfs/lfs_accessors.h:747:1, member access within misaligned address 0x7f7ff7934444 for type 'union FINFO' which requires 8 byte alignment
These reports are pretty much selfcontained and similar to the ones from the Clang/LLVM runtime:
test.c:4:14: runtime error: left shift of 1 by 31 places cannot be represented in type 'int'
The Clang/LLVM runtime ships with a callback API for the purpose of debuggers that can be notified by sanitizers reports.
A debugger has to define __ubsan_on_report() function and call __ubsan_get_current_report_data() to collect report's information.
As an illustration of usage, there is a testing code shipped with compiler-rt for this feature
(test/ubsan/TestCases/Misc/monitor.cpp):
// Override the definition of __ubsan_on_report from the runtime, just for
// testing purposes.
void __ubsan_on_report(void) {
const char *IssueKind, *Message, *Filename;
unsigned Line, Col;
char *Addr;
__ubsan_get_current_report_data(&IssueKind, &Message, &Filename, &Line, &Col,
&Addr);
std::cout << "Issue: " << IssueKind << "\n"
<< "Location: " << Filename << ":" << Line << ":" << Col << "\n"
<< "Message: " << Message << std::endl;
(void)Addr;
}
Unfortunately this API is not thread aware and guaranteeing so in the implementation
would require excessively complicated code shared between the kernel and libc.
The usability is still restricted to debugger (like a LLDB plugin for UBSan),
there is already an alternative plugin for such use-cases when it would matter.
I've documented the __ubsan_get_current_report_data() routine with the following comment:
/* * Unimplemented. * * The __ubsan_on_report() feature is non trivial to implement in a * shared code between the kernel and userland. It's also opening * new sets of potential problems as we are not expected to slow down * execution of certain kernel subsystems (synchronization issues, * interrupt handling etc). * * A proper solution would need probably a lock-free bounded queue built * with atomic operations with the property of miltiple consumers and * multiple producers. Maintaining and validating such code is not * worth the effort. * * A legitimate user - besides testing framework - is a debugger plugin * intercepting reports from the UBSan instrumentation. For such * scenarios it is better to run the Clang/GCC version. */
The basic reporting channel for kernel messages is the dmesg(8) buffer.
As an implementation detail I'm using variadic output routines (va_list) such as vprintf() ones.
Depending on the type of a report there are two types of calls used in the kernel:
The userland version has three reporting channels:
stdout),stderr),LOG_DEBUG | LOG_USER)
Additionally, a user can tune into the runtime whether non-fatal reports are turned into fatal messages or not.
The fatal messages stop the execution of a process and raise the abort signal (SIGABRT).
The dynamic options in uUBSan can be changed with LIBC_UBSAN environment variable. The variable accepts options specified with single characters that either enable or disable a specified option. There are the following optons supported:
The default configuration is "AeLO". The flags are parsed from left to right and supersede previous options for the same property.
There are three contexts of operation of µUBsan and there is need to use conditional compilation in few parts. I've been trying to keep to keep the differences to an absolute minimum, they are as follows:
I've implemented a global build option of the distribution MKLIBCSANITIZER. A user can build the whole userland including libc, libm, librt, libpthread with a dedicated sanitizer implemented inside libc. Right now, there is only support for the Undefined Behavior sanitizer with the µUBSan runtime.
I've documented this feature in share/mk/bsd.README with the following text:
MKLIBCSANITIZER If "yes", use the selected sanitizer inside libc to compile
userland programs and libraries as defined in
USE_LIBCSANITIZER, which defaults to "undefined".
The undefined behavior detector is currently the only supported
sanitizer in this mode. Its runtime differs from the UBSan
available in MKSANITIZER, and it is reimplemented from scratch
as micro-UBSan in the user mode (uUBSan). Its code is shared
with the kernel mode variation (kUBSan). The runtime is
stripped down from C++ features, in particular -fsanitize=vptr
is not supported and explicitly disabled. The only runtime
configuration is restricted to the LIBC_UBSAN environment
variable, that is designed to be safe for hardening.
The USE_LIBCSANITIZER value is passed to the -fsanitize=
argument to the compiler in CFLAGS and CXXFLAGS, but not in
LDFLAGS, as the runtime part is located inside libc.
Additional sanitizer arguments can be passed through
LIBCSANITIZERFLAGS.
Default: no
This means that a user can build the distribution with the following command:
./build.sh -V MKLIBCSANITIZER=yes distribution
The number of issues detected is overwhelming. The Clang/LLVM toolchain - as mentioned above - reports much more potential bugs than GCC, but with both compilers during the execution of ATF tests there are thousands or reports. Most of them are reported multiple times and the number of potential code flaws is around 100.
An example log of execution of the ATF tests with MKLIBCSANITIZER (GCC): atf-mklibcsanitizer-2018-07-25.txt. I've alsp prepared a version that is preprocessed with identical lines removed, and reduced to UBSan reports only: atf-mklibcsanitizer-2018-07-25-processed.txt. I've fixed a selection of reported issues, mostly the low-hanging fruit ones. Part of the reports, especially the misaligned pointer usage ones (for variables it means that their address has to be a multiplication of their size) usage ones might be controversial. Popular CPU architectures such as X86 are tolerant to misaligned pointer usage and most programmers are not aware of potential issues in other environments. I defer further discussion on this topic to other resources, such as the kernel misaligned data pointer policy in other kernels.
As already noted, kUBSan uses the same runtime as uBSan with a minimal conditional switches.
µUBSan can be enabled in a kernel config with the KUBSAN option.
Althought, the feature is Machine Independent, I've been testing it with the NetBSD/amd64 kernel.
The Sanitizer can be enabled in the kernel configuration with the following diff:
Index: sys/arch/amd64/conf/GENERIC =================================================================== RCS file: /cvsroot/src/sys/arch/amd64/conf/GENERIC,v retrieving revision 1.499 diff -u -r1.499 GENERIC --- sys/arch/amd64/conf/GENERIC 3 Aug 2018 04:35:20 -0000 1.499 +++ sys/arch/amd64/conf/GENERIC 7 Aug 2018 00:10:44 -0000 @@ -111,7 +111,7 @@ #options KGDB # remote debugger #options KGDB_DEVNAME="\"com\"",KGDB_DEVADDR=0x3f8,KGDB_DEVRATE=9600 makeoptions DEBUG="-g" # compile full symbol table for CTF -#options KUBSAN # Kernel Undefined Behavior Sanitizer (kUBSan) +options KUBSAN # Kernel Undefined Behavior Sanitizer (kUBSan) #options SYSCALL_STATS # per syscall counts #options SYSCALL_TIMES # per syscall times #options SYSCALL_TIMES_HASCOUNTER # use 'broken' rdtsc (soekris)
As a reminder, the command to build a kernel is as follows:
./build.sh kernel=GENERIC
A number of issues have been detected and a selection of them already fixed. Some of the fixes change undefined behavior into inplementation specific behavior, which might be treated as appeasing the sanitizer, e.g. casting a variable to an unsigned type, shifting bits and casting back to signed.
I've implemented 38 test scenarios verifying various types of Undefined Behavior that can be caught by the sanitizer. The are two sets of tests: C and C++ ones and they are located in tests/lib/libc/misc/t_ubsan.c and tests/lib/libc/misc/t_ubsanxx.cpp. Some of the issues are C and C++ specific only, others just C or C++ ones.
I've decided to achieve the following purposes of the tests:
The following tests have been implemented:
The tests have all been verified to work with the following configurations:
The NetBSD community has aquired a new clean-room Undefined Behavior sanitizer runtime µUBSan, that is already ready to use by the community of developers.
There are three modes of µUBSan:
A new set of bugs can be detected with a new development tool, ensuring better quality of the NetBSD Operating System.
It's worth to note the selection of fixes have been ported and/or pushed to other projects. Among them FreeBSD developers merged some of the patches into their soures.
The new runtime is designed to be portable and resaonably licensed (BSD-2-clause) and can be reused by other operating systems, improving the overall quality in them.
The Google Summer of Code programming period is over and I intend to finish two leftover tasks::
The NetBSD Foundation is a non-profit organization and welcomes any donations to help us continue funding projects and services to the open-source community. Please consider visiting the following URL, and chip in what you can: