Abstract This paper introduces a formal definition of a Cyber-Physical System (CPS) in the spirit of the CPS Framework proposed by the National Institute of Standards and Technology (NIST). It shows that using this definition, various problems related to concerns in a CPS can be precisely formalized and implemented using Answer Set Programming (ASP). These include problems related to the dependency or conflicts between concerns, how to mitigate an issue, and what the most suitable mitigation strategy for a given issue would be. It then shows how ASP can be used to develop an implementation that addresses the aforementioned problems. The paper concludes with a discussion of the potentials of the proposed methodologies.

By 2030, over a half trillion devices will be connected to the internet. With so many devices providing a wide range of features, there is a need for a framework for innovation and reuse of Internet of Things (IoT) and Cyber-Physical Systems (CPS) capabilities. Such framework should facilitate the composition of capabilities and provide stakeholders means to reliably model and verify compositions. An IoT and CPS Composition Framework (ICCF) is proposed to achieve this goal. ICCF is based on the NIST CPS framework composition guidelines, intuitive composition semantics inspired from the mPlane protocol, and strong formal verification capabilities of the Temporal Logic of Actions (TLA) formal descriptors and tools. This paper demonstrates why such framework, semantics, and formal specification and verification components form a powerful and intuitive composition framework that satisfies different stakeholders concerns. To achieve this purpose, semantics and formal specification of the composition algebra were provided, a well-being composite capability within a smart building was specified, its prototype model in a formal verification tool was run, an analysis of the results of symbolic execution quantitatively and qualitatively was performed, and assessment of the trustworthiness of the composition was done. Lastly, implementation details were provided and proposed extensions to other domains such as smart transportation and smart health were discussed.

Formal specifications on temporal behavior of Cyber-Physical Systems (CPS) is essential for verification of performance and safety. Existing solutions for verifying the satisfaction of temporal constraints on a CPS are compute and resource intensive since they require buffering signals from the CPS prior to constraint checking. We present an online approach, based on Timestamp Temporal Logic (TTL), for monitoring the timing constraints in CPS. The approach reduces the computation and memory requirements by processing the timestamps of pertinent events reducing the need to capture the full data set from the signal sampling. The signal buffer size bears a geometric relationship to the dimension of the signal vector, the time interval being considered, and the sampling resolution. Since monitoring logic is typically implemented on Field Programmable Gate Arrays (FPGAs) for efficient monitoring of multiple signals simultaneously, the space required to store the buffered data becomes the limiting resource. The monitoring logic, for the timing constraints on the Flying Paster (a printing application requiring synchronization between two motors), is illustrated in this paper to demonstrate a geometric reduction in memory and computational resources in the realization of an online monitor.

Smart Cities are complex environments, comprising diverse cyber-physical systems (CPS), including Internet of Things (IoT). Smart Cities pose challenges of scale, integration, interoperability, sophisticated processes, governance, human elements. Trustworthiness (including safety, security, privacy, reliability and resilience) of these Smart Cities and their elements is critical for gaining broad adoption by the leadership and the public. The US National Institute of Standards and Technology (NIST) and its government, university and industry collaborators, have developed an approach to reasoning about CPS/IoT trustworthiness that can be applied to Smart Cities. The approach uses ontology and reasoning techniques, is based on the NIST Framework for Cyber-Physical Systems, and demonstrates how a greater understanding of the interdependencies between concerns (elements of the CPS Framework) can be achieved. To demonstrate capabilities of the approach in a short paper, we develop a public safety use case and show how reasoning can be used to analyze and validate the trustworthiness of elements of Smart Cities.

Time is a foundational aspect of Cyber-Physical Systems (CPS). Correct time and timing of system events are critical to optimized responsiveness to the environment, in terms of timeliness, accuracy, and precision in the knowledge, measurement, prediction, and control of CPS behavior. However, both the specification and verification of timing requirements of the CPS are typically done in an ad-hoc manner. While feasible, the system can become costly and difficult to analyze and maintain, and the process of implementing and verifying correct timing behavior can be error-prone. Towards the development of a verification testbed for testing timing behavior in tools and platforms with explicit time support, this paper first describes a way to express the various kinds of timing constraints in distributed CPS. Then, we outline the design and initial implementation of a distributed testbed to verify the timing of a distributed CPS analytically through a systematic framework. Finally, we illustrate the use of the verified timing testbed on two distributed CPS case studies.

In order to test the performance and verify the correctness of Cyber-Physical Systems (CPS), the timing constraints on the system behavior must be met. Signal Temporal Logic (STL) can efficiently and succinctly capture the timing constraints of a given system model. However, many timing constraints on CPS are more naturally expressed in terms of events on signals. While it is possible to specify event-based timing constraints in STL, such statements can quickly become long and arcane in even simple systems. Timing constraints for CPS, which can be large and complex systems, are often associated with tolerances, the expression of which can make the timing constraints even more cumbersome using STL. This paper proposes a new logic, Timestamp Temporal Logic (TTL), to provide a definitional extension of STL that more intuitively expresses the timing constraints of distributed CPS. TTL also allows for a more natural expression of timing tolerances. Additionally, this paper outlines a methodology to automatically generate logic code and programs to monitor the expressed timing constraints. Since our TTL monitoring logic evaluates the timing constraints using only the timestamps of the required events on the signal, the TTL monitoring logic has significantly less memory footprint when compared to traditional STL monitoring logic, which stores the signal value at the required sampling frequency. The key contribution of this paper is a scalable approach for online monitoring of the timing constraints. We demonstrate the capabilities of TTL and our methodology for online monitoring of TTL constraints on two case studies: 1) Synchronization and phase control of two generators and, 2) Simultaneous image capture using distributed cameras for 3D image reconstruction.

The question of the limits of recursive enumerability was first formulated by Sacks (1980) and investigated further in Sacks (198?). E-recursion or “set recursion”, as a natural generalization of Kleene recursion in normal objects of finite type, was introduced by Normann (1978) in order to facilitate the study of the degrees of functionals. We shall extend the work of Sacks on the question of how definable is the E-closure of an ordinal α (written E(α)). We write gc(κ) to denote the largest τ < κ such that Lκ ⊨ “τ is a cardinal” and cf (τ) for τ ∈ ON to denote the cofinality of τ. In §1 we give the basic definitions and state the results of Silver and Friedman (1980) used by Sacks to show that if E(α) = Lκ and is not Σ1-admissible and then P(gc(κ)) ∩ Lκ is indexical on Lκ and hence RE. We show in this case first that P(gc(κ)) ∩ Lκ indexical implies that Lκ is indexical (and hence RE). In §2 we introduce the notion of a “nonstandard stage comparison” and use it to extend the definability result of §1 to show that this Lκ is in fact REC. Finally we remark that E(α) is indexical if and only if E(α) is RE.