Live modeling is the ability to change an executable model at runtime, and without having to restart its execution. Sometimes this 'breaks' the ongoing execution, but in many cases, it does not have to. In earlier work, we reduced this problem to detecting fine-grained read/write conflicts between the recorded history of edit operations (created by the user) and execution steps (created by the interpreter). In this paper, we extend our approach by adding the ability to perform model checking during live modeling sessions. We motivate that this further enhances the live modeling experience, producing counter-examples or 'witness traces' relative to the current execution state, as a possible 'future', integrated with the execution and edit history, minimizing the mental gap. The model checker itself is generic, and uses (via an adapter) the language's existing interpreter. This way, we could implement this paper's running example in a working prototype with relatively little effort.

Live modeling is the ability to edit an executable model at run-time, and to subsequently continue the execution instead of having to restart it. Few modeling frameworks support this feature. Much of the research concerning live modeling attempts to bring “liveness” to existing modeling languages and environments, which is a complex, and often ad hoc endeavor. We instead argue to build modeling environments on an operation-based versioning foundation, to not only record edit operations, but also execution steps on an explicit run-time model. This reduces the complexity of patching the run-time state with edit operations to a simple merge-operation, while getting powerful features such as collaborative editing and debugging “for free.”

Security by Design (SbD) has gained increasing interest over the past decade. While iterative processes and legacy preservation aim to reduce costs and mitigate risks through continuity, SbD encourages a break in the way we do things with a simple idea: dealing with new threats, leading to new risks, requires a complete rethink of our design processes.

Multiverse debugging extends classical and omniscient debugging to allow the exhaustive exploration of non-deterministic and concurrent systems during debug sessions. The introduction of user-defined reductions significantly improves the scalability of the approach. However, the literature fails to recognize the importance of using more expressive logics, besides local-state predicates, to express breakpoints. In this article, we address this problem by introducing temporal breakpoints for multiverse debugging. Temporal breakpoints greatly enhance the expressivity of conditional breakpoints, allowing users to reason about the past and future of computations in the multiverse. Moreover, we show that it is relatively straightforward to extend a language-agnostic multiverse debugger semantics with temporal breakpoints, while preserving its generality. To show the elegance and practicability of our approach, we have implemented a multiverse debugger for the AnimUML modeling environment that supports 3 different temporal breakpoint formalisms: regular-expressions, statecharts, and statechart-based Büchi automata.

To ensure correctness of critical systems, swarm verification produces proofs of failure on systems too large to be verified using model-checking. Recent research efforts exploit both intrinsic parallelism and low-latency on-chip memory offered by FPGAs to achieve 3 orders of magnitude speedups over software. However, these approaches are limited to safety verification that encodes only what the system should not do. Liveness properties express what the system should do, and are widely used in the verification of operating systems, distributed systems, and communication protocols. Both safety and liveness properties are of paramount importance to ensure systems correctness. This paper presents Dolmen, the first FPGA implementation of a swarm verification engine that supports both safety and liveness properties. Dolmen features a deeply pipelined verification core, along with a scalable architecture to allow high-frequency synthesis on large FPGAs. Our experimental results, on a Xilinx Virtex Ultrascale+ FPGA, show that the Dolmen architecture can achieve up to 4 orders of magnitude speedups compared to software model-checking.

Multiverse debugging is an extension of classical debugging methods, particularly adapted to non-deterministic systems. Recently, a language-independent formalization was proposed. Moreover, multiverse debugging is particularly beneficial for specification and design languages, such as UML. However, this method suffers from scalability issues during breakpoint lookup. This problem arises due to the exhaustive exploration performed on the potentially infinite state-space of the system.

The mapping of software verification algorithms on FPGA promise orders of magnitude faster verification. FP-GASwarm shows 900X speedup over software swarm verification. However, this approach misses important optimization opportunities and glosses over algorithmic design-space exploration.This paper introduces Carnac, a deeply pipelined swarm verification architecture, which by exposing the algorithmic variability points can realize multiple verification algorithms. Furthermore, we introduce the Mixed Young Random Frontier-Bounded (MYR_FB), a new swarm verification algorithm, found through an efficiency-based design-space exploration.Evaluated on the BEEM benchmark, the MYR_FB algorithm shows up to 144% efficiency gain over FPGASwarm on 72% of the models. The Carnac architecture runs at 400MHz on Xilinx Ultrascale+ FPGA, and can accommodate twice more verification cores than FPGASwarm. Overall the evaluation shows a 7.58X speedup over FPGASwarm, while enabling an unprecedented scalability on high-end FPGAs.

International audience

EFPGAs give designers the flexibility to make changes at any point in the chip’s life span, even in the customers’ systems. Though, eFPGA are not efficient from an integration perspective, making proper dimensionning and tailoring mandatory. Unfortunately, designing an eFPGA is a complex and error-prone task. Even though automatic generation from high level models can produce correct-by-construction layouts, integration remains complex due to process variation. A key point is then to reduce the technology dependency.This paper presents the ELNATH project in which three implementations of the same architecture have been addressed: overlay, eFPGA, and 55 nm FPGA thanks to an open-source integrated tool flow that supports defining, implementing and programming reconfigurable architectures.

Among formal methods, model-checking offers a high-level of automation and can lower the cost of the verification process. Two preliminary studies on FPGA model-checking show a high-performance increase, thanks to the massive parallelism and precise memory control opportunities. However, these approaches rely on HDL-based ad-hoc model encoding, and miss the importance of decoupling the modeling language from the verification core, which greatly limits their usability. In this paper we propose Menhir, a new highly modular hardware model-checker, inspired by the architecture of software verification frameworks. Menhir is based on a generic language-verification interface which isolates the modeling-language semantics from the verification core, allowing their independent evolution. Menhir opens the architecture to the whole spectrum of modeling languages. Moreover, it proposes a polymorphic verification core, which offers a continuum between partial and exhaustive verification, with promising performances.

Cybersecurity is becoming vital as industries are gradually moving from automating physical processes to a higher level automation using cyber physical systems (CPS) and internet of things (IoT). In this context, security is becoming a continuous process that runs in parallel to other processes during the complete life cycle of a system. Traditional threat analysis methods use design models alongside threat models as an input for security analysis, hence missing the life-cycle-based dynamicity required by the security concern. In this paper, we argue for an attacker-aware systems modeling language that exposes the systems attack surfaces. For this purpose, we have designed Pimca, a domain specific modeling language geared towards capturing the attacker point of view of the system. This study introduces the formalism along with the Pimca workbench, a framework designed to ease the development and manipulation of the Pimca models. Finally, we present two relevant use cases, serving as a preliminary validation of our approach. © Copyright 2020 by SCITEPRESS - Science and Technology Publications, Lda. All rights reserved.

Models have been shown to be useful during virtually all stages of the software lifecycle. They can be reverse engineered from existing artifacts, or created as part of a system's execution, but in many cases models are created by designers from informal specifications. In the latter case, such design models are typically used as means of communication between designers, and developers. They can also in some cases be validated by simulation over test cases, or even by formal verification. However, most existing model simulation or verification approaches require relatively consistent and complete models, whereas design models often start small, incomplete, and inconsistent. Moreover, few design models actually reach the stage where they can be simulated, and even fewer the stage where they can be formally verified. In order to address this issue, we propose a partial modeling approach that makes it possible to animate incomplete and inconsistent models. This approach makes it possible to incrementally improve testable models, and can also help designers reach the stage where their models can be formally verified. A proof-of-concept tool called AnimUML has been created in order to provide means to evaluate the approach on several examples. They are all executable, and some can even undergo model-checking.

The increasing complexity of embedded systems renders verification of software programs more complex and may require applying monitoring and formal techniques, like model-checking. However, to use such techniques, system engineers usually need formal experts to express software requirements in a formal language. To facilitate the use of model-checking tools by system engineers, our approach consists of using a UML model interpreter with which the software requirements can directly be expressed as observer automata in UML as well. These observer automata are synchronously composed with the system, and can be used unchanged both for model verification and runtime monitoring. Our approach has been evaluated on the user interface model of a cruise control system. The observer verification results are in line with the verification of equivalent LTL properties. The runtime overhead of the monitoring infrastructure is 6.5%, with only 1.2% memory overhead.

A leader node in Ad hoc networks and especially in WSNs and IoT networks is needed in many cases, for example to find a node with minimum energy or situated on the extreme left of the network. For this kind of applications, algorithms must be robust and fault-tolerant since it is difficult and even impossible to intervene if a node fails. Such a situation can be catastrophic in case that this node is the leader. In this paper, we present a new algorithm, which is based on a tree routing protocol. It starts from local leaders which will start the process of flooding to determine a spanning tree. During this process their value will be routed. If two spanning trees meet each other then the tree routing the best value will continue its process while the other tree will stop it. The remaining tree is the dominating one and its root will be the leader. This algorithm turns out to be low energy consuming with reduction rates that can exceed 85%. It is efficient and fault-tolerant since it works in the case where any node can fail and in the case where the network is disconnected.

The increasing complexity of embedded systems leads to uncertain behaviors, security flaws, and design mistakes. With model-based engineering, early diagnosis of such issues is made possible by verification tools working on design models. However, three severe drawbacks remain to be fixed. First, transforming design models into executable code creates a semantic gap between models and code. Furthermore, for formal verification, a second transformation (towards a formal language) is generally required, which complicates the diagnosis process. Finally, an equivalence relation between verified formal models and deployed code should be built, proven, and maintained. To tackle these issues, we introduce a UML interpreter that fulfills multiple purposes: simulation, formal verification, and execution on both desktop computer and bare-metal embedded target. Using a single interpreter for all these activities ensures operational semantics consistency. We illustrate our approach on a level crossing example, showing verification of LTL properties on a desktop computer, as well as execution on a stm32 embedded target.

Summary Model‐checking enables the automated formal verification of software systems through the explicit enumeration of all the reachable states. While this technique has been successfully applied to industrial systems, it suffers from the state‐space explosion problem because of the exponential growth in the number of states with respect to the number of interacting components. In this paper, we present a new reachability analysis algorithm, named Past‐Free[ze], that reduces the state‐space explosion problem by freeing parts of the state‐space from memory. This algorithm relies on the explicit isolation of the acyclic parts of the system before analysis. The parallel composition of these parts drives the reachability analysis, the core of all model‐checkers. During the execution, the past states of the system are freed from memory making room for more future states. To enable counter‐example construction, the past states can be stored on external storage. To show the effectiveness of the approach, the algorithm was implemented in the OBPObservation Engineand was evaluated both on a synthetic benchmark and on realistic case studies from automotive and aerospace domains. The benchmark, composed of 50 test cases, shows that in average, 75%of the state‐space can be dropped from memory thus enabling the exploration of up to 14 times more states than traditional approaches. Moreover, in some cases, the reachability analysis time can be reduced by up to 25%. In realistic settings, the use of Past‐Free[ze] enabled the exploration of a state‐space 4.5 times larger on the automotive case study, where almost 50%of the states are freed from memory. Moreover, this approach offers the possibility of analyzing an arbitrary number of interactions between the environment and the system‐under‐verification; for instance, in the case of the aerospace example, 1000 pilot/system interactions could be analyzed unraveling an 80 GB state‐space using only 10 GB of memory. Copyright © 2016 John Wiley & Sons, Ltd.

SUMMARY The current integrated circuit technologies are approaching their physical limits in terms of scaling and power consumption, in this context, the electronic design automation (EDA) industry is pushed towards solving ever more challenging problems in terms of performance, scalability and adaptability. Meeting these constraints needs innovation at both the algorithmic and the methodological level. Amongst academic EDA tools, Madeo toolkit has been targeting field‐programmable gate array (FPGA) design‐automation at the logic and the physical level since the late 1990s. As many other long‐living software, despite embedding valuable legacy, Madeo exhibits unwanted characteristics that penalize evolution and render the automation problems even more difficult. This study presents a methodological approach to physical‐design automation relying on model‐driven engineering, which is illustrated through the incremental redesign of the Madeo framework. A benefit of this approach is the emergence of a common vocabulary to describe the EDA domain in an FPGA scope. A second advantage is the isolation of the optimization algorithms from the structural domain models. However, the main asset is the possibility to re‐inject into the newly designed toolkit most of the legacy code. The redesigned framework is compared with and scored against initial code‐base, and demonstrates a regression‐free remodeling of the environment with net improvements in terms of size and complexity metrics. As a consequence, the evolution capability is back on stage, and the domain‐space exploration widens to the algorithmic axis. Copyright © 2013 John Wiley & Sons, Ltd.