Networked cybernetic and physical systems of the Internet of Things (IoT) immerse civilian and industrial infrastructures into an interconnected and dynamic web of hybrid and mobile devices. The key feature of such systems is the hybrid and tight coupling of mobile and pervasive discrete communications in a continuously evolving environment (discrete computations with predominant continuous dynamics). In the aim of ensuring the correctness and reliability of such heterogeneous infrastructures, we introduce the hybrid π -calculus ( H p C ), to formally capture both mobility, pervasiveness and hybridisation in infrastructures where the network topology and its communicating entities evolve continuously in the physical world. The π -calculus proposed by Robin Milner et al. is a process calculus that can model mobile communications and computations in a very elegant manner. The H p C we propose is a conservative extension of the classical π -calculus, i.e., the extension is “minimal”, and yet describes mobility, time and physics of systems, while allowing to lift all theoretical results (e.g. bisimulation) to the context of that extension. We showcase the H p C by considering a realistic handover protocol among mobile devices.

The major drawback of using static schedules to execute dataflow applications is their high inflexibility. In real-time systems, periodic schedules make it easier to assert safety guarantees and to decrease the schedule size, but their characteristics remain hard to compute. This article presents an approach to automatically generate fixed priority schedules from a dataflow specification. To do so, precedence dependencies between actors in the dataflow graphs are abstracted, as well as the task periods, by using affine relations . This abstraction allows us to synthesize schedules efficiently considering two main objectives: the maximization of throughput and the minimization of buffer sizes. Given a dataflow graph to execute in a real-time environment, we transform it into an Affine Dataflow Graph (ADFG) and compute the task priorities, their mapping, the number of delays in the buffers, and the buffer sizes. This article is the first to present an overview of both theoretical and practical aspects of ADFG. On the theoretical side, it presents corrections and improvements on the fixed priority case. On the practical side, benchmark evaluations demonstrate the robustness and maturity of the approach that our scheduling synthesizer implements. Synthesized schedules are evaluated by using scheduling simulation and real-time implementation. Last but not least, the synthesized periods reach the optimal throughput if enough processors are available, and most of the time the periods reach the maximal processor utilization factor in the uni-processor case. Moreover, execution time of the synthesis is about only 1 second for the main proposed algorithms.

Abstract Modern operating systems have adopted Berkeley Packet Filters (BPF) as a mechanism to extend kernel functionalities dynamically, e.g., Linux’s eBPF or RIOT’s rBPF. The just-in-time (JIT) compilation of eBPF introduced in Linux eBPF for performance has however led to numerous critical issues. Instead, RIOT’s rBPF uses a slower but memory-isolating interpreter (a virtual machine) which implements a defensive semantics of BPF; and therefore trades performance for security. To increase performance without sacrificing security, this paper presents a fully verified JIT implementation for RIOT’s rBPF, consisting of: i/ an end-to-end refinement workflow to both proving the JIT correct from an abstract specification and by deriving a verified concrete C implementation; ii/ a symbolic CompCert interpreter for executing binary code; iii/ a verified JIT compiler for rBPF; iv/ a verified hybrid rBPF virtual machine. Our core contribution is, to the best of our knowledge, the first and fully verified rBPF JIT compiler with correctness guarantees from high-level specification to low-level implementation. Benchmarks on microcontrollers hosting the RIOT operating system demonstrate significant performance improvements over the existing implementations of rBPF, even in worst-case application scenarios.

Model-based design has become the predominant approach to the design of hybrid and cyber-physical systems (CPSs). It advocates the use of mathematically founded models to capture heterogeneous digital and analog behaviours from domain-specific formalisms, allowing all engineering tasks of verification, code synthesis, and validation to be performed within a single semantic body. Guaranteeing the consistency among the different views and heterogeneous models of a system at different levels of abstraction, however, poses significant challenges. To address these issues, Hoare and He’s Unifying Theories of Programming (UTP) proposes a calculus to capture domain-specific programming and modelling paradigms into a unified semantic framework. Our goal is to extend UTP to form a semantic foundation for CPS design. Higher-order UTP (HUTP) is a conservative extension to Hoare and He’s theory that supports the specification of discrete, real-time, and continuous dynamics, concurrency and communication, and higher-order quantification. Within HUTP, we define a calculus of normal hybrid designs to model, analyse, compose, refine, and verify heterogeneous hybrid system models. In addition, we define respective formal semantics for Hybrid Communicating Sequential Processes and Simulink using HUTP.

Abstract RIOT is a micro-kernel dedicated to IoT applications that adopts eBPF (extended Berkeley Packet Filters) to implement so-called femto-containers. As micro-controllers rarely feature hardware memory protection, the isolation of eBPF virtual machines (VM) is critical to ensure system integrity against potentially malicious programs. This paper shows how to directly derive, within the Coq proof assistant, the verified C implementation of an eBPF virtual machine from a Gallina specification. Leveraging the formal semantics of the CompCert C compiler, we obtain an end-to-end theorem stating that the C code of our VM inherits the safety and security properties of the Gallina specification. Our refinement methodology ensures that the isolation property of the specification holds in the verified C implementation. Preliminary experiments demonstrate satisfying performance.

Low-power operating system runtimes used on IoT microcontrollers typically provide rudimentary APIs, basic connectivity and, sometimes, a (secure) firmware update mechanism. In contrast, on less constrained hardware, networked software has entered the age of serverless, microservices and agility. With a view to bridge this gap, in the paper we design Femto-Containers, a new middleware runtime which can be embedded on heterogeneous low-power IoT devices. Femto-Containers enable the secure deployment, execution and isolation of small virtual software functions on low-power IoT devices, over the network. We implement Femto-Containers, and provide integration in RIOT, a popular open source IoT operating system. We then evaluate the performance of our implementation, which was formally verified for fault-isolation, guaranteeing that RIOT is shielded from logic loaded and executed in a Femto-Container. Our experiments on various popular micro-controller architectures (Arm Cortex-M, ESP32 and RISC-V) show that Femto-Containers offer an attractive trade-off in terms of memory footprint overhead, energy consumption, and security.

Smart contracts are the artifact of the blockchain that provides immutable and verifiable specifications of physical transactions. Solidity is a domain-specific programming language with the purpose of defining smart contracts. It aims at reducing the transaction costs occasioned by the execution of contracts on the distributed ledgers such as Ethereum. However, Solidity contracts need to adhere to safety and security requirements that require formal verification and certification. This paper proposes a method to meet such requirements by translating Solidity contracts to Event-B models, supporting certification. To that purpose, we define a restrained Solidity subset and a transfer function that translates Solidity contracts to Event-B models. Besides, we have implemented a translator to improve the conversion efficiency. As a case study, we take advantage of Event-B method capabilities to simulate models at different levels of abstraction and to express the properties of a typical smart contract: Honeypot contract. Lastly, we verify the generated proof obligations of the Event-B model with the help of the Rodin platform.

The fault of one device on a grid may incur severe economical or physical damages. Among the many critical components in such IoT devices, the operating system's bootloader comes first to initiate the trusted function of the device on the network. However, a bootloader uses hardware-dependent features that make its functional correctness proof difficult. This paper uses verified programming to automate the verification of both the C libraries and assembly boot-sequence of such a, real-world, bootloader in an operating system for ARM-based IoT devices: RIoT. We first define the ARM ISA specification, semantics and properties in F* to model its critical assembly code boot sequence. We then use Low*, a DSL rendering a C-like memory model in F*, to implement the complete bootloader library and verify its functional correctness and memory safety. Other than fixing potential faults and vulnerabilities in the source C and ASM bootloader, our evaluation provides an optimized and formally documented code structure, a reasonable specification/implementation ratio, a high degree of proof automation and an equally efficient generated code.

We propose a type-driven approach to building verified safe and correct IoT applications. Today's IoT applications are plagued with bugs that can cause physical damage. This is largely because developers account for physical constraints using ad-hoc techniques. Accounting for such constrains in a more principled fashion demands reasoning about the composition of all the software and hardware components of the application. Our proposed framework takes a step in this direction by (1) using refinement types to make make physical constraints explicit and (2) imposing an event-driven programing discipline to simplify the reasoning of system-wide properties to that of an event queue. In taking this approach, our framework makes it possible for developers to build verified IoT application by making it a type error for code to violate physical constraints.

Novel memory architectures have been introduced in multi/many-core processors to address the performance bottle neck due to shared memory accesses. Taking the advantages brought by these architectures in scheduling analysis is still an open challenge. In this article, we present a scheduling analysis technique that exploits a shared multi-bank memory architecture to efficiently schedule parallel real-time applications modeled as synchronous data flow (SDF) graphs by minimizing the memory access contentions. Our approach aims at producing a static time-triggered schedule with the objective of minimizing the makespan and buffer size requirements while respecting consistency and data dependency constraints. An Integer Linear Programming formulation of the scheduling problem is presented, as well as a heuristic with significantly lower time complexity. Experimental results are given using synthetic SDF graphs generated by the SDF3 tool and applications available in the StreamIt benchmark.

No abstract available.

Transformation of synchronous data flow graphs (SDF) into equivalent homogeneous SDF representations has been extensively applied as a pre-processing stage when mapping signal processing algorithms onto parallel platforms. While this transformation helps fully expose task and data parallelism, it also presents several limitations such as an exponential increase in the number of actors and excessive communication overhead. Partial expansion graphs were introduced to address these limitations for multi-core platforms. However, existing solutions are not well-suited to achieve efficient scheduling on many-core architectures. In this article, we develop a new approach that employs cyclo-static data flow techniques to provide a simple but efficient method of coordinating the data production and consumption in the expanded graphs. We demonstrate the advantage of our approach through experiments on real application models.

No abstract available.

Model-Based Engineering (MBE) is a promising approach to cope with the challenges of designing the next-generation automotive systems. The increasing complexity of automotive electronics, the platform, distributed real-time embedded software, and the need for continuous evolution from one generation to the next has necessitated highly productive design approaches. However, heterogeneity, interoperability, and the lack of formal semantic underpinning in modeling, integration, validation and optimization make design automation a big challenge, which becomes a hindrance to the wider application of MBE in the industry. This paper briefly presents the interoperability challenges in the context of MBE and summarizes our current contribution to address these challenges with regard to automotive control software systems. A novel model-based formal integration framework is being developed to enable architecture modeling, timing specification, formal semantics, design by contract and optimization in the system-level design. The main advantages of the proposed approach include its pervasive use of formal methods, architecture analysis and design language (AADL) and associated tools, a novel timing annex for AADL with an expressive timing relationship language, a formal contract language to express component-level requirements and validation of component integration, and the resulting high assurance system delivery.

The concept of liquid clocks introduced in this paper is a significant step towards a more precise compile-time framework for the analysis of synchronous and polychromous languages. Compiling languages such as Lustre or Signal indeed involves a number of static analyses of programs before they can be synthesized into executable code, e.g., synchronicity class characterization, clock assignment, static scheduling or causality analysis. These analyses are often equivalent to undecidable problems, necessitating abstracting such programs to provide sound yet incomplete analyses. Such abstractions unfortunately often lead to the rejection of programs that could very well be synthesized into deterministic code, provided abstraction refinement steps could be applied for more accurate analysis. To reduce the number of false negatives occurring during the compilation process, we leverage recent advances in type theory - with the definition of decidable classes of value-dependent type systems - and formal verification, linked to the development of efficient SAT/SMT solvers, to provide a type-theoretic approach that considers all the above analyses as type inference problems. To simplify the exposition of our new approach in this paper, we define a refinement type system for a minimalistic, synchronous, stream-processing language to concisely represent, analyze, and verify logical and quantitative properties of programs expressed as stream-processing data-flow networks. Our type system provides a new framework for representing logical time (clocks) and scheduling properties, and to describe their relations with stream values and, possibly, other quantas. We show how to analyze synchronous stream processing programs (à la Lustre, Signal) to enable previously described analyses involved in compiling such programs. We also prove the soundness of our type system and elaborate on the adaptability of this core framework by outlining its extensibility to specific models of computations and other quantas.

This presentation demonstrates a scalable, modular, refinable methodology for translation validation applied to a mature (20 years old), large (500k lines of C), open source (Eclipse/Polarsys IWG project POP) code generation suite, all by using off-the-shelf, open-source, SAT/SMT verification tools (Yices), by adapting and optimizing the translation validation principle introduced by Pnueli et al. in 1998. This methodology results from the ANR project VERISYNC, in which we aimed at revisiting Pnueli's seminal work on translation validation using off-the-shelf, up-to-date, verification technology. In face of the enormous task at hand, the verification of a compiler infrastructure comprising around 500 000 lines of C code, we devised to narrow down and isolate the problem to the very data-structures manipulated by the infrastructure at the successive steps of code generation, in order to both optimize the whole verification process and make the implementation of a working prototype at all doable. Our presentation outlines the successive steps of this endeavour, from clock synthesis, static scheduling to target code production.

This paper investigates the way state diagrams can be best represented in the polychronous model of computation. In this relational model, the basic objects are signals, which are related through data-flow equations. Signals are associated with logical clocks, which provide the capability to describe systems in which componentsobey to multiple clock rates. We propose a model of finite-state automata, called polychronous automata, which is based on clock relations. A specificity of this model is that an automaton is submitted to clock constraints. This allows one to specify a wide range of control-related configurations, either reactive, or restrictivewith respect to their control environment. A semantic model is defined for these polychronous automata, that relies on a Boolean algebra of clocks.

High-level architecture modeling languages, such as Architecture Analysis & Design Language (AADL), are gradually adopted in the design of embedded systems so that design choice verification, architecture exploration, and system property checking are carried out as early as possible. This paper presents our recent contributions to cope with clock-based timing analysis and validation of software architectures specified in AADL. In order to avoid semantics ambiguities of AADL, we mainly consider the AADL features related to real-time and logical time properties. We endue them with a semantics in the polychronous model of computation; this semantics is quickly reviewed. The semantics enables timing analysis, formal verification and simulation. In addition, thread-level scheduling, based on affine clock relations is also briefly presented here. A tutorial avionic case study, provided by C-S, has been adopted to illustrate our overall contribution.

Symbolic schedulability analysis of dataflow graphs is the process of synthesizing the timing parameters (i.e. periods, phases, and deadlines) of actors so that the task system is schedulable and achieves a high throughput when using a specific scheduling policy. Furthermore, the resulted schedule must ensure that communication buffers are underflow- and overflow-free. This paper describes a (partitioned) earliest-deadline first symbolic schedulability analysis of dataflow graphs that minimizes the buffering requirements.

This paper presents an embedding of polychronous programs into synchronous ones. Due to this embedding, it is not only possible to deepen the understanding of these different models of computation, but, more importantly, it is possible to transfer compilation techniques that were developed for synchronous programs to polychronous programs. This transfer is nontrivial because the underlying paradigms differ more than their names suggest: Since synchronous systems react deterministically to given inputs in discrete steps, they are typically used to describe reactive systems with a totally ordered notion of time. In contrast, polychronous system models entail a partially ordered notion of time, and are most suited to interface a system with an asynchronous environment by specifying input/output constraints from which a deterministic controller may eventually be refined and synthesized. As particular examples for the mentioned cross fertilization, we show how a simulator and a verification backend for synchronous programs can be made available to polychronous specifications, which is a first step toward integrating heterogeneous models of computation.

The analysis and verification of an AADL model usually requires its transformation into the meta-model of this model-checker or that schedulability analysis tool. However, one challenging problem is to prove that the transformation into the target model of computation (MoC) preserves the semantics of the original AADL model or at least some of its properties. Moreover, the AADL standard lacks a formal semantics to make the validation of this translation possible. Albeit some of the related works give informal explanations on the model transformations they apply to interpret or compile AADL, the formal proof of semantics preservation remains in most cases altogether impossible. Our contribution is to bridge this gap by providing two formal semantics for a synchronous subset of AADL, which includes periodic threads and data port communications. Its operational semantics is formalized as a TTS (Timed Transition System). This formalization is one prerequisite to the formal proof of semantics preservation for our model transformation from AADL sources to our target verification formalism: TASM (Timed Abstract State Machine). In this paper, an abstract syntax of (our subset of) AADL is given, together with the abstract syntax of TASM. The translation is formalized by a family of semantics functions, which associates each AADL construct to a TASM fragment. Then, the proof of simulation equivalence between the TTSs of the AADL and the TASM models is formalized and mechanized using the proof assistant Coq.

The UML Profile for Modeling and Analysis of Real-Time and Embedded systems (MARTE) defines a mathematically expressive model of time, the Clock Constraint Specification Language (CCSL), to specify timed annotations on UML diagrams and thus provides them with formally defined timed interpretations. Thanks to its expressive capability, the CCSL allows for the specification of static and dynamic properties, of deterministic and non-deterministic behaviors, or of systems with multiple clock domains. Code generation from such multi-clocked specifications (for the purpose of synthesizing a simulator, for instance) is known to be a difficult issue. We address it by using the approach of controller synthesis. In our framework, a timed CCSL specification is regarded as a property whose satisfaction should be enforced for any UML diagram carrying it as annotation. To do so, CCSL statements are first translated into dynamical polynomial systems. Such systems can be manipulated using the model-checker Sigali to synthesize an executable property (a controller) which enforces the satisfaction of the specified timing constraints on the UML diagram with which it is executed.

We propose a general method to characterize and synthesize correctness-preserving asynchronous wrappers for synchronous processes on a globally asynchronous locally synchronous (GALS) architecture. While a synchronous process may rely on the absence

THE idea of this special section dawned on us during various discussions on the recent trends in computer system design throughout the 2008-2009 academic year when one of the editors spent a sabbatical year at INRIA hosted by the other editor. Cyber Physical System (CPS) was the most recent buzz word replacing the ‘hybrid systems’, and the ‘Science of Design’ (SoD) was the other buzz word on its way out to the perished land of unfashionable terminologies. In the realm of cyber physical systems there had been a lot of foundational developments under the guise of hybrid systems since the mid-nineties. The science of design, another terminology coined at the US National Science Foundation (NSF) somehow remained within the traditional programming language design community and did not get a wider acceptance. Within cyber physical systems, however, there are special classes of systems which are safety critical such as avionics, automotive, space mission systems, missile control, smart grid, industrial process control or SCADA etc. This is the class of systems that interested us the most. We realized that since many of these are domain specific, the engineers who design them are not necessarily computer scientists, and they could be from any other engineering field such as aerospace, electrical, mechanical, power systems, control and so on. The question that naturally comes up as to how they collaborate with the computer scientists who develop the foundations of system design especially systems that have digital control with analog environments which are very common in most safety-critical systems. So we appropriated the term “Science of Design” and termed the foundational aspect of such design as the science, and the domain specific engineering as the application of science. Next we talked to some of our colleagues who were involved in designs of unmanned vehicle systems. It was hoped that a strong contribution to this special issue could be obtained from such colleagues. One would assume that major requirements on the cyber components of such unmanned vehicles must be low power consumption, small form-factor, reliability, verifiability, etc. A paper describing how these requirements interplay with their system design approach, and how the physical system design influences the requirements of the cyber parts and the control algorithms, would have been a great contribution. It turned out that no integrated approach was followed by these designers. Intel x86 processors were purchased (a power hungry one), and an off-the-shelf real-time Linux was used as an execution environment, while MATLAB based control algorithm models were provided to C programmers to create the software. Disappointed by the lack of an integration of science of design into the engineering, we spoke to a number of researchers at a number of defense labs, and contractors, and heard very similar ‘separation of concern’ stories. The safety-critical systems that we were concerned with had strong coupling and interactions between one or more physical environments and a number of cyber or computing components. Evolution of the physical environments over time and space, described by their trajectories in continuous state spaces, are modeled by parameters whose evolution is best captured with continuous dynamical systems. Some of these parameters are controllable by the cyber components, and some evolve based on the dynamics of the physical worlds. The cyber components usually sample some or all of these parameters based on Nyquist criteria, and actuate robust feedback control over controllable parameters. This is often called digital control because the continuously varying parameters are sampled and discretized, while the control algorithms process the information to create control actuations in the form of discrete signals. The feedback control affects the trajectory in the physical state space. Specifically, robust control algorithms make sure that the planned trajectories are tracked by the physical system as accurately as possible, regardless of various uncertainties and exogenous disturbances. Before digital computers were cost effective, much of the control in many such systems were analog and mechanical in nature. This meant that the control components and the physical world together formed a complex dynamical system. The analysis of such system was within the realm of continuous mathematics. However, CPS systems have a dichotomy (between the continuous and the discrete) which poses challenges to their algorithmic development, proof of stability and robustness, etc. On the other hand, there is a tremendous opportunity due to the exponential effects of Moore’s law, making computing exponentially faster, cheaper, and smaller in size. However, the implementation of the control algorithms in hardware and/or software is often distributed in nature (digital signal processing, control computation for a large number of controllable parameters, and real time requirements may necessitate the use of a large number of processors, e.g. a modern automotive vehicle has more than 80 microcontrollers and processors). To make such hardware/software optimized and correct, one has to take care of concurrency issues, timing issues, power vs. performance trade-offs, and most importantly eliminate any redundant sampling or computation. Unfortunately, since such systems are often safety-critical (avionics, automotive, IEEE TRANSACTIONS ON COMPUTERS, VOL. 60, NO. 8, AUGUST 2011 1057

This article presents the very first effective design of higher-order modules in the programming language Esterel. Higher-order modules, together with the robust separate compilation scheme that implements it, allow us to address a yet unexplored application spectrum ranging from rapid prototyping of embedded functionality to hot reconfiguration of embedded software within the formal modeling framework of the synchronous hypothesis. While extensions of data-flow languages had already been proposed for Lustre [11] and Signal [25], the adaptation of similar programming concepts to imperative frameworks like Esterel has long posed major technical challenges, due to the specificity of its model of computation. We present a framework including a formal semantics, a type system, and a modular code generator, that tackle this challenge. We consider a specific stack-based module call convention and a simple event pooling protocol; in consequence signals can refer to modules and modules can be transmitted and instantiated by referencing a signal. We define a type system that computes the potential emissions of a module and prove it sound. Our type system seamlessly fits an extension of Esterel's constructive semantics with higher-order modules.

The compilation of imperative synchronous languages like Esterel has been widely studied, the separate compilation of synchronous modules has not, and remains a challenge. We propose a new compilation method inspired by traditional sequential code generation techniques to produce coroutines whose hierarchical structure reflects the control flow of the original source code. A minimalistic runtime system executes separately compiled modules.

An important step in model-based embedded system design consists in mapping functional specifications and their tasks/operations onto execution architectures and their resources. This mapping comprises both temporal scheduling and spatial allocation aspects. Therefore, we promote an approach which starts from loosely-timed/asynchronous models and proceeds by refining them to fully synchronized ones, using so-called clock calculus techniques under the architecture constraints. In this paper we provide a modeling framework based on an intermediate representation format, called clocked graphs, for polychronous endochronous specifications, which are the ones that can be safely considered for deterministic distributed real-time implementation using static scheduling techniques. Our formalism allows the specification of both "intrinsic" correctness properties of the specification, such as causality and clock consistency, and "external" correctness properties, such as endochrony, which ensure compatibility with the desired implementation architecture, including both hardware and software aspects. Using this formalism, we define a new method for distributed real-time implementation of synchronous specification. The move from (endochronous) synchronous specification to realtime scheduled implementation is a seamless sequence of model decorations.

The synchronous modeling paradigm provides strong execution correctness guarantees to embedded system design while making minimal environmental assumptions. In most related frameworks, global execution correctness is achieved by ensuring endochrony: the insensitivity of (logical) time in the system from (real) time in the environment. Interestingly, endochrony can be statically checked, making it fast to ensure design correctness. Unfortunately, endochrony is not preserved by composition, making it difficult to exploit with component-based design concepts in mind. Compositionality can be achieved by weakening the objective of endochrony but at the cost of an exhaustive state-space exploration. This raise a tradeoff between performance and precision. Our aim is to balance it by proposing a formal design methodology that adheres to a weakened global design objective: the non-blocking composition of weakly endochronous processes, while preserving local endochrony objectives. This yields an ad-hoc yet cost- efficient approach to compositional synchronous modeling.

In order to exploit the emerging multi-core processors, creating multi-threaded applications is going to be a necessity. However, resolving concurrency, synchronization, and coordination issues, and tackling the non-determinism germane in multi-threaded software is extremely difficult. Ensuring deterministic behavior and correctness with respect to the specification is necessary for safe execution of such code. It is desirable to synthesize multi-threaded code from formal specifications using a provably 'correct-by- construction' approach. In the past, reasonable success has been achieved in the 'correct-by-construction' sequential software synthesis for embedded reactive systems from synchronous programming models. Here we target deterministic multi-threaded software synthesis from deterministic specifications, such that the behavior of the code is semantically equivalent to that of the specification. We choose the polychronous model of computation for specification because (i) such specifications are multi-rate, reactive, concurrent and can be made deterministic through constraints on the environment, and (ii) formal verification methodologies and tools exist for such specifications. In this paper, we analyze under what condition a polychronous specification can be synthesized into multi-threaded C-code preserving its semantics. We also discuss how the synchronous data flow graph structure for a polychronous specification can be used to infer the threading structure of the resulting C-code.

While synchrony and asynchrony are two distinct concepts of concurrency theory, effective and formally defined embedded system design methodologies usually mix the best from both synchronous and asynchronous worlds by considering locally synchronous processes composed in a globally asynchronous way to form so called GALS architectures. In the avionics domain, for instance, the Architecture Analysis and Design Language (AADL) may be used to describe both the hardware and software architecture of an application at system-level. Yet, a synchronous design formalism might be preferred to model and validate each of the critical components of the architecture in isolation. In this paper, we illustrate the use of the polychronous (multi-clocked synchronous) paradigm to model partially asynchronous applications. The specification formalism Signal is used to describe real-world avionic applications using concepts of Integrated Modular Avionics (IMA). We show how an AADL architecture can be automatically translated into a synchronous model in SIGNAL using these modeling concepts. We present a case study on the design of generic system architecture. The approach is being implemented in the framework of the ANR project TopCased.

Embedded real-time systems consist of hardware and software that controls the behavior of a device or plant. They are ubiquitous in today's technological landscape and found in domains such as telecommunications, nuclear power, avionics, and medical technology. These systems are difficult to design and build because they must satisfy both functional and timing requirements to work correctly in their intended environment. Furthermore, embedded systems are often critical systems, where failure can lead to loss of life, loss of mission, or serious financial consequences. Because of the difficulty in creating these systems and the consequences of failure, they require rigorous and reliable design approaches. The synchronous approach is one possible answer to this demand. Its mathematical basis provides formal concepts that favor the trusted design of embedded real-time systems. The multiclock or polychronous model stands out from other synchronous specification models by its capability to enable the design of systems where each component holds its own activation clock as well as single-clocked systems in a uniform way. A great advantage is its convenience for component-based design approaches that enable modular development of increasingly complex modern systems. The expressiveness of its underlying semantics allows dealing with several issues of real-time design. This article exposes insights gained during recent years from the design of real-time applications within the polychronous framework. In particular, it shows promising results about the design of applications from the avionics domain.

Among related synchronous programming principles, the model of computation of the POLYCHRONY workbench stands out by its capability to give high-level description of systems where each component owns a local activation clock (such as, typically,distributed real-time systems or systems on a chip). In order to bring the modeling capability of POLYCHRONY to the context of a model-driven engineering toolset for embedded system design, we define a diagramic notation composed of mode automata and data-flow equations on top of the multi-clocked synchronous model of computation supported by the POLYCHRONY workbench. We demonstrate the agility of this paradigm by considering the example of an integrated modular avionics application. Our presentation features the formalization and use of model transformation techniques of the GME environment to embed the extension of POLYCHRONY's meta-model with mode automata.

We consider the problem of synthesizing correct-by-construction globally asynchronous, locally synchronous (GALS) implementations from modular synchronous specifications. This involves the synthesis of asynchronous wrappers that drive the synchronous clocks of the modules and perform input reading in such a fashion as to preserve, in a certain sense, the global properties of the system. Our approach is based on the theory of weakly endochronous systems, which gives criteria guaranteeing the existence of simple and efficient asynchronous wrappers. We focus on the transformation (by means of added signalling) of the synchronous modules of a multiclock synchronous specification into weakly endochronous modules, for which simple and efficient wrappers exist.

This special issue is based on innovative ideas presented and discussed during the first ACM/IEEE Conference on Formal Methods and Models for Co-Design (MEMOCODE) held at Mont Saint Michel in France during the summer of 2003. Selected papers from the conference were invited for this special issue together with an open call for papers soliciting novel contributions on the topics of this conference. Rigorous reviews of 12 submissions led to the selection of four papers for this special issue. In this editorial statement, we outline the premise and the context of this special issue, and give a short introduction to the theme under consideration and briefly introduce the papers selected. We also thank the authors who submitted their contributions to this special issue, and all the reviewers without whose dedication and hard work toward ensuring the quality of the selections, editing this special issue would have been impossible.

Growing design sizes and shrinking time to market windows can only be met with drastically increased productivity. One way to obtain this is a smart reuse of intellectual property. This paper presents a methodology for modular design with the help of component abstraction. It describes how imperative components can be transformed into a formal, synchronous description to provide behavioral types to the components. The synchronous composition of these abstracted components helps discover errors in the component composition. The presented methodology is illustrated by the detailed case study of a Finite Impulse Response filter. We transform initial \systemc\ modules into an intermediate static single assignment representation which is used as a basis from which corresponding behavioral types are built.

We lay a foundation for modeling and validation of asynchronous designs in a multi-clock synchronous programming model. This allows us to study properties of globally asynchronous systems using synchronous simulation and model-checking toolkits. Our approach can be summarized as automatic transformation of a design consisting of two asynchronously composed synchronous components into a fully synchronous multi-clock model preserving behavioral equivalence. The ultimate goal of this research is to provide the ability to model and build GALS systems in a fully synchronous design framework and deploy it on an asynchronous network preserving all properties of the system proven in the synchronous framework.

The synchronous model of concurrency has demonstrated its practicality for the design of circuits, embedded systems, reactive and distributed systems. This model allows to design systems around an idealized notion of deterministic concurrency, which is much easier to deal with than classical, nondeterministic, asynchronous concurrency. Compiling, optimizing, and verifying programs are done using powerful techniques. We take advantage of this rich background by presenting a translation of UML state-machines into a pivot synchronous calculus, based on mathematical notions of pre-orders, in the aim of providing an integrated development cycle for the reliable deployment of synchronous system specifications over asynchronous networks. In this paper we first present the structure of UML state-machines. Compared with earlier studies on that matter the structure under consideration supports, e.g., composite transition and history. Then, we give a brief presentation of the pivot formalism, BDL, which is used to finally give a formal semantics of UML state-machines in terms of pre-ordered transition systems.

We introduce the definition of a language of distributed reactive objects, a Behaviour Description Language (BDL), as a unified medium for specifying, verifying, compiling and validating object-oriented distributed reactive systems. One of the novelties in BDL is its seamless integration into the Unified Modeling Language approach (UML). BDL supports a description of objects interaction which respects both the functional architecture of system designs and the declarative style of diagram descriptions. This support is implemented by means of a partial-order theoretical framework. This framework allows to specify both the causality and the control models of object interactions independently of any hypothesis on the actual configuration of the system. Given the description of such a configuration, the use of BDL offers new perspectives for a flexible verification of systems by modeling them as an asynchronous network of synchronous components. It allows an optimized code generation by using compilation techniques developed for synchronous languages. It permits an accurate validation and test of applications by supporting the manipulation of both causal and control dependencies. BDL aims at maximizing the re-usability of high-level specifications while minimizing programming effort and test-case based validation of distributed systems.

Abstract Over 25 implementations of different functional languages are benchmarked using the same program, a floating-point intensive application taken from molecular biology. The principal aspects studied are compile time and execution time for the various implementations that were benchmarked. An important consideration is how the program can be modified and tuned to obtain maximal performance on each language implementation. With few exceptions, the compilers take a significant amount of time to compile this program, though most compilers were faster than the then current GNU C compiler (GCC version 2.5.8). Compilers that generate C or Lisp are often slower than those that generate native code directly: the cost of compiling the intermediate form is normally a large fraction of the total compilation time. There is no clear distinction between the runtime performance of eager and lazy implementations when appropriate annotations are used: lazy implementations have clearly come of age when it comes to implementing largely strict applications, such as the Pseudoknot program. The speed of C can be approached by some implementations, but to achieve this performance, special measures such as strictness annotations are required by non-strict implementations. The benchmark results have to be interpreted with care. Firstly, a benchmark based on a single program cannot cover a wide spectrum of ‘typical’ applications. Secondly, the compilers vary in the kind and level of optimisations offered, so the effort required to obtain an optimal version of the program is similarly varied.

We present a translation scheme for the polymorphically typed call-by-value λ-calculus. All runtime values, including function closures, are put into regions. The store consists of a stack of regions. Region inference and effect inference are used to infer where regions can be allocated and de-allocated. Recursive functions are handled using a limited form of polymorphic recursion. The translation is proved correct with respect to a store semantics, which models as a region-based run-time system. Experimental results suggest that regions tend to be small, that region allocation is frequent and that overall memory demands are usually modest, even without garbage collection.

The type and effect discipline, a framework for reconstructing the principal type and the minimal effect of expressions in implicitly typed polymorphic functional languages that support imperative constructs, is introduced. The type and effect discipline outperforms other polymorphic type systems. Just as types abstract collections of concrete values, effects denote imperative operations on regions. Regions abstract sets of possibly aliased memory locations. Effects are used to control type generalization in the presence of imperative constructs while regions delimit observable side effects. The observable effects of an expression range over the regions that are free in its type environment and its type; effects related to local data structures can be discarded during type reconstruction. The type of an expression can be generalized with respect to the variables that are not free in the type environment or in the observable effect.>

Abstract We present a new static system which reconstructs the types, regions and effects of expressions in an implicitly typed functional language that supports imperative operations on reference values. Just as types structurally abstract collections of concrete values, regions represent sets of possibly aliased reference values and effects represent approximations of the imperative behaviour on regions. We introduce a static semantics for inferring types, regions and effects, and prove that it is consistent with respect to the dynamic semantics of the language. We present a reconstruction algorithm that computes the types and effects of expressions, and assigns regions to reference values. We prove the correctness of the reconstruction algorithm with respect to the static semantics. Finally, we discuss potential applications of our system to automatic stack allocation and parallel code generation.