Search

This paper presents a comprehensive approach for planning for teams of heterogeneous robots with different capabilities and the transportation of resources. We use Capability Temporal Logic (CaTL), a formal language that helps express tasks involving robots with multiple capabilities with spatial, temporal, and logical constraints. We extend CaTL to also capture resource constraints, where resources can be divisible and indivisible, for instance, sand and bricks, respectively. Robots transport resources using various storage types, such as uniform (shared storage among resources) and compartmental (individual storage per resource). Robots' resource transportation capacity is defined based on resource type and robot class. Robot and resource dynamics and the CaTL mission are jointly encoded in a Mixed Integer Linear Programming (MILP), which maximizes disjoint robot and resource robustness while minimizing spurious movement of both. We propose a multi-robustness approach for Multi-Class Signal Temporal Logic (mcSTL), allowing for generalized quantitative semantics across multiple predicate classes. Thus, we compute availability robustness scores for robots and resources separately. Finally, we conduct multiple experiments demonstrating functionality and time performance by varying resources and storage types. [ABSTRACT FROM AUTHOR]

The development of smart contracts remains in its early stages, with significant differences in underlying programming languages and application platforms resulting in a lack of standardization. This lack of standardization increases the susceptibility to vulnerabilities and associated financial losses. To address security vulnerabilities in smart contracts on the Ethereum blockchain platform, this paper proposes a security audit method based on formal verification. The method integrates an input module, static analysis module, formal verification module, analog execution module, and report and recommendation module, which can accurately discover the security vulnerabilities and logical flaws of smart contracts through formal verification and other analysis techniques, thus realizing correctness detection. During the experiment, the method detects 8 types of common vulnerabilities in 148 smart contracts and marks 21 smart contracts with vulnerabilities. After manual review and analysis, it is found that 17 of these 21 marked smart contracts do have security vulnerabilities. The experimental results show that the proposed method can accurately detect security vulnerabilities and logic flaws in smart contracts through formal verification and other analysis techniques before smart contracts are deployed, thus significantly improving the security of smart contracts and reducing the economic losses that may be caused by code defects. [ABSTRACT FROM AUTHOR]

NeVer2 is an open-source, cross-platform tool aimed at designing, training, and verifying neural networks. It seamlessly integrates popular learning libraries with our verification backend, offering their functionalities via a graphical interface. Users can design the structure of a neural network by intuitively arranging blocks on a canvas. Subsequently, network training involves specifying dataset sources and hyperparameters through dialog boxes. After training, the verification process entails two steps: (i) incorporating input preconditions and output postconditions via dedicated blocks, and (ii) initiating verification with a simple "push-button" action. To our knowledge, there is currently no other publicly available tool that encompasses all these features. In this paper, we present a comprehensive description of NeVer2, illustrating its complete integration of design, training, and verification through examples. Additionally, we conduct experimental analyses on various verification benchmarks to illustrate the trade-off between completeness and computability using different algorithms. We also include a comparison with state-of-the-art tools such as α , β -CROWN and NNV for reference. [ABSTRACT FROM AUTHOR]

Introduction: Acute pancreatitis (AP) is a common disease, and several scores aim to assess its prognosis. Our study aims to automatically recognize mild AP from computed tomography (CT) images in patients with acute abdominal pain but uncertain diagnosis from clinical and serological data through Radiomic model based on formal methods (FMs). Methods: We retrospectively reviewed the CT scans acquired with Dual Source 256-slice CT scanner (Somatom Definition Flash; Siemens Healthineers, Erlangen, Germany) of 80 patients admitted to the radiology unit of Antonio Cardarelli hospital (Naples) with acute abdominal pain. Patients were divided into 2 groups: 40 underwent showed a healthy pancreatic gland, and 40 affected by four different grades (CTSI 0, 1, 2, 3) of mild pancreatitis at CT without clear clinical presentation or biochemical findings. Segmentation was manually performed. Radiologists identified 6 patients with a high expression of diseases (CTSI 3) to formulate a formal property (Rule) to detect AP in the testing set automatically. Once the rule was formulated, and Model Checker classified 70 patients into "healthy" or "unhealthy". Results: The model achieved: accuracy 81%, precision 78% and recall 81%. Combining FMs results with radiologists agreement, and applying the mode in clinical practice, the global accuracy would have been 100%. Conclusions: Our model was reliable to automatically detect mild AP at primary diagnosis even in uncertain presentation and it will be tested prospectively in clinical practice. [ABSTRACT FROM AUTHOR]

The Signal is an end-to-end encrypted communication protocol composed of a double ratchet (DR) protocol and an extended triple Diffie-Hellman (X3DH) protocol. Its complex ratchet structure and the characteristics of protocol composition make it challenging to realize formal analysis. A formal analysis method based on logic of events theory (LoET) is proposed to conduct a security analysis of the Signal protocol. The method includes inference rules with key relation and key chain as the core to realize the formal analysis of ratchet structure, and the inference relation between sub-protocols is established by putting forward the composition theorem. The proposed method achieves a formal analysis of Signal, revealing that it does not satisfy a strong authentication property during the X3DH phase. The results show that the LoET-based method can be effectively applied in the formal analysis of Signal protocols, thus promoting the application and development of these protocols with ratchet structure and composition properties. [ABSTRACT FROM AUTHOR]

Petri nets are a graphical notation for describing a class of discrete event dynamic systems whose behaviours are characterised by concurrency, synchronisation, mutual exclusion and conflict. They have been used over the years for the modelling of various distributed systems applications. With the advent of pervasive systems and the Internet of Things, the Calculus of Context-aware Ambients (CCA) has emerged as a suitable formal notation for analysing the behaviours of these systems. In this paper, we are interested in comparing the expressive power of Petri nets to that of CCA. That is, can the class of systems represented by Petri nets be modelled in CCA? To answer this question, an algorithm is proposed that maps any Petri net onto a CCA process. We prove that a Petri net and its corresponding CCA process are behavioural equivalent. It follows that CCA is at least as expressive as Petri nets, i.e., any system that can be specified in Petri nets can also be specified in CCA. Moreover, tools developed for CCA can also be used to analyse the behaviours of Petri nets. [ABSTRACT FROM AUTHOR]

Over the past few years, neural networks have started penetrating safety critical systems to make decisions as, for example, in robots, rockets, and autonomous driving cars. Neural networks based on floating-point arithmetic are very time and memory consuming, which are not compatible with embedded systems known to have limited resources. They are also very sensitive to the precision in which they have been trained, so changing this precision generally degrades the quality of their answers. To deal with that, we introduce a new technique to generate a fixed-point code for a trained neural network. This technique is based on fixed-point arithmetic with mixed-precision. This arithmetic is based on integer operations only, which are compatible with small memory devices. The obtained neural network has the same behavior as the initial one (based on the floating-point arithmetic) up to an error threshold defined by the user. The experimental results show the efficiency of our tool SyFix in terms of memory saved and the accuracy of the computations. [ABSTRACT FROM AUTHOR]

Abstract The Signal is an end-to-end encrypted communication protocol composed of a double ratchet (DR) protocol and an extended triple Diffie-Hellman (X3DH) protocol. Its complex ratchet structure and the characteristics of protocol composition make it challenging to realize formal analysis. A formal analysis method based on logic of events theory (LoET) is proposed to conduct a security analysis of the Signal protocol. The method includes inference rules with key relation and key chain as the core to realize the formal analysis of ratchet structure, and the inference relation between sub-protocols is established by putting forward the composition theorem. The proposed method achieves a formal analysis of Signal, revealing that it does not satisfy a strong authentication property during the X3DH phase. The results show that the LoET-based method can be effectively applied in the formal analysis of Signal protocols, thus promoting the application and development of these protocols with ratchet structure and composition properties.

Abstract Adhesive Capsulitis of the shoulder is a painful pathology limiting shoulder movements, commonly known as “Frozen Shoulder”. Since this pathology limits movement, it is important to make an early diagnosis. Diagnosing capsulitis relies on clinical assessment, although diagnostic imaging, such as Magnetic Resonance Imaging, can provide predictive or supportive information for specific characteristic signs. However, its diagnosis is not so simple nor so immediate, indeed it remains a difficult topic for many general radiologists and expert musculoskeletal radiologists. This study aims to investigate whether it is possible to use disease signs within a medical image to automatically diagnose Adhesive Capsulitis. To this purpose, we propose an automatic Model Checking-based approach to quickly diagnose the Adhesive Capsulitis taking as input the radiomic feature values from the medical images. Furthermore, we compare the performance achieved by our method with diagnostic results obtained by professional radiologists with different levels of experience. To the best of our knowledge, this is the first method for the automatic diagnosis of Adhesive Capsulitis of the Shoulder.

Adhesive Capsulitis of the shoulder is a painful pathology limiting shoulder movements, commonly known as "Frozen Shoulder". Since this pathology limits movement, it is important to make an early diagnosis. Diagnosing capsulitis relies on clinical assessment, although diagnostic imaging, such as Magnetic Resonance Imaging, can provide predictive or supportive information for specific characteristic signs. However, its diagnosis is not so simple nor so immediate, indeed it remains a difficult topic for many general radiologists and expert musculoskeletal radiologists. This study aims to investigate whether it is possible to use disease signs within a medical image to automatically diagnose Adhesive Capsulitis. To this purpose, we propose an automatic Model Checking-based approach to quickly diagnose the Adhesive Capsulitis taking as input the radiomic feature values from the medical images. Furthermore, we compare the performance achieved by our method with diagnostic results obtained by professional radiologists with different levels of experience. To the best of our knowledge, this is the first method for the automatic diagnosis of Adhesive Capsulitis of the Shoulder. [ABSTRACT FROM AUTHOR]

Software verification aims to prove that a program satisfies some given properties for all its possible executions. Software evolved incredibly fast during the last century, exposing several challenges to this scientific discipline. The goal of the "Challenges of Software Verification Symposium" is to monitor the state-of-the-art in this field. In this article, we will present the evolution of software from its inception in the 1940s to today's applications, how this exposed new challenges to software verification, and what this discipline achieved. We will then discuss how this chapter covers most of the current open challenges, the possible future software developments, and what challenges this will raise in software verification. [ABSTRACT FROM AUTHOR]

The widespread use of advanced driver assistance systems in modern vehicles, together with their integration with the Internet and other road nodes, has made vehicle more vulnerable to cyber-attacks. To address these risks, the automotive industry is increasingly focusing on the development of security solutions: formal methods and software verification techniques, which have been successfully applied to a number of safety-critical systems, could be a promising approach in the automotive area. In this work, we concentrate on in-vehicle communications, provided by many Electronic Control Units (ECUs) that work together thanks to serial protocols such as Controller Area Network (CAN). However, increasing connectivity exposes the internal network to a variety of cyber-risks. Our aim is to formally verify the AUTOSAR-based Basic Software module called CINNAMON, designed to ensure confidentiality, integrity, and authentication at the same time for traffic exchanged over CAN protocol. More precisely, it adds confidentiality guarantees to the Secure Onboard Communication (SecOC) module. We formally analyze CINNAMON with the verification tool Tamarin. Our analysis shows that CINNAMON could be an effective security solution, as it can ensure the desired properties, in particular, confidentiality in a send-receive scenario between two ECUs. Finally, we describe a potential application scenario. [ABSTRACT FROM AUTHOR]

A composite smart contract can execute smart contracts that may belong to other owners or companies through external calls, bringing more security challenges to blockchain applications. Traditional static verification methods are inadequate for analyzing the dynamic execution of these contracts, resulting in misjudgment and omission issues. Therefore, this paper proposes a model checking approach based on dynamic behavior that verifies the security and business logic of composite smart contracts. Utilizing automata, the method models contracts, users, attackers, and extracts properties, focusing on six types of common security vulnerabilities. A thorough case study and experimental evaluation demonstrate the method's efficiency in identifying vulnerabilities and ensuring alignment with business requirements. The UPPAAL tool is employed for comprehensive verification, proving its effectiveness in enhancing smart contract security. [ABSTRACT FROM AUTHOR]

In the robustness verification of neural networks, formal methods have been used to give deterministic guarantees for neural networks. However, recent studies have found that the verification method of single-neuron relaxation in this field has an inherent convex barrier that affects its verification capability. To address this problem, we propose a new verification method by combining dual-neuron relaxation and linear programming. This method captures the dependencies between different neurons in the same hidden layer by adding a two-neuron joint constraint to the linear programming model, thus overcoming the convex barrier problem caused by relaxation for only a single neuron. Our method avoids the combination of exponential inequality constraints and can be computed in polynomial time. Experimental results show that we can obtain tighter bounds and achieve more accurate verification than single-neuron relaxation methods. [ABSTRACT FROM AUTHOR]

This paper presents a control strategy synthesis method for dynamical systems with differential constraints, emphasizing the prioritization of specific rules. Special attention is given to scenarios where not all rules can be simultaneously satisfied to complete a given task, necessitating decisions on the extent to which each rule is satisfied, including which rules must be upheld or disregarded. We propose a learning-based Model Predictive Control (MPC) method designed to address these challenges. Our approach integrates a learning method with a traditional control scheme, enabling the controller to emulate human expert behavior. Rules are represented as Signal Temporal Logic (STL) formulas. A robustness margin, quantifying the degree of rule satisfaction, is learned from expert demonstrations using a Conditional Variational Autoencoder (CVAE). This learned margin is then applied in the MPC process to guide the prioritization or exclusion of rules. In a track driving simulation, our method demonstrates the ability to generate behavior resembling that of human experts and effectively manage rule-based dilemmas. [ABSTRACT FROM AUTHOR]

This paper presents a modern method of detecting unstable states in ladder programs. Ladder programs are standard formalism used in a wide range of automation applications, especially in railway signaling systems. This formalism is characterized by a lack of explicit program control flow, which can result in the presence of unstable states. A state is unstable, if it leads to cyclic state transitions not anticipated by the designer (loop). The presence of unstable states is one of the possible program defects. This kind of defect is hard to detect and can harm program reliability. The presence of unstable states can be verified with formal methods by the construction of a ladder program model and analysis of its properties. The authors propose a method of static analysis of ladder programs by translating them into predicate logic formulas and construction of formulas expression stability of the program, which can be analyzed with SAT solvers. The presented method allows for automatic verification of the presence of unstable states in the program. The method is conservative (i.e., it concludes that the program has no unstable states only if it is the case). Preliminary experiments performed by authors with a Z3 solver indicate that the method is suitable for use for verification of interlocking programs of computer-based railway signaling systems. [ABSTRACT FROM AUTHOR]

The visual modeling language UML embodies object-oriented design principles. It provides a standard way to visualize the design of a system. It exploits a rich set of well-defined graphical notations for creating abstract models. However, the power of UML is lessened through partially specified formal semantics. Indeed, UML notations are semi-formal and do not lead to fully formalized and executable semantics. Fortunately, UML diagrams are prone to early formalization. Formal methods are a valuable tool that can help overcome the UML constructs' shortage of firm semantics. It is a powerful way to ascribe precise semantics to the graphical notations used in UML diagrams and models. Our work aims to support the semantics of the UML Interaction Overview Diagram. It introduces an approach to leveraging the strengths of the Maude Rewriting Logic language as a formal specification language. The proposal relies on a model-driven engineering approach. It aims to automate the UML Interaction Overview Diagram's mapping to a Maude language specification. The Maude language and its linked tools, including the Maude Model Checker, are used to analyze and verify the resulting Maude specification. Finally, an application example shows the feasibility and benefits of the proposed approach. [ABSTRACT FROM AUTHOR]

The inordinate financial cost of mitigating post-production cybersecurity vulnerabilities in cyber- physical systems (CPS) is forcing the industry to rethink systems design cycles: greater attention is being given to the design phase - with the goal of reducing the attack surface of systems at an early stage (i.e., before silicon tape out). Fortunately, formal methods have advanced to the point that they can address such needs and contribute towards achieving security certification. However, new methods and tools focusing on industrial scalability and usability for systems engineers are required. In this ongoing research paper, we describe a framework that will help systems engineers to: a) design cyber-assured CPS using a Model Based Engineering (MBE) approach; b) formally map security requirements to different hardware and software blocks in the model; and c) formally verify security requirements. Based on the nature of each requirement, our framework collects formal correctness evidence from different tools: while high-level architectural properties are suitable for a contract- or ontology-based reasoning, more complex properties with rich semantics require the use of model checking or theorem proving techniques. [ABSTRACT FROM AUTHOR]

In this article, we present an approach to the ABZ 2020 case study that differs from those usually presented at ABZ: Rather than using a (correct-by-construction) approach following a formal method, we use C for a low-level implementation instead. We strictly adhere to test-driven development for validation, and only afterwards apply model checking using CBMC for verification. While the approach has several benefits compared to the more rigorous approaches, it also provides less mathematical clarity and overall less thorough verification. In consequence, our realization of the ABZ case study serves as a baseline reference for comparison, allowing to assess the benefit provided by the various formal modeling languages, methods and tools. [ABSTRACT FROM AUTHOR]

System requirements can occasionally be ill-defined and difficult to define. In this case, graphic representation of the system created using semi-formal modelling is advantageous. A smart power grid, for example, includes numerous important needs and function points. We can portray the system functionalities graphically to better grasp the requirements before moving forward with the formal definition. Though, graphic models like Unified Modeling Language (UML) have ambiguity issues as they work on predefined rules. On the other hand, the formal technique uses the correct-by-construction method to guarantee the system's dependability. The formal technique is based on well-practiced mathematical notation. In this article, a smart grid (SG) system based on blockchain (BC) is formally modelled and verified. The system requirements are validated using the formal modelling technique Event-B. To illustrate the system, we first suggest various graphical notations. After that, the notations are translated into a JSON (JavaScript Object Notation) format. Java executable codes are generated in order to validate the JSON schemas. The graphical model is then translated into Event-B specifications and validated using RODIN, a standard tool support. [ABSTRACT FROM AUTHOR]

Markov chain analysis is a key technique in formal verification. A practical obstacle is that all probabilities in Markov models need to be known. However, system quantities such as failure rates or packet loss ratios, etc. are often not—or only partially—known. This motivates considering parametric models with transitions labeled with functions over parameters. Whereas traditional Markov chain analysis relies on a single, fixed set of probabilities, analysing parametric Markov models focuses on synthesising parameter values that establish a given safety or performance specification φ . Examples are: what component failure rates ensure the probability of a system breakdown to be below 0.00000001?, or which failure rates maximise the performance, for instance the throughput, of the system? This paper presents various analysis algorithms for parametric discrete-time Markov chains and Markov decision processes. We focus on three problems: (a) do all parameter values within a given region satisfy φ ?, (b) which regions satisfy φ and which ones do not?, and (c) an approximate version of (b) focusing on covering a large fraction of all possible parameter values. We give a detailed account of the various algorithms, present a software tool realising these techniques, and report on an extensive experimental evaluation on benchmarks that span a wide range of applications. [ABSTRACT FROM AUTHOR]

Over the last several decades, static and dynamic program analysis techniques have received widespread attention. Their application to mainstream programming languages always requires extending theories and finding practical solutions. This special issue of Software Tools for Technology Transfer presents novel theoretical directions and practical applications of these techniques. The papers in this special issue are extended versions of selected workshop papers from the proceedings of the 12th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis (SOAP'23). [ABSTRACT FROM AUTHOR]