Domain-specific languages: from design to implementationapplication to video device drivers generation

Domain-specific languages (DSL) have many potential advantages in terms of software engineering, ranging from increased productivity to the application of formal methods. Although they have been used in practice for decades, there has been little study of methodology or implementation tools for the DSL approach. We present our DSL approach and its application to a realistic domain: the generation of video display device drivers. The article focuses on the validation of our proposed framework for domain-specific languages, from design to implementation. The framework leads to a flexible design and structure, and provides automatic generation of efficient implementations of DSL programs. Additionally, we describe an example of a complete DSL for video display adaptors and the benefits of the DSL approach for this application. This demonstrates some of the generally claimed benefits of using DSLs: increased productivity, higher-level abstraction, and easier verification. This DSL has been fully implemented with our approach and is available. Compose project URL: http://www.irisa.fr/compose/gal     

An application adaptation layer for wireless sensor networks

In wireless sensor networks, poor performance or unexpected behavior may be experienced for several reasons, such as trivial deterioration of sensing hardware, unsatisfactory implementation of application logic, or mutated network conditions. This leads to the necessity of changing the application behavior after the network has been deployed. Such flexibility is still an open issue as it can be achieved either at the expense of significant energy consumption or through software complexity. This paper describes an approach to adapt the behavior of running applications by intercepting the calls made to the operating system services and changing their effects at run-time. Customization is obtained through small fragments of interpreted bytecode, called adaptlets, injected into the network by the base station. Differently from other approaches, where the entire application is interpreted, adaptlets are tied only to specific services, while the bulk of the application is still written in native code. This makes our system able to preserve the compactness and efficiency of native code and to have little impact on the overall application performance. Also, applications must not be rewritten because the operating system interfaces are unaffected. The adaptation layer has been implemented in the context of TinyOS using an instruction set inspired to the Java bytecode. Examples that illustrate the programming of the adaptation layer are presented together with their experimental validation.     

Implementing an embedded compiler using program transformation rules

Domain‐specific languages (DSLs) are well‐recognized to ease programming and improve robustness for a specific domain, by providing high‐level domain‐specific notations and checks of domain‐specific properties. The compiler of a DSL, however, is often difficult to develop and maintain, because of the need to define a specific treatment for a large and potentially increasing number of language constructs. To address this issue, we propose an approach for specifying a DSL compiler using control‐flow sensitive concrete‐syntax based matching rules. These rules either collect information about the source code to carry out checks or perform transformations to carry out compilation. Because rules only mention the relevant constructs, using their concrete syntax, and hide the complexity of control‐flow graph traversal, it is easy to understand the purpose of each rule. Furthermore, new compilation steps can be added using only a small number of lines of code. We explore this approach in the context of the z2z DSL for network gateway development and show that it is beneficial to implement the core of its compiler in this manner.Copyright © 2013 John Wiley & Sons, Ltd.     

A Design for Type-Directed Programming in Java

Type-directed programming is an important and widely used paradigm in the design of software. With this form of programming, an application may analyze type information to determine its behavior. By analyzing the structure of data, many operations, such as serialization, cloning, adaptors and iterators may be defined once, for all types of data. That way, as the program evolves, these operations need not be updated—they will automatically adapt to new data forms. Otherwise, each of these operations must be individually redefined for each type of data, forcing programmers to revisit the same program logic many times during a program's lifetime.The Java language supports type directed programming with the instanceof operator and the Java Reflection API. These mechanisms allow Java programs to depend on the name and structure of the run-time classes of objects. However, the Java mechanisms for type-directed programming are difficult to use. They also do not integrate well with generics, an important new feature of the Java language.In this paper, we describe the design of several expressive new mechanisms for type-directed programming in Java, and show that these mechanisms are sound when included in a language similar to Featherweight Java. Basically, these new mechanisms pattern-match the name and structure of the type parameters of generic code, instead of the run-time classes of objects. Therefore, they naturally integrate with generics and provide strong guarantees about program correctness. As these mechanisms are based on pattern matching, they naturally and succinctly express many operations that depend on type information. Finally, they provide programmers with some degree of protection for their abstractions. Whereas instanceof and reflection can determine the exact run-time type of an object, our mechanisms allow any supertype to be supplied for analysis, hiding its precise structure.     

Combining static analysis and state transition graphs for verification of event-condition-action systems in the RERS 2012 and 2013 challenges

We present a combination of approaches for the verification of event-condition-action (ECA) systems. The analyzed ECA systems range from structurally simple to structurally complex systems. We address the verification of reachability properties and behavioral properties. Reachability properties are represented by assertions in the program and we determine statically whether an assertion holds for all execution paths. Behavioral properties are represented as linear temporal logic formulas specifying the input/output behavior of the program. Our approach assumes a finite state space. We compare a symbolic analysis with an exhaustive state space exploration and discuss the trade-offs between the approaches in terms of the number of computed states and run-time behavior. All variants compute a state transition graph which can also be passed to an LTL verifier. The variants have a different impact on the number of computed states in the state transition graph which in turn impacts the run-time and memory consumption of subsequent phases. We evaluate the different analysis variants with the RERS benchmarks.     

Patterns of self-stabilization in database consistency maintenance

A substantial portion of the database programming efforts are invested in integrity constraints enforcement. Traditionally, both the constraint semantics and their enforcement were embedded inside application programs. In recent years several studies have dealt with specifying integrity constraints as separate entities (e.g. rules), and relating the database consistency requirements to these rules. In this paper we deal with the complementary issue of stabilizing the database when update exceptions occur. While a simplistic approach is to abort any transaction that inflicts consistency violations, this is not always the desired action. We take advantage of the empirical observation that most of the exception-handling policies follow a small number of behavior patterns. Unlike some previous approaches that base their repair solution on syntactic analysis of the constraints and performance issues, we base our approach on the application semantics as reflected in these behavioral patterns. We describe a model that uses high-level abstractions called stabilizer types denoting these behavior patterns for consistency restorations, whose exact semantics is case dependent. It follows the fault tolerance's self-stabilization approach. An inference mechanism translates these abstractions into executable active rules. This approach provides high-level language to the exception handling portion of the application and substantially reduces the required programming.     

A domain specific language for spatial simulation scenarios

This article describes DSL3S, a domain specific modelling language for Spatial Simulation in the field of Geographic Information Systems (GIS). Techniques such as cellular automata and agent-based modelling have long been used to capture and simulate the temporal dynamics of spatial information. Tools commonly employed to implement spatial simulation models include code libraries and pre-compiled models; the former require advanced programming skills while the latter impose relevant constraints on application scope. Previous attempts to produce domain specific languages in the field have invariably resulted in new textual programming languages (e.g. SELES, NetLogo, Ocelet) that are platform specific and in some cases with weak GIS support and interoperability. DSL3S synthesises relevant concepts of spatial simulation in a UML profile, that allows the design of simulation models through the arrangement of graphical elements. An implementation of this language is also presented, that relies on Model Driven Development (MDD) tools distributed with the Eclipse IDE. This includes a code generation infrastructure, that produces ready to run simulations from DSL3S models, supported by the MASON simulation tool-kit. Finally, DSL3S models for three simple and classical simulations allows to better illustrate and discuss the usage of the language.     

A technique for non-invasive application-level checkpointing

One of the key elements required for writing self-healing applications for distributed and dynamic computing environments is checkpointing. Checkpointing is a mechanism by which an application is made resilient to failures by storing its state periodically to the disk. The main goal of this research is to enable non-invasive reengineering of existing applications to insert Application-Level Checkpointing (ALC) mechanism. The Domain-Specific Language (DSL) developed in this research serves as a perfect means towards this end and is used for obtaining the ALC-specifications from the end-users. These specifications are used for generating and inserting the actual checkpointing code into the existing application. The performance of the application having the generated checkpointing code is comparable to the performance of the application in which the checkpointing code was inserted manually. With slight modifications, the DSL developed in this research can be used for specifying the ALC mechanism in several base languages (e.g., C/C++, Java, and FORTRAN).     

Toward architecture-based context-aware deployment and adaptation

Software systems are increasingly expected to dynamically self-adapt to the changing environments. One of the main adaptation mechanisms is dynamic recomposition of application components. This paper addresses the key issues that arise when context knowledge is used to steer the run-time (re)composition process so as to match the new environmental conditions. In order to integrate such knowledge into this process, A Continuous Context-Aware Deployment and Adaptation (ACCADA) framework is proposed. To support run-time component composition, the essential runtime abstractions of the underlying component model are studied. By using a layered modeling approach, our framework gradually incorporates design-time as well as run-time knowledge into the component composition process. Service orientation is employed to facilitate the changes of adaptation policy. Results show that our framework has significant advantages over traditional approaches in light of flexibility, resource usage and lines of code. Although our experience was based on the OSGi middleware, we believe our findings to be general to architecture-based management systems using reflective component models.     

Performance of multi-tasking and synchronization mechanisms in the programming language SR

High-level language primitives for concurrent programming exist in languages such as Ada and Modula-2. However, each of these languages provides only a single means for specifying multitasking and synchronization, essential in the implementation of concurrent systems. The SR language provides several mechanisms for specifying multi-tasking and synchronization, so it can be used to explore the performance of various communication techniques. This paper presents performance results for SR's multi-tasking and synchronization mechanisms and discusses the effects of the generated code, the run-time support and the hardware on these results. These results are compared with those for similar mechanisms in other languages, leading to some general conclusions about the performance of process communication primitives. These performance results can be used by programmers to make design choices that allow systems programs written in high-level languages to meet real-time performance specifications.     

Developing and evolving a DSL-based approach for runtime monitoring of systems of systems

Complex software-intensive systems are often described as systems of systems (SoS) due to their heterogeneous architectural elements. As SoS behavior is often only understandable during operation, runtime monitoring is needed to detect deviations from requirements. Today, while diverse monitoring approaches exist, most do not provide what is needed to monitor SoS, e.g., support for dynamically defining and deploying diverse checks across multiple systems. In this paper we report on our experiences of developing, applying, and evolving an approach for monitoring an SoS in the domain of industrial automation software, that is based on a domain-specific language (DSL). We first describe our initial approach to dynamically define and check constraints in SoS at runtime and then motivate and describe its evolution based on requirements elicited in an industry collaboration project. We furthermore describe solutions we have developed to support the evolution of our approach, i.e., a code generation approach and a framework to automate testing the DSL after changes. We evaluate the expressiveness and scalability of our new DSL-based approach using an industrial SoS. We also discuss lessons we learned. Our results show that while developing a DSL-based approach is a good solution to support industrial users, one must prepare the approach for evolution, by making it extensible and adaptable to future scenarios. Particularly, support for automated (re-)generation of tools and code after changes and automated testing are essential.     

SIMCom: Statistical sniffing of inter-module communications for runtime hardware trojan detection

Timely detection of Hardware Trojans (HTs) has become a major challenge for secure integrated circuits. We present a run-time methodology for HT detection that employs a multi-parameter statistical traffic modeling of the communication channel in a given System-on-Chip (SoC), named as SIMCom. The main idea is to model the communication using multiple side-channel information like the Hurst exponent, the standard deviation of the injection distribution, and the hop distribution jointly to accurately identify HT-based online anomalies (that affects the communication without affecting the protocols or control signals). At design time, our methodology employs a “property specification language” to define and embed assertions in the RTL, specifying the correct communication behavior of a given SoC. At run-time, it monitors the anomalies in the communication behavior by checking the execution patterns against these assertions. For illustration, we evaluate SIMCom for three SoCs, i.e., SoC1 (four single-core MC8051 and UART modules), SoC2 (four single-core MC8051, AES, ethernet, memctrl, BasicRSA, RS232 modules), and SoC3 (four single-core LEON3 connected with each other and AES, ethernet, memctrl, BasicRSA, RS23s modules microcontrollers). The experimental results show that with the combined analysis of multiple statistical parameters, SIMCom is able to detect all the benchmark Trojans (available on trust-hub) with less than 1% area and power overhead.     

Asymptotic performance of ZF and MMSE crosstalk cancelers for DSL systems

We present asymptotic expressions for user throughput in a multi-user digital subscriber line system (DSL) with a linear decoder, in increasingly large system sizes. This analysis can be seen as a generalization of results obtained for wireless communication. The features of the diagonal elements of the wireline DSL channel matrices make wireless asymptotic analyses inapplicable for wireline systems. Further, direct application of results from random matrix theory (RMT) yields a trivial lower bound. This paper presents a novel approach to asymptotic analysis, where an alternative sequence of systems is constructed that includes the system of interest in order to approximate the spectral efficiency of the linear zero-forcing (ZF) and minimum mean squared error (MMSE) crosstalk cancelers. Using works in the field of large dimensional random matrices, we show that the user rate in this sequence converges to a non-zero rate. The approximation of the user rate for both the ZF and MMSE cancelers are very simple to evaluate and does not need to take specific channel realizations into account. The analysis reveals the intricate behavior of the throughput as a function of the transmission power and the channel crosstalk. This unique behavior has not been observed for linear decoders in other systems. The approximation presented here is much more useful for the next generation G.fast wireline system than earlier DSL systems as previously computed performance bounds, which are strictly larger than zero only at low frequencies. We also provide a numerical performance analysis over measured and simulated DSL channels which show that the approximation is accurate even for relatively low dimensional systems and is useful for many scenarios in practical DSL systems.     

Automated fault tolerance augmentation in model-driven engineering for CPS

Cyber-Physical Systems are usually subject to dependability requirements such as safety and reliability constraints. Over the last 50 years, a body of efficient fault-tolerance mechanisms has been devised to handle faults occurring at run-time. However, properly implementing those mechanisms is a time-consuming task that requires a great deal of know-how. In this paper, we propose a general framework which allows system designers to decouple functional and non-functional concerns, and express non-functional properties at design time using domain-specific languages. In the spirit of generative programming, functional models are then automatically “augmented” with dependability mechanisms. Importantly, the real-time behavior of the initial models in terms of sampling times and meeting deadlines is preserved. The practicality of the approach is demonstrated with the automated implementation of one prominent software fault-tolerance pattern, namely N-Version Programming, in the CPAL model-driven engineering workflow.     

Encoding Generic Judgments: Preliminary results

Operational semantics is often presented in a rather syntactic fashion using relations specified by inference rules or equivalently by clauses in a suitable logic programming language. As it is well known, various syntactic details of specifications involving bound variables can be greatly simplified if that logic programming language has term-level abstractions (λ-abstraction) and proof-level abstractions (eigenvariables) and the specification encodes object-level binders using λ-terms and universal quantification. We shall attempt to extend this specification setting to include the problem of specifying not only relations capturing operational semantics, such as one-step evaluation, but also properties and relations about the semantics, such as simulation. Central to our approach is the encoding of generic object-level judgments (universally quantified formulas) as suitable atomic meta-level judgments. We shall encode both the one-step transition semantics and simulation of (finite) π-calculus to illustrate our approach.     

Itemset mining: A constraint programming perspective

The field of data mining has become accustomed to specifying constraints on patterns of interest. A large number of systems and techniques has been developed for solving such constraint-based mining problems, especially for mining itemsets. The approach taken in the field of data mining contrasts with the constraint programming principles developed within the artificial intelligence community. While most data mining research focuses on algorithmic issues and aims at developing highly optimized and scalable implementations that are tailored towards specific tasks, constraint programming employs a more declarative approach. The emphasis lies on developing high-level modeling languages and general solvers that specify what the problem is, rather than outlining how a solution should be computed, yet are powerful enough to be used across a wide variety of applications and application domains.This paper contributes a declarative constraint programming approach to data mining. More specifically, we show that it is possible to employ off-the-shelf constraint programming techniques for modeling and solving a wide variety of constraint-based itemset mining tasks, such as frequent, closed, discriminative, and cost-based itemset mining. In particular, we develop a basic constraint programming model for specifying frequent itemsets and show that this model can easily be extended to realize the other settings. This contrasts with typical procedural data mining systems where the underlying procedures need to be modified in order to accommodate new types of constraint, or novel combinations thereof. Even though the performance of state-of-the-art data mining systems outperforms that of the constraint programming approach on some standard tasks, we also show that there exist problems where the constraint programming approach leads to significant performance improvements over state-of-the-art methods in data mining and as well as to new insights into the underlying data mining problems. Many such insights can be obtained by relating the underlying search algorithms of data mining and constraint programming systems to one another. We discuss a number of interesting new research questions and challenges raised by the declarative constraint programming approach to data mining.     

A non-invasive object-oriented tool for software testing

A non-invasive approach for capture and playback (C&P) can be a very useful tool for testing applications endowed of a graphic user interface in local and/or distributed environments, and in general for testing applications without modifying their run-time environment. In the software lifecycle, the phases ofC&P are performed after the application design. Since these are close to the delivery deadline, the time needed for application testing is considered as a high, and frequently unacceptable, cost. In this paper, a new approach for non-invasiveC&P testing techniques is proposed. This is strongly based on the object-oriented paradigm at both hardware and software levels. In particular, a new board for image grabbing and pattern matching, and a new object-oriented language for specifying the tests have been defined. The main goals of this new approach are (i) the reduction of testing time by supporting the reuse of tests (coded by using a specific language) at each level of abstraction, and (ii) the anticipation of the capture-phase of testing with the system design.     

Real-time Concurrent C: A language for programming dynamic real-time systems

Concurrent C, is a parallel superset of C (and of C++) that provides facilities such as specifying timeouts during process interactions, delaying program execution, accepting messages in a user-specified order, and asynchronous messages that can be used for writing real-time programs. However, Concurrent C does not provide facilities for specifying strict timing constraints, e.g., Concurrent C only ensures that the lower bounds on the specified delay and timeout periods are satisfied. Real-Time Concurrent C extends Concurrent C by providing facilities to specify periodicity or deadline constraints, to seek guarantees that timing constraints will be met, and to perform alternative actions when either the timing constraints cannot be met or the guarantees are not available.In this paper, we will discuss requirements for a real-time programming language, briefly summarize Concurrent C, and motivate and describe the real-time extensions to Concurrent C. We also discuss scheduling and other run-time facilities that have been incorporated to support the real-time extensions. A prototype implementation of Real-Time Concurrent C is nearing completion.