Industry is presently investigating the possibility to use commodity multicore processors connected by standard network components in safety critical systems like cars. In this scenario one clearly wants to be able to argue that a passenger on the rear seat trying to hack the car's entertainment system cannot shoot down the electronic chassis control and the engine control, although large portions of the hardware are shared. Any such argument - be it informal, a paper and pencil proof, or formally verified by a CAV system - has to consider the layers of the architecture of the car's computer system; it has to show that each layer provides a simulation between two adjacent computational models in the systems architecture and that these simulated models stay intact for all configurations and input sequences of the entire system. These models turn out to be far from obvious with very subtle and nontrivial modifications compared to classical textbook computer science.

Abstract Formal verification of software systems is a challenge that is particularly important in the area of safety-critical automotive systems. Here, approaches like direct code verification are far too complicated, unless the verification is restricted to small textbook examples. Furthermore, the verification of application logic is of limited use in industrial context, unless the underlying operating system and the hardware are verified, too. This paper introduces a generic model stack, allowing the verification of all system layers as well as the concrete application models being used in the upper layers. The presented models and proofs close the gap between the correctness proof for the lower layers of car electronics developed at the Saarland University and the verification procedure for distributed applications developed at the Technische Universität München.

The mission of the Verisoft project is (i) to develop techniques, which permit the pervasive formal verification of computer systems comprising hardware, system software, communication systems, and applications, (ii) to apply these techniques in an industrial context to verify prototypical systems. One such application is an emergency call, which is automatically placed on the mobile phone net after the sensors of a car have detected that it was involved in a crash. The application runs on a system of several electronic control units (ECUs). The local application programs of the ECUs run on top of a simple real time operating system kernel like described in the OSEKTime standard. ECUs are connected via a FlexRay bus. We outline the structure of an overall correctness proof for such a parallel system from the gate to the kernel level for the communication system hardware one has to combine existing correctness proofs for components of time triggered architectures (e.g. clock synchronization) and arguments about hardware correctness into a single theorem. Results on processor, driver, and kernel correctness can to a large extent be imported from existing research in the Verisoft project. worst case execution time bounds are derived with advanced industrial tools based on abstract interpretation.

Device drivers can be tested and debugged much better with techniques from the field of formal verification than with classical methods. The total verification of drivers together with the underlying hardware, however has remained an unsolved problem. Here we outline a paper-and-pencil solution for this problem and report on the status of the formal verification. This work is part of the Verisoft project. In its subproject 2, the seamless verification of the academic system, comprising hardware, system software and applications, is attempted. We survey the techniques and tools used for program verification in Verisoft.

In the spirit of the famous CLI stack project the Verisoft project aims at the pervasive verification of entire computer systems including hardware, system software, compiler, and communicating applications, with a special focus on industrial applications. The main programming language used in the Verisoft project is C0 (a subset of C which is similar to MISRA C). This paper reports on (i) an operational small steps semantics for C0 which is formalized in Isabelle/HOL, (ii) the formal specification of a compiler from C0 to the DLX machine language in Isabelle/HOL, (iii) a paper and pencil correctness proof for this compiler and the status of the formal verification effort for this proof, and (iv) the implementation of the compiler in C0 and a formal proof in Isabelle/HOL that the implementation produces the same code as the specification.

The interlock and forwarding logic is considered the tricky part of fully-featured piplined microprocessor and especially debugging these parts delays the hardware design process considerably. It is therefore desirable to automate the design of both interlock and forwarding logic. The hardware design engineer begins with a sequential implementation without any interlock and forwarding logic. A tool then adds the forwarding and interlock logic required for pipelining. This paper describes the algorithm for such a tool and the correctness is formally verified. We use a standard DLX RISC processor as an example.

Engineering design methodology recommends designing a system as follows: Start with an unambiguous specification, partition the system into blocks, specify the functionality of each block, design each block separately, and glue the blocks together. Verifying the correctness of an implementation then reduces to a local verification procedure. We apply this methodology for designing a provably correct IEEE rounding unit that can be used for various operations, such as addition and multiplication. First, we provide a mathematical and, hopefully, unambiguous definition of the IEEE Standard which specifies the functionality. We give explicit and concise rules for gluing the rounding unit with a floating-point adder and multiplier. We then present floating-point addition and multiplication algorithms that use the rounding unit. To the best of our knowledge, our design is the first publication that deals with detecting exceptions and trapped overflow and underflow exceptions as an integral part of the rounding unit in a floating point unit. Our abstraction level avoids bit-level representations and arguments to help clarify the functionality of the algorithm.

Engineering design methodology recommends designing a system as follows: start with an unambiguous specification, partition the system into blocks, specify the functionality of each block, design each block separately, and glue the blocks together. Verifying the correctness of an implementation then reduces to a local verification procedure. We apply this methodology for designing a provably correct, modular, IEEE-compliant floating point unit. First, we provide a mathematical, and hopefully unambiguous, definition of IEEE Standard 754 (1985) which specifies the functionality. The design consists of an adder, a multiplier and a rounding unit, each of which is further partitioned. Our floating point unit design deals with the detection of exceptions and trapped overflow and underflow exceptions as an integral part of the rounding unit. Our abstraction level avoids bit-level arguments while still enabling the addressing of crucial implementation issues such as delay and cost.

We sketch the physical design of a prototype of a PRAM architecture based on Ranade’s Fluent Machine. We describe a specially developed processor chip with several instruction streams and a fast butterfly connection network. For the realization of the network we consider alternatively optoelectronic and electric transmission. We also discuss some basic software issues.

Branching programs have been studied as a fundamental model for space bounded computations and, in particular, as a model in which to try to establish nontrivial space lower bounds and time-space trade-offs. At present, there still do not exist any results for single output functions. We consider a class of severely constrained programs (those having width 2) and establish characterizations as well as lower bounds for some Boolean functions computable within this model.

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with πk-formula of size n for which every σk-formula has size exp ω(n1/(k−1)). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a σk-formula of size exp o(n1/(k−1)). Thus our hierarchy theorem is the best possible.

We show that, for multi-tape Turing machines, non-deterministic linear time is more powerful than deterministic linear time. We also discuss the prospects for extending this result to more general Turing machines.

Branching programs for the computation of Boolean functions were first studied in the Master's thesis of Masek.7 In a rather straightforward manner they generalize the concept of a decision tree to a decision graph.

We prove the following lower bounds for on line computation.

The question of what is a good way to interconnect a large number of processors is investigated The roam result is the construction of a universal parallel machine that can simulate every reasonable parallel machine with only a small loss of time and with essentially the same number of processors.

On-line simulation of real-time (k+1)-tape Turing machines by k-tape Turing machines requires time n(log n)1/(k+1).

2-dimensional 2-tape Turing machines cannot simulate 2-dimensional Turing machines with 2 heads on 1 tape in real time.

In this paper we investigate the question of what is a good way to interconnect a large number of processors. Our main result is the construction of a universal parallel machine that can simulate every reasonable parallel machine with only a small loss of time and with essentially the same number of processors.

Static, descriptional complexity (program size) [16, 9] can be used to obtain lower bounds on dynamic, computational complexity (such as running time). We describe and discuss this “information-theoretic approach” in the following section. Paul introduced it in [13], to obtain restricted lower bounds on the time complexity of sorting. We use the approach here to obtain lower time bounds for on-line simulation of one abstract storage unit by another. A major goal of our work is to promote the approach.

Logarithmically t(n)-time bounded RAMs can be simulated by t(n)/log t(n)-tape bounded Turing machines, t(n)-time bounded multidimensional multitape Turing machines can be simulated by t(n) loglog t(n)/log t(n)-tape bounded Turing machines.

Every alternating t(n) -time bounded multitape Turing machine can be simulated by an alternating t(n) -time bounded 1-tape Turing machine. Every nondeterministic t(n) -time bounded 1-tape Turing machine can be simulated by an alternating O(n+(t(n))1/2) -time bounded 1-tape Turing machine. For well-behaved functions t(n) every nondeterministic t(n) -time bounded 1-tape Turing machine can be simulated by a deterministic ((n log n)1/2 + (t(n))1/2) -tape bounded off-line Turing machine. These results improve or extend results by Chandra-Stockmeyer, Lipton-Tarjan and Paterson.

For fixed k ≥ 2 we tighten the time hierarchy for k-tape Turing machines. Also for fixed k ≥ 2 we exhibit infinite hierarchies of languages recognizable by k-tape machines with increasing amount of time on the same amount of space.

It is shown that every deterministic multitape Turing machine of time complexity t ( n ) can be simulated by a deterministic Turing machine of tape complexity t ( n )/log t ( n ). Consequently, for tape constructable t ( n ), the class of languages recognizable by multitape Turing machines of time complexity t ( n ) is strictly contained in the class of languages recognized by Turing machines of tape complexity t ( n ). In particular the context-sensitive languages cannot be recognized in linear time by deterministic multitape Turing machines.

Consider the combinational complexity $L(f)$ of Boolean functions over the basis $\Omega = \{ f|f:\{ 0,1\} ^2 \to \{ 0,1\} \} $. A new method for proving linear lower bounds of size $2n$ is presented. Combining it with methods presented in Savage [13, (1974)] and Schnorr [18, (1974)], we establish for a special sequence of functions $f_n :\{ 0,1\} ^{n + 2\log (n) + 1} \to \{ 0,1\} :2.5n \leqq L(f) \leqq 6n$. Also a trade-off result between circuit complexity and formula size is derived.

We study a one-person game played by placing pebbles, according to certain rules, on the vertices of a directed graph. In [3] it was shown that for each graph with n vertices and maximum in-degree d , there is a pebbling strategy which requires at most c(d) n/log n pebbles. Here we show that this bound is tight to within a constant factor. We also analyze a variety of pebbling algorithms, including one which achieves the 0(n/log n) bound.

Consider the combinational complexity L(f) of Boolean functions over the basis Ω = {f¦ f:{0,1}2 → {0,1}}. A new Method for proving linear lower bounds of size 2n is presented. Combining it with methods presented in [12] and [15], we establish for a special sequence of functions fn:{0,1}n → {0,1}: 2.5n ≤ L(f) &le 6n. Also a trade-off result between circuit complexity and formula size is derived.