Analyzing the patchiness of vendor kernels

The full title of Munakata's talk was "Digitization of kernel diversion from the upstream to minimize local code modifications." As the latter half of that title suggests, Munakata believes that measuring the number and riskiness of out-of-tree patches is only the first step; SoC vendors and board manufacturers can and should seek to reduce their kernels' divergence from mainline over time. He works for the embedded Linux device vendor Renesas and tested the measurement approach against the company's own R-Car boards, which are designed for use in automotive projects. Most of the problems that embedded developers encounter come from working with BSPs, he said, so assessing a BSP's "health" is a task all vendors would do well to consider.

Unlike those working on desktop and server Linux projects, Munakata said, embedded developers do not have a turnkey Linux distribution that they can rely on to provide hardware support for the boards or system-on-chips (SoCs) they use. Instead, they almost always rely on the board or SoC vendor's BSP and its included kernel, which they combine in-house with other components.

Vendors pick "random kernels" to ship, he said, while the board is in development. The Long-Term Support Initiative (LTSI) has helped standardize such selections to a degree, but not entirely. Because BSP kernels are generally developed by the vendor while the product is also in development, the hardware is often revised several times prior to release. Thus, the drivers and other patches are often written and tested rapidly and may include patches that are little more than "quick and dirty hacks." Those patches may work for the board in question but break for other use cases, so they will never get merged—assuming they are ever sent upstream.

For users, these BSP kernels cause two main problems: difficulty when migrating to a new kernel releases and difficulty applying security patches. Migration to a new release is sometimes required, even when it is arduous, to make use of a significant new feature or API. Vendor patches that touch the kernel outside of device drivers make this process more complicated. The security-patch issue is similar, except that a security fix backported to an older kernel release also adds a sense of urgency.

Considering these issues, Munakata said, he decided it would be useful to have a "sanity assessment" check for BSP kernels. Ideally, he said, a vendor kernel would include a human-readable "certification of contents" file (in its board's bill of materials or BOM) that captured where the kernel differs from the mainline kernel. The file would describe the purpose of each patch, the size and location of each patch in the tree, and some sort of qualitative measurement of each patch's riskiness. He proposed a simple, three-class system for categorizing riskiness: "clean" for patches that merely enable support for new hardware features or backport a relatively self-contained feature, "safe" for patches that implement minor fixes, and "dirty" for patches that either rewrite or outright break functionality from the mainline kernel.

Considering the size of contemporary kernels, he said, such an assessment has to be generated programmatically. Initially, he tried counting the matches and mismatches of SHA-256 file hashes, using the Yaminabe tool. That method provided insufficient detail, however, because trivial and major changes both trigger a hash mismatch. He also tried tracing patches by Git commit IDs, which he said was better at determining how many in-house patch sets have been applied to a kernel, but still fell far short of the goal, since it does not provide any way to measure the riskiness of a particular patch. Naturally, that approach is also limited to those vendors that manage their kernel patches in Git.

The solution he finally settled on was combining Yaminabe's simple hash-mismatch hits with a second scan using a locality-sensitive hash, a hash function that gives similar hashes for similar files and progressively diverging hashes the more that the files compared differ. The Trend Micro Locality Sensitive Hash (TLSH) is such a hash available in open-source form. The result, built in collaboration with Armijn Hemel, is Yaminabe2. It can compare two Git trees, first weeding out identical files by comparing SHA-256 hashes. For the mismatches, it computes the TLSH hashes and reports a "distance" score for each pair.

Transforming those distance scores into the "clean," "safe," and "dirty" assessments desired took a bit of investigative work. Running Yaminabe2 against various revisions of the R-Car BSP, the distance scores reported ranged from less than 10 (for trivial differences) up to nearly 400. After several rounds of testing, he settled on some cut-off points. A distance score less than 60 can be marked as "clean;" a distance between 60 and 150 can be marked as "safe," and any distance above 150 likely indicates that a patched file is "dirty." Naturally, such cut-off points can catch some false positives, and any such assessment also needs to take a file's location in the kernel source tree into account (e.g., whether it is a device driver or not). But they serve as a good starting point for further exploration.

Munakata showed sample output from his R-Car BSP tests. For the sake of speed, Yaminabe2 uses a pre-computed database of SHA-256 and TLSH hash scores for the comparison kernel (that is, the mainline) and only processes the "target" Git tree for each run. The terminal version of the comparison tool reports the total number of mismatched files, then lists each file and its distance score, followed by the total accumulated distance for the entire tree. For the R-Car second-generation board, based on the 3.10 LTSI kernel, the first BSP release tested (version 1.1.0) had a total distance of 63,616, while the last (version 1.9.6) had a total distance of 72,242. That increase reflects the growing number of bug fixes applied. Over time, he said, he hopes to track such total distance scores as aide to decreasing the R-Car BSP's divergence from mainline.

The third-generation board, which was released in December 2015, is currently working to keep pace with the current kernel, he said, because the company wants to settle on the 2017 LTSI kernel for the board's long-term support. Interestingly enough, he added, the total distance reported by Yaminabe2 is presently higher for the R-Car third generation, which he finds perplexing. But there are still many opportunities to tune Yaminabe2: it could be taught to ignore files for irrelevant architectures or features disabled by the BSP kernel configuration, for example. Perhaps one of those factors accounts for the unexpected results for the new R-Car BSP.

The biggest improvement, he said, would be for other vendors to test Yaminabe2 against their own BSPs, and for companies buying boards or SoCs to run tests against the BSPs provided by their vendors. This would be particularly useful as a way to further refine the risk-scoring system, which at present is quite simple. Munakata added that he also hopes to improve Yaminabe2's reporting features, and to simplify the setup process. At the moment, each Yaminabe2 installation requires a fair amount of customization to tune the TLSH parameters to fit the hardware available (since TLSH is quite CPU-intensive; a full scan can take 12 or more hours).

The code is currently available only as a tar archive on the Yaminabe2 eLinux wiki page, while TLSH must be retrieved from that project's GitHub page. Yaminabe2 is a Python application, and the bundle includes everything users will need to scan and compare any two arbitrary Git trees. But Munakata advised interested parties to start with the (multi-gigabyte) pre-built SHA-256 and TLSH databases also linked to from the wiki page, since scanning and hashing the mainline kernel is a multi-hour operation even on a fast machine.

There are many ways one could gauge the riskiness of vendor-supplied kernel. Munakata and Hemel's work on Yaminabe2 offers just one approach, and it certainly needs more widespread testing. But it may prove to be a good start toward solving an under-addressed problem: helping embedded users get a handle on precisely where and how their BSP kernel diverges from the mainstream.

[The author would like to thank the Linux Foundation for travel assistance to attend ELC 2016.]

Note: you can avoid this step in the future by logging into your LWN account.