More Like this

1. Connecting Higher-Order Separation Logic to a First-Order Outside World

   https://doi.org/10.1007/978-3-030-44914-8_16  

   William Mansky, Wolf Honoré ( April 2020 , Programming Languages and Systems. ESOP 2020)

   Separation logic is a useful tool for proving the correctness of programs that manipulate memory, especially when the model of memory includes higher-order state: Step-indexing, predicates in the heap, and higher-order ghost state have been used to reason about function pointers, data structure invariants, and complex concurrency patterns. On the other hand, the behavior of system features (e.g., operating systems) and the external world (e.g., communication between components) is usually specified using first-order formalisms. In principle, the soundness theorem of a separation logic is its interface with first-order theorems, but the soundness theorem may implicitly make assumptions about how other components are specified, limiting its use. In this paper, we show how to extend the higher-order separation logic of the Verified Software Toolchain to interface with a first-order verified operating system, in this case CertiKOS, that mediates its interaction with the outside world. The resulting system allows us to prove the correctness of C programs in separation logic based on the semantics of system calls implemented in CertiKOS. It also demonstrates that the combination of interaction trees + CompCert memories serves well as a lingua franca to interface and compose two quite different styles of program verification. 

   more » « less
2. Founded semantics and constraint semantics of logic rules

   https://doi.org/10.1093/logcom/exaa056  

   Liu, Yanhong A ; Stoller, Scott D ( October 2020 , Journal of Logic and Computation)

   null (Ed.)

   Abstract Logic rules and inference are fundamental in computer science and have been studied extensively. However, prior semantics of logic languages can have subtle implications and can disagree significantly, on even very simple programs, including in attempting to solve the well-known Russell’s paradox. These semantics are often non-intuitive and hard-to-understand when unrestricted negation is used in recursion. This paper describes a simple new semantics for logic rules, founded semantics, and its straightforward extension to another simple new semantics, constraint semantics, that unify the core of different prior semantics. The new semantics support unrestricted negation, as well as unrestricted existential and universal quantifications. They are uniquely expressive and intuitive by allowing assumptions about the predicates, rules and reasoning to be specified explicitly, as simple and precise binary choices. They are completely declarative and relate cleanly to prior semantics. In addition, founded semantics can be computed in linear time in the size of the ground program. 

   more » « less
3. Interval Signal Temporal Logic From Natural Inclusion Functions

   https://doi.org/10.1109/LCSYS.2023.3337744  

   Baird, Luke ; Harapanahalli, Akash ; Coogan, Samuel ( January 2023 , IEEE Control Systems Letters)

   We propose an interval extension of Signal Temporal Logic (STL) called Interval Signal Temporal Logic (I-STL). Given an STL formula, we consider an interval inclusion function for each of its predicates. Then, we use minimal inclusion functions for the min and max functions to recursively build an interval robustness that is a natural inclusion function for the robustness of the original STL formula. The resulting interval semantics accommodate, for example, uncertain signals modeled as a signal of intervals and uncertain predicates modeled with appropriate inclusion functions. In many cases, verification or synthesis algorithms developed for STL apply to I-STL with minimal theoretic and algorithmic changes, and existing code can be readily extended using interval arithmetic packages at negligible computational expense. To demonstrate I-STL, we present an example of offline monitoring from an uncertain signal trace obtained from a hardware experiment and an example of robust online control synthesis enforcing an STL formula with uncertain predicates. 

   more » « less
4. A new schema of logic representation and reasoning for automated building code compliance checking.

   Yang, F. ; Zhang, J. ; Chen, Y. ; and Debs, L. ( January 2022 , Proceedings of the GPEA Polytechnic Summit 2022: Session Papers)

   Steinmetz, A. (Ed.)

   Manual building code compliance checking is a time-consuming, labor-intensive and error-prone process. Automated logic-based reasoning is an essential step in the automation of this process. There have been previous studies using logic programming languages for automated logic-based reasoning to support automated compliance checking (ACC) of building designs with building codes. As a high-performance implementation of the standard logic programming language, B-Prolog was widely used in these studies. However, due to the support of dynamic predicates and user-defined operators, the predicates’ functions vary according to different user definitions; therefore, B-Prolog is sometimes not reliable for building code reasoning. As a more expressive, scalable, and reliable alterative to B-Prolog, Picat, a logic-based multi-paradigm programming language, provides a new and potentially more powerful platform for automated logic-based reasoning in ACC. To explore the potential value of Picat in ACC, in this study, the authors compared Picat and B-Prolog performance in automatically checking 20 requirement rules in the 2015 International Building Code. The experimental results showed that the automated checking for building codes in the B-Prolog version was faster than that in the Picat version, whereas the Picat version was more reliable than the B-Prolog version. This could be the result of B-Prolog using unifica-tion and Picat using pattern matching for indexing rules. More potential applications of Picat in ACC domain need further research. Furthermore, this schema could be used in the teaching of ACC to graduate construction students, illustrating the need to focus on the reliability, predictability and scalability of the process, in order to provide a practical solution to improving code compliance checking processes. 

   more » « less
5. TeLEx: learning signal temporal logic from positive examples using tightness metric

   https://doi.org/10.1007/s10703-019-00332-1  

   Jha, Susmit ; Tiwari, Ashish ; Seshia, Sanjit A. ; Sahai, Tuhin ; Shankar, Natarajan ( April 2019 , Formal Methods in System Design)

   We propose a novel passive learning approach, TeLex, to infer signal temporal logic (STL) formulas that characterize the behavior of a dynamical system using only observed signal traces of the system. First, we present a template-driven learning approach that requires two inputs: a set of observed traces and a template STL formula. The unknown parameters in the template can include time-bounds of the temporal operators, as well as the thresholds in the inequality predicates. TeLEx finds the value of the unknown parameters such that the synthesized STL property is satisfied by all the provided traces and it is tight. This requirement of tightness is essential to generating interesting properties when only positive examples are provided and there is no option to actively query the dynamical system to discover the boundaries of legal behavior. We propose a novel quantitative semantics for satisfaction of STL properties which enables TeLEx to learn tight STL properties without multidimensional optimization. The proposed new metric is also smooth. This is critical to enable the use of gradient-based numerical optimization engines and it produces a 30x to 100x speed-up with respect to the state-of-art gradient-free optimization. Second, we present a novel technique for automatically learning the structure of the STL formula by incrementally constructing more complex formula guided by the robustness metric of subformula. We demonstrate the effectiveness of the overall approach for learning STL formulas from only positive examples on a set of synthetic and real-world benchmarks. 

   more » « less