Automated Porting of Device Drivers - APD2

I.  Scientific and technological goals

The device drivers are the main cause of operating system (OS) crashes. Ganapathi et al. observed that for Windows, they represent half of the cause of crashes [5] ; For Linux, we recently shown similar results and found that most of the software faults are located in the driver sub-part of the kernel [14]. However, we also have found in our study that the overall quality of drivers is quickly improving in Linux. Would it not be great if such an improvement took benefit to all OSes ? Moreover, Linux has the largest number of supported devices [7]. These devices are supported by Linux until "no user can be found", while some still-working devices are unusable when migrating from a proprietary OS version to the next version of the same OS. The users are thus forced to stick with an obsolete Windows version, or buy a new version of the device for which a driver is available for the new Windows version. Would it not be great if all these devices were usable with any version of any OS ? One solution may be to have an OS-independent implementation of the device drivers, making easier the building of new versions for different OSes.

To ease and boost the development of device drivers, code generation have already been used, generally based on Domain-Specific Languages (DSL), from the HAL (Hardware Abstraction Layer) with device interface languages such as Devil [11], to a more or less complete driver with approaches like Termite [15], Laddie, NDL, RATHAXES, or Me3D [3]. Unfortunately, none of these approaches is used at a large scale. One may suspect that developing device drivers requires a broad and multiple expertise. Indeed, the developer must be used to read and understand hardware technical documentation, and know the internal kernel API for which the development is being performed. By using one of the DSL approaches, the developer further needs to learn new domain-specific languages.

Anyway, there are some interesting related work dealing with driver synthesis or code portability, and in the same spirit of our project.

The RevNIC [4] project proposes to synthesize network device drivers from binary drivers, with reverse engineering and decompilation techniques. Some boilerplate code is however provided in hand-written templates. RevNIC emphasizes the need of driver portability. In the domain of image processing, Helium [10] proposes the extraction of code in stencil kernels to the Halide DSL. The purpose of Helium is to rejuvenate old optimized code subject to "bit rot" on new hardware platform.

The Linux kernel is a versatile operating system running on systems ranging from small embedded system, to supercomputers. As it is the most deployed OS in the world, used on desktops, mainframe servers, embedded systems, Android-based smartphones and cloud servers, Linux has the largest number of device drivers. However, this database of code is only usable for the Linux kernel, albeit other OSes lack the support of devices. The main reason is that the Linux code of device drivers are tight to the inner kernel interfaces, and those interfaces are constantly evolving. Moreover to keep the code base clean and lean, there is not useless abstraction that could be used by other OSes. As a result, developers of other (open-source) OSes are forced to manually port these device drivers as a one-shot operation in operating systems such as GNU Hurd, BSD-based OSes, L4, ReactOS, or FreeRTOS. Due to the lack of hardware support, the experiments of research OSes, Barrelfish, DNA-OS, on real hardware are time-consuming, thus performed on a limited set of platforms.

In this project, we propose to leverage the synthesis approaches by extracting the high-level definition of the device drivers from an existing implementation. As this implementation is specific to a particular OS, details specific of this OS must be abstracted, while preserving the details of the behavior, particularly the device specific commands. Then, from this new abstract definition of the device driver, we must be able to generate a new driver for the same device, but targeting another OS.

The typical expected process, illustrated on Figure 1, will be to (1) specify the internal API of an OS (OS-dependent specifications); (2) identify the API calls in a selected driver in the Analysis phase; (3) Extract the high-level definition and logic of those drivers to get the OS-independent intermediate model; (4) Generate some sibling device drivers for other OSes from the high-level definition and the API specifications of the targeted OSes.

II.  Relevance and strategic nature of the project

In the Linux community, there is a sub-project focused on back-porting newly introduced drivers in the previously released kernel versions. The goal of this effort is to allow already released Linux distributions to be deployed on any (new) hardware machine. The goal of our project is to extend this benefit to other operating systems in lack of device drivers. The back-porting effort of device drivers was historically manually managed. Nowadays, Coccinelle is used to easy and speed up the back-porting of bug fixes and newly released drivers. However, some parts still need to be manually adapted. Similarly, Coccinelle could help us in this project for software code comprehension and code transformation, but it lacks Linux internal API semantics to truly abstract the driver code to an OS-independent version, or adapt the code to another OS.

Linux has the most important set of supported devices. However, this knowledge base is of limited interest for the other OSes. Indeed, each of them needs to re-implement the drivers for its own internal API. This overwhelming task limits in practice the use of other OSes on a small set of hardware platforms. This effect is particularly true for experimental OSes for which the engineering effort needed could not be ensured. Multiple generative approaches have been proposed, but lack of mainstream adoption. Among the reason, there is the need to learn one or some new languages. Moreover, an approach like Me3D still requires some substantial manual interventions. One of the goal of this project is to improve the generative approach by automating further the generation of device drivers thanks to the understanding of a particular implementation and the OS-independent representation.

The RevNIC approach is bound to a binary version, a single flavour of the device can be considered. In this project, by relying on the source code, we will explore more features and functioning modes of the devices. Indeed, a binary version reflects only a single configuration of the code. Moreover, RevNIC relies on the activity traces of the running device driver. The coverage is thus limited to the code executed, which in practice quickly max out between 60% and 80% of the code according the device driver. In contrast, by relying on the source code, we will have instantly a coverage of 100%.

The long term perspective is to have an OS-independent specification with sufficient details to be able to target several OSes, multiple operational modes, or a user-provided context. Achieving this goal will provide a competitive advantage to hardware manufacturers. Indeed, instead of having development teams providing demonstrative code, or drivers for multiples OSes, a single software development team will be needed to make the software part of demonstrator. The hardware manufacturer will reduce its time-to-market while keeping or enlarging its client base thanks to a broader supported set of OSes. This long term perspective has a corollary challenge. While, technical documentation presents a particular device with generality, presenting multiple operational modes, a particular implementation often proposes a limited set of operational modes, if not only one ! For instance, a driver may operate a device by polling or with hardware interruptions. These modes are often implemented in exclusion with the other one. The challenge will thus be to either untangle the code to identify the different modes, or to merge the OS-independent representation generated from multiple implementations providing support for different modes. None of these solutions is straightforward. In the first case, the code can be for instance selected by preprocessor macros, or operate on exclusion on behalf of the dynamic configuration. In the second case, the algorithm used to drive the device may be different in each OS, merging them impractical to impossible.

Extracting the specification for the same driver, but from multiple OSes, offers another long-term research perspective. It will allow to identify software faults by comparing the different version extracted from each OS. By identifying the software faults, developers could fix them, thus leading to more robust and dependable OSes.

III.  Internships

In the context of this exploratory project, we request two internships. The first one will be dedicated to the extraction of the device driver model, while the second one will be focused on the generation.

Internship 1

The goal of the first internship is to study and evaluate approaches that allow to extract the underlying automaton hand-coded in C by the device driver developer in the Linux kernel code, and then to retrieve the semantics of the actions and transitions of the automaton.

To extract the automaton, the intern has to go through the related work and evaluate the most appropriate approaches and tools. The intern will study for instance Helium [10], RevNIC [4], or some other approaches such as Argos [1].

The resulting automaton must be annotated to identify the several parts that compose it. In particular, we expect to mark operations and events that belong to the device-class of the driver being proceed, operations related to the operational mode of the device (i.e. polling or interrupt), operations related to the platform (e.g. when MMU or DMA is involved in the use of the device), and operations related to non-functional features, such as power management. We think that Coccinelle may help to identify the annotations type, and to locate the right annotation places.

The annotated automaton will have to be represented by a domain-specific language directly readable and writable by a developer. It will indeed represent the OS-independent version of the device driver that will be used for the generation part.

Towards a PhD subject: The goals of this project go beyond the ones of this first internship. We will for instance leave for a PhD thesis the ability to extract the automaton from multiple OSes, and to handle multiple operating modes of a device driver. Moreover, designing and formalizing a domain-specific language need some time to mature. Even if a master project allows to define the cornerstones and the coarse abstractions for the DSL we need, a PhD will be more appropriate to handle all the remaining subtle problems faced. Pursuing with a PhD project, this is a better guarantee to mature this project and to finally define a domain-specific language that scales. A success criterion of this language and its tool-chain will be its adoption by the device driver developers.

Internship 2

The goal of the second internship is to study the generation of a device driver from the abstract specification previously extracted. We will first target Linux to ensure we have an idempotent process, then target an embedded OS (e.g. DNA-OS) before generalizing the approach to other OSes.

To validate the overall approach, we will compare the hand-written device driver version with the generated one. The comparison will be performed first on micro-benchmark testing atomic features, then on benchmark based on normal device usage. Among the available device drivers, the intern can select drivers for SPI, I2C, or UART devices, then investigates more complex drivers for devices like Ethernet cards, or hard drives.

The RevNIC [4] project also considers the portability of the extracted code. The RevNIC approach should be studied during the bibliography. Nevertheless, RevNIC is based on execution traces, with a limited code coverage, and we can thus expect a better ratio of generated code in the targeted platforms.

Towards a PhD subject: The mid-term goals of the project go beyond this internship. The project will be continued by studying the applicability of the approach to scale to multiple and different OSes, like BSD-based OSes, MS Windows, or FreeRTOS. Achieving this demonstration, with a PhD project, will validate our work on OSes with different purposes (e.g. desktop versus embedded system), and different driver models.

IV.  Positioning

The APD² project belongs to the "Pervasive Computing Systems" (PCS) research action of the Persyval laboratory. It could fit with two dimensions addressed by PCS: Autonomous Embedded Systems and Robust and Dependable Embedded Systems. Indeed, we expect by an automated porting of device drivers to reach a higher quality of the driver code, thus being more robust and dependable, in the context of autonomous embedded systems, not necessarily relying on Linux.

V.  Partnership in the Persyval Labex

V.1.  LIG Lab

Nicolas Palix is a junior lecturer at the University of Grenoble-Alps, doing his research in the ERODS research group of the LIG. During his PhD, he has studied the development of communication services for IP telephony and ubiquitous systems. The approach was based on domain-specific languages. After his Phd, he worked as a post-doctorate at the University of Copenhagen, where he studied the Linux kernel code [8, 9, 12], mostly for studying faults [13].

V.2.  TIMA Lab

Frédéric Rousseau has been professor at University of Grenoble-Alps since 2007 and researcher in the TIMA-SLS team. Since this time, he has had a reasearch activity about low level software development, validation and generation, mainly in the context of FP6 and FP7 European projects [2]. He was also co-advisor of a Ph.D. student about the partial automatic generation of device drivers [3] with an application on the TIMA Operating System called DNA-OS [6].

VI.  References

[1] Nicolas Berthier, Florence Maraninchi, and Laurent Mounier. Synchronous programming of device drivers for global resource control in embedded operating systems. ACM Transactions on Embedded Computing Systems (TECS), 12(1s):39, 2013.

[2] Alexandre Chagoya-Garzon, Frédéric Rousseau, and Frédéric Pétrot. Multi-device driver synthesis flow for heterogeneous hi- erarchical systems. In DSD 2012, Cesme, Izmir, Turkey, Septem- ber 5-8, 2012, pages 389–396. IEEE Computer Society, 2012.

[3] Hui Chen, Guillaume Godet-Bar, Frédéric Rousseau, and Frédéric Pétrot. Device driver generation targeting multiple op- erating systems using a model-driven methodology. In RSP 2014, New Delhi, India, October 16-17, 2014, pages 30–36. IEEE, 2014.

[4] Vitaly Chipounov and George Candea. Reverse engineering of binary device drivers with revnic. In Proceedings of the 5th Eu- ropean conference on Computer systems, pages 167–180. ACM, 2010.

[5] Archana Ganapathi, Viji Ganapathi, and David A Patterson. Windows XP kernel crash analysis. In Proceedings of LISA ’06: 20th Large Installation System Administration Conference, vol- ume 6, pages 49–159. USENIX Association, December 2006.

[6] Xavier Guerin and Frédéric Pétrot. A system framework for the design of embedded software targeting heterogeneous multi- core socs. In ASAP 2009, July 7-9, 2009, Boston, MA, USA, pages 153–160. IEEE, 2009.

[7] Dan Kohn. The Linux driver model: A better way to support devices, June 2008.

[8] Julia L. Lawall, Julien Brunel, Nicolas Palix, René Rydhof Hansen, Henrik Stuart, and Gilles Muller. WYSIWIB: A declar- ative approach to finding API protocols and bugs in linux code. In Proceedings of the 2009 IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2009, Estoril, Lis- bon, Portugal, June 29 - July 2, 2009, pages 43–52. IEEE, 2009.

[9] Julia L. Lawall, Julien Brunel, Nicolas Palix, René Rydhof Hansen, Henrik Stuart, and Gilles Muller. WYSIWIB: ex- ploiting fine-grained program structure in a scriptable api-usage protocol-finding process. Softw., Pract. Exper., 43(1):67–92, 2013.

[10] Charith Mendis and al.. Helium: lifting high-performance stencil kernels from stripped x86 binaries to halide DSL code. In David Grove and Steve Blackburn, editors, ACM SIGPLAN Conference on Programming Language Design and Implemen- tation, Portland, OR, USA, June 15-17, 2015, pages 391–402. ACM, 2015.

[11] Fabrice Mérillon, Laurent Réveillère, Charles Consel, Renaud Marlet, and Gilles Muller. Devil: An IDL for hardware pro- gramming. In 4th Symposium on Operating System Design and Implementation (OSDI 2000), San Diego, California, USA, Oc- tober 23-25, 2000, pages 17–30. USENIX Association, 2000.

[12] Nicolas Palix, Julia L. Lawall, and Gilles Muller. Tracking code patterns over multiple software versions with herodotos. In Jean-Marc Jézéquel and Mario Südholt, editors, Proceed- ings of the 9th International Conference on Aspect-Oriented Software Development, AOSD 2010, Rennes and Saint-Malo, France, March 15-19, 2010, pages 169–180. ACM, 2010.

[13] Nicolas Palix, Gaël Thomas, Suman Saha, Christophe Calvès, Julia L. Lawall, and Gilles Muller. Faults in linux: ten years later. In ASPLOS 2011, Newport Beach, CA, USA, March 5-11, 2011, pages 305–318. ACM, 2011.

[14] Nicolas Palix, Gae ̄l Thomas, Suman Saha, Christophe Calves, Gilles Muller, and Julia Lawall. Faults in linux 2.6. ACM Trans- actions on Computer Systems (TOCS), 32(2):4, June 2014.

[15] Leonid Ryzhyk, Peter Chubb, Ihor Kuz, Etienne Le Sueur, and Gernot Heiser. Automatic device driver synthesis with termite. In ACM Symposium on Operating Systems Principles, SOSP ’09, pages 73–86, New York, NY, USA, 2009. ACM.