Automated Verification of Network Function Binaries

Formally verifying the correctness of software network functions (NFs) is necessary for network reliability, yet existing techniques require full source code and mandate the use of specific data structures. We describe an automated technique to verify NF binaries, making verification usable by network operators even on proprietary code. To solve the key challenge of bridging the abstraction levels of NF implementations and specifications without special-casing a set of data structures, we observe that data structures used by NFs can be modeled as maps, and introduce a universal type to specify both NFs and their data structures, the "ghost map". In addition, we observe that the interactions between an NF and its environment are sufficient to infer control flow and types, removing the requirement for source code. We implement our technique in Klint, a tool with which we verify, in minutes, that 7 NF binaries satisfy their specifications, without limiting developers' choices of data structures. The specifications are written in Python and use maps to model state. Klint can also verify an entire NF binary stack, all the way down to the NIC driver, using a minimal operating system. Operators can thus verify NF binaries, without source code or debug symbols, without requiring developers to use specific programming languages or data structures, and without trusting any software except Klint.

Concrete syntax definition for modeling languages

Frédéric Fondement

Model Driven Engineering (MDE) promotes the use of models as primary artefacts of a software development process, as an attempt to handle complexity through abstraction, e.g. to cope with the evolution of execution platforms. MDE follows a stepwise approach, by prescribing to develop abstract models further improved to integrate little by little details relative to the final deployment platforms. Thus, the application of an MDE process results in various models residing at various levels of abstraction. Each one of these models is expressed in a modeling language, in which one may find appropriate concepts for the abstraction level considered. Many advocate to use the right (modeling) language for the right purpose. This means that it is sometimes better approach to use small languages specific to the considered domain and abstraction level, than to use general purpose languages (e.g. UML) when they do not perfectly fit the (modeling) needs. As a matter of fact, an MDE development process, which involves many different domains and abstraction levels, should also involve a large variety of modeling languages. Project managers who want to apply an MDE process need to deal with this language proliferation to such an extent that, in the long run, one may infer that language engineers can become major actors of software development teams. We believe that comprehensive modeling language management facilities may considerably alleviate that MDE drawback. Such facilities may include modeling language definition, extension, adaptation, or composition. To define a (modeling) language, one needs to define its abstract syntax, its semantics, and one or more concrete syntaxes. This thesis focuses on concrete syntax definition for modeling languages, when the abstract syntax is given in the form of a metamodel. We will provide solutions both for textual and graphical concrete syntaxes. Some of our experiences in building textual languages (as MTL, a model transformation language), and graphical languages (as Netsilon, a web-application modeler) has shown that a lot of work was spent in implementing interface using traditional techniques, be it a text processor generated from a compiler compiler specification, or a modeler making use of modern 2D graphical libraries. Indeed, abstract and concrete syntax were implemented in a disconnected way, and it was then necessary to assemble them, which became rapidly clumsy while abstract syntax evolved. We built our solution to concrete syntax definition as companions of the abstract syntax. The definition of concrete syntax we propose here made it possible to build automatic tools able to analyze or synthesize models from/to text, and to create graphical modelers. We will present a metamodel for textual concrete syntax definition to construct constructive reversible grammars. We will also propose a technique for graphical concrete syntax definition following a two-step process: specification and realization. Specification is a restrictive approach in which a metamodel defines a graphical concrete syntax. Both relations with abstract syntax and spatial relationships are expressed by means of constraints. The realization step proposes a way to provide the concrete syntax tree a meaning, by attributing it a graphical appearance, and by expressing possible user interactions. The structure of the document is the following. After introducing in deeper details the problem and the general structure of the solution we propose, we will take a tour of MDE, text and graph grammars. Then, we will present Netsilon as an example of an MDE tool to MDE development, which required both the definition of a graphical and a textual modeling language. The two following sections will present the solutions we propose for textual and graphical concrete syntax definition, respectively. Final remarks and possible improvements, especially regarding reusability in general of MDE meta-artifacts (like metamodels or model transformations), and of concrete syntax in particular, will conclude the document.

EPFL2007

Embedded Domain-Specific Languages using Libraries and Dynamic Metaprogramming

Gilles Dubochet

Domain-specific programming is bound to play a central role in improving the productivity of writing software. This is because modern, intricate, general-purpose abstractions are rarely applicable directly to everyday programming. However, such abstractions can be used to encode domain-specific abstractions, so that the general-purpose language serves as a host in which domain-specific fragments are embedded. The benefit of traditional software engineering is maintained, while allowing writing software that integrates multiple domains. This thesis describes two such techniques in Scala –a modern language with functional and object-oriented features. The first allows embedding fragments of code with domain-specific syntax, which is weaved within the host language's own syntax so that it appears as being different. The second technique uses structural types to encode domain-specific correctness properties that object-oriented types cannot represent. An implementation of structural types in Scala is also described. The common characteristic of both techniques is that domain-specific properties are provided by a library relying only on general-purpose abstractions. However, the techniques also exemplify how certain embedding tasks rely on data that is available in the compiler but is then lost in statically-typed languages. General-purpose abstractions do not give access to this data, nor do traditional runtime reflection techniques; keeping all data is also impractical. This thesis describes two metaprogramming techniques whereby compiler data on code (code lifting) and types (manifests) can be requested by embedding libraries when needed. Compiler data is then available as literal values in the program. It further describes a metaprogramming framework that combine compiler data available in code with reflection. Its design is mirror-based, and allows a high degree of code sharing between the metaprogramming framework and the compiler.

EPFL2011

Universally Scalable Concurrent Data Structures

Tudor Alexandru David

The increase in the number of cores in processors has been an important trend over the past decade. In order to be able to efficiently use such architectures, modern software must be scalable: performance should increase proportionally to the number of allotted cores. While some software is inherently parallel, with threads seldom having to coordinate, a large fraction of software systems are based on shared state, to which access must be coordinated. This shared state generally comes in the form of a concurrent data structure. It is thus essential for these concurrent data structures to be correct, fast and scalable, regardless of the scenario (i.e.,different workloads, processors, memory units, programming abstractions). Nevertheless, few or no generic approaches exist that result in concurrent data structures which scale in a large spectrum of environments. This dissertation introduces a set of generic methods that allows to build - irrespective of the deployment environment - fast and scalable concurrent data structures. We start by identifying a set of sufficient conditions for concurrent search data structures to scale and perform well regardless of the workloads and processors they are running on.We introduce âasynchronized concurrencyâ, a paradigm consisting of four complementary programming patterns, which calls for the design of concurrent search data structures to resemble that of their sequential counterparts. Next, we show that there is virtually no practical situation in which one should seek a âtheoretically wait-freeâ algorithm at the expense of a state-of-the-art blocking algorithm in the case of search data structures: blocking algorithms are simple, fast, and can be made "practically wait-free". We then focus on the memory unit, and provide a method yielding fast concurrent data structures even when the memory is non-volatile, and structures must be recoverable in case of a transient failure. We start by introducing a generic technique that allows us to avoid doing expensive writes to non-volatile memory by using a fast software cache. We also study memory management, and propose a solution tailored to concurrent data structures that uses coarse-grained memory management in order to avoid logging. Moreover, we argue for the use of lock-free algorithms in this non-volatile context, and show how by optimizing them we can avoid expensive logging operations. Together, the techniques we propose enable us to avoid any form of logging in the common case, thus significantly improving concurrent data structure performance when using non-volatile RAM. Finally, we go beyond basic interfaces, and look at scalable partitioned data structures implemented through a transactional interface. We present multiversion timestamp locking (MVTL),a new genre of multiversion concurrency control algorithms for serializable transactions. The key idea behind MVTL is simple and novel: lock individual time points instead of locking objects or versions. We provide several MVTL-based algorithms, that address limitations of current concurrency-control schemes. In short, by spanning workloads, processors, storage abstractions, and system sizes, this dissertation takes a step towards concurrent data structures that are universally scalable.

EPFL2017