Linux Kernel Space Verification

user warning: Got error 28 from storage engine query: SELECT t.*,v.weight AS v_weight_unused FROM term_node r INNER JOIN term_data t ON r.tid = t.tid INNER JOIN vocabulary v ON t.vid = v.vid WHERE r.vid = 249 ORDER BY v.weight, t.weight, in /opt/drupal-6.33/modules/taxonomy/taxonomy.module on line 640.

Linux kernel consists of core components implementing basic functionality of an operation system (scheduling, memory management, interprocess communication, etc.) and loadable modules that implement additional functionality (file systems, network protocols, device drivers, etc.). Loadable modules make up 70% of source code of Linux kernel, while attention paid to them is much less than attention paid to the core components. No wonder that the loadable modules are the main source of kernel crashes, hangs, and other issues.

There are two active projects of Linux Verification Center aimed to improve quality of the loadable kernel modules.

  • Linux Driver Verification - a comprehensive toolset for static source code verification of Linux device drivers.
  • KEDR Framework - an extensible framework for dynamic analysis and verification of kernel modules.

Static analysis and dynamic analysis complement each other nicely. Strengths and weaknesses of the two approaches are considered in details here.

Another ongoing project is Linux File System Verification that aims to develop a dedicated toolset for verification of Linux file system implementations. The central component of the toolset is Spruce system that provides run-time tests to check behaviour of file system drivers under various circumstances.

The most advanced verification techniques are investigated within Linux Deductive Verification project. The goal of the project is to improve open source deductive verification tools, so they can be used to prove properties of Linux kernel code. A target for the first round of the project is a custom LSM implementation that is a part of the Astra Linux Special Edition distribution.