Catálogo de publicaciones - libros

Wilhelm’s career in Computer Science spans more than a third of a century. During this time, he has made numerous research contributions in the areas of programming languages, compilers and compiler generators, static program analysis, program transformation, algorithm animation, and real-time systems; co-founded a company to transfer some of these ideas to industry; held the Chair for Programming Languages and Compiler Construction at Saarland University; and served since its inception as the Scientific Director of the International Conference and Research Center for Computer Science at Schloß Dagstuhl.

The worst-case execution time analyzer aiT originally developed by Saarland University and AbsInt GmbH computes safe and precise upper bounds for the WCETs of tasks. It relies on a pipeline model that usually has been handcrafted. We present some new approaches aiming at automatically obtaining a pipeline model as required by aiT from a formal processor description in VHDL or Verilog. The derivation of the total WCET from the basic-block WCETs requires knowledge about upper bounds on the number of loop iterations. We present a new method for loop bound detection using dataflow analysis to derive loop invariants. A task may contain infeasible paths caused by conditionals with logically related conditions. We present a static analysis that identifies and collects conditions from the executable, and relates these collections to detect infeasible paths. This new analysis uses the results of a novel generic slicer on the level of binary code.

We describe a gate level design of a FlexRay-like bus interface. An electronic control unit (ECU) is obtained by integrating this interface into the design of the verified VAMP processor. We get a time triggered distributed real-time system by connecting several such ECU’s via a common bus. We define a programming model for such a system at the instruction set architecture (ISA) level and prove that it is correctly implemented at the gate level. The proof combines theories of processor correctness, communication systems, program correctness and realistic worst-case execution time (WCET) analysis into a single unified mathematical theory.

Lazy evaluation, the technique to build special data structures allowing to perform an evaluation at a later time, has many uses in functional programming languagues [1,2,3]. This article shows a use in imperative (object oriented) languages: the lazy execution of boolean queries. Applying lazy index lookup can result in drastic gains in search speed and reduce the amount of required main memory.

We consider secrecy problems for cryptographic protocols modeled using Horn clauses and present general classes of Horn clauses which can be efficiently decided. Besides simplifying the methods for the class of flat and one-variable clauses introduced for modeling of protocols with single blind copying [7,25], we also generalize this class by considering -variable clauses instead of one-variable clauses with suitable restrictions similar to those for the class . This class allows to conveniently model protocols with joint blind copying. We show that for a fixed , our new class can be decided in DEXPTIME, as in the case of one variable.

Modular analyses of object-oriented programs need clear encapsulation boundaries between program components. The reference semantics of object-oriented languages complicates encapsulation. Ownership type systems are a way to guarantee encapsulation. However, they introduce a substantial and nontrivial annotation overhead for the programmer. This is in particular true for type systems with an access policy that is more flexible than owners-as-dominators. As we want to use ownership disciplines as basis for modular analyses, we need the flexibility. However, to keep it practical, the annotation overhead should be kept minimal.

In this paper, we present such a flexible ownership type system together with an inference technique to reduce the annotation overhead. Runtime components in our approach can be accessed via the interface of the owner as well as via other boundary objects with explicitly declared interface types. The resulting type system is quite complex, however, the programmer only has to annotate the interface types of a component. The ownership type information for the classes implementing the components is automatically inferred by a constraint-based algorithm. We proved the soundness of our approach for a Java-like core language.

Designing optimizing compilers is a challenging task that involves numerous mutually interdependent transformations. Often, these interdependencies are only captured in an ad-hoc manner, relying on the ingenuity and experience of the compiler engineers. ViDoC is a tool-kit for the specification-driven, interactive development of program optimizers in a service oriented way. In particular, ViDoC facilitates the specification of dependencies between transformations in terms of modal logic properties and requirements. These specifications can be used for checking, as well as synthesizing, suitable optimization sequences , which are expressed in terms of a workflow (graph) model. ViDoC also offers various kinds of visual support, like the display of flow graphs, call graphs and analysis information, and the visualization and even manipulation of the graphs expressing the optimization workflows. These features make ViDoC especially appropriate for rapid prototyping. ViDoC is constructed on top of the Soot infrastructure project, that targets the manipulation of Java byte code and offers powerful engines for realizing the specified analyzes and transformations. The visualization and workflow handling are designed according to the paradigm of Lightweight Process Coordination, realized in the jABC environment.

We review Wilhelm’s work on WCET for hard real-time applications and also recent work on analysis of soft-real time systems using probabilistic methods. We then present Probabilistic Abstract Interpretation (PAI) as a quantitative variation of the classical approach; PAI aims to provide close approximations – this should be contrasted to the safe approximations studied in the standard setting. We discuss the relation between PAI and classical Abstract Interpretation as well as average case analysis.

We study abstract interpretations of a fixpoint protoderivation semantics defining the maximal derivations of a transitional semantics of context-free grammars akin to pushdown automata. The result is a hierarchy of bottom-up or top-down semantics refining the classical equational and derivational language semantics and including Knuth grammar problem, classical grammar flow analysis algorithms, and parsing algorithms.

We propose results ensuring properties of a component-based system from properties of its interaction model and of its components. We consider here deadlock-freedom and local progress of subsystems. This is done in the framework of interaction systems, a model for component based modelling described in [9]. An interaction system is the superposition of two models: a behavior model and an interaction model. The behavior model describes the behavior of individual components. The interaction model describes the way the components may interact by introducing connectors that relate actions from different components. We illustrate our concepts and results with examples.