Device driver synthesis and verification

Device driver

In computing, a device driver or software driver is a computer program allowing higher-level computer programs to interact with a hardware device....

is a program which allows the software or higher-level computer program

Computer program

A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...

s to interact with a hardware

Hardware

Hardware is a general term for equipment such as keys, locks, hinges, latches, handles, wire, chains, plumbing supplies, tools, utensils, cutlery and machine parts. Household hardware is typically sold in hardware stores....

device. These software components act as a link between the devices and the operating system

Operating system

An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...

s, communicating with each of these systems and executing commands. They provide an abstraction layer

Abstraction layer

An abstraction layer is a way of hiding the implementation details of a particular set of functionality...

for the software above and also mediate the communication between the operating system kernel and the devices below.
Usually the operating systems comes with a support for the common device drivers and usually the hardware vendors provide the device driver for their hardware devices for most platforms.
The aggressive scaling of the hardware devices and the complex software components has made the device driver development process cumbersome and complex. When the size and functionality

Function (engineering)

In engineering, a function is interpreted as a specific process, action or task that a system is able to perform .-In engineering design:In the lifecycle of engineering projects, there are usually distinguished subsequently: Requirements and Functional specification documents. The Requirements...

of the drivers started increasing the device drivers became a key role in defining the reliability

Reliability

In general, reliability is the ability of a person or system to perform and maintain its functions in routine circumstances, as well as hostile or unexpected circumstances.Reliability may refer to:...

of the system. This has developed an incentive towards automatic synthesis

Synthesis

In general, the noun synthesis refers to a combination of two or more entities that together form something new; alternately, it refers to the creating of something by artificial means...

and verification

Software verification

Software verification is a broader and more complex discipline of software engineering whose goal is to assure that software fully satisfies all the expected requirements.There are two fundamental approaches to verification:...

of device drivers. This article sheds some light into some approaches in synthesis and verification of device drivers.

Motivation for automatic driver synthesis and verification

The device drivers are the principal failing component in most systems.
The Berkeley Open Infrastructure for Network Computing

Berkeley Open Infrastructure for Network Computing

The Berkeley Open Infrastructure for Network Computing is an open source middleware system for volunteer and grid computing. It was originally developed to support the SETI@home project before it became useful as a platform for other distributed applications in areas as diverse as mathematics,...

(BOINC) project found that OS crashes are predominantly caused by poorly-written device driver code. In Windows XP

Windows XP

Windows XP is an operating system produced by Microsoft for use on personal computers, including home and business desktops, laptops and media centers. First released to computer manufacturers on August 24, 2001, it is the second most popular version of Windows, based on installed user base...

, drivers account for 85% of the reported failures. In the Linux

Linux

Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...

kernel 2.4.1 device driver code accounts for about 70% of the code size. The driver fault can crash the whole system as it is running in the kernel mode. These findings resulted in various methodologies and techniques for verification of device drivers. An alternative was to develop techniques which can synthesize device drivers robustly. Less human interaction in the development process and proper specification of the device and operating systems can lead to more reliable drivers.

The other motivation for driver synthesis, is the large number of flavors of operating systems and device combinations. Each of these have its own set of input/output control and specifications which makes support of hardware devices on each of the operating systems difficult. So the ability to use a device with an operating system requires the availability of corresponding device driver combination. Hardware vendors usually supply the drivers for Windows, Linux and Mac OS but due to the high development or porting costs and technical support

Technical support

Technical support or tech support refers to a range of services by which enterprises provide assistance to users of technology products such as mobile phones, televisions, computers, software products or other electronic or mechanical goods...

difficulties they are unable to provide drivers on all platforms. An automated synthesis technique can help the vendors in providing drivers to support any devices on any operating system.

Verification of Device Drivers

There are two challenges that limit testing the device drivers.

It is very hard to determine the exact operation or time, when there is a fault in the interaction between driver and the kernel. The system could go in to some inconsistent state and the crash is reported after a long time, blurring the real cause of the crash.
The drivers which work properly in normal circumstances can go wrong in rare and exceptional cases and the traditional testing techniques may not help in detecting the corner case behavior of the drivers.

The verification wave of device drivers, initiated by Microsoft through their SLAM project

SLAM project

The SLAM project, which was started by Microsoft Research, aimed at verifying some software safety properties using model checking techniques. It is implemented in Ocaml, and has been used to find many bugs in Windows Device Drivers...

as early as the year 2000. The motivation for the project was that 500,000 crashes reported a day was caused by one video driver and thus became cautious about the great vulnerability in using complex device drivers, More details can be found here, in the speech delivered by Bill Gates. A large number of static and runtime techniques have since been proposed for bug detection and isolation.

Static Analysis

Static analysis means analyzing the program without executing to check whether it comply with the safety critical properties specified. For example, the system software should constrain themselves to rules such as "check user permissions before writing to kernel data structures", "referencing null pointer without check", "overflowing buffer size" etc. Using the traditional testing process (dynamic execution) requires writing many testcases to exercise these paths and drive the system in to error states. This process can take a long time and effort and is not a practical solution. Another approach is manual inspection but the code size is in millions of lines of code and too complex to be analyzed by humans.

Compiler Techniques

The rules that have a straight forward mapping to source code can be checked using a compiler. Rule violations can be found by checking if the source operations does not make sense. For example, rules like "enabling an interrupt after being disabled" can be checked by looking at the order of function calls. But if the source code type system cannot specify the rules in its semantics, then the compilers cannot catch those kind of errors. Many type safe languages allow memory safety violations resulting from unsafe type casting to be detected by compiler.

Another approach is to use meta-level compilation (MC), they extend the compilers with lightweight, system specific checkers and optimizers. These extensions are to be written by system implementers in a high level language which are dynamically linked to the compilers to do strict static analysis.

Software Model Checking

Software model checking is the algorithmic analysis of programs to prove properties of their executions. This automates the reasoning about the program behavior with respect to the given correct specifications. Model checking and symbolic execution are used to verify the safety critical properties of device drivers. The input to the model checker is the program and the temporal safety properties. The output is the proof that the program is correct or violation of the specification as a counterexample in the form of a specific execution path.

The tool SDV (Static Driver Verifier) from Microsoft uses static analysis for windows device drivers. The back end analysis engine SLAM

SLAM project

used model checking and symbolic execution for compile time static verification. The rules that are to be observed by the drivers for each API are specified in a C like language SLIC (Specification Language for Interface Checking). The analysis engine finds all paths which can lead to violations of the API usage rules and are presented as source level error paths through the driver source code. Internally, it abstracts the C code in to a boolean program and a set of predicates which are rules that are to be observed on this program. Then it uses the symbolic model checking to validate the predicates on the boolean program.

The model checker BLAST (Berkeley Lazy Abstraction Software verification Tool)

BLAST model checker

The Berkeley Lazy Abstraction Software Verification Tool is a software model checking tool for C programs. The task addressed by BLAST is the need to check whether software satisfies the behavioral requirements of its associated interfaces...

is used to find memory safety and incorrect locking errors in linux kernel. It uses an abstraction algorithm called lazy abstraction to build the model from the driver C code. It has been successful in verifying temporal safety properties of C programs with up to 50K lines of code. It is also used to determine if a change in the source code affects the proof of property in the previous version and is demonstrated on a Windows device driver.

Avinux is another tool that facilitates the automatic analysis of linux device drives and is build on top of bounded model checker CBMC. There exist fault localization methods to find the bug location as these model checking tools return a long counter example trace and it is hard to find the exact faulty location.

Run Time Analysis

Dynamic program analysis is performed by running the program with sufficient test inputs to produce interesting behaviors. Safe Drive is a low overhead system for detecting and recovering from type safety violations in device drivers. With only 4% changes to the source code of linux network drivers they were able to implement SafeDrive and give better protection and recovery to linux kernel. A similar project using hardware to isolate the device drivers from the main kernel is Nook.They place device drivers in separate hardware protection domain called "nooks" and they have separate permission setting for each pages making sure that a driver does not modify pages which are not in its domain but can read all kernel data since they share the same address space.

Another similar work in this area is on automatic recovery of operating systems due to driver faults. MINIX 3 is an operating system which can isolate major faults, defects are detected and failing components are replaced on the fly.

Device driver Synthesis

An alternative to verification and isolation of faults is to deploy techniques in device driver development process to make it more robust. Given a device specification and operating system functions, one method is to synthesize device driver for that device. This helps to reduce the human introduced errors as well as the cost and time involved in developing the system software. All the synthesis methods rely on some form of specification from the hardware device manufacturers and operating system functions.

Interface Specification Languages

Hardware operating code is usually low level and is prone to errors. The code development engineer rely on the hardware documentation which typically contains imprecise or inaccurate information. There are several Interface Definition Languages (IDL) to express the hardware functionalities. The modern OSes uses these IDLs to glue components or to hide heterogeneity, like remote procedural call IDL. The same applies to hardware functionalities as well. In this section we discuss writing device drivers in domain specific languages which helps to abstract the low level coding and use specific compilers to generate the code.

Devil allows high level definition of the communication with the device. The hardware components are expressed as I/O ports and memory-mapped registers. These specifications are then converted to a set of C macros which can be called from the driver code and thus eliminates the error induced by programmer while writing low level functions. NDL is an enhancement to Devil, describing the driver in terms of its operational interface. It uses the Devil's interface definition syntax and includes set of register definitions, protocols for accessing those registers and a collection of device functions. Device functions are then translated in to a series of operations on that interface. For a device driver generation, one have to first write the driver functionalities in these interface specification languages and then use a compiler which will generate the low level driver code.

HAIL (Hardware Access Interface Language) is another domain-specific device driver specification language. The driver developer needs to write the following.

Register map description, which describes various device registers and bit fields from the device data sheet.
Address space description for accessing the bus.
Instantiation of the device in the particular system.
Invariant specification, which constraints accessing the device.

The HAIL compiler takes these inputs and translates the specification in to C code.

Hardware Software Co-design

In hardware software co-design, the designer specifies the structure and behavior of the system using finite state machines which communicate among themselves. Then a series of testing, simulation and formal verification are done on these state machines before deciding which components go in to the hardware and which of these in to the software. The hardware is usually done in field programmable gate arrays (FPGAs) or application specific integrated circuits (ASICs), whereas the software part is translated in to low-level programming language. This approach mostly applies in embedded systems which is defined as a collection of programmable parts that interact continuously with environment through sensors. Existing techniques are intended for generating simple micro-controllers and their drivers.

Standalone Driver Synthesis

In the standalone synthesis both the device and the system software are done separately. The device is modeled using any Hardware Description Language (HDL) and the software developer does not have access to the HDL specifications. The hardware developers put forth the device interface in the data sheet for the device. From the data sheet the driver developer extracts register and memory layout of the device and the behavioral model in the form of finite state machines. This is expressed in the domain specific languages described in the Interface language section. Final step involves generating the code from these specifications.

The tool termite takes three specifications to generate the driver.

Device specification : The device register, memory and interrupt services specification obtained from the device data sheet.
Device class specification : This can be obtained from the relevant device I/O protocol standard. For example for ethernet the Ethernet LAN standard describes the common behavior of these controller devices. This is usually encoded as a set of events like packet transmission, completion of auto negotiation and link status change etc.
OS specification : This describes the OS interface with the driver. More specifically the request OS can make to the driver, the order of these requests and what the OS expects the driver in return for these requests. It defines a state machine where each transition corresponds to a driver invocation by OS, the callback made by driver or a protocol specified event.

Given these specifications the termite will generate the driver implementation that translates any valid sequence of OS request in to a sequence of device commands. Due to formal specification of the interfaces, termite can generate the driver code which holds the safety and liveness properties.

Another very interesting hacking effort is done by RevNIC, which generate a driver state machine by reverse engineering an existing driver to create inter-portable and safe drivers for new platforms. To reverse engineer a driver, it wiretaps the hardware I/O operations by executing the driver using symbolic and concrete executions. The output of the wiretap is fed to a synthesizer, which reconstruct a control flow graph of the original driver from these multiple traces along with the boiler plate template for the corresponding device class. They have ported some of windows drivers for network interfaces to other linux and embedded operating systems.

Conclusion

The various verification and synthesis techniques surveyed in this article have their own advantages and disadvantages. Like the runtime fault isolations have performance overhead, where as, the static analysis does not cover all classes of errors. The complete automation of device driver synthesis is still in its early stages and has a promising future research direction. The existence of many languages for interface specification would eventually consolidate in to a single format, which is supported universally by device vendors and operating systems team. This can result in complete automated synthesis of reliable device drivers in future.

External links

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.