Cyber-Physical Systems (CPS) consist of software interacting with the physical world, such as robots, vehicles, and industrial processes. CPS are frequently responsible for the safety of lives, property, or the enviro...
详细信息
Cyber-Physical Systems (CPS) consist of software interacting with the physical world, such as robots, vehicles, and industrial processes. CPS are frequently responsible for the safety of lives, property, or the environment, and so software correctness must be determined with a high degree of certainty. To that end, simply testing a CPS is insufficient, as its interactions with the physical world may be difficult to predict, and unsafe conditions may not be immediately obvious. Formal verification can provide stronger safety guarantees but relies on the accuracy of the verified system in representing the real system. Bringing together verification and implementation can be challenging, as languages that are typically used to implement CPS are not easy to formally verify, and languages that lend themselves well to verification often abstract away low-level implementation details. Translation between verification and implementation languages is possible, but requires additional assurances in the translation process and increases software complexity;having both in a single language is desirable. This paper presents a formalization of MARVeLus, a CPS language which combines verification and implementation. We develop a metatheory for its synchronous refinement type system and demonstrate verified synchronous programs executing on real systems.
During testing, an error in software can either propagate to the output variables or be masked before it reaches them. Error propagation and masking characteristics are crucial in software testing because they directl...
详细信息
During testing, an error in software can either propagate to the output variables or be masked before it reaches them. Error propagation and masking characteristics are crucial in software testing because they directly influence testing effectiveness. The testing community has hence focused on developing test mechanisms to promote the propagation and reduce masking of errors in software under test. However, little is known about how severely the errors propagate and are masked during software execution. Moreover, little is known about what influences software's propagation and masking characteristics. Thus, in this study, we performed experiments to investigate the behavior of errors during software execution. We chose six case examples and created mutants per case example by seeding an error into each one. We then executed the mutants with randomly selected test cases and investigated how many errors were propagated and masked. If an error was masked, we examined the cause. In addition, we investigated what percentage of errors in the mutants reached the output variables. This study provides insight into the characteristics of errors in terms of propagation and masking, which will help testers design test inputs and choose monitoring variables to properly handle the masking of errors during testing.
Robots and other cyber-physical systems are held to high standards of safety and reliability, and thus one must be confident in the correctness of their software. Formal verification can provide such confidence, but p...
详细信息
ISBN:
(纸本)9781450399074
Robots and other cyber-physical systems are held to high standards of safety and reliability, and thus one must be confident in the correctness of their software. Formal verification can provide such confidence, but programming languages that lend themselves well to verification often do not produce executable code, and languages that are executable do not typically have precise enough formal semantics. We present MARVeLus, a stream-based approach to combining verification and execution in a synchronous programming language that allows formal guarantees to be made about implementation-level source code. We then demonstrate the end-to-end process of developing a safe robotics application, from modeling and verification to implementation and execution.
We present ***, a synchronous reactive language that adds synchronous concurrency and preemption to JavaScript. Inspired from Esterel, *** simplifies the programming of non-trivial temporal behaviors as found in compl...
详细信息
ISBN:
(纸本)9781450376136
We present ***, a synchronous reactive language that adds synchronous concurrency and preemption to JavaScript. Inspired from Esterel, *** simplifies the programming of non-trivial temporal behaviors as found in complex web interfaces or IoT controllers and the cooperation between synchronous and asynchronous activities. *** is compiled into plain sequential JavaScript and executes on unmodified runtime environments. We use three examples to present and discuss ***: a simple web login form to introduce the language and show how it differs from JavaScript, and two real life examples, a medical prescription pillbox and an interactive music system that show why concurrency and preemption help programming such temporal applications.
In this article, a formal generic framework for defining and reasoning about deterministic concurrency in synchronous systems is implemented in the SPIN model checker. Concretely, the work implements the clock- synchr...
详细信息
In this article, a formal generic framework for defining and reasoning about deterministic concurrency in synchronous systems is implemented in the SPIN model checker. Concretely, the work implements the clock- synchronised shared memory (CSM) theory, which extends synchronous programming with more and higher- level CSM data types. These CSM data types are equipped with a synchronisation policy prescribing how concurrent calls to objects methods must be organised. In a policy constructive system, all methods of every object can be scheduled in a policy-conformant manner without deadlocking. In our framework, synchronous policies get codified as PRoMELA never-claims. In this form, the model checker can search for executions (interleavings) that satisfy the synchronous product of all the never-claims, namely policy-conformant schedules for all the CSM objects. The existence of such policy-conformant schedules verifies that the concurrent synchronous system is deterministic. The approach of this article extends beyond a single semantics since it can handle the synchronous programming model as well as the various forms of the sequentially constructive model found in the literature.
The security of Cyber-Physical Systems (CPSs) is increasingly important as more and more of these systems are added to the Internet of Things (IoT). As we increase the complexity and connectivity of our smart systems,...
详细信息
The security of Cyber-Physical Systems (CPSs) is increasingly important as more and more of these systems are added to the Internet of Things (IoT). As we increase the complexity and connectivity of our smart systems, we likewise broaden their digital attack surface. Recorded attacks on CPSs have caused significant physical impacts making methods for mitigation of attacks of paramount importance. The use of runtime enforcement (RE) can prevent violation of security policies. Here, runtime enforcers intervene before the CPS is compromised. Two key challenges are presented: (1) for complex systems, methods for automatically composing multiple policies are lacking;and (2) runtime enforcers are themselves executed digitally-meaning they too could have potential security vulnerabilities. We present the first comprehensive runtime enforcement framework which addresses both challenges. It can compose a lot of security policies in parallel and synthesize these policies into the more trustworthy hardware layers of a system. This removes reliance on potentially vulnerable firmware and software layers. We demonstrate our approach with policies to mitigate a set of attacks on a Fused Filament Fabrication (FFF) 3D printer. The experimental results show linear growth in logic element and register usage as the number of policies increase. This compares favourably to the exponential state space explosion that occurs with the conventional approach of monolithic composition. Additionally, we find higher enforcer clock frequencies are possible with the proposed parallel approach compared to existing serial approaches.
Cyber-Physical attacks (CP-attacks) are launched either from the cyber-space or from the physical-space to take control of a Cyber-Physical System (CPS). Unlike conventional cyber-attacks, which are prevented through ...
详细信息
Cyber-Physical attacks (CP-attacks) are launched either from the cyber-space or from the physical-space to take control of a Cyber-Physical System (CPS). Unlike conventional cyber-attacks, which are prevented through new security patches as new attacks emerge, there are no known mechanisms for incrementally patching CPS in the event of new attacks. To this end, we develop a novel approach based on recent advances in mitigating CP-attacks using run-time enforcement (RE). RE-methods have been developed for CPS, such as industrial processes and pacemakers. However, the proposed solutions are not developed considering the need for future patching as new attacks emerge. To this end, we develop the first compositional RE framework, which is specifically developed to be able to add new security patches as new security policies are added. We illustrate our approach using the case study of a drone swarm. The experimental results show that the proposed compositional/incremental approach does not suffer from the state space explosion, unlike the monolithic composition. We demonstrate a linear relationship between compile time, compile size, and execution time as the number of policies increases in the proposed compositional scheme.
Scade is a domain-specific synchronous functional language used to implement safety-critical real-time software for more than twenty years. Two main approaches have been considered for its semantics: (i) an indirect c...
详细信息
Scade is a domain-specific synchronous functional language used to implement safety-critical real-time software for more than twenty years. Two main approaches have been considered for its semantics: (i) an indirect collapsing semantics based on a source-to-source translation of high-level constructs into a data-flow core language whose semantics is precisely specified and is the entry for code generation;a relational synchronous semantics, akin to Esterel, that applies directly to the source. It defines what is a valid synchronous reaction but hides, on purpose, if a semantics exists, is unique and can be computed;hence, it is not executable. This paper presents, for the first time, an executable, state-based semantics for a language that has the key constructs of Scade all together, in particular the arbitrary combination of data-flow equations and hierarchical state machines. It can apply directly to the source language before static checks and compilation steps. It is constructive in the sense that the language in which the semantics is defined is a statically typed functional language with call-by-value and strong normalization, e.g., it is expressible in a proof-assistant where all functions terminate. It leads to a reference, purely functional, interpreter. This semantics is modular and can account for possible errors, allowing to establish what property is ensured by each static verification performed by the compiler. It also clarifies how causality is treated in Scade compared with Esterel. This semantics can serve as an oracle for compiler testing and validation;to prototype novel language constructs before they are implemented, to execute possibly unfinishedmodels or that are correct but rejected by the compiler;to prove the correctness of compilation steps. The semantics given in the paper is implemented as an interpreter in a purely functional style, in OCaml.
We present a hardware implementation of the high-level multi-paradigm language OCAML using a declarative language called Eclat. Eclat is tailored for programming reactive hardware applications mixing interaction with ...
详细信息
ISBN:
(纸本)9783031520372;9783031520389
We present a hardware implementation of the high-level multi-paradigm language OCAML using a declarative language called Eclat. Eclat is tailored for programming reactive hardware applications mixing interaction with physical devices and long-running computations. It is compiled to synthesizable hardware descriptions for configuring Field Programmable Gate Arrays (FPGAs). We have implemented the OCAML Virtual Machine as an Eclat function to execute complex computations (programmed in OCAML) in reactive applications (programmed in Eclat). This implementation comprises a bytecode interpreter and a runtime system with automatic memory management. The OCAML programmers can customize this runtime by defining external Eclat functions, i.e., hardware accelerators.
Search strategies are crucial to efficiently solve constraint satisfaction problems. However, programming search strategies in the existing constraint solvers is a daunting task and constraint-based languages usually ...
详细信息
ISBN:
(纸本)9781450372497
Search strategies are crucial to efficiently solve constraint satisfaction problems. However, programming search strategies in the existing constraint solvers is a daunting task and constraint-based languages usually have compositionality issues. We propose space-time programming, a paradigm extending the synchronous language Esterel and timed concurrent constraint programming with backtracking, for creating and composing search strategies. In this formalism, the search strategies are composed in the same way as we compose concurrent processes. Our contributions include the design and behavioral semantics of spacetime programming, and the proofs that spacetime programs are deterministic, reactive and extensive functions. Moreover, spacetime programming provides a bridge between the theoretical foundations of constraint-based concurrency and the practical aspects of constraint solving. We developed a prototype of the compiler that produces search strategies with a small overhead compared to the hard-coded ones.
暂无评论