Search

Reusability is a central concept of Web services as it allows for the construction of composite Web services at lower cost/effort. Web services offer diverse functional capabilities ({\it e.g.,} ticket purchase, hotel booking) and inherent transactional properties. However, due to the lack of an explicit and formal description of these functional and transactional perspectives, the correctness of the transactional reliability and functional properties cannot be verified. The composite Web service reliability is computed using a set of transactional requirements defined by designers throughout the Accepted Termination States (ATS) concept. The main objective of this paper is to introduce a formal model of the Web service configuration and its correctness requirements that permit to ensure the correct Web service execution from functional and transactional points of view. For that purpose, we developed a Correct Configuration Model for Transactional Composite Services (CCM4TCS) using the \eventB method. This model is used to formally validate the consistency of composite Web service configuration's properties and requirements. It allows also to check the correctness of ATS constraints that we use as reliability parameters. The correctness and the validation of our model are ensured by discharging proof obligations and by animating the specification using the ProB model-checker

This article proposes a new logic synthesis and verification paradigm based on circuit simulation. In this paradigm, high quality, expressive simulation patterns are pregenerated to be reused in multiple runs of optimization and verification algorithms, resulting in reduced time-consuming Boolean computations such as satisfiability (SAT) solving. Methods to generate expressive simulation patterns are presented and compared, and a bit-packing technique to compress them is integrated into the implementation. The generated patterns are shown to be reusable across different algorithms and after network function modifications. A logic synthesis algorithm, Boolean resubstitution, and a verification algorithm, combinational equivalence checking, are two examples of using this paradigm. In simulation-guided Boolean resubstitution, simulation patterns are used for efficient filtering of optimization choices, leading to a lower cost in expanding the search space. By adopting the proposed paradigm, we achieve a 5.9% reduction in the number of AIG nodes, compared to 3.7% by a state-of-the-art resubstitution algorithm, within comparable runtime. In simulation-guided equivalence checking, the number of SAT solver calls is reduced by 9.5% with the use of the expressive simulation patterns accumulated in earlier logic synthesis stages.

An increase in digitization is giving rise to cybercrimes. The existing network protocols are insufficient for collecting the required digital evidence of cybercrime, which eventually makes the process of forensic investigation difficult. In the current scenario of network forensics, the investigator with current capabilities can reach only up to the ISP. This is not primary evidence. Currently, available tools work only at the network layer. In this work, we propose a protocol that ensures tracking up to the true source by collecting beforehand forensically sound evidence. The proposed protocol can collect target data from the device in the form of a device fingerprint with the help of an agent process. The proposed methodology will help in proving non-repudiation, which is a well-known challenge in forensic cases. The fingerprint evidence generated by the proposed method has the capability of not getting obsolete even if the criminal tries to destroy evidence. The fingerprinting technique deployed uses a hash tree and generates evidence in such a way that this fingerprint can act as legal evidence. The security validation of the proposed system is done using the BAN logic. Formal verification is performed using the AVISPA tool. The system has been implemented as a prototype and hosted on AWS.

Formal verification of integer multipliers is one of the important but challenging problems in the verification community. Recently, the methods based on Symbolic Computer Algebra (SCA) have shown very good results in comparison to all other existing proof techniques. However, when it comes to verification of huge and structurally complex multipliers they completely fail as an explosion happens in the number of monomials. The reason for this explosion is the generation of redundant monomials known as vanishing monomials. This paper introduces the SCA-based approach that combines reverse engineering and local vanishing removal to verify large and non-trivial multipliers. For our approach, we first come up with a theory for the origin of vanishing monomials, i.e. we prove that the gates/nodes where both outputs of Half Adders (HAs) converge are the origins of vanishing monomials. Then, we propose a dedicated reverse engineering technique to identify atomic blocks including HAs. The identified HAs are the basis for detecting converging cones and locally removing vanishing monomials which finally results in a vanishing-free global backward rewriting. The efficiency of is demonstrated using an extensive set of multipliers with up to several million gates.

The Internet-of-Things (IoT) scenarios commonly present security and privacy concerns, either due to the processing constraints of devices or the employment of external servers to process and store data, for instance, in cloud-based IoT applications. In this sense, to protect data and decrease user distrust in external entities, security technologies are of utmost importance. Trusted execution environments (TEEs), which process data in an isolated and protected region of memory, are among these technologies. We focus on a trusted architecture solution based on the use of TEEs and the application of authentication, authorization, and encryption mechanisms to protect data in IoT applications. We specified the trusted IoT architecture (TIoTA) using hierarchical colored Petri nets, and performed simulations and model checking of key security properties related to desired and prohibited behaviors, enabling model-based testing. This article enhances the state of the art by providing project artifacts (e.g., executable and parametric models) for correctly implementing the TIoTA and by presenting evidence that the usage of the architecture can improve security and privacy.

As software becomes more complex and assumes an even greater role in our lives, formal verification is set to become the gold standard in securing software systems into the future, since it can guarantee the absence of errors and entire classes of attack. Recent advances in formal verification are being used to secure everything from unmanned drones to the internet. At the same time, the usable security research community has made huge progress in improving the usability of security products and end-users comprehension of security issues. However, there have been no human-centered studies focused on the impact of formal verification on the use and adoption of formally verified software products. We propose a research agenda to fill this gap and to contribute with the first collection of studies on people's mental models on formal verification and associated security and privacy guarantees and threats. The proposed research has the potential to increase the adoption of more secure products and it can be directly used by the security and formal methods communities to create more effective and secure software tools., Comment: In Proceedings AppFM 2021, arXiv:2111.07538

Studying biological systems is a difficult but important task. Traditional methods include laboratory experimentation and computer simulations. However, often researchers need to explore important but potentially rare events that are not easily observed or simulated. We use UPPAAL-SMC, a formal verification tool to support a methodology that allows modelling biological systems, specify events and conditions that we want to analyze, and to explore system executions using controlled simulations. We also describe an efficient way to reproduce laboratory experiments in silico. Unlike traditional simulations, we are able to guide the experiment to explore special events and conditions expressing these conditions in temporal logic formulas. We have applied this methodology to create a more detailed model of Palytoxin-induced Na + /K + pump channels than was previously possible. Moreover, we have reproduced experimental protocols and their associated electrophysiological recordings, which has not been done in previous works. As a consequence, we have been able to propose a new diprotomeric model for the PTX-pump complex and study its behaviour. The use of our methodology enabled us to reduce the effort and time to perform this research. It can be used to model other complex biological systems, potentially increasing the productivity of such studies.

Closures are a language feature supported by many mainstream languages, combining the ability to package up references to code blocks with the possibility of capturing state from the environment of the closure's declaration. Closures are powerful, but complicate understanding and formal reasoning, especially when closure invocations may mutate objects reachable from the captured state or from closure arguments. This paper presents a novel technique for the modular specification and verification of closure-manipulating code in Rust. Our technique combines Rust's type system guarantees and novel specification features to enable formal verification of rich functional properties. It encodes higher-order concerns into a first-order logic, which enables automation via SMT solvers. Our technique is implemented as an extension of the deductive verifier Prusti, with which we have successfully verified many common idioms of closure usage., Proceedings of the ACM on Programming Languages, 5 (OOPSLA), ISSN:2475-1421

Home Energy Management Systems (HEMS) contain devices of multiple manufacturers. Also, a large number of groups of devices must be managed according to several clustering situations. Hence, since it is necessary to establish a common secret group key among group members, the group key management scheme of IEEE 802.21 is used. However, no security verification result by formal methods is known. In this paper, we give the first formal verification result of secrecy and authenticity of the group key management scheme of IEEE 802.21 against insider and outsider attacks using ProVerif, which is an automatic verification tool for cryptographic protocols. As a result, we clarify that a spoofing attack by an insider and a reply attack by an outsider are found for the basic scheme, but these attacks can be prevented by using the scheme with the digital signature option.

As quantum computers become real, it is high time we come up with effective techniques that help programmers write correct quantum programs. In classical computing, formal verification and sound static type systems prevent several classes of bugs from being introduced. There is a need for similar techniques in the quantum regime. Inspired by Hoare Type Theory in the classical paradigm, we propose Quantum Hoare Types by extending the Quantum IO Monad by indexing it with pre- and post-conditions that serve as program specifications. In this paper, we introduce Quantum Hoare Type Theory (QHTT), present its syntax and typing rules, and demonstrate its effectiveness with the help of examples. QHTT has the potential to be a unified system for programming, specifying, and reasoning about quantum programs. This is a work in progress., Comment: In Proceedings QPL 2020, arXiv:2109.01534. See expanded version at arXiv:2012.02154

P systems are widely used to solve computationally hard problems. In this study, we formally verify cP systems (P systems with complex objects) in the Coq proof assistant, and provide a corresponding open source library. To help transform cP notation into Gallina, we propose two sets of modelling guidelines. Comparing to existing P system formal verification studies, our approach shows many advantages and has great potential. To the best of our knowledge, this is the first study to formally verify membrane computing models using an interactive theorem prover.

Rigorous reasoning about programs calls for some amount of bureaucracy in managing details like variable binding, but, in guiding students through big ideas in semantics, we might hope to minimize the overhead. We describe our experiment introducing a range of such ideas, using the Coq proof assistant, without any explicit representation of variables, instead using a higher-order syntax encoding that we dub "mixed embedding": it is neither the fully explicit syntax of deep embeddings nor the syntax-free programming of shallow embeddings. Marquee examples include different takes on concurrency reasoning, including in the traditions of model checking (partial-order reduction), program logics (concurrent separation logic), and type checking (session types) -- all presented without any side conditions on variables.

When designing Wireless Sensor Networks it is important to analyze their security risks and provide adequate solutions for protecting them from malicious attacks. Unfortunately, perfect security cannot be achieved, for performance reasons. Therefore, designers have to devise security priorities, and select security mechanisms accordingly. However, in the early stages of the design process, the concrete effects of security attacks on the system may not be clearly identified. In this paper, we propose a framework that integrates formal verification and network simulation for enabling designers to evaluate the effects of attacks, identify possible security mechanisms, and evaluate their effectiveness, since design time. Formal methods are used to build the abstract model of the application, together with a set of attacks, and to state properties of general validity. The simulator measures the impact of the attacks in terms of common network parameters, like energy consumption or computational effort. Such information can be used to select adequate security mechanisms, then the initial abstract model can be refined to adopt them, and finally prove that former system properties are still verified. The framework relies on UPPAAL for formal modeling and verification and uses the Attack Simulation Framework on top of Castalia as a network simulator. As proof of concept, a case study is shown.

An integral part of any project to create or assess the security of information systems and databases is the presence of a security model. The paper considers the main positions of the most common security models based on controlling the access of subjects to objects. The analysis of formal models for access control has revealed that each of them, having certain advantages and disadvantages, has the right to be used. The decisive factor in making a decision is an assessment of a specific situation, which will allow one to make the right choice. In this regard, the paper notes that security models based on discretionary policies are advisable to be applied when conducting formal verification of the correctness of building access control systems in well-protected information systems and databases. However, it is emphasized that these models have certain drawbacks that limit their use. The paper states that despite the fact that security models based on the mandatory access policy play a significant role in information security theory and their provisions have been introduced as mandatory requirements for systems that process secret information, as well as in the standards of secure systems, a number of problems may arise in the practical implementation of these models. Among these problems there are the problems associated with overestimating the security level, blind recordings, performing operations that do not fit into the framework of the model by privileged subjects. The paper also concludes that the use of security models based on role-based policy allows one to implement access control rules dynamically changing during the operation of information systems and databases, the effectiveness of which is especially noticeable when organizing access to the resources of systems with a large number of users and objects.

Time Petri nets (TPN) are successfully used in the specification and analysis of distributed systems that involve explicit timing constraints. Especially, model checking TPN is a hopeful method for the formal verification of such complex systems. For this, it is promising to lean to the construction of an optimized version of the state space. The well-known methods of state space abstraction are SCG (state class graph) and ZBG (graph based on zones). For ZBG, a symbolic state represents the real evaluations of the clocks of the TPN; it is thus possible to directly check quantitative time properties. However, this method suffers from the state space explosion. To attenuate this problem, the authors propose in this paper to combine the ZBG approach with the partial order reduction technique based on stubborn set, leading thus to the proposal of a new state space abstraction called reduced zone-based graph (RZBG). The authors show via case studies the efficiency of the RZBG which is implemented and integrated within the 〖TPN-TCTL〗_h^∆ model checking in the model checker Romeo.

Introduction: In developing safety and security critical systems, separation kernel acts as a primary foundation, which provides spatial as well as temporal separation. Separation kernel offers highly assured partitions to the applications hosted on the fundamentally critical systems and can also control the flow of information between them. The industries, as well as academia, have developed several separation kernels that have been broadly applied in critical systems like military/defense secured applications, avionics/aerospace intelligent systems, healthcare units that deal with human lives and in many more areas. The increasing popularity of separation kernels demands the formal verification that assures the correctness of the functionalities in it. Further, formal verification of separation kernels has become mandatory by the security/safety certification authorities. Conclusion: This paper first presents the concept of separation kernel, and then it discusses the functionalities, design, and properties of it. The classification and analysis of the formal languages are being presented in this paper that has been used for writing the specifications of separation kernel and verifying it. The paper is an attempt towards the classification of formal languages being used for the verification of several separation kernels.

Editor’s note: This article proposes a formal design system for automatically generating provably secure register transfer level description of cryptographic hardware based on generalized masking scheme. —Rosario Cammarota, Intel Labs —Francesco Regazzoni, University of Amsterdam and Universita della Svizzera Italiana

Industry applications of formal verification to signaling control tables require formulation of a large number of mathematical conjectures expressing verification rules. It is paramount to establish the validity and completeness of these conjectures. This article discusses a mutation-based validation technique that guides domain experts in the construction of such verification rules. Furthermore, we use genetic programming to quickly generate millions of well-formed data mutations of control tables and to synthesize mutation programs. The technique is illustrated by a synthetic running example and a discussion of our experience in using it in the industrial setting.

Cloud computing is a new technology, providing different online resources and services to users. Load balancing has become an interesting research area in this field. A few existing scheduling algorithms can maintain load balancing and provide better strategies through efficient job scheduling and resource allocation techniques as well. In order to gain maximum profits with optimized load balancing algorithms, it is necessary to guarantee a service level along dimensions such as performance, availability and reliability. In this work, we propose a Model-based approach to study and analyze centralized and distributed dynamic load balancing protocols in the Cloud. The formal verification of different properties of the studied protocols has been performed automatically and a performance analysis allowing their comparison is also provided. In this paper, we show how aspects of performance, resource consumption, and reliability of the Cloud can be formally modeled, verified and analyzed using a component-based architecture.

Radio Frequency Identification (RFID) is an emerging technology that is used for the unique identification of objects. RFID can be used in different application domains, including Health-care systems, where the safety of patient-sensitive data is a primary concern. Since the RFID technology is used in various medicine sectors, particularly real-time patient monitoring, patient medicine Information, medical emergency, and drug administration system, the use of RFID raises severe security and privacy concerns. In order to cope with these security issues, we propose an Elliptic curve based authentication protocol for RFID. The proposed model uses an implicit certificate concept to secure health-care data. We prove this claim for secure communication using the formal security analysis, i.e., BAN logic, security analysis based on the mathematical model, i.e., ROR model, formal verification using AVISPA tool, and informal security analysis. We review some of the RFID authentication schemes based on ECC in terms of performance and security. Our analysis indicates that the proposed protocol provides mobility, scalability, security, and privacy in the health care environment.

We present the first specification and verification of an implementation of a causally-consistent distributed database that supports modular verification of full functional correctness properties of clients and servers. We specify and reason about the causally-consistent distributed database in Aneris, a higher-order distributed separation logic for an ML-like programming language with network primitives for programming distributed systems. We demonstrate that our specifications are useful, by proving the correctness of small, but tricky, synthetic examples involving causal dependency and by verifying a session manager library implemented on top of the distributed database. We use Aneris's facilities for modular specification and verification to obtain a highly modular development, where each component is verified in isolation, relying only on the specifications (not the implementations) of other components. We have used the Coq formalization of the Aneris logic to formalize all the results presented in the paper in the Coq proof assistant.

We present VOQC, the first fully verified optimizer for quantum circuits, written using the Coq proof assistant. Quantum circuits are expressed as programs in a simple, low-level language called SQIR, a simple quantum intermediate representation, which is deeply embedded in Coq. Optimizations and other transformations are expressed as Coq functions, which are proved correct with respect to a semantics of SQIR programs. SQIR uses a semantics of matrices of complex numbers, which is the standard for quantum computation, but treats matrices symbolically in order to reason about programs that use an arbitrary number of quantum bits. SQIR's careful design and our provided automation make it possible to write and verify a broad range of optimizations in VOQC, including full-circuit transformations from cutting-edge optimizers., This paper supercedes arXiv:1904.06319; version 2 includes additional results and improved formatting; version 3 is the final draft with additional formatting improvements and some restructuring

State-of-the-art software technologies have enabled Higher Education Institutions to record and store large amounts of student data. Analyzing this large amount of data can facilitate the decision-making process. Decisions made in higher education institutions affect policies, strategies and actions that improve education quality. It can be argued that machine learning algorithms demonstrate a remarkable ability to recognize models and predict results based on data. However, machine learning outcomes were subject to bias and erroneous labelling. Consequently, to mitigate the impact of such errors in decision making, it is necessary to put in place mechanisms to correct decision rules. This article presents an approach to learn decision rules through supervised machine learning and proves the correctness of these rules with hierarchical Coloured Petri Nets. The use of formalism in the proposed methodology ensures that the decision rules are correct and comprehensible. Empirical results show that we improved correctness with 98.68% accuracy on decision rules. This research work contributes to the improvement of the decision-making process for the academic administration of Higher Education Institutes.

Formal verification can mathematically prove whether a software satisfies the requirements described in its design. In traditional software development, even if the software systems, especially the operating system for Internet of Things in smart cities, passes the verification test, it is difficult to explain its correctness. The implementation of formal verification after the design and development process proves that the software system meets the expected requirements. This will become a trend for future software development. In this paper, we model the system state of the X86 architecture on the assembly layer, and use a micro operating system prototype for Internet of Things in smart cities as an example to explain the proposed method that can verify operating systems for Internet of Things in smart cities on the assembly layer. The verification result shows that this method is feasible.

Communication is a key element of everyone's life. Nowadays, we most often use internet connections for communication. We use the network to communicate with our family, make purchases, we operate home appliances, and handle various matters related to public administration. Moreover, the Internet enables us to participate virtually in various official meetings or conferences. There is a risk of losing our sensitive data, as well as their use for malicious purposes. In this situation, each connection should be secured with an appropriate security protocol. These protocols also need to be regularly checked for vulnerability to attacks. In this article, we consider a tool that allows to analyze different executions of security protocols as well as simulate their operation. This research enables the gathering of knowledge about the behaviour of the security protocol, taking into account various time parameters (time of sending the message, time of generation confidential information, encryption and decryption times, delay in the network, lifetime) and various aspects of computer networks. The conducted research and analysis of the obtained results enable the evaluation of the protocol security and its vulnerability to attacks. Our approach also assumes the possibility of setting time limits that should be met during communication and operation of the security protocol. We show obtained results on Andrew and Needham Schroeder Public Key protocols examples.

The Internet of Things (IoT) is becoming an increasingly common paradigm. As IoT usage scenarios have increased, many challenges in IoT operating systems’ safety and adaptability have remained. According to the programming model, IoT operating systems can be categorized into three types: multithreading, event-driven, and hybrid. Different operating system models are applied in different scenarios depending on the real-time requirements or resource richness. The safety of IoT operating systems is critical; hence, formal verification is an important method of detecting potential vulnerabilities and providing safety guarantees. This paper proposes a hybrid model for an IoT operating system and employs the Event-B method for modeling and verification. We rewrite the requirements and divide the Event-Bus hybrid operating system model into eight levels for refinement. The safety and liveness properties of Event-Bus are guaranteed by generating and proving the proof obligations at each model level. A large proportion of the proof obligations (91%) are automatically proven on the Rodin platform to simplify the development process.

In the future, assistive robots will spread to everyday settings and regularly interact with humans. This paper introduces a deployment approach for assistive robotic applications where human-robot interaction is the main element. The deployment infrastructure hinges on a model-to-code transformation technique and a ROS-based middleware layer and enables deployment in real life or simulation in a virtual environment. The approach fits into a model-driven framework for the formal verification of interactive scenarios. At design-time, the application analyst estimates the most likely outcome of the robotic mission through Statistical Model Checking of a Stochastic Hybrid Automata network modeling the scenario. We introduce an innovative approach to convert a specific subset of Stochastic Hybrid Automata into executable code to control the robot and respond to human actions. Deploying or simulating the application allows analysts to validate the results obtained at design time or to refine the formal model based on runs in the real or the virtual scene. The methodology’s effectiveness is tested via simulation of use cases from the healthcare setting, which can significantly benefit from this kind of approach thanks to its innovative features related to human physiology and autonomous behavior.

The state-of-the-art SAT solvers usually share the same core techniques, for instance: the watched literals structure, conflict clause recording and non-chronological backtracking. Nevertheless, they might differ in the elimination of learnt clauses, as well as in the decision heuristic. This article presents a framework for generating configurable SAT solvers. The proposed framework is composed of the following components: a Base SAT Solver, a Perl Preprocessor, XML files (Solver Description and Heuristics Description files) to describe each heuristic as well as the set of heuristics that the generated solver uses. This solvers may use several techniques and heuristics such as those implemented in BerkMin, and in Equivalence Checking of Dissimilar Circuits, and also in Minisat. In order to demonstrate the effectiveness of the proposed framework, this article also presents three distinct SAT solver instances generated by the framework to address a complex and challenging industry problem: the Combinational Equivalence Checking problem (CEC).The first instance is a SAT solver that uses BerkMin and Dissimilar Circuits core techniques except the learnt clause elimination heuristic that has been adapted from Minisat; the second is another solver that combines BerkMin and Minisat decision heuristics at run-time; and the third is yet another SAT solver that changes the database reducing heuristic at run-time. The experiments demonstrate that the first SAT solver generated is a faster solver than state-of-the-art SAT solver BerkMin for several instances as well as for Minisat in almost every instance.

In this paper we consider the software architecture of InnoChain, a distributed ledger system (DLS) with 5 levels of formal verification, including a formally-verified underlying operating system (OS). The objective of this architecture is to achieve a higher level of DLS dependability compared to more traditional software architectures and quality assurance (QA) methods. The architecture of InnoChain includes (1) a programming language for smart contracts which is a domain-specific language with formal semantics embedded into CakeML, which is a functional language ofthe ML family; this allows us to carry out formal verification of smart contracts' correctness properties using higher-order logic systems, such as HOL4; (2) trusted compilation of smart contracts into the machine code using the verified compiler available for CakeML, rather than relying on a virtual machine for execution of smart contracts; (3) using CakeML for implementation of InnoChain node functionality which allows for formal verification of code correctness and trusted compilation into the machine code; (4) formal verification of the consensus protocol used InnoChain, namely HotStuff BFT; (5) using seL4, a formally-verified microkernel, as the underlying OS for InnoChain instead of more traditional general-purpose OSes such as Linux. The proposed verified architecture will allow InnoChain to be used in mission-critical applications, such as the decentralized Aircraft Fuelling Control System which is currently under development for JSC Aeroflot, the Russian national air carrier.

Change of artefact-centric business process instances is important for an enterprise to keep competitive. However, to preserve the correctness of changes of an artefact-centric business process instance is still a big challenge. The hardness mainly stems from the fact that whether a business process instance can reach a final state has been proved to be undecidable. As such, finding a reliable verification algorithm for preserving correctness becomes impossible. In this study, the authors propose a random-forest-based approach to predict the correctness of changes in a business process instance. The availability of the proposed method is validated by comparing it to the traditional formal verification method. They also propose two optimisations of the proposed method and validate their effectiveness through extensive experimental analysis.

Reflex is a process-oriented language that provides a design of easy-to-maintain control software for programmable logic controllers. The language has been successfully used in a several reliability critical control systems, e. g. control software for a silicon single crystal growth furnace and electronic equipment control system. Currently, the main goal of the Reflex language project is to develop formal verification methods for Reflex programs in order to guarantee increased reliability of the software created on its basis. The paper presents the formal operational semantics of Reflex programs extended by annotations describing the formal specification of software requirements as a necessary basis for the application of such methods. A brief overview of the Reflex language is given and a simple example of its use – a control program for a hand dryer – is provided. The concepts of environment and variables shared with the environment are defined that allows to disengage from specific input/output ports. Types of annotations that specify restrictions on the values of the variables at program launch, restrictions on the environment (in particular, on the control object), invariants of the control cycle, pre- and postconditions of external functions used in Reflex programs are defined. Annotated Reflex also uses standard annotations assume, assert and havoc. The operational semantics of the annotated Reflex programs uses the global clock as well as the local clocks of separate processes, the time of which is measured in the number of iterations of the control cycle, to simulate time constraints on the execution of processes at certain states. It stores a complete history of changes of the values of shared variables for a more precise description of the time properties of the program and its environment. Semantics takes into account the infinity of the program execution cycle, the logic of process transition management from state to state and the interaction of processes with each other and with the environment. Extending the formal operational semantics of the Reflex language to annotations simplifies the proof of the correctness of the transformation approach to deductive verification of Reflex programs developed by the authors, transforming an annotated Reflex program to an annotated program in a very limited subset of the C language, by reducing a complex proof of preserving the truth of program requirements during the transformation to a simpler proof of equivalence of the original and the resulting annotated programs with respect to their operational semantics.

User-friendly formal specification and verification of concurrent and distributed systems for various domains, such as automatic control systems, telecommunications, and business processes, are active research topics due to their practical significance. In this paper, we present methods of developing verification-oriented domain-specific process ontologies used to describe concurrent systems of subject domains. One of the advantages of such ontologies is their formal semantics, which provides formal verification of the described systems. Our method is based on an abstract verification-oriented process ontology. We use two methods of domain specialization of the abstract process ontology. The declarative method relies on specializing classes of the original ontology, introducing new declarative classes, and using a new set of axioms to set restrictions on classes and relations of the abstract ontology. The constructive method uses semantic markup and pattern matching techniques to link domain concepts to classes of the abstract process ontology. We provide detailed ontological specifications for these techniques. Our methods preserve the formal semantics of the original process ontology; therefore, formal verification methods can be applied to the resulting domain-specific process ontologies. We demonstrate that the constructive method is a refined version of the declarative method. We illustrate our methods on the example of constructing an ontology for standard elements of automatic control systems: we develop declarative descriptions of the classes and restrictions of the domain-specific ontology in the Protege system in the Web Ontology Language (OWL) using inference rules written in the Semantic Web Rule Language (SWRL) and construct a system of semantic markup patterns that implements standard elements of automatic control systems.

Software products are evolving during their life cycles. Ideally, every revision need be formally verified to ensure software quality. Yet repeated formal verification requires significant computing resources. Verifying each and every revision can be very challenging. It is desirable to ameliorate regression verification for practical purposes. In this paper, we regard predicate analysis as a process of assertion annotation. Assertion annotations can be used as a certificate for the verification results. It is thus a waste of resources to throw them away after each verification. We propose to reuse the previously-yielded assertion annotation in regression verification. A light-weight impact-analysis technique is proposed to analyze the reusability of assertions. A novel assertion strengthening technique is furthermore developed to improve reusability of annotation. With these techniques, we present an incremental predicate analysis technique for regression verification. Correctness of our incremental technique is formally proved. We performed comprehensive experiments on revisions of Linux kernel device drivers. Our technique outperforms the state-of-the-art program verification tool CPAchecker by getting 2.8x speedup in total time and solving additional 393 tasks.

Formally verifying software correctness is a highly manual process. However, because verification proof scripts often share structure, it is possible to learn from existing proof scripts to fully automate some formal verification. The goal of this paper is to improve proof script synthesis and enable fully automating more verification. Interactive theorem provers, such as the Coq proof assistant, allow programmers to write partial proof scripts, observe the semantics of the proof state thus far, and then attempt more progress. Knowing the proof state semantics is a significant aid. Recent research has shown that the proof state can help predict the next step. In this paper, we present TacTok, the first technique that attempts to fully automate proof script synthesis by modeling proof scripts using both the partial proof script written thus far and the semantics of the proof state. Thus, TacTok more completely models the information the programmer has access to when writing proof scripts manually. We evaluate TacTok on a benchmark of 26 software projects in Coq, consisting of over 10 thousand theorems. We compare our approach to five tools. Two prior techniques, CoqHammer, the state-of-the-art proof synthesis technique, and ASTactic, a proof script synthesis technique that models proof state. And three new proof script synthesis technique we create ourselves, SeqOnly, which models only the partial proof script and the initial theorem being proven, and WeightedRandom and WeightedGreedy, which use metaheuristic search biased by frequencies of proof tactics in existing, successful proof scripts. We find that TacTok outperforms WeightedRandom and WeightedGreedy, and is complementary to CoqHammer and ASTactic: for 24 out of the 26 projects, TacTok can synthesize proof scripts for some theorems the prior tools cannot. Together with TacTok, 11.5% more theorems can be proven automatically than by CoqHammer alone, and 20.0% than by ASTactic alone. Compared to a combination of CoqHammer and ASTactic, TacTok can prove an additional 3.6% more theorems, proving 115 theorems no tool could previously prove. Overall, our experiments provide evidence that partial proof script and proof state semantics, together, provide useful information for proof script modeling, and that metaheuristic search is a promising direction for proof script synthesis. TacTok is open-source and we make public all our data and a replication package of our experiments.

International audience; Side-channel attacks are amongst the major threats for embedded systems and IoT devices. Masking is one of the most used countermeasure against such attacks, but its application remains a difficult process. We propose a target-independent approach for applying a first-order boolean masking countermeasure during compilation, on the static single assignment form. Contrary to state-of-the art automated approaches that require to simplify the control flow of the input program, our approach supports regular control-flow program structures. Moreover, our compiler is the first to automatically mask table lookups using a polynomial interpolation approach. We also present new optimisations to speed up the evaluation of polynomials: we reduce the number of terms of the polynomial, and we accelerate finite field multiplication. We show that our approach is faster than the standard masked table approach with mask refresh after each access, with speedups up to ×2.4 in our experiments. Finally, using a formal verification approach, we show that the compiled machine code is secure, i.e., that all intermediate computations are statistically independent of the secrets.

Collaborative text editing systems allow multiple users to concurrently edit the same document, which can be modeled by a replicated list object. In the literature, there is a family of operational transformation (OT)-based Jupiter protocols for replicated lists, including AJupiter, XJupiter, and CJupiter. They are hard to understand due to the subtle OT technique, and little work has been done on formal verification of complete Jupiter protocols. Worse still, they use quite different data structures. It is unclear about how they are related to each other, and it would be laborious to verify each Jupiter protocol separately. In this work, we make contributions towards a better understanding of Jupiter protocols and the relation among them. We first identify the key OT issue in Jupiter and present a generic solution. We summarize several techniques for carrying out the solution, including the data structures to maintain OT results and to guide OTs. Then, we propose an implementation-independent AbsJupiter protocol. Finally, we establish the (data) refinement relation among these Jupiter protocols (AbsJupiter included). We also formally specify and verify the family of Jupiter protocols and the refinement relation among them using TLA+ (TLA stands for “Temporal Logic of Actions”) and the TLC model checker. To our knowledge, this is the first work to formally specify and verify a family of OT-based Jupiter protocols and the refinement relation among them. It would be helpful to promote a rigorous study of OT-based protocols.

This paper presents a new Property-Driven Design (PDD) method that starts from an abstract system model and integrates formal property checking early into a top-down design methodology for register transfer level (RTL) hardware. In PDD the role of formal verification is not limited to “bug hunting” alone. Instead, the formal techniques are applied in such a way that a formal relationship is provided between the abstract system model and its concrete implementation at the RTL. In order to avoid the high efforts associated with verification by property checking the proposed PDD approach automatically generates abstract properties from a system-level description and later refines them along the design process. The advantage of this methodology is to obtain a formally verified design at lower costs when compared to conventional design flows with property checking. The main benefit of the proposed approach results from the fact that a formally sound system model is available together with the RTL design. Specifically, LTL properties proven on the abstract model also hold on the concrete implementation. This facilitates many complex analysis and verification tasks in today’s design flows and contributes to emancipating system-level models from prototypes to golden design models. Several open-source and industrial case studies are reported that demonstrate the high potential of a PDD-based design paradigm.

Unmanned Aerial Vehicle (UAV) has extensively been practiced in the military and civilian surveillance systems that access sensitive data over the cellular networks. However, channel insecurity and battery limitation may not protect the aerial coverage area. Thus, sensitive information gathered through aerial vehicles causes security threats. To manage the security issues, Smart Internet of Drone (S-IoD) have been evolved to use Intelligent Personal Assistant (IPA) as a software agent while monitoring and observing areas of interest. The current state-of-the-art technologies provide ubiquitous communication to enable several Internet of Things (IoT) paradigms. It achieves a feature of a decision support system that allows the smart interaction and communication between real-time entities. IPA offers smart interaction with other smart real-time entities to gain the user’s knowledge and awareness. This paper presents an S-IoD framework for a UAV environment that independently collects sensible information. In order to reduce the computation cost of the authentication protocol, a lightweight privacy-preserving scheme (L-PPS) is introduced. The proposed L-PPS is constructive to provide the robustness between the IoT devices with a valid authentication period. To demonstrate the security and performance efficiencies, the formal verification was performed using a verification tool, Scyther, and a random oracle model. In addition, the proposed L-PPS introduces a secret token and dynamic user authentication to speed up the authentication process between the communication entities. Importantly, the authentication session of L-PPS does not use any complex cryptographic operations, whereby it has less computation and communication costs to meet the standard constraints of surveillance systems. Moreover, the obtained simulation analysis proves that the proposed L-PPS achieves better quality metrics than other authentication schemes in the literature.

The authors present a theoretical proposal for the organization of mathematical contents, more precisely to curricula development formalization and formal verification, inspired by knowledge engineering techniques. The situation addressed is the following: the starting point is a mathematical “official curriculum” (or part of it), not necessarily completely detailed. In our proposal, a group of experts would have to first build a detailed formulation of this curriculum (including the “prerequisite” relation between contents), which we will denominate “preprocessed official curriculum.” We detail how any “official curriculum development” could then be rigorously formalized and formally verified in a way inspired by rule-based expert system formal verification. We have defined the following terms: “contents soundness,” “contents completeness,” “relation soundness,” “relation completeness,” and “absence of cycles.” We believe that this is a completely new formalization within mathematics teaching theory that, once computer is implemented, would be very helpful. That would be the case, for instance, in countries where government sets the “official curricula” for Primary and Secondary Education and textbook contents have to be manually checked and approved by academic authorities: evaluators would “only” have to extract the textbook contents and set the “prerequisite” relation among them and let the computer do the rest.

In this paper, we study the problem of formal verification for Answer Set Programming (ASP), namely, obtaining a formal proof showing that the answer sets of a given (non-ground) logic program P correctly correspond to the solutions to the problem encoded by P, regardless of the problem instance. To this aim, we use a formal specification language based on ASP modules, so that each module can be proved to capture some informal aspect of the problem in an isolated way. This specification language relies on a novel definition of (possibly nested, first order) program modules that may incorporate local hidden atoms at different levels. Then, verifying the logic program P amounts to prove some kind of equivalence between P and its modular specification. Under consideration for acceptance in TPLP., Comment: Paper presented at the 36th International Conference on Logic Programming (ICLP 2019), University Of Calabria, Rende (CS), Italy, September 2020, 16 pages

An approach for formal verification of UML 2.0 using mapping OWL-DL in UML 2.0 is proposed. As a result, an original approach for mapping OWL-DL to UML 2.0 through description logic has been proposed. The completeness of the mapping of UML-OWL through stereotypes and labeled UML 2.0 values at the level of M0, M1 of the MOF metamodel is provided. A model of the information object (IO) for the semantic electronic library, which is described by using the UML language, is proposed. The proposed IO model was also verified by mapping it into OWL and then validating the constructed ontology by using risoners. Problems in programming 2020; 2-3: 31-38

One of the major challenges in the formal verification of embedded system software is the complexity and substantially large size of the implementation. The problem becomes crucial when the embedded system is a complex medical device that is executing convoluted algorithms. In refinement-based verification, both specification and implementation are expressed as transition systems. Each behavior of the implementation transition system is matched to the specification transition system with the help of a refinement map. The refinement map can only project those values from the implementation which are responsible for labeling the current state of the system. When the refinement map is applied at the object code level, numerous instructions map to a single state in the specification transition system called stuttering instructions. We use the concept of Static Stuttering Abstraction (SSA) that filters the common multiple segments of stuttering instructions and replaces each segment with a merger. SSA algorithm reduces the implementation state space in embedded software, subsequently decreasing the efforts involved in manual verification with WEB refinement. The algorithm is formally proven for correctness. SSA is implemented on the pacemaker object code to evaluate the effectiveness of abstracted code in verification process. The results helped to establish the fact that, despite code size reduction, the bugs and errors can still be found. We implemented the SSA technique on two different platforms and it has been proven to be consistent in decreasing the code size significantly and hence the complexity of the implementation transition system. The results illustrate that there is considerable reduction in time and effort required for the verification of a complex software control, i.e., pacemaker when statically stuttering abstracted code is employed.

The increasing complexity of reactive systems can be mitigated with the use of components and composition languages in model-driven engineering. Designing composition languages is a challenge itself as both practical applicability (support for different composition approaches in various application domains), and precise formal semantics (support for verification and code generation) have to be taken into account. In our Gamma Statechart Composition Framework, we designed and implemented a composition language for the synchronous, cascade synchronous and asynchronous composition of statechart-based reactive components. We formalized the semantics of this composition language that provides the basis for generating composition-related Java source code as well as mapping the composite system to a back-end model checker for formal verification and model-based test case generation. In this paper, we present the composition language with its formal semantics, putting special emphasis on design decisions related to the language and their effects on verifiability and applicability. Furthermore, we demonstrate the design and verification functionality of the composition framework by presenting case studies from the cyber-physical system domain.

Peer (P2P) networks have emerged as an efficient and affordable means of transmitting videos to numerous end-users via the Internet. The dynamic and heterogeneous nature of P2P streaming systems (P2PSS) makes testing, analyzing and verification a cumbersome task. However, formal methods offer efficient approaches to rigorously analyze and verify P2PSS. This paper demonstrates the use of formal verification techniques for analyzing the behavioral properties of P2PSS. We use temporal logics to analyze whether all the possible behaviors within the P2P streaming systems conform to the defined specifications. Specifically, we apply model checking to check the consistency, completeness and certainty of the model if the temporal properties of the proposed system satisfies the required specifications. Furthermore, the P2PSS framework was modeled and verified using Simulink Design Verifier (SDV) in MATLAB simulation tool. The simulations results showed 100% validation for all frames and 50% validation for I-frames prioritisation. Further, the probability of a peer capable of forwarding frames while receiving is at most 0.5.

In order to achieve the highest safety integrity levels, ISO26262 recommends the use of formal methods for various verification activities, throughout the lifecycle of safety-related embedded systems for road vehicles. Since formal methods are known to be difficult to use, one of the main challenges raised by these ISO26262 requirements is to find cost-effective approaches for being compliant with them. This paper proposes an approach for requirements formal verification where formal methods, languages, and tools are only minimally exposed to the user, and are integrated into one of the commonly used system modeling environments based on SysML. This approach does not require particular expertise in formal methods still allowing to apply them. Hence, personnel training costs and development costs should be kept limited. The proposed approach has been implemented as a plugin of the Topcased environment. Although it is limited to discrete system models, it has been successfully experimented on an industrial use case.

We study the problem of formally and automatically verifying robustness properties of decision tree ensemble classifiers such as random forests and gradient boosted decision tree models. A recent stream of works showed how abstract interpretation, which is ubiquitously used in static program analysis, can be successfully deployed to formally verify (deep) neural networks. In this work we push forward this line of research by designing a general and principled abstract interpretation-based framework for the formal verification of robustness and stability properties of decision tree ensemble models. Our abstract interpretation-based method may induce complete robustness checks of standard adversarial perturbations and output concrete adversarial attacks. We implemented our abstract verification technique in a tool called silva, which leverages an abstract domain of not necessarily closed real hyperrectangles and is instantiated to verify random forests and gradient boosted decision trees. Our experimental evaluation on the MNIST dataset shows that silva provides a precise and efficient tool which advances the current state of the art in tree ensembles verification.

Statechart notations with ‘run to completion’ semantics, are popular with engineers for designing controllers that respond to events in the environment with a sequence of state transitions. However, they lack formal refinement and rigorous verification methods. Open image in new window , on the other hand, is based on refinement from an initial abstraction and is designed to make formal verification by automatic theorem provers feasible. We introduce a notion of refinement into a ‘run to completion’ statechart modelling notation, and leverage Open image in new window tool support for theorem proving. We describe the difficulties in translating ‘run to completion’ semantics into Open image in new window refinements and suggest a solution. We outline how safety and liveness properties could be verified.

As one type of machine-learning model, a "decision-tree ensemble model" (DTEM) is represented by a set of decision trees. A DTEM is mainly known to be valid for structured data; however, like other machine-learning models, it is difficult to train so that it returns the correct output value for any input value. Accordingly, when a DTEM is used in regard to a system that requires reliability, it is important to comprehensively detect input values that lead to malfunctions of a system (failures) during development and take appropriate measures. One conceivable solution is to install an input filter that controls the input to the DTEM, and to use separate software to process input values that may lead to failures. To develop the input filter, it is necessary to specify the filtering condition of the input value that leads to the malfunction of the system. Given that necessity, in this paper, we propose a method for formally verifying a DTEM and, according to the result of the verification, if an input value leading to a failure is found, extracting the range in which such an input value exists. The proposed method can comprehensively extract the range in which the input value leading to the failure exists; therefore, by creating an input filter based on that range, it is possible to prevent the failure occurring in the system. In this paper, the algorithm of the proposed method is described, and the results of a case study using a dataset of house prices are presented. On the basis of those results, the feasibility of the proposed method is demonstrated, and its scalability is evaluated.